Algoritmos y Estructuras de Datos II

• Notas del tercer parcial.

• 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, Damian Barsotti, Martín Domínguez.

• Ayudantes: Santiago Bruno, Carlos de la Torre, Jorge Venzon, Luis Ferrer Fioriti, Tomás Cohen, Diego Lis.

• Lista de Mail: alualgo2@hal.famaf.unc.edu.ar (instrucciones para inscribirse).

• Pagina Web: http://hal.famaf.unc.edu.ar/~ayed2.

• 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.

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.

• 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, Cálculo de Programas.

• Tutoriales de lenguaje C
  • En castellano pero básico
  • En ingles pero muy completo
  • Manual de referencia en inglés

• 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.

• Este es el práctico completo de la materia ejercicios_2006.pdf

• 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.

• Los proyectos se evaluarán de forma individual aunque su realización haya sido grupal.

• 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.

• Proyecto 1 (Algoritmo de la División).

• Proyecto 2 (TAD Arreglo de Enteros).

• Proyecto 3 (Algorítmos de Ordenación).

• Proyecto 4 (Diccionario con Arreglos), librería cinta de lectura y escritura, headers, fuentes de la cinta.

• Proyecto 5 (Diccionario con Hash).

• Proyecto 6 (Diccionario sobre ABB).

:algo2:notas_finales_taller.pdf

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.

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.