Criada: 2003-02-15
Modificada: 2003-03-03
Modificada: 2003-03-09
Modificada: 2003-05-18
| Getting Started | Exercícios |
| sorting problem insertion sort loop invariants modelo RAM análise: custo e número de vezes que cada linha é executada pior caso e caso médio razão de crescimento divisão e conquista: merge sort recorrência do merge sort |
2.1-3 2.2-2 2.3-7 |
| Growth of Functions | Exercícios |
| notação Θ notação O notação Ω notação assintótica em igualdades notação o notação ω comparação de funções seção 3.2: o que é novidade para você? |
3-2 3-3 3-4 |
| Recurrences |
Exercícios |
| Tecnicalidades: condições de contorno,
restringir a potências de 2 Método da substituição Subtraindo termos menores Cuidados com a notação O Troca de variáveis Árvores de recursão Master: quando a=b |
4-4 a. 4-4 f. 4-4 i. |
| Heapsort |
Exercícios |
| Heaps: min heap, max heap Max-Heapify Build-Max-Heap HeapSort e seu invariante Heap-Maximum, Heap-Extract-Max Heap-Increase-Key, Max-Heap-Insert |
6.5-7 6.4-3 |
| Quicksort |
Exercícios |
| Quicksort, Partition Pior partição Melhor partição Partição balanceada |
7.1-2 7.1-3 7-3 |
| Sorting in Linear Time |
Exercícios |
| Lower bounds - Teo. 8.1 Counting sort Radix sort Bucket sort |
8.3-4 8.4-2 8-2 |
| Medians and Other Statistics |
Exercícios |
| Min e Max Seleção do i-ésimo em tempo esperado linear Seleção do i-ésimo em tempo linear |
9.1-1 9.3-1 9-1 |
| Programação Dinâmica 1 |
Exercícios |
| Linha de montagem Etapa 1: estrutura da solução ótima Propriedade da subestrutura ótima Etapa 2: solução recursiva Etapa 3: cálculo do custo ótimo Etapa 4: construção de solução ótima Multiplicação de cadeias de matrizes (As quatro etapas para este problema) |
15.1-1 15.2-1 15.2-3 |
| Programação Dinâmica 2 |
Exercícios |
| Elementos da programação dinâmica Subestrutura ótima Sutilezas: o problema do caminho mais longo Número total de subproblemas a resolver Subseqüência comum mais longa (As quatro etapas para este problema) Árvore de busca ótima (As quatro etapas para este problema) |
15.3-5 15.4-1 15.5-2 |
| Algoritmos Gulosos 1 |
Exercícios |
| Seleção de atividades Teorema 16.1 Algoritmo guloso interativo Elementos da estratégia gulosa Escolha gulosa Subestrutura ótima Estratégia gulosa vs. programação dinâmica mochila 0-1 vs. mochila fracionária |
16.1-4 16.2-2 16.2-3 16.2-5 16.2-7 |
| Algoritmos Gulosos 2 |
Exercícios |
| Códigos de Huffman |
16.3-2 |
| Heaps Binomiais e de Fibonacci |
Exercícios |
| Tabela da Figura 19.1 Árvores binomiais (desenhar algumas) Definição de heap binomial União de heaps binomiais Definiçao de heaps de Fibonacci |
19.1-2 19.2-3 20.2-1 |
| Conjuntos Disjuntos | Exercícios |
| Operações Make-Set, Union, Find-Set Aplicação: componentes conexos (Pular a implementação com listas) Florestas de conjuntos disjuntos União por ordem (ou posto) Compressão de caminhos Make-Set, Union, Link, Find-Set Tempo de execução: função alpha |
21.3-1 21.3-2 21.3-3 |
| Grafos 1 |
Exercícios |
| Listas de adjacência Matriz de adjacência Buscas em largura Caminhos mais curtos Árvores produzidas por buscas em largura |
22.1-6 22.2-6 22.2-7 |
| Grafos 2 |
Exercícios |
| Buscas em profundidade Árvores produzidas por buscas em profundidade Ordenação topológica |
22.3-2 22.4-2 22.4-3 |
| Árvores espalhadas mínimas |
Exercícios |
| Definição de árvore espalhada mínima Como aumentá-la: cortes Algoritmo de Kruskal Algoritmo de Prim |
23.2-3 23.2-4 23.2-8 (tome V1 e V2 conexos) |
| Caminhos mais curtos - fonte única 1 |
Exercícios |
| Definição de caminho mais curto entre dois
vértices Subestrutura ótima Arestas e ciclos de peso negativo Ciclos em caminhos mais curtos Algoritmo de Bellman-Ford |
24.1-3 24.1-4 24-1 (c) ( assuma (a) e (b) ) |
| Caminhos mais curtos - fonte única 2 |
Exercícios |
| Solução para grafos orientados acíclicos Algoritmo de Dijkstra Implementação de Dijkstra em O(V2) Implementação de Dijkstra em O(E log V) Implementação de Dijkstra em O(E + V log V) |
24.2-3 24.3-6 24.3-7 |
| Caminhos mais curtos - todos os pares |
Exercícios |
| Estrutura de um caminho mais curto (subestrutura
ótima) Fórmula recursiva Solução usando multiplicação de matrizes, mas com "+" e "*" trocados por "min" e "+" Elevação ao quadrado repetida Algorithmo de Floyd-Warshall Fecho transitivo |
25.1-9 25.2-4 25.3-3 |
| Fluxo máximo 1 |
Exercícios |
| Redes de fluxo Fluxo, valor, fluxo máximo Método de Ford-Fulkerson Redes residuais, caminhos aumentantes Corte, capacidade do corte Exemplo da Fig. 26.4 |
26.2-1 26.2-3 26.2-8 |
| Fluxo máximo 2 | Exercícios |
| Algoritmo básico de Ford-Fulkerson, O(E |f*| ) Algoritmo de Edmonds-Karp, O(V E2) Emparelhamento bipartido máximo |
26.3-1 26-4 |
| NP completude 1 |
Exercícios |
| Problemas NP: complexidade desconhecida,
geralmente entre polinomial e exponencial Exemplo de pares de problemas "próximos" sendo um polinomial e o outro NP completo Porque é importante conhecer pelo menos os rudimentos da teoria de NP completude Problemas de decisão e problemas de otimização O adjetivo "NP completo" aplica-se a que tipo de problema diretamente? Problemas, codificações, linguagens |
34.1-2 34.1-4 34.1-5 |
| NP completude 2 |
Exercícios |
| Algoritmos de verificação: exemplos Classes NP e co-NP Redutibilidade: algoritmo de redução, função de redução, linguagem redutível a outra A classe NPC (linguagens NP completas) Um problema NP completo: satisfatibilidade de circuitos, CIRCUIT-SAT Redução de CIRCUIT-SAT a SAT |
34.2-1 34.2-3 34.2-8 34-3 (c), (d), (e), (f) |
© 2003 João Meidanis