Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== 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.
  * {{:algo2:main:algoritmos_y_estructuras_de_datos_ii_2013.doc|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í.

/* ¿Incluso si no regularicé el laboratorio ? Incluso en ese caso. */
/* ¿Incluso si no regularicé el escrito ? Incluso en ese caso. */
 
===== Evaluaciones =====

==== Parciales ====

    * Primer {{:algo2:main:2014.04.23.p1.pdf|parcial}}, 23/04/2014.
    * Segundo {{:algo2:main:2014.06.18.p2.pdf|parcial}}, 18/06/2014.
    * {{:algo2:main:r1.2014.06.25.pdf|Primer}} y {{:algo2:main:r2.2014.06.25.pdf|segundo}} recuperatorios, 25/06/2014.
==== Finales ====


===== Teórico =====

==== Horarios ====

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

==== Bibliografía ====

    * Notas de Algoritmos y Estructuras de Datos II.
          * {{:algo2:main:01.analisis.pdf|}}
          * {{:algo2:main:02.tiposconcretos.pdf|}}
          * {{:algo2:main:03.tiposabstractos.pdf|}}
          * {{:algo2:main:04.implementacioneselementales.pdf|}}
          * {{:algo2:main:05.listasenlazadas.pdf|}}
          * {{:algo2:main:06.arbolesbinarios.pdf|}}
          * {{:algo2:main:07.tecnicasavanzadas.pdf|}}
          * {{:algo2:main:08.dfs.pdf|}}
 
    * 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, {{http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/apunte/main.pdf|Cálculo de Programas}}.

    * Tutoriales de lenguaje C
          * {{algo2:cursc.html | En castellano pero básico}}
          * [[http://www.cs.cf.ac.uk/Dave/C/ | En ingles pero muy completo]]
          * [[http://www.gnu.org/software/gnu-c-manual/gnu-c-manual.html|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
          * {{algo2:main:cookoopvsadt90.pdf|Object-Oriented Programming Versus Abstract Data Types}}

==== Clases ====

          * Primera parte: Análisis de Algoritmos.
              * 10/03/14: Introducción a la materia, análisis de algoritmos (motivación), problema del bibliotecario, ordenación por selección, número de comparaciones, conteo de operaciones, número de intercambios. {{:algo2:main:01.ordenacion_seleccion.pdf|}}
              * 12/03/14: Repaso. Ordenación por inserción, análisis, mejor caso, peor caso y caso medio. {{:algo2:main:01b.ordenacion_insercion.pdf|}}. Ordenación por intercalación. {{:algo2:main:02.ordenacion_intercalacion_filminas.pdf|}}
              * 17/03/14: Análisis de la ordenación por intercalación. Ordenación rápida. {{:algo2:main:03.ordenacion_rapida_filminas.pdf|}}. Ordenación en el sitio {{http://www.sorting-algorithms.com/}}.
              * 19/03/14: Notación O, Omega y Theta. Propiedades elementales. Regla del límite. Jerarquía. Propiedades adicionales. {{:algo2:main:04.notacion_o.pdf|}}
              * 24/03/14: Feriado.
              * 26/03/14: Notación O, Omega y Theta. Propiedades. Jerarquía. Algoritmos divide y vencerás. Recurrencias divide y vencerás. {{:algo2:main:05.recurrencias_dyv.pdf|}}
              * 31/03/14: Recurrencias homogéneas y no homogéneas. {{:algo2:main:06.recurrencias_homogeneas_y_no.pdf|}}
          * Segunda parte: Estructuras de Datos.
              * 07/04/14: Tipos de datos. Tipos concretos y tipos abstractos. Tipos concretos: arreglos, listas, tuplas y punteros.{{:algo2:main:07_tipos.pdf|}}
              * 09/04/14: Tipos abstractos de datos. Paréntesis balanceados, {{:algo2:main:tadcontador.hs.pdf|TAD contador}} (grabá en tu disco y borrá la extensión .pdf). Delimitadores balanceados, {{:algo2:main:tadpila.hs.pdf|TAD pila}} (grabá en tu disco y borrá la extensión .pdf). {{:algo2:main:08.tads.pdf|}}
              * 14/04/14: Implementación del TAD contador. Listas enlazadas. Implementación del TAD pila usando listas enlazadas. {{:algo2:main:11.listas_enlazadas.pdf|}}
              * 16/04/14: Tipos abstractos de datos. Productor-consumidor. Buffer. {{:algo2:main:tadcola.hs.pdf|TAD cola}}. {{:algo2:main:09.tads.pdf|}}
              * 21/04/14: Tipos abstractos de datos. Implementaciones elementales (basadas en arreglos) de pila y cola. {{:algo2:main:10.implementaciones_elementales.pdf|}}
              * 23/04/14: Primer {{:algo2:main:2014.04.23.p1.pdf|parcial}}.
              * 28/04/14: Resolución del {{:algo2:main:1erparcial.pdf|parcial}}. {{:algo2:main:12.arboles_binarios.pdf|Árboles binarios}} y árboles {{:algo2:main:13.abb.pdf|binarios de búsqueda}}.
              * 30/04/14: Árboles binarios de búsqueda y heaps. {{:algo2:main:14.heap.pdf|}}
              * 05/05/14: Implementación de heap, cola de prioridades, heapsort. {{:algo2:main:14.heap.pdf|}}
          * Tercera parte: Algoritmos Avanzados.
              * 07/05/14: Algoritmos voraces. Forma general. Problema de la moneda. Problema de la mochila. {{:algo2:main: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. {{:algo2:main:16.voraz.pdf|}} 
              * 14/05/14: Algoritmos voraces. Problema del camino de costo mínimo. Algoritmo de Dijkstra. {{:algo2:main: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. {{:algo2:main: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. {{:algo2:main: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. {{:algo2:main: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. {{:algo2:main:21.dfs.pdf|}}
              * 04/06/14: Backtracking es DFS en un grafo implícito. El problema de n reinas, {{:algo2:main:reinas.hs.gz|(n reinas en Haskell)}}. {{:algo2:main:22.8reinas.pdf|}}
              * 09/06/14: Repaso de algoritmos voraces {{:algo2:main:23.combustible.pdf|}}.
              * 11/06/14: Repaso de backtracking {{:algo2:main:reinas.c.gz|(8 reinas en c)}}.
              * 16/06/14: Repaso de backtracking y programación dinámica.

==== Vínculos interesantes ====

    * Algoritmos de ordenación.
          * {{http://en.wikipedia.org/wiki/Sorting_algorithms | en wikipedia}}
          * Algunos visualizadores
                 * [[http://www.sorting-algorithms.com/]]
                 * [[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
                 * [[http://www.youtube.com/watch?v=XaqR3G_NVoo|Ordenación por intercalación]]
                 * [[http://www.youtube.com/watch?v=kDgvnbUIqT4|Ordenación rápida]]
    * Notación //O//
          * {{http://en.wikipedia.org/wiki/O_notation | en wikipedia}}
          * Visualizador
                 * {{http://rechneronline.de/function-graphs/}}
    * TADs
          * Algunos visualizadores
                 * Pilas y colas {{http://www.cs.usfca.edu/~galles/visualization/download.html}}
                 * Árboles binarios {{http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm|AVL}}


===== Práctico =====


==== Horarios ====

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

==== Guías de ejercicios ====

     * Práctico 1: Análisis de algoritmos {{:algo2:main:practico1.1.pdf|Parte 1}} y {{:algo2:main:practico1.2.pdf|Parte 2}}
     * Práctico 2: Estructuras de datos {{:algo2:main:practico2.pdf|}}
     * Práctico 3: Tipos abstractos de datos - Árboles {{:algo2:main:2013:practico3.pdf|Práctico 3}} 
     * Práctico 4: Algoritmos voraces. {{:algo2:main:2013:practico4.pdf|Práctico 4}}
     * Práctico 5: Backtracking, programación dinámica y recorrido de grafos. {{:algo2:main:2013:practico5.pdf|Práctico 5}}
==== 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 ====
{{:algo2:main:2014:pointersintro.odp|Intro a punteros - slides}}

{{:algo2:main:2014:pointers-tads-in-c.pdf|Punteros - slides}}

{{:algo2:main:2014:tads.pdf|Intro a TADs}}

{{:algo2:main:2014:gdb.pdf|GDB - slides}}

{{:algo2:main:2014:make.pdf|Makefile - slides}}
==== Proyectos ====

  * Proyecto 1: Algoritmos de Ordenación
    * {{:algo2:main:2014:proyecto01.pdf|Enunciado}}
    * {{:algo2:main:2014:sorting-skeleton_1.1_2014-03-15.tar.gz|Esqueleto de código}}
  * Proyecto 2: Tipos Abstractos de Datos, Diccionarios y Listas enlazadas
    * {{:algo2:main:2014:proyecto02-dict.pdf|Enunciado parte A}}, implementación del TAD dict y main.c
    * {{:algo2:main:2014:proyecto02-list.pdf|Enunciado parte B}}, implementación de los TAD list y pair
    * {{:algo2:main:2014:dictionary-skeleton-amd64_1.2_2014-04-14.tar.gz|Esqueleto de código para x86_64/amd64}} (NUEVO!!! subido el 2014-04-14)
    * {{:algo2:main:2014:dictionary-skeleton-i386_1.2_2014-04-14.tar.gz|Esqueleto de código para i386}} (NUEVO!!! subido el 2014-04-14)
  * Proyecto 3: Tipos Abstractos de Datos, Árboles Binarios de Búsqueda
    * {{:algo2:main:2014:proyecto03.pdf|Enunciado}} (no hay esqueleto para este proyecto)
  * Proyecto 4: Kruskal, el algoritmos para generar grafos de costo mínimo
    * {{:algo2:main:2014:proyecto04.pdf|Enunciado}}
    * {{:algo2:main:2014:kruskal-skeleton_1.0_2014-05-11.tar.gz|Esqueleto de código para i386 y x86_64}} (los .o para cada arquitectura están adentro de carpetas i386/ y x86_64/)

==== Cómo correr los tests en sus compus ====

Cómo correr los tests de unidad de los proyectos: ver detalle en [[run-tests-proy2-a|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á:

{{:algo2:main:2014:ayed2-group.png}}

===== 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