Conteúdo / Main content
Menu Rodapé
  1. Início
  2. Cursos
  3. Matemática e Aplicações
  4. Algoritmos e Estruturas de Dados

Algoritmos e Estruturas de Dados

Código 14799
Ano 3
Semestre S2
Créditos ECTS 6
Carga Horária PL(30H)/T(30H)
Área Científica Informática
Tipo de ensino Presencial
Estágios (Não aplicável)
Objectivos de Aprendizagem Os objetivos principais prendem-se com a compreensão de estruturas de dados complexas e algoritmia avançada na resolução de problemas computacionais.
Os alunos deverão compreender e assimilar:
- As estruturas de dadas mais avançadas relacionadas com listas ligadas, árvores balanceadas e não balanceadas, Grafos e processamento de strings.
- Como selecionar as estruturas de dados apropriadas à resolução de problemas práticos.
- Como selecionar os algoritmos apropriados às estruturas de dados definidas.
- Desenvolver competências na utilização de técnicas matemáticas de análise da complexidade computacional espacial e temporal de algoritmos.
No final desta unidade curricular o estudante deve ser capaz de
- Explicar a necessidade de eficiência por parte dos algoritmos e estruturas de dados.
- Analisar a complexidade computacional (temporal e espacial) de programas.
- Implementar programas que utilizam os algoritmos e estruturas de dados.
Conteúdos programáticos A - COMPLEXIDADE COMPUTACIONAL DOS ALGORITMOS
1. Big-O
2. Análise Amortizada
B - ESTRUTURAS ABSTRATAS DE DADOS
1. Listas
2. Pilhas
3. Filas
4. Árvores binárias
5. Árvores binárias de pesquisa
C - ÁRVORE BINÁRIA DE PESQUISA BALANCEADA
1. Inserção binária
2. Adelson-Velskii Landis (AVL)
3. Vermelho-Preto (Red-Black)
D - ÁRVORE DE PESQUISA BALANCEADA
1. Árvore 2-3
2. Árvores de Intervalos
E - FILAS DE PRIORIDADE (HEAPS)
1. Binário
2. Binomial
3. Fibonacci
F - GRAFOS
1. Tipos de grafos
2. Representação computacional de um grafo
3. Algoritmos de pesquisa em grafos: em profundidade primeiro e em largura primeiro
4. Problemas envolvendo grafos: Árvore Abrangente Mínima, Caminho Mais Curto, Fluxo Máximo e Emparelhamento Estável
G - STRINGS
1. Conjuntos de Strings
2. Ordenação de Strings: Ordenação por Radix
3. Pesquisa de Strings: Pesquisa Binária
4. Pesquisa de uma substring numa String: Knuth-Morris-Pratt e Boyer-Moore
5. Prefix Tree, Suffix Tree e Suffix Arrays
Bibliografia principal "Competitive Programmer’s Handbook"; Antti Laaksonen; Draft July 3, 2018
"Algorithms", 4th Edition, 2011; Robert Sedgewick and Kevin Wayne; Addison Wesley, ISBN-13: 978-0321573513
"Introduction to Algorithms", 3rd Edition, 2009; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein; MIT Press, ISBN-13: 978-0262033848
"Estruturas de Dados e Algoritmos em C", 2008; António Manuel Adrego da Rocha; FCA-Editora de Informática. Coleção: Tecnologias de Informação; ISBN: 9789727222957
"Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", 3rd Edition, 2001; By Robert Sedgewick; Addison-Wesley Professional; ISBN: 0201756080
"Data Structures and Algorithm Analysis", Edition 3.2 (C++ Version), 2013; Clifford A. Shaffer; Department of Computer Science, Virginia Tech.
Língua Português
Data da última atualização: 2024-06-12
As cookies utilizadas neste sítio web não recolhem informação pessoal que permitam a sua identificação. Ao continuar está a aceitar a política de cookies.