“Las computadoras son increíblemente rápidas, precisas y estúpidas; los humanos son increíblemente lentos, imprecisos y brillantes; juntos son poderosos más allá de la imaginación” – Albert Einstein
Un algoritmo es una secuencia finita de operaciones, organizadas para realizar una tarea determinada. Las estructuras de datos son la forma en que se organizan los datos para ser usados. Puede ser una colección de variables, posiblemente de diferentes tipos de datos, conectadas de un modo determinado.
Una estructura de datos bien organizada debe permitir realizar un conjunto de acciones sobre los datos de tal forma de minimizar el uso de los recursos y el tiempo empleado para efectuar la operación.
Pilas
Es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del ingles Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos.
El método de pila para la evaluación de expresiones fue propuesta en 1955 y 2 años después patentado por Friedrich L. Bauer, quién recibió en 1988 el premio IEEE. Computer Society Pionner Award por su trabajo en el desarrollo de dicha estructura de datos.
Pila de llamada
Es un segmento de memoria que utiliza esta estructura de datos para almacenar información sobre los llamadas a subrutinas actualmente en ejecución en un programa en proceso.
Cada vez que una nueva subrutina es llamada, se apila una nueva entrada con información sobre esta tal como sus variables locales. En especial, se almacena aquí el punto de retorno al que regresar cuando esta subrutina termine (para volver a la subrutina anterior y continuar su ejecución después de esta llamada).
Como tipo abstracto de datos
La pila es un contenedor de nodos y tiene dos operaciones básicas, push (o apilar) y pop (o desapilar). “Push” añade un nodo a la parte superior de la pila, dejando por debajo el resto de los nodos. “Pop” elimina y devuelve el actual nodo superior de la pila.
Operaciones con pilas
Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.
Crear: se crea la pila vacía.
Apilar: se añade un elemento a la pila (push).
Desapilar: se elimina el elemento frontal de la pila (pop).
Cima: devuelve el elemento que está en la cima de la pila (top o peek).
Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.
Colas
Es una estructura de datos lineal, es decir una colección de elementos en la cual cada elemento tiene un sucesor y un predecesor únicos, con excepción del primero y del último. La estructura cola se caracteriza porque las operaciones de inserción y eliminación de elementos deben hacerse por extremos diferentes.
El frente o principio de la cola será el extremo en el cual se eliminarán elementos, mientras que al final será el extremo en el cual se harán las inserciones.
Clasificación de Colas
Es aquella en la cual el sucesor del último elemento es el primero.
Por lo tanto, el manejo de las colas como estructuras circulares permite un mejor uso del espacio de memoria reservando para la implementación de las pilas.
Colas dobles
Permiten realizar las operaciones de inserción y eliminación por cualquiera de sus extremos.
Una cola doble también puede ser circular, en dicho caso, será necesario que los métodos de inserción y eliminación (sobre cualquiera de los métodos de inserción y eliminación (sobre cualquiera de los extremos) considere el movimiento adecuado de los punteros.
Otros tipos:
Colas de Prioridad
En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay dos formas de implementación.
Por lo tanto, el manejo de las colas como estructuras circulares permite un mejor uso del espacio de memoria reservando para la implementación de las pilas.
Colas dobles
Permiten realizar las operaciones de inserción y eliminación por cualquiera de sus extremos.
Una cola doble también puede ser circular, en dicho caso, será necesario que los métodos de inserción y eliminación (sobre cualquiera de los métodos de inserción y eliminación (sobre cualquiera de los extremos) considere el movimiento adecuado de los punteros.
Otros tipos:
Colas de Prioridad
En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay dos formas de implementación.
Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
Bicolas de entrada registrada: Son aquellas donde la inserción solo se hace por el fina, aunque podemos eliminar al inicio o al final.
Bicolas de salida restringida: Son aquellas donde solo se elimina por el final, aunque se puede insertar al inicio y al final.
Arboles y Características:Bicolas de entrada registrada: Son aquellas donde la inserción solo se hace por el fina, aunque podemos eliminar al inicio o al final.
Bicolas de salida restringida: Son aquellas donde solo se elimina por el final, aunque se puede insertar al inicio y al final.
Los árboles son estructuras de datos no lineales.
Cada elemento conocido con el nombre de NODO.
Un árbol se define como una colección de nodos donde cada uno además de almacenar información, guarda las direcciones de sus sucesores.
Se conoce la dirección de uno de los nodos, llamado raíz y a partir de el se tiene acceso a todos los otros miembros de la estructura, grafos, anidación de paréntesis y diagramas de venn.
Hijo: Es aquel nodo que siempre va a tener un nodo antecesor o padre, son aquellos que se encuentran en el mismo nivel.
Padre: Es aquel que tiene hijos y también puede tener o no antecesores.
Hermano: Dos nodos son hermanos si son apuntados por el mismo nodo, es decir si tienen el mismo padre.
Raíz: Es el nodo principal de un árbol y no tiene antecesores.
Hoja o terminal: Son aquellos nodos que no tienen hijos o también los nodos finales de un árbol.
Interior: Se dice que un nodo es interior si no es raíz ni hoja.
Nivel de un nodo: Se dice que el nivel de un nodo es el número de arcos que deben ser recorridos, partiendo de la raíz para llegar hasta él.
Altura del árbol: Se dice que la altura de un árbol es el máximo de los niveles considerando todos sus nodos.
Grado de un nodo: se dice que el grado de un nodo es el número de hijos que tiene dicho nodo.Tipos de Arboles:
Arboles binarios: Son árboles donde cada nodo sólo puede apuntar a dos nodos
Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vacío o está formado por una raíz con dos árboles binarios disjuntos, es decir, dos descendientes directos llamados subárbol izquierdo y subárbol derecho.
Los árboles binarios (también llamados de grado 2) tienen una especial importancia.
Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.
Arboles Binarios De Busqueda:
Son árboles binarios ordenados. Desde cada nodo todos los nodos de una rama serán mayores, según la norma que se haya seguido para ordenar el árbol, y los de la otra rama serán menores.
Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.
Arboles- B:
Son árboles cuyos nodos pueden tener un número múltiple de hijos tal como muestra el esquema.
Los grafos se pueden clasificar en dos grupos:
Dirigidos y no Dirigidos.
En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que representan dos arcos diferentes
En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que representan dos arcos diferentes
En un grafo no dirigido el par de vértices que representa un arco no está ordenado
Tipos De Grafos:
Grafo regular: Aquel con el mismo grado en todos los vértices.
Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto.
Grafo completo: Aquel con una arista entre cada par de vértices.
Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no
Están conectados, esto es, que son vértices aislados.
Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia
Biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan
unidos por una arista en común.
Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
Grafo conexo: Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
Dígrafo (GRAFO DIRIGIDO): A un grafo dirigido se le puede definir como un grafo que contiene aristas dirigidas, como en el siguiente caso.
Representación de los grafos en programas
Representación mediante matrices:
La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos se pueden ver cómo relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
Representación mediante listas:
En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de los nodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
Representación mediante matrices dispersas:
Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.
¿Cual es la Utilidad de Datos Avanzados en la Programacion?
Las estructuras de datos son un medio para manejar grandes cantidades de datos de manera eficiente para usos tales como grandes base de datos (conjunto de archivos organizados) y servicios de indización de Internet. Por lo general, las estructuras de datos eficientes son clave para diseñar eficientes algoritmos y algunos métodos formales de diseño y lenguajes de programación destacan las estructuras de datos, en lugar de los algoritmos, como el factor clave de organización en el diseño de software.
