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.

Tarea 1 Unidad III

Recursividad.

Un programa o subprograma que se llama a si mismo se dice que es recursivo.

El concepto de recursividad está ligado, en los lenguajes de programación, al concepto de procedimiento o función. Un procedimiento o función es recursivo cuando durante una invocación a él puede ser invocado a su vez él mismo.

La recursividad es una de las formas de control más importantes en la programación. Los procedimientos recursivos son la forma más natural de representación de muchos algoritmos.

Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de construcción. La base no es recursiva y es el punto tanto de partida como de terminación de la definición.

Tipos de Recursividad.

Recursión Directa e Indirecta.

Directo: El subprograma se llama directamente a si mismo.

Indirecta: Un programa llama a otro subprograma y este a su vez al primero

Recursividad Infinita

Es muy importante que toda función recursiva tenga un caso en el que no se llame a sí misma, o

las llamadas serían infinitas y el programa no tendría fin.

Por eso, siempre una función recursiva tiene una condición inicial en la que no debe llamarse a sí misma.

Diferencias entre recursión e iteración.

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Tanto la iteración como la recursión se basan en una estructura de control:

- La iteración utiliza una estructura repetitiva

- La recursión utiliza una estructura de selección.

La iteración y la recursión implican ambas repetición:

- La iteración utiliza explícitamente una estructura repetitiva

- La recursión consume la repetición mediante llamadas repetidas.

La iteración y la recursión implican cada una un test mientras que la recursión termina cuando se reconoce un caso base o la condición de salida se alcanza.

Ventajas y desventajas.

Ventajas de la Recursión.

- Soluciones simples, claras

- Soluciones elegantes.

- Soluciones a problemas complejos.

Desventajas de la Recursión:

- INEFICIENCIA

-Sobrecarga asociada con las llamadas a subalgoritmos

Una simple llamada puede generar un gran número de llamadas recursivas. (Fact(n) genera n llamadas recursivas)

¿La claridad compensa la sobrecarga?

El valor de la recursividad reside en el hecho de que se puede usar para resolver problemas sin fácil solución iterativa.

- La ineficiencia inherente de algunos algoritmos recursivos.

La recursividad se debe usar cuando sea realmente necesaria, es decir, cuando no exista una solución iterativa simple.

Actividad IV Unidad II

Listas
Definición	Clasificación	Representación grafica y en memoria	Modo cabecera
- Una lista es una estructura de datos lineal que se puede representar simbólicamente como un conjunto de nodos enlazados entre si. - Por la forma de acceder a sus elementos. -Por la información utilizada para acceder a sus elementos.	Listas densas. Cuando la estructura que contiene la lista es la que determina la posición del siguiente elemento. Listas enlazadas: La localización de un elemento es: - Estará en la dirección k, si es el primer elemento, siendo k conocido. -Sino es el primer elemento de la lista, estará en una dirección, j, que está contenida en el elemento anterior. Listas ordinales. La posición de los elementos en la estructura la determina su orden de llegada. Listas calificadas. Se accede a un elemento por un valor que coincide con el de un determinado campo, conocido como clave. Este tipo de listas se pueden clasificar a su vez en ordenadas o no ordenadas por el campo clave.	Public class ListaS { Prívate nodo primero; Prívate nodo ultimo; Prívate int tamaño; Public listas(){ This.primero=null; This.ultimo=null; This.tamano=0;	Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista estará diferenciando de los demás. Una lista con nodo cabecera satisface el requerimiento: cada nodo que tiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías. Se simplifica el código y aumenta la velocidad a cambio de un despreciable aumento de espacio.

Positivo:

Las listas permiten modelar diversas entidades del mundo real, puede implementarse en soportes informáticos de diferentes maneras. Las listas que son un conjunto de nodos tienen cierta relación, los nodos también tienen un valor, cada una tiene su dirección, cuando nosotros reservamos un espacio de memoria, y por ejemplo cuando ya está en la memoria y cada celda y cada una tiene un valor. Las listas se pueden decir que cada nodo es un eslabón de la cadena.

Negativo:

La declaración de una lista mediante una matriz implica conocer de antemano el número (o al menos el orden de magnitud) de elementos que va a almacenar, pudiendo darse las circunstancias de que si se declara pequeño podría desbordarse su capacidad o, en caso contrario, declararlo desproporcionadamente elevado provocaría un decremento de eficiencia.

Otro problema asociado es el tratamiento de los elementos eliminados. Dado que en el caso de no informar, de alguna manera, de la inexistencia de dicho elemento el nodo previamente ocupado (y ahora no válido) quedaría como no disponible.

Interesante:

En el caso de java, se utilizan nodos que son una clase cualquiera que creas, con unos campos dedicados a guardar información, y otro campo que apunta a otro objeto de la clase que has creado, que a su vez contiene información y un enlace a otro nodo, de forma que a partir de uno, puedes avanzar al siguiente y así sucesivamente.

Conclusión:

Una lista con nodo cabecera satisface el requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías, conocemos muchas cosas interesantes.

Bibliografía:

·http://ocw.upm.es/lenguajes-y-sistemas-informaticos/estructuras-de-datos/contenidos/tema3nuevo/Listas.pdf

· http://www.programacionfacil.com/estructura_de_datos:colas

· http://c.conclase.net/edd/index.php?cap=003

· http://www.slideshare.net/egpena/estructura-de-datos-listas-pilas-y-colas-7075957

· http://mit.ocw.universia.net/1.00/s02/class-sessions/lecture-25/lecture-25.pdf

Tarea IV Actividad II

Listas

Una LISTA es un conjunto ordenado de elementos homogéneos, en la que no hay restricciones de acceso, la introducción y borrado de elementos puede realizarse en cualquier posición de la misma.

Representación gráfica:

Representación en Memoria:

Tipos o Clasificación. Listas simples enlazadas.

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Lista Doblemente Enlazada

Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Listas enlazadas circulares

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Listas enlazadas circulares simples.

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciando Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.

Lista Enlazada Doblemente Circular

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Nodo cabecera.

Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista estará diferenciado de los demás. Una lista con nodo cabecera satisface el requerimiento: cada nodo que contiene un elemento tiene un nodo anterior. Esto simplifica las operaciones de eliminación e inserción, pues no hay que tratar los casos especiales para listas vacías. Se simplifica el código y aumenta la velocidad a cambio de un despreciable aumento de espacio.

Bibliografía.

- Algoritmos, estructuras de datos y programación orientada a objetos. Escrito por Roberto Flórez Rueda

- Cómo programar en Java. Escrito por Harvey M. Deitel, Paul J. Deitel

- Estructuras de datos: Referencia práctica con orientación a objetos. Escrito por Román Martínez, Elda Quiroga

- http://popys.edublogs.org/2011/01/14/representacion-de-listas-enlazadas- en-memoria/

- http://tesciedd.blogspot.mx/2011/01/unidad-3-clasificacion-de-listas.html

Tarea 3 Unidad II

Los Algoritmos de pop mejorado

Con Pila Auxiliar

- Bubble Sort (Intercambio directo)

El método de intercambio directo puede trabajar de dos maneras diferentes.

1. llevando los elementos más pequeños hacia la parte izquierda del arreglo.

2. llevando los elementos más grandes hacia la parte derecha del mismo.

La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados. Se realizan N-1 pasadas, transportando en cada una de las mismas el menor o mayor elemento (Según sea el caso) su posición ideal. Al final de las N-1 pasadas los elementos del arreglo estarán ordenados.

Lo siguiente, es una implementación en Pseudocódigo, donde A es un arreglo de N elementos

BURBUJA(A,N)

{I, J y AUX son variables de tipo entero}

1. Repetir con I desde 2 hasta N

1.1 Repetir con J desde N hasta I

1.1.1 Si A [J-1] > A [J] entonces

Hacer AUX? A [J-1] A [J-1] ? A [J]

A[J] ? AUX

1.1.2 {Fin del condicional del paso 1.1.1}

1.2 {Fin del ciclo del paso 1.1}

2. {Fin del ciclo del paso 1}

Con Corrimientos

· Insertion Sort

Este es uno de los métodos más sencillos. Consta de tomar uno por uno los elementos de un arreglo y recorrerlo hacia su posición con respecto a los anteriormente ordenados. Así empieza con el segundo elemento y lo ordena con respecto al primero. Luego sigue con el tercero y lo coloca en su posición ordenada con respecto a los dos anteriores, así sucesivamente hasta recorrer todas las posiciones del arreglo. Este es el algoritmo:

- Procedimiento Insertion Sort

Este procedimiento recibe el arreglo de datos a ordenar a[] y altera las posiciones de sus elementos hasta dejarlos ordenados de menor a mayor. N representa el número de elementos que contiene a[].

paso 1: [Para cada pos. del arreglo] For i <- 2 to N do

paso 2: [Inicializa v y j] v <- a[i] j <- i.

paso 3: [Compara v con los anteriores] While a[j-1] > v AND j>1 do

paso 4: [Recorre los datos mayores] Set a[j] <- a[j-1], paso 5: [Decrementa j] set j <- j-1. paso 5: [Inserta v en su posición] Set a[j] <- v.

paso 6: [Fin] End.

- Selection Sort

El método de ordenamiento por selección consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.

- Procedimiento Selection Sort

paso 1: [Para cada pos. del arreglo]

paso 2: [Inicializa la pos. del menor]

For i <- 1 to N do

menor <- i

paso 3: [Recorre todo el arreglo]

paso 4: [Si a[j] es menor]
For j <- i+1 to N do If a[j] < a[menor] then

paso 5: [Reasigna el apuntador al menor] min = j paso 6: [Intercambia los datos de la pos. min y posición i] Swap(a, min, j).

paso 7: [Fin] End.

Actividad 2 Unidad II

Positivo:

Esta caracterizada por ser una secuencia de los elementos donde se utilizan los algoritmos push y pop, va auxiliada con la estructura de uno de ellos que es FIFOS.

Negativo:

Presenta muchas desventajas pues si eliminamos un elemento de nuestra cola, (el primero justamente) tendríamos que recorrer todos los siguientes elementos una posición adelante y esta manera seria muy lenta de implementar pues que pasa si son 1000 elementos, eso es mucho tiempo perdido, entonces es por eso que usamos dos variables que me digan dónde empieza y dónde terminan los elementos de la cola, dos variables enteras que llamaremos inicio y fin.

Interesante:

Es interesante saber que dentro de la Estructura de Datos una “Cola” va de la mano con los algoritmos de push y pop para que su función sea precisa y adecuada, de tal modo los elementos sean guardados de manera adecuada.

BIBLIOGRAFIA

http://www.programacion.com/articulo/estructuras_de_datos_y_algoritmos_en_java_309/5

https://tails.boum.org/bugs/Java_is_enabled_by_default [Página en Ingles]

http://soloinformaticayalgomas.blogspot.mx/2011/03/colas-en-java.html