 |
Cálculo de Programas - 2008/09
|
|
[ DI/UM ]
|
|---|
- Disponíveis em PDF
-
- t = informação teórica
por prova escrita sem consulta de acordo com regulamentação interna em
vigor (épocas normal, de recurso ou especial) -- 60%
(nota mínima: 8)
- p1 = informação prática
relativa a
um prático trabalho obrigatório a realizar por grupos de 2 alunos -- 30%
- p2 = componente de avaliação contínua
relativa à resposta dos alunos aos desafios e sugestões de estudo que vão
sendo propostos no Wiki da disciplina -- 10%
- Em qualquer altura: via correio electrónico pressionando aqui
(J.N. Oliveira) ou aqui
(Hugo Macedo).
- Sujeito a marcação verbal junto do docente responsável pela disciplina,
com um mínimo de uma semana de antecedência:
-
- Motivação.
Teoria e método em programação.
Cálculo e raciocínio sobre programas.
Composicionalidade. Combinadores de programas.
Modularidade e reutilização.
«Pacotes» de programação.
- Programação funcional: sua motivação e antecendentes históricos.
Composição de funções.
Noções de abstracção e de isomorfismo.
- Iniciação à estruturação de dados.
Combinadores básicos e suas propriedades estruturais
(reflexão, fusão, absorção, cancelamento e de functorialidade).
Álgebra de um tipo de dados.
Lei da troca.
- Introdução às estruturas de dados indutivas regulares.
Álgebras de functores.
A triologia «cata-ana-hilo».
Recursividade polinomial.
Lei de recursividade múltipla e suas aplicações na construção de algoritmos eficientes (eg. iterativas).
Caso de estudo: implementação do cálculo de séries de Taylor por algoritmos iterativos.
- Parametrização e polimorfismo.
Inferência de tipos polimórficos segundo o método Hindley-Milner.
Programação genérica.
Functores de tipo.
Introdução ao politipismo.
- Programação modular.
- Programação funcional com mónades. `Input/output'. Excepções.
- Teoria e método em programação.
Arquitectura do «software».
Composicionalidade.
Interfaces. Combinadores de programas.
«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.
- 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. Igualdade extensional.
Diagramas funcionais. Setas f : A -> B.
Notação funcional com ou sem variáveis.
- 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.
- Á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.
- 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.
- Programação com tipos de dados indutivos.
Tipos de dados recursivos vistos como equações.
Os número naturais e a equação N =1 + × N .
As listas ligadas e a equação L =1 + A × L .
Apresentação do módulo List.hs.
Estudo da triologia cata-ana-hilo associada ao tipo
List.
O algoritmo de cálculo do quadrado de um número visto como
hilomorfismo sobre a estrutura List a.
O algoritmo de ordenação por inserção simples visto como
hilomorfismo sobre a estrutura List 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: o hilomorfismo fib (série de Fibonacci) e o
hilomorfismo mSort (`merge sort').
- 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.
- 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».
- 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.
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.
- Ver Material Pedagógico.
- Em ficheiro zip
encontram-se,
até à data desta versão [2009.06.27] os ficheiros/directorias:
- ficheiro
_exp.pdf útil para a realização do exercício 6 do trabalho prático.
- ficheiros
cp0809t.* relevantes para a realização do trabalho prático
da disciplina. Começar por ler cp0809t.pdf.
- ficheiro
demos.hs - contendo
- material auxiliar para a visualização em da estrutura de
dados virtual (intermédia) dos hilomorfismos qSort, hanoi, mSort etc
das bibliotecas BTree.hs e LTree.hs.
Experimente
qSort_vtree [6,3,9,1,7,18]
e hanoi_vtree (True, 7), por exemplo. Encontrará a
visualização no ficheiro _.html da directoria corrente.
- o estudo da função fib feito nas aulas teorico-práticas, com recurso à biblioteca
System.Time.
- LTree.hs -
contendo os cata/ana/hilomorfismos 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);
- BTree.hs -
contendo os cata/ana/hilomorfismos 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);
- Exp.hs e HugsList.hs -
auxiliares a demos.hs;
- ficheiro
List.hs -
possibilitando a manipulação de listas do Haskell sob a forma de catamorfismos, anamorfismos, etc.
- ficheiro
Nat.hs - possibilitando a manipulação de números naturais em Haskell sob a forma de
catamorfismos.
- Cp.hs - contendo os combinadores de base da notação adoptada,
e.g. split, ><, -|- etc.;
- _ms.pdf - contendo os apontamentos manuscritos sobre algoritmo de Hindley-Milner;
- ficheiro cpCalFun.pdf -
contendo tabela de leis de cálculo funcional.
- Ol05
-
J.N. Oliveira.
Program Design by Calculation .
Chapters 2, 3 and 4 of draft textbook in preparation.
Departamento de Informática, Universidade do Minho, 2005. (Updated 2008)
|
Bibliografia complementar
|
-
- Bir98
-
R. Bird and O. de Moor.
Algebra of Programming .
Series in Computer Science. Prentice-Hall International, 1997.
C. A. R. Hoare, series editor.
- Bir98
-
R. Bird.
Introduction to Functional Programming
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.
- Calendário:
| Época
|
Data
|
Hora
|
Salas
|
Inscritos
|
Prova
|
|---|
| Normal |
29-Jun |
16h00-18h00 |
Sala 2203 |
- |
pdf |
| Recurso |
17-Jul |
14h00-16h00 |
Sala 1201 |
- |
pdf |
- Classificações finais:
- 23180 = 14;
25364 = F;
28162 = F;
30481 = 10;
30712 = 10;
30726 = F;
30746 = F;
30755 = 15;
31195 = F;
33691 = F;
33694 = F;
33712 = R;
35820 = F;
35857 = F;
38584 = 10;
39293 = F;
40995 = F;
41041 = 12;
42198 = R;
42211 = F;
43502 = 11;
43533 = F;
43534 = F;
43538 = F;
43545 = 13;
44633 = 12;
46222 = 16;
47401 = R;
47403 = F;
47408 = 15;
47410 = F;
47415 = 13;
47422 = R;
47424 = F;
47425 = F;
47429 = F;
48392 = 10;
48401 = F;
48406 = 10;
48408 = F;
48410 = F;
48418 = 14;
50187 = F;
50188 = 13;
50190 = F;
50192 = F;
50195 = R;
50197 = R;
50199 = F;
50200 = 10;
50201 = F;
50202 = 10;
50204 = 13;
51142 = F;
51150 = F;
51152 = F;
51155 = 13;
51157 = 14;
51163 = F;
51164 = 13;
51166 = 17;
51176 = 14;
51177 = F;
51178 = F;
52818 = F;
52853 = R;
52856 = 17;
54052 = F;
54056 = F;
54058 = F;
54073 = F.
Voltar à página principal de CP.
- Outras disciplinas leccionadas pelo DIUM
J. Nuno Oliveira
2009-07-28