Algoritmos e Estruturas de Dados

Não tem Fotografia:
Vasco Ferrinho Lopes
Código:
16671
Ano:
1
Semestre:
S2
Créditos ECTS:
6
Carga Horária:
PL(30H)/T(30H)
Área Científica:
Informática
Objectivos de Aprendizagem:
Os objetivos desta UC focam-se em proporcionar aos estudantes técnicas de análise de complexidade algoritmica, diferentes estruturas de dados complexas e um conjunto de algoritmos para resolução de problemas computacionais.

No final desta unidade curricular o estudante deve ser capaz de:
- Explicar a utilidade e complexidade de diferentes estruturas de dados, assim como ser capaz de combinar diferentes estruturas de dados para resolução de problemas.
- Analisar a complexidade computacional (temporal e espacial) de um dado algoritmo.
- Implementar diferentes algoritmos e estruturas de dados para resolução de problemas complexos.
Conteúdos programáticos:
A unidade curricular aborda os seguintes conteúdos programáticos: (1) Recursividade: definição, chamadas recursivas, relações de recorrência e análise de algoritmos recursivos. (2) Análise de complexidade temporal e espacial: notação assintótica (O, T, O), análise de ciclos, casos médio e pior caso, e introdução a recorrências. (3) Algoritmos de ordenação: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort e Quick Sort, com comparação de eficiência e estabilidade. (4) Estruturas de dados: vetores, vetores dinâmicos, listas ligadas simples e duplas, pilhas, filas, filas de prioridade, árvores binárias, árvores de pesquisa e representação de grafos por matriz e lista de adjacência. (5) Algoritmos de pesquisa e percursos em árvores e grafos (DFS e BFS).
Bibliografia principal:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (Fourth Edition), The MIT Press, 2022.
Brad Miller and David Ranum. Problem Solving with Algorithms and Data Structures using Python, Luther College, 2006.
Língua:
Português