U.Minho Métodos de Programação I - 2005/06
[ DI/UM ]

 Novo  Classificações finais da época tinynew.gifespecial -- ver Classificações.

[ Contacto | Página principal
Equipa docente | Horário | Regime de Avaliação | Atendimento
Sumários | Programa Resumido | Programa Detalhado
Trabalhos Práticos | Material Pedagógico
FAQs | Bibliografia de Apoio | tinynew.gif Provas de Avaliação | tinynew.gif Classificações ]

  Equipa docente

  Sumários

  Horário

Ref Dia Hora Tipo Sala Cursos Docente
1 2.ª-feira 09h00-11h00 TP(1) DI-0.02 LESI O.M. Pacheco
2 2.ª-feira 16h00-18h00 TP(2) CP1-311 LESI O.M. Pacheco
3 3.ª-feira 08h00-10h00 TP(3) CP3-404 LESI M.A. Cunha
4 3.ª-feira 10h00-12h00 TP(4) CP3-403 LESI M.A. Cunha
5 3.ª-feira 16h00-17h00 T CP1-A4 LESI J.N. Oliveira
6 5.ª-feira 12h00-13h00 T CP2-A101 LESI J.N. Oliveira
7 5.ª-feira 16h00-18h00 TP(5) CP1-104 LESI J.C. Bacelar
8 5.ª-feira 18h00-20h00 TP(6) CP1-104 LESI J.C. Bacelar

  Regime de Avaliação

  Atendimento

  Programa Resumido

  Programa Detalhado

  1. Teoria e método em programação. Arquitectura do «software». Composicionalidade. Interfaces. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.

  2. Introdução à Programação funcional. Conceito de função. A função como contrato. Diagramas de blocos. Domínio e codomínio de uma função. Diagramas funcionais. Setas f : A -> B. Notação funcional com ou sem variáveis.

  3. Combinadores de programas funcionais. A composição f ·g como combinador elementar de funções. Associatividade da composição: Função identidade id. O polimorfismo de id e a propriedade f ·id = id ·f = f e seu diagramas comutativo.
            O combinador <f,g> e o produto A * B (analogia com «struct» em C) e suas projecções. O combinador [f,g] e o coproduto A + B (analogia com «union» em C) e suas injecções.
            Os combinadores f * g e f + g .
            Noção de isomorfismo entre tipos de dados. Funções bijectivas ou isomorfismos. Função inversa. Predicados e guardas. Condicional de McCarthy.
            Funções de ordem superior. Noção de espaço funcional. O combinador curry f e o operador ap. A exponenciação B^A e seus isomorfismos (eg. curry, split, either, etc).

  4. Álgebra da programação funcional. Propriedades universais. Propriedades de reflexão. Propriedades de cancelamento e fusão. Lei da troca. Propriedades de absorção e propriedades functoriais. Leis de fusão do condicional de McCarthy. Propriedade universal da exponenciação B^A . Leis da exponenciação (cancelamento, reflexão e fusão).

  5. Programação funcional em HASKELL e sua comparação com C. Costumização de produtos e coprodutos em HASKELL. Álgebras e coálgebras de tipos de dados. O conceito de «apontador» 1 + A (Maybe a em HASKELL). Funções parciais. Regras para codificação de estruturas de dados funcionais na linguagem de programação C.

  6. Programação funcional monádica. Motivação: funções parciais e sua composição. Manipulação de erros e mecanismos de excepção («exception handling»). Funções monádicas envolvendo listas.
            Mónadas versus functores. Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Regra geral para a composição monádica.
            Bifunctores e respectivas propriedades. Transformações naturais entre functores. Polimorfismo em HASKELL e «teoremas grátis».
            Definição formal de mónade. Composição e sua unidade. Multiplicação e suas propriedades.
            Exemplos: listas e Maybe. Mónadas em HASKELL: a class Monad e os operadores return, (»=) e ». A notação do. Introdução à notação em compreensão. A definição fmap f x = do { a <- x ; return (f a) } e sua generalização à promoção monádica de operações n-árias.
            Apresentação da mónada de IO e da mónada de estado. Noção de autómato (determinístico). Função de transição de estado e sua codificação usando exponenciais. Exemplo: autómato de gestão de uma agenda de telemóvel.

  7. Introdução aos tipos de dados indutivos. Tipos de dados recursivos vistos como equações. As listas ligadas e a equação L =1 + A * L .
            Apresentação do módulo RList.hs. Estudo da triologia cata-ana-hilo associada ao tipo RList. O algoritmo de cálculo do quadrado de um número visto como hilomorfismo sobre a estrutura RList a. O algoritmo de ordenação por inserção simples visto como hilomorfismo sobre a estrutura RList a.
            Introdução ao tipo de dados árvores binárias simples, ou listas bi-lineares. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplo: o hilomorfismo qSort (`quick sort').
            Estudo da triologia cata-ana-hilo associada ao tipo LTree. Exemplos: os hilomorfismos dfac (duplo factorial) e fib (série de Fibonacci). O hilomorfismo mSort (`merge sort').

  8. Definição genérica de um tipo indutivo de dados. Noção de functor de base. Operadores fmap vs catamorfismos: Politipismo da definição t a =b(a,t a) de um tipo indutivo genérico paramétrico. Noção de functor de tipo e sua formulação genérica como o catamorfismo t f =cata (in ·b(f,id)).
            Propriedade universal de um catamorfismo cata (f) do tipo genérico t a =b(a,t a) e suas derivadas: cancelamento-cata e reflexão-cata.

  9. Classificação algorítmica. Quadro sinóptico dos principais algoritmos analisados e estudados ao longo da disciplina. Polimorfismo versus politipismo. Programação dita «genérica».

  Trabalhos Práticos

  Material Pedagógico

  FAQs

Carregar aqui para obter respostas às dúvidas mais frequentes da disciplina.

  Bibliografia de Apoio

Bir98
R. Bird.
Introduction to Functional Programming Using Haskell .
Series in Computer Science. Prentice-Hall International, 2nd edition, 1998.
C. A. R. Hoare, series editor.

Hu00
P. Hudak.
The Haskell School of Expression - Learning Functional Programming Through Multimedia .
Cambridge University Press, 1st edition, 2000.
ISBN 0-521-64408-9.

MP04
J.C. Bacelar, L.S. Barbosa, J.B. Barros, A. Cunha, M.J. Frade, F.L. Neves, J.N. Oliveira, Jorge Sousa Pinto
Métodos de Programação I - Exercícios .
Universidade do Minho Dezembro 2004.

Ol05
J.N. Oliveira.
Program Design by Calculation . Draft of textbook in preparation: chapters 2 (PDF) , 3 (PDF) and 4 tinynew.gif(PDF) .
Departamento de Informática, Universidade do Minho, 2005.

VB00
J.M. Valença and J.B. Barros.
Fundamentos da Computação II: Programação funcional.
Universidade Aberta, 2000.
ISBN 972-674-318-4, 234 p.

  Provas de Avaliação

Calendário:
Época Chamada Data Hora Salas Inscritos Prova
Normal 1.ª 3.ª-feira, 10 de Janeiro 2006 14h00 2201 a 2210 135 pdf
Normal 2.ª 4.ª-feira, 25 de Janeiro 2006 09h30 2201 a 2210 186 pdf
Recurso - 2.ª-feira, 13 de Fevereiro 2006 09h30 2202 a 2205

pdf

  Classificações
[ Informação removida (RGPD artigo 17º) ]


Voltar à página principal de MP-I.
Outras disciplinas leccionadas pelo DIUM


J. Nuno Oliveira 2006-11-03