====== Algoritmos y Estructuras de Datos I - 2017 1er cuatrimestre ====== {{ :algo1:portada.jpg?150 }} [[http://cs.famaf.unc.edu.ar/wiki/doku.php?id=algo1:2017-1|¡Bienvenido a la página de Algoritmos I!]] [[http://www.famaf.proed.unc.edu.ar/course/view.php?id=318|Aula Virtual]] (recuerde inscribirse). /* ===== Novedades ===== * 04/08/2015: Relanzamiento de la página! * 13/08/2015: Publicado el práctico 1. * 25/08/2015: Se publicó el práctico 1 corregido. Se subió el borrador del libro de la materia. * 01/09/2015: Se publicó el práctico 2 completo. Se publicaron las fechas de los parciales. * 07/10/2015: Se publicaron los prácticos 3 y 4. ===== Aula Virtual (Moodle) ====== * [[http://www.famaf.proed.unc.edu.ar/course/view.php?id=10|Página principal]] * [[http://www.famaf.proed.unc.edu.ar/mod/forum/view.php?f=626|Foro de Novedades y Anuncios]] * [[http://www.famaf.proed.unc.edu.ar/mod/forum/view.php?f=627|Foro para hacer preguntas]] */ ===== Docentes ===== **Teórico/Práctico**: Damián Barsotti, Demetrio Martín Vilela, Ignacio Moretti. **Laboratorio**: Martín Domínguez, Paula Estrella, Juan Cruz Rodríguez. **Ayudantes**: Diego Piloni, Matias Gastón Silva, Meriles Emanuel Juan René. ===== Horarios ===== **Teórico/Practico**: martes y jueves de 14 a 18 hs, aula 25. **Laboratorio**: lunes de 14 a 18 hs, Lab. 30. ===== Regularidad / Promoción ===== * 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, hay condiciones particulares respecto al taller. Ver [[algo1:taller:modalidad|Modalidad del taller]] para los detalles. Nota: El taller también se considerará aprobado si lo fue en el segundo cuatrimestre de 2015. /* - las notas son números redondos */ ===== Fechas de parciales y recuperatorio ==== /* * Primer parcial: 11 de Abril * Segundo parcial: 6 de Junio * Recuperatorios: 16 de Junio * {{:algo1:2014-2:ejemplo_parcial1.pdf|Ejemplo de 1er parcial.}} * {{:algo1:2016-1:ejemplo_parcial2.pdf||Ejemplo de 2do parcial.}} */ ===== Material ===== "Borrador" del [[http://www.cs.famaf.unc.edu.ar/~damian/calcprog|libro]] de la materia: Programación funcional: * {{:algo1:2017-1:digesto.pdf|Digesto}} de axiomas y teoremas para cálculo proposicional y expresiones cuantificadas. * {{:algo1:2017-1:cuantificador_n.pdf|Anexo}} (axiomas y teoremas cuantificador de conteo). * {{:algo1:2017-1:listas.pdf|Digesto}} de funciones de listas y propiedades. * {{:algo1:2014-2:ejemplo_parcial1.pdf|Ejemplo de 1er parcial.}} Programación imperativa: * {{:algo1:2017-1:imperativo.pdf|Digesto}} para la programación imperativa. * {{:algo1:2016-1:ejemplo_parcial2.pdf|Ejemplo de 2do parcial.}} Más bibliografía y material ''[[:algo1:bibliografia2|acá]]''. ===== Prácticos ===== Acá pondremos los prácticos. * {{:algo1:2017-1:practico1.pdf|Práctico 1}} - Cálculo proposicional y expresiones cuantificadas. * {{:algo1:2017-1:practico2.pdf|Práctico 2}} - Especificación derivación y verificación de programas funcionales. * {{:algo1:2017-1:practico3.pdf|Práctico 3}} - Introducción a la programación imperativa. * {{:algo1:2017-1:practico4.pdf|Práctico 4}} - Programación imperativa. ===== Parciales, recuperatorios y finales ===== * {{:algo1:2017-1:algoritmos_i_2017_primer_cuatrimestre_-_teorico_-_notas1.pdf|Notas parcial 1}}. * {{:algo1:2017-1:algoritmos_i_2017_primer_cuatrimestre_-_teorico_notas2.pdf|Notas parcial 2}}. * {{:algo1:2017-1:algoritmos_i_2017_primer_cuatrimestre_-_condicion.pdf|Notas recuperatorio y condición final}}. * {{:algo1:2017-1:algoritmos_i_2017_primer_cuatrimestre_-_final_1.pdf|Notas Final 1}}. * {{:algo1:2017-1:algoritmos_i_2017_primer_cuatrimestre_-_final_2.pdf|Notas Final 2}}. * {{:algo1:2017-1:algoritmos_i_2017_primer_cuatrimestre_-_final_3.pdf|Notas Final 3}}. ===== Laboratorio ===== | ^ Enunciado ^ Teóricos ^ Fecha corrección ^ ^ Presentación | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/presentacion_2016_1.html|Presentación]] ||| ^ Proyecto 1 | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proy1.pdf|Proyecto 1]] |[[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/Linux_y_consola.html|Linux y consola]] | 3/4| ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/Ejercicio_extra_clase_1.hs|Ejercicios de Haskell.]] | ::: | ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/CLASE_1_proy_1.html|Haskell, GHCI, secciones, map, filter]] | | ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/CLASE_2_proy_1.html|Tipos, polimorfismo, clases de tipos y más]] | : | ^ Proyecto 2 | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proy2.pdf|Proyecto 2]] | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/clase_2_ejemplo_tipos.hs|Ejemplos tipos de datos (archivo .hs)]] | | ^ ::: | ::: |[[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/Tipos_en_Haskell.pdf|Tipos de datos en Haskell]] | 24/4 | ^ ::: | ::: |[[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proyecto_2_CLASE_1.html|Tipos de datos, deriving, case, Maybe]] | ^ Proyecto 3|[[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proy3.pdf|Proyecto 3]]([[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/hal-gui.zip|Archivos HAL]])|[[https://docs.google.com/presentation/d/104uhjnehOSZ5tu11AQRB2D-Mt71cuEa8zZE7Zi4Xex8/edit?usp=sharing|Presentación de HAL]]| 22/5| ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/presentacio_modelo_comp.pdf|Modelo Computacional]] | ::: | ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/Examples-HAL.zip|Ejemplos de programas en HAL]] | ::: | ^ ::: | ::: | [[algo1:instalarhal|Instalar HAL]]| ::: | ^ Proyecto 4 | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proy4_2016_2.pdf|Proyecto 4]] | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/Clase_1_de_C_con_hal.html|Programación C, GDB]]; [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/funciones_en_c.c|Ejemplo de funciones en C]] | ^ | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/archivos_ejercicios.zip|Archivos complementarios Proy. 4]] |[[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/clase_arreglo.html|Teórico de Arreglos]], [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/arreglo.c|Código Arreglo]], [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/inicializar.c|Ejemplo de inicialización de arreglos]]; [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/clase_struct.html|Teórico de Estructuras]], [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/struct_ejemplo.c|Struct]], | 19/6| Enunciados y teóricos de años previos: * Introduccion a GDB. Por Marco Brunello y Leandro Ramos. {{:algo1:2011-2:gdb.pdf|Presentación}}, {{:algo1:2011-2:ejemplo_gdb.tar.gz|ejemplos}}. [[https://gist.github.com/zhaidongplus/5113855|Resumen de comandos de consola Linux]] y [[http://cli.learncodethehardway.org/book/| un libro sobre el tema]]. ===== Calendario Tentativo ===== Acá pondremos el calendario completo de la materia como esperamos darla. ==== Teórico Práctico ==== * 14/3 Presentación de la materia. Derivación y verificación de programas. **Practico 1**. Expresiones Cuantificadas. * 16/3 Reglas para la cuantificación general. * 21/3 Cuantificador N. Análisis por casos y pruebas de implicación descargando antecedentes. * 23/3 Consulta. * 28/3 **Practico 2**. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Recursión lineal ej. 3. * 30/3 Recursión lineal. Modularización. * 4/4 Esquemas inductivos. Generalización por abstracción. * 6/4 Consulta. Segmentos. * 11/4 Consulta. * 13/4 Feriado * 18/4 ** 1er Parcial** * 20/4 **Practico 3** (Modelo computacional imperativo). Estados y transiciones. Anotaciones con predicados. * 25/4 Terna de Hoare. Weakest Precondition (asignación, composición secuencial). * 27/4 Weakest Precondition (if). * 2/5 Teorema de la invariancia. * 4/5 Derivación de asignación e if. * 9/5 Derivación con invariantes. * 11/5 Arreglos * 16/5 **Practico 4**. Tecnicas para encontrar invariantes: termino de la conjunción. * 18/5 Técnica de reemplazo cte. por variable. * 23/5 Semana de Mayo * 25/5 Feriado * 30/5 Técnica de fortalecimiento de invariantes. * 1/6 Problemas de Borde. * 6/6 Consulta. * 8/6 **2do Parcial** * 13/6 Problemas de Borde. Consulta. * 15/6 Consulta * 20/6 Feriado * 22/6 Recuperatorio /* No damos Técnica de predicados intermedios. */ ==== Taller ==== *13/3: Presentación Proyecto 1 y auto-repaso linux *20/3: Teórico de Taller: Haskell, GHCI, secciones, map, filter. *27/3: Teórico de Taller: Tipos, clases de tipos y más. *3/4: Corrección Proyecto 1. Presentación Proyecto 2. *10/4: Teórico de Taller: Tipos de datos, deriving, case, Maybe. *24/4: Corrección proyecto 2. Presentación Proyecto 3. *8/5: Teórico primera parte. Uso de Hal - Teórico semántica. *22/5: Corrección proyecto 3. Presentación proyecto 4 *29/5: Teórico de Taller: Programación C, GDB. *5/6: Teórico de Taller: Arreglos y Estructuras en C. *19/6: Corrección proyecto 4. ===== Bitácora ===== Acá pondremos lo que efectivamente fuimos dando en cada clase. * 14/3 Presentación de la materia.Expresiones Cuantificadas. Pueden hacer ejercicios 1-9 y 12-14(cuantgen). * 16/3 Paro * 21/3 Paro * 23/3 Axiomas y teoremas de la cuantificación general (digesto). Cuantificador N. Análisis por casos y pruebas de implicación descargando antecedentes. Pueden ir haciendo los ejercicios 3 a 9 y 12 a 14 * 27/3 Práctico 2. Demostración vs. derivación. Pueden ir haciendo hasta el 4 inclusive. * 30/3 Paro * 4/4 Modularización. Esquemas inductivos. * 6/4 Paro * 11/4 Paro * 13/4 Feriado. * 18/4 1er **Parcial** * 20/4 Generalización. * 25/4 Segmentos. * 27/4 **Práctico 3**: Introducción a la programación imperativa. Modelo computacional imperativo. Sintaxis y semántica con estados de ''skip'', asignación ('':=''), composición ('';''), condicional (''if'') y de la repetición (''do''). * 2/5 Terna de Hoare. wp de ''skip'', asignación ('':='') /* * 06/10: 1er parcial. * 11/10: Anotaciones de programa. Precondición y postcondición. Especificación. * 13/10: Precondición más débil. Demostración de programas imperativos. Demostración de skip, asignación, composición y condicional. * 18/10: Demostración de ciclos. Invariante y función de cota. * 20/10: Demostración completa de un programa. * 25/10: Introducción a la derivación de programas. Derivación de asignaciones. * 27/10: Derivación de condicionales. Derivación de ciclos. Técnicas para determinar invariantes: Tomar términos de una conjunción (ejemplo: algoritmo de la división). * 1/11: Técnicas para determinar invariantes: * Tomar términos de una conjunción (ejemplo: búsqueda lineal). * Reemplazo de constantes por variables (ejemplo: suma de arreglo, exponenciación). * 3/11: Fortalecimiento de invariantes (ejemplo: ''sumant''). * 8/11: Problemas de borde al fortalecer invariantes (ejemplos: segmento de suma máxima, máxima distancia entre elementos). * 10/11: Estados intermedios (ejemplo: varianza). * 15/11: 2do parcial. * 17/11: Consulta. * 22/11: Consulta. * 24/11: Recuperatorios. */