- 1 -

Carrera: Licenciatura en Sistemas

Materia: ALGORITMOS Y ESTRUCTURAS DE DATOS

Profesor Asociado: Mg. Diego Azcurra Instructor JTP: Lic. Damián Santos Año: 2011 Cuatrimestre: Primero

- 2 -

Fundamentación de la Asignatura: Esta asignatura desarrolla el primer contacto del alumno con los fundamentos teóricos del área de programación. Esta situación fundacional implica que los resultados a obtener se deben medir tanto en conocimientos específicos a incorporar, como en la adquisición de hábitos de “buena construcción algorítmica” que apunten a toda la carrera y a la futura actividad profesional. El concepto central de iniciación en la construcción de algoritmos y las estructuras de datos asociadas, se basa en transmitir los principios básicos e invariantes de la disciplina. Ante el bombardeo permanente de novedades tecnológicas, el alumno se ve inducido a pensar que lo valioso es la persecución, en realidad imposible, de la “última versión”; siendo un peligro común que existe al intentar comprender esta disciplina, el pasar por alto los conceptos generales para sumergirse en la incorporación acrítica y memorista de recetas vinculados a una herramienta determinada (a veces con una marca determinada). En este contexto, uno de los objetivos a conseguir es justamente el que se comprenda que existen conceptos primigenios y fundamentales, cuyo conocimiento permitirá el enfrentarse con solvencia a las novedades. Se busca transmitir paradigmas poniendo énfasis en la modulación y lo estructurado, en la línea de Wirth, buscando potenciar el tratamiento de las estructuras de datos como un modelo conceptual de organizar la información y algoritmos asociados a su manejo con las nociones de eficiencia y corrección. Efectos paralelos y deseables, compartidos con otras asignaturas, son ejercitar la capacidad de correlacionar, abstraer y concretar pensamientos. 2 - Objetivos: - Que el alumno maneje los fundamentos teóricos de las estructuras de datos no

lineales, su representación conceptual mediante la teoría de grafos y teorías conexas y la correspondiente manipulación algorítmica.

- Que el alumno asimile los conceptos de recursión y complejidad algorítmica. 3 - Contenidos: UNIDAD 1: ESTRUCTURAS DE DATOS NO LINEALES CON ÁRBOLES Propiedades de los árboles. Árboles generadores. Árboles generadores

minimales. Recorrido de árbol. Ordenamiento de árboles. Balanceo de árboles. Árboles de juegos. Búsqueda en profundidad. Búsqueda en anchura. Estructuras de datos no lineales asociadas a árboles. Punteros. Aplicaciones.

UNIDAD 2: RECURSIÓN Generalidades sobre recursión. Recurrencias lineales. Bisección

recursiva. Optimización Recursiva. Fundamentos de la teoría de funciones recursivas. Funciones recursivas primitivas. Alcances de la

- 3 -

funciones recursivas primitivas. Funciones recursivas parciales. Recursión en los lenguajes de programación. Aplicaciones.

UNIDAD 3: GRAFOS Representaciones de Grafos. Caminos y circuitos. Camino más corto

entre nodos. Isomorfismo de grafos. Planaridad de grafos. Dígrafos. Redes y caminos críticos. Flujos y cortes. Flujo máximo y corte mínimo. Etiquetado para flujo en redes. Aplicaciones.

UNIDAD 4: ALGORÍTMICAS Algoritmo de recorrido de árbol. Algoritmo de ordenamiento de árboles.

Algoritmo de balanceo de árboles. Algoritmo de búsqueda en profundidad. Algoritmo de búsqueda en anchura. Algoritmo para el camino más corto en grafos. Algoritmo de obtención del flujo máximo y corte mínimo en redes. Algoritmo de etiquetado para flujo en redes.

UNIDAD 5: COMPLEJIDAD Complejidad de cálculos. Complejidad de algoritmos. Complejidad de

problemas. Complejidad de temporal de los problemas de reconocimiento de lenguajes. Complejidad de temporal de maquinas no deterministas. Aplicaciones.

4 - Metodología de Trabajo: Clases teórico-prácticas:

Exposición teórica de conceptos fundamentales con base en guias de estudio de material seleccionado, con resolución metódica y revision en clase. Discusión de algoritmos destacados con base en resultados de investigación documental en repositorios de internet.

Clases prácticas:

Resolución por parte de los alumnos y controlada por el equipo docente de problemas correspondientes a las unidades temáticas del programa, ya sea por escrito o por máquina (programas). En general se tratará de problemas abiertos, que generen dudas y motiven la consulta a los docentes y la profundización del conocimiento a través de la bibliografía. Durante el curso se plantearán trabajos prácticos con problemas complejos a resolver, que los alumnos deberán desarrollar en grupo.

Clases de consulta:

Se dispondrá de un sistema de atencion de consultas via correo electrónico utilizando las cuentas ptrovistas por la Facultad.

- 4 -

5 - Evaluación y Acreditación: De manejo de conceptos, aplicación de conocimientos y dominio de técnicas, mediante la respuesta a preguntas y la resolución de problemas por escrito en evaluaciones parciales e integradoras, y el desarrollo controlado de guias de estudio y trabajos prácticos. Las evaluaciones parciales e integradoras son por unidades o subunidades temáticas. La evaluación de los trabajos practicos es por presentación en tiempo y forma (plazos y formato establecido), método de desarrollo (aplicación de método de desarrollo visto en el curso) y corrección del resultado (cumplimiento de objetivos del programa) 6 - Bibliografía: Aho, A., Hopcroft, J. y Ullman, J. 1988. Estructura de Datos y Algoritmos. Editorial

Addison-Wesley Iberomaricana.

Biggs, N. 1994. Matemáticas Discretas. Ediciones Vicens Vives.

Braunstein, S. y Gioia, A. 1987. Introducción a la Programación y a las Estructuras de Datos. EUDEBA.

Brookshear, J. 1993. Teoría de la Computación. Editorial Addison-Wesley Iberomaricana.

Johnsonbaugh, R. 1988. Matemáticas Discretas. Grupo Editorial Iberomaricana.

Weiss, M. 1995. Estructura de Datos y Algoritmos. Editorial Addison-Wesley Iberomaricana.