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