| Código |
14335
|
| Ano |
2
|
| 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 |
Esta UC tem como objetivos adquirir conhecimentos sobre:
- algoritmia, em particular algoritmos de ordenação e de pesquisa, e de análise de complexidade dos algoritmos
- estruturas de dadas de acesso sequencial (listas, pilhas e filas) e de acesso não sequencial (árvores não balanceadas e balanceadas, heaps e grafos)
- como selecionar as estruturas de dados apropriadas à resolução de problemas práticos
- como selecionar os algoritmos apropriados às estruturas de dados definidas.
Após a conclusão da UC, os estudantes deverão ser capazes de:
- desenvolver competências de algoritmia, em particular em problemas que envolvam 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 para a resolução do problema em questão
- explicar a necessidade de eficiência por parte dos algoritmos e das estruturas de dados
- implementar programas que utilizam os algoritmos e as estruturas estudadas.
|
|
Conteúdos programáticos |
ALGORITMOS
- Análise de Complexidade: Big-O
- Análise Amortizada
- Algoritmos de ordenação em arrays 1D
- Algoritmos de pesquisa em arrays 1D
ESTRUTURAS ABSTRATAS DE DADOS
- Listas ligadas (simples e duplas)
- Pilhas
- Filas
- Árvores binárias
- Árvores binárias de pesquisa
- Árvores N-árias
ÁRVORES DE PESQUISA BALANCEADAS
- Adelson-Velskii Landis (AVL)
- Vermelho-Preto (Red-Black)
- Árvore de Intervalos
- Árvore 2-3
FILAS DE PRIORIDADE (HEAPS)
- Binário
- Binomial
GRAFOS
- Tipos de grafos
- Representação computacional
- Algoritmos de pesquisa: em profundidade primeiro e em largura primeiro
- Problemas envolvendo grafos: Árvore Abrangente Mínima, Caminho Mais Curto, Fluxo Máximo e Emparelhamento Estável
|
|
Metodologias de Ensino e Critérios de Avaliação |
Para que o estudante possa adquirir as competências exigidas, estão previstas:
- 2h/semana de aulas teóricas (T) para exposição oral dos conceitos teóricos, métodos e algoritmos, utilizando-se ainda a escrita no quadro, a discussão de ideias com os alunos, e a projeção de diapositivos;
- 2h/semana de aulas prático-laboratoriais (PL), nas quais o estudante aplicará e testará os conceitos, os métodos e os algoritmos apresentados nas aulas teóricas, através da resolução de exercícios que constam em fichas criadas para o efeito;
- 2h/semana de tutoria para o esclarecimento de dúvidas e para o acompanhamento dos alunos no desenvolvimento dos seus projetos individuais.
Avaliação:
- 2 mini-testes práticos; cada um vale 2.0 valores.
- 2 testes escritos; cada teste vale 8.0 valores;
Teste escrito 1: 16/04/2024, 18h
Teste escrito 2: 21/05/2024, 18h
|
|
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
|