Algoritmos y Estructuras de Datos I

¡Bienvenido a la página de Algoritmos I!

• Página principal
• Foro de Novedades y Anuncios
• Foro para hacer preguntas

Teórico/Práctico: Franco M. Luque, Matías Lee, Demetrio Martín Vilela, Mauricio Tellechea, Mariana Badano.

Laboratorio: Martín Domínguez, Renato Cherini, Demetrio Martín Vilela, Leonardo Rodríguez, Raúl Fervari, Alejandro Gadea.

Ayudantes: Lucía Pappaterra, Joaquín Barotto, Franco Margaría, Agustín Capello, Kevin Clemoveki, Ángel Argüello.

Teórico/Practico: martes y jueves de 9 a 13 hs, aula D4 (baterías D).

Laboratorio: miércoles de 14 a 18 hs., Labs. 28 y 30.

• 2014/10/28: ¡Práctico 5 publicado!
• 2014/10/14: ¡Práctico 4 publicado!
• 2014/10/14: ¡Enunciado y notas del primer parcial publicados!
• 2014/10/02: ¡Práctico 3 publicado!
• 2014/09/17: Nuevo material: Ejemplo de 1er parcial.
• 2014/09/09: ¡Cambios en el calendario! Semana del estudiante y primer parcial.
• 2014/09/02: Nuevo material: Digesto de funciones de listas y propiedades.
• 2014/08/21: ¡Práctico 2 publicado!
• 2014/08/14: Nuevo material: Digesto Anexo: axiomas y teoremas cuantificador de conteo.
• 2014/08/08: Página publicada!

• Para regularizar la materia: 2 parciales aprobados con nota >= 4 o recuperatorio equivalente y el taller aprobado. Se pueden recuperar ambos parciales.
• Para promocionar la materia: 2 parciales aprobados con nota >= 6 o recuperatorio equivalente, promedio >= 7.5 y el taller aprobado. Se puede recuperar sólo un parcial. Queda la nota del recuperatorio.
• 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 primer cuatrimestre del año 2014.

Sí, pero sólo para regularizar, y contando con el mismo tiempo que si recuperara uno solo. Para promocionar sólo se puede recuperar uno de los dos parciales.

Sí, pero sólo un parcial, y queda la nota del recuperatorio, a riesgo de bajar la nota de promoción o incluso de perderla. ¡Solo para guapos!

No. Sólo valen los del cuatrimestre pasado.

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.
• Ejemplo de 2do parcial.

Programación imperativa:

• Digesto para la programación imperativa.

Más bibliografía y material acá.

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 - Introducción a la programación imperativa (continuación).
• Práctico 5 - Programación imperativa.

Acá pondremos los enunciados y las notas de los parciales.

Enunciados:

• Parcial 1
• Parcial 2

Notas:

• Parcial 1
• Parcial 2 y promedio. La nota final de los promocionados se define una vez corregido el laboratorio.
• Notas del recuperatorio + Notas promoción.

Finales

• Final 2

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 los enunciados de los finales.

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

• 13/8: Presentación Proyecto 1
• 20/8: Teórico de Taller: Haskell, GHCI, secciones, map, filter.
• 27/8: Teórico de Taller: Tipos, clases de tipos y más.
• 3/9: Corrección Proyecto 1. Presentación Proyecto 2.
• 10/9: Teórico de Taller: Tipos de datos, deriving, case, Maybe.
• 24/9: Corrección proyecto 2. Presentación Proyecto 3.
• 25/9: Primer parcial.
• 1/10: Teórico de Taller: Módulos, TADs, instanciaciones de clases.
• 15/10: Corrección proyecto 3. Presentación Proyecto 4.
• 22/10: Teórico de Taller: Programación C, GDB.
• 5/11: Corrección proyecto 4. Presentación Proyecto 5.
• 13/11: Segundo parcial.
• 22/10: Teórico de Taller: Arreglos y Estructuras en C.
• 20/11: Recuperatorio.
• 26/11: Corrección proyecto 5.

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

• 12/8:
  • Presentación de la materia.
  • Métodos de prueba básicos.
  • Cuantificación general.
• 14/8:
  • Reglas para la cuantificación general: Rango vacío, rango unitario, partición de rango, regla del término, término constate y distributividad. Intuición y ejemplos.
• 19/8:
  • Reglas para la cuantificación general: Anidado, cambio de variable y separación de un término. Intuición, ejemplos y demostraciones.
  • Cuantificador de conteo: Definición. Reglas: rango vacío y rango unitario.
  • Métodos de prueba: Análisis por casos.
• 21/8:
  • Inducción:
    • Inducción sobre números y listas.
    • Diferentes esquemas de inducción.
    • Demostración por inducción vs. derivación por inducción.
• 26/8:
  • Conceptos: Propiedad, especificación, programa/definición, demostración y derivación.
  • Derivación por inducción básica sobre números y listas.
• 28/8:
  • Modularización: concepto, intuición y ejemplos.
  • Más derivación por inducción: ejemplo con esquema sobre listas [], [x] y (y:x:xs) (función creciente).
• 2/9:
  • Generalización: concepto e intuición. Procedimiento. Ejemplos.
• 4/9:
  • Más generalización: Más ejemplos con listas y números.
• 9/9:
  • Segmentos de lista: definiciones de segmento, segmento inicial y segmento final.
  • Especificación y derivación de problemas con segmentos.
• 11/9:
  • Complejidad algorítmica.
  • Técnica de tuplas.
• 2/10:
  • Presentación de Programación Imperativa.
  • Lenguaje de programación imperativo: sentencias, con su sintaxis, semántica y ejemplos.
• 7/10:
  • Arreglos: Declaración y uso.
  • Anotación de programas. Precondición y postcondición.
  • Especificaciones.
• 9/10:
  • Ternas de Hoare: Definición y ejemplos.
  • Debilidad y fortaleza de predicados.
  • Precondición más débil (weakest precondition):
    • Intuición y definición.
    • Relación con terna de hoare.
    • Wp de skip, abort y asignación.
• 14/10: (Entra Chun, sale Franco)
  • Repaso de las tres clases de imperativo.
  • Respondimos las preguntas ¿qué hace el comando X?,¿cuándo la terna de Hoare para el comando X es válida?, ¿cuál es la precondición más débil para el comando X y la postcondición Q? para los comandos skip, abort, asignación e if.
• 16/10:
  • Ternade hoare y wp para la concatenación.
  • Repetición/Ciclo/DO: válidez de la terna de Hoare sin cota. Idea de invariante.
• 21/10:
  • Función de cota.
  • Derivación de programas sin ciclos.
• 23/10: Técnicas para derivar invariantes
  • T1: El invariante como términos de una conjunción
• 28/10: Técnicas para derivar invariantes
  • T2: Reemplazo de constantes por variables.
• 30/10:
  • Predicados intermedios.
  • Ejercicio 8.a del práctico 4.
• 04/11:
  • T3: Fortalecimiento de invariante.
  • Repaso de la función de cota.
• 06/11:
  • Fortalecimiento de invariante y problemas con los bordes