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 - INTRODUÇÃO Linguagem C B - ALGORITMOS Conceitos fundamentais Algoritmos recursivos Complexidade computacional C - ESTRUTURAS DE DADOS SEQUENCIAIS Estrutura Abstrata de Dados (EAD) A EAD "LISTA" (com ligações simples) A EAD "PILHA" A EAD "FILA" Análise amortizada de algoritmos D - ESTRUTURAS DE DADOS NÃO SEQUENCIAL - ÁRVORES Árvores binárias Árvores binárias de pesquisa Árvores binárias de pesquisa balanceadas Árvores binárias de pesquisa balanceadas avançadas Heaps E - ESTRUTURAS DE DADOS NÃO SEQUENCIAL - GRAFOS Tipos de grafos Representação computacional (estrutura de dados) de um grafo Algoritmos de pesquisa em grafos Problemas envolvendo grafos F - STRINGS Conjuntos de Strings Pesquisa e ordenação de Strings Pesquisa de uma substring numa String Prefix Tree (Trie) Suffix Tree Suffix Arrays
|
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 testes escritos; cada teste vale 7.0 valores; - 3 testes práticos; cada trabalho vale 2.0 valores.
Teste 1: 19/04/2022, 18h; Teste 2: 23/05/2022, 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
|