Portafolio de Kimberly Ardon

Biografía

Imagen representante Kimberly Ardon

Kimberly Ardón

Estudiante de ingeniería en sistemas en la UNAH.

Este portafolio es una colección de información referente a la clase de Algoritmos y estructura de datos incluye métodos vistos en clase, como datos producto de investigación personal.

Estructura de Datos

Sabemos que el trabajo principal de una maquina guardar y recuperar información además de realizar cálculos. Ahora bien el problema radica en que la maquina debe saber que es lo que nosotros queremos que ella almacene o use para determinada tarea y es ahí donde nacen los tipos de datos.

Tipos de datos

Simples: Son aquellos que hacen referencia a un solo valor estos puede ser de tipo entero, flotante (decimal), lógico, y de tipo carácter.

Estructurados: Como su nombre indica estos tipos de datos son estructurados por otros tipos de datos generalmente de datos simples. Ejemplos de estos son los arreglos, y registros.

Una estructura de datos es cualquier representación de datos y sus operaciones asociadas.

Algunas Estructuras de Datos

Pilas y Colas

Ambos son algoritmos de ordenamiento en secuencia en los cuales la información (datos) es colocada y luego retirada.

Para diferenciarlos conviene recordar dos cosas, primero a pila de libros y segundo la cola del supermercado, si retiramos un libro de la pila se hace con el ultimo que se dejó en la pila por eso la frase de la pila es “primero en entrar último en salir”. En cambio en la cola del supermercado siempre se atiende al que llego primero a si que “el primero en entrar es el primero en salir”.

Cabe mencionar la diferencia de una estructura estática de dinámica una pila o cola estática tienen un tamaño ya esta establecido mientras en el dinámico el tamaño lo decide el usuario durante la ejecución.

Pila

WordReference.com define pila como “Montón o cúmulo que se hace poniendo una pieza sobre otras piezas o porciones de que consta algo”.

Y es muy acertado en el caso de nuestra estructura de datos, pues su finalidad es la organización información de tal forma que se pueda acceder solo por su parte superior de la pila (cima).

Métodos básicos de la pila: Iniciar Insertar Eliminar Verificar pila Vaciar pila Obtener cima

Un programa que implementa esta estructura es Kardex, este es un registro organizado de la mercancía que se tiene en un almacén para hacerlo es necesario un inventario de todo el contenido, la cantidad, un valor de medida y el precio unitario. Kardex utiliza un sistema de inventario perpetuo o uno periódico. El permanente permite un control constante del inventario perpetuo o uno periódico. El permanente permite un control constante del inventario, llevando el registro de cada unidad que se ingresa y sale, pudiendo conocer el saldo exacto y el valor de la renta. Además permite la determinación del costo en el momento exacto de la venta, debido a que la salida de un producto, se registra su cantidad y costo.

Pila

pila.txt
pila.txt (788 o)

Cola

Estas se asemejan a una cola normal es decir; por un extremo de la cola se sale mientras por el otro se puede entrar, la cola (estructura de datos) se utiliza para almacenar datos según su orden de aparición, y solo se puede entrar por un lado de la cola y salir por el otro extremo.

Métodos básicos de la cola Crear Cola Insertar Retirar Cola vacía Cola llena Obtener frente Tamaño de la cola

Una aplicación de ella la encontramos en: (Estructura de datos en java Joyanes) “Numerosos modelos de sistemas del mundo real son de tipo cola: la cola de impresión en un servidor de impresoras, los programas de simulación, las colas de prioridades en organización de viajes. Una cola es la estructura típica que se suele utilizar como almacenamiento de datos, cuando se envían datos desde un componente rápido de una computadora a un componente lento (por ejemplo, a una impresora). ”(pag. 311).

Cola

cola.txt
cola.txt (412 o)

Listas Enlazadas

Es una representación enlazada de elementos de un cierto tipo de datos, la idea básica es construir una lista cuyos elementos llamados nodos tendrán dos partes, una contiene información y es de tipo simple y la segunda es un puntero que apunta al siguiente elemento de la lista. La diferencia entre listas enlazadas simples y dobles es que las dobles requieren más espacio y sus operaciones resultan más costosas pero facilitan su manipulación pues se puede tener acceso a un elemento de la lista en ambas direcciones, también se puede insertar o borrar un nodo si damos su dirección pero en las listas simples requieren la dirección del nodo anterior para borrar o insertar correctamente. Las listas enlazadas dobles apuntan tanto a quien las apunta como a quien tienen en frente como (Sauceda 2015) menciono “son elefantes mutantes que tienen dos cabezas y todos van tomados de sus trompas”.

Métodos básicos de las listas:

Inicialización o creación

Insertar

Eliminar

Buscar

Recorrer

Comprobar

Imprimir 

Podemos implementar este tipo de estructura para un supermercado cuando pasamos lo que compramos el cajero ingresa los datos de la compra y estos se guardan en la lista y ocupara el tamaño exacto de la lista no importa cuantos productos llevemos y podemos sacar de la lista cualquiera que no queramos llevar sin importar el lugar de su ubicación.

listas.txt

listas.txt
listas.txt (4.4 ko)

Arboles (BB y AVL)

Alfred V. Aho,   John E, Horpcoroft   Jeffrey D. Ullman  (1983) Estructura de datos y algoritmos

“Un árbol es una estructura jerárquica sobre una colección de objetos. Los árboles se usan para organizar información en sistemas de bases de datos y para representar la estructura sintáctica de un programa fuente en los compiladores”(pag.76).

Estos se organizan en forma que el nodo raíz sea lo más importante del árbol luego los datos de menor tamaño se van a la izquierda y los de mayor tamaño a la derecha.

Existen dos tipos de árboles los arboles binarios de búsqueda (ABB) y AVL (se llama a si por los creadores de tal estructura Adelson- Velskii y Landis).

Los AVL se diferencian por su estructura los ABB pues son balanceados es decir que el factor de equilibrio esta de 1 a -1 mientras que el ABB no se preocupa por eso solo se  dedica  a almacenar ”izquierda-derecha, izquierda-derecha” si saber su factor de equilibrio.

Métodos que implementan

Crear

Construir (crea la raíz)

Verificar si esta vacío

ObtenerRaíz

ObtenerIzquierdo

ObtenerDerecho

Borrar

Insertar

Búsqueda Post-orden (raíz, izquierdo, derecho.

Búsqueda In-orden (izquierdo, raíz, derecho)

Búsqueda Pre-orden­  (raíz, izquierdo, derecho)

Método extra del AVL

Rotación (implementado para obtener la característica esencial del AVL y es que este equilibrado)

Aplicación

Se podría usar un árbol en una aplicación en la que se use quiera ver el nota de un grupo de alumnos usaríamos el 60 de nodo raíz y los reprobados quedarían en el sub árbol izquierdo y los aprobados en sub-árbol derecho.

Código ABB

ABB.txt
ABB.txt (4.9 ko)

Código AVL

AVL.txt
AVL.txt (7.3 ko)

Grafos

Usualmente las aplicaciones que implementan grafos son las que buscan modelar rutas, planificar tareas,  incluso es implementada por sistemas de geo-posicionamiento global.

Es una representación de una gráfica cuyos punto de interés son llamados vértices estos a su vez están unidos por líneas que las conocemos como aristas.

Una definición formal de grafos que recopile de http://www.monografias.com/trabajos16/grafos/grafos.shtml  es:

“Un grafo es una terna G = (V, A, j), en donde V y A son conjuntos finitos, y j es una aplicación que hace corresponder a cada elemento de A un par de elementos de V. Los elementos de V y de A se llaman, respectivamente, "vértices" y "aristas" de G, y j asocia entonces a cada arista con sus dos vértices”.

 

Métodos de los grafos

Arista (u, v).

Arista Peso (u, v, w).

Borra Arista (u, v).

Elimina del grafo la arista (u, v).

Adyacente (u, v).  Operación que devuelve cierto si los vértices u, v están unidos.

Nuevo Vértice (u)

Borra Vértice (u, v)

Recorrer

 

Tipos de recorrido en un grafo

Recorrer consiste en visitar tomando un vértice de partida y analiza los enlaces a otros vértices, esto se puede hacer de dos formas en profundidad y en anchura:

 

Anchura

Los pasos a seguir son:

  1. Marcar el vértice de partida
  2. Meter en la cola el vértice de partida
  3. Entrar en un bucle

3.1     quitar el nodo frente de la cola w  visitar w

3.2   meter en la cola todos los vértices adyacentes a w que no estén marcados como visitados

       4. Fin

 

Profundidad

Los pasos a seguir son:

  1. se escoge el vértice de partida y se mete en la pila
  2. se meten en la pila sus adyacentes no marcados y se marcan
  3. fin

 

Se pueden clasificar en dos tipos: los grafos dirigidos y los no dirigidos.

Dirigidos

Según Cairo y Guardati Estructuras de Datos (pág. 281) se distinguen por que “cada arista a tiene una dirección asignada; es decir, cada arista esta asociada a un par ordenado (u, v) de vértices de G [grafica].”

No dirigidos

Sus aristas son un par no ordenado de vértices esto alude a que también la arista (camino) tiene un costo para llegar a sí mismo.

Explicación del Ing. Miguel Eduardo Sacumuta

https://www.youtube.com/watch?v=9Gn-QDXad-s

Una explicacion sencilla de lo que son los grafos.

Representación de Grafos

Es existen varias opciones para representar los grafos todo depende de las necesidades ya que se puede usar matriz de adyacencia o una representación mediante listas de adyacencia, para un grafo con muchas aristas, es preferible usar una matriz, en cambio sí son pocas se usan listas de adyacencia que se ajustan al número de ellas.

Matriz de adyacencia

http://lamarchadufour.wikispaces.com/file/view/Grafos_6.jpg/292237223/Grafos_6.jpg

Es una matriz que se llena con binarios (0 y 1) estos indican si hay conexión entre dos nodos ( i , j ) 0 sin no hay conexión , y 1 si existe.

Lista de Adyacencia

http://upload.wikimedia.org/wikipedia/commons/6/6f/Listas_de_adyacencia.jpg

Si se representa un grafo mediante listas, la regla es que la que (Cairo) menciono en su libro “tendrá tantas lista como vértices tenga” es decir cada lista representa las aristas con vértice en el origen del nodo de la lista “raíz”.

Matriz de Caminos

También llamada matriz de costos ya que permite manipular mejor la información tal que podamos saber el costo de los caminos al conocerlos podemos obtener un camino más corto de un vértice a otro, o utilizar la información para otros fines.

Matriz de costos

costos.png
costos.png (83.7 ko)

Algoritmo de Dijkstra

Dijkstra busca un camino más corto a través de la matriz de caminos ¿Cómo lo hace?

Primero debe tenerse en cuenta que las aristas deben tener un costo no negativo.

Luego se debe tener dos arreglos S y D y la matriz de caminos.

S almacena los vértices de los cuales se conoce la distancia mínima usualmente se inicia con el

Vértice de partida.

D de almacena el menor costo de los vértices visitados

Al final del recorrido de la matriz de costos D tendrá la distancia mínima entre el vértice de partida y cada uno de los vértices al cual tiene acceso.

Dijkstra

Algoritmo Voraz

Yaddy sanchez y Wilfredo torrros En la pagina con vinculo http://www.unicauca.edu.co/matematicas/eventos/log&co/MEMORIAS/AlgoritmosVoraces_abstract.pdf lo definen de una mare muy acertada mencionan: “Son utilizados para solucionar problemas de optimización y toman decisiones basándose en la información que tienen de modo inmediato, sin tener en cuenta los efectos que estas decisiones pueden tener a futuro”.

Ejemplos de algoritmos voraces son: dijkstra, Prim, Kruskal.

Algoritmo Repercusivo

Un algoritmo recursivo es aquel que se llama a si mismo, para lograrlo basta con hacer la llamada correspondiente dentro de cuerpo del sub-programa que se quiere hacer llamar al finalizar la ejecución es sustituida por el valor de retorno. Todo proceso recursivo puede convertirse en iterativo y viceversa la diferencia radica que los recursivos son más simples, pero son más lentos a la hora de ejecutarse y requieren más recursos.

Ejemplos de estructuras que pueden ser recursivos: Quicksort Pilas Colas

Quicksort

quick.txt
quick.txt (2.6 ko)

Reflexiones

Analizamos varios algoritmos, queda ganar más experiencia en el empleo de ellos pues todos son importantes sin embargo, eso es cierto si se aplican correctamente, a lo que me refiero es, “que una decisión correcta, tomada por una razón equivocada puede ser incorrecta”.  Si tenemos las herramientas solo queda aprender a usarlas en momento correcto, para optimizar nuestros códigos.  

El trabajo realizado fue muy apropiado ya que son los temas y la investigación realizada hace que el los temas desarrollados en clase se tengan una mejor compresión o enfoque.