| Métodos de Programação I - 1999/2000 |
|---|---|
| [ DI/UM ] |
Sumário: Apresentação da disciplina. Equipa docente. Programa da disciplina e seu enquadramento no plano de estudos. Regime de avaliação. Informação electrónica sobre a disciplina: URL: HTTP://WWW.DI.UMINHO.PT/ JNO/HTML/MPI.HTML. Bibliografia.
Sumário: Motivação. Teoria e método em programação. Composicionalidade. Interfaces. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.Programação funcional: sua motivação e antecendentes históricos. Conceito de função. A função como contrato. Diagramas de blocos. Diagramas funcionais.
Sumário: Estudo dos combinadores elementares de programas funcionais: Domínio e codomínio de uma função. Igualdade extensional. A composição como combinador elementar de funções. Função identidade. Notação com ou sem variáveis. Associatividade da composição. Polimorfismo da identidade.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.): O combinador <f,g> e o produto A ×B («struct») e suas projecções. Propriedade universal e suas derivadas (cancelamento, reflexão e fusão).
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.): O combinador [f,g] e o coproduto A + B (analogia com «union») e suas injecções. Propriedade universal e suas derivadas (cancelamento, reflexão e fusão).
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Os combinadores f ×g e f + g . Propriedades de absorção. Propriedades functoriais. Lei da troca.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Invertibilidade à esquerda e à direita. Noção de isomorfismo. O isomorfismo A ×B =B ×A (swap). Outros isomorfismos célebres envolvendo produtos e coprodutos (assocr, undistr, etc). Propriedades naturais.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Produtos e coprodutos n-ários ( n>=0). Tipos elementares genéricos: 0 (Void em HASKELL ), 1 (() em HASKELL ) e 2 (Bool em HASKELL ). Segmentos iniciais e tipos enumerados. Funções constantes. O combinador c . Propriedades. As funções ! : A ->1 e ? : 0 ->A.
Sumário: <387>>4.11
Sumário: Apresentação da disciplina. Equipa docente. Programa da disciplina e seu enquadramento no plano de estudos. Regime de avaliação. Informação electrónica sobre a disciplina: URL: HTTP://WWW.DI.UMINHO.PT/ JNO/HTML/MPI.HTML. Bibliografia.
Sumário: Motivação. Teoria e método em programação. Composicionalidade. Interfaces. Combinadores de programas. Modularidade e reutilização. «Pacotes» de programação.Programação funcional: sua motivação e antecendentes históricos. Conceito de função. A função como contrato. Diagramas de blocos. Diagramas funcionais.
Sumário: Estudo dos combinadores elementares de programas funcionais: Domínio e codomínio de uma função. Igualdade extensional. A composição como combinador elementar de funções. Função identidade. Notação com ou sem variáveis. Associatividade da composição. Polimorfismo da identidade.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.): O combinador <f,g> e o produto A ×B («struct») e suas projecções. Propriedade universal e suas derivadas (cancelamento, reflexão e fusão).
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.): O combinador [f,g] e o coproduto A + B (analogia com «union») e suas injecções. Propriedade universal e suas derivadas (cancelamento, reflexão e fusão).
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Os combinadores f ×g e f + g . Propriedades de absorção. Propriedades functoriais. Lei da troca.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Invertibilidade à esquerda e à direita. Noção de isomorfismo. O isomorfismo A ×B =B ×A (swap). Outros isomorfismos célebres envolvendo produtos e coprodutos (assocr, undistr, etc). Propriedades naturais.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Produtos e coprodutos n-ários ( n>=0). Tipos elementares genéricos: 0 (Void em HASKELL ), 1 (() em HASKELL ) e 2 (Bool em HASKELL ). Segmentos iniciais e tipos enumerados. Funções constantes. O combinador c . Propriedades. As funções ! : A ->1 e ? : 0 ->A.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Predicados e guardas. Condicional de McCarthy.
Sumário: Estudo dos combinadores elementares de programas funcionais (cont.) : Funções de ordem superior. Noção de espaço funcional. O combinador curry f (curry f em HASKELL ). A exponencial BA. Propriedade universal e suas consequências (cancelamento, fusão e reflexão). A construção fA.
Sumário: Estudo dos combinadores elementares de programas funcionais (conclusão) : conclusão da aula anterior. Apresentação da extensão Mpi.hs ao Prelude.hs do Hugs 1.4 .
Sumário: Introdução aos tipos de dados recursivos a partir de uma analogia com a programação imperativa : O conceito de «apontador» 1 + A (Maybe a em HASKELL ). Tipos de dados recursivos vistos como equações. As listas ligadas e a equação L =1 + A ×L .
Sumário: Introdução aos tipos indutivos : Declaração de tipos de dados em HASKELL . Sua relação com o coproduto. Álgebra e co-álgebra do tipo indutivo definido pela equação L =1 + A ×L . Isomorfismo. Introdução à observação de tipos indutivos usando como exemplo listas de inteiros - data L = Nil | Cons (Int,L) .
Sumário: Introdução aos tipos indutivos (cont.) : Conceitos de catamorfismo e anamorfismo usando o tipo de dados exemplo listas de inteiros - data L = Nil | Cons (Int,L) .
Sumário: Introdução aos tipos indutivos (cont.) : Conceito de hilomorfismo usando o tipo de dados exemplo listas de inteiros - data L = Nil | Cons (Int,L) . O factorial visto como um hilomorfismo.Apresentação do módulo RList.hs.
Sumário: Introdução aos tipos indutivos (cont.) : Apresentação do algoritmo de ordenação por inserção simples como hilomorfismo sobre a estrutura RList a.Cálculo de programas: eliminação da estrutura de dados intermédia de um hilomorfismo .
Introdução ao tipo de dados árvores binárias simples , ou listas bi-lineares: data BTree a = Empty | Node(a, (BTree a, BTree a)).
Sumário: Introdução aos tipos indutivos (cont.) : Apresentação do módulo BTree.hs. Estudo da triologia cata-ana-hilo associada ao tipo BTree. Exemplos célebres: os catamorfismos de travessia (in/pre/pós-ordem) e os hilomorfismos qSort ('quick sort') e hanoi (torres de Hanói).
Sumário: Introdução aos tipos indutivos (cont.) : Noção de functor. Propriedades functoriais. Functores em HASKELL : a class Functor e o operador map. Exemplos: functor indentidade, functor constante e a exponencial.
Sumário: Introdução aos tipos indutivos (cont.) : Noção de bi-functor. Propriedades. Bi-functores em HASKELL : a class BiFunctor e o operador bmap. Exemplos: functor produto e coproduto.
Sumário: Não houve aula (participação do docente num júri de doutoramento).
Sumário: Tipos indutivos polinomiais : Functores polinomais. Forma canónica de um functor polinomial. Lei do binómio de Newton. Noção de tipo de dados indutivo polinomial.
Sumário: Tipos indutivos polinomiais (cont.) : 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').
Sumário: Tipos indutivos polinomiais : Generalização da triologia cata-ana-hilo à indução polinomial.Parametrização. Noção de functor de base . maps são catamorfismos: noção de functor de tipo e sua formulação genérica como catamorfismo de um tipo de dados recursivo da forma T a1...an =B(a1,...,an,Ta1...an) .
Sumário: Tipos indutivos polinomiais (cont.) : Estudo da triologia cata-ana-hilo associada ao tipo FTree.Quadro sinóptico classificativo dos principais algoritmos analisados e estudados ao longo da disciplina:
Classe B(A,X) B(A,C,X) Travessias Ordenação Factorial Outros RList 1 + A × X iSort fac sq LList 1 + X × A BTree 1 + A × X² in/pré/pós qSort hanoi LTree A + X² flatten mSort dfac fib FTree C + A × X²
Sumário: Conclusão : Síntese final. Articulação da disciplina com outras que se lhe seguem no plano de estudos. Preenchimento do questionário de avaliação da disciplina.