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

Maria Armanda Simenta Rodrigues Grueau

Horas

Semanais - 6

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 (3rd edition). Addison-Wesley, 2012.

Referência Mais Elementar

  • Mark Allen Weiss. Data Structures and Problem Solving Using 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 inscritos no mesmo turno e é realizado em 2 fases, entregues em datas marcadas. O trabalho é obrigatório para os alunos que não têm frequência e dá frequência. A frequência, tal como seja obtida nas aulas, é válida por um ano.

 Os testes e exames são sem consulta, escritos, presenciais e individuais. Não são permitidos quaisquer materiais de consulta, nem acesso a telemóvel ou calculadora.

Obtenção de Frequência: Para os alunos sem frequência, esta é atribuída como resultado da submissão das duas 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 (NP) calculada de acordo com a fórmula apresentada abaixo, terá de ser superior ou igual a 10 para a obtenção da frequência e a autoria do trabalho deverá ser comprovada em discussão presencial.

 Avaliação:

- Notas combinadas das duas fases do trabalho, valendo respetivamente 10% (P1) e 20% (P2) para a 1ª e 2ªs fases do trabalho (NP). A componente de avaliação Laboratorial (NP) tem assim o valor de 30% sobre a nota final com a seguinte fórmula

NP = (P1*0,1 + P2 * 0,2) / 0,3

NP será arredonda à unidade.

- Notas combinadas de 2 testes, valendo o primeiro 20% da nota final e o segundo 50% da nota final (NT). As notas dos testes são arredondadas à décima antes de executada a ponderação. A componente de avaliação Teórico-Prática (NT) tem assim o valor de 70% sobre a nota final com a seguinte fórmula

NT = (T1*0,2 + T2*0,5) / 0,7

NT será arredondada à unidade.

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

O aluno obtém aprovação se ambas as notas NP e NT forem superiores ou iguais a 10 valores em 20, segundo a seguinte fórmula

NF = NT * 0,7 + NP * 0,3

A nota final para estudantes reprovados com frequência (em que NT < 10) é igual a NT.

NF = NT.

De acordo com o regulamento de avaliação da FCT, as frequências do ano passado são válidas.

Os alunos que tenham sido aprovados no ano passado e que pretendam realizar melhoria do trabalho devem avisar a responsável da UC até à entrega da 1ª fase do trabalho e devem cumprir as datas de entrega ano letivo em curso. Para os alunos que pretendam apenas realizar melhoria da avaliação teórico-prática, a fórmula aplicada é NF, utilizando a nota do trabalho obtida no ano anterior.

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: