====== Algoritmos y Estructuras de Datos I ====== {{ :algo1:portada.jpg?150 }} [[http://cs.famaf.unc.edu.ar/wiki/doku.php?id=algo1:2014-2|¡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/~francolq|Franco M. Luque]], [[http://cs.famaf.unc.edu.ar/~lee|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, [[http://cs.famaf.unc.edu.ar/~rfervari/|Raúl Fervari]], Alejandro Gadea. **Ayudantes**: Lucía Pappaterra, Joaquín Barotto, Franco Margaría, Agustín Capello, Kevin Clemoveki, Ángel Argüello. ===== Horarios ===== **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. ===== Novedades ===== * **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! ===== Regularidad / Promoción ===== * 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 [[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 primer cuatrimestre del año 2014. /* - las notas son números redondos */ ===== Preguntas Frecuentes (FAQs) ===== === ¿Se pueden recuperar los dos parciales? === 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. === ¿Se puede recuperar para levantar nota de promoción? === 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! === ¿Me dan el taller por aprobado si lo aprobé el año pasado? === No. Sólo valen los del cuatrimestre pasado. ===== 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.}} * {{:algo1:2014-2:ejemplo_parcial2.pdf|Ejemplo de 2do parcial.}} Programación imperativa: * {{:algo1:2014-1:imperativo.pdf|Digesto}} para la programación imperativa. [[bibliografia|Más bibliografía y material acá.]] ===== Prácticos ===== Acá pondremos los prácticos. * {{:algo1:2014-2:practico1.pdf|Práctico 1}} - Repaso cálculo proposicional y expresiones cuantificadas. * {{:algo1:2014-2:practico2.pdf|Práctico 2}} - Especificación derivación y verificación de programas funcionales. * {{:algo1:2014-2:practico3.pdf|Práctico 3}} - Introducción a la programación imperativa. * {{:algo1:2014-2:practico4.pdf|Práctico 4}} - Introducción a la programación imperativa (continuación). * {{:algo1:2014-2:practico5.pdf|Práctico 5}} - Programación imperativa. /* * {{:algo1:2014-1:practico2.pdf|Práctico 2}} - Especificación derivación y verificación de programas funcionales. * {{:algo1:2014-1:practico3.pdf|Práctico 3}} - Introducción a la programación imperativa. * {{:algo1:2014-1:practico4.pdf|Práctico 4}} - Programación imperativa. */ ===== Parciales (y Recuperatorios) ===== Acá pondremos los enunciados y las notas de los parciales. **Enunciados:** * {{:algo1:2014-2:2014c2par1.pdf|Parcial 1}} * {{:algo1:2014-2:2014c2par2.pdf|Parcial 2}} **Notas:** * {{:algo1:2014-2:notas_parcial_1.pdf|Parcial 1}} * {{:algo1:2014-2:parcial_1_2_y_promedio.pdf|Parcial 2 y promedio}}. La nota final de los promocionados se define una vez corregido el laboratorio. * {{:algo1:2014-2:NotasFinalMateria_2014.pdf|Notas del recuperatorio + Notas promoción}}. **Finales** * {{:algo1:2014-2:final_17_12.pdf|Final 2}} ===== 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]] | 3/9| ^ ::: | ::: | [[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)]] | 24/9| ^ ::: | ::: |[[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]]| 15/10| ^ ::: | ::: | [[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]]| 5/11| ^ 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]]| 26/11| 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]]. ===== Finales ===== Acá pondremos los enunciados de los finales. ===== Calendario tentativo ===== 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.** ===== Bitácora ===== 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 /* * 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**. */