====== Algoritmos y Estructuras de Datos II ====== ==== Novedades ==== * 23/04/2019: enunciado del {{ :algo2:main:2019.parcial1.pdf |primer parcial}} en la wiki. ===== Generalidades ===== ==== Docentes ==== * Teóricos: Daniel Fridlender. * Prácticos: Romina Altamirano, Emmanuel Gunther y Alejandro Gadea. * Laboratorio: * Martes: Gonzalo Peralta, Leandro Ramos y Marco Rocchietti. * Jueves: Carlos Bederián, Sergio Canchi y Leonardo Rodríguez. ==== 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 o jueves de 14 a 18hs, en el aula 28 (lab). ==== 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 y describir 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: 22/04/2019 ({{ :algo2:main:2019.parcial1.pdf |primer parcial}}) y 10/06/2019 ({{ :algo2:main:2019.parcial2.pdf |segundo parcial}}). * Recuperatorios: 19/06/2019. * Laboratorio: ejercicios y proyecto. También tiene dos parciales. La aprobación del día a día a todo lo largo del cuatrimestre, aporta para la promoción. * Regularidad: aprobando dos parciales (eventualmente recuperando uno de ellos) + aprobando los parciales del laboratorio. * Promoción: aprobando cada parcial con 6 o más, con promedio total de 7 o más + aprobando los parciales del laboratorio con 6 o más. En los parciales del lab, para la promoción, se cuentan los resultados logrados durante las clases, en el día a día. * Examen final: evaluación por escrito de teórico-práctico + resolución de problemas frente a la computadora (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 2019, ú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 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 no se recomienda, puesto que deberás demostrar destreza durante el examen de laboratorio en la resolución de problemas similares a los resueltos durante el cursado del lab. * 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 (fines de junio o principios de julio de 2019) 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 2019, 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 2019, no. Después de esas mesas, sí. ===== Teórico ===== Lunes y miércoles de 14 a 16hs, en el aula 17. ==== Clases ==== * Primera parte: Análisis de Algoritmos. * Primera semana: {{ :algo2:main:2019.01.ordenacion.elemental.pdf |Ordenación elemental}} (ordenación por selección y ordenación por inserción). * Segunda semana: {{ :algo2:main:2019.02.ordenacion.avanzada.pdf | Ordenación avanzada}} (ordenación por intercalación y ordenación rápida). * Tercera semana: {{ :algo2:main:2019.03.recurrenciasdyv.y.jerarquia.pdf | Recurrencias y jerarquía de funciones}}. * Segunda parte: Estructuras de Datos. * Cuarta semana: {{ :algo2:main:2019.04.tipos.concretos.pdf | Tipos de datos.}} Tipos concretos. * Quinta semana: {{ :algo2:main:2019.05.tipos.abstractos.pdf | Tipos abstractos.}} {{ :algo2:main:tads.tgz |TAD Natural, Booleano, Contador, Pila.}} {{ :algo2:main:2019.05.especificaciones.colas.pdf | Tipos abstractos (2).}} {{ :algo2:main:tadcolas.tgz |TADs Cola y cola de prioridades}} * Sexta semana: {{ :algo2:main:tadeqcp.tgz |TADs Entero, Racional, Conjunto finito, Polinomio.}} {{ :algo2:main:2019.06.implementaciones.de.tads.pdf | Implementación de pilas y colas.}} * Séptima semana: {{ :algo2:main:2019.07.abb.pdf | Árboles binarios de búsqueda}} y {{ :algo2:main:2019.07.heap.pdf | heaps}}. {{ :algo2:main:tadarbol.tgz |TAD Arbol binario}}. * Tercera parte: Algoritmos Avanzados. * Octava semana: {{ :algo2:main:2019.08.voraz.pdf |Algoritmos voraces.}} * Novena semana: {{ :algo2:main:2019.09.backtracking.pdf |Backtracking.}} * Décima semana: {{ :algo2:main:2019.10.programacion.dinamica.pdf |Programación dinámica.}} * Undécima semana: {{ :algo2:main:2019.11.dfs.pdf | Recorrida de grafos.}} DFS y BFS. ==== 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}} ==== Vínculos interesantes ==== * Visualizador de ejecución de programas * [[http://pythontutor.com/visualize.html#mode=edit|Python tutor]] Permite visualizar la ejecución de programas en python, c, java entre otros lenguajes. * 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 * [[https://www.youtube.com/watch?v=Ns4TPTC8whw|Ordenación por selección]] * [[https://www.youtube.com/watch?v=ROalU379l3U|Ordenación por inserción]] * [[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 de funciones y su crecimiento * [[http://rechneronline.de/function-graphs/]] * TADs * [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html]] ===== Práctico ===== Lunes y miércoles de 16 a 18hs, en el aula 17. ==== Guías de ejercicios ==== * Primera parte: Análisis de Algoritmos. * {{ :algo2:main:2019.01.practico.pdf |Práctico 1.1.}} Ordenación elemental. * {{ :algo2:main:2019.02.practico.pdf |Práctico 1.2.}} Ordenación avanzada. * {{ :algo2:main:2019.03.practico.pdf |Práctico 1.3.}} Recurrencias y jerarquía de funciones. * Segunda parte: Estructuras de Datos. * {{ :algo2:main:2019.04.practico.pdf |Práctico 2.1.}} Tipos concretos. * {{ :algo2:main:2019.05.practico.pdf |Práctico 2.2.}} Tipos abstratos. * {{ :algo2:main:2019.06.practico.pdf |Práctico 2.3.}} Implementación de tipos abstractos. * {{ :algo2:main:2019.07.practico.pdf |Práctico 2.4.}} Árboles binarios. * Tercera parte: Algoritmos Avanzados. * {{ :algo2:main:2019.08.practico.pdf |Práctico 3.1.}} Algoritmos voraces. * {{ :algo2:main:2019.09.practico.pdf |Práctico 3.2.}} Backtracking. * {{ :algo2:main:2019.10.practico.pdf |Práctico 3.3.}} Programación dinámica. * {{ :algo2:main:2019.11.practico.pdf |Práctico 3.4.}} Recorrida de grafos. ===== Laboratorio ===== Los grupos serán de 2 (dos) personas. Mínimo 2, máximo 2. O sea, 2 :-). ==== Horarios ==== * Martes 14 a 18 hs. * Jueves 14 a 18 hs. Todas las clases son en el laboratorio de computación del 2do piso (aula 28). ==== Proyectos ==== ==== Clases de laboratorio ==== * {{ :algo2:main:lab1.tar.gz | Lectura de archivos en C - Manejo de arreglos}}. * {{ :algo2:main:lab01.tar.gz | Algoritmos de ordenación}}. * {{ :algo2:main:lab03.tar.gz | Punteros y estructuras en C}}. * {{ :algo2:main:lab4.tgz | Especificaciones de grafos y matrices en Haskell}}. * {{ :algo2:lab05-2019.tar.gz | TAD Stack - Listas enlazadas}}. * {{ :algo2:main:lab06.tar.gz | TAD Map - Árboles binarios de búsqueda}}. * {{ :algo2:main:lab07-2019.tar.gz | Knapsack Problem - Backtacking - Programación Dinámica }}, Bajar también {{ :algo2:main:lab07-2019-input-examples.tar.gz | Input}}. ===== Instrucciones para agregarse al grupo de correo ===== 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 "Accede para ver este grupo" (o "subscribe to this group", o similar). Por favor, además de la dirección de mail asegurarse de proporcionar su nombre y apellido. En caso contrario, no se accederá a la solicitud hasta tanto podamos identificarlo como alumno de la asignatura. 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. Una vez que solicitaron acceder al grupo, aguardar que llegue a su casilla de correo la aprobación de esa solicitud. ==== Instrucciones para mandar un mail a la lista de correo ==== Para mandar un mail a la lista de la materia, escribir a: ayed2-famaf@googlegroups.com