Planeamento
Aulas Teóricas
Introdução & Revisão.
Introdução à disciplina de Análise e Síntese de Algoritmos.
Revisão de IAED: pseudo-código; técnicas de síntese de algoritmos; notação assimptótica; outra notação.
Revisão de IAED.
Revisão de IAED: recorrências, amontoados.
Revisão de IAED.
Revisão de IAED: Algoritmos quicksort, counting sort e radix sort. Exemplos.
Algoritmos Eementares em Grafos
Algoritmos elementares em grafos: BFS e DFS. Exemplos e problemas.
Algoritmos Elementares em Grafos
Caracterização de arcos na DFS. Ordenação topológica. Componentes fortemente ligados.
Estruturas de Dados para Conjuntos Disjuntos
Algoritmos elementares em grafos: exemplos e problemas.
Estruturas de dados para conjuntos disjuntos.
Árvores Abrangentes de Menor Custo
Árvores abrangentes de menor custo. Algoritmos de Kruskal, Boruvka e Prim. Caminhos mais curtos com fonte única: notação e definições.
Caminhos Mais Curtos com Fonte Única
Caminhos mais curtos com fonte única. Relaxação e propriedades. Algoritmo de Dijkstra: descrição, complexidade e correcção. Algoritmo de Bellman-Ford: descrição e complexidade.
Caminhos Mais Curtos
Caminhos mais curtos em DAGs. Caminhos mais curtos entre todos os pares de vértices: propriedades. Algoritmo recursivo e de Floyd-Warshall. Fecho transitivo.
Caminhos Mais Curtos & Fluxos Máximos
Algoritmo de Johnson. Fluxos máximos: redes de fluxo, definição de fluxo, método de Ford-Fulkerson, rede residual, caminhos de aumento.
Fluxos Máximos
Fluxos máximos: redes de fluxo, definição de fluxo, método de Ford-Fulkerson, rede residual, caminhos de aumento, exemplo do método de Ford-Fulkerson, teorema do fluxo máximo/corte mínimo, complexidade do método de Ford-Fulkerson.
Fluxos Máximos
Complexidade do método de Ford-Fulkerson. Convergência com capacidades irracionais. Algoritmo de Edmonds-Karp, correcção e complexidade do algoritmo de Edmonds-Karp. Emparelhamento bipartido máximo. Motivação para a utilização de pré-fluxos.
Fluxos Máximos com Pré-Fluxos
Fluxos máximos: algoritmo genérico baseado em pré-fluxos, correcção e complexidade do algoritmo genérico;
Fluxos Máximos com Pré-Fluxos & Programação Linear
Algoritmo de pré-fluxo relabel-to-front: descrição, exemplo, análise da complexidade. Introdução à programação linear: definição, exemplos de aplicação, interpretação gráfica.
Programação Linear
Programação linear: definição, exemplos de aplicação, interpretação gráfica, formas standard e forma slack, o algoritmo Simplex, exemplos, cálculo de solução exequível inicial.
Programação Dinâmica
Programação linear: dualidade.
Programação dinâmica: motivação e exemplos, características da programação dinâmica, o problema da multiplicação de cadeias de matrizes.
Programação Dinâmica
Programação dinâmica: análise de exemplos, sub-sequência comum de maior comprimento, realização de trocos, maior palíndromo. Memorização.
Programação Dinâmica e Algoritmos Greedy
Algoritmos greedy: características dos algoritmos greedy, análise de exemplos, maximizar actividades, problema da mochila fraccionário, minimizar tempo no sistema, códigos de Huffman.
Algoritmos Greedy e Emparelhamento de Cadeias de Caracteres
Algoritmos greedy: códigos de Huffman. Emparelhamento de cadeias de caracteres: definições e propriedades, algoritmo elementar, utilização de autómatos finitos. Introdução ao algoritmo de Knuth-Morris-Pratt (KMP).
Emparelhamento de Cadeias de Caracteres
Emparelhamento de cadeias de caracteres: algoritmo de Knuth-Morris-Pratt (KMP), algoritmo de Rabin-Karp.
Introdução ao estudo dos problemas NP-completos.
Problemas NP-Completos
Problemas de decisão, classe de complexidade P, codificação de problemas, linguagens formais, algoritmos de verificação, classe de complexidade NP, redutibilidade entre problemas de decisão, definição de problema NP-completo, implicações da definição, abordagem para provar um problema de decisão NP-completo; exemplos de problemas NP-completos: SAT & CNFSAT. Prova de que CNFSAT é NP-completo.
Problemas NP-Completos
Problemas NP-Completos: classe de complexidade P, codificação de problemas, linguagens formais, algoritmos de verificação, classe de complexidade NP, redutibilidade entre problemas de decisão, definição de problema NP-completo, implicações da definição, abordagem para provar um problema de decisão NP-completo; exemplos de problemas NP-completos: CNFSAT, 3CNFSAT, CLIQUE e cobertura de vértices.
Problemas NP-Completos & Algoritmos de Aproximação
Problemas NP-completos: exemplos adicionais de problemas NP-completos: coloração de grafos com três cores. Exemplo prático de problema NP-completo.
Algoritmos de aproximação: motivação e definições; algoritmos de aproximação para os problemas da cobertura de vértices, da mochila, do caixeiro viajante, e da cobertura de conjuntos.