Algoritmos y Estructuras de Datos I

Docentes

Teórico/práctico:

Laboratorio: Martín Dominguez,Renato Cherini, Demetrio Vilela, Raúl Fervari, Leonardo Rodríguez, Alejandro Gadea, Lucía Papaterra, Joaquín Barotto, Agustín Capello,Pablo Pastore Franco Margaría, Kevin Clemoveki.

Horarios

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

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

Novedades

Regularidad / Promoción

Para regularizar la materia: 2 parciales aprobados con nota > 3 o un recuperatorio equivalente y el taller aprobado.
Para promocionar la materia: 2 parciales aprobados con nota >= 6, promedio >= 8 y el taller aprobado.
Para rendir libre la materia: seguiremos la modalidad del dictado ordinario de la materia, que aparece en “Condiciones para rendir libre el taller” en la página de la materia del año pasado.

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

Parciales

Notas primer parcial algoritmos_i_2014_primer_cuatrimestre_-_teorico.pdf.

Condicion Final algoritmos_i_2014_primer_cuatrimestre_-_teorico_final.pdf.

Finales

Bitácora

10/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.
13/3 Reglas para la cuantificación general.
17/3 Ejercicio del rango unitario para N el cual introduce los conceptos de prueba de análisis por casos y pruebas de implicación descargando antecedentes. Esto último para B ⇒ E, B ⇒ E = E', B1 /\ B2 ⇒ E (usando intercambio).
20/3 Practico 2. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Comienza derivación de recursión lineal ej. 3.
24/3 Feriado
27/3 Recursión lineal. Modularización hasta ejercicio pi.
31/3 Esquemas inductivos con ejercicio 6. Generalizacion por abstraccion: ejercicio 7.a) psum.
3/4 Ejercicio sum_ant. Segmentos hasta 10 b).
7/4 Ejercicio suma mínima de un segmento. Consulta.
10/4 Paro
14/4 Parcial.
17/4 Feriado
21/4 Practico 3 Modelo computacional imperativo. Hasta ej 2. Terna de Hoare: principio de capítulo 16 del libro.
24/4 Terna de Hoare. Weakest Precondition. Wp de asignacion. wp del if. Hasta ejercicio 4.
28/4 ej 5 con wp del if. Teorema de invariancia. Hasta ejercicio 5. En casa ejercicios 8 y 9
1/5 Feriado
5/5 Derivación de asignaciones y if (ej 7). Pueden hacer hasta el ejercicio 9.
8/5 Derivación algoritmo de la division (javi)(proximo práctico) y mcd.
12/5 Arreglos ej 11. Ej 10. Exp de ejercicio.
15/5 Practico 4. Tecnicas para encontrar invariantes: termino de la conjunción. Ejercicios 1 y 2 en clase. Pueden hacer hasta el 4.
19/5 Técnica de reemplazo cte. por variable. Ej 5 Ej 6 y 6.a). Pueden hacer hasta ej 8.
22/5 Técnica de predicados intermedios Ej 9 y 10. Pueden hacer hasta el 11.
26/5 Consulta. Técnica de fortalecimiento de invariantes. Ej 12
29/5 Consulta. Problemas de Borde.
2/6 Problemas de Borde.

Bibliografía / Media

Haskell

Lenguaje C

Lecturas recomendadas

Why Functional Programming Matters John Hughes.
Trampa en el cyberespacio.
Software's Chronic Crisis.
Voto electrónico. Los riesgos de una ilusión. Federico Heinz.
X11 windows manager in Haskell!.

Media

Charla sobre Software Libre de Federico Heinz 6/5/2013.

Prácticos

Digesto de axiomas y teoremas para cálculo proposicional y expresiones cuantificadas.

Digesto para la programación imperativa.

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.

Calendario tentativo

10/3 Presentación de la materia. Derivación y verificación de programas. Practico 1. Expresiones Cuantificadas.
13/3 Reglas para la cuantificación general.
17/3 Cuantificador N. Análisis por casos y pruebas de implicación descargando antecedentes.
20/3 Practico 2. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Recursión lineal ej. 3.
24/3 Feriado
26/3 Corrección proyecto 1.
27/3 Recursión lineal. Modularización.
31/3 Esquemas inductivos. Generalizacion por abstraccion.
3/4 Consulta.
7/4 Segmentos.
14/4 Parcial.
17/4 Feriado
21/4 Practico 3 Modelo computacional imperativo.
23/4 Corrección proyecto 2.
24/4 Terna de Hoare. Weakest Precondition. Wp de asignacion. wp del if
28/4 Especificación y derivación.
1/5 Feriado
5/5 Teorema de la invariancia.
8/5 Derivación de asignaciones y if
12/5 Derivación con invariante.
14/5 Corrección proyecto 3.
15/5 Consulta
19/5 Practico 4. Tecnicas para encontrar invariantes: termino de la conjunción.
22/5 Técnica de reemplazo cte. por variable. Ej 6 y 6.a). Pueden hacer hasta ej 8
26/5 Técnica de predicados intermedios.
29/5 Técnica de fortalecimiento de invariantes.
2/6 Consulta
4/6 Corrección proyecto 4.
5/6 Problemas de Borde.
9/6 Problemas de Borde. Consulta.
12/6 Parcial.
16/6 Problema de asignación de arreglos. Consulta.
19/6 Recuperatorio.
25/6 Corrección proyecto 5.

Laboratorio

	Enunciado	Teóricos	Fecha corrección
Presentación	Presentación
Proyecto 1	Proyecto 1	Linux y consola	26/3
		Haskell, GHCI, secciones, map, filter
		Tipos, clases de tipos y más
Proyecto 2	Proyecto 2	Ejemplos tipos de datos (archivo .hs)	23/4
Proyecto 2	Proyecto 2	Tipos de datos, deriving, case, Maybe	23/4
Proyecto 3	Proyecto 3 (Archivos)	Módulos, TADs, instanciaciones de clases	14/5
Proyecto 3	Proyecto 3 (Archivos)	Lista con invariante de orden (archivo .hs)	14/5
Proyecto 4	Proyecto 4	Programación C, GDB	4/6
Proyecto 5	Proyecto 5	Arreglo, Inicialización; Struct, Struct 2	25/6

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.

Información para Docentes

Bitácora tentativa del teórico/práctico

10/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.
13/3 Reglas para la cuantificación general.
17/3 Ejercicio del rango unitario para N el cual introduce los conceptos de prueba de análisis por casos y pruebas de implicación descargando antecedentes. Esto último para B ⇒ E, B ⇒ E = E', B1 /\ B2 ⇒ E (usando intercambio).
20/3 Practico 2. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Comienza derivación de recursión lineal ej. 3.
24/3 Feriado
27/3 Derivación de recursión lineal. Hasta ejercicio 4. Ejercicio 5 de modularización. Suma de potencias en clase.
31/3 Esquemas inductivos con ejercicio 6. Generalizacion por abstraccion: ejercicio 7.a) psum.
3/4 Ejercicio sum_ant. Consulta. Hasta ej 8.
7/4 Segmentos. Ejercicio suma mínima de un segmento.
10/4 Parcial.
14/4 Practico 3 Modelo computacional imperativo. Hasta ej 2
17/4 Feriado
21/4 Terna de Hoare. Weakest Precondition. Wp de asignacion. Hasta ejercicio 3.e). wp del if
24/4 Feriado
28/4 wp del if. Especificación y derivación. Hasta ejercicio 5.d
1/5 Feriado
5/5 Teorema de la invariancia. Ej 5.e y f
8/5 Derivación de asignaciones y if (ej 6 y 7). Pueden hacer hasta el ejercicio 8.
12/5 Derivación mcd. Salte el ej 9 (arreglos)
15/5 Ej 9. Exp de ejercicio 10
19/5 Practico 4. Tecnicas para encontrar invariantes: termino de la conjunción. Ejercicios 1 y 2 en clase. Pueden hacer hasta el 4.
22/5 Técnica de reemplazo cte. por variable. Ej 6 y 6.a). Pueden hacer hasta ej 8
26/5 Técnica de predicados intermedios Ej 9 y 11.a)
29/5 Técnica de fortalecimiento de invariantes. Ej 12
2/6 Consulta
5/6 Problemas de Borde.
9/6 Problemas de Borde. Consulta.
12/6 Parcial.
16/6 Problema de asignación de arreglos. Consulta.
19/6 Recuperatorio.