Algoritmos e Estruturas de Dados (11154)

Informação adicional: https://moodle.fct.unl.pt/course/view.php?name=AED1718

Introdução dos conceitos fundamentais de algoritmos e das estruturas de dados básicas, como ferramentas essenciais para resolver problemas de forma eficiente.

Dois hábitos são particularmente exercitados: analisar a eficiência de um algoritmo antes de o implementar e separar o tipo abstracto de dados das estruturas de dados que o implementam.

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.

Referências Principais

Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java (5th edition). John Wiley & Sons, 2010.
Mark Allen Weiss. Data Structures and Algorithm Analysis in Java (2nd edition). Addison-Wesley, 2007.

Referência Mais Elementar

Mark Allen Weiss. Data Structures and Problem Solving Using Java (4th edition). Addison-Wesley, 2010.

Referência Mais Avançada

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.

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.

	Horas por crédito		28
	Horas p/ semana	Semanas	Horas
Aulas prÃ¡ticas e laboratoriais			26.0
Aulas teÃ³ricas			42.0
AvaliaÃ§Ã£o			4.0
Estudo			42.0
OrientaÃ§Ã£o tutorial			3.0
Projectos e trabalhos			130.0
Total de Horas			247
ECTS			9.0