Métodos de Programação I - 2006/07
[ DI/UM ]

Novo	Classificações da época especial -- ver Classificações.

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

  Equipa docente

• Teóricas: J.N. Oliveira (406006)
• Teórico-práticas: L.S. Barbosa (406023) e M.A. Cunha (406081)
• Trabalhos práticos: N. Rodrigues (nfr@di.uminho.pt). Monitor suportado pela Microsoft Portugal ao abrigo de um protocolo institucional

  Sumários

• Aulas Teóricas (pdf)

  Horário

Ref	Dia	Hora	Tipo	Sala	Cursos	Docente
1	3.ª-feira	09h00-10h00	T	CP1-A5	LESI	J.N. Oliveira
2	3.ª-feira	11h00-13h00	TP(1)	CP2-111	LESI	L.S. Barbosa
3	5.ª-feira	14h00-16h00	TP(2)	CP1-308	LESI	M.A. Cunha
4	5.ª-feira	16h00-18h00	TP(3)	CP1-308	LESI	L.S. Barbosa
5	5.ª-feira	18h00-20h00	TP(4)	CP1-308	LESI	L.S. Barbosa
6	6.ª-feira	09h00-11h00	TP(5)	CP2-111	LESI	M.A. Cunha
7	6.ª-feira	11h00-13h00	TP(6)	CP2-111	LESI	M.A. Cunha
8	6.ª-feira	16h00-17h00	T	CP1-A5	LESI	J.N. Oliveira

  Regime de Avaliação

• 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

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

  Atendimento

• Em qualquer altura: via correio electrónico (jno@di.uminho.pt), devendo ser colocado no assunto o `string' MP-I/0607;
• Sujeito a marcação verbal pelo docente respectivo, com um mínimo de uma semana de antecedência:

  Dia	Hora	Cursos	Docente
  5.ª-feira	09h00-11h00	LESI	M.A. Cunha
  6.ª-feira	14h00-16h00	LESI	M.A. Cunha
  4.ª-feira	9h00-12h00	LESI	L.S. Barbosa
  6.ª-feira	17h00-18h00	LESI	J.N. Oliveira

  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. Propriedades e teoremas grátis. Introdução ao politipismo.

• Programação funcional com mónades. `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. 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.

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.

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ónades 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ónades 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 do mónade de IO e do mónade 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.

   O mónade de (transição de) estado e sua utilização para modelar a transição de estado de um autómato, Combinação de mónades: transformadores de mónades. Mónade de estado transformado por outro mónade. Exemplo: computações com estado e IO: modelo típico de um autómato determinístico interactivo.

   Projecto de software «por camadas»: a camada puramente funcional, a camada reactiva e a camada interactiva. Exemplo de aplicação: serviço de gestão de listas de chamadas num telemóvel.

7. Programação com 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:
  • Enunciado: entrar no sistema de submissão ou consultar o material pedagógico
  • Data limite da submissão electrónica: 12 de Novembro
• Trabalho prático Nr. 2:
  • Enunciado: entrar no sistema de submissão ou consultar o material pedagógico
  • Data limite da submissão electrónica: 17 de Dezembro

  Material Pedagógico

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

  

  Os ficheiros mobile.hs, Smonad.hs e SImonad.hs que foram apresentados em aulas teóricas sobre mónades.

  

  Directoria TrabalhosP - enunciados e ficheiros relevantes para a realização dos trabalhos práticos.

  

  Directoria AulasTP - ficheiros ou textos de apoio às aulas práticas

  

  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);

  

  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;

  

  List.hs - contendo os cata/ana/hilo-morfismos do tipo de dados listas em Haskell e aplicações suas (e.g. factorial, `insertion sort', 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, `quicSort', 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 _.html;

  

  Exp.hs e HugsList.hs - auxiliares a demoBTree.hs;

  

  Nat.hs - auxiliar a RList.hs

  

  Mpi.hs - contendo as construções base da notação adoptada, e.g. ><, -|- etc.;

  

  troca.hs - contendo uma animação da lei da troca;

  

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

  FAQs

Os grupos devem consultar e participar activamente no forum que está a correr no sistema de submissão dos trabalhos práticos, onde se encontram respostas para dúvidas muito frequentes.

  Bibliografia essencial

Ol05

J.N. Oliveira.
Program Design by Calculation . Draft of textbook in preparation: chapters 2 (PDF) , 3 (PDF) and 4 (PDF) .
Departamento de Informática, Universidade do Minho, 2005.

MP04

J.C. Bacelar, L.S. Barbosa, J.B. Barros, A. Cunha, M.J. Frade, F.L. Neves, J.N. Oliveira, Jorge Sousa Pinto
Métodos de Programação I - Exercícios .
Universidade do Minho Dezembro 2004.

  Bibliografia complementar

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.

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

Calendário:

Época	Chamada	Data	Hora	Salas	Inscritos	Prova
Normal	1.ª	5.ª-feira, 11-Jan	09h30	2201 a 2208	180	pdf
Normal	2.ª	4.ª-feira, 24-Jan	09h30	2202 a 2205	180	pdf
Recurso	-	2.ª-feira, 12-Fev	14h00	2202 a 2205	352	pdf
Especial	-	3.ª-feira, 18-Set	14h00	1201, 1206, 1212	-	pdf

  Classificações

Notas finais da época especial:

Número	Aluno	Regime	Classificação
47050	Adelino Miguel Melo Pereira Portela	ORD	13
43500	Alberto Manuel da Silva Gomes	ORD	13
22641	António Manuel Pereira Costa	ORD	11
32646	Bruno Abel Tavares Guedes dos Santos Costa	T-E	R
30169	Bruno Eduardo Azevedo Gomes	ORD	F
43120	Bruno Miguel Viana Gomes	ORD	13
30176	Bruno Ricardo Duarte Magalhães	ORD	F
40644	Carlos António Vieira Silva	T-E	R
38125	Carlos César Madureira Romano	ORD	F
24654	Carlos de Sousa Cabral Brandão	T-E	F
33149	Carlos Tiago da Fonte Lapa	ORD	F
44245	Christophe de Brito Gonçalves	ORD	F
43114	Cristiano da Silva Castro	ORD	F
40646	Daniel Valadares Machado Urjais	ORD	F
26336	Duarte Nuno Alves Pereira da Rocha Martins	ORD	10
47130	Emanuel José Oliveira Braga	ORD	F
36445	Filipe Barroso de Oliveira	ORD	F
43154	Flávio Miguel Alves Lemos	ORD	F
35308	Francisco José Maio Leite	ORD	F
40634	Hermano José Pereira Andrade	ORD	R
41836	Hugo da Costa Roda	ORD	F
43144	Hugo Miguel dos Santos Areias	ORD	13
22780	Hugo Tiago da Conceição Rocha	ORD	F
43143	Igor Filipe Alves da Silva Brás	ORD	F
33168	Joana Souto de Miranda Gonzalez	ORD	R
47124	João Fernando Oliveira Branco	ORD	12
43111	João Manuel Rodrigues Ferreira	ORD	F
33171	João Miguel Mondego de Palhares Falcão	ORD	F
33172	João Miguel Raposo da Silva Marques	ORD	F
35325	João Paulo Coelho Gomes Teixeira e Oliveira	T-E	F
33173	João Paulo Minhava Peixoto Assis Cardoso	ORD	F
35832	João Pedro Gonçalves de Carvalho	ORD	10
38198	Joaquim Machado Gonçalves Sampaio	ORD	10
42158	Joaquim Vítor Araújo Oliveira	ORD	11
43098	Joel Amorim Pinho	ORD	F
43102	Jorge Amílcar da Silva Pereira	ORD	F
40682	Jorge Filipe Ferreira Barbosa	ORD	12
43103	Jorge Henrique Martins de Pinho	ORD	14
19704	Jorge Manuel Dias Pinto	ORD	F
30208	Jorge Meireles Rebelo	T-E	10
30212	José Carlos da Rocha Machado	ORD	F
33180	José Carlos Fernandes de Abreu	ORD	F
42235	José Miguel Carvalho Magalhães	T-E	F
40607	José Miguel Ferreira Vilela Marques	ORD	12
40637	José Pedro Borges Gonçalves	ORD	10
35337	José Pedro Domingues	ORD	10
33185	José Pedro Peixoto Cabral	ORD	F
38137	José Pedro Ribeiro da Araújo	ORD	10
30214	José Pedro Silva de Oliveira Carvalho	ORD	13
44525	José Pedro Vilaça Novais	ORD	R
38155	Júlio André Rodrigues Araújo	ORD	10
29238	Leandro José Devezas de Matos	ORD	F
24839	Leonor Isabel Ferreira de Melo Osório Araújo	ORD	F
40604	Luis Alexandre Ferreira da Silva Machado	T-E	R
33186	Luis Filipe Gama Pais Cabral	T-E	R
22678	Luís Filipe Lopes Alves	T-E	F
38172	Luis Tiago Afonso Mascarenhas	ORD	R
30219	Manuel Fernando Soto Maior Franqueira	ORD	F
27637	Manuel José Torres Sousa da Cunha	ORD	F
35665	Mara Diana Araújo da Silva Costa	T-E	10
24848	Márcio Alexandre Freitas Diogo	T-E	R
42102	Marco Aurélio de Melo Caldas	ORD	12
12753	Maria Luisa Villaverde Machado Fernandes Novais	T-E	F
47078	Mário Nuno Ferreira São João	ORD	F
40652	Marta de Jesus Rodrigues Fernandes	T-E	12
37047	Miguel António Barbosa Araújo	ORD	F
40677	Miguel Craveiro Martins de Almeida	ORD	F
30229	Miguel Rodrigues Marques	ORD	F
29063	Miguel Terrível Inocêncio	ORD	F
40615	Miriam Isabel Teixeira de Abreu Dias	ORD	F
30230	Moisés Filipe Vieira Sequeira	T-E	F
27640	Mónica de La Salete Assunção Santos	T-E	F
38573	Nelson Duarte Cardoso da Mota	ORD	F
33197	Nelson Sousa Dias	ORD	R
43192	Nuno André Faria Lebreiro	ORD	F
33727	Nuno Filipe Antunes da Silva	ORD	13
43179	Nuno Miguel Mendonça Coutinho Correia	ORD	12
29241	Nuno Miguel Silva da Costa	T-E	F
38120	Octávio David da Conceição Jacinto	ORD	F
22703	Paulo Carlos Barbosa Fernandes	ORD	F
34508	Paulo César Almeida de Sá	ORD	11
33207	Paulo José Pires Soares	ORD	F
47049	Paulo Rui Lopes Pereira da Silva	ORD	R
47086	Pedro André Moreira da Silva	ORD	F
40602	Pedro Daniel Gomes Baptista	ORD	R
27653	Pedro Filipe Ferreira de Sá	T-E	R
47094	Pedro Joaquim Oliveira Vilaça	ORD	F
47101	Pedro Jorge Barros Vasconcelos Guimarães	ORD	11
40613	Pedro José Aragão Henriques	ORD	10
38159	Pedro Miguel Azevedo de Oliveira	ORD	10
38154	Rafael de Castro Carreira	ORD	F
19750	Raúl Rodrigues de Castro	ORD	F
47033	Ricardo Daniel Queirós Alves	ORD	F
38129	Ricardo Gomes de Faria	ORD	10
47072	Ricardo Jorge Oliveira Tching de Magalhães Coelho	ORD	13
34435	Ricardo José Ferreira Dias de Oliveira	ORD	F
38055	Rodrigo Mucha Carvalho	ORD	14
38200	Rui Alexandre Serrano de Moura	ORD	R
36764	Rui André Ferreira Silva	ORD	F
43518	Rui António Sabino Castiço da Silva	ORD	12
22723	Rui Jorge Ferreira Teixeira	ORD	F
35371	Rui Jorge Guimarães Machado Rodrigues Valente	ORD	11
27672	Rui Miguel Loureiro Gomes Salgado	ORD	10
32015	Rui Miguel Vieira da Silva	ORD	F
30262	Sandra Heloisa Moura Ferreira	ORD	F
40678	Sérgio André da Cunha Rodrigues	ORD	10
43172	Sérgio André dos Santos Areias	ORD	11
35374	Sérgio Manuel Pereira Barreiro	T-E	F
30263	Sérgio Paulo Silva dos Santos	ORD	F
43211	Telmo Miguel Pires Pinto	ORD	11
47109	Tiago Costa Oliveira	ORD	F
41034	Tiago de Almeida Marques	ORD	10
38602	Tiago Emanuel Jerónimo Ferreira	T-E	12
40665	Tiago Gil Ribeiro Passos de Almeida	ORD	F
40673	Tiago Jorge Henriques Quintela	ORD	F
43203	Tiago Manuel Pereira de Carvalho	ORD	13
47108	Tiago Mendonça Coutinho Correia	ORD	13
47122	Victor Fernandes Malheiro	ORD	F
33282	Virgílio Abrantes Vinha	T-E	F
47064	Vítor Calvão Borges	ORD	F
30266	Vítor Carlos Teixeira Pimentel	T-E	10
35379	Vítor José Torres Videira	ORD	F
47121	Vítor Tiago Varajão Martins	ORD	R

Época	Pauta	Curso
Normal	PDF	LESI
Recurso	PDF	LESI

Voltar à página principal de MP-I.

Outras disciplinas leccionadas pelo DIUM