B2T3 Estructura de datos y Algoritmos Flashcards
(66 cards)
Que es el Tipo Abstracto de Datos (TAD)?
TAD = ¿Que resuelvo?
Modelo matemático para definir los tipos de datos (comportamiento Primitivos).
Especifica operaciones y comportamientos sin detallar la implementación.
Que es la estructura de datos?
Estructurad de datos = ¿Cómo resuelvo?
Concepto más concreto que TAD(tipo abstracto de datos) orientado a la implementación.
Define como se almacenan y manipulan los datos (como se implementan).
Un TAD puede tener varias estructuras de datos posibles para su implementación.
Dime algunos ejemplos de Tipos Abstractos de Datos (TAD) y luego me dices posibles Estructuras de datos.
1 List = Secuencia
Array, Lista enlazada
2 Set/Multiset (con repetidos) = Grupo
Árbol rojo-negro, tabla hash
3 Queue/Double-ended Queue (bicola)=cola
Array, Lista [doble_]enlazada
4 Stack = Pila
Array, Lista enlazada
5 Priority Queue (heap)= Cola con prioridad
Montículo (propiedad)
6 Tree = árbol
7 Graph = Grafo
Matriz, Array de listas enlazadas
8 Associative Array = Diccionario o Mapa
Tabla de hash
Dime las operaciones por defecto que se pueden hacer con los tipos de datos abstractos Stack, Queue y List
Stack (pila) “LIFO”: push, pop, isEmpty, top
Queue (cola) “FIFO”: enqueue, dequeue, isEmpty, top(top=consulta)
List (lista): isEmpty, insertarDelante, insertarDetrás, head, tail
Como funciona el tipo abstracto de datos (primitiva) tail en List?
Cada vez que llamemos a tail nos devuelve la Lista sin el primer elemento (cabeza).
lista = [1,3,7,2,5]
tail(tail(tail(lista))) = [2,5]
head(tail(tail(tail(lista)))) = [2]
Estructura de datos Tabla Hash, características principales.
1 Los datos operan con la función hash y luego obtienen su posición en la tabla hash
2 Pueden ser funciones hash que generen datos circulares, como obtener el resto de una división (mod)
3 Si se aplica mod los datos se devuelven en progresión circular, por lo que saldrán repetidos (colisiones) cuanto la tabla sea más pequeña más colisiones saldrán
4 Para solucionar las colisiones se encadena una lista enlazada por cada campo de la tabla hash
Estructura de datos Montículo, características principales
1 Están en forma de árbol y el vértice/nodo más alto/raíz será el máximo(max-heap)/mínimo(min-heap)
2 Un vértice más alto será mayor/menor que los vértices más bajos
2 Con un árbol binario -> Montículo binario
3 Con un array -> hijos del nodo n -> 2n y 2n+1
En la imagen si vemos el array de nodos, podemos sacar la posición de los dos hijos de cada nodo con 2n y 2n+1
Parámetros de un árbol: Orden, Grado, Profundidad, Altura, Factor de equilibrio, Árbol Completo, Peso
0 Orden de un árbol: Nº máximo de hijos que puede tener cualquier nodo.
1 Grado de un nodo: nº de hijos directos que tiene un nodo particular.
2 Profundidad de un nodo: nº aristas desde la raíz al nodo (nodo raíz = 0).
3 Altura de un nodo: Trayectoria más larga en nº de aristas desde ese nodo a una hoja.
3B Nivel de un árbol: Raiz=Nivel 1, 1ºhijos=Nivel2, 2ºhijos=Nivel3…..
4 Factor de equilibrio (FE): Diferencia altura entre subárbol izquierda y derecho.
5 Árbol completo: Tiene todos sus hijos, es decir, todos los nodos llegan al orden del árbol (máximo de hijos).
6 Peso: Nº de nodos que tiene el árbol
1 Recorridos en profundidad: Preorden, Inorden y Postorden
2 Recorridos en amplitud
* Recorridos en Profundidad*
1 Preorden (RID): Raíz, izq, derecha
2 Inorden (IRD): Izq, raíz, derecha
3 Postorden (IDR): Izq, derecha, raíz
** Recorridos en Amplitud **
1 Recorrer el árbol por niveles
Árboles binarios búsqueda y fibonacci
- Árboles binarios: Tienen orden 2.
1 Árbol binario de búsqueda: Recorrido Inorden (IRD) -> Devuelve elementos ordenados ya que datos IZQ > RAÍZ> DER
2 Árbol binario de Fibonacci (AVL):
Árboles equilibrados (auto-balanceables), tipos
Factor de equilibrio(altura de subarboles) es -1, 0 o 1.
—Tipos—
1 AVL (rotaciones)
2 AA
3 rojo-negro
4 splay
5 árbol B
Árboles B, B+ y B*
- Tienen más de una clave
- Usado en BBDD y Sistemas de ficheros
- Cada nodo puede tener +2 hijos (nº hijos se llama orden M)
— Árbol B+ —
1 Mantiene datos ordenados
2 Inserciones y borrados en tiempo logarítmico (proporcional)
3 Cada nodo tiene como máximo M hijos
4 Cada nodo (excepto raíz) tiene mínimo M/2 claves
— Árbol B+ —
1 Nodos internos sólo contienen claves y punteros
2 Los nodos hojas sólo tienen datos y punteros
3 Los nodos hojas estan enlazados entre sí por punteros
— Árbol B* —
1 Realiza reestructuración (fusión y rupturas de nodos) para garantizar densidad de ocupación 2/3
Representación de los Grafos
— Representación —
1 Listas de adyacencias: array de vértices + listas enlazas por cada vértice
2 Matrices de adyacencia: Matriz cuadrada (desperdicia memoria con muchos nodos)
- filas y columnas = orden del grafo
- Valores interiores marcan si están conectados (1,0) y si lo están y están ponderados el peso (4”vertices”)
— Parámetros —
1 Dirigidos o dígrafo (sentido único)
2 Grafo conexo (Todos nodos conectados)
3 Multígrafo (+1 arista entre dos vertices)
4 Etiquetado/Ponderado (Peso numerico en aristas)
5 Orden del grafo (nº vértices)
6 Grado de un vértice (nº arcos incidentes)
Parámetros de los Grafos
— Parámetros —
1 Dirigidos o dígrafo (sentido único)
2 No Dirigidos (ambos sentidos)
3 Grafo conexo (Todos nodos conectados)
4 Multígrafo (+1 arista entre dos vertices)
5 Etiquetado/Ponderado (Peso numerico en aristas)
6 Orden del grafo (nº vértices)
7 Grado de un vértice (nº arcos incidentes)
— Representación —
1 Listas de adyacencias: array de vértices + listas enlazas por cada vértice
2 Matrices de adyacencia: Matriz cuadrada (desperdicia memoria con muchos nodos)
- filas y columnas = orden del grafo
- Valores interiores marcan si están conectados (1,0) y si lo están y están ponderados el peso (4”vertices”)
Algoritmos de los Grafos
1 PRIM (árbol recubrimiento min)
“camino mínimo pasar todos los vértices”
2 KRUSKAL (árbol recubrimiento min) “ STP”
“camino mínimo pasar todos los vértices”
3 DIJKSTRA (camino min 2 vértices, No soporta pesos negativos) OSPF
4 BELLMAN-FORD (camino min 2 vértices) RIP
7 FLOYD-WARSHALL (camino min entre todos los vertices, origen no unico)
5 FORD-FULKERSON (camino que maximicen el flujo entre 2 nodos)
6 TARJAN (Crea/Identifica grupos de vértices fuertemente conexos)
Que es un algoritmo?
Un conjunto de reglas que, aplicadas sistematicamente a unos datos de entrada apropiados, resuelven un problema en un número finito de pasos elementales.
Un algoritmo debe terminar.
Técnicas de análisis y diseño de algoritmos:
1 Divide y vencerás: TOP-DOWN
“Dividiendo en problemas más pequeños”
2 Voraces: Opción óptima en cada paso
Dijkstra/A*/Prim/Kruskal
3 Probabilisticos: Montecarlo/Las Vegas
4 Backtracking: Explora árbol soluciones
5 Programación dínamica: BOTTOM-UP o TOP-DOWN + memorización
“Combinar subproblemas óptimos”
Representación de la complejidad espacial y temporal de un algoritmo con conta superior asintótica Big O notation
Ordenado por crecimiento de más lento a más rápido:
1 O(1) -> Constante -> Acceder a elemento de array por índice
2 O(log(n)) -> Logarítmica -> Búsqueda binaria en un arreglo ordenado
3 O(n) -> Lineal -> Recorrer un array
4 O(n log(n) -> n Logarítmica -> Merge o Sort
5 O(n^2) -> Cuadrática -> Comparar pares de elementos
6 O(2^n) -> Exponencial -> Problemas de optimización con recursión exponencial
7 O(n!) -> Factorial -> Generación de todas las permutaciones de una lista
8 O(n^n) -> Potencial exponencial
Clasificación de algoritmos de ordenación
1 Interno (memoria) Externo (fichero)
2 Natural (Tarda lo mínimo si la entrada está ordenada)
3 Estable (mantiene orden relativo origina para claves iguales
Tipos de algoritmos de ordenación
1 Exchange Sorts: Intercambiar y mover datos. Burbuja / Quick Sort / Cocktail
2 Selection Sorts: Busca la información. Seleccion / Heap Sort
3 Insertion Sort: Busca donde insertar. Inserción / Shell Sort
4 Merge Sorts: Mezclar. Merge Sort
5 Distribution Sorts: No comparan. Tiene cajones y distribuye los datos en base a un criterio. Bucket Sort o Bin Sort / Radix Sort
Explícame los siguientes algoritmos de ordenación: Burbuja y Inserción Directa.
1 Burbuja -> O(n^2) -> Va desplazando el nº más grande a la derecha a base de comparaciones e intercambios entre elementos adyacentes. O(n) si la lista ya esta ordenada
2 Inserción Directa -> O(n2) -> Busca donde insertar el dato y desplaza los siguientes elementos. Si hace búsqueda binaria -> Inserción binaria.
Explícame los siguientes algoritmos de ordenación: Merge Sort y Quick Sort.
1 Merge Sort -> O (n log n) -> (DIvide y vence) Es recursivo. Divide la lista en sublista hasta llegar al caso más sencillo para comparar (parejas). Luego mezcla las sublistas para obtener una lista ordenada.
2 Quick Sort -> O (n log(n)) -> (Divide y vence) Es recursivo. Elegimos un pivote. En la primera pasada, los menores del pivote se ponen a la izquierda y los mayores a la derecha. 2ª pasada, hacemos 2 llamadas de T(n/2). Peor caso O(n^2) si el pivote es el menor o el mayor de los valores.
Explícame los siguientes algoritmos de ordenación: Heap Sort o Montículos y Selección.
1 Heap Sort o Montículos -> O(n log(n)) -> Se meten los datos en un montículo Max-Heap y luego se realizan N llamadas a EliminarMax(). Por tanto al regenerarse se encuentra la nueva raíz max hasta ordenarlos todos.
2 Selección -> Siempre O(n^2) -> Primero busca el mínimo y lo coloca el primero. Luego busca el siguiente mínimo y lo coloca después.
Explícame los siguientes algoritmos de ordenación: RadixSort y BucketSort o BinSort.
1 RadixSort -> O(n K) ->Se basa en el número de cifras de los números a ordenar. LSD usa el digito menos significativo y MSD el más significativo.
2 BucketSort o BinSort -> O(n) -> Distribuye los números en casilleros y dentro de cada casillero aplicas el criterio que sea como otro algoritmo de ordenación.
