Cálculo de Programas - 2006/07
[ 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 |
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)

  Sumários

• Aulas Teóricas (pdf)

  Horário

Ref	Dia	Hora	Tipo	Sala	Cursos	Docente
1	2.ª-feira	15h00-16h00	T	CP2 104	LCC	J.N. Oliveira
2	3.ª-feira	10h00-11h00	TP(1)	DI A1	LCC	L.S. Barbosa
3	3.ª-feira	11h00-13h00	P(1)	DI A1	LCC	L.S. Barbosa
4	4.ª-feira	10h00-11h00	TP(2)	DI A1	LCC	L.S. Barbosa
5	4.ª-feira	11h00-13h00	P(2)	DI A1	LCC	L.S. Barbosa
6	5.ª-feira	16h00-17h00	T	CP1 A5	LCC	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 teórico-prática calculada como a média da informação relativa a:
    • 2 trabalhos teórico-práticos a realizar por grupos de 2 alunos.

• Fórmula de avaliação: a nota final nf será dada pela fórmula:

  nf = p * 0.2 + t * 0.8

  sujeita à condição:

  t >= 8.0

  Atendimento

• Em qualquer altura: via correio electrónico (jno@di.uminho.pt), devendo ser colocado no assunto o `string' CP/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-10h00	LCC	J.N. Oliveira
  4.ª-feira	08h00-10h00	LCC	L.S. Barbosa

  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. 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 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').

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

8. 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».

9. 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ónada. 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. Exemplo: autómato de gestão de uma agenda de telemóvel.

   A mónada de (transição de) estado e sua utilização para modelar a transição de estado de um autómato, 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.

  Trabalhos Práticos

• Trabalho prático Nr. 1: o enunciado está no ficheiro cp0607t1.pdf da directoria TP1 do material pedagógico.
• Trabalho prático Nr. 2: o enunciado está no ficheiro cp0607t2.pdf da directoria TP2 do material pedagógico.

  Material Pedagógico

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

O ficheiro AulaMonadsJun07.hs demonstrado nas aulas práticas.

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

TP2 - directoria contendo material para realização do 2.º trabalho teorico-prático, incluindo manual do xypic.

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;

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;

TP1 - directoria contendo material para realização do 1.º trabalho teorico-prático, incluindo manual do xypic.

ficheiro List.hs - apresentando a manipulação de listas do Haskell sob a forma de catamorfismos

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

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

  Bibliografia essencial

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.

  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.ª	11-Jun	14H00	2303, 2304		pdf
Normal	2.ª	26-Jun	14H00	2303, 2304		pdf
Recurso	-	18-Jul	09H30	1103, 1104		pdf
Especial	-	3.ª-feira, 18-Set	14h00	1201, 1206, 1212	-	pdf

  Classificações

Notas da época special:

Número	Aluno	Regime	Curso	Classificação final
35804	Ângelo David Soares Perez Dias	ORD	LCC	F
43542	Bruno Miguel Cálix Esteves Lopes	ORD	LCC	11
30713	Eduardo Gandarela de Lima	T-E	LMCC	F
39496	Filipe Miguel Torres Falcão	ORD	LCC	11
30726	Henrique José de Jesus Rodrigues	ORD	LCC	F
43544	Hugo Manuel Sousa Ribeiro	ORD	LCC	R
35842	Katia Marina Ferreira da Silva	ORD	LCC	F
43510	Paulo Manuel de Oliveira Gomes	ORD	LCC	F
39837	Rui Miguel Pacheco Almeida	ORD	LMCC	11
43501	Vânio Miguel Rodrigues Ferreira	ORD	LCC	10

Notas finais (Julho 2007):

Número	Aluno	Regime	Curso	Classificação final
39293	Adérito Francisco Silves Ferreira Carvalho de Melo	T-E	LCC	F
41029	Adriana Sucena Santos	MEL	LMCC	14
43496	Ana Isabel Pinto Monteiro dos Santos	ORD	LCC	13
43540	Ana Sofia da Silva Duarte	ORD	LCC	13
43527	Anabela Azevedo Lima	T-E	LCC	12
47414	André da Silva Rocha	ORD	LCC	F
40997	André Feliciano Quintas da Silva Coelho	ORD	LCC	13
48407	André Filipe Ferreira de Araújo Barbosa	ORD	LCC	10
41037	André Vilas Boas da Costa	ORD	LCC	10
35804	Ângelo David Soares Perez Dias	ORD	LCC	R
23168	Ari Alexandre Pereira da Silva	ORD	LCC	F
43502	Arsénio Miguel Santos Costa	ORD	LCC	F
39838	Bruno Edgar Almeida Soares	ORD	LCC	10
43543	Bruno Henrique Lourenço Ferreira	ORD	LCC	11
43542	Bruno Miguel Cálix Esteves Lopes	ORD	LCC	R
33691	Carlos Filipe Lima Duarte	ORD	LCC	F
16326	Carlos Manuel Areias da Silva	ORD	LCC	F
41020	Carlos Manuel Ferreira Lopes	ORD	LCC	13
35812	Carlos Manuel Gomes Vilhena	ORD	LMCC	16
47402	Carlos Miguel da Silva Brandão	ORD	LCC	10
43514	César Carlos Martins Gomes	ORD	LCC	11
33694	César Miguel Vieira Martins	ORD	LCC	F
48405	Christophe Campos Peixoto	ORD	LCC	R
48390	Daniel Tiago Rodrigues Braga	ORD	LCC	16
30711	Dario da Chão Samico	ORD	LMCC	F
43509	Dave Lage Moderno	ORD	LCC	16
30712	David José Macedo Guimarães	T-E	LCC	F
47425	Diogo Frederico Andrade Murteira	ORD	LCC	F
30713	Eduardo Gandarela de Lima	T-E	LMCC	F
47420	Eduardo Jorge Araújo da Costa	ORD	LCC	R
28892	Emanuel de Araújo Gonçalves	T-E	LCC	F
30717	Fernando Pedro Viana Morais	ORD	LMCC	10
47405	Filipe Daniel Vieira da Silva	ORD	LCC	15
39496	Filipe Miguel Torres Falcão	ORD	LCC	(t)
43534	Francisco Manuel Pereira da Cunha	ORD	LCC	F
41038	Hélder Nuno Ribeiro Macedo	ORD	LCC	12
30726	Henrique José Jesus Rodrigues	ORD	LCC	R
42817	Hugo Adriano Ferreira Maia	ORD	LCC	19
43544	Hugo Manuel Sousa Ribeiro	ORD	LCC	R
42201	Humberto Domingues da Mota Longo	ORD	LCC	10
43526	Isac Lima Nunes	ORD	LCC	11
42198	Ivan Romeu Vaz Pereira	ORD	LCC	R
43520	Ivo Manuel Lopes Rodrigues	ORD	LCC	R
46287	João Batista da Costa Lopes	ORD	LCC	13
35828	João Henrique Alves Cerqueira	ORD	LCC	12
28154	João Manuel de Sousa Carmo	ORD	LCC	F
33705	João Manuel Lourenço Caldeira Pinto	ORD	LMCC	10
47418	João Paulo da Silva Bordalo	ORD	LCC	R
35831	João Pedro Afonso Cerqueira	ORD	LCC	R
38572	João Pedro Domingues Cadinha	ORD	LCC	12
43545	João Pedro Ferreira Mendes	ORD	LCC	R
25363	José Augusto da Rocha Gonçalves	T-E	LCC	F
33712	José Edmundo Ponte da Cunha	T-E	LCC	F
25364	José Filipe da Silva Caldas	T-E	LCC	F
41005	José Pedro Coelho Fernandes	ORD	LCC	F
35842	Katia Marina Ferreira da Silva	ORD	LCC	(t)
41018	Leandro Miranda Sousa Pinto	T-E	LCC	F
35782	Luis Filipe Magalhães Teixeira	T-E	LCC	F
42237	Luis Miguel Cruz Duarte	ORD	LCC	11
41007	Luis Pedro Lima e Horta Nova	ORD	LCC	12
20208	Magda Sofia Fernandes Cerqueira Peixoto	ORD	LCC	F
28162	Manuel José Oliveira Mendes	ORD	LCC	F
39431	Marco Paulo Fernandes Martins	ORD	LCC	F
30481	Maria de Fátima Sancho Monteiro	ORD	LCC	R
41010	Marta Sofia Vilaça de Oliveira	ORD	LCC	15
41019	Mercedes dos Santos Fernandes	T-E	LCC	F
43533	Miguel Alexandre Vieira dos Santos	T-E	LCC	F
41009	Miguel Filipe Dias Pinto	ORD	LCC	11
30746	Nuno André Passos Geraldes	ORD	LCC	R
43550	Nuno Diogo Neto Ferreira	ORD	LCC	10
41021	Nuno Filipe Pereira da Costa	ORD	LCC	F
41017	Nuno Miguel Macedo Salgado	ORD	LCC	12
40998	Otília Daniela Vieira de Carvalho	ORD	LCC	10
37074	Patrícia Alexandra Ribeiro	ORD	LCC	10
44633	Paulo Alexandre da Silva Lopes	ORD	LCC	F
50515	Paulo Alexandre Pinheiro da Silva	ORD	LCC	10
43510	Paulo Manuel de Oliveira Gomes	ORD	LCC	R
43511	Paulo Renato Ribeiro Xavier	T-E	LCC	F
32738	Paulo Sérgio Azevedo Magalhães	ORD	LMCC	11
41025	Pedro Manuel Neto Sousa Baltarejo	ORD	LCC	12
43532	Pedro Miguel Correia Araújo	ORD	LCC	15
41041	Pedro Miguel Matos dos Santos	ORD	LCC	F
41042	Pedro Miguel Ribeiro Martins	ORD	LCC	12
35857	Pedro Tiago Ribeiro Lopes Cunha	ORD	LCC	R
42211	Ricardo Jorge da Silva Costa	ORD	LCC	F
38584	Rui Dinis da Silva	ORD	LCC	R
39837	Rui Miguel Pacheco Almeida	ORD	LMCC	R
43503	Rui Pedro Alves de Carvalho	ORD	LCC	11
36867	Rui Samuel Portilha Valinho	ORD	LCC	R
41705	Sandra Cláudia Pereira Rodrigues	T-E	LCC	R
20235	Sérgio Bruno Fernandes Peixoto	ORD	LCC	F
47411	Tiago Campelo Vilas Boas	ORD	LCC	F
46222	Tiago de Sá Camacho da Côrte	ORD	LCC	F
41039	Tiago Fernando Melo Machado da Costa	ORD	LCC	10
43501	Vânio Miguel Rodrigues Ferreira	ORD	LCC	R
47406	Vera Lúcia Gonçalves Reina	ORD	LCC	10
48399	Vicente Machado Fernandes	ORD	LCC	14
48397	Vítor Hugo Correia Fernandes	ORD	LCC	14

(t) - O aluno tem a possibilidade de se apresentar à época especial sem ir a exame escrito, mediante submissão e defesa oral dos trabalhos práticos.

Voltar à página principal de CP.

Outras disciplinas leccionadas pelo DIUM