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

 Novo   Correcção do exame da época de recurso 2000/01

[ 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.gifProvas de Avaliação | Notas Finais ]

  Equipa docente

  Horário

Ref Dia Hora Tipo Sala Cursos Docente
1 2.ª-feira 18h00-20h00 TP(1) 2.307 LESI M.A. Cunha
2 3.ª-feira 08h00-10h00 TP(2) 2.312 LESI J.C. Bacelar
3 3.ª-feira 08h00-10h00 TP(1) Anf. MICA LMCC J.B. Barros
4 3.ª-feira 10h00-12h00 TP(3) 2.311 LESI J.C. Bacelar
5 3.ª-feira 10h00-12h00 TP(2) DI-2(?) LMCC M.A. Cunha
6 3.ª-feira 16h00-17h00 T 2.A102 LESI+LMCC J.N. Oliveira
7 5.ª-feira 18h00-20h00 TP(4) 2.304 LESI M.A. Cunha
8 5.ª-feira 11h00-12h00 T 2.A102 LMCC+LESI J.N. Oliveira
9 6.ª-feira 16h00-18h00 TP(5) 2.306 LESI M.A. Cunha

  Regime de Avaliação

  Atendimento

  Sumários

  Programa Resumido

  Programa Detalhado

  1. Teoria e método em programação. 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.

  3. Estudo dos combinadores elementares de programas funcionais

    A composição f ·g como combinador elementar de funções. Associatividade da composição. Função identidade id. Estudo dos combinadores elementares de programas funcionais (cont.): Polimorfismo da função identidade. A propriedade f ·id = id ·f = f e seu diagramas comutativo. Notação funcional com ou sem variáveis.

    O combinador <f,g> e o produto A * B (analogia com «struct» em C) e suas projecções. Propriedade de cancelamento- * . O combinador [f,g] e o coproduto A + B (analogia com «union» em C) e suas injecções. Propriedades universais de <f,g> e de [f,g] e suas derivadas (cancelamento, reflexão e fusão). Os combinadores f * g e f + g . Propriedades de absorção. Propriedades functoriais.

    Apresentação da extensão Mpi.hs ao Prelude.hs do Hugs 98.

    Lei da troca. Diagrama da lei da troca. Exemplo: undistr.

  4. Isomorfismo entre tipos de dados Invertibilidade à esquerda e à direita. Funções sobrejectivas (com inversa à direita) e funções injectivas (com inversa à esquerda). Funções bijectivas ou isomorfismos. O isomorfismo A * B =B * A (swap). Outros isomorfismos célebres envolvendo produtos e coprodutos (assocr etc).

    Predicados e guardas. Condicional de McCarthy. Lei da fusão do condicional de McCarthy.

    Tipos elementares genéricos: 0 , 1 e 2 (resp. Void, () e Bool em HASKELL). Segmentos iniciais e tipos enumerados.

    Funções constantes. O combinador c . Propriedades. Polimorfismo da função constante: c = c ·f.

  5. Estudo dos combinadores avançados de programas funcionais

    Funções de ordem superior. Noção de espaço funcional. O combinador curry f e o operador ap. A exponencial B^A e seus isomorfismos (eg. curry, split, either etc). As funções ! : A ->1 e ? : 0 ->A .

    Propriedade universal de curry f e cancelamento da exponencial.

    As propriedades de fusão e reflexão da exponencial como consequência da propriedade universal de curry f . A construção f^A e a propriedade de absorção.

    Produtos e coprodutos n -ários ( n>=0 ).

  6. Introdução aos tipos de dados recursivos a partir de uma analogia com a programação imperativa

    O conceito de «apontador» 1 + A (Maybe a em HASKELL). Tipos de dados recursivos vistos como equações. As listas ligadas e a equação L =1 + A * L .

  7. Tipos indutivos de dados e seus ccombinadores

    Declaração de tipos de dados em HASKELL. Sua relação com o coproduto. Álgebra e co-álgebra do tipo indutivo definido pela equação L =1 + A * L . Isomorfismo. Introdução à observação de tipos indutivos usando como exemplo listas de inteiros: data L = Nil | Cons (Int,L) .

    Conceitos de catamorfismo e anamorfismo usando o tipo de dados exemplo listas de inteiros: data L = Nil | Cons (Int,L) . Conceito de hilomorfismo usando o tipo de dados exemplo listas de inteiros - data L = Nil | Cons (Int,L) . O factorial visto como um hilomorfismo. Cálculo de programas: eliminação da estrutura de dados intermédia de um hilomorfismo.

    Apresentação do módulo RList.hs: o algoritmo de ordenação por inserção simples como hilomorfismo sobre a estrutura RList a.

    Introdução ao tipo de dados árvores binárias simples, ou listas bi-lineares: data BTree a = Empty | Node(a, (BTree a, BTree a)). Apresentação do módulo BTree.hs. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplo: o hilomorfismo qSort (`quick sort').

  8. Introdução à parametrização e ao polimorfismo.

    Formulação de map (em [a]) e de fmap em RList como catamorfismos. Propriedades:

    fmap id = id
    fmap (f . g) = (fmap f) . (fmap g)

    Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Exemplos: functor indentidade, functor constante e a exponencial. Propriedades naturais.

    Noção de bi-functor. Propriedades. Bi-functores em HASKELL: a class BiFunctor e o operador bmap. Exemplos: functor produto e coproduto.

  9. Politipismo ou programação genérica

    Definição genérica de um tipo indutivo de dados. Parametrização. Noção de functor de base. maps são 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).

    Polimorfismo versus politipismo. Programação dita «genérica». Propriedade universal de um catamorfismo cata f do tipo genérico t a =b(a,t a) e suas derivadas: cancelamento-cata. Derivação das leis genéricas de reflexão-cata e de fusão-cata. Exemplos de aplicação. Derivação da lei genérica de absorção-cata.

    Noção de functor polinomial. Forma canónica de um functor polinomial. Lei do binómio de Newton. Noção de tipo de dados indutivo polinomial. t a1...an =b(a1,...,an,ta1...an) . Generalização da triologia cata-ana-hilo à indução polinomial.

  10. Exemplos de aplicação

    Triologia cata-ana-hilo associada ao tipo BTree - exemplos célebres: os catamorfismos de travessia (in/pre/pós-ordem). 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').

  11. Introdução ao conceito de mónada:

    Motivação e definição formal. Operadores de composição, multiplicação e aplicação monádica (`bind'). Extensão monádica de uma função. Propriedades. Mónadas em HASKELL: a class Monad e os operadores return, (»=), » e fail. Exemplos de mónadas: excepções, listas e funcionalidade de entrada/saída.

  12. Síntese final. Quadro sinóptico classificativo dos algoritmos analisados e estudados ao longo da disciplina:
    Classe B(A,X)B(A,C,X)TravessiasOrdenaçãoFactorialOutros
    RList 1 + A × X iSort fac sq
    LList 1 + X × A
    BTree 1 + A × X² in/pré/pós qSort hanoi
    LTree A + X² flatten mSort dfac fib
    FTree C + A × X²

  Trabalhos Práticos

  Material Pedagógico

No ficheiro mpi0001mp.zip encontram-se, até ao momento [data desta versão: 00.16.06]:
-
mpiCalFun.(ps|pdf) - contendo tabela de leis de cálculo funcional.
-
o ficheiro vexed.hs necessário à execução do 2.º trabalho prático.
-
os seguintes módulos de extensão ao Prelude.hs do Hugs 98 que são relevantes para esta disciplina:
-
Mpi.hs - contendo as construções base da notação adoptada, e.g. ><, -|- etc.;
-
RList.hs - contendo os cata/ana/hilo-morfismos do tipo de dados listas à direita - data RList a = Nil | Cons (a, RList a) , e aplicações suas (e.g. factorial, `insertion sort', etc);
-
BTree.hs - contendo os cata/ana/hilo-morfismos do tipo de dados árvores binárias - data BTree a = Empty | Node(a, (BTree a, BTree a)), e aplicações suas (e.g. torres de Hanói, `quick-sort', etc);
-
demoBTree.hs - contendo material auxiliar para a visualização em HTML da estrutura de dados intermédia dos hilomorfismos qSort e hanoi do módulo anterior. Experimentar qSort_in_html [6,3,9,1,7,18] e hanoi_run_in_html 7, por exemplo. Encontrar-se-á a visualização no ficheiro /tmp/_.html;
-
LTree.hs - contendo os cata/ana/hilo-morfismos do tipo de dados árvores binárias de folhas - LTree a = Leaf a | Split (LTree a, LTree a) e aplicações suas (e.g. duplo-factorial, `merge-sort', Fibonacci etc);
-
demoLTree.hs - contendo material auxiliar para a visualização em HTML da estrutura de dados intermédia dos hilomorfismos mSort, dfac e fib do módulo anterior;
-
Exp.hs - auxiliar a demoBTree.hs e demoLTree.hs;

  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.

Ol99a
J.N. Oliveira.
An Introduction to Pointfree Programming.
37p., Departamento de Informática, Universidade do Minho, 1999.

Ol99b
J.N. Oliveira.
Recursion in the Pointfree Style.
33p., Departamento de Informática, Universidade do Minho, 1999.

VB98
J.M. Valença and J.B. Barros.
Fundamentos da Computação II: Programação funcional, 206p., 1998.

  Provas de Avaliação

Época Chamada Data Hora Salas Inscritos Prova
Normal 1.ª 5.ª-feira, 11 de Janeiro 2001 09h30 2206 a 2211 91 + 288 pdf
Normal 2.ª 3.ª-feira, 30 de Janeiro 2001 14h30 2201, 2202, 2209, 2210 ... pdf
Recurso - 2.ª-feira, 03 de Setembro 2001 14h30 2203 a 2206 156 + 57 tinynew.gifpdf
Especial - 6.ª-feira, 23 de Novembro 2001 17h00 1319 16 + 4 pdf

  Notas Finais

  Notas da Época Especial

NrCoDisRegAnoNomeClass.
19667 5303O7 ORD 4 Agostinho Nuno Alves Gomes Reprovado
22648 5303O7 ORD 4 Carlos Miguel Marques Barroso Reprovado
22652 5303O7 T-E 5 Fernando Alexandre Peixoto Gomes Reprovado
24855 5303O7 T-E 2 Marlene Gil de Miranda Reprovado
22716 5303O7 ORD 5 Ricardo André Fernandes Costa Reprovado
22722 5303O7 ORD 4 Rogério Cristiano Ribeiro Martins Reprovado
22727 5303O7 T-E 5 Sérgio Manuel de Carvalho Gonçalves Reprovado
22730 5303O7 ORD 4 Sónia Marlene Rodrigues da Silva 10
30709 7003N5 T-E 2 Conceição Silva Miranda Martins Reprovado
20206 7003N5 ORD 4 Liliana Elisa da Riba Nobre Castilho Reprovado
25387 7003N5 ORD 2 Rodrigo Dinis de Freitas 11
28191 7003N5 T-E 2 Vítor Rui de Oliveira Gonçalves Reprovado

  Pauta à data Época de Recurso

NrCoDisRegAnoNomeClass.
24797 5303O7 ORD 4 Alexandre Albuquerque Rodrigues Reprovado
23259 5303O7 ORD 3 Almeno Hugo da Silva Soares Reprovado
30162 5303O7 ORD 2 André Filipe Portolada Gonçalves Lopes Reprovado
30163 5303O7 ORD 2 Ângelo Marques Oliveira Cabral Reprovado
30164 5303O7 ORD 2 Ângelo Simao Gonçalves Vilela Reprovado
22641 5303O7 ORD 3 António Manuel Pereira Costa Reprovado
30168 5303O7 ORD 2 Armindo Borges Sá Cachada 18
22643 5303O7 ORD 3 Aureliana dos Santos Pinto 10
27595 5303O7 T-E 1 Bruno José Carneiro da Silva Reprovado
30171 5303O7 ORD 2 Bruno Maciel Almeida Costa 14
30174 5303O7 ORD 2 Bruno Miguel Sá Ribeiro Silva 12
30175 5303O7 ORD 2 Bruno Pacheco Machado dos Santos Reprovado
27597 5303O7 ORD 3 Carlos Alberto da Silva Fernandes Reprovado
27599 5303O7 ORD 2 Carlos Emanuel Neves Lopes 10
30179 5303O7 ORD 2 Carlos Manuel Araújo Rodrigues 14
24755 5303O7 T-E 2 Carlos Manuel de Sá Martins 11
22648 5303O7 ORD 4 Carlos Miguel Marques Barroso Desistiu
25014 5303O7 ORD 2 Cedric Amaro Ferreira Capela 10
24813 5303O7 ORD 3 Daniel Gonçalves Pires Reprovado
27603 5303O7 ORD 2 Daniel Oliveira Silva 11
30183 5303O7 ORD 2 Domingos Viriato Ferreira Freitas 11
30184 5303O7 ORD 2 Edgar Pereira Alves 15
30186 5303O7 ORD 2 Fernando Albuquerque Rodrigues 13
22654 5303O7 ORD 3 Filipe Branco Froufe Andrade 10
24819 5303O7 ORD 2 Floriano Augusto de Oliveira Alves Reprovado
27616 5303O7 ORD 2 Francisco José Prata da Paz Reprovado
30191 5303O7 ORD 2 Helena Isabel da Cunha Lopes Reprovado
32649 5303O7 ORD 2 Hugo de Oliveira Alves Reprovado
30199 5303O7 ORD 2 Ivo Dinis Castro Rodrigues Reprovado
27619 5303O7 ORD 2 João Afonso Vieira Casal Reprovado
23943 5303O7 ORD 2 João Alberto Pereira de Araújo Reprovado
30203 5303O7 ORD 2 João Paulo dos Santos Martins 13
27625 5303O7 ORD 2 Jorge Miguel de Sousa Abreu Reprovado
24990 5303O7 ORD 3 José Alberto Alves de Melo 16
27628 5303O7 ORD 2 José Jorge Barbosa Branco Reprovado
17863 5303O7 ORD 3 José Miguel Morais Justo Reprovado
15556 5303O7 T-E 4 Juliana Maria Gomes de Sousa Reprovado
30216 5303O7 ORD 2 Lília Isidra de Barros Ferreira Reprovado
27633 5303O7 ORD 2 Luís Gomes Meireles Reprovado
30217 5303O7 ORD 2 Luís Manuel Vieira Carvalho Oliveira Reprovado
28988 5303O7 ORD 3 Luís Miguel Cardoso Fernandes 12
28989 5303O7 ORD 2 Luís Miguel dos Santos Simões Reprovado
22682 5303O7 ORD 2 Manuel José da Luz Cruz e Sousa 11
22684 5303O7 ORD 3 Marcio Alexandre Amorim Ferreira da Costa Reprovado
22685 5303O7 T-E 3 Marco Francisco da Silva Lizardo Reprovado
30221 5303O7 T-E 2 Maria Luísa do Rosario da Silva Reprovado
30222 5303O7 ORD 2 Maria Rute Moreira dos Santos Silva 12
24855 5303O7 T-E 2 Marlene Gil de Miranda Reprovado
30224 5303O7 ORD 2 Marta da Conceição Fernandes Borlido 10
22692 5303O7 ORD 2 Miguel Ângelo Rodrigues Fernandes Reprovado
24856 5303O7 T-E 2 Miguel Fernandes da Costa Reprovado
30230 5303O7 T-E 2 Moises Filipe Vieira Sequeira Reprovado
27640 5303O7 ORD 2 Mónica de La Salete Assuncao Santos Reprovado
32013 5303O7 ORD 2 Mónica Patrícia Freire do Vale Reprovado
22696 5303O7 ORD 2 Nuno Alexandre Ramos de Carvalho Reprovado
27642 5303O7 T-E 3 Nuno Edgar Ferreira dos Santos 12
30233 5303O7 ORD 2 Nuno Filipe Soares Caridade Reprovado
24279 5303O7 ORD 2 Nuno Miguel Gomes da Costa Reprovado
27648 5303O7 ORD 2 Nuno Ramos Matos Reprovado
30235 5303O7 ORD 2 Paulo Filipe Araújo da Silva 16
19740 5303O7 ORD 3 Paulo Jorge Catarino Nuno Reprovado
30236 5303O7 ORD 2 Paulo Jorge de Jesus e Silva 15
30239 5303O7 ORD 2 Paulo Reis Rodrigues 14
27655 5303O7 ORD 2 Pedro Filipe Vieira Martinho dos Reis Dias Reprovado
24938 5303O7 ORD 2 Pedro Miguel Rego de Sousa Reprovado
19748 5303O7 ORD 3 Pedro Nuno Coelho Lopes Reprovado
27660 5303O7 ORD 3 Renato Costa Neves 10
30249 5303O7 ORD 2 Ricardo Daniel da Silva Lima 16
30250 5303O7 ORD 2 Ricardo dos Santos Alves 12
22717 5303O7 T-E 3 Ricardo Jorge Bernardo de Sousa Reprovado
30251 5303O7 ORD 2 Ricardo José de Pinho Rebelo Reprovado
19753 5303O7 ORD 2 Ricardo José Guedes Ferreira Dias Desistiu
27666 5303O7 ORD 3 Ricardo Miguel Ribeiro Ferreira Reprovado
30257 5303O7 ORD 2 Rui Filipe Lima Maranhao de Abreu 13
23818 5303O7 ORD 2 Rui Filipe Tavares da Silva Reprovado
30258 5303O7 ORD 2 Rui Manuel Coimbra Oliveira Afonseca Reprovado
27675 5303O7 ORD 3 Rui Pedro Dias Pinho Reprovado
24878 5303O7 ORD 3 Rui Pedro Gouveia dos Santos Vinagre Reprovado
27676 5303O7 T-E 2 Rui Pedro Nunes Marques Reprovado
30261 5303O7 T-E 2 Sandra Catarina da Silva Bermudes Reprovado
22725 5303O7 ORD 3 Sandra Isolete Freitas Adrião Reprovado
24884 5303O7 ORD 2 Sérgio Manuel da Silva Magalhães 11
24888 5303O7 ORD 3 Sérgio Nuno Ferreira de Nóbrega Reprovado
24892 5303O7 T-E 2 Tiago José Pereira Lourenço Pinto Marques 11
27686 5303O7 ORD 2 Vasco Miguel Dias Pinto da Rocha 10
30693 7003N5 ORD 2 Adalberto Nuno da Silva Leite de Freitas Reprovado
28134 7003N5 ORD 2 Ana Catarina Fernandes Silva Reprovado
23163 7003N5 ORD 3 Ana Cláudia Barbosa de Faria 10
28136 7003N5 ORD 3 Ana Luísa Pinto Teixeira 10
18662 7003N5 ORD 4 Anabela Cardoso da Silva Reprovado
28139 7003N5 ORD 2 Ângelo Miguel Lira de Moreira Reprovado
20191 7003N5 T-E 3 António José Coutinho Barbosa 10
28141 7003N5 ORD 2 Arnaldino José Osório Pinto Reprovado
28142 7003N5 ORD 2 Artur Jorge Oliveira de Carvalho Reprovado
28146 7003N5 ORD 3 Carla Susana Dantas Teixeira Reprovado
25351 7003N5 ORD 2 Carlos Guilherme Pelaio Macedo Costa 10
21801 7003N5 ORD 3 Carlos Miguel Figueiredo Costa Reprovado
26334 7003N5 T-E 2 Catarina Jesus Lopes Ferreira Reprovado
30707 7003N5 ORD 2 Catia Vilhena 14
20195 7003N5 ORD 4 Célia Luísa Reis Pereira Reprovado
28148 7003N5 T-E 2 Cláudia Alexandrina Cerqueira Nunes Reprovado
30709 7003N5 T-E 2 Conceição Silva Miranda Martins Reprovado
23180 7003N5 ORD 2 Fernando Jorge da Silva Nogueira Reprovado
30719 7003N5 ORD 2 Filipe Leonel Ribeiro Pereira 16
28152 7003N5 ORD 2 Helder Domingos Ferreira Mendes 10
30730 7003N5 ORD 2 João Paulo de Sousa Ferreira Fernandes 14
23186 7003N5 ORD 5 Jorge Miguel Teixeira Sampaio Reprovado
28158 7003N5 ORD 2 José Augusto Alves Neves 11
23188 7003N5 ORD 3 José Manuel Certal Álvaro 14
30733 7003N5 ORD 2 José Miguel Pereira Vilaca 14
20206 7003N5 ORD 4 Liliana Elisa da Riba Nobre Castilho Reprovado
28160 7003N5 T-E 2 Lúcia Sofia de Sousa Belchior Miranda 11
28982 7003N5 T-E 3 Luís Filipe Duarte dos Santos Reprovado
28164 7003N5 ORD 2 Marcio Abel Pereira Ferreira 10
29016 7003N5 ORD 3 Marco Paulo Martins da Cruz 10
28168 7003N5 ORD 3 Maria João Fernandes Guerreiro da Silva Reprovado
23777 7003N5 ORD 3 Marlene de Jesus Camões Moura Reprovado
23198 7003N5 T-E 3 Marta Regina Carneiro da Silva Reprovado
28173 7003N5 T-E 2 Miguel Filipe Teixeira Carreira 10
25944 7003N5 ORD 2 Miguel Pedro Eiriz Gonçalves Desistiu
29060 7003N5 ORD 2 Miguel Pereira Mateus Reprovado
18702 7003N5 ORD 3 Nuno Miguel Sousa Nogueira 10
21147 7003N5 ORD 3 Patrícia Maria Alves da Silva Reprovado
23203 7003N5 T-E 3 Paulo Alexandre Afonso Dias 13
28179 7003N5 ORD 2 Raquel Maria Couto Pires Reprovado
26342 7003N5 ORD 2 Renato André Morgado Leite da Costa 11
20225 7003N5 T-E 3 Ricardo Alexandre Gaspar da Paz 10
25387 7003N5 ORD 2 Rodrigo Dinis de Freitas Reprovado
28184 7003N5 ORD 2 Rui Braga Nogueira Marques Ribeiro Reprovado
23218 7003N5 ORD 3 Susana Marisa Morais Pacheco Reprovado
25400 7003N5 ORD 3 Vania Sofia Gomes Carvalho Reprovado
28191 7003N5 T-E 2 Vítor Rui de Oliveira Gonçalves Reprovado
25403 7003N5 ORD 2 Wagner Barreto de Faria Reprovado


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


J. N. Oliveira
2002-01-13