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
Maria Armanda Simenta Rodrigues Grueau
Horas
Semanais - 6
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 and Roberto Tamassia. Data Structures and Algorithms in Java (6th edition). John Wiley & Sons, 2015.
- Mark Allen Weiss. Data Structures and Algorithm Analysis in Java (3rd edition). Addison-Wesley, 2012.
Referência Mais Elementar
- Mark Allen Weiss. Data Structures and Problem Solving Using 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 inscritos no mesmo turno e é realizado em 2 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 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.
Avaliação:
- Notas combinadas das duas fases do trabalho, valendo respetivamente 10% (P1) e 20% (P2) para a 1ª e 2ªs fases do trabalho (NP). A componente de avaliação Laboratorial (NP) tem assim o valor de 30% sobre a nota final com a seguinte fórmula
NP = (P1*0,1 + P2 * 0,2) / 0,3
NP será arredonda à unidade.
- Notas combinadas de 2 testes, valendo o primeiro 20% da nota final e o segundo 50% da nota final (NT). As notas dos testes são arredondadas à décima antes de executada a ponderação. A componente de avaliação Teórico-Prática (NT) tem assim o valor de 70% sobre a nota final com a seguinte fórmula
NT = (T1*0,2 + T2*0,5) / 0,7
NT será arredondada à unidade.
- 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 10 valores em 20, segundo a seguinte fórmula
NF = NT * 0,7 + NP * 0,3
A nota final para estudantes reprovados com frequência (em que NT < 10) é igual a NT.
NF = NT.
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 a 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.
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.