Algoritmos y Estructuras de Datos I

Javier O. Blanco, 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.

• Tutorial Haskell.
• Introducción a Haskell.
• Lenguaje de Programación Funcional Haskell.
• Wikipedia.

• Tutorial Haskell.
• Manual Hugs.
• Especificación del lenguaje Haskell 98.
• En la web.

• En castellano pero básico.
• En ingles pero muy completo.
• Manual de referencia en inglés.
• Otro en castellano.

• Trampa en el cyberespacio.
• Software's Chronic Crisis.
• Implementing Functional Languages: a Tutorial. Simon L. Peyton Jones.
• Voto electrónico. Los riesgos de una ilusión. Federico Heinz.
• X11 windows manager in Haskell!.

• Práctico 1.

• Práctico 2.

• Práctico 3.

• Práctico 7.

• 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.

• 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)

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.

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.

• 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

• 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 (Cola.hs gzipeado¹⁾).

• Modulos en haskell. Declaración simple (sin exports). Uso desde otros archivos.
• Ejemplo de tipo Cola a en módulo (modulo Cola, programa que lo usa. Modulo cola implementado con dos listas, programa que lo usa).
• Explicación de foldl.

• 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.

• 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.

• 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.

• 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.

• Archivos separados.
• Arreglos en C.

• Memoria global, stack y heap.
• Variables y direcciones de memoria.
• Paso de parámetros. Variables y arreglos.

• Cadena de caracteres en C.
• Tipos abstractos de datos en C.

• Proyecto 1 - Recursión.
• Proyecto 2 - Tipos de datos creados por el usuario en Haskell.
• Proyecto 3 - TAD Diccionario en Haskell.
  • Interface - Interface para probar los Dict del proy3.
• Proyecto 4 (versión nueva) - Traducción de programas imperativos del teórico a C.
• Proyecto 5 - Programas con arreglos y TAD números complejos en C.

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.

Desde la cuenta de mail <tu-usuario>@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 webmail del FaMAF.

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.