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