====== Algoritmos y Estructuras de Datos II ====== ==== Novedades ==== * A partir de hoy (29/05/2017) el lab de Algoritmos 2 es sólo los martes. Los jueves está disponible el aula de laboratorio y hay una guardia mínima de docentes (1 docente de 14 a 16hs y 1 ó 2 ayudantes alumno de 14 a 18hs) para atender consultas. * El 2do parcial será el dia 19/6 (lab día jueves 22/6) * El recuperatorio será el día 26/6 (lab día 27/6) ===== Generalidades ===== ==== Docentes ==== * Teóricos: Daniel Fridlender. * Prácticos: Alejandro Gadea, Emmanuel Gunther y Demetrio Vilela. * Laboratorio: Sergio Canchi, Diego Lis, Gonzalo Peralta, Jorge Rafael y Leandro Ramos. * Ayudantes: Elian Bravin, Guillermo Incatasciato e Illak Zapata. ==== Horarios ==== * Teóricos: lunes y miércoles de 14 a 16hs, en el aula 17. * Prácticos: lunes y miércoles de 16 a 18hs, en el aula 17. * Laboratorio: martes y jueves de 14 a 18hs, en el aula 28 (lab). Algunos alumnos tendrán lab los martes y otros los jueves. Dependiendo del número de alumnos y el espacio se podrá cambiar esta organización durante la marcha del cuatrimestre. ==== Objetivos ==== 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, * 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. ==== 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. * En {{:algo2:main:algoritmos_y_estructuras_de_datos_ii_2015.doc|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. ==== Régimen de aprobación, promoción y regularidad ==== * Parciales: 2. * Fechas: 03-04/05/2017 y {{ :algo2:main:2017.13.parcial2.pdf |19-22/06/2017}}. * Recuperatorio: 26-27/06/2017. El recuperatorio no cuenta para la promoción. * Laboratorio: ejercicios y proyecto. * Fechas preliminares de evaluación de proyectos: aún no determinadas. * Regularidad: aprobando dos parciales (eventualmente recuperando uno de ellos) + aprobando al menos el 60 por ciento de los ejercicios y/o proyectos del laboratorio. * 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, normalmente 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 2017, ú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 2016, 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 2016, no. Después de esas mesas, sí. ===== Evaluaciones ===== ==== Parciales ==== /* * {{:algo2:main:p1.2016.05.02.pdf|2/05/2016}}. * {{:algo2:main:p2.2016.06.15.pdf|15/06/2016}}. * Primer y segundo recuperatorios, 22/06/2016. */ ==== Finales ==== ====== Clases ====== /* * {{:algo2:main:algoritmos2.2017.semana01.tgz|Semana 01}} : ordenación por selección y por inserción. */ ===== Teórico ===== ==== Horarios ==== Lunes y miércoles de 14 a 16hs, en el aula 17. ==== Bibliografía ==== * Notas de Algoritmos y Estructuras de Datos II. * Buscar en la wiki de años anteriores. * 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. * {{:algo2:main:2017.01.ordenacion.elemental.imprimible.pdf|Primera semana.}} Ordenación elemental: ordenación por selección y ordenación por inserción. * {{:algo2:main:2017.02.ordenacion.avanzada.imprimible.pdf|Segunda semana.}} Ordenación avanzada: ordenación por intercalación y ordenación rápida. * {{:algo2:main:2017.03.recurrenciasdyv.y.jerarquia.imprimible.pdf|Tercera semana.}} Recurrencias divide y vencerás. Jerarquía de funciones según su ritmo de crecimiento. * Segunda parte: Estructuras de Datos. * {{:algo2:main:2017.04.tipos.imprimible.pdf|Cuarta semana.}} Tipos concretos. Tipos abstractos de datos. Paréntesis balanceados y el TAD Contador. Especificación y prototipo. Delimitadores balanceados y el TAD Pila. * {{:algo2:main:2017.05.impl.contador.esp.colas.imprimible.pdf|Quinta semana.}} Implementación del TAD contador. Productor-consumidor y el TAD Cola. Ordenación por selección y el TAD PCola (cola de prioridades). * {{:algo2:main:2017.06.implementaciones.de.tads.arboles.binarios.imprimible.pdf|Sexta semana.}} Implementaciones de pilas y colas utilizando listas, arreglos y listas enlazadas. Árboles binarios. * {{:algo2:main:2017.07.abb.heap.imprimible.pdf|Séptima semana.}} Árboles binarios de búsqueda, heaps. * Octava semana: parcial. * Tercera parte: Algoritmos Avanzados. * {{:algo2:main:2017.09.voraz.imprimible.pdf|Novena semana.}} Algoritmos voraces. * {{:algo2:main:2017.10.backtracking.imprimible.pdf|Décima semana.}} Bactracking. * {{:algo2:main:2017.11.programacion.dinamica.imprimible.pdf|Undécima semana.}} Programación dinámica. * {{:algo2:main:2017.12.dfs.imprimible.pdf|Duodécima semana.}} Recorrida de grafos. /* * 9-5-16: {{:algo2:main:15.voraz.pdf|}} Algoritmos voraces. Características. Forma general. Problema de la moneda. Problema de la mochila. Problema del árbol generador de costo mínimo. * 11-5-16: {{:algo2:main:16.voraz.pdf|}} Árbol generador de costo mínimo. Algoritmo de Prim. Algoritmo de Kruskal. Problema Union-Find. * 16-5-16: {{:algo2:main:17.dijkstra.pdf|}} Problema del camino de costo mínimo. Algoritmo de Dijkstra. Orden de los algoritmos voraces sobre grafos. * 18-5-16: {{:algo2:main:18.backtracking.pdf|}} Backtracking. Solución general al problema de la moneda. Solución general al problema de la mochila. Problema de los caminos de costo mínimo. * 23-5-16: {{:algo2:main:19.grafo_implicito.pdf|}} Grafo implícito en los algoritmos de backtracking. Ejemplo: problema de la moneda. * 25-5-16: feriado * 30-5-16: {{:algo2:main:20.programacion_dinamica.pdf|}} Programación dinámica. Fibonacci, problema de la moneda, problema de la mochila. * 1-6-16: {{:algo2:main:21.programacion_dinamica.pdf|}} Programación dinámica. Problema del camino de costo mínimo. * 6-6-16: {{:algo2:main:22.dfs.pdf|}} Recorrida de árboles binarios. Pre-orden, in-orden y pos-orden. Recorrida de árboles finitarios. Recorrida de grafos. DFS iterativo. BFS. * 8-6-16: {{:algo2:main:23.8reinas.pdf|}} Backtracking. Grafos implícitos. 8 reinas. n reinas. */ /* * 06/05/15: Algoritmos voraces. Forma general. Problema de la moneda. Problema de la mochila. {{:algo2:main: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. {{:algo2:main:16.voraz.pdf|}} * 13/05/15: Algoritmos voraces. Problema del camino de costo mínimo. Algoritmo de Dijkstra. {{:algo2:main:17.dijkstra.pdf|}}. * 18/05/15: Backtracking. Problema de la moneda, simplificación, generalización, variantes. {{:algo2:main:moneda.tgz|}} Problema de la mochila. Problema de los caminos de costo mínimo. {{:algo2:main:caminos.tgz|}} {{:algo2:main:18.backtracking.pdf|}} * 20/05/15: Programación dinámica: Fibonacci, problema de la moneda, problema de la mochila. {{:algo2:main:19.programacion_dinamica.pdf|}}. {{:algo2:main:fibonacci.tgz|}} {{:algo2:main:moneda2.tgz|}} * 27/05/15: Programación dinámica: algoritmo de Floyd. {{:algo2:main:20.programacion_dinamica.pdf|}}. {{:algo2:main: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. {{:algo2:main:21.dfs.pdf|}} * 03/06/15: Backtracking y DFS. Problema de las 8 reinas. {{:algo2:main:22.8reinas.pdf|}}.{{:algo2:main:reinas.tgz|}} * 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://sorting.at/]] * [[http://www.sorting-algorithms.com/]] * [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html]] * [[http://math.hws.edu/TMCM/java/xSortLab/]] * 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 y miércoles de 16 a 18hs, en el aula 17. ==== Guías de ejercicios ==== * {{:algo2:main:2017.01.practico.pdf|Ejercicios primera semana.}} Ordenación elemental. * {{:algo2:main:2017.02.practico.pdf|Ejercicios segunda semana.}} Ordenación avanzada. * {{:algo2:main:2017.03.practico.pdf|Ejercicios tercera semana.}} Recurrencias y jerarquía. * {{:algo2:main:2017.04.practico.pdf|Ejercicios cuarta semana.}} Tipos concretos: arreglos, tuplas, punteros, listas. * {{:algo2:main:2017.05.practico.pdf|Ejercicios quinta semana.}} Especificación de tipos abstractos de datos. * {{:algo2:main:2017.06.practico.pdf|Ejercicios sexta semana.}} Implementación de tipos abstractos de datos. * {{:algo2:main:2017.07.practico.pdf|Ejercicios séptima semana.}} Árboles binarios, ABBs y heaps. * Octava semana: feriado y parcial. * {{:algo2:main:2017.09.practico.pdf|Ejercicios novena semana.}} Algoritmos voraces. * {{:algo2:main:2017.10.practico.pdf|Ejercicios décima semana.}} Backtracking. * {{:algo2:main:2017.11.practico.pdf|Ejercicios undécima semana.}} Programación dinámica. * {{:algo2:main:2017.12.practico.pdf|Ejercicios duodécima semana.}} DFS y BFS. /* * Práctico 1: Análisis de algoritmos {{:algo2:main:practico1.1.pdf|Parte 1}}, {{:algo2:main:practico1.2.pdf|Parte 2}} y {{:algo2:main:practico1.3.pdf|Parte 3}}. * Práctico 2: Estructuras de Datos {{:algo2:main:practico2.1.pdf|Parte 1}}, {{:algo2:main:practico2.2.pdf|Parte 2}} y {{:algo2:main:practico2.3.pdf|Parte 3}}. * Práctico 3: Algoritmos avanzados {{:algo2:main:practico3.1.pdf|Parte 1}}, {{:algo2:main:practico3.2.pdf|Parte 2}} y {{:algo2:main:practico3.3.pdf|Parte 3}}. */ /* * , {{:algo2:main:practico1.2.pdf|Parte 2}} y {{:algo2:main:practico1.3.pdf|Parte 3}}. * Práctico 2: Estructuras de datos {{:algo2:main:practico2.pdf|Parte 1}} y {{:algo2:main:practico2.2.pdf|Parte 2}}. * Práctico 3: Algoritmos avanzados {{:algo2:main:practico3.1.pdf|Parte 1, algoritmos voraces}}, {{:algo2:main:practico3.2.pdf|Parte 2, backtracking y programación dinámica}} y {{:algo2:main:practico3.3.pdf|DFS, BFS y backtracking.}} * 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). ==== Proyectos ==== * Los ejercicios de laboratorio se descargan ejecutando en linux el comando git clone https://gitlab.com/famaf-algo2/Algoritmos2.2017.git /* * Proyecto 1: Algoritmos de Ordenación * {{:algo2:main:presentacion-proy1-2016.pdf|Slides de Presentación}} * {{:algo2:main:enunciado-proyecto1-2016.pdf|Enunciado}} * {{:algo2:main:esqueleto-proyecto1-2016.tar.gz|Esqueleto de Código}} * Proyecto 2: Diccionario con Listas Enlazadas. * {{:algo2:main:esqueleto-proyecto2.tar.gz| Esqueleto de Código}} * {{:algo2:main:mac-proy2.tar.gz| Código objeto para MAC}} * {{:algo2:main:parche-esqueleto-proy2-v1.1.tar.gz| Parche Esqueleto - 1}} * {{{{:algo2:main:parche-esqueleto-proy2-2.tar.gz| Parche Esqueleto - 2}} * {{{{:algo2:main:enunciado-proy2.pdf| Enunciado}} * Proyecto 3: Map con Árboles Binarios de Búsqueda. * {{:algo2:main:enunciado-proy3-2016.pdf| Enunciado}} * Proyecto 4: Backtracking y Programación Dinámica - (Knapsack problem). * {{:algo2:main:esqueleto-proy4-2016.tar.gz| Esqueleto de Código}} * {{:algo2:main:enunciado-proy4-2016.pdf|Enunciado}} */ ==== Clases ==== /* * {{:algo2:main:informacion.pdf| Información del Lab}} * {{:algo2:main:punteros2016.odp| Punteros en C}} * {{:algo2:main:clase-punteros-tads.tar.gz| Códigos de Ejemplo, TADs, escrito en clase.}} * {{:algo2:main:2014:tads.pdf| Tutorial de TADs en C}} * {{:algo2:main:matricesdinamicas2016.odp|Matrices Dinámicas en C}} * {{:algo2:main:proy4-2016.odp|Knapsack, pseudocódigo Backtracking y Dinámica}} * {{:algo2:main:2014:make.pdf|Makefile - slides}} * {{:algo2:main:persona.tar.gz|Ejemplo Makefile + TAD Person}} */ /* * Repaso de arreglos, estructuras. {{:algo2:ejemplo-estructuras.tar.gz|Código de ejemplo}} * {{:algo2:main:2014:gdb.pdf|GDB - slides}} * {{:algo2:main:punteros2015.odp| Punteros (slides)}} * {{:algo2:main:2014:tads.pdf|Intro a TADs}} * {{:algo2:main:2014:make.pdf|Makefile - slides}} * {{:algo2:main:persona.tar.gz|Ejemplo Makefile + TAD Person}} ==== Sistema de Integración Continua ==== * [[http://jaime.famaf.unc.edu.ar/| Jaime]] */ /* {{: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}} ==== 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/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á: {{: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: ayed2-famaf@googlegroups.com