Guia de Cursos

Queres conhecer a oferta de cursos da NOVA, nas áreas das licenciaturas, mestrados e doutoramentos?
No nosso Guia de Cursos encontras informação útil sobre Faculdades, Institutos e Escolas.
Podes ainda aceder a informações complementares necessárias a uma completa integração.

saber mais Guia de Cursos

Faculdade de Ciências e Tecnologia

Algoritmos e Estruturas de Dados

Código

11154

Unidade Orgânica

Faculdade de Ciências e Tecnologia

Departamento

Departamento de Informática

Créditos

9.0

Professor responsável

Luís Manuel Marques da Costa Caires, Maria Armanda Simenta Rodrigues Grueau

Horas semanais

5

Total de horas

71

Língua de ensino

Português

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.

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.

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.

Bibliografia

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.

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 individualmente ou 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. A frequência, tal como seja obtida nas aulas, é válida apenas por um ano. Os alunos cuja frequência foi obtida em anos anteriores, poderão ser dispensados da mesma, mediante condições descritas abaixo.

 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 10 para a obtenção da frequência e a autoria do trabalho deverá ser comprovada em discussão presencial.

 Avaliação (ver quadro resumo nos slides de apresentação - no Moodle - para cálculo da nota):

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

- Notas combinadas de 2 testes, valendo o primeiro 20% da nota final e o segundo 55% 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 75% sobre a nota final.

- Em época de recurso, a nota dos dois testes é substituída pela nota do exame, que vale 75% (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 10 valores em 20.

OS alunos que tenham obtido frequência em anos anteriores a 2016/17 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, o primeiro teste vale 27% da nota final e o segundo teste, 73%;
  • 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.

Cursos