Algoritmos e Estruturas de Dados

Caracterização geral

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

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: