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

 Novo   Classificações 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 essencial | Bibliografia complementar
Provas de Avaliação | tinynew.gif Classificações ]

  Equipa docente

  Sumários

  Horário

Ref Dia Hora Tipo Sala Cursos Docente
1 3.ª-feira 09h00-10h00 T CP1-A5 LESI J.N. Oliveira
2 3.ª-feira 11h00-13h00 TP(1) CP2-111 LESI L.S. Barbosa
3 5.ª-feira 14h00-16h00 TP(2) CP1-308 LESI M.A. Cunha
4 5.ª-feira 16h00-18h00 TP(3) CP1-308 LESI L.S. Barbosa
5 5.ª-feira 18h00-20h00 TP(4) CP1-308 LESI L.S. Barbosa
6 6.ª-feira 09h00-11h00 TP(5) CP2-111 LESI M.A. Cunha
7 6.ª-feira 11h00-13h00 TP(6) CP2-111 LESI M.A. Cunha
8 6.ª-feira 16h00-17h00 T CP1-A5 LESI J.N. Oliveira

  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. Análise de requisitos e sua captação funcional. Exemplo: gestão de listas de chamadas num telemóvel. Concepção composicional e reutilizaçã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.

  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ónades 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ónades 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 do mónade de IO e do mónade 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.

    O mónade de (transição de) estado e sua utilização para modelar a transição de estado de um autómato, Combinação de mónades: transformadores de mónades. Mónade de estado transformado por outro mónade. Exemplo: computações com estado e IO: modelo típico de um autómato determinístico interactivo.

    Projecto de software «por camadas»: a camada puramente funcional, a camada reactiva e a camada interactiva. Exemplo de aplicação: serviço de gestão de listas de chamadas num telemóvel.

  7. Programação com 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

Os grupos devem consultar e participar activamente no forum que está a correr no sistema de submissão dos trabalhos práticos, onde se encontram respostas para dúvidas muito frequentes.

  Bibliografia essencial

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

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.

  Bibliografia complementar

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.

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.ª 5.ª-feira, 11-Jan 09h30 2201 a 2208 180 pdf
Normal 2.ª 4.ª-feira, 24-Jan 09h30 2202 a 2205 180 pdf
Recurso - 2.ª-feira, 12-Fev 14h00 2202 a 2205 352 pdf
Especial - 3.ª-feira, 18-Set 14h00 1201, 1206, 1212 - pdf

  Classificações

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


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


J. Nuno Oliveira 2007-09-21