No final do curso, os estudantes deverão ser capazes de:
1. desenvolver e implementar A&ED e analisá-los no que respeita à sua correcção
2. compreender conceitos básicos de teoria da complexidade
3. analisar a eficiência dos A&ED com base em diferentes medidas, como o tempo e a memória
4. escrever programas que usem A&ED socorrendo-se de bons princípios de programação, como seja a especificação de API's e utilizar testes apoiados em A&ED
5. resolver problemas através da utilização de ED tais como listas simples, pilhas, filas, tabelas de dispersão, acervos, árvoresbinárias de procura e grafos e escrever programas para estas soluções
6. resolver problemas utilizando métodos de desenho e concepçáo de algoritmos, como abordagens "greedy", decomposição, programação dinâmica, "backtracking" e escrever programas para estas soluções
7. ser capaz de, desenhar a DS apropriada, criar um algoritmo que o resolva ou identificar o problema como um que não possa ser resolvido eficientemente
1. Análise básica
Introdução à teoria da complexidade; Análise assimptótica de complexidade; Notações padrão; O teorema Mestre; As classes mais comuns de complexidade; Estimação empírica de complexidade; Complexidade em tempo e memória; Uso de recursão na análise de algoritmos; Análise de melhor, pior e caso médio
2. ED básicas: listas, pilhas, filas, tabelas de dispersão, acervos, árvores, grafos
3. Estratégias para desenvolvimento de A&ED
Algoritmos de força bruta, "greedy", decomposição, "backtracking", heurísticas.
4. Algoritmos básicos
Algoritmos numéricos simples, procura sequencial e binária, ordenação quadrática e O(N log N), tabelas de dispersão, árvores binárias de procura, representação de grafos, DFS, BFS e PFS, algoritmos de caminhos mais curtos (Dijkstra e Floyd), árvores de suporte mínimas (Prim e Kruskal)
As metodologias de ensino pretendem fomentar a aprendizagem baseada em resolução de problemas e por projectos, reforçando-se a componente prática, a aprendizagem, activa, o trabalho autónomo e a responsabilização do estudante. O modelo de avaliação incorpora elementos de avaliação contínua no âmbito da aprendizagem ativa (p. ex, projectos, trabalhos de casa, fichas, etc)
compatível com a redução significativa do peso de avaliação por exames, propondo-se 50% avaliação contínua e 50% avaliação não contínua
Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", Robert Sedgewick,2001, Addison-Wesley Professional
Introduction to Algoritms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, 1999, MIT Press
Algorithms - fourth edition, Robert Sedgewick and Kevin Wayne, 2011, Addison-Wesley
0104102
6
