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. Nestes casos será sempre tido em consideração o disposto no nº3 do artigo 10º do Regulamento de Avaliação da FCT NOVA.

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. A nota do trabalho é individual. 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 ou teste prático, cujos detalhes serão definidos posteriormente.

 Avaliação:

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

NP = (P1*0,15 + P2 * 0,25) / 0,4

NP será arredonda à unidade.

- Componente Teórico-Prática: Notas combinadas de 2 testes, valendo cada um 50% da nota teórico-prática (NTP). As notas dos testes são arredondadas à décima antes de executada a ponderação. A componente de avaliação Teórico-Prática (NTP) tem assim o valor de 60% sobre a nota final com a seguinte fórmula

NTP = (T1*0,3+ T2*0,3) / 0.6

NTP será arredondada à unidade.

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

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

NF = NTP * 0,6 + NP * 0,4

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

NF = NTP.

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 o 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.

A utilização de ferramentas de IA (como, por exemplo, ChatGPT ou Copilot) tem de ser explicitamente referida no código e relatório. Considera-se que um grupo que use estas ferramentas durante a realização de um trabalho e omita que as usou comete plágio.

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

  - Ordenação

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

  - Pesquisa em Strings

•    Algoritmo de Knuth-Morris-Pratt

Cursos

Cursos onde a unidade curricular é leccionada: