Apuntes, tps y TDAs de la cátedra algoritmos y programación 2 - 75.41 Mendez
Los objetivos de la materia son:
- Que se maneje de modo correcto el diseño de un TDA de acuerdo a las exigencias de una determinada situación problemática.
- Que se apliquen estrategias de solución de problemas complejos, definiéndolas en forma abstracta.
- Que se puedan plantear y desarrollar distintas implementaciones para un TDA eligiendo la más adecuada en función de su eficiencia temporal y espacial.
- Que se aplique de modo conveniente los conceptos de complejidad computacional para garantizar la eficiencia del producto final.
Orden en que fueron hechos los trabajos a lo largo de la cursada:
1) TP1
2) TDA Pila
3) TDA Cola
4) TDA Lista
5) TDA ABB
6) TDA Hash
7) TP2
8) TDA Grafo TPcito (TDA Heap)
Todos fueron realizados en C.
- Memoria dinámica, punteros y su aritmética, compilación, casteo, valgrind
- Concepto de TDA: especificación e implementación.
- TDA pila , TDA cola, TDA Lista, y sus diferentes implementaciones
- Iteradores externos, internos
- Complejidad temporal y espacial de algoritmos. Medidas asintóticas: notación Big Omega y Big Theta. Orden de complejidad de un algoritmo. El teorema Maestro.
- Recursividad. Principios de la recursividad. Tipos de recursividad (directa, indirecta, de cola). Diseño de algoritmos recursivos. Pilas y recursividad.
- Análisis de la estrategia "Dividir y conquistar" ("Divide and Conquer").
- Búsqueda y Ordenamiento. Búsqueda secuencial. Búsqueda binaria. Mergesort, Quicksort, Counting sort, Radix sort, Bucket sort. Comparación de la eficiencia de distintos métodos de ordenamiento interno.
- Estructura de árbol binario de búsqueda. Balanceo de árboles. Árboles AVL.
- Conceptos de árbol B, B+, B*, arbol rojo-negro, recorridos.
- TDA Heap, Heapsort, Heapify.
- El TDA Diccionario. Primitivas e implementaciones diversas. Hash, funciones, abierto, cerrado, colisiones
- Grafos no dirigidos y grafos dirigidos. Recorridos en profundidad y en anchura.
- Dijkstra, Floyd, Prim, Kruskal