Departamento de Informática (UM)

Página de Unidade Curricular 🇬🇧

DesignaçãoCódigoCursoRegimeRegente

Técnicas Algorítmicas e Computabilidade

15955 [L302N2]

Licenciatura em Ciência de Dados [CDADOS]

S2

Paulo Jorge Sousa Azevedo

Objetivos

Esta UC baseia-se no paradigma imperativo da programação de computadores a alunos que já tiveram uma primeira abordagem (imperativa e declarativa) à programação de computadores.
Esta unidade curricular visa introduzir técnicas para o desenho de algoritmos (seguindo estratégias algorítmicas comuns e utilizando estruturas de dados clássicas), e para a análise rigorosa da sua eficiência.
Esta unidade curricular visa ainda introduzir os estudantes às noções de computabilidade e estruturas discretas para modelação de dados, nomeadamente grafos e estruturas ordenadas.

Programa

1. 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.
2. Algoritmos e computabilidade. Autómatos e máquinas de Turing; Recursividade e função computável; tese de ChurchTuring; Indecibilidade; completude NP
3. 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.
4. Algoritmos fundamentais sobre grafos; estratégia algorítmica "greedy" e programação dinâmica.
5. Introdução às classes de problemas P, NP, e NP-completo.

Bibliografia

Kernigham, B.W., Ritchie, D.M. (1988) The C programming language. 2nd edition. Prentice Hall Software Series.
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.
Sedgewick, R. (2001) Algorithms in C, part 5: Graph Algorithms, third edition. Addison-Wesley.

Resultados da aprendizagem

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

Método de avaliação

Realização de duas provas escritas ou exame de recurso (70%). Realização de projeto prático (30%).

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.

[ Outras UCs do Departamento ]