| 09/nov |
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. |
| | | | | | |
| 11/nov |
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. |
|
|
|
|
|
|
|
| 16/nov |
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. |
|
|
|
|
|
|
|
| 18/nov |
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. |
|
|
|
|
|
|
|
| 23/nov |
Busca em Vetor Ordenado |
(aula) |
(slides) |
(a) |
Problema, algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo e resolvendo a recorrência. |
|
|
|
|
|
|
|
| 25/nov |
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. |
|
|
|
|
|
|
|
| 30/nov |
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. |
|
|
|
|
|
|
|
| 02/dez |
Selection Sort |
(aula) |
(slides) |
(a) |
Algoritmo e exemplo. |
Feof |
| (b) |
Análise: obtendo e resolvendo a recorrência. |
|
|
|
|
|
|
|
| 02/dez |
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. |
|
|
|
|
|
|
|
| 07/dez |
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. |
| | | | | | |
| 18/jan |
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 |
| | | | | | |
| 20/jan |
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 |
| | | | | | |
| 25/jan |
Panorama dos algoritmos de ordenação |
|
(slides a) |
(a) |
Parte 1 |
|
| (slides b) |
(b) |
Parte 2 |
| (slides c) |
(c) |
Parte 3 |
| | | | | | |
| 27/jan |
Limite Inferior para Ordenação e Outros Algoritmos |
|
(slides a) |
(a) |
Limite Inferior para Ordenação |
|
| (slides b) |
(b) |
CountingSort |
| (slides c) |
(c) |
RadixSort |
| (slides d) |
(d) |
BucketSort |
| | | | | | |
| 03/fev |
Permutações e combinações |
|
(slides) |
(a) |
Permutações e combinações com recursão. |
|
| | | | | | |
| 08/fev |
Backtracking 1 |
|
(slides) |
(a) |
Backtracking e o problema das 8 rainhas. |
|
| (b) |
Backtracking: conceitos e algoritmo. |
| (c) |
Backtracking: execução das 4 rainhas. |
| | | | | | |
| 10/fev |
Backtracking 2 |
|
(slides) |
(a) |
Problema do labirinto: versão backtracking recursivo. |
|
| (b) |
Problema do labirinto: versão backtracking com pilha. |
| | | | | | |
| 22/fev |
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 |