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

Docente	Función	Cargo	Dedicación
HERRERA, NORMA EDITH	Prof. Responsable	P.Asoc Exc	40 Hs
REYES, NORA SUSANA	Prof. Responsable	SEC U EX	2 Hs
KASIAN, FERNANDO ANDRES	Prof. Co-Responsable	P.Adj Exc	40 Hs

En esta asignatura se recuperan los fundamentos de distintas estructuras de datos, para analizar en detalle la eficiencia de los algoritmos que operan sobre ellas.

Además, como el estudiante ya se inició en el análisis de algoritmos en la materia Estructuras de Datos y Algoritmos I, se estudiarán las herramientas matemáticas necesarias y se profundizará desde allí el aprendizaje de cómo comparar algoritmos y analizar su desempeño, porque es fundamental al momento de diseñar buenas soluciones.

Se fortalecen aquí las bases sobre Estructuras de Datos y Algoritmos, de la materia previa y luego se integran con las que se aporten en la asignatura Base de Datos I, para lograr finalmente una base consolidada en las disciplinas Estructuras de Datos, Algoritmos 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.

Para complementar las estructuras de datos ya vistas, se aborda su diseño considerando las evocaciones asociativas con respuesta múltiple y, además, cuáles son las características a considerar respecto de cualquier estructura de datos que deba almacenarse en memoria secundaria. Este proceso incluye el análisis de eficiencia de las estructuras presentadas.

Como se han estudiado distintas técnicas de diseños de algoritmos previamente, se analizarán otros algoritmos representativos de cada una, entre los cuales se considerarán Algoritmos y Aplicaciones sobre grafos.

El presente curso tiene como objetivo principal que los estudiantes sean capaces de manejar con idoneidad otros conceptos que involucran el diseño de diferentes estructuras de datos y algoritmos. Además, se espera que adquieran un conocimiento exhaustivo de las principales estructuras de datos, tanto de respuesta única como múltiple y de almacenamiento en memoria principal o secundaria, y su desempeño. También se pretende que los estudiantes afiancen 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 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 curiosa y crítica 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


Sucesiones y series. Aplicaciones en Análisis de Algoritmos. Aplicaciones de Grafos. Algoritmos sobre grafos. Análisis de Algoritmos: comportamiento en el mejor caso, caso promedio y peor caso. Notaciones asintóticas. Balance entre tiempo y espacio en los algoritmos. Análisis de operaciones sobre estructuras de datos para evocaciones de respuesta única. Evocaciones de respuesta múltiple sobre distintas estructuras de datos. Características de estructuras de datos para memoria secundaria. Características de algoritmos desarrollados con distintas técnicas de diseño de algoritmos.


Contenidos Detallados


1. Sucesiones y Series:


Repaso de temas y homogeneización de terminología. Fórmulas sumatorias y propiedades. Series aritméticas, geométricas, harmónicas. Operaciones sobre sumatorias.


2. Análisis de algoritmos:


Repaso de conceptos de evaluación de algoritmos. Análisis del comportamiento en el mejor caso, caso promedio y peor caso. Otras notaciones asintóticas. Balance entre tiempo y espacio en los algoritmos. Análisis detallado de los algoritmos que operan en las estructuras de datos para evocaciones de respuesta única.


3. Evocaciones de Respuesta Múltiple:


Problema de evocación de respuesta múltiple. Comportamiento de los algoritmos y las estructuras para evocaciones de respuesta única frente a este problema. Adaptación de las estructuras de datos conocidas. Estructura general y componentes para la rutina de evocación asociativa. Transformación de evocación de respuesta múltiple a respuesta única.


4. Estructuras de Datos para Memoria Secundaria:


Componentes y características de los dispositivos de almacenamiento para memoria secundaria. Tiempos de acceso. Consideraciones para minimizar los tiempos de acceso. Características de estructuras de datos para memoria secundaria. Ejemplos de estructuras.


5. Diseño de algoritmos:


Repaso de técnicas de diseño de algoritmos. Ejemplos de aplicación en algoritmos sobre Grafos. Características de algoritmos desarrollados con distintas técnicas de diseño de algoritmos.

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. Para llevar a cabo estas prácticas se considera el estudio de una situación real para luego informatizar, esto permite que los estudiantes evalúen el contexto social en el que estará inserto su proyecto y adecúen el mismo para que se amolde a ese contexto global y local.

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, de manera continua, 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).

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. Sucesiones y Series. Resolución de ejercicios típicos y su aplicación al análisis de algoritmos.

2. Análisis de los algoritmos que implementan las operaciones sobre las estructuras de datos vistas para evocaciones de respuesta única.

3. Evocaciones de Respuesta Múltiple. Posibles implementaciones. Desarrollo y análisis de los algoritmos necesarios para responder a este tipo de servicio.

4. Estructuras de Datos para Memoria Secundaria. Posibles implementaciones. Desarrollo y análisis de los algoritmos necesarios para este tipo de estructuras de datos.

5. Diseño de algoritmos. Soluciones a problemas en grafos. Análisis de los algoritmos usados.

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 estudiantes 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 y 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 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, AddisonWesley 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: 0673-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. * Árboles Binarios Ordenados. * Costos de Búsqueda en Árboles Binarios de Búsqueda. * Lista de 2 Niveles. * Distribución Pseudo-aleatoria de Datos. * Deducción de algunos esfuerzos para distribución pseudo- aleatoria de datos.

[1] COMPUTER ALGORITHMS: INTRODUCTION TO DESIGN AND ANALYSIS, Autor: Baase, Sara, ISBN: 0201-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: 0201-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:0201-00029-6, Addison-Wesley, 1974, Ubicación en biblioteca: 519.683.2 A286.
[4] 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.
[5] DATA STRUCTURES TECHNIQUES, Autor: Standish, T., ISBN: 0-201-07256-4, Addison-Wesley, 1980, Ubicación en biblioteca: 681.3.0651.S785.
[6] 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.
[7] 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.
[8] PUGH, WILLIAM: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM, 33, 1990, pág. 668-676.
[9] LEWIS, T y COOK, C: Hashing for Dynamic and Static Internal Tables. IEEE Comp. Oct.1988.
[10] LARSON, P: Dynamic Hash Tables. C. ACM, Vol 31 N0 4, Abril 1988.

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. Sucesiones y Series

2. Análisis de algoritmos

3. Evocaciones de Respuesta Múltiple

4. Estructuras de Datos para Memoria Secundaria

5. Diseño de algoritmos

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. En caso de presentarse alguna dificultad con respecto al modo de dictado, por favor comunicarse de inmediato con la cátedra.