Carga horária: 60 Créditos: 4 Responsável: Jair.
Aula 02 - Problema computacional. Representação.
Complexidade de tempo. Pior caso. Caso Médio.
Aula 03 - Notação assintótica.
Aula 04 - Busca em vetor ordenado: busca linear (caso médio).
Recorrências-Busca Binária
Aula 05 - Recorrências-Mergesort.
Aula 06 - Recorrência-caso geral para divisão-e-conquista.
Aula 07 - Quicksort,pior caso e caso médio.
Aula 08 - Quicksort-resolução da recorrência do caso médio.
Aula 09 - Quicksort probabilistico.
Aula 10 - Heap.
Aula 11 - Heapsort, filas de prioridade.
aula 12 - Prova
Aula 12 - Cota inferior para ordenação. Algoritmos de tempo linear para ordenação.
Aula 13 - Mediana e outras ordens - algoritmo probabilístico de tempo linear.
Aula 14 - Mediana e outras ordens - algoritmo determinístico de tempo linear.
Aula 15 - Busca.
Aula 16 - Árvores de busca.
Aula 17 - Árvores de busca.
Aula 18 - Árvores de busca.
Aula 19 - NP-completude.
Aula 20 - NP-completude.
Aula 21 - Seminario: The influence of caches on the performance of sorting - Vinicius
Aula 22 - Seminario: Improving memory performance of sorting algorithms - Yves
Aula 23 - Seminario: Efficient sorting using register and caches - Cassio
Aula 24 - Seminario: The influence of caches on the performance of heaps - Carolina
Aula 25 - Seminario: Graphs and hashing algorithms for modern architetures - Leonides
Aula 26 - Seminario: An empirical assessment of algorithms for constructing a minimum spannig tree - Claudinei
Aula 27 - Seminario: on-line approximate string searching algorithms -
Homero.
Aula 28 - Seminario: Fast and pratical approximate string matching -
Natascha.
Aula 29 - Seminario: The number of tests requerid to search an unordered table - Francisco
Bibliografia:
Sistema de avaliação:
Media ponderada de listas, provas e seminários.
Calendário de provas
Não haverá aulas em:
Listas de exercícios
Tópicos das aulas
Aula 01 - Motivação; cota superior e inferior para MAX A[1..n].
Aula 30 - prova
Calendario:
2005
--------------------------------------------------------------------
January February March
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 1 2 3 4 5 1 2 3 4 5
2 3 4 5 6 7 8 6 7 8 9 10 11 12 6 7 8 9 10 11 12
9 10 11 12 13 14 15 13 14 15 16 17 18 19 13 14 15 16 17 18 19
16 17 18 19 20 21 22 20 21 22 23 24 25 26 20 21 22 23 24 25 26
23 24 25 26 27 28 29 27 28 27 28 29 30 31
30 31
28: inicio do 1.sem 25: Sexta-feira Santa
--------------------------------------------------------------------
April May June
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 1 2 3 4 5 6 7 1 2 3 4
3 4 5 6 7 8 9 8 9 10 11 12 13 14 5 6 7 8 9 10 11
10 11 12 13 14 15 16 15 16 17 18 19 20 21 12 13 14 15 16 17 18
17 18 19 20 21 22 23 22 23 24 25 26 27 28 19 20 21 22 23 24 25
24 25 26 27 28 29 30 29 30 31 26 27 28 29 30
21: Tiradentes 1: Dia do trabalho 25: final 1.sem
27: prazo canc. disc. 26: Corpus Christi 30: inicio finais
--------------------------------------------------------------------
Datas dos seminários
25/05 -
The influence of caches on the performance of sorting -
Vinicius. Local Anfiteatro do Dinf. SLIDES
01/06 -
Improving memory performance of sorting algorithms - Yves. Local Anfiteatro do Dinf.
03/06 -
Efficient sorting using register and caches - Cassio. Local Anfiteatro do Dinf.
08/06 -
The influence of caches on the performance of heaps - Carolina. Local Lab 3.
10/06 -
Graphs and hashing algorithms for modern architetures -
Leonides. Local Anfiteatro A PC.
15/06 -
An empirical assessment of algorithms for constructing a minimum spannig
tree - Claudinei. Local Anfiteatro do Dinf.
17/06 -
on-line approximate string searching algorithms -
Homero. Local Anf A bloco PC
22/06 -
Fast and practical approximate string matching - Natascha. aud. dinf.
24/06 -
The number of tests requered to search an unordered table - Francisco