| Código |
13940
|
| Ano |
3
|
| Semestre |
S1
|
| Créditos ECTS |
6
|
| Carga Horária |
PL(30H)/T(30H)
|
| Área Científica |
Informática
|
|
Objectivos de Aprendizagem |
Esta unidade visa a definição de estruturas de dados apropriadas a um problema e a sua utilização através de algoritmos eficientes tem impacto na eficiência de um programa e, em última análise, na sua utilidade.
Assim, os alunos deverão compreender e assimilar:
- Como a estrutura de dados e a sua utilização através de algoritmos afeta o desempenho de sistemas computacionais;
- Os algoritmos e estruturas de dados fundamentais em termos de pesquisa e ordenação, designadamente em termos dos seus requisitos e complexidade espacial e temporal;
- Como selecionar as estruturas de dados apropriadas à resolução de problemas práticos;
- Como selecionar os algoritmos apropriados às estruturas de dados definidas;
- Técnicas matemáticas de análise da complexidade computacional espacial e temporal de algoritmos.
|
|
Conteúdos programáticos |
- Recursividade (Recursividade Terminal, Notação Big-O)
- Alocação dinâmica de recursos
- Complexidade Computacional (complexidade espacial e temporal)
- Estruturas de acesso sequencial: listas, pilhas e filas
- Estruturas de acesso quase-sequencial: listas de salto
- Ordenação, indexação e pesquisa
- Árvores binárias (árvores de pesquisa, AVLs, Árvores “Scapegoat”, Árvores “Red-Black”)
- Algoritmia (algoritmos gulosos, programação dinâmica)
|
|
Metodologias de Ensino e Critérios de Avaliação |
Para que o estudante possa adquirir as competências exigidas na unidade curricular, 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, PL, bem como para o acompanhamento dos alunos no desenvolvimento dos seus projetos individuais.
Avaliação:
-2 testes escritos; cada teste 7.0 valores;
- 1 projeto individual: 6.0 valores; o projeto carece de relatório final e do respetivo código, bem como de defesa pública.
A aprovação à disciplina está condicionada pela obtenção da nota mínima de 6 valores (6/20) no trabalho prático.
|
|
Bibliografia principal |
"Introduction to Algorithms (2nd edition)", Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, The MIT Press, 2001.?
"C Programming Language”, Brian Kernighan and Dennis Ritchie, Prentice Hall, ISBN: 978-0131103627
?"Mastering Algorithms in C", Kyle Loudon, O''Reilly, 1999.?
"A Book on C: Programming in C", Al Kelley and Ira Pohl, Addison-Wesley Professional, 978-0201183993.
|
| Língua |
Português
|