Métodos de Programação I - 2002/03
[ DI/UM ]

Novo	Classificações dos alunos que compareceram à época especial

[ 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 | [NOVO] Notas Finais ]

  Equipa docente

• Teóricas -- J.N. Oliveira (406006)
• Teórico-práticas -- J.B. Barros (406024), J.S. Pinto (406069) e M.J. Frade (406054)

  Horário

Ref	Dia	Hora	Tipo	Sala	Cursos	Docente
1	2.ª-feira	18h00-20h00	TP(1)	CP2-307	LESI	J.S. Pinto
2	3.ª-feira	08h00-10h00	TP(2)	CP3-404	LESI	M.J. Frade
3	3.ª-feira	10h00-12h00	TP(3)	CP3-403	LESI	M.J. Frade
4	3.ª-feira	17h00-19h00	TP(1)	CP2-303	LMCC	J.S. Pinto
5	3.ª-feira	16h00-17h00	T	CP1-A3	LESI+LMCC	J.N. Oliveira
6	5.ª-feira	11h00-12h00	T	CP2-A102	LMCC+LESI	J.N. Oliveira
7	5.ª-feira	16h00-18h00	TP(2)	CP1-104	LMCC	J.S. Pinto
8	5.ª-feira	18h00-20h00	TP(3)	CP1-104	LMCC	J.S. Pinto
8	5.ª-feira	18h00-20h00	TP(4)	CP2-304	LESI	J.B. Barros

  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:
    • 3 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 email (jno@di.uminho.pt), devendo ser colocando no assunto o `string' MP-I/0203; 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	14h00-18h00	LESI+LMCC	J.S. Pinto
  2.ª-feira,3.ª-feira	12h00-13h00	LESI	M.J. Frade
  3.ª-feira	9h00-10h00	LESI	J.B. Barros
  3.ª-feira	17h00-18h00	LESI+LMCC	J.N. Oliveira

  Sumários

• Aulas Teóricas
• Aulas Práticas (M.J. Frade)

  Programa Resumido

• Motivação. Teoria e método em programação. 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 (prazo de entrega: 02.10.24)
• Trabalho prático Nr. 2 (prazo de entrega: 02.11.29)
• Trabalho prático Nr. 3 (prazo de entrega: 03.01.17)

Sumbissão electrónica de trabalhos práticos:

• Instruções: Entrar em

  http://lmf.di.uminho.pt/ nrodrigues/submit.html

  e fazer o preenchimento da CGI de acordo com as normas seguintes:
  • Um membro do grupo deverá ser eleito como porta-voz, a quem deve corresponder o nome a preencher no campo CORRESPONDING AUTHOR'S NAME e o e-mail a preencher no campo CORRESPONDING AUTHOR'S EMAIL.
  • A constituição de todo o grupo deve ser discriminada no campo AUTHORS (NAME: NUMBER;) segundo o formato sugerido, eg. Nuno Rodrigues: 26967; David Costa: 28873
  • Seleccionar o ficheiro a enviar no campo FILE.
  • Completar a submissão premindo o botão SUBMIT WORK.
  • Aguardar a confirmação automática, que será enviada para o email do porta-voz acima referido.
  • Importante:
    1. Apenas pode ser submetido um ficheiro por trabalho prático. Os vários ficheiros que compõem o trabalho devem assim ser compactados num de dois formatos admissíveis: zip ou tgz.
    2. O número gerado pelo sistema e enviado ao CORRESPONDING AUTHOR'S EMAIL é o identificador único do grupo para a apresentação oral, que deve ser cuidadosamente registado por cada grupo.
• Apoio: Nuno Rodrigues (monitor .NET), Sala 108 (DI). Horário: 2.ª e 3.ª feiras, 14h00 às 17h00. Contacto: nunorodrigues@di.uminho.pt.

  Material Pedagógico

No ficheiro mpi0203mp.zip encontram-se, até ao momento [data desta versão: 03.02.22]:

ficheiro "mobile.hs" que foi assunto da aula teórica de 2002.11.19.

ficheiro "undistr.c" contendo uma implementação «pointwise» de undistr, cf. utilização (e limitações) da programação de ordem superior e polimorfismo em C.

os ficheiros mpi0203t3.* (+ etc) necessários à execução do 3.º trabalho prático. (NB: aconselha-se a seguir o «link» HTML para obter mais informação sobre a linguagem.)

os ficheiros mpi0203t2.* (+ MonadicPComb.hs + MSPLPMAN.pdf) necessários à execução do 2.º trabalho prático.

os ficheiros mpi0203t1.* necessários à execução do 1.º trabalho prático.

ficheiro mpiCalFun.pdf - contendo tabela de leis de cálculo funcional.

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_in_html (True, 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.

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

• Período de exames: 2003.01.06 a 2003.02.22.

• Lançamento das notas no livro de termos: 2003.03.05

• Calendário:

  Época	Chamada	Data	Hora	Salas	Inscritos	Prova
  Normal	1.ª	5.ª-feira, 16 de Janeiro 2003	09h30	2201 a 2208	196 + 72	pdf
  Normal	2.ª	3.ª-feira, 4 de Fevereiro 2003	14h00	2201 a 2210	120 + 22	pdf
  Recurso	-	6.ª-feira, 21 de Fevereiro 2003	14h00	2201,2202,2210	...	pdf
  Especial	-	5.ª-feira, 11 de Setembro de 2003	14h00	...	...	...

• Alunos inscritos por chamadas.

  Notas Finais

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

Voltar à página principal de MP-I.

Outras disciplinas leccionadas pelo DIUM