Actividad 1 Unidad IV


1. ¿Cuál de los métodos de ordenamiento consideras que tiene mayor aplicabilidad?

El método de la burbuja es el que más aplicabilidad tiene, ya que tiene una fácil implementación y no requiere memoria adicional, mientras que el QuickSort y Shell cuentan con implementaciones muy complejas y un tanto difíciles de entender, por ello es que pienso que el que más se aplica es el de la burbuja, aunque obviamente este tiene sus desventajas.

2. ¿Cuál de los métodos de búsqueda consideras que tiene mayor aplicabilidad?

Pienso que el método que más aplica es el de búsqueda binaria, ya que tarda menos en su tiempo de ejecución pese a que sólo realiza una comparación y no depende de los datos que están ya previamente establecidos, además no requiere de muchos elementos ordenados, en conclusión, es el de complejidad menor, por ello creo que es el que más se aplica.

CONCLUSIÓN

El tema de las ordenaciones y los métodos de búsqueda, es muy interesante desde el punto de vista computacional. Tiene su aplicación en la vida diaria cuando se tienen que ordenar cosas como fichas de un directorio personal, publicaciones periódicas por fecha, o paginas fotocopiadas que están en desorden. Sin duda esto adquiere mayor importancia ahora que las personas manejamos volúmenes de Información cada vez más grandes dada la revolución en las telecomunicaciones.

Tarea 1 Unidad IV



Algoritmos de Ordenamiento Interno 

Burbuja 

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. 

Ventajas: 

· Fácil implementación. 

· No requiere memoria adicional. 

Desventajas: 

· Muy lento. 

· Realiza numerosas comparaciones. 

· Realiza numerosos intercambios. 

QuickSort 

Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). 

Ventajas: 

· Muy rápido 

· No requiere memoria adicional. 

Desventajas:

· Implementación un poco más complicada. 

· Recursividad (utiliza muchos recursos). 

· Mucha diferencia entre el peor y el mejor caso. 

Shell 

Este método utiliza una segmentación entre los datos. Funciona comparando elementos que estén distantes; la distancia entre comparaciones decrece conforme el algoritmo se ejecuta hasta la última fase, en la cual se comparan los elementos adyacentes, por esta razón se le llama ordenación por disminución de incrementos. 

Ventajas: 

· No requiere de memoria adicional 

· Mejor rendimiento que el método de inserción clásico 

Desventajas: 

· Implementación algo confusa 

· Realiza numerosas comparaciones e intercambios 

Métodos de búsqueda 

Búsqueda Secuencial

Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. Y así poder encontrar el dato requerido. 

Mejor caso: Si tenemos mucha suerte, puede ser que la primera posición examinada contenga el elemento que buscamos, en cuyo caso el algoritmo informará que tuvo éxito después de una sola comparación. Por tanto, su complejidad será O (1). { 

Peor caso: Sucede cuando encontramos X en la última posición del array. Como se requieren n ejecuciones del bucle mientras, la cantidad de tiempo es proporcional a la longitud del array n, más un cierto tiempo para realizar las condiciones del bucle mientras y para la llamada al método. Por lo tanto, la cantidad de tiempo es de la forma an+ b para ciertas constantes ay b. En notación O, O (an+b) = O (an) = O(n). { 

Búsqueda Binaria 

La búsqueda binaria es el método, donde si el arreglo o vector está bien ordenado, se reduce sucesivamente la operación eliminando repetidas veces la mitad de la lista restante. El proceso comienza comparando el elemento central del arreglo con el elemento buscado. Si ambos coinciden finaliza la búsqueda. Si no ocurre así, el elemento buscado será mayor o menor en sentido estricto que el elemento central del arreglo. 

Caso optimo: La búsqueda binaria requiere sólo una comparación; esto significa que su tiempo de ejecución óptimo no depende de la cantidad de datos: es constante y por tanto proporcional a 1, es decir, O (1). { 

Peor caso: En el peor caso sí dependen de N. La búsqueda binaria divide el array, requiriendo sólo un tiempo O (logn). 

Búsqueda hashing 

En este método se requiere que los elementos estén ordenados. El método consiste en asignar el índice a cada elemento mediante una transformación del elemento, esto se hace mediante una función de conversión llamada función hash. Hay diferentes funciones para transformar el elemento y el número obtenido es el índice del elemento. 

Bibliografía: 



Actividad 3 Unidad III







Positivo: Tiene acceso rápido a la información, la memoria consumida está en función del número de nodos y del número de aristas, si el grafo es poco denso, se desaprovecha poca memoria. 


Negativo: Lo negativo de la implementación de los grafos es que Complejidad temporal para acceder a un nodo es O para el caso peor, además, si el grafo es denso se desaprovecha mucha memoria por las referencias o si el grafo es completo es cuando se desaprovecha el máximo de memoria. 

Interesante: Es interesante el hecho de que los grafos pueden ser cíclicos a diferencia de los árboles que ya vimos anteriormente. Para un grafo dado pueden existir muchos árboles cobertores. Si introducimos un concepto de "peso" (o "costo") sobre los arcos, es interesante tratar de encontrar un árbol cobertor que tenga costo mínimo. 

Conclusión: 

A partir de esta actividad se puede deducir lo siguiente, que un grafo es un conjunto de vértices y aristas, lo cuales se representan gráficamente como un conjunto de puntos llamados nodos y las aristas se representan por líneas o puentes que unen a los nodos. 

Los grafos tienen dos clasificaciones, los dirigidos y los no dirigidos, los primeros consisten en un conjunto de vértices y con conjunto de estos y aristas del grafo. Por otra parte los grafos no dirigidos se diferencian de un grafo dirigido debido a que cada arista en el conjunto, es un par no ordenado de vértices. 

Una diferencia con los árboles, se puede denotar que los árboles son grafos que no tienen ciclos y que conecta a todos los puntos, los grafos tienen múltiples aplicaciones dentro de la vida real, las cuales por mencionar algunas la redes de carreteras, la duración de los vuelos en un aeropuerto, las líneas de los ferrocarriles, los grafos tienen múltiples usos. 


Bibliografías: 






Tarea 3 Unidad III



GRAFOS
Un grafo está formado por un conjunto de nodos(o vértices) y un conjunto de arcos. Cada arco en un grafo se especifica por un par de nodos.
El conjunto de nodos es {A, B, C, D, F, G, H} y el conjunto de arcos {(A, B), (A, D), (A,
C), (C, D), (C, F), (E, G), (A, A)} para el siguiente grafo:


Si los pares de nodos en los arcos dirigidos, el grafo se denomina grafo directo, dirigido o dígrafo.

Terminología.
  • Vértice: Nodo
  •  Enlace: Conexión entre dos vértices (nodos).
  •  Adyacencia : Se dice que dos vértices son adyacentes si entre ellos hay un enlace directo.
  • Vecindad: Conjunto de vértices adyacentes a otro.
  • Camino: Conjunto de vértices que hay que recorrer para llegar desde un nodo origen hasta un nodo destino.
  • Grafo conectado: Aquél que tiene camino directo entre todos los nodos.
  • Grafo dirigido: Aquél cuyos enlaces son unidireccionales e indican hacia donde están dirigidos.
  • Gafo con pesos: Aquél cuyos enlaces tienen asociado un valor. En general en este tipo de grafos no suele tener sentido que un nodo se apunte a sí mismo porque el coste de este enlace sería nulo.


Matriz de adyacencia.


.-Un grafo sin ciclos es un árbol.
*.-El entregado de un nodo indica el número de arcos que llegan a ser nodo.
*.-El fuera de grado de un nodo indica el número de arcos que salen de él.
*.-Un grafo de N vértices o nodos es un árbol si cumple las siguientes condiciones
 a) Tiene N-1 arcos
 b) Existe una trayectoria entre cada par de nodos.
 c) Esta mínimamente conectado.


*.-Un grafo esta etiquetado si sus arcos tiene valores asignados. Si este valor es numérico
 se dice que el grafo tiene peso.

Recorrido de un grafo:

Hay dos tipos de recorridos de un grafo, y pueden ser implementados tanto de forma recursiva como de forma iterativa. Estos recorridos son:
  • En profundidad, que consiste en alejarse todo lo posible del nodo origen para después empezar a visitar los nodos restantes a la vuelta.
  •  A lo ancho (o por nivel), que consiste en visitar primero los nodos vecinos del origen, luego los vecinos de éstos, y así sucesivamente.



Bibliografía:



Actividad 2 Unidad III


¿Cuál de las dos estructuras consideras que tienen mayor aplicabilidad?
Va variando el contexto al cual va utilizado, pues consideramos que los arboles tienen una mayor aplicabilidad debido a que cuenta con la estructura dinámica similar a la lista, es por esto que cuenta con características similares, son viables para aplicación de direcciones complejas y estructuradas, para la búsqueda de claves, para los compiladores, diccionarios etc.
Positivo: En cuestión de búsqueda los arboles suelen ser efectivos. Los árboles binarios de búsqueda se utilizan para localizar en forma rápida un elemento almacenado en ese árbol, a partir de una clave. Son una forma de implementar arreglos asociativos o mapas, en donde se almacenan elementos que son pares
Negativo: Es difícil construir un árbol binario de búsqueda perfectamente equilibrado. El número de consultas en el árbol no equilibrado es impredecible. Y además el número de consultas aumenta rápidamente con el número de registros a ordenar.
Interesante: Se utiliza un árbol binario de búsqueda cuando se desea almacenar en una estructura de datos cierta información, a la cual luego se desea acceder en forma rápida a partir de una clave.
CONCLUSIÓN
Como ya se ha mencionado antes un árbol es una estructura dinámica, la cual no es una estructura lineal, está más enfocada a la representación de los datos por medio de nodos en una forma jerárquica, esta estructura tiene a su vez una raíz, entre otras cosas que se pueden mencionar de los árboles se puede mencionar acerca de los nodos que son los que permiten el enlace y la diferencia entre los nodos sucesores y los nodos terminales .Un árbol binario puede ser implementado fácilmente en una computadora. Este tipo de estructuras suelen ser muy efectivas para el uso de búsquedas. Si dentro de los árboles se hace la implementación de claves el proceso de búsqueda es mejor y más efectivo.

BIBLIOGRAFÍA:
*http://blog.unab.cl/maxbecerrabustamante/arboles/
*http://es.scribd.com/doc/24062352/Arboles-y-Grafos
*http://www.slideshare.net/ulises_e/savedfiles?s_title=arboles1670628&user_login=zamanthag [Página en Ingles] 

Tarea 2 Unidad III


Arboles.


 Definición
Un árbol es una estructura de datos dinámica (las estructuras del árbol pueden cambiar durante la ejecución del programa) no lineal (puesto que a cada elemento del árbol puede seguirle varios elementos) y homogénea en el que cada elemento puede tener varios elementos posteriores y solamente un elemento anterior. Es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos, de los cuales uno es conocido como raíz, además se crea una relación de parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.
Clasificación.
Distintos: Dos árboles binarios son distintos cuando sus estructuras son diferentes.
Similares: Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.
Equivalentes: Son aquellos árboles que son similares y que además los nodos contienen la misma información.
Completos: Son aquellos árboles en los que todos sus nodos excepto los del último nivel, tiene dos hijos; subárbol izquierdo y el subárbol derecho.
Árbol binario
Representación Grafica
 Representación en memoria.
Hay dos formas tradicionales de representar un árbol binario en memoria:
1.-Por medio de datos tipo punteros también conocidos como variables dinámicas o listas. Esta es la forma más utilizada, puesto que es la más natural para tratar este tipo de estructuras.
2.-Por medio de arreglos. Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subárbol izquierdo y derecho del subárbol en cuestión.
Aplicaciones:
Las aplicaciones de los arboles binarios se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
Una aplicación de los árboles binarios es la de representar una expresión que contiene operando y operadores binarios.
Una aplicación de los árboles binarios es la creación de Árboles binarios de búsqueda, en donde dada una secuencia de datos el árbol binario de búsqueda se construye dadas las sig. reglas:
·         Cualquier nodo del subárbol derecho contiene Información >= al nodo padre.
·         Cualquier nodo del subárbol izquierdo contiene Información < al nodo padre.
Diferencias entre un árbol general y un árbol binario:
Son árboles cuyo grado es mayor que dos.
Por cada nodo: la información y una lista de referencia saca da uno de sus hijos.
•Secuencial: Se pierde espacio, cada nodo tiene un agrado diferente.
•Enlazada: la manipulación de la lista de hijos se hace difícil.
Bibliografías:
http://blog.unab.cl/maxbecerrabustamante/arboles/
http://upload.wikimedia.org/wikipedia/commons/5/51/APUNTES.pdf
http://es.scribd.com/doc/24062352/Arboles-y-Grafos
http://www.slideshare.net/ulises_e/savedfiles?s_title=arboles-1670628&user_login=zamanthag

Actividad 1 Unidad III


RESUMEN

La recursividad es un tópico importante examinado frecuentemente en cursos de programación y de introducción a las ciencias de la computación. Un método que tiene sentencias entre las que se encuentra al menos una que se llama al propio método se dice que es recursivo.
Un método recursivo es un método que se invoca a sí mismo de forma directa o indirecta. En recursión directa, el código del método f () contiene una sentencia que invoca a f (), mientras que en recursión indirecta el método f () invoca a un método g () que invoca a su vez al método p (), y así sucesivamente hasta que se invoca de nuevo al método f ().
Un requisito para que un algoritmo recursivo sea correcto es que no genere una secuencia infinita de llamadas sobre sí mismo, así mismo un método recursivo correcto debe incluir un componente base o condición de salida, ya que en caso contrario produce una recursión infinita.
La recursión directa se produce cuando un método P contiene dentro de sí un llamado a sí mismo.
La recursión indirecta se produce cuando un método llama a otro, que eventualmente terminará llamando de nuevo al primer método.
La recursión infinita significa que cada llamada recursiva produce otra llamada recursiva, y esta a su vez otra llamada recursiva, y así para siempre.
La recursión tiene muchas desventajas. Se invoca repetidamente al mecanismo de llamadas a métodos y, en consecuencia, se necesita un tiempo suplementario para realizar cada llamada, esta característica puede resultar cara en tiempo de procesador y espacio de memoria, cada llamada recursiva produce que otra copia del método sea creada; esto puede consumir memoria considerablemente, por el contrario la iteración se produce dentro de un método de modo que las operaciones suplementarias de las llamadas al método y asignación de memoria adicional son omitidas.

Recursividad
Definición
Tipos
Diferencias
Ventajas
Desventajas
Es una técnica de programación que permite que un bloque de instrucciones se ejecute n veces, directamente o a través de otro método.
Directa
Cuando un método P contiene dentro de sí un llamado a sí mismo.
- Asignación de memoria estática o dinámica.
- Se pueden aplicar los dos tipos de memoria.
- Reducción en el tamaño del código.
- El espacio de memoria es limitado.
-Los métodos son lentos.
- Consumen más memoria.
- Cada llamada implica el almacenamiento de variables de estado y otros parámetros.
Indirecta
Cuando un método contiene dentro de si un llamado a otro método Q que contiene llamados (directos o indirectos) a P.
Infinita
La clave de funcionamiento es que obligatoriamente existir una condición terminal con el objeto de que la función se verifique hacia una resolución no recursiva en algún punto. De lo contrario la función entra en un bucle infinito y nunca finaliza.

Positivo.

- Debe contener uno o más casos base, casos para los que existe una solución directa.
- Debe contener una o más llamadas recursivas, casos en los que se llama sí mismo.
- Reducción del código de programación.

Negativo.

- Pueden resultar complejas un algoritmo mal codificado.
- En algunos casos un programa, en su ejecución con determinados parámetros de entrada puede requerir tantas llamadas recursivas que llegue a agotar los recursos del sistema.

Interesante.

- Cada vez que se produce una nueva llamada al método se crean en memoria de nuevo las variables y comienza la ejecución del nuevo método.
- El uso de ambas memorias (dinámica y estática) en una misma clase.

Conclusiones:
La recursividad es buena para reducir el código que podemos emplear en algún programa realizado en java, pero que esta conlleva a mucho tiempo de ejecución siendo así una desventaja, la cual nos pone en un dilema como programadores en la búsqueda de un aprovechamiento completo de los programas.

BIBLIOGRAFÍA.
·         Fundamentos de Programación, Algoritmos, estructuras de datos y objetos, Luís Joyanes Aguilar, Mc-Graw Hill. Madrid, 2003.
·         Harvey M. Deitel, P. J. (2004). Como programar en JAVA. Mexico.: PEARSON educacion.
·         Drozdek, A. (2007). Estructura de Datos Y Algoritmos Con Java. Mexico: THOMSON.