Métodos de Programação I - 1998/99
[ DI/UM ]

Equipa docente

• Teóricas -- J.N. Oliveira (406006)
• Teórico-práticas -- J.B. Barros (406024) e J.C. Bacelar (406052)

Horário

1 2.ª-feira 15h00-16h00 T C2/A101 LMCC J.N. Oliveira

2 2.ª-feira 16h00-18h00 TP(1) C2/111 LMCC J.B. Barros

3 3.ª-feira 16h00-17h00 T C2/A104 LESI J.N. Oliveira

4 4.ª-feira 09h00-11h00 TP(2) C2/109 LMCC J.B. Barros

5 5.ª-feira 09h00-11h00 TP(2) C2/304 LESI J.C. Bacelar

6 5.ª-feira 11h00-12h00 T C2/A104 LESI J.N. Oliveira

7 5.ª-feira 12h00-13h00 T C2/111 LMCC J.N. Oliveira

8 5.ª-feira 14h00-16h00 TP(3) C2/303 LESI J.C. Bacelar

9 5.ª-feira 16h00-18h00 TP(4) C2/305 LESI J.C. Bacelar

10 6.ª-feira 16h00-18h00 TP(5) C2/207 LESI J.C. Bacelar

Sumários

• Aulas Teóricas

Atendimento

• Em qualquer altura: via email (jno@di.uminho.pt ), devendo ser colocando no assunto o 'string' MP-I/9899; toda a resposta que tenha interesse geral será aqui afixada na secção de 'FAQ's.
• Sujeito a marcação verbal pelo docente respectivo, com um mínimo de uma semana de antecedência:

  2.ª-feira 09h00-12h30 LMCC J.B. Barros

  2.ª-feira 14h00-17h00 LESI J.C. Bacelar

  2.ª-feira 16h00-17h00 LESI+LMCC J.N. Oliveira

  3.ª-feira 17h00-18h00 LESI+LMCC J.N. Oliveira

  5.ª-feira 11h00-12h30 LMCC J.B. Barros

  5.ª-feira 11h00-13h00 LESI J.C. Bacelar

Regime de Avaliação

• Componentes:
  • t = informação teórica por prova escrita de acordo com regulamentação interna em vigor (épocas de Junho, Julho, Setembro ou Dezembro)
  • p = informação prática calculada como a média da informação relativa a:
    • 4 trabalhos práticos para realização em grupo; cada trabalho, acompanhado dum relatório sucinto, será discutido em frente ao computador com cada grupo.
• Fórmula de avaliação: a nota final nf será dada pela fórmula:

  nf = if p < 9.5 then (if t > 16 then 16 else t) else p * 0.4 + t* 0.6

  sujeita à condição:

  t >= (if (p >= 9.5) then 8.0 else 9.5)

Programa Resumido

• Introdução à programação funcional - sua motivação e antecendentes históricos.
• Iniciação à teoria dos tipos de dados. Conceito básicos. Noções de abstracção e de isomorfismo.
• Tipos de dados estruturados. Construções básicas. Propriedades functoriais, de reflexão, fusão, absorção e cancelamento. Lei da troca.
• Método Hindley-Milner para inferência de tipos.
• Introdução aos tipos de dados regulares. Recursividade polinomial. Parametrização e polimorfismo.
• Programação funcional genérica. Tipos de dados «são» functores. Álgebras de functores. Catamorfismos, anamorfismos e hilomorfismos. Functores de tipo. Politipismo.

Programa Detalhado

• Introdução à programação funcional - sua motivação e antecendentes históricos.
• Iniciação à teoria dos tipos de dados
  • Conceito de função. Domínio e codomínio. Composição de funções. Função identidade. Funções constantes. Notação sem variáveis.
  • Tipos de funções: injectivas, sobrejectivas e bijectivas. Funções parcialmente definidas. Funções estritas. Tipos de dados: noções de abstracção e de isomorfismo.
  • Tipos de dados elementares: 0 (Void), 1 (()), 2 (Bool) e Nat.
  • Construções da teoria de conjuntos usadas na estruturação dos tipos de dados.
    • Construções primitivas: produto, coproduto e exponenciação. Produto e soma de funções. Condições e condicionais. Funções de ordem superior. Currying .
    • Propriedades functoriais.
    • Propriedades de reflexão, fusão, absorção e cancelamento. Lei da troca.
• Introdução aos tipos de dados regulares.
  • Expressões polinomiais. Equações polinomiais. Recursividade polinomial.
  • Listas, árvores binárias e suas variantes.
  • Parametrização e polimorfismo.
  • Método Hindley-Milner para inferência de tipos.
• Programação funcional genérica.
  • Tipos de dados «são» functores. Noção de functor. Functores polinomais. Álgebras de functores. Tipos iniciais e terminais.
  • Esquemas de funcionalidade recursiva: catamorfismos, anamorfismos e hilomorfismos. Estruturas de dados virtuais. Functores de tipo.
  • Caso de estudo: algorítmos de ordenação.
  • Introdução ao politipismo.

Bibliografia de Apoio

Bir98

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

BdM97

R. Bird and O. de Moor.
Algebra of Programming .
Series in Computer Science. Prentice-Hall International, 1997.
C. A. R. Hoare, series editor.

VB98

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

Material Pedagógico

• Apontamentos da disciplina:
  • Capítulo 1 - págs.3-36: 90228 bytes de Postscript
  • Capítulo 2 - págs.37-52: 47845 bytes de Postscript
  ou ambos os ficheiros em formato *.tar.gz: 137876 bytes.
• Procure aqui [tgz , data desta versão: 98.12.03] os seguintes ficheiros, que contêm extensões ao Prelude.hs do Hugs 1.4 que são relevantes para esta disciplina:
  • Mpi.hs - contendo as construções base da notação adoptada, e.g. ><, -|- etc.
  • LList.hs - contendo os cata/ana/hilo -morfismos do tipo de dados listas lineares - data LList a = Nil | Cons(a,LList a), e aplicações suas (e.g. '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 suas aplicações (e.g. 'quicksort', etc).
  • LTree.hs - contendo os cata/ana/hilo -morfismos do tipo de dados árvores binárias com folhas - LTree a = Leaf a | Split (LTree a, LTree a), e suas aplicações (e.g. 'mergesort', etc).
  • FTree.hs - contendo os cata/ana/hilo -morfismos do tipo de dados árvores binárias completas - data FTree a c = Unit c | Comp (a, (FTree a c, FTree a c)), e aplicações suas.

Trabalhos Práticos

• Trabalho prático Nr. 1 (prazo de entrega: terminou a 6 de Novembro)
• Trabalho prático Nr. 2 (prazo de entrega: terminou a 2 de Dezembro)
• Trabalho prático Nr. 3 (prazo de entrega: terminou a 15 de Janeiro)
• Trabalho prático Nr. 4 (prazo de entrega: terminou a 22 de Janeiro)

FAQs

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

Lista dos alunos inscritos

A lista completa dos alunos inscritos, ordenada por CoDisc (código de disciplina) e Nome, incluindo informação sobre inscrições em exames encontra-se disponível aqui .

Provas de Avaliação

• Época Normal
  • 1.ª chamada - 6.ª-feira, 29 de Janeiro 1999, 14h30, Salas 2201 a 2206 - Prova (incluindo correcção)
  • 2.ª chamada - 3.ª-feira, 9 de Fevereiro 1999, 14h30, Salas 2201 a 2206 - Prova
• Época de Recurso - 2.ª-feira, 6 de Setembro 1999, 14h30
  • Prova
• Época Especial
  • Prova

Notas Finais

Observações:

• À data da Época Especial.
• A pauta está ordenada por CoDisc (código de disciplina) e Nome dos alunos.

(Pauta removida - contactar o docente)

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