Cálculo de Programas

Licenciatura em Engenharia Informática

Tópicos

Avisos

30 Set - Classificações finais dos alunos que fizeram exame da época especial: - ver Alunos

12 Set - Data, hora e sala do exame da época especial - ver sumários

25 Jul - Publicadas em Alunos as notas finais da disciplina.

9 Jul - Publicado no Material Pedagógico o enunciado do teste de 18-Jun com 5 questões resolvidas.

8 Jul - Hora e salas do exame de recurso de 12-Jul - ver sumários.

30 Jun - As classificações dos alunos com avaliação após teste de 18-Jun estão disponíveis em Alunos

18 Jun - Tal como se avisou a 22-Fev, a equipa docente insiste que não poderá assegurar a componente de avaliação contínua aos alunos que não tiverem a sua fotografia no BB.

14 Jun - Não serão distribuídos formulários no teste de 18-Jun. Quem desejar pode levar o formulário que está disponível no Material Pedagógico e que é o único elemento de consulta.

12 Jun - As classificações das fichas de avaliação do Método A estão disponíveis em Alunos.

9 Jun - Publicadas no Material Pedagógico as fichas de avaliação do Método A.

28 Mai - Publicada no Material Pedagógico a ficha nr.12, destinada às aulas práticas da última semana de aulas.

27 Mai - Hora e salas do teste individual - ver sumários.

21 Mai - Publicada no Material Pedagógico a ficha nr.11, destinada às aulas práticas da semana que começa a 23-Mai.

15 Mai - Publicada na Bibliografia a última parte do texto de apoio à disciplina.

14 Mai - Publicada no Material Pedagógico a ficha nr.10, destinada às aulas práticas da semana que começa a 16-Mai.

04 Mai - Publicados no Material Pedagógico (secção "Bibliotecas") uma série de ficheiros em Haskell de apoio às aulas sobre a segunda parte da matéria.

30 Abr - Publicada no Material Pedagógico a ficha nr.9, destinada às aulas práticas da semana que começa a 2-Mai.

16 Abr - Publicada no Material Pedagógico a ficha nr.8, destinada às aulas práticas da semana que começa a 26-Abr.

11 Abr - Tendo sido por vários alunos manifestada vontade de anularem a ficha de avaliação nr.1 e transitarem para o método B, informa-se que o prazo limite para tomarem essa decisão é a próxima 6a-feira, dia 15-Abr, comunicando-o ao docente responsável carregando aqui.

09 Abr - Publicada no Material Pedagógico a ficha nr.7, destinada às aulas práticas da semana que começa a 11-Abr.

02 Abr - Método A - recorda-se que a avaliação nr.1 decorrerá nas aulas práticas da próxima semana. O único material de consulta é o formulário (em papel).

02 Abr - Publicadas no Material Pedagógico: (a) duas notas de apoio às aulas teóricas T-09 e T-10; (b) a ficha nr.6, destinada às aulas práticas da semana que começa a 4-Abr.

02 Abr - Publicado na Bibliografia mais um capítulo do texto de apoio à disciplina.

26 Mar - Publicada no Material Pedagógico a ficha nr.5, destinada às aulas práticas da semana que começa a 28-Mar.

19 Mar - Publicada no Material Pedagógico a ficha nr.4, destinada às aulas práticas da semana que começa a 21-Mar.

12 Mar - Publicada no Material Pedagógico a ficha nr.3, destinada às aulas práticas da semana que começa a 14-Mar.

5 Mar - Publicada nos sumários a calendarização prevista para as avaliações do Método A.

5 Mar - Publicada no Material Pedagógico a ficha nr.2, destinada às aulas práticas da semana que começa a 7-Mar.

26 Fev - Publicada no Material Pedagógico a ficha nr.1, destinada às aulas práticas da semana que começa a 28-Fev.

26 Fev - Publicada em Alunos a alocação aos turnos práticos revista de acordo com as condições de frequência do método A.

23 Fev - Mensagens para a equpa docente: usem Contacto ou no mínimo garantam que o string "CP/1011" aparece no assunto; de outra forma, não há garantia de se não perderem nos filtros de SPAM.

22 Fev - Fotografias: os alunos que não tem fotografia no portal académico (logo também não no BB) devem colocá-la o mais depressa possível.

22 Fev - Tendo a equipa docente recebido emails de alunos que se enganaram na sua inscrição, informa-se que essas situações serão tratadas após o fecho das inscrições, por ordem de chegada.

21 Fev - Inscrição nos turnos práticos: ver as condições de frequência em Regime de Avaliação.

19 Fev - Turnos práticos: a inscrição electrónica nos turnos práticos terá lugar 3ª-feira, dia 22-Fev das 10h00 às 18h00 via Blackboard (código: 1011.8204N5).

19 Fev - Os alunos devem estar atentos aos Avisos da página da disciplina.

16 Fev - As aulas teóricas começam na próxima 5ª-feira, 24-Fev, às 09h00 - ver sumários.

16 Fev - Já estão calendarizadas as provas de avaliação -- ver calendário da disciplina.

15 Fev - Foi criada esta página.

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.

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

  • Parametrização e polimorfismo. Inferência de tipos polimórficos. Programação genérica. Functores de tipo. Introdução ao politipismo.

  • Programação funcional com efeitos. Mónades e sua teoria. Construção de programas monádicos. Exemplos: excepções, processamento de listas, computações com estado. Breve referência ao `input/output'.

Programa detalhado

1. Teoria e método em programação. Concepção composicional e reutilização. Combinadores de programas. Modelação funcional de problemas.

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. Igualdade extensional. Diagramas funcionais. Recurso a setas f : A -> B e diagramas. 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. Inferência de tipos polimórficos com recurso a diagramas. Propriedades naturais e propridades 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.

5. Programação funcional em HASKELL. Costumização de produtos e coprodutos. Álgebras e coálgebras de tipos de dados. O conceito de «apontador» 1 + A (Maybe a em HASKELL). Funções parciais.

6. Programação com tipos de dados indutivos. Tipos de dados recursivos vistos como equações. Os número naturais e a equação N =1 + N. As listas ligadas e a equação L = 1 + A × L. Noção de combinadores recursivos. Exemplos: catamorfismos e anamorfismos. Hilomorfismos (anamorfismos seguidos de catamorfismos). Apresentação do módulo List.hs. Estudo da triologia cata-ana-hilo associada ao tipo List. O algoritmo de cálculo do quadrado de um número visto como hilomorfismo sobre a estrutura List a. O algoritmo de ordenação por inserção simples visto como hilomorfismo sobre a estrutura List 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: o hilomorfismo fib (série de Fibonacci) e 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ónade. 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) }. Regras para a monadificação de funções arbitrárias com recurso à notação "do".

r3 - 12 Jul 2011 - 14:38:02 - JoseNunoOliveira
This site is powered by the TWiki collaboration platform Copyright © by the contributing authors. Ideas, requests, problems? Send feedback.
Syndicate this site RSSATOM