Algoritmos e Estruturas de Dados, 2017/2018

Índice


Professores

Descrição e objectivos da disciplina

Esta disciplina é sobre algoritmos e estruturas de dados. Iremos aprender uma série de algoritmos clássicos de procura e de ordenação, e a saber a analisar a sua complexidade. Paralelamente iremos aprender estratégias de concepção de algoritmos.

Vamos também aprender estruturas de dados fundamentais como filas, stacks, árvores, tabelas de dispersão, e grafos. O conhecimento destas estruturas de dados é essencial para a resolução eficiente de um grande número de problemas.

Programa resumido

Bibliografia

Referência principal

Referências complementares

ou:

Regras de avaliação

Trabalhos práticos e sua discussão 30%
Exame final 70%

É necessário uma nota não inferior a 7,0 valores na avaliação prática para serem admitidos a exame final.

Os trabalhos práticos podem ser feitos individualmente ou em grupos de 2 alunos. Na última semana de aulas haverá discussão dos trabalhos durante o horário das aulas práticas. As discussões serão individuais e são obrigatórias. A avaliação prática final estará dependente do desempenho de cada aluno(a) na discussão dos trabalhos.


Aulas

aula data tópico slides CLRS (3rd Ed.) CLRS (2nd Ed.) CLR (1st Ed.)
01 06/Fev Apresentação da disciplina. (PDF) cap 1, 2.1, 2.2 cap 1, 2.1, 2.2 cap 1.1, 1.2
02 08/Fev Análise de algoritmos. Melhor caso, pior caso, caso médio. (PDF)
03 15/Fev Crescimento de funções. Complexidade assimptótica. Notação O, Ω, Θ (PDF) cap 3 cap 3 cap 2
04 20/Fev Estruturas de dados para listas: arrays e listas ligadas (PDF) cap 10 cap 10 cap 11
05 22/Fev Arrays redimensionáveis, análise amortizada (PDF) cap 17.4 cap 17.4 cap 18.4
06 27/Fev
07 01/Mar Filas e Stacks (PDF) cap 10 cap 10 cap 11
08 06/Mar Filas com prioridade, Heaps (PDF) cap 6 cap 6 cap 7
09 13/Mar Heapsort (PDF) cap 6 cap 6 cap 7
10 14/Mar Mergesort, Divisão e Conquista (PDF) cap 2.3 cap 2.3 cap 1.3
11 16/Mar Resolução de recorrências (PDF) cap 4.3, 4.4, 4.5, 4.6 cap 4.1, 4.2, 4.3 cap 4.1, 4.2, 4.3
12 20/Mar Quicksort (PDF) cap 7 cap 7 cap 8
13 22/Mar Mais divisão e conquista (PDF)      
14 03/Abr Estatísticas de ordem. Limite assimptótico inferior para ordenação (PDF) cap 9.1, 9.2; cap 8.1 cap 9.1, 9.2; cap 8.1 cap 10.1, 10.2; cap 9.1
15 05/Abr Programação dinâmica (PDF) cap 15 cap 15 cap 16
16 10/Abr
17 12/Abr Árvores n-árias. Árvores ordenadas. Tries (PDF) cap 10.4 cap 10.4 cap 10.4
18 17/Abr Árvores binárias de pesquisa (PDF) cap 12 cap 12 cap 13
19 19/Abr Árvores Red-Black (PDF) cap 13 cap 13 cap 14
20 24/Abr
21 26/Abr Tabelas de Hash (PDF) cap 11 cap 11 cap 12
22 03/Mai Grafos: Definições básicas, representação.
Procura em largura (BFS).
(PDF)
(PDF)
cap 22.1, 22.2 cap 22.1, 22.2 cap 23.1, 23.2
23 15/Mai Grafos: Procura em profundidade (DFS). Componentes conexas. Ordenação topológica.
(PDF) cap 22.3, 22.4 cap 22.3, 22.4 cap 23.3, 23.4
24 17/Mai
25 22/Mai Grafos: Caminho mais curto. Algoritmo de Dijkstra. (PDF) cap 24, 24.3 cap 24, 24.3 cap 25.1, 25.2
26 24/Mai Grafos: Árvores abrangentes de custo mínimo. Algoritmos de Prim e Kruskal. (PDF) cap 23, 23.1, 23.2 cap 23.1, 23.2 cap 24.1, 24.2
27 29/Mai Estruturas de dados para conjuntos disjuntos (Union-Find). (PDF) cap 21.1, 21.2, 21.3 cap 21.1, 21.2, 21.3 cap 22.1, 22.2, 22.3

Aulas práticas

semana datas tópico exercícios
01 05-09/Fev Escalabilidade empírica. (PDF)
02 12-16/Fev (PDF)
03 19-23/Fev Trabalho 1: variante do buddy system. ver tutoria
04 26-02/Mar
05 05-09/Mar Trabalho 2: filas com prioridade ver tutoria
06 12-16/Mar
07 19-23/Mar Trabalho 3: bolsa (divisão e conquista) ver tutoria
08 03-06/Abr
09 09-13/Abr Trabalho 4: sail away (prog. dinâmica) ver tutoria
10 16-20/Abr
11 23-27/Abr Trabalho 5: árvores ver tutoria
12 30-04/Mai
13 14-18/Mai Trabalho 6: palavra puxa palavra ver tutoria
14 21-25/Mai
15 28-30/Mai Discussão dos trabalhos práticos  

Links úteis