Páginas

Mostrando entradas con la etiqueta algoritmos. Mostrar todas las entradas
Mostrando entradas con la etiqueta algoritmos. Mostrar todas las entradas

miércoles, 6 de marzo de 2013

Modelo vista controlador MVC

Introducción:

Cuando programamos siempre deberíamos tener tres componentes  básicos, la interfaz para el usuario, la lógica del negocio y un componte que conecte estos dos elementos; los docentes de programación y software siempre intentan que separemos estos componentes para tener una mayor organización y rendimiento en nuestros proyectos, sin embargo nosotros nos resistimos a este cambio con la excusa de "que estos funcionan igual" o "yo entiendo mi desorden", la idea de este articulo es contribuir a mejorar en estos aspectos y dar una introducción al paradigma de modelo vista controlador de ahora en adelante MVC.

El patrón de arquitectura de programación MVC descrito por primera vez en 1979 por Trygve Reenskaug, un programador que trabajaba en los laboratorio de investigación de Xerox, 33 años despues se sigue usando y ha tomado mucha fuerza con el desarrollo web.

Elementos:

La idea es muy simple, separar nuestro código en tres grupos:

La lógica del negocio: MODELO
La la interfaz de usuario: VISTA
La conexión entre el modelo y la vista: CONTROLADOR

Modelo: son las partes de la aplicación que implementan la lógica del negocio, a menudo estos recuperan y almacenan los objetos que están registrados en una base de datos. En este caso se haría referencia a las clases genéricas que creamos como "Persona", "Animal", "Universidad", entre otras, estas clases son representaciones estructurales de sus similares en el mundo real, tienen atributos (características del objeto) y métodos(operaciones relacionadas con el objeto).

Vista: son los componentes que muestran la interfaz de usuario de la aplicación (UI), esta interfaz se crea a partir de los datos del modelo y sirve para que el usuario final interactue con la aplicación. En este caso se habla de lo que ve el usuario la aplicación, osea la estructura con botones, campos de texto, casillas de verificación, párrafos entre otros, y las características de estos elementos.

Controlador: son los componentes que manejan la interacción del usuario, con el modelo de trabajo, y finalmente seleccionan una vista para mostrar información al usuario. En este caso es la parte que controla las interacciones del usuario y dependiendo el caso administra que modelos y que vistas usar para responder a estas interacciones, como las clases que se encargaban de controlar los eventos de los dispositivos de entrada del computador en los primeros programas que realizamos.

Ejemplo:

En una restaurante también se separa las funciones:



En la cocina se maneja la lógica del negocio, se prepara la comida y se organizan los platos este componente seria el modelo.



En la recepción se manejan los pedidos ( a cada cliente se le tiene que mandar preparar el plato que pidió) osea este seria el controlador. 




Y por ultimo los meseros serian la vista pues son quienes tratan con los usuarios finales. 


Proceso del  MVC

1. El usuario interactúa con la aplicación de alguna forma (por medio de algún elemento de la vista, como un botón o la pulsación de una tecla).

2. Se dispara el evento y el controlador lo recibe la notificación de la acción solicitada por el usuario (se entera que el usuario realizo una interacción).

3. El controlador gestiona el evento (decide que hacer con el).

4. El controlador accede al modelo y realiza la operación pertinente (generalmente se realiza un acceso a la información de la base de datos de la aplicación).

5. El controlador gestiona el despliegue de la vista adecuada ye en ella se reflejan los cambios en el modelo (la vista en si puede ser la misma pero la información del modelo ha cambiado).

6. La vista queda dispuesta para futuras interacciones del usuario.

MVC Architecture por http://developer.chrome.com


Ventajas de usar MVC:

  • Es más sencillo trabajar sobre una aplicación cuando esta esta ordenada y claramente separada en las áreas que se propone en MVC.
  • Es más fácil gestionar una aplicación que usa MVC, debido a las las interacciones de los usuarios pueden ser controladas.
  • Se mejora el campo de la reutilización de componentes.
  • Facilita las tareas de mantenimiento.
  • Los programas se vuelven más escalables (lo que quiere decir que si se añade elementos o se modifica el programa no se tienen tantos problemas).
Conclusiones:

El MVC esta siendo muy usado en el desarrollo web y es prácticamente un estándar de facto en el desarrollo actual de aplicaciones, por ello es importante conocerlo y usarlo desde nuestros proyectos más básicos.




lunes, 27 de agosto de 2012

Búsqueda Secuencial



Teoría


La búsqueda secuencial es un algoritmo de búsqueda donde se evalúan los elementos uno por uno hasta llegar con el que se está buscando o en su defecto hasta llegar al final.
Se usa en conjuntos que no están ordenados, algo que hay que destacar es que como se compara con todos los elementos, no se puede saber si un elemento está en el conjunto hasta evaluar todos.

Caso de estudio


Ud. está en una fiesta y alguien le pide el favor de llevar una bebida a un invitado que Ud. no conoce, los invitados están recostados contra la pared en forma de fila y el único dato que le dan es el nombre: “Alejandra”.
secu_01.png
La idea es preguntarles a todos hasta llegar con la persona que se está buscando.

-¿Sujeto 1 Ud. se llama “Alejandra”?
-No, pero la vi por ahí.
secu_02.png

-¿Sujeto 2 Ud. se llama “Alejandra”?
-No, ¡yo soy hombre que le pasa!
secu_03.png

-¿Sujeto 3 Ud. se llama “Alejandra”?
-Sí, esa bebida es para mí gracias.
secu_04.png

En este caso solo le preguntamos a 3 personas, pero se puede dar el caso que la primera persona a la que le preguntemos sea la que estamos buscando, así como que sea la última o simplemente que no esté pero para eso hay que verificar todos los elementos.

Algoritmo


Se identificó el siguiente algoritmo teniendo en cuenta el caso de estudio:

1. Verificar el primer elemento de la lista
a. El elemento coincide con el que estamos buscado (fin).
b. El elemento NO coincide con el que estamos buscado, se continúa con el paso 2.
2. Se continúa con el siguiente elemento, vuelve al paso 1 pero teniendo como primer elemento de la lista este elemento (este paso se repite hasta que no existan elementos en la lista en este caso el elemento no está en la lista).

Búsqueda binaria


Teoria

Este algoritmo se usa para buscar elementos en un conjunto de datos ordenados tipo lista.

La idea es la siguiente, usando el principio divide y vencerás ir limitando el rango de búsqueda, como cuando se busca una página de un libro, se abre el libro en una página al azar, si está más adelante pues pasamos un grupo de páginas así delante de lo contrario nos devolvemos, reduciendo el rango de búsqueda hasta llegar a la página buscada.
Se compara el elemento a buscar, con un elemento central de la lista, si este elemento central es mayor que el del elemento buscado, se toma el intervalo inferior (del inicio a la mitad de la lista, en caso contrario se toma la parte de superior (que va desde el elemento de la mitad hasta el final); en los dos casos, se repite el procedimiento en la parte del lista seleccionada. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en toda la lista.

Caso estudio

Buscando en su ordenada colección de comics Alexander que hallar la edición 84 de “The Walking Dead”, lo haría de la siguiente manera.

bin_01.png

1. Se divide la lista en dos y se ubica el elemento de la mitad, en este caso TWD 77.

bin_02.png
2. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (77) es menor, entonces se toma la parte “superior” de la lista.

bin_03.png


bin_04.png



bin_05.png

3. Ahora se repite el procedimiento con la nueva lista, se toma el elemento de la mitad.

bin_06.png

4. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (99) es mayor, entonces se toma la parte “inferior” de la lista.

bin_07.png



bin_08.png


bin_09.png
5. Ahora se repite el procedimiento con la nueva lista, se toma el elemento de la mitad.

bin_10.png

6. Lo comparamos con el que queremos encontrar que es el 84, el elemento referencia (84) es mayor, como son igual quiere decir que ya encontramos el elemento que estábamos buscando y está en la posición 7.

bin_11.png

Algoritmo


1. Se busca el elemento de la mitad de la lista.
2. Se compara con el elemento que se está buscando.
a. Si el elemento de la mitad es mayor, se toma la parte de inferior de la lista (del primer elemento al de la mitad) vuelve al paso 1 pero con esta nueva sublista.
b. Si el elemento de la mitad es menor, se toma la parte de superior de la lista (del elemento de la mitad hay último elemento) vuelve al paso 1 pero con esta nueva sublista.
c. Si el elemento de la mitad es igual al elemento que estamos buscando se concluye la búsqueda exitosamente (fin).
d. Es el último elemento de la lista y no es igual al que se está buscando, el elemento no está en la lista (fin).

Ordenamiento por inserción


Teoría


En este algoritmo la idea es ordenar un conjunto de números realizando múltiples comparaciones iniciando con los dos primeros elementos del conjunto, luego agregando uno por uno hasta terminar con todos.

Caso de estudio


Imagine un juego de cartas, a usted le entregan su primera carta, que resulta ser un 5, este es su punto de referencia, al recibir la segunda carta obtiene un 3, en este momento se ubica el 3 a la izquierda del 5, ordenando las primeras dos cartas; la siguiente carta es un 7 la cual se compara con las cartas que ya tiene, de derecha a izquierda, al compararla con el 5 el 7 es mayor, y este queda de ultimo, a continuación recibe un 4, siguiente el método, se compara con la primera carta de la derecha, que es un 7, al ser menor el 4 continua comparando, se compara con el 5, al ser menor sigue comparando, se compara con el 3, al ser mayor se detiene en esa posición, la ultima carta es un 6, siguiente el método se compara con el 7, al ser menor pasa a comparar con el 5, pero al ser mayor que el 5 se detiene en esa posición, al final se obtienen las cartas ordenas.

1. Recibe el 5 y se ubica en la primera posición de izquierda a derecha.

1.jpg


2. Recibe el 3 y lo compara con el 5.

2.jpg

3. Al ser 3 menor que 5 se ubica en la primera posición a la izquierda.

3.jpg

4. Recibe 7 y lo compara con el 5.

4.jpg

5. Al ser 7 mayor que 5, se ubica 7 en la ultima posición después del 5, aunque el 7 sea mayor se debe realizar la comparación porque el computador es bruto.

4.jpg

6. Recibe 4 y se compara con 7.

5.jpg

7. Al ser 4 menor que 7, se continua comparando con 5.

6.jpg

8. Al ser 4 menor que 5, se continua comparando con 3.

7.jpg

9. Al ser 4 mayor que 3, se ubica el 4 entre el 3 y el 5.

7.jpg

10. Recibe 6 y se compara con 7.

8.jpg

11. Al ser 6 menor que 7, se continua comparando con 5.

9.jpg

12. Al ser 6 mayor que 5, se ubica el 6 entre el 5 y el 7.

9.jpg

13. Como ya no hay mas elementos las cartas están ordenadas.

9.jpg

NOTA: Si nos asignaran todas las cartas al mismo tiempo, la idea seria la misma pero la ejecución se haría de la siguiente manera:
250px-Insertion-sort-example-300px.gif
By Swfung8 (Own work) via Wikimedia Commons

Algoritmo


Para ordenar una lista de números(sin repetirse) de menor a mayor de izquierda a derecha usando "Ordenamiento por inserción".

1. Se toma el segundo elemento de izquierda a derecha de la lista a ordenar.
2. Se evalúa si existe un elemento anterior, de ser así continua al paso 3, de lo contrario al paso 4.
3. Se evalúa si dicho elemento es menor que el anterior.
3.1 Si es menor, se intercambian de posición, garantizando que el menor quede a la izquierda y se continua al paso 2.
3.2 En caso contrario, se conservan las posiciones iniciales y se continua con el paso 4.
4. Se vuelve al paso 2 con siguiente elemento de la lista hasta que no queden más.

Vídeo


Por si todavía no es claro, dejamos a su disposición un vídeo demasiado didáctico.










Enlaces recomendados


Libros:

  • Ejemplo completo y muy gráfico [Ingles]

Java 6 Illuminated: An Active Learning Approach, Julie Anderson y Hervé Franceschi, Pag. 516 a 524.

  • Explicación mas concreta.

Beginning Programming For Dummies, Wallace Wang, Pag. 216 a 223.

Ordenamiento por selección


Teoría


En este algoritmo el objetivo es ordenar una serie de números, buscando el menor elemento de la lista e intercambiándolo con el primero, se repite estos pasos con el resto de la lista hasta que la lista completa este ordenada.

Caso de estudio


Imagine que quiere ordenar un estante de libros, por tamaño de menor a mayor, tiene 5 libros con los siguiente tamaños:
  1. 12 cm
  2. 15 cm
  3. 10 cm
  4. 20 cm
  5. 13 cm

Acontinuacion se muestran los pasos necesarios para ordenar la lista.

1. Se inicia comparando los primeros dos libros de la lista, para determinar el de menor tamaño.

1.png

2. Como el menor es el libro de 12 cm se descarta el de 15 cm y se continua comparando con el tercer libro de la estante en este caso el de 10 cm.

2.png

3. Como el libro de 10 cm es el menor se descarta el de 12 cm y se continua comparando con el cuarto libro en este caso el de 20 cm.

3.png

4. Como el menor sigue siendo el de 10 cm se descarta el libro de 20 cm y se continua comparando con el ultimo libro , el de 13 cm.

4.png

5.Como el libro de 10 cm tiene el menor tamaño se cambia de posición con el primer libro.
5.png
6. Como el menor libro ya esta ubicado en su lugar, se debe continuar comparando con los libros restantes, se comparan el segundo y tercer libro.

sel_6.png

7. El menor es el libro de 12 cm, se descarta el de 15 cm y se continua comparando con el siguiente libro, de 20 cm.

sel_7.png

8. Como el menor sigue siendo el libro de 12 cm, se descarta el de 20 cm y se compara con el ultimo libro, de 13 cm.

sel_8.png

9. El menor es el libro de 12 cm, al no tener mas libros para comparar se cambia de lugar con el segundo libro, el de 15 cm,
9.png
10.El primer y segundo libro ya estan ubicados, se continua ordenando los libros restantes, se compara el tercer y cuarto libro.

10.png

11.Como el menor es el libro de 15 se descarta el de 20 cm y se continua comparando con el ultimo libro, de 13 cm.

11.png
12. Al ser el libro de 13 el menor y no tener mas libros para comparar, se cambia de lugar con el tercer libro.
12.png
13. Ya estan ordenados los primeros 3 libros, falta comparar los ultimos dos libros.

13a.png

14. como el menor es el libro de 15 se cambia de posición con el cuarto libro el de 20.
15a.png
15. De esta manera se organizan todos los libros del estante.

final.png


Algoritmo
Para ordenar una lista de números(sin repetirse) de menor a mayor usando "Ordenamiento por selección".
  • Buscar el mínimo elemento de la lista
  • Intercambiarlo con el primero
  • Buscar el mínimo en el resto de la lista
  • Intercambiarlo con el segundo (Primero de la sub-lista)
  • Continuar hasta que no queden elementos con los cuales comparar



Enlaces recomendados


Libros:

  • Ejemplo completo y muy gráfico [Ingles]

Java 6 Illuminated: An Active Learning Approach, Julie Anderson y Hervé Franceschi, Pag. 510 a 515.

Ordenamiento Burbuja


Teoría


También conocido como método de intercambio directo, consiste en comparar los elementos de una lista, tomando uno por uno, comparándolo con el siguiente y ordenándolo (si es menor se dejan igual, si no se cambian), siguiendo con los demás hasta terminar con todos los elementos y luego realzar este proceso varias veces.

Caso de estudio


Un estudiante quiere ordenar su colección de música por el año de lanzamiento de los álbumes.
Él cuenta con los siguientes discos:
DiscoAño de lanzamiento
Led Zeppelin III1970
Highway to Hell1979
The Rolling Stones No. 21966
My Generation1965
Bob Dylan1962

Nota: los valores en color azul se están comparando, en naranja siguen igual y en verde cambiaron de posición.

1. Se toma el primer disco que es Led Zeppelin III del año 1970 ahora se compara con el segundo Highway to Hell de 1979, como el primero es menor, se dejan igual.

1970-1979-1966-1965-1962
1970-1979-1966-1965-1962

2. Ahora se compara Highway to Hell de 1979 con The Rolling Stones No. 2 de 1966, en este caso el primer álbum es de un año posterior al del segundo, entonces se cambian.

1970-1979-1966-1965-1962
1970-1966-1979-1965-1962

3. Continuamos con Highway to Hell de 1979 pero ahora lo comparamos con My Generation de 1965, el primero es mayor entonces se cambian.

1970-1966-1979-1965-1962
1970-1966-1965-1979-1962

4. Continuamos con My Generation de 1965 y lo comparamos con el último elemento Bob Dylan de 1962, como el primero es mayor entonces se cambian.

1970-1966-1965-1979-1962
1970-1966-1965-1962-1979

¿Cómo vamos?
DiscoAño de lanzamiento
Led Zeppelin III1970
The Rolling Stones No. 21966
My Generation1965
Bob Dylan1962
Highway to Hell1979

Vamos bien pero hay elementos que siguen si organizarse, así que hay que hacer otra pasada, siguiendo el mismo procedimiento.

1. Volvemos a tomar el primer elemento que es “Led Zeppelin III” del año 1970 y lo comparamos con el segundo The Rolling Stones No. 2 de 1966, como el primero es mayor se cambian.

1970-1966-1965-1962-1979
1966-1970-1965-1962-1979

2. Ahora se compara Led Zeppelin III de 1970 con con My Generation de1965, como el primero es mayor se cambian.

1966-1970-1965-1962-1979
1966-1965-1970-1962-1979

3. Seguimos con Led Zeppelin III de 1970 y se compara con Bob Dylan de 1962 como el primero es de un año posterior se cambian.

1966-1965-1970-1962-1979
1966-1965-1962-1970-1979

4. Con Led Zeppelin III de 1970 se compara con Highway to Hell de 1979, como el primero es menor no hacemos ningún cambio.

1966-1965-1962-1970-1979
1966-1965-1962-1970-1979

¿Cómo vamos?
DiscoAño de lanzamiento
The Rolling Stones No. 21966
My Generation1965
Bob Dylan1962
Led Zeppelin III1970
Highway to Hell1979

Vamos bien pero hay elementos que siguen si organizarse, así que hay que hacer otra pasada, siguiendo el mismo procedimiento.

1. Volvemos a tomar el primer elemento que es The Rolling Stones No. 2 de 1966 comparamos con el segundo My Generation 1965, como el primero es mayor se cambian.

1966-1965-1962-1970-1979
1965-1966-1962-1970-1979

2. Volvemos a tomar el primer elemento que es The Rolling Stones No. 2 de 1966 se compara con Bob Dylan de 1962, como el primero es mayor los cambiamos.

1965-1966-1962-1970-1979
1965-1962-1966-1970-1979

3. Volvemos a tomar el primer elemento que es The Rolling Stones No. 2 de 1966 pero ahora comparamos Led Zeppelin III 1970, como el primero es menor entonces los dejamos así.

1965-1962-1966-1970-1979
1965-1962-1966-1970-1979

4. En este punto comparamos Led Zeppelin III 1970 con Highway to Hell de 1979, como el primero es menor no hacemos ningún cambio.

1965-1962-1966-1970-1979
1965-1962-1966-1970-1979

¿Cómo vamos?
DiscoAño de lanzamiento
My Generation1965
Bob Dylan1962
The Rolling Stones No. 21966
Led Zeppelin III1970
Highway to Hell1979

1. Volvemos a tomar el primer elemento que es My Generation 1965 se compara con Bob Dylan de 1962, el primero es mayor así que se cambian.

1965-1962-1966-1970-1979
1962-1965-1966-1970-1979


2. Continuamos con My Generation 1965 se compara The Rolling Stones No. 2 de 1966, como el primero es menor no hacemos ningún cambio.

1962-1965-1966-1970-1979
1962-1965-1966-1970-1979

3. Seguimos con The Rolling Stones No. 2 de 1966 se compara con Led Zeppelin III 1970, como el primero es menor se dejan igual.

1962-1965-1966-1970-1979
1962-1965-1966-1970-1979

4. Ahora Led Zeppelin III 1970 con Highway to Hell de 1979, también se dejan igual.

1965-1962-1966-1970-1979
1965-1962-1966-1970-1979

En este caso fueron necesarias 4 pasadas ósea una menos del número de elementos lo que nos indica que es necesario ejecutar n-1 pasadas y en cada pasada n-1 comparaciones.
Y listo tenemos los álbumes ordenados por año de lanzamiento.

DiscoAño de lanzamiento
Bob Dylan1962
My Generation1965
The Rolling Stones No. 21966
Led Zeppelin III1970
Highway to Hell1979

Notemos como en cada pasada los elemento mayores quedan al final de la lista, lo que significa que ya no es necesario ordenarlos, este es el punto de partida para el algoritmo de burbuja mejorado.

Algoritmo


Para ordenar una lista de números (sin elementos repetidos), de menor a mayor de izquierda a derecha usando “Ordenamiento Burbuja”.

1. Se toma el primer elemento y se compara con el de la derecha.
2. Se evalúa si dicho elemento (1°) es mayor al otro (2°) de ser así se continua en el paso 2.1 de lo contrario en el paso 2.2.
2.1 Se cambian de lugar los elementos garantizando que el menor quede a la izquierda.
2.2 Se dejan los elementos en el mismo orden.
3. Se continua repitiendo el paso uno hasta terminar con todos los elementos.
4. Se realiza el mismo procedimiento de los pasos 1-3 un número de veces igual al número de elementos a ordenar.