Ciencias de la Computación FAMAF

Herramientas de usuario

Herramientas del sitio

Traza: • 2014
algo2:main:2014

Tabla de Contenidos

Algoritmos y Estructuras de Datos II

Novedades

Generalidades

Docentes

  • Teóricos: Daniel Fridlender.
  • Prácticos: Gonzalo Peralta y Alejandro Gadea (¡nuevo!).
  • Laboratorio: Natalia Bidart, Matías Bordese, Diego Dubois, Leonardo Rodríguez y Araceli Acosta (¡nueva!).
    • Ayudantes: Daniel Bridera, Lucía Pappaterra y Milagro Teruel.

Horarios

  • 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. Los martes se dicta clase, se enuncian y evalúan los proyectos, y se atienden consultas. Los jueves solo se atienden consultas.

Programa

  • 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.
  • Programa de la materia.

Régimen de aprobación, promoción y regularidad

  • Parciales: 2.
  • Fechas preliminares: 23/4/14 y 18/6/14.
  • Recuperatorio: 25/6/14. El recuperatorio no cuenta para la promoción.
  • Proyectos del laboratorio: 4.
  • Fechas preliminares de evaluación de proyectos: 25/3/14, 8 y 29/4/14, 13/5/14 y 10/6/14.
  • 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 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 2014, únicamente.

Preguntas frecuentes

  • 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 2014, 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 2014, no. Después de esas mesas, sí.

Evaluaciones

Parciales

Finales

Teórico

Horarios

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

Bibliografía

  • 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.

Clases

  • Primera parte: Análisis de Algoritmos.
  • Segunda parte: Estructuras de Datos.
    • 07/04/14: Tipos de datos. Tipos concretos y tipos abstractos. Tipos concretos: arreglos, listas, tuplas y punteros.07_tipos.pdf
    • 09/04/14: Tipos abstractos de datos. Paréntesis balanceados, TAD contador (grabá en tu disco y borrá la extensión .pdf). Delimitadores balanceados, TAD pila (grabá en tu disco y borrá la extensión .pdf). 08.tads.pdf
    • 14/04/14: Implementación del TAD contador. Listas enlazadas. Implementación del TAD pila usando listas enlazadas. 11.listas_enlazadas.pdf
    • 16/04/14: Tipos abstractos de datos. Productor-consumidor. Buffer. TAD cola. 09.tads.pdf
    • 21/04/14: Tipos abstractos de datos. Implementaciones elementales (basadas en arreglos) de pila y cola. 10.implementaciones_elementales.pdf
    • 23/04/14: Primer parcial.
    • 28/04/14: Resolución del parcial. Árboles binarios y árboles binarios de búsqueda.
    • 30/04/14: Árboles binarios de búsqueda y heaps. 14.heap.pdf
    • 05/05/14: Implementación de heap, cola de prioridades, heapsort. 14.heap.pdf
  • Tercera parte: Algoritmos Avanzados.
    • 07/05/14: Algoritmos voraces. Forma general. Problema de la moneda. Problema de la mochila. 15.voraz.pdf
    • 12/05/14: Algoritmos voraces. Problema del árbol generador de costo mínimo. Algoritmo de Prim. Algoritmo de Kruskal. Problema Union-Find. 16.voraz.pdf
    • 14/05/14: Algoritmos voraces. Problema del camino de costo mínimo. Algoritmo de Dijkstra. 17.dijkstra.pdf
    • 19/05/14: Backtracking. Problema de la moneda. Casos sin solución voraz. Solución que usa backtracking. Generalización. Recursión. Exploración de todas las posibilidades. 18.backtracking.pdf
    • 21/05/14: Paro (no hay teórico pero sí práctico). Leer por su propia cuenta el apunte y las filminas. Programación Dinámica. Problema de la moneda. Problema de la mochila. 19.programacion_dinamica.pdf
    • 26/05/14: Programación dinámica. Algoritmo de Floyd para el camino de costo mínimo entre todo par de vértices. 20.programacion_dinamica.pdf
    • 28/05/14: Algoritmo de Floyd, cálculo de los caminos. Obtención de las soluciones en los problemas de la moneda y la mochila.
    • 02/06/14: Recorrida de grafos. 21.dfs.pdf
    • 04/06/14: Backtracking es DFS en un grafo implícito. El problema de n reinas, (n reinas en Haskell). 22.8reinas.pdf
    • 09/06/14: Repaso de algoritmos voraces 23.combustible.pdf.
    • 11/06/14: Repaso de backtracking (8 reinas en c).
    • 16/06/14: Repaso de backtracking y programación dinámica.

Vínculos interesantes

Práctico

Horarios

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

Guías de ejercicios

Notas de parciales

Laboratorio

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

Horarios

  • 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).

Clases

Intro a punteros - slides

Punteros - slides

Intro a TADs

GDB - slides

Makefile - slides

Proyectos

Cómo correr los tests en sus compus

Cómo correr los tests de unidad de los proyectos: ver detalle en este tutorial.

Jaime

A lo largo de este cuatrimestre, las entregas de los proyectos y las entregas de los “parcialitos” van a ser a través de nuestro ayudante, Jaime.

Jaime es un ejecutor de tareas muy muy simple. Por cada proyecto, Jaime va a tener disponible un listado de tareas que va a permitir correr una serie de tests sobre el código producido por cada alumno.

Para visitar Jaime, ir a http://jaime.no-ip.info/. Es obligatorio tener un usuario, y se va a crear automáticamente un usuario por cada miembro de cada grupo del taller. Por cualquier duda, consultar en la lista de la materia.

Instrucciones para inscribirse en la lista de mails

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

https://groups.google.com/d/forum/famaf-ayed2

Para subscribirse, visitar el siguiente link:

http://groups.google.com/group/famaf-ayed2/subscribe

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á:

Instrucciones para mandar un mail en la lista de mails

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

famaf-ayed2@googlegroups.com

algo2/main/2014.txt · Última modificación: 2018/08/10 03:03 por 127.0.0.1