====== Algoritmos y Estructuras de Datos II ====== ===== Generalidades ===== ==== Docentes ==== * Teóricos: Daniel Fridlender. * Prácticos: Silvia Pelozo. * Ayudantes: Felipe Espósito, Emmanuel Gunther. * Laboratorio: Natalia Bidart, Matías Bordese, Diego Dubois y Leonardo Rodríguez. * Ayudantes: David Arch, Maximiliano Bustos y Leandro Ramos. ==== 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, enuncian los proyectos y atienden consultas. Los jueves también se atienden consultas. ==== Régimen de aprobación, promoción y regularidad ==== * Parciales: 3. * Fechas preliminares: {{:algo2:main:2012.04.16.p1.pdf|16/4/2012}}, {{:algo2:main:2012.05.14.p2.pdf|14/5/2012}} y {{:algo2:main:2012.06.21.p3.pdf|21/6/2012}}. * Recuperatorio: el jueves 7/6/2012 de 14 a 18hs quienes no hayan aprobado el primer o segundo parcial tendrán la opción de recuperar. Quienes no hayan aprobado ninguno de los dos deberán elegir cuál recuperan. El recuperatorio no cuenta para la promoción. * Proyectos del laboratorio: 4. * Promoción: aprobando cada parcial con 6 o más, con promedio de 7 o más, y aprobando cada proyecto del laboratorio con 7 o más. * Regularidad: aprobando dos parciales + aprobando cada proyecto del laboratorio (con 4 o más). * Examen: examen escrito + resolución de problemas frente a la computadora (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 2012. ==== Preguntas frecuentes ==== * 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é rendir un examen de laboratorio con ejercicios adicionales? * Sí, porque vas a rendir como alumno libre. * Si apruebo los proyectos del laboratorio pero no alcanzo a aprobar los parciales, ¿deberé resolver ejercicios adicionales en el examen escrito? * 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. * Saqué 7 o más en los tres parciales pero no en los proyectos del laboratorio. ¿Debo rendir el escrito también? * En las mesas de julio-agosto 2012, no. Después de esas mesas, sí. * Saqué 7 o más en los proyectos del laboratorio pero no en los parciales. ¿Debo rendir el laboratorio también? * En las mesas de julio-agosto 2012, no. Después de esas mesas, sí. ===== 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:2012parte1.pdf|Primera parte}}: Análisis de Algoritmos. * Segunda parte: Estructuras de Datos. * {{:algo2:main:2012parte2-01-tiposconcretos.pdf|Tipos concretos.}} * {{:algo2:main:2012parte2-02-tiposabstractos.pdf|Tipos abstractos de datos.}} TADs [[algo2:main:2012:contador|Contador]], [[algo2:main:2012:pila|Pila]] y [[algo2:main:2012:cola|Cola]] en Haskell. * {{:algo2:main:2012parte2-03-tads-implementacioneselementales.pdf|Implementaciones elementales.}} * {{:2012parte2-04-listasenlazadas.pdf|Listas enlazadas}} con su {{:algo2:main:2012parte2-04bis-listasenlazadas.pdf|addenda.}} * {{:algo2:main:2012parte2-05-arbolesbinarios.pdf|Árboles binarios.}} * Tercera parte: {{:algo2:main:2012parte3.pdf|Algoritmos Avanzados}}, {{:algo2:main:2012recorrida.pdf|Recorrida de grafos.}} * 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. * Lunes 12 de marzo: presentación de la materia, introducción, distinción entre qué hace un algoritmo y cómo lo hace. Motivación: problema del bibliotecario. Ordenación por selección. Demos visuales. Procedimiento selection_sort en pseudo-código. Diseño top-down, procedimiento swap, función min_pos_from. Beneficio de usar swap. Análisis del algoritmo, elección de operación elemental, conteo. Aplicación al problema del bibliotecario. Método de conteo de operaciones de un algoritmo. * Miércoles 14 de marzo: Repaso. Conteo mecánico de comparaciones del selection_sort. Procedimiento insertion_sort en pseudo-código. Procedimiento insert. Análisis del algoritmo. Peor y mejor caso. Caso medio. Demos visuales. * Lunes 19 de marzo: Repaso, número de comparaciones de la ordenación por selección y por inserción. Notación O, Omega y Theta. Propiedades elementales. Equivalencias. Regla del límite, enunciado y demostración. * Miércoles 21 de marzo: Repaso, regla del límite. Jerarquía de funciones según su orden de crecimiento. Terminología. * Lunes 26 de marzo: Problema del bibliotecario. Ordenación por intercalación. Ordenación rápida. * Miércoles 28 de marzo: Orden de la ordenación por intercalación. Recurrencias divide y vencerás. Búsqueda lineal y búsqueda binaria. * Lunes 2 de abril: Feriado. * Miércoles 4 de abril: Recurrencias homogéneas y no homogéneas. * Lunes 9 de abril: Repaso de análisis y recurrencias. * Segunda parte: Estructuras de Datos. * Miércoles 11 de abril: Tipos de datos. Tipos concretos. * Lunes 16 de abril: Primer parcial. * Miércoles 18 de abril: Tipos abstractos. Paréntesis balanceados, TAD contador. Paréntesis, corchetes, llaves, etc, TAD pila. * Lunes 23 de abril: Implementaciones del TAD pila: listas, listas enlazadas, arreglos. Eficiencia. * Miércoles 25 de abril: TAD cola, especificación e implementación. * Lunes 30 de abril: Feriado * Miércoles 2 de mayo: Implementación de colas con listas enlazadas, listas circulares, arreglos circulares. * Lunes 7 de mayo: Cola de prioridades. Implementación con listas enlazadas circulares. Árboles binarios. Implementación con punteros. * Miércoles 9 de mayo: Árboles binarios de búsqueda y heaps. * Lunes 14 de mayo: Segundo parcial. * Tercera parte: Algoritmos Avanzados. * Miércoles 16 de mayo: Implementación de cola de prioridades usando heaps. Heapsort. Algoritmos voraces. Algoritmo de Kruskal. * Lunes 28 de mayo: Problema union-find. Algoritmo de Prim. Forma general de los algoritmos voraces. * Miércoles 30 de mayo: Algoritmo de Dijkstra. Problema de la moneda. Problema de la mochila. * Lunes 4 de junio: Divide y vencerás (ya vimos). Backtracking. Problema de la moneda. Problema de la mochila. Problema de los caminos mńimos. * Miércoles 6 de junio: Programación dinámica. Fibonacci. Problema de la moneda. Problema de la mochila. Algoritmo de Floyd. * Lunes 11 de junio: Recorrida de árboles y grafos. DFS. * Miércoles 13 de junio: DFS, BFS y últimas palabras sobre backtracking. ==== Vínculos interesantes ==== * Algoritmos de ordenación. * {{http://en.wikipedia.org/wiki/Sorting_algorithms | en wikipedia}} * Algunos visualizadores * {{http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html}} * {{http://math.hws.edu/TMCM/java/xSortLab/}} * {{http://thomas.baudel.name/Visualisation/VisuTri/}} * 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 ==== {{:algo2:main:2012:practico1.pdf|Práctico 1}} {{:algo2:main:2012:practico1_2.pdf|Práctico 1 (segunda parte)}} {{:algo2:main:2012:practico2.1.pdf|Práctico 2 (primera parte)}} {{:algo2:main:2012:practico2.2.pdf|Práctico 2 (segunda parte)}} {{:algo2:main:2012:practico3.1.pdf|Práctico 3}} ==== Notas de parciales ==== En [[http://famaf.guarani.unc.edu.ar/|Guarani]] (hasta primer segundo parcial recuperatorio). ===== Laboratorio ===== Los grupos serán de 2 (dos) personas. Mínimo 2, máximo 2. O sea, 2 :-). El listado completo de grupos y mapeo a profes encargados es: [[algo2:main:2012:grupos|grupos del lab]]. ==== Horarios ==== * Martes 14 a 18 hs: Teórico del taller y 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:2012:pointers-tads-in-c.pdf | Teórico de TADs, punteros y manejo de memoria en C}} * {{:algo2:main:2012:make.pdf | Filminas de la charla de make}} * {{:algo2:main:gdb2012.pdf | Filminas GDB}} ==== Proyectos ==== * Proyecto 1: Ordenación, algoritmos elementales. * {{:algo2:main:2012:proy01.pdf|Enunciado del proyecto 1}} * [[ http://ubuntuone.com/7OKYbqIUnydMIKgTCFmfDv| Esqueleto del código a completar (versión nueva 0.99.1) ]] * Proyecto 1.b: Ordenación, algoritmos avanzados. * {{:algo2:main:2012:proy01b-latest.pdf|Enunciado del proyecto 1.b}} * {{:algo2:main:2012:input-files-100-1000-10000.tar.gz|Archivos de entrada para realizar la tabla comparativa}} * Proyecto 2: Tipos Abstractos de Datos. * {{:algo2:main:2012:proyecto2.pdf|Enunciado del proyecto 2}} * {{:algo2:main:2012:dictionary-skeleton-amd64_0.99.1_2012-04-17.tar.gz | Esqueleto del código a extender (para arquitecturas de 64 bits)}} * {{:algo2:main:2012:dictionary-skeleton-i386_0.99.1_2012-04-17.tar.gz | Esqueleto del código a extender (para arquitecturas de 32 bits)}} * {{:algo2:main:2012:dictionary-skeleton-mac_0.99.1_2012-04-17.tar.gz | Esqueleto del código a extender (para Mac)}} * Proyecto 2b: Listas Enlazadas. * {{:algo2:main:2012:proyecto2b.pdf|Enunciado del proyecto 2.b}} * Proyecto 3: Árboles Binarios de Búsqueda. * {{:algo2:main:2012:proyecto3.pdf|Enunciado del proyecto 3}} * Proyecto 4: Algoritmo de Kruskal. * {{:algo2:main:2012:proyecto4.pdf|Enunciado del proyecto 4}} (Versión actualizada al 5 de Junio de 2012) * {{:algo2:main:2012:kruskal-skeleton_0.99.1_2012-06-05.tar.gz | Esqueleto del código a extender (para todas las arquitecturas, incluye los .h del enunciado)}} ===== Instrucciones para inscribirse en la lista de mails ===== Desde el [[http://webmail.famaf.unc.edu.ar/src/login.php|webmail del FaMAF]] enviar un mail a: alualgo2-join@famaf.unc.edu.ar con cualquier subject o cuerpo del mail. Después de enviarlo debe llegar un mail con un link a una página donde donde se deben llenar los datos personales. Todo esto hay que hacerlo desde el [[http://webmail.famaf.unc.edu.ar/|webmail del FaMAF]]. ===== Instrucciones para mandar un mail en la lista de mails ===== Desde el [[http://webmail.famaf.unc.edu.ar/src/login.php|webmail del FaMAF]] enviar un mail a: alualgo2@famaf.unc.edu.ar Tener en cuenta que todos los alumnos y todos los profes reciben los mails de esta lista. === ¡¡ Tener en cuenta !! === Si se cometió 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. Cualquier problema consultar con los administradores del laboratorio.