Métodos de Programação I - 2003/04
[ DI/UM ]

[ 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 | Provas de Avaliação | Classificações ]

  Equipa docente

• Teóricas -- J.N. Oliveira (406006)
• Teórico-práticas -- J.C. Bacelar (406052), L.S. Barbosa (406023) e J.S. Pinto (406069)

  Horário

Ref	Dia	Hora	Tipo	Sala	Cursos	Docente
1	2.ª-feira	09h00-11h00	TP(1)	DI-1.06	LESI	J.S. Pinto
2	2.ª-feira	18h00-20h00	TP(2)	CP2-307	LESI	J.S. Pinto
3	3.ª-feira	08h00-10h00	TP(3)	CP3-404	LESI	J.S. Pinto
4	3.ª-feira	10h00-12h00	TP(4)	CP3-403	LESI	J.S. Pinto
5	3.ª-feira	14h00-16h00	TP(1)	DI-0.04	LMCC	L.S. Barbosa
6	3.ª-feira	16h00-17h00	T	CP1-A4	LESI+LMCC	J.N. Oliveira
7	4.ª-feira	08h00-10h00	TP(5)	CP1-201	LESI	J.S. Pinto
8	5.ª-feira	11h00-12h00	T	CP2-A102	LMCC+LESI	J.N. Oliveira
9	5.ª-feira	16h00-18h00	TP(2)	CP1-104	LMCC	L.S. Barbosa
10	5.ª-feira	18h00-20h00	TP(3)	CP1-104	LMCC	L.S. Barbosa
11	5.ª-feira	18h00-20h00	TP(6)	CP2-304	LESI	J.C. Bacelar

  Regime de Avaliação

• A realização dos trabalhos práticos é obrigatória, devendo ser encarada pelos trabalhadores-estudantes no contexto do respectivo Estatuto.

Componentes:

• t = informação teórica por prova escrita sem consulta de acordo com regulamentação interna em vigor (épocas normal, de recurso ou especial)
• p = informação prática calculada como a média da informação relativa a:
  • 2 trabalhos práticos propostos 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 = p * 0.4 + t * 0.6

sujeita à condição:

t >= 8.0

  Atendimento

• Em qualquer altura: via e-mail (jno@di.uminho.pt), devendo ser colocando no assunto o `string' MP-I/0304; 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:

  Dia	Hora	Cursos	Docente
  2.ª-feira	11h00-13h00	LESI	J.S. Pinto
  4.ª-feira	10h00-13h00	LESI	J.S. Pinto
  5.ª-feira	14h00-15h00	LMCC/LESI	J.N. Oliveira
  5.ª-feira	17h00-18h00	LESI	J.C. Bacelar
  6.ª-feira	8h00-11h00	LMCC	L.S. Barbosa

  Sumários

• Aulas Teóricas

  Programa Resumido

• 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.

• Inferência de tipos segundo o método Hindley-Milner.

• Introdução às estruturas de dados indutivas regulares. Álgebras de functores. A triologia «cata-ana-hilo». Recursividade polinomial. Caso de estudo: algoritmos de ordenação.

• Regras para codificação de estruturas de dados funcionais na linguagem de programação C.

• Parametrização e polimorfismo. Programação genérica. Functores de tipo. Introdução ao politipismo.

• Programação modular.

• Programação funcional com mónadas. `Input/output'. Excepções.

  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

• Trabalho prático Nr. 1 (data de entrega: 03.12.05)
• Trabalho prático Nr. 2 (data de entrega: 04.01.09)

  Material Pedagógico

Em ficheiro zip encontram-se, até à data desta versão [04.01.05] os ficheiros:

• Os ficheiros mb.hs, tlm.hs, Smonad.hs e state.hs que foram apresentados em aulas teóricas e práticas sobre mónades.
• mpi0304*.*, HaPar.hs, TDecl.hs, Picture*.pdf,eps e visual.NET.zip necessários à execução do 1.º trabalho prático e do 2.º trabalho prático. Os ficheiros mpi0304tp2a.* referem-se a uma versão actualizada do enunciado do 2.º Trabalho Prático. O pacote visual.NET.zip inclui um visualizador que lê ficheiros no formato *.bmp e *.mpb e escreve apenas no formato *.mpb (=«mp1 bitmap»). Com isto, temos não só um visualizador de bitmaps e *.mpb's mas também um conversor de bitmap para o *.bmp. Para isso basta carregar um bitmap no visualizador e guardar como *.mpb. O visualizador vem acompanhado de exemplos.
• 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, `quicort', 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_visual [6,3,9,1,7,18] e hanoi_visual (True, 7), por exemplo. Encontrará a visualização no ficheiro /tmp/_.html;
• 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. duplactorial, `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;
• 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);
• Mpi.hs - contendo as construções base da notação adoptada, e.g. ><, -|- etc.;
• ficheiro mpiCalFun.pdf - contendo tabela de leis de cálculo funcional.

  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.

Ol01a

J.N. Oliveira.
A Quick Look at Monads, 2001.
Departamento de Informática, Universidade do Minho. Chapter of book in preparation.

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

Época	Chamada	Data	Hora	Salas	Inscritos	Prova
Normal	1.ª	5.ª-feira, 22 de Janeiro 2004	14h00	2201 a 2210	223 + 54	pdf
Normal	2.ª	Sábado, 31 de Janeiro 2004	09h30	2105, 2111	101 + 31	pdf
Recurso	-	Sábado, 21 de Fevereiro 2004	09h30	2201 a 2204	...	pdf
Especial	-	3.ª-feira, 14 de Setembro de 2004	17h00	...	...	pdf

  Classificações

Informação removida (RGPD artigo 17º)

Voltar à página principal de MP-I.

Outras disciplinas leccionadas pelo DIUM