Cálculo de Programas

Informação geral

Código: 14309
Área científica predominante: Informática
Regime: Semestral
ECTS: 5
Tipo de ensino: Presencial

Carga Horária

Trabalho autónomo: 80 horas

Aulas:
30 horas - Teóricas
30 horas - Teórico-práticas

Objetivos de ensino

A disciplina tem por objectivo ensinar a programar de forma científica, com base em teorias da programação hoje amplamente reconhecidas pela comunidade científica.
Mas o objectivo é sobretudo o de não se ficar pela teoria e passar à prática, como é timbre de um curso de engenharia.
Sendo a construção de programas uma actividade essencialmete colectiva, é importante haver um trabalho de grupo, em complemento da componente teórica dos conteúdos, que será objecto de aulas teórico-práticos para realização de exercícios.

Resultados de aprendizagem

- Programação composicional: aprender a escrever programas complexos por composição de programas mais simples (princípio da composicionalidade).
- Programação construtiva: aprender a escrever programas funcionais com recurso a combinadores algébricos.
- Transformação de programas: recurso à algebra da programação para se obter eficiência sem sacrifício da correção.
- Arquitectura da programação: Análise, compreensão e catalogação de programas: recurso à factorização algorítmica (hilomorfismos) como forma de se perceber a arquitectura dos algoritmos e sua taxonomia.
- Síntese de programas: cálculo de ciclos-for a partir de definições indutivas da matemática.
- Programação funcional avançada: construir e raciocinar sobre programas funcionais com efeitos sob a forma de mónades.

Programa sucinto

1. 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
2. Programação funcional:motivação e história.Composição de funções.Noções de abstração e de isomorfismo.Iniciação à estruturação de dados.Combinadores básicos e propriedades estruturais(reflexão,fusão,absorção,cancelamento e de functorialidade)
3. Á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»
4. Recursividade polinomial.Caso de estudo:algoritmos de ordenação.Parametrização e polimorfismo.Inferência de tipos polimórficos
5. Programação genérica.Functores de tipo.Introdução ao politipismo
6. Programação funcional com efeitos Mónades e sua teoria.Construção de programas monádicos.Exemplos:tratamento de erros,processamento de listas,computações probabilísticas e computações com estado.Referência ao mónade ‘input/output’

Bibliografia essencial

• J.N. Oliveira. Program Design by Calculation, 2008 (Chapters 2, 3 and 4). Draft of textbook in preparation, current version: October 2019. Available from http://www4.di.uminho.pt/~jno/ps/pdbc.pdf . Informatics Department, University of Minho.
• A. Cunha. Cálculo de Programas: notas teórico-práticas. Departamento de Informática, Universidade do Minho, 2005.
• R. Bird and O. de Moor. Algebra of Programming. Series in Computer Science. Prentice-Hall International, 1997. C. A. R. Hoare, series editor. BGUM 510.5-B .

Métodos de ensino

A metodologia de ensino orienta-se para o método pedagógico conhecido como ‘Flipped Classroom’, com base na disponibilização atempada dos conteúdos e fichas de trabalho para as aulas teórico-práticas.
Os sumários, que são publicados com uma semana de antecedência, indicam como os alunos se devem preparar para as aulas da semana seguinte.

Métodos de avaliação

A avaliação é feita com base numa prova individual sem consulta, com exame de recurso, e num trabalho de grupo a realizar fora das aulas e sujeito a uma prova oral (apresentação e demonstração do trabalho).
Alunos do mesmo grupo poderão ter classificações diferentes conforme a sua prestação oral. O trabalho será realizado na linguagem Haskell.