| 27/set |
Problemas Computacionais e Algoritmos |
(aula) |
(slides) |
(a) |
Apresentação. Diferenças de ALG 1 e 2. |
CLRS - Cap. 1 |
| (b) |
Problemas computacionais. Abstração matemática de problemas reais. |
| (c) |
Problemas mal-definidos. Algoritmos. |
| (d) |
Computação ≠ tecnologia. Análise de Algoritmos. |
| | | | | | |
| 29/set |
Introdução à Recursão |
(aula) |
(slides) |
(a) |
Fatorial. |
Feof |
| (b) |
Elementos da recursão. Potenciação. |
| (c) |
Passo-a-passo para algoritmos recursivos. |
| (d) |
Fibonacci. |
|
|
|
|
|
|
|
| 04/out |
Mínimo de Vetor |
(aula) |
(slides) |
(a) |
Problema, algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo a recorrência. |
| (c) |
Análise: solução da recorrência. |
|
|
|
|
|
|
|
| 06/out |
Busca em Vetor |
(aula) |
(slides) |
(a) |
Problema, algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo a recorrência. |
| (c) |
Análise: solução da recorrência. Pior e melhor caso. |
|
|
|
|
|
|
|
| 11/out |
Busca em Vetor Ordenado |
(aula) |
(slides) |
(a) |
Problema, algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo e resolvendo a recorrência. |
|
|
|
|
|
|
|
| 13/out |
Busca Binária |
(aula) |
(slides) |
(a) |
Problema, algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo a recorrência. |
| (c) |
Analise: solução da recorrência. |
|
|
|
|
|
|
|
| 18/out |
Insertion Sort |
(aula) |
(slides) |
(a) |
Problema, algoritmo e exemplo. |
CLRS - Sec. 2.1 e Feof |
| (b) |
Análise: obtendo e resolvendo a recorrência. |
| (c) |
Insere: algoritmo e análise. Insertion Sort: concluindo a análise de pior e melhor caso. |
|
|
|
|
|
|
|
| 20/out |
Selection Sort |
(aula) |
(slides) |
(a) |
Algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo e resolvendo a recorrência. |
|
|
|
|
|
|
|
| 20/out |
Merge Sort |
(aula) |
(slides) |
(a) |
Intercala: problema, algoritmo, exemplo e análise. |
CLRS - Sec. 3.2 e Feof |
| (b) |
Merge Sort: algoritmo e exemplo. |
| (c) |
Análise: obtendo e resolvendo a recorrência. |
|
|
|
|
|
|
|
| 25/out |
Quick Sort |
(aula) |
(slides) |
(a) |
Partição: problema, algoritmo, exemplo e análise. |
CLRS - Sec. 7.1 e 7.2 e Feof |
| (b) |
Quick Sort: algoritmo e exemplo. |
| (c) |
Análise: pior caso |
| (d) |
Análise: melhor caso. Discussão. |
| | | | | | |
| 01/nov |
Filas de Prioridade e Heaps |
|
(slides a) |
(a) |
Introdução às Filas de Prioridade e Heaps |
CLRS - Sec. 6.1 e 6.2, e SW - Sec. 2.4 |
| (slides b) |
(b) |
Heap Binário: Implementação e Max-Heapify |
| (slides c) |
(c) |
Análise do Max-Heapify |
| | | | | | |
| 03/nov |
Contrução de Heaps e HeapSort |
|
(slides a) |
(a) |
Construção de Heaps |
CLRS - Sec. 6.3 e 6.4 |
| (slides b) |
(b) |
Análise de Construção de Heaps |
| (slides c) |
(c) |
HeapSort |
| | | | | | |
| 08/nov |
Panorama dos algoritmos de ordenação |
|
(slides a) |
(a) |
Parte 1 |
|
| (slides b) |
(b) |
Parte 2 |
| (slides c) |
(c) |
Parte 3 |
| | | | | | |
| 10/nov |
Limite Inferior para Ordenação |
|
(slides a) |
(a) |
Limite Inferior para Ordenação |
|
| | | | | | |
| 15/nov |
Outros Algoritmos de Ordenação |
|
(slides b) |
(b) |
CountingSort |
|
| (slides c) |
(c) |
RadixSort |
| (slides d) |
(d) |
BucketSort |
| | | | | | |
| 17/nov |
Permutações e combinações |
|
(slides) |
(a) |
Permutações e combinações com recursão. |
|
| | | | | | |
| 22/nov |
Backtracking 1 |
|
(slides) |
(a) |
Backtracking e o problema das 8 rainhas. |
|
| (b) |
Backtracking: conceitos e algoritmo. |
| (c) |
Backtracking: execução das 4 rainhas. |
| | | | | | |
| 24/nov |
Backtracking 2 |
|
(slides) |
(a) |
Problema do labirinto: versão backtracking recursivo. |
|
| (b) |
Problema do labirinto: versão backtracking com pilha. |
| | | | | | |
| 29/nov |
Removendo Recursão |
|
(slides a) |
(a) |
Removendo recursão de cauda |
|
| (slides b) |
(b) |
Removendo recursão usando pilha |
| (slides c) |
(c) |
Soma de subconjuntos usando backtracking |