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

Sumários - 2002/03

J.N. Oliveira 406006

  Aula Teórica de 02.09.24 [Ref:4]:

Sumário: Apresentação da disciplina. Equipa docente.

Programa da disciplina e seu enquadramento no plano de estudos. Teoria e método em programação. Arquitectura do «software». Composicionalidade. Interfaces. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.

Regime de avaliação. Bibliografia. Informação electrónica sobre a disciplina: URL: http://www.di.uminho.pt/~jno/html/mpi.html.

  Aula Teórica de 02.09.26 [Ref:5]:

Sumário: 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.

Início do estudo dos combinadores de programas funcionais: A composição f ·g como combinador elementar de funções. Associatividade da composição: f ·(g ·h) = (f ·g) ·h .

Função identidade id. O polimorfismo de id e a propriedade f ·id = id ·f = f e seu diagramas comutativo.

  Aula Teórica de 02.10.01 [Ref:4]:

Sumário: Estudo dos combinadores de programas funcionais (cont.): 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.

Apresentação da extensão Mpi.hs ao Prelude.hs do Hugs 98.

  Aula Teórica de 02.10.03 [Ref:5]:

Sumário: Estudo dos combinadores de programas funcionais (cont.): Propriedades universais de <f,g> e de [f,g] . Propriedades de reflexão- × e reflexão-+.

Introdução à noção de isomorfismo entre tipos de dados. Motivação: a função swap = <pi2,pi1>, sua propriedade involutiva ( swap ·swap = id ) e o isomorfismo A × B =B × A . Funções bijectivas ou isomorfismos. Função inversa.

  Aula Teórica de 02.10.08 [Ref:4]:

Sumário: Estudo dos combinadores de programas funcionais (cont.) : Propriedades de cancelamento- × e cancelamento-+. Propriedades de fusão- × e fusão-+.

  Aula Teórica de 02.10.10 [Ref:5]:

Sumário: Estudo dos combinadores de programas funcionais (cont.) : Os combinadores f × g e f + g . Propriedades de absorção-+, × . Propriedades functoriais.

  Aula Teórica de 02.10.15 [Ref:4]:

Sumário: Estudo dos combinadores de programas funcionais (cont.) :

Lei da troca. Diagrama da lei da troca. Exemplo de aplicação da lei da troca: undistr e o isomorfismo (A × B) + (A × C) =A × (B+C).

Predicados e guardas. Condicional de McCarthy. Enunciado das leis de fusão do condicional de McCarthy:

f ·(p -> g, h) = p -> f ·g , f ·h
(p -> f, g) ·h = (p ·h) -> (f ·h), (g ·h) .

  Aula Teórica de 02.10.17 [Ref:5]:

Sumário: Não houve aula (dispensa de aulas devida aos festejos académicos).

  Aula Teórica de 02.10.22 [Ref:4]:

Sumário: 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).

  Aula Teórica de 02.10.24 [Ref:5]:

Sumário: Propriedade universal da exponenciação B^A . Leis da exponenciação (cancelamento, reflexão e fusão). Tipos elementares genéricos: 0 , 1 e 2 (resp. Void, () e Bool em HASKELL).

  Aula Teórica de 02.10.29 [Ref:4]:

Sumário: As funções ! : A ->1 e ? : 0 ->A . Funções constantes. O combinador c . Propriedades. Polimorfismo da função constante: c = c ·f.

O conceito de «apontador» 1 + A (Maybe a em HASKELL). Funções parciais.

Costumização de produtos e coprodutos em HASKELL. Álgebras e coálgebras de tipos de dados. Exemplo: o tipo data Error a = Err String | Ok a de valores ou mensagens de erro. Sua álgebra e sua coálgebra.

  Aula Teórica de 02.10.31 [Ref:5]:

Sumário: Introdução à composiçã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.

  Aula Teórica de 02.11.05 [Ref:4]:

Sumário: Composição funcional monádica : Mónadas versus functores. Noção de functor. Propriedades functoriais. Functores em HASKELL: a class Functor e o operador fmap. Exemplos simples: functor identidade e functor constante. Functor exponencial. Regra geral para a composição monádica.

  Aula Teórica de 02.11.07 [Ref:5]:

Sumário: Bifunctores e respectivas propriedades. Transformações naturais entre functores. Polimorfismo em HASKELL e «teoremas grátis». Exemplos.

  Aula Teórica de 02.11.12 [Ref:4]:

Sumário: Programação funcional monádica (cont.) : Definição formal. Composição e sua unidade. Multiplicação e suas propriedades. Exemplos: listas e Maybe.

  Aula Teórica de 02.11.14 [Ref:5]:

Sumário: Programação funcional monádica (cont.) : 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. Exemplos: listas, Maybe e IO.

  Aula Teórica de 02.11.19 [Ref:4]:

Sumário: Programação funcional monádica (conclusão) : 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.

  Aula Teórica de 02.11.21 [Ref:5]:

Sumário: Introdução aos tipos de dados indutivos a partir de uma analogia com a programação imperativa : Tipos de dados recursivos vistos como equações. As listas ligadas e a equação L =1 + A × L .

  Aula Teórica de 02.11.26 [Ref:4]:

Sumário: Introdução aos tipos indutivos (cont.) : 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: data BTree a = Empty | Node(a, (BTree a, BTree a)).

  Aula Teórica de 02.11.28 [Ref:5]:

Sumário: Apresentação dos módulos BTree.hs e LTree.hs : 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').

  Aula Teórica de 02.12.03 [Ref:4]:

Sumário: Noções de functor e bifunctor (cont.) : Noção de bi-functor. Propriedades. Bi-functores em HASKELL: a class BiFunctor e o operador bmap. Exemplos: bifunctores produto e coproduto. Functores polinomiais. Propriedades naturais.

  Aula Teórica de 02.12.05 [Ref:5]:

Sumário: Noções de functor e bifunctor (cont.) : síntese de fmap para o tipo LTree como um catamorfismo. Parametrização e polimorfismo. Introdução ao conceito de functor de tipo (`type functor').

  Aula Teórica de 02.12.10 [Ref:4]:

Sumário: 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)).

  Aula Teórica de 02.12.12 [Ref:5]:

Sumário: 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. Preenchimento do questionário de avaliação da disciplina.

  Aula Teórica de 02.12.17 [Ref:4]:

Sumário: Classificação algorítmica. Quadro sinóptico dos principais algoritmos analisados e estudados ao longo da disciplina:

Classe	B(A,X)	Serialização	Ordenação	Inversão	Factorial	Quadrado	Outros
RList	1 + A × X	cRList2h	iSort	invl	fac	sq	look
BTree	1 + A × X²	in/pré/pós	qSort				hanoi, traces
LTree	A + X²	tips	mSort	invLTree	dfac	dsq	fib

Polimorfismo versus politipismo. Programação dita «genérica».

  Aula Teórica de 02.12.19 [Ref:5]:

Sumário: Conclusão : Síntese final. Revisão dos sumários. Articulação da disciplina com outras que se lhe seguem no plano de estudos. Encerramento da disciplina.