Algoritmos y Estructuras de Datos II

  • Docentes:
    • Teóricos: Daniel Fridlender
    • Prácticos: Walter Alini, Diego Lis, Alejandro Tiraboschi
      • Ayudantes: Germán Ceballos, Franco Rodríguez Fábregues
    • Taller: Damian Barsotti, Martín Domínguez, Diego Dubois, Natalia Bidart.
      • Ayudantes: Florencia Mihaich, Cesar Bernardini, Leonardo Rodriguez, Ezequiel Velez.

Generalidades

  • Parciales: 3 (fechas preliminares: 7/4/10, 10/5/10 y 16/6/10).
  • Promoción: no hay.
  • Regularidad: estando inscripto como regular + aprobando 2 parciales + aprobando el taller.
  • Examen: examen escrito + resolución de problemas frente a la computadora (2 días).
  • Alumnos libres: ambas partes del examen contienen ejercicios adicionales.

Preguntas frecuentes

  • Si apruebo los parciales pero no el taller, ¿deberé resolver ejercicios adicionales en el examen escrito?

Sí, porque vas a rendir como alumno libre.

  • Si apruebo el taller pero no alcanzo a aprobar dos 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 el taller, ¿debo rendir los parciales nuevamente durante este año?

Para poder regularizar, sí.

  • El año pasado aprobé el taller pero no alcancé a aprobar dos parciales, ¿debo volver a hacer el taller este año?

Para poder regularizar, sí.

  • ¿Puedo rendir el examen final sin haber hecho el taller?

Sí. Como alumno libre.

  • El año pasado regularicé (es decir, estaba inscripto como regular, aprobé los parciales y el taller). 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.

Teórico

Bibliografía

  • 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

  • Parte 1: Análisis de algoritmos.
    • Lunes 08/03: Presentación, motivación, ordenación por selección, conteo.
    • Miércoles 10/03: Método para contar operaciones, ordenación por inserción, peor caso, mejor caso y caso medio.
    • Lunes 15/03: Notación O. Definición, propiedades. Regla del límite. Jerarquía de funciones.
    • Miércoles 17/03: Jerarquía de funciones. Notación complementaria. Equivalencias. Búsqueda lineal y binaria. Ordenación por intercalación.
    • Lunes 22/03: Análisis de la ordenación por intercalación para potencias de 2. Funciones eventualmente no decrecientes. Funciones i-suaves, funciones suaves. Ejemplos. Ordenación por intercalación. Recurrencias divide y vencerás. Análisis de una versión recursiva de la búsqueda binaria.
    • Miércoles 24/03: Feriado.
    • Lunes 29/03: Ejemplos de recurrencias divide y vencerás. Recurrencias homogéneas. Ejemplos. Método general. Demo de ordenación.
    • Miércoles 31/03: Recurrencias no homogéneas. Método general. Ejemplos (entre ellos: comparaciones del algoritmo de intercalación).
  • Parte 2: Estructuras de datos.
    • Lunes 05/04: Estructuras de datos: concretas (demo) vs. abstractas. Estructuras concretas: arreglos, listas, tuplas, punteros. Estructuras abstractas: paréntesis balanceados (TAD contador).
    • Miércoles 07/04: Primer parcial.
    • Lunes 12/04: Generalización de paréntesis balanceados (TAD pila), especificación, pila y recursión, implementaciones habituales. En el práctico: clase del TAD cola, implementaciones con listas y con arreglos.
    • Miércoles 14/04: TAD cola: repaso e implementaciones. Listas enlazadas. Pilas con listas enlazadas, demo.
    • Lunes 19/04: Implementación de colas con listas enlazadas. Con dos punteros. Con listas circulares. TAD lista. TAD árbol binario, introduccion.
    • Miércoles 21/04: Árboles binarios de búsqueda, implementación de diccionarios.
    • Lunes 26/04: Cola de prioridades y heaps. Heapsort.
  • Parte 3: Técnicas de diseño de algoritmos.
    • Miércoles 28/04: Heapsort. Desarrollos top-down y bottom-up. Algoritmos divide y vencerás. Características. Ejemplos. Forma general. Quicksort (ordenación rápida), clasificar, elección del pivot.
    • Lunes 03/05: Divide y vencerás: Ejemplo de quicksort. Exponenciación. Multiplicación de números grandes. Algoritmos voraces: problema de la moneda, problema de la mochila.
    • Miércoles 05/05: Algoritmos voraces: algoritmo de Dijkstra.
    • Lunes 10/05: Segundo parcial.
    • Miércoles 12/05: Algoritmos voraces: árbol generador de costo mínimo. Prim. Kruskal. Problema Union-Find.
    • Lunes 17/05: Programación dinámica (y backtracking). Fibonacci. Problema de la moneda. Problema de la mochila.
    • Miércoles 19/05: Programación dinámica (y backtracking). Algoritmo de Floyd. Funciones con memoria. Inicialización virtual.
    • Lunes 31/05: Inicialización virtual. Recorrida de árboles binarios y finitarios
    • Miércoles 02/06: Recorrida de grafos, dfs y bfs
    • Lunes 07/06: Backtracking.
    • Miércoles 09/06: Branch & Bound.
    • Lunes 14/06: Branch & Bound.

Vínculos interesantes

Práctico

Laboratorio

Horarios

  • Martes 14 a 18 hs: Uso reservado para prácticas libres de alumnos de la materia.
  • Jueves 14 a 18 hs: Teórico del taller y consultas.

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

Clases

9/03:

Modelos de memoria

Punteros en C

Funciones malloc calloc free

Proyectos

  • Proyecto 2 segunda parte: TAD Diccionario con lista de asociaciones en cinta de tuplas. Librería de cinta de escritura y lectura de tuplas en archivos ☛ libcrw.
  • Proyecto 4: Kruskal. Se brinda además un archivo .dot con el grafo de ciudades y distancia entre ellas, mas una tabla que mapea que número de nodo corresponde a que ciudad y un script para generar el archivo pdf ejecutando neato. Con el programa del proyecto calcular el mínimo tendido de fibra óptica para interconectar las ciudades.

Notas del Taller

Instrucciones para inscribirse en la lista de mails

Ir a la página de la lista y llenar los datos.

o

Enviar un mail a:

alualgo2-join@famaf.unc.edu.ar

con cualquier subject o cuerpo del mail.

Despues de enviarlo debe llegar un mail donde diga que la subscripcion fue realizada correctamente. Hacer un reply con el mismo subjet (pero que no diga Re: —).

!! Tener en cuenta !!

Si se cometio un error el sistema enviará un mail avisando. Por lo cual, siempre lea el mail de respuesta a la inscripción y verifique que no hubo un error. Si es así repita el proceso.

algo2/main/2010.txt · Última modificación: 2010/06/10 16:10 por damian
 
Excepto donde se indique lo contrario, el contenido de esta wiki se autoriza bajo la siguiente licencia: CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Run by Debian Driven by DokuWiki