Código |
12121
|
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 principais objetivos desta Unidade Curricular são: - adquirir conhecimentos sobre algoritmia, em particular algoritmos recursivos, de ordenação, de pesquisa e tabelas de Hash, e análise de complexidade dos algoritmos; - compreender os conceitos fundamentais associados aos vários tipos de estruturas de dados sequenciais (listas ligadas) e não sequenciais (árvores binárias), e dos algoritmos passíveis de aplicação a cada estrutura. No final da Unidade Curricular o estudante deve ser capaz de - desenvolver competências de algoritmia, em particular em problemas que envolvam recursividade, ordenação e/ou pesquisa; - analisar a eficiência dos algoritmos, através da respetiva análise de complexidade, de forma a usar os algoritmos mais eficientes na resolução do problema em questão; - idealizar, esquematizar e implementar estruturas de dados e respectivos algoritmos com vista à resolução de problemas.
|
Conteúdos programáticos |
A - Complexidade Computacional dos Algoritmos 1. Big-O 2. Análise Amortizada B - Estruturas de Dados 1. Listas 2. Pilhas 3. Filas 4. Árvores binárias e árvores binárias de pesquisa C – Árvores Avançadas 1. Árvores binárias de pesquisa balanceadas: AVL e Red-Black 2. Árvores de pesquisa 2-3 3. Árvores de Intervalos 4. Heaps: binomial e fibonacci D - 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 E - 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
|
Metodologias de Ensino e Critérios de Avaliação |
Estão previstas para a UC; - 2 horas semanais de aulas teóricas para exposição dos conceitos teóricos e teórico-práticos, através de slides - 2 horas semanais de práticas num dos laboratórios de desenvolvimento de software, nas quais o estudante irá aplicar e testar os conhecimentos adquiridos nas aulas teóricas.
|
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
|