Portafolio de Jesus Arias

Plan

El vínculo marcado [+] permite publicar y además ocultar las subsecciones que contiene la sección correspondiente.

Biografía

Imagen representante Jesus Arias

Guten Tag! Soy Jesús Arias y bienvend@ a mi portafolio. Soy estudiante de la carrera de Ing. En Sistemas de la UNAH.

En este portfolio se encuentra un compendio de los temas aprendidos durante el curso de Algoritmos y Estructuras de Datos. 

Estructuras de Datos

En la informática, así como se lee en su nombre, es necesario poder procesar información, almacenarla y modificarla. Esta información muchas veces es representada a través de los datos. El dato es el elemento primario de la información y a su vez está formado por símbolos que por sí mismos no tienen valor alguno, pero que al ser unidos con otros símbolos pueden adquirir significado significado.

Los datos están conformados por dos tipos:

  • Primitivos
  • Compuestos

Los datos primitivos son aquellos más simples, éstos no pueden descomponerse en partes. Ejemplos de tipos de datos podrían ser los enteros, lógicos, caracteres, etc.

Los datos compuestos son los tipos de datos cuyas partes, al ser descompuestas, tienen signficado.En esta categoría caben los tipos agregados que son colecciones de elementos de datos. Ejemplos de los tipos agregados pueden ser los arreglos, registros y las cadenas.

Exsisten tipos de datos definidos por el usuario y éstos reciben el nombre de clases.

Los datos dan paso a un concepto que se utiliza frecuentemente en la informática: las estructuras de datos.

“Una estructura de datos es una agregación de tipos de datos compuestos y atómicos en un conjunto con relaciones bien definidas. Una estructura significa un conjunto de reglas que contienen los datos juntos.” (Luis Joyanes Aguilar, 2008, Primera Edición Español, Estructuras de datos en Java, McGraw-Hill, España) 

¿Por qué utilizar estructuras de datos?

La POO se caracterizar por reutilizar componentes previamente creados, es por eso que se utilizan estructuras de datos. Una vez que una estructura ha sido implementada puede ser utilizada muchas veces para aplicaciones diferentes. En algunos casos necesitaríamos guardar nuestros pasos o acciones para poder regresar sobre ellas o quizás en otro necesitaríamos almacenar datos que dependiendo de su inserción pueden ser procesados, es aquí donde entran las estructuras de datos.

Ejemplo de arreglo bidimensional.

Tipos de estructuras de datos

Existen dos tipos de estructuras de datos según su forma: 

  • Aquellas que son una combinación de tipos de datos.
  • Las que son una combinación de otras estructuras de datos

Así mismo existen dos tipos de estructuras de datos según su implementación:

  • Estáticas: este tipo de estructura utiliza un espacio de memoria reservado con anterioridad a la ejecución del programa, por ende no puede modificarse en su ejecución. Pero cuenta con la ventaja de ocupar casillas continuas de memoria. Las colas y pilas pueden implementarse de esta manera.
  • Dinámicas:  éstas no tienen limitaciones en cuanto al uso de la memoria; su implementación se basa en el uso de los apuntadores.

Por último cabe diferenciar las estructuras de datos lineales y las no lineales.

  • Lineales: reciben su nombre por la manera en la que se relacionan los elementos, uno después de otro. Sus elementos estan organizados en una secuencia lineal. En esta categoría están las pilas, colas y listas.
  • Estructuras de datos no lineales o jerárquicas: se conforman de una manera jerárquica como indica su nombre, o por niveles. Sus nodos pueden estar conectados a más de un nodo, por ende no son lineales. Los grafos y árboles son tipos de estructuras jerárquicas.

Pilas

Una pila es una estructura de datos en la cual el acceso está limitado al elemento más recientemente insertado. Podemos imaginarnos una pila de libros o de platos, su funciomaniento es el mismo. Conceptualmente el último elemento que se agrega a la pila se coloca en su cima, de donde se puede tomar muy fácilmente. Mientras que los elementos que llevan más tiempo en la pila son más dificiles de acceder. En un principio los elementos que no están en la cima son inaccesibles.

Las operaciones elementales de un pila son insertar, eliminar y buscar. Se puede notar qe una pila puede ser utilizda para dar vuelta a una lista de elementos.

No se puede eliminar elementos que no estén en la cima. 

No se pueden insertar elementos que sea sobre la cima.

Aplicaciones para las pilas: el gestor de ventana de Windows utiliza una pila para que, al cerrar una ventana, se muestre la anterior; también se utilizan pilas para saber que cada parentésis esté debidamente unido con otro al momento de realizar operaciones; las pilas son usadas para poder regresar sobre los pasos que se han hecho, por ejemplo para resolver laberintos en inteligencia artificial.

Ejemplo visual de una pila.

Pila implementada con arreglo:

Pila.java (834 o)

Pila implementada con listas:

Pila.java (753 o)

Colas

Dependiendo de la situación necesitaremos encontrar y eliminar el elementos más recientemente encontrado, pero en otras situaciones sería la forma errónea de proceder. Es por eso que existen lo que conocemos como colas. Podemos imaginarnos conceptualmente a las colas como las colas de un supermercado o un banco, donde el primer elemento que entra es el próximo en salir y el último elemento espera hasta que la cola se vacíe para poder ser atendido o salir.

Las operaciones básicas de la cola son: insertar, quitar el primer elemento y acceder al primer elemento. 

Note que sólo se puede insertar en la última posición.

Una aplicación práctica para las colas pueden encontrarse en el sistema de las impresoras, las cuales imprimen el elemento que lleva más tiempo en su lista de impresón primero y posteriormente siguen con las que llevan menos tiempo.

Las colas también son utilizadas en la ejecución de procesos de sistemas operativos como Unix, por ejemplo.

Tipos de colas:

  • Circulares: son las que están implementadas para funcionar de una manera circular o anular, los elementos que salen pueden ser llenados por otros elementos siempre que haya espacio.
  • De Prioridad: son las que dependiendo de la prioridad del elemento pueden colocarse en el primer lugar para que su procesamiento se haga inmediatamente.

Ejemplo visual de una cola circular.

Cola implementada con lista:

Cola.java (1.2 ko)

Cola implementada con arreglo:

Cola.java (1.6 ko)

Cola circular:

ColaC.java (1.9 ko)

Listas Enlazadas

Las listas enlazadas se caracterizan por almacenar los elementos de una forma no contigua, en su lugar utiliza apuntadores al siguiente espacio de memoria.

Los elementos se almacenan en un nodo que contiene el objeto a utilizar y ademas hace referencia al siguiente nodo de la lista. Cuando un nodo hace referencia a null decimos que es el último elemento.

La mayor ventaja de las listas enlazadas es su facilidad de manipulación al momento de insertar nuevos nodos, y al momento de recorrerlos ya que su recorrido siempre se realiza en tiempo constante.

Cabe mencionar que con las listas enlazadas pueden implementarse tanto las colas como las pilas, solo habría que limitar el acceso a los nodos y listo.

Las operaciones elementales de las listas son la inserción, buscar, visitar el primer elemento y eliminar elementos.

Dentro de las listas enlazadas existen dos tipos:

Clase lista:

Lista.java (4.2 ko)

Árboles

Los árboles son estructuras de datos jerárquicas utilizadas con mucha frecuencia. Los árboles están formados por un conjunto de nodos y un conjunto de aristas que conectan los dichos nodos.

Los árbolos con raíz se caracterizan por:

  • Tener un nodo distinguido como raíz.
  • Todo nodo c está conectado por medio de una arista a un único nodo p.
  • Sólo existe un único camino de la raíz a cada nodo.

Conceptos importantes:

  • Raíz: es el nodo principal de un árbol, de él se desprenden el resto de los nodos. Es el único nodo que no tiene un padre. 
  • Nodo Padre: son aquellos nodos que hacen referencia a otros nodos.
  • Nodo HIjo: son los nodos referenciados por un mismo padre.
  • Nodo Hoja: son los extremos del árbol, no contienen nodos hijos.
  • Altura: es el máximo numero de niveles de todos los nodos del árbol.
  • Longitud o Nivel: es la cantidad de aristas que se requieren recorrer para llegar a un nodo en particular.

Algunas aplicaciones de los árboles se encuentran en los compiladores que crean árboles de sintaxis; también se encuentran en algoritmos de compresión como el caso de los jpeg.

Las operaciones básicas de los árboles son: buscar, insertar y borrar. 

A diferencia de las estructuras anteriores los árboles nos permiten borrar de la posición que deseemos.

Cabe mencionar que los árboles son grafos, pero no todos los grafos son árboles.

ABB

Los árboles binarios de búsqueda también conocidos como ABB son variantes de los árboles que se caracterizan por la cantidad de hijos que contiene cada nodo, que tal como lo dice su nombre “binario” son dos.

Los ABB utilizan los mismos conceptos que un árbol comun.

Los ABB están estructurados de tal manera que dependiendo de el valor que contenga el nodo raíz, los nodos hijos estén a la derecha o izquierda de ese nodo; si se agrega un dato con un valor menor al de la raíz, éste se agregará como hijo izquierdo del nodo raíz; en cambio si se agrega un nodo con un valor mayor a aquél que se encuentra en la raíz se agregará al lado derecho del nodo raíz. Lo mismo ocurre para los nodos que se agreguen con posterioridad de manera que los ABB toman una estructura particular con gran potencial.

Gracias a la conformación de éstos ABB, la utilidad por excelencia de los ABB es su método de búsqueda, el cual reduce el timpo de ejecución al momento de buscar elementos, haciéndolo más eficiente que otros métdos de búsqueda.

Las operaciones elementales del ABB son las mismas que las de un árbol común: insertar, borrar, buscar y recorridos. Los recorridos de los árboles son un gran ejemplo del uso de algoritmos recursivos.

Sólo puede realizarse la inserición en los nodos hoja.

Para borrar un nodo hay dos caminos:

  • Referenciar el nodo deseado al nodo con valor más grande de su rama izquierda y borrar ese nodo.
  • Referencial el nodo deseado al nodo con valor más bajo de la rama derecha y borrar ese nodo.

Ejemplo de un ABB.

El ABB consta de tres recorridos fundamentales:

  • Recorrido Pre-Orden(NID):
    • Se visita el Nodo.
    • Se realiza el recorrido Pre-Orden por la rama Izquierda
    • Después se realiza para la rama Derecha.
  • Recorrido In-Orden (IND):
    • Se baja por la rama Izquierda y se realiza el recorrido In-Orden.
    • Se visita el Nodo.
    • Se reliza el recorrido In-Orden para la rama Derecha.
  • Recorrido Post-Orden(IDN): 
    • Se realiza el recorrido en Post-Orden por la rama Izquierda.
    • Se realiza el reccorido en Post-Orden por la rama Derecha.
    • Se visita el Nodo.

Clase ABB:

Arbol.java (9.8 ko)

Clase Nodo:

Nodo.java (1.3 ko)

AVL

Los árboles AVL son una versión mejorada de los ABB. Reciben su nombre de sus creadores Andelson-Velskii y Landis.

Los AVL cuentan con algo que se conoce como factor de equilibrio. El factor de equilibrio es la diferencia entre las alturas de los nodos derecho e izquierdo. Para que un AVL se encuentre equilibrado su factor de equilibrio puede ser -1,0 o 1. En caso de que su factor de equilibrio no se encuentre en ese rango se dice que el árbol está desequilibrado, por lo que se hacen las rotaciones pertinentes.

Operaciones elementales: borrar, insertar, buscar y rotaciones.

Hay que tener en cuenta que una vez que se borra o se inserta un método hay que modificarlo de nuevo para que quede equilibrado.

El potencial más grande de los AVL es su búsqueda, ya que por cada decisión que se toma se elimina un 50% de las opciones.

Para borrar un nodo hay dos caminos:

  • Referenciar el nodo deseado al nodo con valor más grande de su rama izquierda y borrar ese nodo.
  • Referencial el nodo deseado al nodo con valor más bajo de la rama derecha y borrar ese nodo.

Tipos de rotaciones:

  • Simples: afectan a dos nodos, el tercero no se modifica y es necesario sólo para una rotación.
  • Dobles: afectan a tres nodos. Consta de dos rotaciones simples.

Clase AVL:

ArbolAVL.java (6.6 ko)

Clase Nodo AVL:

NodoAVL.java (626 o)

Grafos

Los grafos son estructuras que nos permiten relacionar conexiones entre dos objetos, por eso son binarias. De manera informal podemos decir que es una colección de vértices y aristas que los unen.

Definicion formal de un grafo:

Un grafo G = (V,E) está formado por un conjunto de vértices V, y un conjunto de aristas E. Cada arista es un par (v,w), donde v,w pertenece a V.” (Mark Allen Weiss, 2000, Primera Edición Español, Estructuras de datos en Java, Pearson, España)

Dentro de los grafos existe lo que conocemos como caminos. Los caminos permiten unir dos nodos a traves de varias aristas. La longitud de un camino, en caso de que el grafo no tenga peso puede considerarse como el numero de aristas que cruza hasta llegar al nodo deseado. En cambio, si el grafo tiene peso o costes, la longitud del camino se determina por la suma de los costes entre aristas que le toma llegar de un nodo a otro.

Los grafos pueden ser:

  • Dirigidos: son los grafos formados por aristas con sentido o dirección.
  • No dirigidos: son los grafos en los que se puede moverse en cualquier dirección a través de las aristas.
  • Mixto: combinación de grafos dirigidos y grafos no dirigidos.

Además pueden ser:

  • Grafos valorado: son aquellos cuyas aristas tienen un coste o peso.
  • Grafos no valorado: no existe coste entre las aristas.

Recorridos:

  • Anchura: este recorrido se lleva a cabo utilizando una cola. Se toma un nodo inicial, se introduce en la cola y sus hijos. Luego se visita el nodo. El proceso se repite hasta que todos los nodos han sido visitados y no se visita un nodo dos veces.
  • Profundidad: en este recorrido se utiliza una pila. Se inicia con un nodo y se visita. Posteriormente se introducen los hijos de dicho nodo y el proceso se repite hasta que todos los nodos no repetidos hayan sido visitados.

Los sistemas GPS son una aplicación práctica para los grafos. También puede utilizarse como una conexión entre personas, a modo de aplicación en trabajos de investigación policial.

Ejemplo de un grafo.

Clase Grafo:

Grafo.java (4.1 ko)

Representación de un grafo

Matriz de adyacencia

En la matriz de adyacencia los nodos se ubican tanto en columnas como en filas en el mismo orden. Para cada posicion de la matriz se marca con un 1 si existe una arista entre el nodo de la fila y el nodo de la columna. De no existir arista entre ellos se marca con un 0 la casilla.

La matriz de adyacencia también puede contener valores distintos a 1 en el caso de que represente un grafo valorado y el valor de 1 es reemplazado por el valor del coste del arco o arista.

Ejemplo de una matriz de adyacencia.

Lista de adyacencia

Los grafos pueden representarse mediante una listas, en los cuales se unen los elementos que están unidos en el grafo mediante las aristas. Las listas de adyacencia pueden parecer tediosas puesto que es más difícil visualizar el grafo, pero cuentan con la ventaja de que el grafo puede verse modificado el momento de agregar algún elemento o borrar ya que su manejo de memoria es dinámico.

Matriz de cierre transitivo y cierre transitivo

Para encontrar los caminos de cierta longitud, se utiliza la relacion entre la matriz de adyacencia y la matriz de caminos. La matriz de caminos se define como la matriz de adyaciencia eleveda a una potencia n con 0 < n < N, donde N es el numero total de nodos.  La matriz de cierre transitivo es aquella que determina en su totalidad la conexión entre nodos, es decir la matriz de adyacencia elevada a la potencia N.

Algoritmos

Algoritmo de Djikstra

Este algoritmo determina el camino más corto de un nodo hacia cualquier otro nodo. Se aplica a los grafos valorados. Tiene un enfoque voraz.

Este algoritmo inicia con un nodo, partiendo de él se identifica cada arista y su peso. Luego se marca la arista de menor peso y sucede lo mismo para esa arista y el nodo original ya que éste también ha sido marcado. El algoritmo continúa marcando las aristas de menor peso hasta alcanzar el nodo deseado. En caso de que un peso sea igual al otro éste no se toma en cuenta.

Algoritmo Recursivo

Es el tipo de algoritmo que resuelve problemas mediantes llamadas a sí mismo, es decir recurre a sí mismo. Al momento de presentarse la solución trivial del problema que el algoritmo conoce se llega al caso base de la recursividad, evitando que el algoritmo recurra infinitamente.

Ejemplo de una función recursiva que calcula el factorial de un numero. Se sabe que el caso base es cuando se calcula el factorial de 0 que es 1 o bien el factorial de 1 que también es 1.

Algoritmo Voraz

Se llaman de esta manera porque tienen una aproximación que se conoce como voraz, que consiste en visitar un elemento una única vez y dependiendo de lo deseado el elemento se selecciona o se descarta. Por lo general estos elementos son marcados con el fin de llegar a la solución óptima del problema, es por eso que sus decisiones son basadas en la opción más óptima que se puede tomar.

Ejemplos de algoritmos voraces: Kruskal, Dijkstra, Prim.

Algoritmos de Ordenamiento

En esta sección se encuentran ejemplos de algunos algoritmos de ordenamiento vistos en clase.

Quicksort Recursivo:

Quicksort.java (3.7 ko)

Quicksort Iterativo:

Método Burbuja:

Tarea

El código que convierte un árbol en un archivo de texto se encuentra en el archivo ABB2.java de la sección ABB. 

En esta sección se encuentra un archivo de prueba que puede ser transformado en un árbol.

NOTA: Es necesario pegarlo en el mismo folder para que funcione.

Arbol.txt

Arbol.txt (16 o)

Reflexiones

  • Veo de gran utilidad tener un porafolio y la construcción del mismo ya que permite identificar el nivel de aprendizaje que desarrollé durante el curso; sirve como un método no sólo de evaluación para el docente sinto de autoevaluación, a modo de repaso del curso.
  • Sobre los trabajos incluidos considero que fue muy satisfactorio realizarlos, luego de no llegar a una solución sino hasta días después de iniciar con el código.
  • Considero que he aprendido muy bien los temas del curso y que serán de utilidad para clases posteriores como el caso de Sitemas Operativos.