Saber

1.Complexidade assintótica, temporal e espacial.

2.Tipos abstratos de dados e estruturas de dados fundamentais.

3.Sistematizar a utilização das estruturas de dados na resolução de categorias de problemas reais.

4.Técnicas fundamentais de desenho de algoritmos (divisão e conquista e função-memória).

5.Algoritmos de ordenação e suas condições de aplicação.

Saber Fazer

6.Calcular a complexidade de algoritmos polinomiais ou exponenciais, iterativos ou recursivos.

7.Modelar programas usando tipos abstratos de dados.

8.Escolher, comparar, adaptar e utilizar estruturas de dados adequadas ao problema.

9.Implementar estruturas de dados, em particular, recorrendo a gestão dinâmica de memória.

10.Implementar algoritmos recursivos polinomiais.

Competências Complementares

11.Efetuar escolhas fundamentadas.

12.Concretização na implementação de um projeto.

13.Avaliar soluções.

14.Gestão do tempo.

15.Comunicação escrita: relatório de projeto da disciplina.

16.Comunicação oral: discussão do projeto da disciplina.

Introdução à Análise de Algoritmos

• Complexidade temporal e espacial.
• Complexidade no melhor caso, no pior caso e no caso esperado.

B.Introdução à Recursividade

• Divisão e conquista.
• Função-memória.

C.Tipos Abstratos de Dados

• Pilha (disciplina LIFO).
• Fila (disciplina FIFO).
• Lista (acesso por posição).
• Dicionário (acesso por chave): não ordenado e ordenado.
• Fila com prioridade.

D.Estruturas de Dados

• Vetores circulares.
• Listas simplesmente e duplamente ligadas.
• Tabelas de dispersão.
• Árvores genéricas.
• Árvores binárias.
• Árvores binárias de pesquisa: árvores sem restrições; árvores AVL.
• Heaps.

E.Algoritmos de Ordenação

• Ingénuos: insertion sort; selection sort; bubble sort.
• Eficientes: heapsort; mergesort; quicksort.
• Por indexação: bucket sort; radix sort.

Os alunos deverão ter realizado as unidades curriculares de Introdução à Programação e de Programação Orientada pelos Objectos.

Os alunos deverão ter:

• alguma experiência de programação, incluindo tópicos de programação orientada pelos objectos e recursividade;
• familiaridade com a linguagem de programação Java; e
• conhecimentos básicos de matemática discreta.