2.1.1 - Algoritmos y estructuras de datos II

Segundo Año

Característica del Área Curricular
Plan	2015
Cuatrimestre	Primero
Hs. Cat.	120
Res. C.S.	291/2015

Presentación

La asignatura se ubica en el primer semestre del segundo año de la carrera. Esta actividad curricular profundiza en los conceptos y practicas de la algoritmia, la resolución de problemas y en la formalización bajo conceptos de induccion.

El objetivo general es que se siente las bases para seguir profundizando los conocimientos y sea una herramienta util para el resto de las materias de programación en general y las algoritmias en particular.

Objetivos

La materia brindará al alumno una aproximación al estudio formal de algoritmos, poniendo énfasis en aspectos relacionados con la computabilidad del problema, complejidad y búsqueda de soluciones optimizadas.

Contenido Temático

Unidad 1:

Modelos de Costo. Modelo basado en lenguajes. Paralelización. Trabajo y profundidad. Recurrencias. Solución de recurrencia. Teorema Maestro.

Unidad 2:

Programación Funcional con Haskell: Entrada/Salida. Tipos Algebraicos, clases e instancias.

Unidad 3:

Especificando y razonando acerca de programas. TAD e inducción estructural. Implementación de TADs en Haskell.

Unidad 4:

Estructuras persistentes: Estructuras de datos funcionales e imperativas. Persistentes y efímeras. Árboles binarios: Árboles binarios de búsqueda, Arboles balanceados: Red Black Tree y Heaps: Leftist Heaps.

Unidad 5:

Técnicas para el diseño de algoritmos: Fuerza Bruta, Divide & Conquer, Programación Dinámica y Algoritmos Voraces (Greedy).

Unidad 6:

Conjuntos Disjuntos: Set, Union y Find. Algoritmos de exploración de grafos.

Bibliografía

Modelo de Costo - J.M. Rabasedas - Apunte de cátedra - 2015.
Introducción a la programación funcional con Haskell - R. Bird - Prentice Hall - 1997.
Introducction to Algotithms - T. H. Comen - MIT Press - 1998.
Purely Functional Data Structures - C. Okasaki - CUP - 1998.