Técnicas Algorítmicas e Computabilidade 2022/23

Resultados de aprendizagem

Ao completar o curso com sucesso os alunos devem ser capazes de:

Dividir um problema em subproblemas mais simples.
Definir tipos de dados para a representação dos dados e resultados de um dado problema.
Analisar e desenvolver algoritmos manipulando diversos tipos de estruturas discretas, nomeadamente, ordens, árvores e grafos;
Determinar a complexidade assimptótica de um algoritmo iterativo ou recursivo.
Pressupões reconhecer e utilizar estratégias algorítmicas fundamentais.
Aplicar a noção de computabilidade (máquina de Turing, função computável) e problemas associados;
Resolver problemas NP-completos e alguns algoritmos aproximados para a sua resolução.

Análise de complexidade de algoritmos: modelo de complexidade assimptótica; estratégias algorítmicas; recorrências; análise de caso médio e amortizada; casos de estudo.
Algoritmos e computabilidade. Autómatos e máquinas de Turing; Recursividade e função computável; tese de ChurchTuring; Indecibilidade; completude NP
Estruturas discretas, algoritmos base associados e sua utilização na representação de dados e conhecimento: árvores AVL, tabelas de dispersão, "heaps". Implementação eficiente de "buffers" e dicionários.
Algoritmos fundamentais sobre grafos; estratégia algorítmica "greedy" e programação dinâmica.
Introdução às classes de problemas P, NP, e NP-completo.

13 Feb (10:00 - 12:00)	Introdução a Técnicas Algorítmicas e Computabilidade (slides)
20 Fev (10:00 - 12:00)	Complexidade (Análise temporal; Tamanho do input; Considerações de hardware; O melhor caso, o pior caso e o caso médio); Análise Assimptótica (Notação Grande-O) (slides)
27 Fev (10:00 - 12:00)	Revisão da aula anterior; Definições recursivas Análise amortizada (slides)
6 Mar (10:00 - 12:00)	Revisão da aula anterior; Análise amortizada: análise agregada, método contabilístico, método potencial, tabelas dinâmicas. (slides)
13 Mar (10:00 - 12:00)	Revisões e preparação para o teste.
20 Mar (10:00 - 12:00)	Teste
17 Abr (10:00-12:00)	Estruturas (Conjuntos e Multi-conjuntos; Sequências; Buffers ) (slides)
24 Abr (10:00-12:00)	Estruturas (dicionários) e Grafos (Introdução e Consultas) (slides)
8 Mai (10:00-12:00)	Revisões e preparação para o teste.
15 Mai (10:00-12:00)	Teste

13 Fev (15:30 - 17:30)	Revisões e Diagnóstico (Exercises 1)
20 Fev (15:30 - 17:30)	Complexidade Parte 1 ( Exercises 2) - soluções
27 Fev (14:00-16:00)	Complexidade Parte 2 ( Exercises 3) - soluções
6 Mar (15:30-17:30)	Complexidade Parte 3 (Exercises 4)
13 Mar (15:30-17:30)	Revisões e preparação para o teste
20 Mar (15:30-17:30)	Classes (Slides)
17 Abr (15:30-17:30)	Estruturas (Exercícios 5)
24 Abr (15:30-17:30)	Estruturas e Grafos (Exercises 6)
8 Mai (15:30-17:30)	Revisões e preparação para o teste
15 Mai (15:30-17:30)	Apresentação de trabalho de grupo (Trabalho Final)

Robert Sedgewick, Kevin Wayne, Robert Dondero (2015). Introduction to Programming in Python: An Interdisciplinary Approach. Addison-Wesley Professional.
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.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. (2009) Introduction to Algorithms. Third Edition. MIT Press