====== Algoritmos y Estructuras de Datos I ====== ===== Novedades ===== ===== Docentes ===== Javier O. Blanco, [[http://www.cs.famaf.unc.edu.ar/~damian|Damián Barsotti]], Silvina Smith, Valeria Rulloni, Martín Dominguez, Walter Alini, Natalia Bidart, Sergio Giro, Mariana Badano, Avalos Ambroggio Santiago, Dionisio E Alonso, Leonardo Rodriguez, Marco Brunello, Florencia Mihaich, Raul Monti. ===== Parciales ===== ==== Calendario ==== ==== Consultas ==== ==== Notas ==== ===== Bibliografía ===== /* * [[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 ==== === Español === * [[http://www.lcc.uma.es/~blas/pfHaskell/gentle/index.html|Tutorial Haskell]]. * [[http://horru.lsi.uniovi.es/~labra/FTP/IntHaskell98.pdf|Introducción a Haskell]]. * [[http://www.frt.utn.edu.ar/sistemas/paradigmas/Haskell.htm|Lenguaje de Programación Funcional Haskell]]. * [[http://es.wikipedia.org/wiki/Haskell|Wikipedia]]. === Inglés === * [[http://www.haskell.org/tutorial/|Tutorial Haskell]]. * [[http://cvs.haskell.org/Hugs/pages/users_guide/index.html|Manual Hugs]]. * [[http://www.haskell.org/haskellwiki/Language_and_library_specification|Especificación del lenguaje Haskell 98]]. * [[http://www.haskell.org/learning.html|En la web]]. ==== Lenguaje C ==== * {{algo2:cursc.html | En castellano pero básico}}. * [[http://www.cs.cf.ac.uk/Dave/C/ | En ingles pero muy completo]]. * [[http://www.space.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.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]]. * {{algo1:2007:pjlester.ps.gz|Implementing Functional Languages: a Tutorial.}} Simon L. Peyton Jones. * [[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!]]. ===== Prácticos ===== * {{:algo1:2009:2009pra1.pdf|Práctico 1}}. * {{:algo1:2009:2009pra2.pdf|Práctico 2}}. * {{:algo1:2009:2009pra3.pdf|Práctico 3}}. * {{:algo1:2009:2009pra7.pdf|Práctico 7}}. ===== Laboratorio ===== ==== Modalidad ==== === Generalidades === * El taller se reliza en dos comisiones. Los horarios de ellas son: lunes de 9 hs a 13 hs y de 14 a 18 hs. Cada alumnos debe inscribirse en una en el despacho de alumnos. * Los teóricos del laboratorio se dictan los jueves en el horario del teórico/práctico (en la misma aula). * El taller consiste en la realización de una serie de proyectos. * Los contenidos necesarios para su realización serán impartidos en los teóricos del taller. * Los proyectos podrán ser consultados en los laboratorios del taller. * La realización de los mismos es grupal. Los grupos son de 4 personas. Los grupos permanecen fijos para todos los proyectos. * Cada grupo tendrá un ayudante asignado. Los ayudantes harán un seguimiento de los proyectos. * Existen horarios reservados para práctica libre en el laboratorio los martes y jueves de 14 hs. a 18 hs. === Criterios generales para la corrección de proyectos === *** Los proyectos se evaluarán de forma individual aunque su realización haya sido grupal.** Las posibles notas son las siguientes: * **B+** (superó los objetivos que se plantearon para el proyecto, por ejemplo, haciendo una implementación novedosa) * **B** (cumplió con todas las pautas estipuladas para el proyecto) * **B-** (el proyecto funciona, pero se evidencia cierta inseguridad en las respuesta) * **R** (El proyecto no fue implementado en su totalidad, o las respuestas son poco precisas) * **M** (no presentó el proyecto, o lo presento y no conoce la resolución del mismo) ==== Bitácora de clases ==== === 13/8 : === Modelo computacional (introduccion): evaluacion lazy e eager. Expresiones que tienen forma normal en una pero no en la otra. Ejemplo: mult inf 0 con la definicion mult x 0 = 0 mult y (x+1) = y + mult y x Clases en haskell: sintaxis para instanciar en una clase, ejemplo con clase Show para mostrar numeros expresados como data Natural = Cero | Sucesor Natural en la forma estandar 0, 1, ... Definicion de la funcion naturalAInt que realiza esta transformacion. Consulta de la tarde: implementacion de las conceptos introducidos en la clase de la mañana. Repaso de currificación y filter. === 18/8: === Funcion foldr: - foldr como formalizacion de la definicion inductiva (captura la manera en la que definimos inductivamente las funciones) - foldr como homomorfismo (reemplaza [] por c y (:) por f) - foldr como mecanismo de iteracion estructurado (empezando por c, reemplaza este valor por f x (foldr f c xs), hasta que la lista termina) Por consulta de un alumno, resolvi el ejercicio de la funcion primIgualesA en el pizarron. === 27/8: === ==Tipos de datos definidos por el usuario == * Tipo sinónimo. * Valores y expresiones. Representación computacional. * Tipos enumerados. Ejemplo tipo ''Color''. * Tipos polimórficos simples. Ejemplo tipo ''Punto a''. Bibliografía : [[http://www.lcc.uma.es/~blas/pfHaskell/gentle/goodies.html]] === 3/9: === == Tipos de datos definidos por el usuario (2da parte)== * Tipos de datos recursivos. Ejemplos de ''Lista a'' y ''Arbol a'' (árbol con información en las hojas). * Modulos en haskell. Ejemplo de ''Cola a'' ({{:algo1:2009:cola1.hs.gz|Cola.hs gzipeado}}((Para descomprimirlo usar el comando ''gunzip''.))). === 10/9: === * Modulos en haskell. Declaración simple (sin exports). Uso desde otros archivos. * Ejemplo de tipo ''Cola a'' en módulo ({{:algo1:2009:cola1.hs.gz|modulo Cola}}, {{:algo1:2009:maincola1.hs.gz|programa que lo usa}}. {{:algo1:2009:colaadt2.hs.gz|Modulo cola implementado con dos listas}}, {{:algo1:2009:maincolaadt.hs.gz|programa que lo usa}}). * Explicación de ''foldl''. === 17/09: == * Principios de ingeniería del software que resuelven los TADs: abstracción, ocultamiento de información, modularidad. * Ejemplo de diferentes implementaciones de un mismo TAD: cola con un datatype isomorfo a lista, y cola con dos listas. * Introducción al proyecto 3 (poquito porque se hizo la una y empezaron a guardar los útiles). * Consulta de la tarde: probar las dos implementaciones del TAD "cola" en máquina. === 8/10 === == Primera clase de C == * Programas compilados: programar entrada/salida. * Traducción de GCL (guarded command language) a C. Solo asignación, skip e if con dos guardas (lo demás no se dió en el teórico). * Ejemplo de cálculo de mínimo. * Estructura básica de un programa en C. * Expresiones y tipos en C. === 15/10 === * Estructura de un programa simple. * Directivas de preprocesamiento. * Definición de constantes con ''#define''. * Inclución de archivos con ''#include''. * Traducción de ''If'' y bucles con muchas guardas. * Gramática de lenguaje C. * Asignación múltiple. === 22/10 === * Funciones en C. * Modularización (dividir y venceras) y reuso. * Gramática C. * Procedimientos. * Sinónimo de tipos. * Tipo ''bool'' * Registros o estructuras en C. === 29/10 === * Archivos separados. * Arreglos en C. === 5/11 === == Modelo de memoria == * Memoria global, stack y heap. * Variables y direcciones de memoria. * Paso de parámetros. Variables y arreglos. === 12/11 === * Cadena de caracteres en C. * Tipos abstractos de datos en C. ==== Proyectos ==== * {{:algo1:2009:proy1.pdf|Proyecto 1}} - Recursión. * {{:algo1:2009:proy2.pdf|Proyecto 2}} - Tipos de datos creados por el usuario en Haskell. * {{:algo1:2009:proy3.pdf|Proyecto 3}} - TAD Diccionario en Haskell. * {{:algo1:2009:interface.tar.gz|Interface}} - Interface para probar los Dict del proy3. * {{:algo1:2009:proy4.pdf|Proyecto 4 (versión nueva)}} - Traducción de programas imperativos del teórico a C. * {{:algo1:2009:proy5.pdf|Proyecto 5}} - Programas con arreglos y TAD números complejos en C. ==== Condiciones para rendir libre el taller ==== Para rendir el taller se deberá presentar 5 dias hábiles antes de rendir el examen: * Una carpeta por cada proyecto del taller de la materia. * Cada carpeta debe contener: * Título del proyecto. * Una sección por cada ejercicio. * Cada seccion debe contener las siguientes subsecciones: * Enunciado del proyecto. * El programa resultado escrito en el formalismo del teórico. * La demostración o derivación de este resultado. * El programa resultado escrito en el lenguaje de programación correspondiente. * Este debe ser el mismo programa que el del item anterior. Es decir debe ser una traducción del anterior. * Si el ejercicio tiene preguntas, se deberá agregar una nueva subsección con las preguntas y las respuestas correctas. * Cualquier otro agregado que crea conveniente para la correcta interpretación del trabajo. * Se deben hacer todos los puntos extras o ejercicios estrella del proyecto. * Se deberá entregar además un CD o disquette con todos los programas de los proyectos. * Los programas de cada proyecto deberán estar en un directorio separado cuyo nombre deberá ser el numero del proyecto. * Se pueden crear subdirectorios para cada ejercicio si lo considera necesario. * Los programas deben poder compilar sin ningún problema y deben coincidir con los de las carpetas. * Para el caso de programas en C, deben poder compilar sin "warnings" con las directivas -Wall -ansi -pedantic. * Si todos los resultados presentados en las carpetas y el CD o disquette son correctos y cumplen con todos los requisitos anteriores entonces el alumno pasará a un examen oral. Este examen se realizará en un horario a convenir con los profesores de la materia. ===== Instrucciones para inscribirse en la lista de mails ===== Desde la cuenta de mail @famaf.unc.edu.ar enviar un mail a: alualgo1-join@famaf.unc.edu.ar con cualquier subject o cuerpo del mail. Después de enviarlo debe llegar un mail donde diga que la subscripcion fue realizada correctamente. Hacer un reply con el mismo subjet (pero que no diga Re: ---). Todo esto hay que hacerlo desde el [[http://webmail.famaf.unc.edu.ar/|webmail del FaMAF]]. === ¡¡ Tener en cuenta !! === Si se cometió un error el sistema enviará un mail avisando. Por lo cual, siempre lea el mail de respuesta a la inscripción y verifique que no hubo un error. Si es así, repita el proceso. Cualquier problema consultar con los administradores del laboratorio.