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.


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:




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


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