Algoritmos y Estructuras de Datos I - 2015 1er cuatrimestre

¡Bienvenido a la página de Algoritmos I!

Teórico/Práctico: Damián Barsotti, Javier Blanco, Demetrio Martín Vilela.

Laboratorio: Martín Domínguez, Juan Cruz Rodríguez.

Ayudantes: Daniel Bridera, Iliak Zapata.

Teórico/Practico: lunes y jueves de 14 a 18 hs, aula 25.

Laboratorio: miércoles de 9 a 18 hs., Lab. 30.

• Para regularizar la materia: 2 parciales aprobados con nota >= 4 o un recuperatorio equivalente y el taller aprobado.
• Para promocionar la materia: 2 parciales aprobados con nota >= 6, promedio >= 7.5 y el taller aprobado.
• Para rendir libre la materia: Ver Condiciones para rendir libre el taller.

Ver también Modalidad del taller.

Nota: El taller también se considerará aprobado si lo fue en el segundo cuatrimestre del año 2014.

Programación funcional:

• Digesto de axiomas y teoremas para cálculo proposicional y expresiones cuantificadas.
  • Anexo (axiomas y teoremas cuantificador de conteo).
• Digesto de funciones de listas y propiedades.
• Ejemplo de 1er parcial.

Programación imperativa:

• Digesto para la programación imperativa.
• Ejemplo de 2do parcial.

Acá pondremos los prácticos.

• Práctico 1 - Repaso cálculo proposicional y expresiones cuantificadas.

• |Práctico 2 - Especificación derivación y verificación de programas funcionales.

• Práctico 3 - Introducción a la programación imperativa.

• Práctico 4 - Programación imperativa.

• Notas primer parcial.
• Notas segundo parcial.
• Notas recuperatorio.
• Condición Final.
• Final 1.
• Final 3.

Ejemplos de programas en C:

• Proyecto 4 / Proyecto 5:
  • Código C: Hello, World!
  • Código C: Assignación múltiple
  • Código C: While
  • Código C: Mcd
  • Código C: Mcd con función

Enunciados y teóricos del año pasado:

• Código C: Collatz
• Introduccion a GDB. Por Marco Brunello y Leandro Ramos. Presentación, ejemplos.

Resumen de comandos de consola Linux y un libro sobre el tema.

Acá pondremos el calendario completo de la materia como esperamos darlo.

• 11/3: Presentación Proyecto 1 y auto-repaso linux
• 18/3: Teórico de Taller: Haskell, GHCI, secciones, map, filter.
• 25/3: Teórico de Taller: Tipos, clases de tipos y más.
• 1/4: Corrección Proyecto 1. Presentación Proyecto 2.
• 8/4: Teórico de Taller: Tipos de datos, deriving, case, Maybe.
• 22/4: Corrección proyecto 2. Presentación Proyecto 3.
• 29/4: Teórico de Taller: Módulos, TADs, instanciaciones de clases.
• 13/5: Corrección proyecto 3. Presentación Proyecto 4.
• 20/5: Teórico de Taller: Programación C, GDB.
• 27/5: Corrección proyecto 4. Presentación Proyecto 5.
• 3/6: Teórico de Taller: Arreglos y Estructuras en C.
• 17/6: Corrección proyecto 5.

• 9/3 Presentación de la materia. Derivación y verificación de programas. Practico 1. Expresiones Cuantificadas.
• 12/3 Reglas para la cuantificación general.
• 16/3 Cuantificador N. Análisis por casos y pruebas de implicación descargando antecedentes.
• 19/3 Practico 2. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Recursión lineal ej. 3.
• 23/3 Feriado
• 26/3 Recursión lineal. Modularización.
• 30/3 Esquemas inductivos. Generalizacion por abstraccion.
• 2/4 Feriado.
• 6/4 Consulta. Segmentos
• 9/4 Consulta.
• 13/4 1er Parcial.
• 16/4 Feriado.
• 20/4 Practico 3 (Modelo computacional imperativo). Estados y transiciones. Anotaciones con predicados.
• 23/4 Terna de Hoare. Weakest Precondition (asignación, composición secuencial).
• 27/4 Weakest Precondition (if).
• 30/4 Teorema de la invariancia.
• 4/5 Derivación de asignación e if.
• 7/5 Derivación con invariantes.
• 11/5 Arreglos
• 14/5 Practico 4. Tecnicas para encontrar invariantes: termino de la conjunción.
• 18/5 Técnica de reemplazo cte. por variable.
• 21/5 Técnica de predicados intermedios.
• 25/5 Feriado
• 28/5 Semana de mayo.
• 1/6 Técnica de fortalecimiento de invariantes.
• 4/6 Problemas de Borde.
• 8/6 Consulta.
• 11/6 2do Parcial .
• 15/6 Problemas de Borde. Consulta.
• 18/6 Consulta
• 22/6 Recuperatorio .

Acá pondremos lo que efectivamente fuimos dando en cada clase.

• 9/3 Presentación de la materia. Derivación y verificación de programas. Practico 1. Expresiones Cuantificadas. Dado ejercicio 3 a. Pueden hacer hasta el ejercicio 4.
• 12/3 Reglas para la cuantificación general. Pueden hacer hasta ej. 7.
• 16/3 Cuantificador N. Ejercicio del rango unitario para N el cual introduce los conceptos de prueba de análisis por casos.
• 19/3 Practico 2. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Comienza derivación de recursión lineal. Pueden hacer hasta ej. 3.
• 23/3 Feriado
• 26/3 Recursión lineal. Modularización hasta ejercicio pi.
• 30/3 Esquemas inductivos con ejercicio 6.
• 2/4 Feriado (semana santa).
• 6/4 Generalizacion por abstraccion: ejercicio 7.a) psum. Ejercicio sum_ant.
• 9/4 Segmentos. Ejercicio xs segmento de ys en clase
• 13/4 Parcial
• 16/4 Feriado
• 20/4 Practico 3. Historia del modelo computacional imperativo. Sentencias y estados (sin bucles). Hasta ej 1.g y 2.c.
• 23/4 Bucles (final ejercicio 1 y 2). Predicados y anotaciones de programas (ej 3). Terna de Hoare y corrección (ej 4 y 5). Wp de skip, abort, composición y asignación (hasta ejercicio 6.e).
• 27/4 Wp if. Hasta ejercicio 7.d)
• 30/4 Teorema de invariancia. Hasta ejercicio 7.
• 4/5 Derivación de asignaciones y if (ej 8 y 9).
• 7/5 Derivación con invariante dado (ej 12)
• 11/5 Algorítmo de la división. Modelo computacional con arreglos (ej 13 en adelante).
• 14/5 Practico 4. Tecnicas para encontrar invariantes: termino de la conjunción. Ejercicios 1 y 2.
• 18/5 Técnica de reemplazo cte. por variable. Ej 3 a 6. Para la casa especificar ej 7 y 10.
• 21/5 Técnica de fortalecimiento de invariantes. Técnica de predicados intermedios (solo un ej).
• 25/4 Feriado.
• 28/4 Semana de Mayo.
• 1/6 Repaso de predicados intermedios. Técnica de fortalecimiento de guarda.