Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== 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 <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 [[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.