PORTAFOLIO DE ANTONY BRENES

Biografía.

Hola mi nombre es Antony Brenes, soy estudiante de Ingenieria en Sistemas, en la UNAH;  este proyecto es creado como fin al curso de Algoritmos y estructuras de datos, con el cual intentamos expresar nuestros conocimientos adquiridos a travez de este sitio.

Qué son las estructuras de datos?

Es el uso de los tipos de datos compuestos y atómicos en combinación para crear una estructura, también puede ser entendido como un medio para el manejo de datos compuestos y atómicos.

Los tipos de datos nos permiten representar los diferentes datos que son necesarios a la hora de implementar un programa. Por ejemplo, si escribimos un programa sencillo que sume,reste,multiplique y divida (una calculadora basica) sera necesario emplear tipos de datos numericos que pueden ser : enteros o flotantes.

Tipos de datos enteros:

1) byte
El tipo de dato byte puede representar datos enteros que se encuentren en el rango de -128 a +127.
El tamaño de un dato de tipo byte es de 8 bits.

2) short
El tipo de dato short puede representar datos enteros que se encuentren en el rango de -32768 y +32767.
El tamaño de un dato de tipo short es de 16 bits.

3) int
El tipo de dato int puede representar datos enteros que se encuentren en el rango de -2147483648 y +2147483647.
El tamaño de un dato de tipo int es de 32 bits.

4) long
El tipo de dato int puede representar datos enteros que se encuentren en el rango de -9223372036854775808 y +9223372036854775807.
El tamaño de un dato de tipo int es de 64 bits.
Para indicar de manera explicita que el dato es un long , se agrega una L o l al final del valor de la variable.

Tipos de datos flotantes:

1) float
El tipo de dato float puede representar datos en coma flotante que se encuentren en el rango de 1.40239846e–45f y 3.40282347e+38f.
El tamaño de un dato de tipo short es de 32 bits. 
Para indicar de manera explicita que el dato es un float , se agrega una F o f al final del valor de la variable.


2) double
El tipo de dato double puede representar datos en coma flotante que se encuentren en el rango de 4.94065645841246544e–324d y 1.7976931348623157e+308d.
El tamaño de un dato de tipo short es de 64 bits. 
Para indicar de manera explicita que el dato es un double , se agrega una D o d al final del valor de la variable.

Tipo de dato boolean:


El tipo de dato boolean puede representar dos valores logicos : true(verdadero) o false(falso).


Tipo de dato char:
El tipo de dato char se usa para representar
caracteres(codigo Unicode).
Un caracter es representado internamente por un entero.

Pilas y Colas

Las Pilas

Las pilas son un tipo de estructuras de datos de ordenamiento en la cual, el primero en entrar en la pila es el primero en poder ser retirado ya que este solo tiene un "Hueco" que funciona al mismo tiempo de entrada y salida; este tipo de estructura de dato puede ser usada en mecanismos de empaque, de traslados, en los cuales lo que se busca es una facilidad de acomodamiento para su inserción y retiro. 

Las Colas

Las colas son un tipo de estructura de datos de ordenamiento en la cual, el primer elemento en entrar es el primero en salir, este tipo de estructura de datos tiene 2 "Huecos" uno de entrada y uno de salida; estas pueden ser utilizadas en mecanismos con colas, como en un banco etc...

Métodos fundamentales de una pila

-Crear_Pila():

Crea la pila e inicia sus metodos.

-Insertar():

Inserta datos en la pila, incrementa en 1 el puntero de cima.

-Borrar():

Elimina el ultimo dato en entrar a la pila, baja en 1 unidad el puntero de cima y elimina el dato de la pila.

-Pila_vacia():

Comprueba si la pila esta vacía.

-Pila_llena(): 

Comprueba si la pila esta llena, la pila esta llena si cima es igual al tamaño de de la pila.

-Limpiar():

Vacia totalmente la pila, elimina todos los datos y cima obtiene el valor de -1.

-Cima_Pila():

Obtiene el ultimo dato de la pila, o mejor dicho el topé de la pila.

______________________________________________________________

pila03.jpg
pila03.jpg (16.1 ko)

Pila en java.

Pila.txt
Pila.txt (2.2 ko)

Métodos fundamentales de una cola

-Crear_Cola():

Crea la cola con todos sus metodos y sus parametros vacios.

-Insertar():

Añade un elemento al final de la cola.

-Borrar():

Elimina el primer elemento de la cola.

-Cola_Vacia():

Verifica si la cola eta vacía.

-Cola_Llena():

Verifica si la cola esta llena.

-Primero():

Obtiene el primer elemento de la cola.

-Ultimo():

Obtiene el último  elemento de la cola.

_____________________________________________________

image571.jpg
image571.jpg (9.2 ko)

Cola en java.

Cola.txt
Cola.txt (2.7 ko)

Listas

Una lista enlazada es un conjunto de datos ordenados uno detrás de otro,en la que cada elemento se conecta al siguiente elemento por una “referencia”. La idea básica consiste en construir una lista cuyos elementos, llamados nodos, se componen de dospartes: la primera parte contiene la información y es, por consiguiente, un valor deun tipo genérico llamado dato o información, y la segunda parte es un enlace al siguiente elemento de la lista.

-Listas simplemente enlazadas. Cada nodo tiene un único enlace que lo conecta al siguiente nodo. Esta lista es usada para recorridos directos (hacia adelante).

-Listas doblemente enlazadas. Cada nodo contiene dos enlaces, uno a su nodo predecesor y otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo comoen recorrido inverso.

-Lista circular simplemente enlazada. Una lista enlazada simplemente en la que el últimoelemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede serrecorrida de modo circular.

-Lista circular doblemente enlazada. Una lista doblemente enlazada en la que el últimoelemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modocircular tanto en dirección directa como inversa.

 

Métodos fundamentales de una Lista.

-Crear_Lista(): 

Crea la lista e inicializa todos sus metodos y sus parametros vacios.

-Insertar():

Agrega un nuevo nodo a la lista.

-Borrar():

Elimina un nodo de la lista.

-Buscar():

Busca un nodo en la lista.

-Recorrer():

Recorre la lista.

-Vacia():

Comprueba si la lista esta vacia.

-Llena():

Comprueba si la lista esta llena.

Lista en Java.

Lista_simple.txt
Lista_simple.txt (2.9 ko)

Clase nodo para listas.

Listas con doble enlace.

Las listas con doble enlace son aquellas en las que sus nodos estan conectados tanto con el nodo que tienen antes y el que tienen despues.

_______________________________________________________________________________

015.jpg
015.jpg (8.6 ko)

Clase ListasDobles.

ListaDoble.txt
ListaDoble.txt (3.1 ko)

Clase Nodo_Listasdobles

Colas y Pilas dinámicas.

Las colas y pilas dinamicas son aquellas que "juegan" con la memoria, esto se logra creando Pilas y colas basadas en la estructura de una lista.

ColaDinamica.

Pila Dinámica.

PilaDinamica.txt
PilaDinamica.txt (1.4 ko)

Clase Nodo para colas y pilas dinámicas.

Arboles de búsqueda(ABB y AVL).

ABB:

Los arboles binarios de búsqueda son una estructura de datos comprendida por nodos conectados comprendidopor un primer nodo denominado raíz del cual se despliegan los demás nodos llamados hojas, los nodos seagrupan según su tamaño o valor, los nodos con un valor mayor al de la raíz son ubicados del lado derecho delárbol y los que tienen un valor menor son ubicados al lado izquierdo del árbol.Esta estructura de datos es utilizada para la búsqueda en grupos grandes de información ya que el tiempo deejecución es mucho menos variable y ofrece un mejor rendimiento.

Operaciones elementales de un ABB:

Buscar un elemento.

Insertar un elemento.Borrar un elemento.

Movimientos a través del árbol:Izquierda.Derecha.Raíz.

Información:

Comprobar si un árbol está vacío.

Calcular el número de nodos.Comprobar si el nodo es hoja.Calcular la altura de un nodo.

Calcular la altura de un árbol.

 

AVL:

Estos tipos de ABB tienen la misma cantidad de niveles tanto en el lado derecho como en el izquierdo con unmáximo de diferencia de 1 nivel, estos ABB son mucho mas eficientes ya que reducen drásticamente el tiempo deejecución y la búsqueda es mas rápido ya que se tiene un mejor orden.

Un AVL se consigue al hacer rotaciones en el árbol para así ubicar correctamente los nodos.

Operaciones elementales de un AVL:Un AVL tiene las mismas operaciones elementales que un ABB, la operación que los diferencia son las rotacionesque pueden ser rotación izquierda y rotación derecha.

Rotación derecha:

Esta rotación se usará cuando el árbol izquierdo de un nodo sea 2 unidades más alto que el derecho, esdecir, cuando su FE sea de -2. Y además, la raíz del árbol izquierdo tenga una FE de -1 ó 0, es decir, que estécargado a la izquierda o equilibrado.

Procederemos del siguiente modo:

Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de -2. Y llamaremos Q al nodo raíz delárbol izquierdo de P. Además, llamaremos A al árbol izquierdo de Q, B al árbol derecho de Q y C al árbol derechode P.En el gráfico que puede observar que tanto B como C tienen la misma altura (n), y A es una unidad mayor (n+1).Esto hace que el FE de Q sea -1, la altura del árbol que tiene Q como raíz es (n+2) y por lo tanto el FE de P es -2.Pasamos el árbol derecho del nodo Q como árbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todoslos valores a la derecha de Q siguen estando a la izquierda de P.

El árbol P pasa a ser el árbol derecho del nodo Q.Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, enlugar del nodo P. Previamente, P puede que fuese un árbol completo o un árbol de otro nodo de menor altura.

Rotación Izquierda:

Se trata del caso simétrico del anterior. Esta rotación se usará cuando el subárbol derecho de un nodo sea2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derechotenga una FE de 1 ó 0, es decir, que esté cargado a la derecha o esté equilibrado.Árbol desequilibrado a la derechaÁrbol desequilibrado a la derechaProcederemos del siguiente modo:Llamaremos P al nodo que muestra el desequilibrio, el que tiene una FE de 2. Y llamaremos Q al nodo raíz delsubárbol derecho de P. Además, llamaremos A al subárbol izquierdo de P, B al subárbol izquierdo de Q y C alsubárbol derecho de Q.

En el gráfico que puede observar que tanto A como B tienen la misma altura (n), y C es una unidad mayor (n+1). Esto hace que el FE de Q sea 1, la altura del subárbol que tiene Q como raíz es (n+2) y por lo tanto el FEde P es 2.Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB,ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.El árbol P pasa a ser el subárbol izquierdo del nodo Q.Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodoQ, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo demenor altura.

ABB en java.

ABB.txt
ABB.txt (2.4 ko)

Clase Nodo_ABB

Nodo_ABB.txt
Nodo_ABB.txt (628 o)

AVL

AVL.txt
AVL.txt (7.4 ko)

Clase_NodoAVL

NodoAVL.txt
NodoAVL.txt (1.2 ko)

Grafos.

Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipoabstracto de datos, que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos(aristas) que establecen relaciones entre los nodos.

Representación de grafos:

Matriz de adyacencias:

se asocia cada fila y cada columna a cada nodo del grafo, siendo los elementosde la matriz la relación entre los mismos, tomando los valores de 1 si existe la arista y 0 en caso contrario.Lista de adyacencias: se asocia a cada nodo del grafo una lista que contenga todos aquellos nodos que seanadyacentes a él.

 

Los grafos se pueden representar tanto en acnchura como en profundidad, como se podra ver a continuacion en la clases de grafos.

Matriz de caminos o Matriz de adyacencia:

___________________________________________________________________________________________

Matriz_de_adyacencia.jpg

___________________________________________________________________________________________

Grafo recorridos(Profundidad y anchura).

Grafos.rar
Grafos.rar (21.1 ko)

Algoritmo de Dijkstra.

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para ladeterminación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos encada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten delvértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde elvértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es unaespecialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costenegativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos queen próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D detamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio,exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.Sea a = x (tomamos a como nodo actual).

Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodosno marcados vi.Para el nodo actual, calculamos la distancia tentativa desde dicho nodo a sus vecinos con la siguientefórmula: dt(vi) = Da + d(a,vi).

Es decir, la distancia tentativa del nodo ‘vi’ es la distancia queactualmente tiene el nodo en el vector D más la distancia desde dicho el nodo ‘a’ (el actual) al nodo vi.

Si la distancia tentativa es menor que la distancia almacenada en el vector, actualizamos el vector conesta distancia tentativa. Es decir: Si dt(vi) < Dvi → Dvi = dt(vi)Marcamos como completo el nodo a.Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valoresen una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.Una vez terminado al algoritmo, D estará completamente lleno.

Algoritmo Voraz.

Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

Algoritmo recursivo.

Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.

FUNCIÓN Factorial(n) VAR resultado: Entero SI (n<2) ENTONCES resultado = 1; SINO resultado = n * Factorial(n-1); FSI RETORNA resultado; FUNCIÓN

Reflexión.

Con este proyecto recalcamos lo aprendido durante nuestro periodo en la clase de Algoritmos y estructuras de datos, con este curso lo logrado es aumentar nuestra logica y conocer la estructura de datos que podemos ultilizar y comprender los algoritmos y su funcionamiento para una correcta implementación.