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

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

Voltar à página principal de MP-I.

Outras disciplinas leccionadas pelo DIUM