CI811 Plano de Aula
CI093 - Tópicos em Análise Numérica/CI811 - Tópicos em Algoritmos
Algoritmos Probabilísticos
Segundo semestre de 2006
sala: PA03
Horário: 4a e 6a 17:30
|
|
Listas de exercicios: lista 1,
lista 2,
lista 3,
lista 4,
lista 5,
lista 6,
lista 7
Notas
Para uma resenha do assunto:
A Taste of Randomized Computations.
(ps)
Conteúdo:
- Probabilidade discreta.
- Leis de grandes desvios.
- Algoritmos probabilísticos: teste de primalidade; cortes mínimos;
roteamento no hipercubo; 2-sat e 3-sat; reconhecimento de
padrões em textos; emparelhamentos perfeitos; teste para
nulidade de polinômios em várias variáveis; conjuntos
independentes maximais; elemento majoritário de uma
sequência; verificação de produto de matrizes; teste de
igualdade de conjuntos; escolha de líder em redes.
- Classes de complexidade de algoritmos probabilisticos: BPP, RP e ZPP.
|
|
Objetivos:
Apresentar ao aluno os fundamentos das técnicas probabilísticas
usadas em projetos de algoritmos e teoria da computação.
Carga horária: 60.
Créditos: 4.
Responsável: Jair Donadelli.
Bibliografia:
- Probablility and Computing,
M. Mitzenmacher,
E. Upfal. Cambridge University Press, 2005.
- Randomized Algorithms, R. Motwani e P. Raghavan. Cambridge University Press, 1995.
Bibliografia Complementar:
- Random walks and
electrical networksDoyle e Snell. First published in 1984 by
the Mathematical Association of America; now freely redistributable
under the terms of the GNU General Public License
- Matemática concreta, Knuth, Graham e Pataschinik
- Concentration of measure for randomized algorithms:
techniques and analysis, D. Dubhashi e S. Sen.
-
Randomized algorithms - Lecture notes, M. Goemans.
-
Lecture notes on Probabilistic Methods in Computer Science, S. Naor
-
On randomization in sequential and distributed algorithms,
R. Gupta, S. Smolka, and S. Bhaskar.
-
Randomized Methods in Computation, O. Goldreich
-
Some elements of probability theory, B. Reed
-
Probabilistic Algorithms and Pseudorandom Generators,
M. Tompa
-
Coloring random graphs - an algorithmic perspective,
M. Krivelevich.
- Optimizing Your Wife
-
15-859(M): Randomized Algorithms, Anupam Gupta and Shuchi
Chawla
Sistema de avaliação:
1 prova
1 lista
1 lista
![](../Cartoons/menimalu.gif)
Calendário:
- 31/07 - Início das aulas
- 07/09 - Feriado: Independencia
- 08/09 - Feriado: Padroeira
- 28/09 - CI093 Prazo final para cancelamento de matricula
- 11/10 - Prova 1:
- 12/10 - Feriado: Padroeira (do Brasil dessa vez)
- 02/11 - Feriado: Finados
- - Prova 2:
- 30/11 - Último dia letivo
- 06/12 - CI093 Prova final todo conteúdo das aulas
|
|
August 2006 September 2006 October 2006
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 3 4 5 1 2 1 2 3 4 5 6 7
6 7 8 9 10 11 12 3 4 5 6 7 8 9 8 9 10 11 12 13 14
13 14 15 16 17 18 19 10 11 12 13 14 15 16 15 16 17 18 19 20 21
20 21 22 23 24 25 26 17 18 19 20 21 22 23 22 23 24 25 26 27 28
27 28 29 30 31 24 25 26 27 28 29 30 29 30 31
October 2006 November 2006 December 2006
Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa
1 2 3 4 5 6 7 1 2 3 4 1 2
8 9 10 11 12 13 14 5 6 7 8 9 10 11 3 4 5 6 7 8 9
15 16 17 18 19 20 21 12 13 14 15 16 17 18 10 11 12 13 14 15 16
22 23 24 25 26 27 28 19 20 21 22 23 24 25 17 18 19 20 21 22 23
29 30 31 26 27 28 29 30 24 25 26 27 28 29 30
31
aula 01 - exemplos: Quicksort aleatorizado; calculo aproximado de pi
aula 02 - probabilidade dicreta, definicoes e propriedades elementares
aula 03 - probabilidade condicional, algroritmo pobabilístico para
identidade polinomial, espaço poduto, lei das
probabilidades totais.
aula 04 - algoritmo probabilístico para igualdade de matrizes.
aula 05 - igualdade de strings e busca de padrões.
aula 06 - probilidade discreta (caso enumeravel), variavel aleatoria,
valor esperado
aula 07 - v.a. Bernoulli, Binomial e geometrica. Esperanca condicional
aula 08 - tempo medio Quicksort, "cupon collector"
aula 09 - momentos e desvios - desigualdades de Markov e Chebyshev
aula 10 - funcao geadora de momentos
aula 11 - leis de grandes desvios - Chernoff
aula 12 - leis de grandes desvios - Chernoff
aula 13 - roteamento no hipercubo
aula 14 - roteamento no hipercubo
aula 15 - distribuicoes continuas: vars aleatorias, distribuicao,
funcao densidade e esperanca.
aula 16 - metodo monte carlo, estimacao de pi, agulhas de Buffon
aula 17 - cadeias de Markov
aula 18 - cadeias de Markov
aula 19 - 2SAT
aula 20 - classificação de estados e "gambler ruin"
aula 21 - distribuicoes estacionarias, passeios aleatorios em grafos
aula 22 - s-t conexidade
Numbers that fool the Fermat test are called Carmichael numbers, and
little is known about them other than that they are
extremely rare. There are 255 Carmichael numbers below
100,000,000. The smallest few are 561, 1105, 1729, 2465,
2821, and 6601. In testing primality of very large numbers
chosen at random, the chance of stumbling upon a value that
fools the Fermat test is less than the chance that cosmic
radiation will cause the computer to make an error in
carrying out a "correct" algorithm. Considering an algorithm
to be inadequate for the first reason but not for the second
illustrates the difference between mathematics and
engineering.
Abelson
& Sussman (agredecimentos ao Boiko pela referência)
FIM
Last modified: Thu Feb 22 16:54:35 BRST 2007