| Código |
16671
|
| Ano |
1
|
| Semestre |
S2
|
| Créditos ECTS |
6
|
| Carga Horária |
PL(30H)/T(30H)
|
| Área Científica |
Informática
|
|
Objectivos de Aprendizagem |
Os objetivos desta UC focam-se em proporcionar aos estudantes técnicas de análise de complexidade algoritmica, diferentes estruturas de dados complexas e um conjunto de algoritmos para resolução de problemas computacionais.
No final desta unidade curricular o estudante deve ser capaz de:
- Explicar a utilidade e complexidade de diferentes estruturas de dados, assim como ser capaz de combinar diferentes estruturas de dados para resolução de problemas.
- Analisar a complexidade computacional (temporal e espacial) de um dado algoritmo.
- Implementar diferentes algoritmos e estruturas de dados para resolução de problemas complexos.
|
|
Conteúdos programáticos |
A unidade curricular aborda os seguintes conteúdos programáticos: (1) Recursividade: definição, chamadas recursivas, relações de recorrência e análise de algoritmos recursivos. (2) Análise de complexidade temporal e espacial: notação assintótica (O, T, O), análise de ciclos, casos médio e pior caso, e introdução a recorrências. (3) Algoritmos de ordenação: Bubble Sort, Insertion Sort, Selection Sort, Merge Sort e Quick Sort, com comparação de eficiência e estabilidade. (4) Estruturas de dados: vetores, vetores dinâmicos, listas ligadas simples e duplas, pilhas, filas, filas de prioridade, árvores binárias, árvores de pesquisa e representação de grafos por matriz e lista de adjacência. (5) Algoritmos de pesquisa e percursos em árvores e grafos (DFS e BFS).
|
|
Metodologias de Ensino e Critérios de Avaliação |
Avaliação Ensino/Aprendizagem
- P1 - Projeto I: 17.5% (trabalho individual)
- P2 - Projeto II: 32.5% (trabalho individual)
- F - Frequência: 50% (prova individual realizada em computador com consulta parcial dos conteúdos)
A classificação final da UC resulta da média ponderada das classificações obtidas nas componentes de avaliação definidas. O aluno obtém aprovação à UC, estando dispensado de Exame, no caso de obter uma nota igual ou superior a 9.5 valores.
Avaliação por Exame
- Exame: 50% (prova escrita)
Os trabalhos práticos contam para a nota final por exame, sendo que o exame só troca a nota de frequência.
Requisitos de admissibilidade à frequência e ao exame:
- Mínimo de 70% de assiduidade às aulas durante o período de ensino-aprendizagem (exceto trabalhadores estudantes);
- Nota mínima de 6 valores em AE, onde AE = ((P1 * 17.5%) + (P2 * 32.5%) + (F * 50%))
O incumprimento de qualquer um dos requisitos implica a não aprovação na UC e a não admissibilidade a exame.
|
|
Bibliografia principal |
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (Fourth Edition), The MIT Press, 2022.
Brad Miller and David Ranum. Problem Solving with Algorithms and Data Structures using Python, Luther College, 2006.
|
| Língua |
Português
|