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.
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.
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.
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).
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.
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.
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:
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:
Se pueden clasificar en dos tipos: los grafos dirigidos y los no 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].”
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.
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.
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.
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.
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.
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.
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
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.
© 2015 Kimberly Ardon Excepto mención contraria explícita.
Última actualización: 2015-05-03.
2712 página(s) cargada(s).