====== Algoritmos y Estructuras de Datos II ====== * {{3erparcial.pdf | Notas del tercer parcial}}. * {{regulares.pdf | Alumnos regulares}}. Son los que aprobaron al menos dos parciales y el taller (en el 2004, 2005 o 2006). * Profesores: Daniel Fridlender, Juan Durán, Alejandro Tiraboschi, [[http://www.cs.famaf.unc.edu.ar/~damian|Damian Barsotti]], Martín Domínguez. * Ayudantes: Santiago Bruno, [[http://www.carlosmatias.com.ar|Carlos de la Torre]], Jorge Venzon, Luis Ferrer Fioriti, Tomás Cohen, Diego Lis. * Lista de Mail: alualgo2@hal.famaf.unc.edu.ar ([[main#instrucciones_para_inscribirse_en_la_lista_de_mails|instrucciones para inscribirse]]). * Pagina Web: http://hal.famaf.unc.edu.ar/~ayed2. ===== Generalidades ===== * Parciales: 3 (primero: 11/4; segundo: 30/5; tercero: 20/6). * 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. == Para alumnos de años anteriores== Quienes aprobaron el taller en el 2004 o 2005 podrán regularizar aprobando 2 parciales y presentando la libreta donde conste la aprobación del taller **AL MOMENTO DE RENDIR LOS PARCIALES**. Asimismo, quienes regularizaron en el 2004 o 2005 podrán rendir el examen sin ejercicios adicionales si aprueban el taller este año. ===== Teórico ===== ==== Bibliografía ==== * {{algoritmos2.pdf | Notas de Algoritmos y Estructuras de Datos II}}. * Brassard and Bratley, Fundamentals of Algoritmics. * Manber, Introduction to Algorithmics: A Creative Approach. * Bibliografía Complementaria * 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://hal.famaf.unc.edu.ar/tutorial_C/www.phim.unibe.ch/comp_doc/c_manual/C/cref.html|Manual de referencia en inglés]] ==== Clases ==== * martes 7/3: Introducción. Ordenación por selección. * jueves 9/3: Análisis de la ordenación por selección. Ordenación por inserción. Análisis. Comparación. Mejor caso, peor caso, caso promedio. Significado. Operación elemental. Aproximación. * martes 14/3: Notación //O//: motivación, definición, propiedades básicas, regla del límite, jerarquía de funciones según su ritmo de crecimiento. * jueves 16/3: Propiedades auxiliares de //O//. Definiciones auxiliares: Omega, Theta. Ejemplos: búsqueda lineal, búsqueda lineal ordenada, búsqueda binaria. Análisis. Notación auxiliar //O(f(n)|P(n)//, //Omega(f(n)|P(n)//, //Theta(f(n)|P(n)//. Crecimiento del logaritmo. * martes 21/3: Función eventualmente no decreciente, i-suave, suave. Equivalencia entre i-suave y suave. Regla de suavidad. Ejemplo: búsqueda binaria. Recurrencias divide y vencerás. Método de resolución. Ejemplo: búsqueda binaria. Ordenación rápida. * jueves 23/3: Recurrencias homogéneas. Método de resolución. Ejemplos. * martes 28/3: * jueves 30/3: Recurrencias no homogéneas. Método de resolución. Ejemplo. * martes 4/4: Estructuras de datos. Tipos concretos: arreglos, listas, tuplas, punteros. * jueves 6/4: * martes 11/4: primer parcial. * martes 18/4: Tipos abstractos. Notación semi-formal. Listas. Pilas. Control de paréntesis balanceados. Colas. * jueves 20/4: * martes 25/4: Implementación de pilas y colas utilizando arreglos. Implementación de pilas utilizando listas enlazadas. * jueves 27/4: Implementación de colas utilizando listas enlazadas. Listas con puntero al primero y al último nodos. Listas circulares. Árboles. Árboles binarios. * martes 2/5: Árboles binarios de búsqueda. Implementación. * jueves 4/5: Colas de prioridades. Heap. * martes 9/5: Implementación de heap. Algoritmos divide y vencerás. Forma general. Repaso de ordenación rápida y búsqueda binaria. * jueves 11/5: Ordenación por interacalación. Exponenciación. Multiplicación de números grandes. * martes 16/5: Algoritmos voraces. Forma general. Problema de la moneda. Problema de la mochila. Camino de costo mínimo. Algoritmo de Dijkstra. * jueves 18/5: Nodos especiales. Caminos especiales. Invariante del algoritmo de Dijkstra. Correctitud. Árboles generadores de costo mínimo. Criterios de elección de nuevas aristas. Algoritmo de Prim. Algoritmo de Kruskal. * martes 30/5: segundo parcial. * jueves 1/6: Problema Union-Find. Programación dinámica. Número de Fibonacci. Problema de la moneda. * martes 6/6: Problema de la mochila. Algoritmo de Floyd. * jueves 8/6: Recorrida de grafos. Árboles binarios: pre-orden, in-orden, pos-orden (derecha a izquierda e izquierda a derecha). Árboles finitarios: pre-orden y pos-orden. Precondicionamiento. Grafos: DFS recursivo e iterativo, BFS. * martes 13/6: Backtracking. Problema de la mochila. 8 reinas. ===== Practico ===== * Este es el práctico completo de la materia {{algo2:ejercicios_2006.pdf}} ===== Taller ===== ==== Modalidad ==== === Generalidades === * Los teóricos del taller se dictan los jueves de 17 hs. a 18 hs. despues del práctico (en la misma aula). * El laboratorio del taller se reliza en dos comisiones. Los horarios de ellas son: viernes de 9 hs a 13 hs y de 14 a 18 hs el mismo día. Cada alumnos debe inscribirse en una. * El taller consiste en la realización de una serie de proyectos. * Los contenidos necesarios para su realización serán impartidos en los teóricos del taller. * Los proyectos podrán ser consultados en los laboratorios del taller. * La realización de los mismos es grupal. Los grupos permanecen fijos para todos los proyectos. * Cada grupo tendrá un ayudante asignado. Los ayudantes harán un seguimiento de los proyectos. === Criterios generales para la corrección de proyectos === * Los proyectos se evaluarán de forma individual aunque su realización haya sido grupal. * FIXME ==== Clases ==== * 9/3: Sinónimo de tipos y estructuras en C. Presentación proyecto 1. * 16/3: TAD en C. Memoria dinámica. Librería assert. Pasaje de parámetros de tipo estructura. Presentación de proyecto 2. * 23/3: Consulta sobre proyectos 2. * 29/3: Repaso de punteros. Implementación de TAD con punteros a estructuras. * 6/4: Paro. * 7/4: Presentación en laboratorio de proyecto 3. * 13/4: Semana Santa. * 20/4: Paro. * 27/4: Presentación en laboratorio de proyecto 4. * 4/5: Cinta de lectura de listas enlasadas. * 11/5: Cinta de lectura/escritura de listas enlasadas. * 18/5: Hash abierto. Presentación de proyecto 5. * 25/5: Feriado. * 1/6: Archivos. Presentación de proyecto 6. * 8/6: Librerias en C. Librerias estáticas. ==== Proyectos ==== * {{algo2:proy1.pdf | Proyecto 1 (Algoritmo de la División)}}. * {{algo2:proy2.pdf | Proyecto 2 (TAD Arreglo de Enteros)}}. * {{algo2:proy3.pdf | Proyecto 3 (Algorítmos de Ordenación)}}. * {{algo2:proy4.pdf | Proyecto 4 (Diccionario con Arreglos)}}, {{algo2:libcrw.tgz | librería cinta de lectura y escritura}}, {{algo2:headers_p04.tgz | headers}}, {{algo2:crw.tgz | fuentes de la cinta}}. * {{algo2:proy5.pdf | Proyecto 5 (Diccionario con Hash)}}. * {{:algo2:proy6.pdf| Proyecto 6 (Diccionario sobre ABB)}}. ==== Notas Finales ==== {{:algo2:notas_finales_taller.pdf|:algo2:notas_finales_taller.pdf}} ===== Instrucciones para inscribirse en la lista de mails ===== Enviar un mail a: minimalist@hal.famaf.unc.edu.ar con el subject: subscribe alualgo2 El cuerpo del mail se puede dejar en blanco. Despues de enviarlo debe llegar un mail donde diga que la subscripcion fue realizada correctamente. === !! 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.