1.Repaso de temas y homogenización de terminología:
Conjuntos: conjunto, elemento, pertenencia. Inclusión de conjuntos. Unión, intersección y diferencia. Sus propiedades.Relaciones Binarias: Dominio y Rango. Relación Inversa. Restricciones. Casos particulares: función, relaciones totales, inyectivas y suryectivas.Relaciones con dominio y rango coincidentes. Propiedades que caracterizan casos particulares de relación: reflexiva, antireflexiva, no reflexiva, simétrica, antisimétrica, débilmente antisimétrica, no simétrica, transitiva y completa. Tipos de relaciones: Preorden parcial, Orden parcial, Orden Total y Buen Orden. Equivalencia.Operaciones con relaciones: Operaciones propias de conjunto: unión, intersección y diferencia. Composición de relaciones binarias: sus propiedades.Estructuras algebraicas. Monoides. Monoides sobre conjuntos: Operadores + y *.Clausuras y generadores. Extensión de funciones y operaciones a subconjuntos.
2.Explicitación del objetivo de la materia.
Las estructuras. Dato e información. Doble acepción de estructuras de datos: estructura de la información y estructura de almacenamiento. Algoritmos: análisis y diseño.
3.Terminología de teoría de grafos
Definición: grafos, digrafos, p-grafos, p-digrafos. Orden. Funciones de incidencia y adyacencia que relacionan arcos y vértices. Grado. Vértices aislados. Grafos triviales. Sub(di)grafo, (di)grafo parcial. (di)Grafos bipartitos. Cadena, camino, ciclo, cociclo, circuito, cocircuito. Fuentes y sumideros. Conectividad, componente (conexa). Conectividad fuerte, bloque. Conectividad cuasi-fuerte. Raíz y raíz del grafo inverso. Árboles, árbol subtenso, foresta. Arborescencias.
4.Propiedades y demostraciones de grafos.
Número ciclomático y número cociclomático, y su deducción a partir de las magnitudes fundamentales. Caracterizaciones equivalentes de árbol y arborescencia. Construcción de base de ciclos y cociclos a partir de un árbol subtenso. Construcción sistemática de árboles subtensos. Lema de los 3 colores. Distancias en grafos.
5.Evaluación de algoritmos.
Planteo. Problema. Función de costo. Necesidad de una función de evaluación. Propiedades de tales funciones. Medidas en tiempo y espacio. Elección de la función de evaluación. Familias de problemas. Solución parametrizada. Función O, W y Q. Propiedades. Complejidad. Clases de Complejidad.
6.Herramientas para resolución de recurrencias.
Funciones generatrices. Inducción completa. Recurrencias típicas comunes a muchos problemas.
7.Listas, Pilas y Colas.
Listas vinculadas y secuenciales. Incidencia del orden, Incidencia del tipo de recurrencia que la define. Operaciones: localización, alta, baja y evocación. Análisis de costos. Costos a priori y a posteriori. Búsqueda binaria: bisección y trisección.Lista Invertida: alta, baja, evocación, localización. Análisis de costos.Pilas y colas: alta y baja (o evocación). Su implantación secuencial y vinculada.
8.Lista de 2 niveles.
Descriptores de listas, representación computacional. Listas de descriptores. Optimización de parámetros.
9.Direccionamiento Directo.
Condiciones para su aplicación. Relajación de la exigencia de totalidad. Ejemplos de funciones de enumeración. Otras aplicaciones de las funciones de enumeración.
10.Árboles computacionales.
Definición. Representación computacional. Distinción con el árbol de teoría de grafos. Árbol completo, lleno y balanceado. Almacenamiento por extensión y por comprensión. Operaciones básicas sobre árboles. Determinación del esfuerzo medio y máximo de búsqueda. Magnitudes, deducción de relaciones entre ellas. Contar árboles: cantidad total y frecuencia de cada forma.
11.Parva.
Definición. Operaciones. Aplicaciones: Heapsort, Algoritmo de Dijkstra (con costo por arco) y Algoritmo de Prim.
12.Distribución pseudo-aleatoria de datos.
Motivación, las dos partes del problema. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Su motivación. Esfuerzos medios en espacio y en tiempo. Deducción de los distintos esfuerzos para rebalse separado y para realeatorizado a una ranura por balde.
13.Skip Lists.
Definición. Operaciones. Análisis de costos. Análisis de ventajas y desventajas respecto de otras estructuras.
14.Técnicas de diseño de algoritmos.
Técnicas ávidas, programación dinámica, dividir para vencer. Ejemplos de aplicación en algoritmos sobre grafos: Dijkstra, Floyd, Warshall, Kruskal y Prim. Otros ejemplos de aplicación de las distintas técnicas: ordenamientos, búsquedas, codificación de Huffmann, etc...
|