====== Algoritmos y Estructuras de Datos I - 2015 1er cuatrimestre ====== {{ :algo1:portada.jpg?150 }} [[http://cs.famaf.unc.edu.ar/wiki/doku.php?id=algo1:2015-1|¡Bienvenido a la página de Algoritmos I!]] /* ===== 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**: [[http://cs.famaf.unc.edu.ar/~damian|Damián Barsotti]], Javier Blanco, Demetrio Martín Vilela. **Laboratorio**: Martín Domínguez, Juan Cruz Rodríguez. **Ayudantes**: Daniel Bridera, Iliak Zapata. ===== Horarios ===== **Teórico/Practico**: lunes y jueves de 14 a 18 hs, aula 25. **Laboratorio**: miércoles de 9 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: Ver [[algo1:taller:modalidad#condiciones_para_rendir_libre_el_taller|Condiciones para rendir libre el taller]]. Ver también [[algo1:taller:modalidad|Modalidad del taller]]. Nota: El taller también se considerará aprobado si lo fue en el segundo cuatrimestre del año 2014. /* - las notas son números redondos */ ===== Material ===== Programación funcional: * {{:algo1:2014-2:digesto.pdf|Digesto}} de axiomas y teoremas para cálculo proposicional y expresiones cuantificadas. * {{:algo1:2014-2:cuantificador_n.pdf|Anexo}} (axiomas y teoremas cuantificador de conteo). * {{:algo1:2014-2:listas.pdf|Digesto}} de funciones de listas y propiedades. * {{:algo1:2014-2:ejemplo_parcial1.pdf|Ejemplo de 1er parcial.}} Programación imperativa: * {{:algo1:2015-1:imperativo.pdf|Digesto}} para la programación imperativa. * {{:algo1:2014-2:ejemplo_parcial2.pdf|Ejemplo de 2do parcial.}} /* [[bibliografia|Más bibliografía y material acá.]] */ ===== Prácticos ===== Acá pondremos los prácticos. * {{:algo1:2015-1:practico1.pdf|Práctico 1}} - Repaso cálculo proposicional y expresiones cuantificadas. * {{:algo1:2015-1:practico2.pdf||Práctico 2}} - Especificación derivación y verificación de programas funcionales. * {{:algo1:2015-1:practico3.pdf|Práctico 3}} - Introducción a la programación imperativa. * {{:algo1:2015-1:practico4.pdf| Práctico 4}} - Programación imperativa. ===== Parciales (y Recuperatorios) ===== * {{:algo1:2015-1:algoritmos_i_2015_primer_cuatrimestre_-_teorico.pdf|Notas primer parcial}}. * {{:algo1:2015-1:algoritmos_i_2015_primer_cuatrimestre_-_teorico-3.pdf|Notas segundo parcial}}. * {{:algo1:2015-1:algoritmos_i_2015_primer_cuatrimestre_-_teorico-6.pdf|Notas recuperatorio}}. * {{:algo1:algoritmos_i_2015_primer_cuatrimestre_-_acta_reg..pdf|Condición Final}}. * {{:algo1:2015-1:algoritmos_i_2015_primer_cuatrimestre_-_final_1.pdf|Final 1}}. * {{:algo1:2015-1:algoritmos_i_2015_primer_cuatrimestre_-_final_3.pdf|Final 3}}. ===== Laboratorio ===== | ^ Enunciado ^ Teóricos ^ Fecha corrección ^ ^ Presentación | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/presentacion_2014.html|Presentación]] ||| ^ Proyecto 1 | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/proyectos/proy1.pdf|Proyecto 1]] |[[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase2_linux.html|Linux y consola]] | 1/4| ^ ::: | ::: | [[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, 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/~hoffmann/algo1/proy2_tiposdedatos.hs|Ejemplos tipos de datos (archivo .hs)]] | 22/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/~hoffmann/algo1/2013-2/proyectos/proyecto3_archivos_alumnos.zip|Archivos]]) | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase6_tad.html|Módulos, TADs, instanciaciones de clases]]| 13/5| ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/proy3_lista_invariante.hs|Lista con invariante de orden (archivo .hs)]] | ::: | ^ Proyecto 4 | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proy4.pdf|Proyecto 4]] | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/clase_1_de_c.html|Programación C, GDB]]| 27/5| ^ Proyecto 5 | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/proy5.pdf|Proyecto 5]] |[[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/clase_arreglo.html|Teórico de Arreglos]], [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/arreglo.c|Código Arreglo]], [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/inicializar.c|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/~hoffmann/algo1/2013-1/struct.c|Struct]], [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/struct2.c|Struct 2]]| 17/6| Ejemplos de programas en C: * Proyecto 4 / Proyecto 5: * Código C: [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/helloworld.c|Hello, World!]] * Código C: [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/assignacion.c|Assignación múltiple]] * Código C: [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/while.c|While]] * Código C: [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/mcd.c|Mcd]] * Código C: [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/mcdFuncion.c|Mcd con función]] Enunciados y teóricos del año pasado: * Código C: [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/collatz.c|Collatz]] * 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://github.com/WilliamHackmore/linuxgems/blob/master/cheat_sheet.org.sh|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 darlo. ==== Taller ==== * 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**. ==== Teórico Práctico ==== * 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 **. ===== Bitácora ===== 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. /* * 26/5 Consulta. Ej 12 * 29/5 Consulta. Problemas de Borde. * 2/6 Problemas de Borde. */