Ministerio de Cultura y Educación
Universidad Nacional de San Luis
Facultad de Ciencias Físico-Matemáticas y Naturales
Departamento: Informatica
Área: Area I: Datos
(Programa del año 2006)
(Programa en trámite de aprobación)
(Programa presentado el 12/09/2006 08:40:08)
I - Oferta Académica
Materia Carrera Plan Año Periodo
ESTRUCTURA DE DATOS Y ALGORITMOS LIC. CS. COMP. 006/05 2 2c
ESTRUCTURA DE DATOS Y ALGORITMOS PROF.CS.COMP. 007/05 2 2c
II - Equipo Docente
Docente Función Cargo Dedicación
REYES, NORA SUSANA Prof. Responsable P.ADJ EXC 40 Hs
RICKEBOER, HUGO Prof. Co-Responsable VISITANTE Hs
LUDUEÑA, VERONICA DEL ROSARIO Responsable de Práctico JTP EXC 40 Hs
BUSTOS, CRISTIAN JAVIER ALEJAN Auxiliar de Práctico A.1RA SEM 20 Hs
TARANILLA, MARIA TERESA Auxiliar de Práctico A.1RA EXC 40 Hs
VILLEGAS AGUILERA, ANA VALERIA Auxiliar de Práctico A.1RA EXC 40 Hs
III - Características del Curso
Credito Horario Semanal Tipificación Duración
Teórico/Práctico Teóricas Prácticas de Aula Práct. de lab/ camp/ Resid/ PIP, etc. Total B - Teoria con prácticas de aula y laboratorio Desde Hasta Cantidad de Semanas Cantidad en Horas
Periodo
 Hs. 4 Hs. 3 Hs. 2 Hs. 9 Hs. 2 Cuatrimestre 07/08/2006 10/11/2006 14 126
IV - Fundamentación
Se toma en este curso el diseño de estructuras de datos considerando principalmente las evocaciones asociativas con respuesta no múltiple y algunos tipos de evocaciones no asociativas, como las extremales.
Además se inicia al alumno en el análisis de algoritmos, con el fin de que aprenda a comparar distintos algoritmos y porque es fundamental para poder diseñar buenos algoritmos.
En esta asignatura se sientan las primeras bases que serán utilizadas por la asignatura Organización de Archivos y Bases de Datos I para construir una base sólida en las disciplinas Estructuras de Datos y Bases de Datos, de forma tal que si opta por obtener sólo el título intermedio tiene la idoneidad suficiente en la temática contando con los conceptos, principios y teorías que constituyen el ámbito de competencia. En caso de que el alumno persiga obtener el título de licenciado, tiene una formación sólida como para encarar un estudio teórico más fuerte de esta temática, que será desarrollado en la asignatura Base de Datos II.


V - Objetivos
Al finalizar el curso se pretende que el alumno sea capaz de:
- Manejar con idoneidad los conceptos que involucran el diseño de estructuras de datos y algoritmos.
- Conocer algunos de los principales algoritmos y estructuras de datos, incluyendo el análisis de su desempeño.
- Analizar y diseñar algoritmos.
- Desarrollar una actitud crítica frente al uso de las estructuras de datos y algoritmos con los que se pueda enfrentar.
- Frente a una aplicación o problema particular, poder brindar una solución eficiente utilizando los conceptos vistos sobre diseño de estructuras de datos y algoritmos, y además utilizar el análisis de los algoritmos para evaluar y justificar la eficiencia de la solución elegida.
VI - Contenidos
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. 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. Visión relacional. Fundamento de la evocación asociativa. Concepto de Servicio en una estructura de datos. Altas, bajas y modificaciones. Varios servicios de evocación con eficiencia. Datos de un problema de estructuras de datos. 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, demostraciones y representación 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. Representaciones básicas de 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 (Big O), W (Big Omega) y Q (Big Theta). Propiedades. Complejidad. Clases de Complejidad.Técnicas para plantear y resolver ecuaciones de recurrencias. Funciones generatrices.

6. 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.

7. Lista de 2 niveles.
Descriptores de listas, representación computacional. Listas de descriptores. Optimización de parámetros.

8. 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.

9. Á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. Árboles Binarios de Búsqueda (árboles ordenados). Árboles Balanceados en altura (AVL). Operaciones básicas sobre árboles. Operaciones sobre árboles balanceados en altura: rotaciones simples y dobles. 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. Árboles de búsqueda auto-ajustables (splay trees).

10. Parva.
Definición. Operaciones. Aplicaciones: Heapsort, Algoritmo de Dijkstra (con costo por arco) y Algoritmo de Prim.

11. 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. Deducción de distintos esfuerzos para rebalse separado y para realeatorizado a una ranura por balde.

12. Skip Lists.
Definición. Operaciones. Análisis de costos. Análisis de ventajas y desventajas respecto de otras estructuras.

13. 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...

14. Búsqueda en Texto.
Representación de textos. Estructuras de datos para búsqueda en texto: Trie, Árboles Patricia.

VII - Plan de Trabajos Prácticos
Prácticos de aula:
-----------------
1. Repaso de relaciones y funciones.

2. Desarrollo de algoritmos para realizar búsqueda de elementos en las distintas representaciones computacionales posibles para un conjunto.

3. Funciones de evaluación: análisis de ejemplos; selección de funciones de evaluación de acuerdo al problema planteado. Notaciones Asintóticas: análisis detallado de su utilización para expresar tiempos de ejecución de un trozo de programa, incluyendo cómo se obtiene en caso de tener recursividad.

4. Análisis de distintas implantaciones de listas: diseño de los algoritmos necesarios en cada caso y cálculos de esfuerzos.

5. Teoría de Grafos: representación de grafos, aplicación de los distintos conceptos teóricos a ejemplos. Algoritmos sobre grafos.

6. Pilas y Colas: Distintas implantaciones posibles y sus algoritmos. Colas de Prioridad. Implantación y algoritmos necesarios para su manejo. Aplicaciones. Algoritmos Golosos: Dijstra, Kruskal y Prim. Técnicas de diseño de algoritmos. Análisis de los algoritmos analizados para cada técnica. Diseño de algoritmos para distintos problemas planteados como ejemplos, usando las técnicas estudiadas.


7. Árboles como estructuras de Información. Barridos en árboles.
Arbol Binario de Búsqueda: construcción de ejemplos e implantación de algoritmos. Balanceo sin utilizar técnicas de AVL. Arbol binario balanceado: construcción de ejemplos, implantación de algoritmos.

8. Implantación de lista de 2 niveles. Optimización de parámetros para distintos casos. Direccionamiento directo.
Skip List: construcción de ejemplos e implantación de algoritmos.
Distribución pseudo-aleatoria de datos: implantación de los distintos algoritmos para cada una de las estrategias de manejo de rebalse.

9. Representación de textos. Trie y Árboles Patricia: construcción de ejemplos e implantación de algoritmos. Comparación. Árboles de búsqueda Auto-ajustables: construcción de ejemplos e implantación de algoritmos.

Prácticos de máquina:
--------------------
1. Se desarrollará un práctico que consiste en el estudio de una situación real a informatizar y se programarán distintas versiones desde el punto de vista de las estructuras de almacenamiento a utilizar para cada servicio, teniendo en cuenta las estructuras que gradualmente se vayan incorporando en las teorías y prácticos de aula.

2. Implantación de una Parva de mínimos.

3. Utilizando lo realizado en el práctico anterior, se implementará algún algoritmo que necesite usar una parva (Dijkstra, Prim, etc...).

VIII - Regimen de Aprobación
- Asistencia a práctico: 70%
- Asistencia a teoría: 70%
- Entregar los ejercicios requeridos de cada práctico de aula.
- Aprobar los prácticos de máquina o sus recuperaciones.
- Aprobar el parcial o sus recuperaciones. Se toma un parcial, que tiene una recuperación y hay una recuperación por trabajo.

- Modalidad de examen final: El examen final podrá ser oral y/o escrito

Examen Libre: No se admiten alumnos libres dado que los prácticos de máquina y aula se desarrollan de manera incremental desde comienzo de cuatrimestre, por consiguiente no es posible en un examen poder evaluar correctamente este proceso.

No es una materia promocional.
IX - Bibliografía Básica
[1] INTRODUCTION TO ALGORITHMS, Autor: Cormen, Leiserson and Rivest, ISBN: 0262031418 -MIT-, Ubicación en biblioteca: 519.254 C811.
[2] FUNDAMENTOS DE ALGORITMIA, Autor: : Brassard, Gilles y Bratley, Paul, ISBN: 84-89660-00-X, Ubicación en Biblioteca: 004.021 # .B823f
[3] COMPARED TO WHAT? : AN INTRODUCTION TO THE ANAYLSIS OF ALGORITHMS, Autor: Rawlins, Gregory, ISBN: 071678243X.
[4] THE ART OF COMPUTER PROGRAMMING (VOL I Y III), Autor: Knuth, Donald E., Ubicación en biblioteca: 681.3.06 K74.
[5] GRAPHES ET HYPERGRAPHES, Autor: Berge, C., Ubicación en biblioteca: 519.28 B495.
[6] AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS, Autor: Sedgewick, Robert and Flajolet, Philippe, ISBN: 020140009X, Ubicación en biblioteca: 004.021 S448.
[7] ALGORITHMIC: THEORY AND PRACTICE, Autor: Brassard, Gilles and Bratley, Paul, Ubicación en biblioteca: : 519.681 B823.
[8] DATA STRUCTURES AND PROGRAM DESIGN IN C, Autores: Kruse, Robert L.; Leung, Bruce P.; Tondo, Clovis L., ISBN: 0-13-725649-3, Ubicación en biblioteca: 519.682.2681.3.06 K94.
[9] DATA STRUCTURES AND THEIR ALGORITHMS, Autor: Lewis, Harry R. , Denenberg, Larry, ISBN: 0-673-39736-X, Ubicación en biblioteca: 519.683.2 L674.
[10] ESTRUCTURA DE DATOS y ALGORITMOS, Autor: Mark Weiss, ISBN: 0-201-62571-7,
[11] APUNTES DE LA CÁTEDRA: Durante el dictado se entregarán apuntes confeccionados por la cátedra sobre algunos de los temas. * Repaso de Conjuntos, Relaciones y Funciones. * Descripción Informática de Conjuntos. * Pertenecia en Conjuntos Computacionales. * Evaluación de Algoritmos. * Operaciones en Conjuntos Computacionales * Teoría de Grafos (Parte I). * Teoría de Grafos (Parte II). * Lista de 2 Niveles. * Funciones de Enumeración. * Distribución Pseudo-aleatoria de Datos * Deducción de algunos esfuerzos para distribución pseudo- aleatoria de datos. * Funciones de pseudo-azar. * Estructuras de Datos Aleatorias: Skip Lists. * Costos de Búsqueda en Árbol. * Arboles Binarios Ordenados
X - Bibliografia Complementaria
[1] COMPUTER ALGORITHMS: INTRODUCTION TO DESIGN AND ANALYSIS, Autor: Baase, Sara, ISBN: 0-201-06035-3, Ubicación en biblioteca: 519.682.4 B111c2.
[2] DATA STRUCTURES AND ALGORITHMS, Autor: Aho, Hopcroft, Ullman, ISBN: 0-201-00023-7, Ubicación en biblioteca: 519.683.2 A286.
[3] CONCRETE MATHEMATICS, Autor: Graham, Ronald L., Knuth, Donald E. , Patashnik, Oren, ISBN: 0-201-55802-5, Ubicación en biblioteca: 511511.333 G741c2.
[4] THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS, Autor: Aho, Hopcroft, Ullman, ISBN: 0-201-00029-6, Ubicación en biblioteca: 519.683.2 A286.
[5] DATA STRUCTURES & PROGRAM DESIGN, Autor: Kruse, Robert, ISBN: 0-132-08182-2, Ubicación en biblioteca: 681.3.06 K94D2.
[6] DATA STRUCTURES TECHNIQUES, Autor: Standish, T., ISBN: 0-201-07256-4, Ubicación en biblioteca: 681.3.06 51 S785.
[7] COMPUTER ALGORITHMS: KEY SEARCH STRATEGIES, IEEE Computer Society Technology Series, ISBN: 0-818-69123-9, Ubicación en biblioteca: 519.681.5519.878681.3.06 A638.
[8] MATHEMATICS FOR THE ANALYSIS OF ALGORITHMS, Autor: Greene, Daniel , Knuth, Donald, ISBN: 0-8176-3515-7 (Birkhäuser), ISBN: 3-7643-3515-7 (Boston-Basel-Berlín),
[9] Publicaciones:
[10] PUGH, WILLIAM: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33, 1990, pág. 668-676.
[11] LEWIS, T y COOK, C: Hashing for Dynamic and Static Internal Tables. IEEE Comp. Oct.1988.
[12] LARSON, P: Dynamic Hash Tables. C. ACM, Vol 31 N0 4, Abril 1988.
[13] SLEATOR D. D. y TARJAN R. E.: Self-adjusting binary search trees Journal of ACM, ISSN 0004-5411, Vol 32, Nro. 3, pág. 652-686, Julio 1985.
XI - Resumen de Objetivos
Al finalizar el curso se pretende que el alumno sea capaz de:
- Manejar con idoneidad los conceptos que involucran el diseño de estructuras de datos.
- Conocer algunos de los principales algoritmos y estructuras de datos, incluyendo el análisis de su desempeño.
- Analizar y diseñar algoritmos.
- Desarrollar una actitud crítica frente al uso de las estructuras de datos y algoritmos con los que se pueda enfrentar.
- Frente a una aplicación o problema particular, poder brindar una solución eficiente utilizando los conceptos vistos sobre diseño de estructuras de datos y algoritmos, y además utilizar el análisis de los algoritmos para evaluar y justificar la eficiencia de la solución elegida.

XII - Resumen del Programa
1. Repaso de temas y homogenización de terminología:
Conjuntos. Relaciones Binarias. Restricciones. Casos particulares.Propiedades que caracterizan casos particulares de relación. Tipos de relaciones. Operaciones con relaciones.

2. Explicitación del objetivo de la materia.
Las estructuras. Dato e información. Doble acepción de estructuras de datos. Visión relacional. Algoritmos: análisis y diseño.

3. Terminología de teoría de grafos
Grafos, digrafos. Incidencia y adyacencia. Grado. Sub(di)grafo, (di)grafo parcial. (di)Grafos bipartitos. Cadena, camino, ciclo, cociclo, circuito, cocircuito. Conectividad. Conectividad fuerte. Conectividad cuasi-fuerte. Árboles. Arborescencias.

4. Propiedades, demostraciones y representación de grafos.
Número ciclomático y cociclomático. Representación de grafos.

5.Evaluación de algoritmos.
Planteo. Problema. Función de costo. Función de evaluación. Propiedades. Medidas en tiempo y espacio. Familias de problemas. Solución parametrizada. Notaciones Asintóticas. Complejidad. Técnicas para plantear y resolver ecuaciones de recurrencias.

6. Listas, Pilas y Colas.
Listas vinculadas y secuenciales. Búsqueda binaria. Lista Invertida. Operaciones. Pilas y colas.

7. Lista de 2 niveles.
Representación computacional. Optimización de parámetros.

8. Direccionamiento Directo.
Condiciones para aplicacrlo. Funciones de enumeración.

9. Árboles computacionales.
Definición. Representación computacional. Árboles Binarios de Búsqueda. Árboles AVL. Árboles auto-ajustables.

10. Parva.
Definición. Operaciones. Aplicaciones.

11. Distribución pseudo-aleatoria de datos.
Funciones de pseudo-aleatorización. Manejo de Rebalses.

12. Skip Lists.
Definición. Ventajas y desventajas.

13. Técnicas de diseño de algoritmos.
Técnicas ávidas, programación dinámica, dividir para vencer. Ejemplos de aplicación

14. Búsqueda en Texto.
Representación de textos. Trie. Árboles Patricia.

XIII - Imprevistos
No los sé en este momento.