Algoritmos e Estruturas de Dados
Código
8145
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Informática
Créditos
6.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
- Complexidade assintótica, temporal e espacial.
- Tipos abstratos de dados e estruturas de dados fundamentais.
- Sistematizar a utilização das estruturas de dados na resolução de categorias de problemas reais.
- Técnicas fundamentais de desenho de algoritmos (divisão e conquista e função-memória).
- Algoritmos de ordenação e suas condições de aplicação.
Saber Fazer
- Calcular a complexidade de algoritmos polinomiais ou exponenciais, iterativos ou recursivos.
- Modelar programas usando tipos abstratos de dados.
- Escolher, comparar, adaptar e utilizar estruturas de dados adequadas ao problema.
- Implementar estruturas de dados, em particular, recorrendo a gestão dinâmica de memória.
- Implementar algoritmos recursivos polinomiais.
Soft-Skills
- Efetuar escolhas fundamentadas.
- Concretização na implementação de um projeto.
- Avaliar soluções.
- Gestão do tempo.
- Comunicação escrita: relatório de projeto da disciplina.
- 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 final.
O trabalho é obrigatório e realizado individualmente ou em grupos de 2 alunos, em 2 fases, entregues em datas marcadas e sujeitas a avaliação independente.
Os testes são sem consulta, escritos e individuais.
Avaliação:
- Notas combinadas das duas fases do trabalho, valendo cada uma 15% da nota final (NP).
- Notas combinadas de 2 testes, valendo o primeiro 25% da nota final e o segundo 45% da nota final (NT).
- 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 9.5 valores em 20.
As melhorias de nota apenas se realizam por exame, sendo a nota final igual à nota do exame.
São aceites trabalhos desenvolvidos com sucesso em edições anteriores da disciplinas, embora a nota do trabalho não seja considerada na nota final. Para estes alunos, a nota final será:
- Em caso de aprovação por testes, o primeiro teste vale 36% da nota final e o segundo teste, 64%;
- Em caso de aprovação por exame, a nota de exame.