Algoritmos y Estructuras de Datos II

• Teóricos: Daniel Fridlender.
• Prácticos: Beta Ziliani, Demetrio Vilela, Emmanuel Gunther y Leandro Ramos.
• Laboratorio: Diego Dubois, Gonzalo Peralta, Jorge Rafael, Leonardo Rodríguez y Santiago Ávalos.
  • Ayudantes: Erik Canto Torres, Franco Margaria y Mariano Schmidt.

• Teóricos: lunes de 9 a 11hs y miércoles de 14 a 16hs, en el aula 17.
• Prácticos: lunes de 11 a 13hs y miércoles de 16 a 18hs, en el aula 17.
• Laboratorio: martes y jueves de 14 a 18hs, en el aula 28 (lab). Los martes se dicta clase, se enuncian y evalúan los proyectos, y se atienden consultas. Los jueves se atienden consultas.

Se pretende que el alumno adquiera:

• capacidad para comprender y describir el problema que resuelve un algoritmo (el “qué”) y diferenciarlo de la manera en que lo resuelve (el “cómo”),
• capacidad para analizar algoritmos, compararlos según su eficiencia en tiempo y en espacio,
• capacidad y hábito de identificar abstracciones relevantes al abordar un problema computacional,
• familiaridad con técnicas de diseño de algoritmos de uso frecuente,
• familiaridad con la programación (en el lenguaje c, entre otros) de algoritmos y estructuras de datos,
• familiaridad con la utilización de diversos niveles de abstracción y lenguajes de programación.

• Los contenidos se dividen en tres partes:
  • Análisis de algoritmos: algoritmos de ordenación, orden de un algoritmo, recurrencias.
  • Tipos abstractos de datos: tipos concretos versus tipos abstractos, contador, pila, cola, árboles.
  • Técnicas de programación: algoritmos voraces, divide y vencerás, programación dinámica, backtracking.
• En Programa de la materia se encuentra una descripción detallada de los contenidos, como así también de los objetivos de la materia, modalidad de evaluación, etc.

• Parciales: 2.
• Fechas: 22/04/2015, 17/06/2015.
• Recuperatorio: 24/06/2015. El recuperatorio no cuenta para la promoción.
• Proyectos del laboratorio: 4.
• Fechas preliminares de evaluación de proyectos: 26/03, a completar.
• Regularidad: aprobando dos parciales (eventualmente recuperando uno de ellos) + aprobando al menos 3 de los 4 proyectos del laboratorio (uno de ellos debe ser el 4to).
• Promoción: aprobando cada parcial con 6 o más, con promedio total de 7 o más + aprobando cada proyecto del laboratorio con 6 o más.
• Examen final: evaluación por escrito de teórico-práctico + resolución de problemas frente a la computadora (1 ó 2 días).
• Alumnos libres: ambas partes del examen (teórico y laboratorio) contienen ejercicios adicionales.
• Los alumnos regulares que promocionan sólo los parciales o sólo los proyectos del laboratorio serán exceptuados de rendir la parte promocionada en las mesas de julio-agosto de 2015, únicamente.

• La regularidad requiere regularidad en el teórico/práctico y en el laboratorio?
  • Sí: la regularidad de la materia es un AND de la regularidad del teórico/práctico con la regularidad del taller.
• Si voy al laboratorio un jueves de 14 a 18hs, ¿tendré a quien consultar mis dudas?
  • Sí, habrá docentes o ayudantes a quienes podrás consultar.
• Si apruebo los parciales pero no los proyectos del laboratorio, ¿deberé resolver ejercicios adicionales en el examen escrito?
  • Sí, porque vas a rendir como alumno libre.
• Si apruebo los proyectos del laboratorio pero no alcanzo a aprobar los parciales, ¿deberé rendir un examen de laboratorio con ejercicios adicionales?
  • Sí, porque vas a rendir como alumno libre.
• El año pasado aprobé los parciales pero no los proyectos del laboratorio, ¿debo rendir los parciales nuevamente durante este año?
  • Para poder regularizar, sí.
• El año pasado aprobé los proyectos del laboratorio pero no alcancé a aprobar los parciales, ¿debo volver a hacer el laboratorio este año?
  • Para poder regularizar, sí.
• ¿Puedo rendir el examen final sin haber hecho el laboratorio?
  • Sí. Como alumno libre. Pero deberás demostrar suficientes conocimientos de programación durante el examen.
• El año pasado regularicé (es decir, estaba inscripto como regular, aprobé los parciales y los proyectos del laboratorio). Quiero volver a cursar este año. ¿Voy a perder la regularidad obtenida el año pasado?
  • Si te inscribís en la materia automáticamente perdés esa regularidad. Te conviene volver a cursarla sin inscribirte.
• En ese caso, ¿qué pasa si este año promociono?
  • Te inscribís en la primera fecha de exámenes y te pasamos la nota de la promoción.
• Tengo condición de regular y promocioné los parciales pero no los proyectos del laboratorio. ¿Debo rendir el escrito también?
  • En las mesas de julio-agosto 2015, no. Después de esas mesas, sí.
• Tengo condición de regular y promocioné los proyectos del laboratorio pero no los parciales. ¿Debo rendir el laboratorio también?
  • En las mesas de julio-agosto 2015, no. Después de esas mesas, sí.

• Primer parcial, 22/04/2015.
• Segundo parcial, 17/06/2015.
• Primer y segundo recuperatorios, 24/06/2015.

Lunes de 9 a 11hs y miércoles de 14 a 16hs, en el aula 17.

• Notas de Algoritmos y Estructuras de Datos II.
  • analisis.pdf
  • Buscar en la wiki del año pasado. Los insertaré aquí a medida de que los actualice.

• Brassard and Bratley, Fundamentals of Algoritmics.

• Manber, Introduction to Algorithmics: A Creative Approach.

• Bibliografía Complementaria
  • Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms.
  • Balcázar, Programación Metódica.
  • Biggs, Matemática Discreta.
  • Kaldewaij, Programming: the Derivation of Algorithms.
  • Blanco, Smith y Barsotti, Cálculo de Programas.

• Tutoriales de lenguaje C
  • En castellano pero básico
  • En ingles pero muy completo
  • Manual de referencia en inglés
    This is a reference manual for the C programming language as implemented by the GNU Compiler Collection (GCC).

• Otros
  • Object-Oriented Programming Versus Abstract Data Types

• Primera parte: Análisis de Algoritmos.
  • 09/03/15: Introducción a la materia, análisis de algoritmos (motivación), problema del bibliotecario, ordenación por selección, número de comparaciones. 01.ordenacion_seleccion.pdf
  • 11/03/15: Conteo de operaciones, número de intercambios. Ordenación por inserción. análisis, mejor caso, peor caso y caso medio.01b.ordenacion_insercion.pdf
  • 16/03/15: Ordenación por intercalación. 02.ordenacion_intercalacion_filminas.pdf. Ordenación rápida. 03.ordenacion_rapida_filminas.pdf
  • 18/03/15: Demo de los diferentes algoritmos de ordenación vistos. Algoritmos “divide y vencerás”. Análisis de la ordenación por intercalación y de la ordenación rápida. 04.divide_y_venceras.pdf
  • 23/03/15: Feriado.
  • 25/03/15: Notación O, Omega y Theta. Propiedades elementales. Regla del límite. Jerarquía. 05.notacion_o.pdf
  • 30/03/15: Jerarquía, propiedades especiales. Algoritmos divide y vencerás. Recurrencias divide y vencerás. Búsqueda binaria. 06.recurrencias_dyv.pdf
  • 01/04/15: Recurrencias homogéneas y no homogéneas. 07.recurrencias_homogeneas_y_no.pdf

• Segunda parte: Estructuras de Datos.
  • 06/04/15: Tipos concretos de datos versus tipos abstractos de datos. Tipos concretos: arreglos, listas, tuplas y punteros. 08.tipos.pdf
  • 08/04/15: Tipos abstractos de datos. Paréntesis balanceados, TAD Contador. Delimitadores balanceados, TAD Pila. 09.tads.pdf
  • 13/04/15: Implementaciones del TAD Contador. Implementaciones naturales y otras. Implementaciones del TAD Pila. Usando listas, arreglos, listas enlazadas. 10.implementaciones_contador_pila.pdf
  • 15/04/15: Buffer. TAD Cola. Implementaciones: usando listas (asumiendo que vienen en el lenguaje), discusión sobre el orden de enqueue; usando arreglos ingenuamente, usando arreglos circulares; usando listas enlazadas ingenuamente, usando listas enlazadas con puntero al primero y al último; y con listas enlazadas circulares. 11.colas.pdf
  • 20/04/15: Repaso de TADs y sus implementaciones.
  • 22/04/15: 1er parcial.
  • 27/04/15: Ordenación, TAD cola de prioridades. TAD árbol binario. Terminología habitual: de la botánica y de la genealogía. 12.arboles_binarios.pdf
  • 29/04/15: Árboles binarios de búsqueda. TAD Conjunto finito, implementación con árboles binarios de búsqueda. 13.abb.pdf
  • 04/05/15: Heaps. Heaps balanceados. Implementación sobre arreglos. Heapsort. 14.heap.pdf

• Tercera parte: Algoritmos Avanzados.
  • 06/05/15: Algoritmos voraces. Forma general. Problema de la moneda. Problema de la mochila. 15.voraz.pdf
  • 11/05/15: Algoritmos voraces. Problema del árbol generador de costo mínimo. Algoritmo de Prim. Algoritmo de Kruskal. Problema Union-Find. 16.voraz.pdf
  • 13/05/15: Algoritmos voraces. Problema del camino de costo mínimo. Algoritmo de Dijkstra. 17.dijkstra.pdf.
  • 18/05/15: Backtracking. Problema de la moneda, simplificación, generalización, variantes. moneda.tgz Problema de la mochila. Problema de los caminos de costo mínimo. caminos.tgz 18.backtracking.pdf
  • 20/05/15: Programación dinámica: Fibonacci, problema de la moneda, problema de la mochila. 19.programacion_dinamica.pdf. fibonacci.tgz moneda2.tgz
  • 27/05/15: Programación dinámica: algoritmo de Floyd. 20.programacion_dinamica.pdf. caminos2.tgz
  • 01/06/15: Recorrida de grafos. Recorrida de árboles binarios, pre-order, in-order, pos-order. Recorrida de árboles finitarios. Recorrida de grafos dirigidos. DFS y BFS. 21.dfs.pdf
  • 03/06/15: Backtracking y DFS. Problema de las 8 reinas. 22.8reinas.pdf.reinas.tgz

• Algoritmos de ordenación.
  • en wikipedia
  • Algunos visualizadores
    • http://sorting.at/
    • http://www.sorting-algorithms.com/
    • https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
    • http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
    • http://math.hws.edu/TMCM/java/xSortLab/
    • http://thomas.baudel.name/Visualisation/VisuTri/
  • Algo-Ritmos
    • Ordenación por intercalación
    • Ordenación rápida
• Notación O
  • en wikipedia
  • Visualizador
    • function-graphs
• TADs
  • Algunos visualizadores
    • Pilas y colas download.html
    • Árboles binarios AVL

Lunes de 11 a 13hs y miércoles de 16 a 18hs, en el aula 17.

• Práctico 1: Análisis de algoritmos Parte 1, Parte 2 y Parte 3.
• Práctico 2: Estructuras de datos Parte 1 y Parte 2.
• Práctico 3: Algoritmos avanzados Parte 1, algoritmos voraces, Parte 2, backtracking y programación dinámica y DFS, BFS y backtracking.

Los grupos serán de 2 (dos) personas. Mínimo 2, máximo 2. O sea, 2 .

• Martes 14 a 18 hs: Teóricos del taller, presentación de enunciados, entregas y evaluación de proyectos, consultas.
• Jueves 14 a 18 hs: Uso del laboratorio y consultas.

Todas las clases son en el laboratorio de computación del 2do piso (aula 28).

• Proyecto 1: Algoritmos de Ordenación
  • Enunciado
  • Esqueleto de Código
• Proyecto 2: Diccionario con Listas Enlazadas
  • Enunciado
  • Esqueleto de código
  • Versión nueva del código objeto para testear.
• Proyecto 3: Diccionario con Árboles Binarios de Búsqueda
  • Enunciado
• Proyecto 4: Algoritmo de Kruskal.
  • Enunciado
  • Esqueleto

• Repaso de arreglos, estructuras. Código de ejemplo
• GDB - slides
• Punteros (slides)
• Intro a TADs
• Makefile - slides
• Ejemplo Makefile + TAD Person

• Jaime

Tenemos un googlegroup para los alumnos y los docentes en la siguiente dirección:

https://groups.google.com/forum/#!forum/ayed2-famaf

Para subscribirse, hacer click en “solicitar membresía” (o “subscribe to this group”).

Por favor elegir una dirección de mail que lean todos los días y que no tenga restricciones de tamaño. No es obligatorio que sea un email de gmail. Las direcciones de hotmail/outlook están particularmente no recomendadas ya que suelen llenarse rápido y no les llegan los correos.

IMPORTANTE 1: una vez que se subscribieron al grupo, ir a la casilla de mail que usaron y aceptar la invitación.

IMPORTANTE 2: si ya estaban logueados en gmail, les aparece un diálogo para la subscripción donde tienen que elegir, entre otras cosas, el tipo de envíos de los emails: elegir “todos los emails”, como se muestra acá:

Para mandar un mail a la lista de la materia, escribir a:

ayed2-famaf@googlegroups.com