Universidad Nacional del Litoral
Facultad de Ingeniería y Ciencias Hídricas

Algoritmos y Estructuras de Datos

ATENCIÓN: Parte del sitio de la cátedra se movió a http://www.cimec.org.ar/cursos

Ir a la Página de Notas

Indice

Cátedra e info de la materia. Contacto

• Carreras: Ingeniería Informática, Analista en Informática Aplicada
• Extension: Cuatrimestral
• Carga horaria: 90 hs de clases (30 hs teoría / 60 hs práctica)

• Docentes:
  • Dr. Mario A. Storti, (mario.storti (at) gmail.com)
  • Dr. Rodrigo R. Paz, (rodrigo.r.paz (at) gmail.com)
  • Dr. Lisandro D. Dalcin, (dalcinl (at) gmail.com)
    (at)=@ para reducir el spam

Programa Analítico

Está accesible la planificación de la materia.

1. Diseño y análisis de algoritmos. De los problemas a los programas. Tipos de datos abstractos (TDA). Tipos de datos, estructura de datos y tipos de datos abstractos.
2. Tipos de datos abstractos fundamentales. El tipo de dato abstracto ``Lista''. Realización de listas. Pilas. Colas. Correspondencias.
3. Arboles. Terminología fundamental. El TDA ``árbol''. Realización de árboles. Arboles binarios.
4. Operaciones básicas con conjuntos. Introducción a los conjuntos (sets). Un TDA con UNION, INTERSECCION y DIFERENCIA. Realización de conjuntos mediante vectores de bits. Realización de conjuntos mediante listas enlazadas. El diccionario. Realizaciones sencillas de diccionarios. La estructura de datos tabla de dispersión. Estimación de la eficiencia de las funciones de dispersión. Realización del TDA CORRESPONDENCIA. Colas de prioridad. Realización de colas de prioridad. Algunas estructuras complejas de conjuntos.
5. Métodos Avanzados de Representación de Conjuntos. Arboles binarios de búsqueda. Tries.
6. Clasificación. El modelo de clasificación interna. Algunos esquemas simples de clasificación. Clasificación rápida (Quicksort). Clasificación por montículos (Heapsort).
7. Técnicas de análisis de algoritmos. Eficiencia de los algoritmos. Tiempo de ejecución de un programa. Cálculo del tiempo de ejecución de un programa. Buenas prácticas de programación. Análisis de programas recursivos.
8. Técnicas de diseño de algoritmos. Algoritmos dividir para vencer. Programación dinámica. Algoritmos ávidos (greedy). Método de retroceso (Backtracking). Algoritmos de búsqueda local.

Bibliografía

Modalidad de Dictado

Se dictarán clases:

• Teóricas (2.5 hs semanales)
• Prácticas (4.5 hs semanales)
• De consulta (2hs semanales)

Horarios

• Teoría: [A cargo de Mario Storti y Rodrigo Paz]
  • Unico turno: Martes de 13:15hs a 15:45hs (Aula 9)
• Prácticas: [A cargo de Rodrigo Paz, Lisandro Dalcín y Mario Storti]
  • Martes de 16:00hs a 18:00hs (Aula 9)
  • Jueves de 16:00hs a 18:30hs (Aula 9)
• Consultas: Miércoles 16:00hs-18.00hs en el CIMEC (ver plano de ubicación)
• Consultas: [A cargo de Diego Galizzi y Juan Daniel Prigioni] Miércoles 1400hs a 1500hs en el Laboratorio 2

Evaluación

La evaluación se realiza mediante tres exámenes parciales. La regularidad se logra aprobando todos los parciales. Para ello deben contar con una calificación mínima de 40% y obtener un porcentaje mínimo en cada sección del parcial. Este porcentaje mínimo puede variar, pero típicamente es de 60% en preguntas, 40% en programacion, 25% en operativos, y 50% en clases.

Lograrán promoción directa aquellos alumnos regulares que obtengan un promedio en los parciales de al menos 70 sobre 100 puntos. Se calcula una Nota Final igual al promedio de las notas de los Exámenes Parciales.

Se realizará un Examen Recuperatorio. Las reglas del mismo se pueden consultar aquí.

Aquellos alumnos que no logren promoción directa, deberán rendir un examen final.

Cronograma Tentativo

• Inicio de Clases: Semana 1
• Primer Parcial: Semana 5
• Segundo Parcial: Semana 11
• Tercer Parcial: Semana 15
• Recuperatorio: Semana 16

Guías de Trabajos Prácticos

Las guías se movieron a la plataforma Moodle http://www.cimec.org.ar/cursos

Exámenes parciales y finales tomados previamente

(Previo a 2002 en formato MS-Word, posteriores en formato PDF)

• Año 2000 (exam00.zip)
• Año 2001 (exam01.zip)
• Año 2002 (exam02.zip)
• Año 2003 (exam03.zip)
• Año 2004 (exam04.zip)
• Año 2005 (exam05.zip)
• Año 2006 (exam06.zip)
• Año 2007 (exam07.zip)
• Año 2008 (exam08.zip)
• Año 2009 (exam09.zip)
• Año 2010 (exam10.zip)
• Año 2011 (exam11.zip)
• Todos hasta 2010 inclusive (zippeados: aed-all-exam.zip, en un gran PDF: aed-all-exam.pdf)

Migración de Pascal a C++

El lenguaje de programación que se usa desde el cursado 2004 es C++. (Anteriormente se daba en Pascal)

• La bibliografía principal a utilizar serán los apuntes de la cátedra (disponible en esta página) y el libro de Aho.
• Los exámenes finales se empezaron a tomar en C++ a partir de la primera fecha de julio 2004. Hasta entonces se tomaba en Pascal.
• Todos los ejemplos se escribirán en C++.

Enlaces de interés

• http://www.cs.princeton.edu/~rs/shell/animate.html: Clasificación animada interactiva (se puede cambiar la secuencia de algoritmos que trabajan con distintos incrementos), se ve muy bien el último paso en clasificación shellsort
• http://oopweb.com/Algorithms/Documents/PLDS210/VolumeFrames.html: OOP, algoritmos y estructura de datos. Parece una buena referencia online.
• http://www.brpreiss.com/books/opus4/: También, una muy buena referencia online sobre OOP, algoritmia y estructuras.
• http://www-cg-hci.informatik.uni-oldenburg.de/~da/peters/Kalvin/Doku-SN.htm Algoritmos de clasificación y sus fuentes. Animaciones.

Repositorio de archivos

En el repositorio de archivos se pueden encontrar ejercicios resueltos de las guías o tomados en exámenes parciales y finales previos. (El viejo repositorio con programas en Pascal se accede aqui )

Lista de correo "Noti-AED"

Las comunicaciones de la cátedra no se realizan más por la lista de correo, se hacen por la plataforma Moodle http://www.cimec.org.ar/cursos