====== Algoritmos y Estructuras de Datos I ====== {{ :algo1:portada.jpg?150 }} ===== 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 ===== /* * 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 segundo cuatrimestre del año 2013. ===== Parciales ===== * Notas primer parcial {{:algo1:2014-1:algoritmos_i_2014_primer_cuatrimestre_-_teorico.pdf|}}. /* * Notas segundo parcial {{:algo1:2013-2:algoritmos_i_2013_segundo_cuatrimestre_-_teorico_par2_full2.pdf|}}. * Recuperatorio y condición final teórico {{:algo1:2014-1:algoritmos_i_2014_primer_cuatrimestre_-_teorico-recup.pdf|}}. */ * Condicion Final {{:algo1:2014-1:algoritmos_i_2014_primer_cuatrimestre_-_teorico_final.pdf|}}. /* * 25/4 y 17/6 * Recuperatorio 24/6. */ ===== Finales ===== * {{:algo1:2014-1:algoritmos_i_2014_primer_cuatrimestre_-_final1.pdf|Final 1}}. * {{:algo1:2014-1:algoritmos_i_2014_primer_cuatrimestre_-_final2.pdf|Final 2}}. * {{:algo1:2014-1:algoritmos_i_2014_primer_cuatrimestre_-_final3.pdf|Final 3}}. ===== 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. /* * 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**. */ ===== 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:2014-1:digesto.pdf|Digesto}} de axiomas y teoremas para cálculo proposicional y expresiones cuantificadas. * {{:algo1:2014-1:imperativo.pdf|Digesto}} para la programación imperativa. * {{:algo1:2014-1:practico1.pdf|Práctico 1}} - Repaso cálculo proposicional y expresiones cuantificadas. * {{: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. ===== 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 | [[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]] | 26/3| ^ ::: | ::: | [[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)]] | 23/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]]| 14/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]]| 4/6| ^ Proyecto 5 | [[http://www.cs.famaf.unc.edu.ar/~mdoming/docencia/algo1/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]]| 25/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]]. ===== 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**.