====== Algoritmos y Estructuras de Datos I ====== {{ :algo1:portada.jpg?150 }} ===== Docentes ===== **Teórico/práctico**: [[http://www.cs.famaf.unc.edu.ar/~damian|Damián Barsotti]], Matías Lee, Franco Luque, Demetrio Martín Vilela, Leonardo Rodríguez, Mauricio Telechea. **Laboratorio**: Martín Dominguez, Guillaume Hoffmann, Diego Dubois, Renato Cherini, Demetrio Martín Vilela, Agus Capello, Alejandro José Naser Pastoriza, Schmidt Mariano. ===== Horarios ===== **Teórico/Practico**: martes y jueves de 9 a 13 hs, aula D4. **Laboratorio**: miércoles de 14 a 18 hs., Lab. 28 y 30. ===== Novedades ===== * Url corto de la materia como [[http://tinyurl.com/algo1-2013-2]]. * Creada [[http://www.famaf.proed.unc.edu.ar/course/view.php?id=113|aula virtual]]. ===== 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 [[2010-2|la página de la materia del año pasado]]. Nota: El taller también se considerará aprobado si lo fue en el primer cuatrimestre del año 2013. ===== Parciales ===== * Notas primer parcial {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_teorico.pdf|}}. * Notas segundo parcial {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_teorico_par2_full2.pdf|}}. * Recuperatorio y condición final {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_recup_condf.pdf|}}. /* * 25/4 y 17/6 * Recuperatorio 24/6. */ ===== Finales ===== * {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_exam1_legajo.pdf|Examen 1}}. * {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_exam2_legajo.pdf|Examen 2}}. * {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_exam3.pdf|Examen 3}}. * {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_exam4.pdf|Examen 4}}. ===== Bitácora ===== * 13/8 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. * 15/8 Reglas para la cuantificación general. * 20/8 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). * 22/8 **Practico 2**. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Hasta ej 2. * 27/8 Derivación de recursión lineal. Hasta ejercicio 4. * 29/8 Modularización. Tratan de hacer en el práctico lo de esquemas inductivos. * 3/9 Esquemas inductivos con ejercicio 5. Tuplas (ejercicio 7.a). * 5/9 Generalizacion por abstraccion: ejercicio 8.a) psum. * 10/9 Ejercicio sum_ant. Consulta. Hasta ej 9. * 12/9 Segmentos. Ejercicio suma mínima de un segmento. * 17/9 Semana del estudiante. * 19/9 Semana del estudiante. * 24/9 Consulta de práctico. * 26/9 **Parcial**. * 1/10 **Practico 3** Modelo computacional imperativo. Hasta ej 2 * 3/10 Terna de Hoare. Weakesr Precondition. Wp de asignacion. Hasta ejercicio 3.e). Chun da wp del if * 8/10 wp del if. Especificación y derivación. Hasta ejercicio 5.d * 10/10 Teorema de la invariancia. Ej 5.e y f * 15/10 Derivación de asignaciones y if (ej 6 y 7). Pueden hacer hasta el ejercicio 8. * 17/10 Derivación mcd. Salte el ej 9 (arreglos) * 22/10 Exp de ejercicio 10. **Practico 4**. Tecnicas para encontrar invariantes: termino de la conjunción. Algoritmo de la division * 24/10 Arreglos y ejercicio 2 **Practico 4**. Pueden hacer hasta el 4. /* * 29/10 Técnica de reemplazo cte. por variable. Ej 6 y 6.a). Pueden hacer hasta ej 8 * 31/10 Técnica de predicados intermedios Ej 9 y 11.a) * 5/11 Técnica de fortalecimiento de invariantes. Ej 12 * 7/11 Problemas de Borde. * 12/11 Problemas de Borde. Consulta. * 14/11 **Parcial**. * 19/11 Problema de asignación de arreglos. Consulta. * 21/11 **Recuperatorio**. */ ===== Bibliografía / Media ===== /* * [[http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/main.pdf | Cálculo de Programas]] (contiene los teóricos y ejercicios del práctico). * [[http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/introlinux.pdf | Introducción a Linux]]. */ ==== Haskell ==== * [[http://www.cs.famaf.unc.edu.ar/~hoffmann/aprendehaskell/main.html|¡Aprende Haskell por el bien de todos!]] * [[http://www.lcc.uma.es/~blas/pfHaskell/gentle/index.html|Una introducción agradable a Haskell]] * [[http://www.haskell.org/hoogle/|Hoogle, búsqueda de funciones por nombre o tipo]]. * [[http://www.haskell.org/ghc/docs/latest/html/users_guide/ghci.html|Using GHCI]] ==== Lenguaje C ==== * [[http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/lenguaje_C/cursc.html|En castellano pero básico]]. * [[http://www.cs.cf.ac.uk/Dave/C/ | En ingles pero muy completo]]. * [[http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/lenguaje_C/www.phim.unibe.ch/comp_doc/c_manual/C/cref.html|Manual de referencia en inglés]]. * {{algo1:curso-c.pdf|Otro en castellano}}. ==== Lecturas recomendadas ==== * [[http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html|Why Functional Programming Matters]] John Hughes. * [[http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/lecturas/dicosmo.html|Trampa en el cyberespacio]]. * [[http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/lecturas/sciam_scc/SciAmSept1994.html|Software's Chronic Crisis]]. * [[http://www.vialibre.org.ar/wp-content/uploads/2009/03/evoto.pdf|Voto electrónico. Los riesgos de una ilusión]]. Federico Heinz. * [[http://www.xmonad.org/|X11 windows manager in Haskell!]]. ==== Media ==== * [[http://www.cs.famaf.unc.edu.ar/~damian/media/charla_fede.html|Charla sobre Software Libre]] de Federico Heinz 6/5/2013. ===== Prácticos ===== * {{:algo1:2013-1:digesto.pdf|Digesto}} de axiomas y teoremas para cálculo proposicional y expresiones cuantificadas. * {{:algo1:2013-2:imperativo.pdf|Digesto}} para la programación imperativa. * {{:algo1:2013-1:practico1.pdf|Práctico 1}} - Repaso cálculo proposicional y expresiones cuantificadas. * {{:algo1:2013-2:practico2.pdf|Práctico 2}} - Especificación derivación y verificación de programas funcionales. * {{:algo1:2013-2:practico3.pdf|Práctico 3}} - Introducción a la programación imperativa. * {{:algo1:2013-2:practico4.pdf|Práctico 4}} - Programación imperativa. ===== Calendario tentativo ===== * 13/8 Presentación de la materia. **Practico 1** (lógica). Expresiones Cuantificadas. * 15/8 Reglas para la cuantificación general. * 20/8 Cuantificador de conteo. Pruebas de implicaciones y por casos. * 22/8 **Practico 2** (programación funcional). Inducción. Demostración por inducción de propiedades. Esquemas de inducción (k-induccion, induccion generalizada). Inducción sobre listas. * 27/8 Derivación de recursión lineal. * 29/8 Modularización. * 3/9 Tuplas. Esquemas inductivos. * //4/9 **Corrección Proyecto 1 laboratorio**.// * 5/9 Generalizacion por abstraccion. * 10/9 Consulta. * 12/9 Segmentos. * 17/9 Semana del Estudiante. * 19/9 Semana del Estudiante. * 24/9 Repaso/Consulta. * //25/9 **Corrección Proyecto 2 laboratorio**.// * 26/9 **Parcial**. * 1/10 **Practico 3**. Modelo computacional imperativo. * 3/10 Ternas de Hoare. * 8/10 Precondición más débil (weakest precondition). * 10/10 Repetición (bucles). Teorema de la invariancia. * 15/10 Derivación imperativa (asignación e if). * //16/10 **Corrección Proyecto 3 laboratorio**.// * 17/10 Demostración con invariantes. * 22/10 Repaso/Consulta. * 24/10 **Practico 4**. Tecnicas para encontrar invariantes: termino de la conjunción. * 29/10 Técnica de reemplazo cte. por variable. * 31/10 Técnica de predicados intermedios. * 5/11 Técnica de fortalecimiento de invariantes. * //6/11 **Corrección Proyecto 4 laboratorio**.// * 7/11 Problemas de Borde. * 12/11 Consulta/Repaso. * 14/11 **Parcial**. * 19/11 Problemas de asignación de arreglos. * 21/11 Recuperatorio. * //27/11 **Corrección Proyecto 5 laboratorio**.// ===== Laboratorio ===== | ^ Enunciado ^ Teóricos ^ Fecha corrección ^ ^ Presentación | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase1_presentacion.html|Introducción a la materia]] ||| ^ 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]] | 4/9 | ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase3_haskell.html|Haskell, GHCI, secciones, map, filter]] | ::: | ^ ::: | ::: | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase4_tipos.html|Tipos, clases de tipos y más]] | ::: | ^ Proyecto 2 | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/proyectos/proy2.pdf|Proyecto 2]] | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/proy2_tiposdedatos.hs|Ejemplos tipos de datos (archivo .hs)]] | 25/9 | ^ ::: | ::: |[[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase5_tipos2.html|Tipos de datos, deriving, case, Maybe]] | ::: | ^ Proyecto 3 | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/proyectos/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]] | 16/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/~hoffmann/algo1/2013-2/proyectos/proy4.pdf|Proyecto 4]] | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/teoricos/html/clase7_c.html|Programación C, GDB]] | 6/11 | ^ Proyecto 5 | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-2/proyectos/proy5.pdf|Proyecto 5]] | [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/arreglo.c|Arreglo]], [[http://www.cs.famaf.unc.edu.ar/~hoffmann/algo1/2013-1/inicializar.c|Inicialización]]; [[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]] | 27/11 | Enunciados y teóricos del año pasado: * 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]] * 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]]. ===== Información para Docentes ===== ==== Bitácora tentativa del teórico/práctico ==== * 13/8 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. * 15/8 Reglas para la cuantificación general. * 20/8 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). * 22/8 **Practico 2**. Inducción. Demostración por inducción de propiedades. Inducción sobre listas. Hasta ej 2. * 27/8 Derivación de recursión lineal. Hasta ejercicio 4. * 29/8 Ejercicio 6 de modularización. Suma de potencias en clase. * 3/9 Tuplas (ejercicio 7.a). Esquemas inductivos con ejercicio 5. * 5/9 Generalizacion por abstraccion: ejercicio 8.a) psum. * 10/9 Ejercicio sum_ant. Consulta. Hasta ej 9. * 12/9 Segmentos. Ejercicio suma mínima de un segmento. * 17/9 Semana del estudiante. * 19/9 Semana del estudiante. * 24/9 Consulta de práctico. * 26/9 **Parcial**. * 1/10 **Practico 3** Modelo computacional imperativo. Hasta ej 2 * 3/10 Terna de Hoare. Weakesr Precondition. Wp de asignacion. Hasta ejercicio 3.e). Chun da wp del if * 8/10 wp del if. Especificación y derivación. Hasta ejercicio 5.d * 10/10 Teorema de la invariancia. Ej 5.e y f * 15/10 Derivación de asignaciones y if (ej 6 y 7). Pueden hacer hasta el ejercicio 8. * 17/10 Derivación mcd. Salte el ej 9 (arreglos) * 22/10 Ej 9. Exp de ejercicio 10 * 24/10 **Practico 4**. Tecnicas para encontrar invariantes: termino de la conjunción. Ejercicios 1 y 2 en clase. Pueden hacer hasta el 4. * 29/10 Técnica de reemplazo cte. por variable. Ej 6 y 6.a). Pueden hacer hasta ej 8 * 31/10 Técnica de predicados intermedios Ej 9 y 11.a) * 5/11 Técnica de fortalecimiento de invariantes. Ej 12 * 7/11 Problemas de Borde. * 12/11 Problemas de Borde. Consulta. * 14/11 **Parcial**. * 19/11 Problema de asignación de arreglos. Consulta. * 21/11 **Recuperatorio**.