nota de régimen interior - CES Felipe II

INDICE
1. Objetivos del programa ESTA ASIGNATURA OPTATIVA VA DIRIGIDA A ALUMNOS DE SEGUNDO O TERCER CURSOS
DE INGENIERÍA TÉCNICA DE INFORMÁTICA DE SISTEMAS DEL CES FELIPE II, QUE
HABRÁN RECIBIDO UN CURSO DE INTRODUCCIÓN A LA PROGRAMACIÓN EN ESTILO
IMPERATIVO Y ESTARÁN ESTUDIANDO SIMULTÁNEAMENTE, O HABRÁN ESTUDIADO EN EL
CURSO ANTERIOR, UNA ASIGNATURA DE ESTRUCTURAS DE DATOS. El objetivo principal del curso es dar a conocer el paradigma funcional y
proporcionar al alumno la capacidad de diseñar algoritmos y estructuras de
datos funcionales, poniendo un énfasis en el uso sistemático de la
recursión y en sus técnicas de razonamiento asociadas. Comenzaremos con unos temas introductorios relativos al paradigma funcional
y los distintos tipos y estructuras de datos, para centrarnos
posteriormente en los capítulos principales dedicados al diseño de
algoritmos recursivos sobre números, listas, vectores y árboles.
Adicionalmente trataremos de abordar dos temas de especial interés: la
programación de orden superior, que añade un factor más de modularidad y
reusabilidad al paradigma funcional, y la programación monádica. Existen diversos lenguajes funcionales (LISP, SCHEME, etc.) pero
utilizaremos como lenguaje de referencia de este curso Haskell 98. 2. Temario
TEMA 1 INTRODUCCIÓN.
Diferencias entre el paradigma funcional y el imperativo Convenios
léxicos y sintácticos. Tipos de datos básicos y operaciones con
ellos. Definición de funciones simples. Mecanismo básico de
evaluación. Tema 2 Sistema de tipos.
Tipos monomórficos, polimórficos y sobrecargados. Sistema de clases
en Haskell. Definición de concreciones de una clase. Creación de
nuevas clases. Tema 3 Recursión sobre números.
Principio de inducción sobre los naturales. Definiciones recursivas
y corrección de las mismas. Definiciones mediante guardas.
Definiciones locales. Coste de los algoritmos recursivos.
Tema 4 Tipos estructurados.
Tuplas, listas, el tipo Array, tipos definidos por el usuario.
Definiciones mediante patrones. Principio de inducción estructural.
recursión sobre listas y vectores. Tema 5 Programación recursiva con listas y vectores.
Recorridos, búsquedas, algoritmos de ordenación. Parámetros
acumuladores. Búsqueda dicotómica en un vector ordenado. Coste de
los algoritmos. Tema 6 Programación recursiva con árboles.
Árboles binarios y n-arios. Funciones simples sobre árboles.
Árboles de búsqueda y sus operaciones. Árboles montículo. Árboles
de Huffman.
Tema 7 Funciones de orden superior.
Concepto. Currificación, secciones y funciones anónimas. Funciones
de orden superior para listas. Listas intensionales. Algoritmos que
utilizan exclusivamente orden superior. Funciones de orden superior
para otros tipos de datos. Tema 8 Programación monádica
Programación monádica: la clase Monad y sus operaciones. La mónada
de entrada/salida. Programación interactiva en Haskell. Otras
mónadas: la mónada Maybe, la mónada de estado, etc. Programación
con vectores mutables. Este temario recoge los puntos que se tratarán a lo largo del curso, aunque
el orden y la agrupación de los mismos podrá variar en función del
profesor. 3. Desarrollo de la asignatura La asignatura se impartirá casi totalmente en el aula, sin una separación
estricta entre clases teóricas y clases de problemas. La exposición de los
temas del programa se irá intercalando en las clases con el planteamiento y
resolución de ejercicios y problemas de programación. En principio, no se han planificado sesiones de laboratorio regulares para
esta asignatura. No obstante, si el desarrollo del curso lo permitiese, se
dedicaría alguna hora a la realización de prácticas sencillas en
Laboratorio, supervisadas por el profesor, con en el intérprete Hugs 98 del
lenguaje funcional Haskell. Esta herramienta es de dominio público y ya se
puede descargar desde la página web indicada en el punto 6. 4. Forma de evaluación El método de evaluación estará basado en un único examen final que cubrirá
todos los temas del programa. Adicionalmente, y con carácter opcional, se realizará una prueba parcial de
una hora de duración basada en los ejercicios realizados periódicamente. La nota de la asignatura coincidirá con el resultado del examen final,
salvo para aquellos alumnos que decidan realizar el examen parcial y
obtengan en dicho examen mejor calificación que en el examen final. Este
caso, en el cálculo de la nota final pesará un 75% la calificación del
examen final y un 25% la del examen parcial. 5. Bibliografía
Básica
Bird, R. "Introducción a la Programación Funcional con Haskell", 2ª ed.
Prentice Hall, 2000. ISBN: 84-8322-176-4
Complementaria
Rabhi, F., Lapalme, G. "Algorithms: A Functional Approach". Addison-Wesley,
1999. ISBN: 0-201-59604-0 Thompson, S. "Haskell. The Craft of Functional Programming", 2ª ed. Addison-
Wesley , 1999. ISBN: 0-201-34275-8 6. Enlaces de interés en Internet The Haskell Home Page, http://www.haskell.org/
Hugs. Evaluador de Haskell, http://www.haskell.org/hugs
CES Felipe II, www.cesfelipesegundo.com
Universidad Complutense de Madrid, www.ucm.es
Facultad de Informática, UCM, www.fdi.ucm.es La información actualizada sobre esta asignatura se encuentra disponible en
www.cesfelipesegundo.com
----------------------- PROGRAMA DE ASIGNATURA
CURSO ACADÉMICO 2001/02
Fecha de Edición: 14/11/2001
Área de Titulación: Ingeniería Técnica en Informática de Sistemas Asignatura: PROGRAMACIÓN FUNCIONAL
Curso:
Duración (Anual/Cuatrimestral): Cuatrimestral
Carácter: Optativa
Créditos: 4,5