Departamento de Informática (UM)

Dados e Computação

14957 [J902N4]

Licenciatura em Engenharia Física [ENGFIS]

S2

Jorge Miguel Matos Sousa Pinto

Objetivos

A Unidade Curricular percorre o programa proposto em círculos concêntricos ilustrando por recurso a uma linguagem de programação moderna as diversas estruturas introduzidas para modelação de dados e conhecimento, de modo a combinar a abordagem teórica/conceptual dos assuntos com a sua implementação e aplicação prática. Deste modo os dois últimos objetivos de aprendizagem são trabalhados em paralelo, reforçando-se mutuamente. O primeiro objetivo é trabalhado diretamente na primeira secção do programa, com a programação de pequenas animações.

Programa

1. Algoritmos e computabilidade. Autómatos e máquinas de Turing; recursividade e função computável; tese de Church-Turing; indecibilidade; completude NP
2. Estruturas discretas, algoritmos base associados e sua utilização na representação de dados e conhecimento, por exemplo:
a. Ordens
b. Árvores e Grafos
c. Estruturas algébricas (monoides, anéis, grupos e corpos)
d. Data streams

Bibliografia

Lewis, H., Papadimitriou, C. (1998). Elements of the Theory of Computation. Prentice-Hall

Jenkins, T., Stephenson, B. (2013). Fundamentals of Discrete Math for Computer Science. Springer

Gopalakrishnan, G. (2019). Automata and Computability: A Programmer's Perspective. Chapman and Hall/CRC.

Jones, N. (1997), Computability and Complexity: From a Programming Perspective. MIT Press

Resultados da aprendizagem

Esta unidade curricular visa introduzir os alunos às noções de computabilidade e estruturas discretas para modelação de dados, nomeadamente grafos e estruturas ordenadas. Os conceitos são animados laboratorialmente com recurso a uma linguagem de programação moderna de alto nível, multi-paradigma e de utilização geral. Assim, no final, os alunos serão capazes de

- Compreender a noção de computabilidade (máquina de Turing, função computável, outros modelos computacionais) e problemas associados
- Analisar e desenvolver algoritmos manipulando diversos tipos de estruturas discretas, nomeadamente, ordens e grafos
- Implementar diversas estruturas discretas e computacionais numa linguagem de programação de alto nível, elegendo em cada caso o paradigma e construções apropriados

Método de avaliação

- Projecto de programação em grupo (30%)
- Teste escrito (70%)

Funcionamento

Turno: T 1; Docente: Paulo Jorge Sousa Azevedo; Dep.: DI; Horas: 30.
Turno: TP 1; Docente: Paulo Jorge Sousa Azevedo; Dep.: DI; Horas: 30.