Ministerio de Educación, Ciencia y Tecnología
Universidad Nacional de San Luis
FACULTAD DE CS. FISICO MAT. Y NAT.

ANEXO II

PROGRAMA DEL CURSO: ESTRUCTURA DE DATOS Y ALGORITMOS

DEPARTAMENTO DE:   INFORMATICA
AREA: DatosAÑO: 2002 (Id: 1618)
Estado: En tramite de Aprobación

 

I - OFERTA ACADÉMICA

CARRERAS PARA LAS QUE SE OFRECE EL MISMO CURSO

PLAN DE ESTUDIOS
ORD. Nº

CRÉDITO HORARIO

   

SEM.

TOTAL

LIC. EN CIENCIAS DE LA COMPUTACION11/98
LIC. EN CIENCIAS DE LA COMPUTACION3/00

II - EQUIPO DOCENTE

Funciones

Apellido y Nombre

Total hs en
este curso

Cargo y Dedic.

Carácter

Responsable

REYES, NORA SUSANA20  hs.PROFESOR ADJUNTO EXC.Interino
Co-ResponsableDNL  hs.CONTRATOSContratado
ColaboradorHERRERA, NORMA EDITH20  hs.PROFESOR ADJUNTO EXC.Interino
Auxiliar de 1ºLUDUE#A, VERONICA DEL ROSARIO 20  hs.AYUDANTE DE 1RA. EXC. Efectivo
Auxiliar de 1ºTARANILLA, MARIA TERESA 20  hs.AYUDANTE DE 1RA. EXC. Temporal
Auxiliar de 2ºARROYUELO, DIEGO GASTON 5  hs.AYUDANTE DE 2DA. SIMP.Temporal
Auxiliar de 2ºARROYUELO, DIEGO GASTON 5  hs.AYUDANTE DE 2DA. SIMP.Temporal
Auxiliar de 2ºRUANO, CARINA MABEL 5  hs.AYUDANTE DE 2DA. SIMP.Temporal
Auxiliar de 2ºRUANO, CARINA MABEL 5  hs.AYUDANTE DE 2DA. SIMP.Temporal
Auxiliar de 2ºVILLEGAS, ANA VALERIA 5  hs.AYUDANTE DE 2DA. SIMP.Temporal
Auxiliar de 2ºVILLEGAS, ANA VALERIA 5  hs.AYUDANTE DE 2DA. SIMP.Temporal

DNL: Docente no listado

III - CARACTERÍSTICAS DEL CURSO

CREDITO HORARIO SEMANAL
MODALIDAD
REGIMEN

Teórico/

Práctico

Teóricas

Prácticas de

Aula

Práct. de lab/ camp/

Resid/ PIP, etc.

2c
 Hs.
4 Hs.
3 Hs.
2 Hs.
Asignatura
Otro: 
Duración: 14 semanas
Período del 12/08/01 al 15/11/01

IV.- FUNDAMENTACION

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


VII. - PLAN DE TRABAJOS PRÁCTICOS

Prácticos de aula:
1. Repaso de relaciones. Propiedades. Operaciones. Relaciones definidas sobre un conjunto. Clasificación de relaciones. Repaso de funciones.
2. Desarrollo de algoritmos para realizar búsqueda de elementos en las distintas representaciones computacionales posibles para un conjunto: listas, árboles, distintos tipos de manejos de rebalse. Implantación de las distintas variantes de búsqueda binaria.
3. Funciones de evaluación: análisis de distintos ejemplos; selección de funciones de evaluación de acuerdo al problema planteado. Análisis de ejemplos de problemas en los que puede aplicarse una función determinada. Notación O: análisis detallado de su utilización para expresar tiempos de ejecución de un trozo de programa, incluyendo el como se obtiene en caso de tener recursividad. Notaciones  y .
4. Teoría de Grafos: representación de grafos, aplicación de los distintos conceptos teóricos a ejemplos.
5. Teoría de Grafos: determinación de bases de ciclos y cociclos. Árboles y arborescencias. Árboles cubrientes
6. Análisis de distintas implantaciones de listas: diseño de los algoritmos necesarios en cada caso y cálculos de esfuerzos. Implementación de las distintas variantes de búsqueda por bisección y su cálculo de esfuerzo.
7. Implantación de pilas y colas. Mejoras a listas vinculadas y secuenciales: implantación. Cálculos de esfuerzo para las distintas estructuras.
8. Implantación de lista de 2 niveles. Optimización de parámetros para distintos casos. Cálculos de esfuerzo para distintos tipos de estructuras. Direccionamiento directo. Distribución pseudo-aleatoria de datos: implantación de los distintos algoritmos para cada una de las estrategias de manejo de rebalse. Análisis de distintas optimizaciones.
9. Arbol Binario ordenado: construcción de ejemplos e implantación de algoritmos. Análisis de la probabilidad de cada árbol posible de acuerdo a la secuencia de entrada. Balanceo sin utilizar técnicas de AVL. Arbol binario balanceado: construcción de ejemplos, implantación de algoritmos. Skip List: construcción de ejemplos e implantación de algoritmos.
10. Utilización de árboles como estructuras de información: Arboles de expresión, obtención de las distintas notaciones mediante la utilización de barridos; evaluación de expresiones representadas de esta forma.
11. Grafos: algoritmos para obtener la base de ciclos y cociclos y componentes fuertemente conectadas, utilizando un algoritmo primero en profundidad. Ejercicios adicionales de complemento.
Prácticos de máquina:
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.


VIII - RÉGIMEN DE APROBACIÓN

Condiciones de regularización:
 Aprobar los dos parciales o sus recuperaciones.
 Aprobar los trabajos en máquina que se realicen.
 70 % de asistencia a clases teóricas.
 70 % de asistencia a clases prácticas.

Se toman dos parciales, cada uno tiene una recuperación y hay una única recuperación por trabajo que se puede utilizar sólo para recuperar uno de los parciales.


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 todo este proceso.



IX.a - BIBLIOGRAFÍA BÁSICA

INTRODUCTION TO ALGORITHMS
Autor: Cormen, Leiserson and Rivest.
ISBN: 0262031418 -MIT-
Ubicación en biblioteca: 519.254 C811

THE ART OF COMPUTER PROGRAMMING (VOL I Y III)
Autor: Knuth, Donald E.
Ubicación en biblioteca: 681.3.06 K74

FUNDAMENTOS DE ALGORITMIA
Autor: : Brassard, Gilles y Bratley, Paul
ISBN: 84-89660-00-X

GRAPHES ET HYPERGRAPHES.
Autor: Berge, C.
Ubicación en biblioteca: 519.28 B495

AN INTRODUCTION TO THE ANALYSIS OF ALGORITHMS
Autor: Sedgewick, Robert and Flajolet, Philippe
ISBN: 020140009X
Ubicación en biblioteca: 004.021 S448

ALGORITHMIC: THEORY AND PRACTICE
Autor: Brassard, Gilles and Bratley, Paul
Ubicación en biblioteca: : 519.681 B823

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

DATA STRUCTURES AND THEIR ALGORITHMS
Autor: Lewis, Harry R. , Denenberg, Larry
ISBN: 0-673-39736-X
Ubicación en biblioteca: 519.683.2 L674

ESTRUCTURA DE DATOS y ALGORITMOS
Autor: Mark Weiss
ISBN: 0-201-62571-7

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.
 Evaluación de Algoritmos.
 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.
 Estructuras de Datos Aleatorias: Skip Lists.
 Ejemplo de resolución de recurrencia utilizando Funciones Generatrices.
 Deducción del esfuerzo medio de evocación exitosa en árboles binarios de búsqueda.



IX b - BIBLIOGRAFÍA COMPLEMENTARIA

COMPUTER ALGORITHMS: INTRODUCTION TO DESIGN AND ANALYSIS
Autor: Baase, Sara
ISBN: 0-201-06035-3
Ubicación en biblioteca: 519.682.4 B111c2

DATA STRUCTURES AND ALGORITHMS
Autor: Aho, Hopcroft, Ullman
ISBN: 0-201-00023-7
Ubicación en biblioteca: 519.683.2 A286

THE DESIGN AND ANALYSIS OF COMPUTER ALGORITHMS
Autor: Aho, Hopcroft, Ullman
ISBN: 0-201-00029-6
Ubicación en biblioteca: 519.683.2 A286

DATA STRUCTURES & PROGRAM DESIGN
Autor: Kruse, Robert
ISBN: 0-132-08182-2
Ubicación en biblioteca: 681.3.06 K94D2

DATA STRUCTURES TECHNIQUES.
Autor: Standish, T.
ISBN: 0-201-07256-4
Ubicación en biblioteca: 681.3.06 51 S785

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

CONCRETE MATHEMATICS.
Autor: Graham, Ronald L., Knuth, Donald E. , Patashnik, Oren
ISBN: 0-201-55802-5
Ubicación en biblioteca: 511511.333 G741c2

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)


Publicaciones:
 PUGH, WILLIAM: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33, 1990, pág. 668-676.
 LEWIS, T y COOK, C: Hashing for Dynamic and Static Internal Tables. IEEE Comp. Oct.1988
 LARSON, P: Dynamic Hash Tables. C. ACM, Vol 31 N0 4, Abril 1988.



COMPLEMENTO DE DIVULGACION


OBJETIVOS DEL CURSO


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.




 

 

PROGRAMA SINTETICO


1. Repaso de temas y homogenización de terminología:
Conjuntos. Relaciones Binarias. Restricciones. Casos particulares.Relaciones con dominio y rango coincidentes. Propiedades que caracterizan casos particulares de relación. Tipos de relaciones. Operaciones con relaciones.
Clausuras y generadores.
2. Explicitación del objetivo de la materia.
Las estructuras. Dato e información. Doble acepción de estructuras de datos. Algoritmos: análisis y diseño.
3. Terminología de teoría de grafos
Grafos, digrafos. Funciones de 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 y demostraciones de grafos.
Número ciclomático y número cociclomático. Caracterizaciones equivalentes de árbol y arborescencia. Distancias en grafos.
5. Evaluación de algoritmos.
Problema. Función de costo. Función de evaluación. Propiedades. Medidas en tiempo y espacio. Elección de la función de evaluación. Familias de problemas. Solución parametrizada. Función O,  y . 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. Operaciones. Análisis de esfuerzos. Búsqueda binaria.
Lista Invertida. Operaciones. Análisis de esfuerzos.
Pilas y colas. Operaciones. Su implantación secuencial y vinculada.
8. Lista de 2 niveles.
Listas de descriptores. Optimización de parámetros.
9. Direccionamiento Directo.
Condiciones para aplicarlo. Funciones de enumeración.
10. Arboles computacionales.
Definición. Representación computacional. Árbol completo, lleno y balanceado. Operaciones. Determinación de esfuerzos medio y máximo. Magnitudes, relaciones entre ellas. Contar árboles.
11. Parva.
Definición. Operaciones. Aplicaciones.
12. Distribución pseudo-aleatoria de datos.
Motivación. Funciones de pseudo-aleatorización. El problema del rebalse: formas de manejarlo. Deducción de esfuerzos para rebalse separado y para realeatorizado total.
13. Skip Lists.
Definición. Operaciones. Análisis de costos. 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: algoritmos sobre grafos, ordenamientos, búsquedas, codificación de Huffmann, etc...




 


IMPREVISTOS