Materia	Carrera	Plan	Año	Periodo
ESTRUCTURA DE DATOS Y ALGORITMOS I	LIC.CS.COMP.	RD-3-1/2023	2024	2° cuatrimestre

Docente	Función	Cargo	Dedicación
REYES, NORA SUSANA	Prof. Responsable	SEC U EX	5 Hs
KASIAN, FERNANDO ANDRES	Prof. Co-Responsable	P.Adj Exc	40 Hs
LUDUEÑA, VERONICA DEL ROSARIO	Prof. Co-Responsable	P.Asoc Exc	40 Hs
AZAR, ELIANA PAOLA	Responsable de Práctico	JTP Exc	40 Hs
SOSA TORANZO, CECILIA LORENA	Responsable de Práctico	JTP Exc	40 Hs
JOFRE, ANA MARIA	Auxiliar de Práctico	A.1ra Exc	40 Hs

En esta asignatura se brindan los fundamentos de distintas estructuras de datos y del análisis de eficiencia de los algoritmos.

Para ello, se aborda el diseño de estructuras de datos considerando principalmente las evocaciones asociativas con respuesta única y algunos tipos de evocaciones no asociativas, como las extremales y las secuenciales. Este proceso incluye el análisis de eficiencia de las estructuras presentadas.
Se estudian distintas técnicas de diseños de algoritmos, analizando algoritmos representativos de cada una. Además, se inicia al estudiante en el análisis de algoritmos, propiciando el aprendizaje de cómo comparar algoritmos y analizar su desempeño, dado que esto resulta fundamental al momento de diseñar buenas soluciones.
Se sientan las primeras bases que serán complementadas con las que se aporten en Estructuras de Datos y Algoritmos II y las utilizadas por la asignatura Base de Datos I para lograr una base consolidada en las disciplinas Estructuras de Datos y Bases de Datos. De esta manera, si el estudiante 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 estudiante le interese 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.

El presente curso tiene como objetivo principal que los estudiantes sean capaces de manejar con idoneidad los conceptos que involucran el diseño de diferentes estructuras de datos, al igual que algunos algoritmos representativos. Además, se espera que adquieran un conocimiento exhaustivo de las principales estructuras de datos y su desempeño, y que logren implementarlas de manera eficiente. También se pretende que los estudiantes alcancen la capacidad de analizar y diseñar diferentes algoritmos y de estudiar su desempeño.


Como objetivos generales se espera que los estudiantes sean capaces de:

• Identificar, formular y resolver problemas, para desarrollar su capacidad de análisis, síntesis, organización y planificación.
• Desarrollar la capacidad de aplicar la teoría a la práctica, generando nuevas ideas.
• Integrar de manera efectiva equipos de trabajo, para favorecer la comunicación, el reparto equilibrado de tareas, el clima interno y la cohesión.
• Desarrollar la capacidad de generar razonamiento crítico y aprendizaje autónomo.

En particular se procura que los estudiantes consigan:

• Manejar con idoneidad los conceptos que involucran el diseño de distintas estructuras de datos y de diferentes algoritmos.
• Diseñar y evaluar soluciones alternativas a un problema, además de aplicar, de forma adecuada, metodologías y buenas prácticas de diseño.
• Conocer las principales estructuras de datos, ser capaces de explicarlas, y de analizar, diseñar, comparar e implementar cada una de ellas.
• Conocer, explicar su funcionamiento, e implementar algunos de los principales algoritmos, incluyendo el análisis de su desempeño.
• Desarrollar una actitud crítica frente al uso de las estructuras de datos y algoritmos con los que se pueda enfrentar.
• Desarrollar una actitud inquisitiva en búsqueda de nuevas soluciones, y ser capaces de reconocer, modificar, innovar y aplicar los distintos tipos de algoritmos; generando,
además, la capacidad del aprendizaje autónomo.

Durante el dictado de la asignatura se abordan los siguientes ejes transversales::

• Identificación, formulación y resolución de problemas de informática.
• Concepción, diseño y desarrollo de proyectos de informática.
• Gestión, planificación, ejecución y control de proyectos de informática.
• Utilización de técnicas y herramientas de aplicación en la informática.
• Contribuir a la generación de desarrollos tecnológicos y/o innovaciones tecnológicas.
• Fundamentos para el desempeño en equipos de trabajo.
• Fundamentos para la comunicación efectiva
• Fundamentos para la acción ética y responsable.
• Fundamentos para evaluar y actuar en relación con el impacto social de su actividad en el contexto global y local.
• Fundamentos para el aprendizaje continuo.

Contenidos Mínimos según Plan de Estudios Vigente (OCD Nº 1/23)
Grafos. Representaciones y algoritmos. Evaluación de algoritmos. Representación de conjuntos dinámicos en memoria principal y sus operaciones. Evocaciones de respuesta única. Evocaciones extremales. Listas, pilas y colas. Direccionamiento directo. Árboles computacionales. Distribución pseudo-aleatoria de datos. Análisis de costos de las operaciones sobre las distintas estructuras de datos. Algoritmos fundamentales: Recorrido, búsqueda, ordenamiento, actualización. Estrategias de diseño de algoritmos.

Contenidos Detallados


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.

2. Evaluación de algoritmos:
Planteo. Problema. Función de costo. Necesidad de una 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. Notaciones asintóticas. Propiedades. Complejidad. Clases de Complejidad. Análisis de costos de las operaciones sobre las distintas estructuras de datos.

3. 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. Evocaciones extremales. Pilas y colas. Skip Lists. Algoritmos fundamentales: Recorrido, búsqueda, ordenamiento, actualización, sobre cada tipo de estructura. Aplicaciones.

4. Propiedades, demostraciones y representación de grafos:
Definiciones. Propiedades. Representaciones básicas de grafos. Algoritmos sobre grafos

5. Árboles computacionales:
Definición. Representación computacional. Árbol completo, lleno y balanceado. Árboles Binarios de Búsqueda. Árboles Balanceados en altura. Evocaciones extremales. Parva. Operaciones básicas sobre cada tipo de árbol. Algoritmos fundamentales sobre cada tipo de árbol. Aplicaciones. Otros tipos de Árboles de búsqueda. Trie y Árboles Patricia. Árboles de búsqueda auto-ajustables.

6. Distribución pseudo-aleatoria de datos:
Motivación. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Direccionamiento Directo, condiciones para su aplicación, relajación de la exigencia de totalidad. Algoritmos fundamentales: Recorrido, búsqueda, ordenamiento, actualización, sobre cada estructura. Aplicaciones.

7. Técnicas de diseño de algoritmos:
Técnicas ávidas, programación dinámica, dividir para vencer. Ejemplos de aplicación sobre métodos de Ordenamiento. Ejemplos de aplicación en algoritmos sobre Grafos. Otros ejemplos de aplicación de las distintas técnicas.

Mediante la realización de práctica, tanto en papel como sobre la computadora, se promueve la integración de conceptos teóricos, su afianzamiento y su aplicación en la resolución de diferentes problemas planteados.

Se proponen diferentes situaciones de la vida real, que permiten al estudiante identificar problemas y abordar su posible solución, aplicando tanto técnicas presentadas en teoría, como mediante su ingenio e investigación. Los planteos presentados, por medio de los prácticos, incrementan gradualmente su complejidad, de manera que el estudiante afiance conceptos más simples, antes de abordar situaciones más complejas.

Este proceso se evalúa de manera formativa, mediante la entrega de ejercicios representativos e integradores que son corregidos y comentados posteriormente en clase, permitiendo una devolución general y otra personal a los estudiantes.

Las prácticas de laboratorio, además de presentar la posibilidad de diseñar y desarrollar un proyecto informático, contribuye a que los estudiantes planifiquen las diferentes etapas del mismo; trabajen de manera colaborativa a través de la formación de grupos de trabajo; debatan y analicen diferentes soluciones a los problemas planteados, para seleccionar la más eficiente y efectiva; utilicen herramientas adecuadas (por ej. un lenguaje de programación imperativo, un entorno de desarrollo, etc.); mejoren su comunicación a través de la presentación de informes, orales y/o escritos, sobre lo desarrollado en cada proyecto; y demuestren su ética, responsabilidad profesional al cumplir con los plazos establecidos al principio del curso.

Este proceso se evalúa de forma sumativa mediante la entrega y aprobación de los proyectos diseñados, presentando su código fuente, en las fechas predeterminadas en el cronograma de la asignatura, y realizando una descripción oral del mismo, en la que todos los integrantes del grupo de trabajo participen.

Además, se propone material extra disponible en la web sobre charlas y temas de interés para que los estudiantes investiguen sobre estructuras y/o algoritmos particularmente novedosos, impulsando su curiosidad, la posibilidad de indagar más allá de lo visto en clase y el aprendizaje autónomo.

Finalmente, lo trabajado durante el cuatrimestre es evaluado de manera sumativa por medio de un examen con sus respectivas recuperaciones. En cada instancia de evaluación, se realiza la devolución de los resultados mediante la corrección y debate sobre posibles soluciones a cada uno de los ejercicios planteados (corrección informada).

De esta manera se aporta a los ejes:
• Identificación, formulación y resolución de problemas de informática.
• Concepción, diseño y desarrollo de proyectos de informática.
• Gestión, planificación, ejecución y control de proyectos de informática.
• Utilización de técnicas y herramientas de aplicación en la informática.
• Contribuir a la generación de desarrollos tecnológicos y/o innovaciones tecnológicas.
• Fundamentos para el desempeño en equipos de trabajo.
• Fundamentos para la comunicación efectiva.
• Fundamentos para la acción ética y responsable.
• Fundamentos para el aprendizaje continuo.

Prácticos de aula:
Los mismos están orientados a afianzar los conceptos teóricos sobre las diferentes estructuras y algoritmos presentados en la asignatura y a estimular el planteo de soluciones ingeniosas a las diferentes problemáticas presentadas. Para un seguimiento formativo, se deberán presentar ejercicios representativos de cada práctico, lo que serán corregidos para una posterior devolución general y personal.

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 operar cada una de las distintas implementaciones de listas y cálculos de esfuerzos. Pilas y Colas.

5. Árboles como estructuras de información. Barridos. Árbol binario de búsqueda. Árbol binario balanceado en altura. Colas de prioridad. Implementación y algoritmos necesarios para su manejo. Aplicaciones.

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

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

8. Técnicas de diseño de algoritmos. Análisis de los algoritmos vistos para cada técnica de diseño. Diseño de algoritmos usando las técnicas estudiadas.

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ácticas 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í. Para la implementación de estos proyectos se deberán conformar grupos de trabajo y se trabajará con un lenguaje de programación, de los vistos en materias anteriores, que se considere apropiado a los fines de lo que se desea evaluar en la práctica. Para su aprobación se deberá presentar el código fuente de cada proyecto, teniendo en cuenta los dispositivos de evaluación provistos para los mismos. Además, los grupos realizarán una presentación oral detallando las decisiones de diseño tomadas, resultados obtenidos y especificaciones de implementación. Cada entrega posee su respectiva recuperación.

Serán prácticos en los que:
- Se implementarán estructuras con todas las operaciones necesarias para resolver el problema real indicado.
- Se calcularán los costos de las estructuras implementadas, debiendo entregarse además un informe en el cual se analicen y comparen los costos obtenidos.

Existe un práctico adicional, para aquellos alumnos que necesiten hacer uso de una recuperación no prevista para los prácticos de máquina, en el cual se implementará alguno de los algoritmos representativos de las técnicas de diseño vistas.

Régimen para estudiantes regulares:
Para regularizar la materia los estudiantes deberán cumplimentar los siguientes requerimientos:
* Asistencia: participar del 70% de las clases prácticas.
participar del 70% de las clases teóricas.
* Entregar los ejercicios requeridos de cada práctico de aula.
* Presentar en tiempo y forma los prácticos de laboratorio propuestos y aprobar el 100% de los mismos. Para ello se debe entregar el código fuente y un informe en el que se justifique la solución propuesta y se brinden detalles del trabajo realizado. Los códigos fuentes deben poder compilarse y resolver las situaciones planteadas. Cada práctico de laboratorio tendrá una posibilidad de recuperación para su aprobación.
* Aprobar la evaluación sumativa, o sus recuperaciones, con el 70%. Se tomará una evaluación, la cual tendrá dos posibles instancias de recuperación.

Aprobación de la asignatura:
* Regularizar la asignatura y aprobar el examen final.
* No es una materia promocional.

Modalidad de examen final:
Se evalúan los conceptos teóricos que fundamentan la práctica regularizada. Podrá ser oral y/o escrito y se rinde en turnos de exámenes establecidos en el Calendario Académico.

Examen libre:
No se admiten estudiantes libres dado que tanto los prácticos de aula como los de laboratorio se desarrollan de manera incremental desde comienzo de cuatrimestre, permitiendo una evaluación continua de los estudiantes, que no es posible evaluar correctamente en una instancia de examen.

[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 ANALYSIS 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.
[5] 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.
[6] GRAPHES ET HYPERGRAPHES, Autor: Berge, C., ISBN-10: 0444876030, ISBN-13: 978-0444876034, North Holland, 1989, Ubicación en biblioteca: 519.28 B495.
[7] 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.
[8] ALGORITHMIC: THEORY AND PRACTICE, Autor: Brassard, Gilles and Bratley, Paul, Ubicación en biblioteca:519.681 B823.
[9] 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.
[10] 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.
[11] ESTRUCTURA DE DATOS y ALGORITMOS, Autor: Mark Weiss, ISBN: 0-201-62571-7, Addison Wesley Longman, 2000.
[12] 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). * Árboles Binarios Ordenados. * Árboles de Expresión.* Lista de 2 Niveles. * Distribución Pseudo-aleatoria de Datos. * Diseño de Funciones de Enumeración. * Diseño de Funciones de pseudo-azar. * Estructuras de Datos Aleatorias: Skip Lists. * Árboles Digitales: Trie y Patricia. * Árboles Autoajustables -Splay Tree

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

Al finalizar el curso se pretende que el estudiante sea capaz de:
• Identificar, formular y resolver problemas, para desarrollar su capacidad de análisis, síntesis, organización y planificación.
• Desarrollar la capacidad de aplicar la teoría a la práctica, generando nuevas ideas.
• Integrar de manera efectiva equipos de trabajo, para favorecer la comunicación, el reparto equilibrado de tareas, el clima interno y la cohesión.
• Desarrollar la capacidad de generar razonamiento crítico y aprendizaje autónomo.

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. Datos de un problema de estructuras de datos. Algoritmos.

2. 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. Clases de Complejidad.

3. Listas, Pilas y Colas:
Listas vinculadas y secuenciales. Búsqueda binaria. Lista Invertida. Lista de 2 niveles. Pilas y colas. Skip Lists. Operaciones sobre cada tipo de estructura. Aplicaciones.

4. Propiedades, demostraciones y representación de grafos:
Definiciones. Propiedades. Representaciones básicas de grafos. Algoritmos sobre grafos.

5. Árboles computacionales:
Definición. Representación computacional. Árboles Binarios de Búsqueda. Árboles Balanceados en altura. Parva. Operaciones. Aplicaciones.

6. Distribución pseudo-aleatoria de datos:
Motivación. Funciones de pseudo-aleatorización. El problema del rebalse. Distintas propuestas para su manejo. Direccionamiento Directo. Aplicaciones.

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

 

Contacto con la cátedra:
- Por mail: eda@unsl.edu.ar
- Por formulario electrónico a través de la página web: http://eda.dirinfo.unsl.edu.ar
- Personalmente: Segundo Bloque - box 7, box 24 - Primer piso.

La modalidad de dictado es totalmente PRESENCIAL, tanto para teorías como para prácticos, siempre que las disposiciones lo permitan. En caso de presentarse alguna dificultad con respecto al modo de dictado, por favor comunicarse de inmediato con la cátedra.