Algoritmos e Estruturas de Dados

Objectivos

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.

Caracterização geral

Código

11154

Créditos

9.0

Professor responsável

Fernanda Maria Barquinha Tavares Vieira Barbosa, Luís Manuel Marques da Costa Caires

Horas

Semanais - 5

Totais - 71

Idioma de ensino

Português

Pré-requisitos

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.

Bibliografia

Referências Principais

  • Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java (6th edition). John Wiley & Sons, 2015.
  • Mark Allen Weiss. Data Structures and Algorithm Analysis in Java (4th edition). Addison-Wesley, 2013.

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.

Método de ensino

O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório. No laboratório, os alunos desenham, analisam e implementam algoritmos. Algumas aulas práticas são dedicadas à realização do trabalho final.

Método de avaliação

Qualquer aluno envolvido numa fraude (detetada imediatamente ou a posteriori, no trabalho, testes ou no exame) reprova na disciplina.

O ensino consiste na exposição da matéria em aulas teóricas e na resolução de problemas em aulas práticas de laboratório. No laboratório, os alunos desenham, analisam e implementam algoritmos. Algumas aulas práticas são dedicadas ao acompanhamento do trabalho prático.

O trabalho é realizado em grupos de 2 alunos. É realizado em 3 fases, entregues em datas marcadas. O trabalho é obrigatório para os alunos que não têm frequência e dá frequência.

Os testes são sem consulta, escritos e individuais.

Obtenção de Frequência: Para os alunos sem frequência, esta é atribuída como resultado da submissão das três fases do trabalho. Se uma das fases não for submetida, esta será assumida como tendo a nota de 0 (zero). A nota global do trabalho terá de ser maior ou igual a 9 para a obtenção da frequência e a autoria do trabalho deverá ser comprovada em discussão presencial.

 Avaliação:

- Notas combinadas das três fases do trabalho, valendo respetivamente 10%, 10% e 20% para a 1ª, 2ª e 3ªs fases do trabalho (NP). A componente de avaliação Laboratorial (NP) tem assim o valor de 40% sobre a nota final.

- Notas combinadas de 2 testes, valendo o primeiro 20% da nota final e o segundo 40% da nota final (NT). As notas dos testes são arredondadas as décimas antes de executada a ponderação. A componente de avaliação Teórico-Prática (NT) tem assim o valor de 60% sobre a nota final.

- Em época de recurso, a nota dos dois testes é substituída pela nota do exame, que vale 60% (NT) da nota final.

NP e NT são arredondadas à unidade. O aluno obtém aprovação se ambas as notas NP e NT forem superiores ou iguais a 9 valores em 20.

Os alunos que tenham obtido frequência em anos anteriores poderão ser dispensados da frequência. Para esses alunos, a  nota do trabalho não é considerada na nota final. Nestes casos, a nota final será:

  • Em caso de aprovação por testes, a nota da componente de avaliação Teórico-Prática;
  • Em caso de aprovação por exame, a nota de exame.

Os alunos que não pretendem ser dispensados de obtenção de frequência devem comunicar esse facto ao docente do seu turno prático e realizar o trabalho prático. A partir do momento em que entregam uma das fases do trabalho, este processo é irreversível.

Conteúdo

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.

Cursos

Cursos onde a unidade curricular é leccionada: