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

Imprimir

Versión PDF

(Programa del año 2022)

I - Oferta Académica

Materia	Carrera	Plan	Año	Periodo
ESTRUCTURA DE DATOS Y ALGORITMOS	LIC.CS.COMP.	18/11	2022	1° cuatrimestre
ESTRUCTURA DE DATOS Y ALGORITMOS	LIC.CS.COMP.	32/12	2022	1° cuatrimestre

II - Equipo Docente

Docente	Función	Cargo	Dedicación
REYES, NORA SUSANA	Prof. Responsable	SEC U EX	5 Hs
KASIAN, FERNANDO ANDRES	Responsable de Práctico	JTP 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
Teórico/Práctico	Teóricas	Prácticas de Aula	Práct. de lab/ camp/ Resid/ PIP, etc.	Total	Periodo	Desde	Hasta	Cantidad de Semanas	Cantidad en Horas
Hs.	3 Hs.	3 Hs.	4 Hs.	10 Hs.	1º Cuatrimestre	21/03/2022	24/06/2022	14	135

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.

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 / Resultados de Aprendizaje
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.

V - Objetivos / Resultados de Aprendizaje

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. Explicitación del objetivo de la materia: Repaso de temas y homogeneización de terminología. Las estructuras. Dato e información. Doble acepción de estructuras de datos. Visión relacional. Fundamento de la evocación asociativa. Concepto de Servicio en una estructura de datos. Operaciones. Datos de un problema de estructuras de datos. Algoritmos. Representación de datos en memoria. 2. Terminología de teoría de grafos: Grafos y dígrafos. Orden. Funciones de incidencia y adyacencia. Grado. Vértices aislados. Clasificación de Grafos. Clasificación de secuencias y conjuntos de arcos. Clasificación de vértices. Conectividad. 3. Propiedades, demostraciones y representación de grafos: Número ciclomático y número cociclomático. Caracterizaciones equivalentes de árbol y arborescencia. Base de ciclos y cociclos. Construcción sistemática de árboles subtensos. Distancias en grafos. Representaciones básicas de grafos. 4. Análisis o Evaluación de algoritmos: Planteo. Problema. Función de costo. Necesidad de una función de evaluación. Propiedades. Medidas en tiempo y espacio. Balance entre tiempo y espacio en los algoritmos. Elección de la función de evaluación. Familias de problemas. Solución parametrizada. Notaciones asintóticas. Propiedades. Análisis asintótico. Complejidad. Clases de Complejidad. Análisis de comportamiento en el mejor caso, caso promedio y peor caso. Técnicas para plantear y resolver ecuaciones de recurrencias. 5. Listas, Pilas y Colas: Listas vinculadas y secuenciales. Incidencia del orden, Incidencia del tipo de recurrencia que la define. Búsqueda binaria. Lista Invertida. Lista de 2 niveles: descriptores de listas, representación computacional, optimización de parámetros. Pilas y colas. Skip Lists. Operaciones o algoritmos fundamentales sobre cada tipo de estructura. Análisis de Costos. Aplicaciones. 6. Direccionamiento Directo: Condiciones para su aplicación. Relajación de la exigencia de totalidad. Funciones de enumeración. Aplicaciones. 7. Árboles computacionales: Definición. Representación computacional. Árbol completo, lleno y balanceado. Almacenamiento por extensión y por comprensión. Árboles Binarios de Búsqueda. Árboles Balanceados en altura. Árboles de búsqueda auto-ajustables. Parva. Trie. Árboles Patricia. Operaciones básicas sobre cada tipo de árbol. Análisis de costos. Magnitudes. Aplicaciones. 8. Distribución pseudo-aleatoria de datos: Motivación. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Operaciones básicas. Análisis de costos. Aplicaciones. 9. 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. Problemas de caminos en digrafos: Dijkstra y Floyd. Conectividad en grafos: Warshall. Árbol subtenso: Kruskal y Prim. Aplicaciones. Otros ejemplos de aplicación de las distintas técnicas: ordenamientos, búsquedas, codificación de Huffmann, etc.

VI - Contenidos

1. Explicitación del objetivo de la materia:
Repaso de temas y homogeneización de terminología. Las estructuras. Dato e información. Doble acepción de estructuras de datos. Visión relacional. Fundamento de la evocación asociativa. Concepto de Servicio en una estructura de datos. Operaciones. Datos de un problema de estructuras de datos. Algoritmos. Representación de datos en memoria.

2. Terminología de teoría de grafos:
Grafos y dígrafos. Orden. Funciones de incidencia y adyacencia. Grado. Vértices aislados. Clasificación de Grafos. Clasificación de secuencias y conjuntos de arcos. Clasificación de vértices. Conectividad.

3. Propiedades, demostraciones y representación de grafos:
Número ciclomático y número cociclomático. Caracterizaciones equivalentes de árbol y arborescencia. Base de ciclos y cociclos. Construcción sistemática de árboles subtensos. Distancias en grafos. Representaciones básicas de grafos.

4. Análisis o Evaluación de algoritmos:
Planteo. Problema. Función de costo. Necesidad de una función de evaluación. Propiedades. Medidas en tiempo y espacio. Balance entre tiempo y espacio en los algoritmos. Elección de la función de evaluación. Familias de problemas. Solución parametrizada. Notaciones asintóticas. Propiedades. Análisis asintótico. Complejidad. Clases de Complejidad. Análisis de comportamiento en el mejor caso, caso promedio y peor caso. Técnicas para plantear y resolver ecuaciones de recurrencias.

5. Listas, Pilas y Colas:
Listas vinculadas y secuenciales. Incidencia del orden, Incidencia del tipo de recurrencia que la define. Búsqueda binaria. Lista Invertida. Lista de 2 niveles: descriptores de listas, representación computacional, optimización de parámetros. Pilas y colas. Skip Lists. Operaciones o algoritmos fundamentales sobre cada tipo de estructura. Análisis de Costos. Aplicaciones.

6. Direccionamiento Directo:
Condiciones para su aplicación. Relajación de la exigencia de totalidad. Funciones de enumeración. Aplicaciones.

7. Árboles computacionales:
Definición. Representación computacional. Árbol completo, lleno y balanceado. Almacenamiento por extensión y por comprensión. Árboles Binarios de Búsqueda. Árboles Balanceados en altura. Árboles de búsqueda auto-ajustables. Parva. Trie. Árboles Patricia. Operaciones básicas sobre cada tipo de árbol. Análisis de costos. Magnitudes. Aplicaciones.

8. Distribución pseudo-aleatoria de datos:
Motivación. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Operaciones básicas. Análisis de costos. Aplicaciones.

9. 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. Problemas de caminos en digrafos: Dijkstra y Floyd. Conectividad en grafos: Warshall. Árbol subtenso: Kruskal y Prim. Aplicaciones. Otros ejemplos de aplicación de las distintas técnicas: ordenamientos, búsquedas, codificación de Huffmann, etc.

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. Notaciones asintóticas. Utilización para expresar tiempos de ejecución de programas. 4. Diseño de los algoritmos necesarios para cada una de las distintas implementaciones de listas y cálculos de esfuerzos. Pilas y Colas. 5. Teoría de grafos. Representación. Aplicación de los distintos conceptos teóricos a ejemplos. Algoritmos sobre grafos. 6. Árboles como estructuras de información. Barridos. Árbol binario de búsqueda. Árbol binario balanceado en altura. 7. Colas de prioridad. Implantación y algoritmos necesarios para su manejo. Aplicaciones. Algoritmos golosos. Análisis de los algoritmos analizados para cada técnica de diseño. Diseño de algoritmos usando las técnicas estudiadas. 8. Lista de 2 niveles. Optimización de parámetros para distintos casos. Direccionamiento directo. Skip list. Distribución pseudo-aleatoria de datos. 9. Otros tipos de Árboles de búsqueda. Trie y Árboles Patricia. Árboles de búsqueda auto-ajustables. Prácticos de máquina: -------------------------------- Se desarrollarán prácticos que consistan en el estudio de una situación real a informatizar. Se implementarán distintas estructuras de almacenamiento, junto con los operadores necesarios para su administración, para soportar la realidad planteada; teniendo en cuenta las estructuras que gradualmente se vayan incorporando en las teorías. Además se deberán calcular los distintos costos (a posteriori) sobre dichas estructuras analizando y comparando los mismos entre sí. Serán tres prácticos. El primero de ellos tratará sobre la implementación de listas básicas y sus operaciones. En los dos restantes: - Se implementarán dos o tres estructuras en cada uno, con todas las operaciones necesarias para resolver el problema real al que se aplica. - Se calcularán los costos de las estructuras implementadas, debiendo redactarse además un informe en el cual se muestren y comparen los costos obtenidos. Cada práctico contará con una instancia de recuperación. * Podrá agregarse un práctico adicional o un complemento a los prácticos anteriores, para aquellos alumnos que necesiten hacer uso de una recuperación no prevista para los prácticos de máquina, en el cual se incorporará algún tema no contemplado en los demás prácticos de máquina.

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. Notaciones asintóticas. Utilización para expresar tiempos de ejecución de programas.

4. Diseño de los algoritmos necesarios para cada una de las distintas implementaciones de listas y cálculos de esfuerzos. Pilas y Colas.

5. Teoría de grafos. Representación. Aplicación de los distintos conceptos teóricos a ejemplos. Algoritmos sobre grafos.

6. Árboles como estructuras de información. Barridos. Árbol binario de búsqueda. Árbol binario balanceado en altura.

7. Colas de prioridad. Implantación y algoritmos necesarios para su manejo. Aplicaciones. Algoritmos golosos. Análisis de los algoritmos analizados para cada técnica de diseño. Diseño de algoritmos usando las técnicas estudiadas.

8. Lista de 2 niveles. Optimización de parámetros para distintos casos. Direccionamiento directo. Skip list. Distribución pseudo-aleatoria de datos.

9. Otros tipos de Árboles de búsqueda. Trie y Árboles Patricia. Árboles de búsqueda auto-ajustables.

Prácticos de máquina:
--------------------------------
Se desarrollarán prácticos que consistan en el estudio de una situación real a informatizar. Se implementarán distintas estructuras de almacenamiento, junto con los operadores necesarios para su administración, para soportar la realidad planteada; teniendo en cuenta las estructuras que gradualmente se vayan incorporando en las teorías. Además se deberán calcular los distintos costos (a posteriori) sobre dichas estructuras analizando y comparando los mismos entre sí.

Serán tres prácticos. El primero de ellos tratará sobre la implementación de listas básicas y sus operaciones. En los dos restantes:
- Se implementarán dos o tres estructuras en cada uno, con todas las operaciones necesarias para resolver el problema real al que se aplica.
- Se calcularán los costos de las estructuras implementadas, debiendo redactarse además un informe en el cual se muestren y comparen los costos obtenidos.

Cada práctico contará con una instancia de recuperación.

* Podrá agregarse un práctico adicional o un complemento a los prácticos anteriores, para aquellos alumnos que necesiten hacer uso de una recuperación no prevista para los prácticos de máquina, en el cual se incorporará algún tema no contemplado en los demás prácticos de máquina.

VIII - Regimen de Aprobación
Las condiciones de regularización son: - 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 la evaluación final, o sus recuperaciones, con el 70%. Se tomará una evaluación, la cual tendrá dos posibles instancias de recuperación. - 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.

VIII - Regimen de Aprobación

Las condiciones de regularización son:
- 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 la evaluación final, o sus recuperaciones, con el 70%. Se tomará una evaluación, la cual tendrá dos posibles instancias de recuperación.

- 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-, The MIT Press, 3a edición, 2003, Ubicación en biblioteca: 519.254 C811 [2] FUNDAMENTOS DE ALGORITMIA, Autor: : Brassard, Gilles y Bratley, Paul, ISBN: 84-89660-00-X, Prentice Hall, 1a. edición, 2000, Ubicación en Biblioteca: 004.021.B823f [3] COMPARED TO WHAT? : AN INTRODUCTION TO THE ANAYLSIS OF ALGORITHMS, Autor: Rawlins, Gregory, ISBN: 071678243X, W. H. Freeman, 1991. [4] THE ART OF COMPUTER PROGRAMMING (VOL 1 Y 3), Autor: Knuth, Donald E., ISBN-10: 0201896834 y 0201896850, ISBN-13: 978-0201896831 y 978-0201896855, Addison-Wesley Professional, VOL 1: 3a edición, 1997, VOL [5] 3: 2a edición, 1998, Ubicación en biblioteca:681.3.06 K74 [6] ALGORITHMS IN C (PARTS 1-4), Autor: Sedgewick, Robert. 3a. Ed. ISBN 0-201-31452-5, Addison-Wesley Professional, 3a edición 1997, Ubicación en Biblioteca: 004.422.63 S448a3 I [7] GRAPHES ET HYPERGRAPHES, Autor: Berge, C., ISBN-10: 0444876030, ISBN-13: 978-0444876034, North Holland, [8] 1989, Ubicación en biblioteca: 519.28 B495 [9] AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS, Autor: Sedgewick, Robert and Flajolet, Philippe.ISBN: 020140009X, Addison-Wesley Professional, 1995, Ubicación en biblioteca: 004.021 S448 [10] ALGORITHMIC: THEORY AND PRACTICE, Autor: Brassard, Gilles and Bratley, Paul, Ubicación en biblioteca:519.681 B823. [11] DATA STRUCTURES AND PROGRAM DESIGN IN C, Autores: Kruse, Robert L.; Leung, Bruce P.; Tondo, Clovis L.,ISBN: 0-13-725649-3, Prentice Hall, 2a edición, 1996, Ubicación en biblioteca: 519.682.2681.3.06 K94. [12] DATA STRUCTURES AND THEIR ALGORITHMS, Autor: Lewis, Harry R.,Denenberg, Larry, ISBN: 0-673-39736-X, Addison Wesley, 1991, Ubicación en biblioteca: 519.683.2 L674. [13] ESTRUCTURA DE DATOS y ALGORITMOS, Autor: Mark Weiss, ISBN: 0-201-62571-7, Addison Wesley Longman, 2000. [14] 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. Introducción a las Estructuras de Datos.Descripción Informática de Conjuntos. Pertenencia en Conjuntos Computacionales. Operaciones en Conjuntos Computacionales. Evaluación de Algoritmos. Teoría de Grafos (Parte I). Teoría de Grafos (Parte II). Arboles Binarios Ordenados. Costos de Búsqueda en Árboles Binarios de Búsqueda. * Árboles de Expresión.Lista de 2 Niveles. Distribución Pseudo-aleatoria de Datos. Diseño de Funciones de Enumeración. Deducción de algunos esfuerzos para distribución pseudo- aleatoria de datos. Diseño de Funciones de pseudo-azar. Estructuras de Datos Aleatorias: Skip Lists. *Árboles Digitales: Trie y Patricia.

IX - Bibliografía Básica

[1] INTRODUCTION TO ALGORITHMS, Autor: Cormen, Leiserson and Rivest, ISBN: 0262031418 -MIT-, The MIT Press, 3a edición, 2003, Ubicación en biblioteca: 519.254 C811
[2] FUNDAMENTOS DE ALGORITMIA, Autor: : Brassard, Gilles y Bratley, Paul, ISBN: 84-89660-00-X, Prentice Hall, 1a. edición, 2000, Ubicación en Biblioteca: 004.021.B823f
[3] COMPARED TO WHAT? : AN INTRODUCTION TO THE ANAYLSIS OF ALGORITHMS, Autor: Rawlins, Gregory, ISBN: 071678243X, W. H. Freeman, 1991.
[4] THE ART OF COMPUTER PROGRAMMING (VOL 1 Y 3), Autor: Knuth, Donald E., ISBN-10: 0201896834 y 0201896850, ISBN-13: 978-0201896831 y 978-0201896855, Addison-Wesley Professional, VOL 1: 3a edición, 1997, VOL
[5] 3: 2a edición, 1998, Ubicación en biblioteca:681.3.06 K74
[6] ALGORITHMS IN C (PARTS 1-4), Autor: Sedgewick, Robert. 3a. Ed. ISBN 0-201-31452-5, Addison-Wesley Professional, 3a edición 1997, Ubicación en Biblioteca: 004.422.63 S448a3 I
[7] GRAPHES ET HYPERGRAPHES, Autor: Berge, C., ISBN-10: 0444876030, ISBN-13: 978-0444876034, North Holland,
[8] 1989, Ubicación en biblioteca: 519.28 B495
[9] AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS, Autor: Sedgewick, Robert and Flajolet, Philippe.ISBN: 020140009X, Addison-Wesley Professional, 1995, Ubicación en biblioteca: 004.021 S448
[10] ALGORITHMIC: THEORY AND PRACTICE, Autor: Brassard, Gilles and Bratley, Paul, Ubicación en biblioteca:519.681 B823.
[11] DATA STRUCTURES AND PROGRAM DESIGN IN C, Autores: Kruse, Robert L.; Leung, Bruce P.; Tondo, Clovis L.,ISBN: 0-13-725649-3, Prentice Hall, 2a edición, 1996, Ubicación en biblioteca: 519.682.2681.3.06 K94.
[12] DATA STRUCTURES AND THEIR ALGORITHMS, Autor: Lewis, Harry R.,Denenberg, Larry, ISBN: 0-673-39736-X, Addison Wesley, 1991, Ubicación en biblioteca: 519.683.2 L674.
[13] ESTRUCTURA DE DATOS y ALGORITMOS, Autor: Mark Weiss, ISBN: 0-201-62571-7, Addison Wesley Longman, 2000.
[14] 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. *Introducción a las Estructuras de Datos.*Descripción Informática de Conjuntos. *Pertenencia en Conjuntos Computacionales. *Operaciones en Conjuntos Computacionales. *Evaluación de Algoritmos. *Teoría de Grafos (Parte I). *Teoría de Grafos (Parte II). *Arboles Binarios Ordenados. *Costos de Búsqueda en Árboles Binarios de Búsqueda. * Árboles de Expresión.*Lista de 2 Niveles. *Distribución Pseudo-aleatoria de Datos. *Diseño de Funciones de Enumeración. *Deducción de algunos esfuerzos para distribución pseudo- aleatoria de datos. *Diseño de Funciones de pseudo-azar. *Estructuras de Datos Aleatorias: Skip Lists. *Árboles Digitales: Trie y Patricia.

X - Bibliografia Complementaria
[1] COMPUTER ALGORITHMS: INTRODUCTION TO DESIGN AND ANALYSIS, Autor: Baase, Sara, ISBN: 0-201-06035-3, Addison Wesley, 3a edición, 1999, Ubicación en biblioteca: 519.682.4 B111c2 [2] DATA STRUCTURES AND ALGORITHMS, Autor: Aho, Hopcroft, Ullman, ISBN: 0-201-00023-7, Addison Wesley, 1983, 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, Addison-Wesley Professional, 2 edición, 1994, Ubicación en biblioteca: 511.333 G741c2 [4] THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS, Autor: Aho, Hopcroft, Ullman, ISBN:0-201-00029-6, Addison-Wesley, 1974, Ubicación en biblioteca: 519.683.2 A286 [5] DATA STRUCTURES & PROGRAM DESIGN, Autor: Kruse, Robert, ISBN: 0-132-08182-2, Prentice-Hall, 2a edición, 1994, Ubicación en biblioteca: 681.3.06 K94D2 [6] DATA STRUCTURES TECHNIQUES, Autor: Standish, T., ISBN: 0-201-07256-4, Addison-Wesley, 1980, Ubicación en biblioteca: 681.3.0651.S785 [7] COMPUTER ALGORITHMS: KEY SEARCH STRATEGIES, IEEE Computer Society Technology Series, ISBN: 0-818-69123-9, IEEE Computer Society, 1990, 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), Birkhäuser Boston; 3a edición Rev., 2007. [9] PUGH, WILLIAM: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33, 1990,pág. 668-676. [10] LEWIS, T y COOK, C: Hashing for Dynamic and Static Internal Tables. IEEE Comp. Oct.1988. [11] LARSON, P: Dynamic Hash Tables. C. ACM, Vol 31 N0 4, Abril 1988. [12] 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.

X - Bibliografia Complementaria

[1] COMPUTER ALGORITHMS: INTRODUCTION TO DESIGN AND ANALYSIS, Autor: Baase, Sara, ISBN: 0-201-06035-3, Addison Wesley, 3a edición, 1999, Ubicación en biblioteca: 519.682.4 B111c2
[2] DATA STRUCTURES AND ALGORITHMS, Autor: Aho, Hopcroft, Ullman, ISBN: 0-201-00023-7, Addison Wesley, 1983, 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, Addison-Wesley Professional, 2 edición, 1994, Ubicación en biblioteca: 511.333 G741c2
[4] THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS, Autor: Aho, Hopcroft, Ullman, ISBN:0-201-00029-6, Addison-Wesley, 1974, Ubicación en biblioteca: 519.683.2 A286
[5] DATA STRUCTURES & PROGRAM DESIGN, Autor: Kruse, Robert, ISBN: 0-132-08182-2, Prentice-Hall, 2a edición, 1994, Ubicación en biblioteca: 681.3.06 K94D2
[6] DATA STRUCTURES TECHNIQUES, Autor: Standish, T., ISBN: 0-201-07256-4, Addison-Wesley, 1980, Ubicación en biblioteca: 681.3.0651.S785
[7] COMPUTER ALGORITHMS: KEY SEARCH STRATEGIES, IEEE Computer Society Technology Series, ISBN: 0-818-69123-9, IEEE Computer Society, 1990, 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), Birkhäuser Boston; 3a edición Rev., 2007.
[9] PUGH, WILLIAM: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33, 1990,pág. 668-676.
[10] LEWIS, T y COOK, C: Hashing for Dynamic and Static Internal Tables. IEEE Comp. Oct.1988.
[11] LARSON, P: Dynamic Hash Tables. C. ACM, Vol 31 N0 4, Abril 1988.
[12] 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 los conceptos que involucran el diseño de estructuras de datos. - Conocer los principales algoritmos y estructuras de datos y su análisis de su desempeño. - Analizar y diseñar algoritmos. - Frente a una aplicación o problema particular, poder brindar una solución eficiente utilizando los conceptos vistos.

XII - Resumen del Programa
1. Explicitación del objetivo de la materia: Homogeneización de terminología. Las estructuras. Dato e información. Doble acepción de estructuras de datos. Visión relacional. Algoritmos. Representación de datos en memoria. 2. Terminología de teoría de grafos: Definición. Orden. Incidencia y adyacencia. Grado. Vértices aislados. Clasificación. Clasificación de secuencias y conjuntos de arcos. Clasificación de vértices. Conectividad. 3. Propiedades, demostraciones y representación de grafos: Número ciclomático y número cociclomático. Construcción sistemática de árboles subtensos. Representaciones básicas de grafos. 4. 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. 5. Listas, Pilas y Colas: Listas vinculadas y secuenciales. Búsqueda binaria. Lista Invertida. Lista de 2 niveles. Pilas y colas. Skip Lists. Operaciones. Análisis de Costos. Aplicaciones. 6. Direccionamiento Directo: Condiciones para su aplicación. Funciones de enumeración. Aplicaciones. 7. Árboles computacionales: Definición. Representación computacional. Árboles Binarios de Búsqueda. Árboles Balanceados en altura. Árboles de búsqueda auto-ajustables. Parva. Trie. Árboles Patricia. Operaciones. Análisis de costos. Magnitudes. Aplicaciones. 8. Distribución pseudo-aleatoria de datos. Motivación. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Análisis de costos. Aplicaciones. 9. 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. Otros ejemplos de aplicación de las distintas técnicas.

XII - Resumen del Programa

1. Explicitación del objetivo de la materia:
Homogeneización de terminología. Las estructuras. Dato e información. Doble acepción de estructuras de datos. Visión relacional. Algoritmos. Representación de datos en memoria.

2. Terminología de teoría de grafos:
Definición. Orden. Incidencia y adyacencia. Grado. Vértices aislados. Clasificación. Clasificación de secuencias y conjuntos de arcos. Clasificación de vértices. Conectividad.

3. Propiedades, demostraciones y representación de grafos:
Número ciclomático y número cociclomático. Construcción sistemática de árboles subtensos. Representaciones básicas de grafos.

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

5. Listas, Pilas y Colas:
Listas vinculadas y secuenciales. Búsqueda binaria. Lista Invertida. Lista de 2 niveles. Pilas y colas. Skip Lists. Operaciones. Análisis de Costos. Aplicaciones.

6. Direccionamiento Directo:
Condiciones para su aplicación. Funciones de enumeración. Aplicaciones.

7. Árboles computacionales:
Definición. Representación computacional. Árboles Binarios de Búsqueda. Árboles Balanceados en altura. Árboles de búsqueda auto-ajustables. Parva. Trie. Árboles Patricia. Operaciones. Análisis de costos. Magnitudes. Aplicaciones.

8. Distribución pseudo-aleatoria de datos.
Motivación. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Análisis de costos. Aplicaciones.

9. 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. Otros ejemplos de aplicación de las distintas técnicas.

XIII - Imprevistos
Se dictarán como máximo 10 horas semanales hasta completar las 135 horas del CHT. Contacto con la cátedra: -Por mail: eda@unsl.edu.ar -Por formulario electrónico a través de la página web: http://dirinfo.unsl.edu.ar/eda/contacto.php -Personalmente: Segundo Bloque - box 7, box 24 - Primer piso.

XIV - Otros