Algoritmos e Estruturas de Dados
Objetivos
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
Luís Manuel Marques da Costa Caires, Sofia Carmen Faria Maia Cavaco
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, Roberto Tamassia, Michael H. Goldwasser. 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 2 fases, entregues em datas marcadas. A divisão do trabalho entre os dois alunos tem que ser equilibrada. 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 de todas as 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.5 para a obtenção da frequência e a autoria do trabalho deverá ser comprovada em discussão presencial.
Avaliação:
- Componente de avaliação Laboratorial (NP): Notas combinadas das duas fases do trabalho, valendo respetivamente 10% e 20% para a 1ª e 2ª fases do trabalho. As notas das duas fases do trabalho são arredondadas às décimas antes de executada a ponderação. NP tem assim o valor de 30% sobre a nota final.
- Componente de avaliação Teórico-Prática (NT): Notas combinadas de 2 testes, valendo o primeiro 20% da nota final e o segundo 50% da nota final. As notas dos testes são arredondadas às décimas antes de executada a ponderação. NT tem assim o valor de 70% sobre a nota final.
- Em época de recurso, a nota dos dois testes é substituída pela nota do exame, que vale 70% (NT) da nota final.
- Nota final (NF): NP e NT são arredondadas às décimas antes de executada a ponderação.
- Aprovação: Para obter aprovação, NP e NT devem ser superiores ou iguais a 9.5 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 obtida em 2019/20 vale 30% da nota final.
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.