CI811 Plano de Aula, algoritmos probabilísticos - randômicos - aleatorizados
2º semestre de 2008 sala: PC07 Horário: 3ª 13:30 e 6ª 15:30

Algoritmos e Probabilidade

Sumário: Conteúdo, Bibliografia, Avaliação, Listas, Programa, Calendário, notas, Diversão.
notas de aula
Objetivos: Apresentar os fundamentos das técnicas probabilísticas usadas em projetos de algoritmos e teoria da computação.
Conteúdo: Probabilidade discreta; Projeto e análise de algoritmos aleatorizados ; Classes de complexidade de algoritmos aleatorizados.
Para uma resenha do assunto da disciplina: A Taste of Randomized Computations, Oded Goldreich.

Carga horária: 60. Créditos: 4. Responsável: Jair Donadelli.

Bibliografia:

  1. Probablility and Computing, M. Mitzenmacher, E. Upfal. Cambridge University Press, 2005 (Biblioteca).
  2. Randomized Algorithms, R. Motwani e P. Raghavan. Cambridge University Press, 1995 (Biblioteca).

    3. Bibliografia complementar:

  3. Matemática concreta: fundamentos para a ciência da computação, Ronald L. Graham, Donald E. Knuth, Oren Patashnik (Biblioteca) - Capítulo 8.
  4. Concrete mathematics: a foundation for computer science, Ronald L. Graham, Donald E. Knuth, Oren Patashnik. (Biblioteca) - Capítulo 8.

    5. Material na web:

  5. Randomized algorithms in "primitive" cultures or what is the oracle complexity of a dead chicken? Jeffrey Shallit, ACM SIGACT News, Volume 23, Issue 4, Pages: 77 - 80
  6. Poker, chance and skill Noga Alon
  7. MIT OpenCourseWare, Notas de aula, Exercícios.
  8. Lecture notes on Probabilistic Methods in Computer Science, S. Naor
  9. On randomization in sequential and distributed algorithms, R. Gupta, S. Smolka, and S. Bhaskar.
  10. Randomized Methods in Computation, O. Goldreich
  11. Probabilistic Algorithms and Pseudorandom Generators, M. Tompa
  12. Coloring random graphs - an algorithmic perspective, M. Krivelevich.
  13. Random walks and electrical networks Doyle e Snell. (freely redistributable under the terms of the GNU General Public License)
  14. Concentration of measure for randomized algorithms: techniques and analysis, D. Dubhashi e S. Sen.

Sistema de avaliação:

trabalhos + seminarios

Calendário:

  • - Início das aulas: 28/06
  • - Último dia letivo: 22/11
  • - Não haverá aula durante a semana acadêmica.
 
     February 2008              March 2008               April 2008     
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                     1  2                        1            1  2  3  4  5 
      3  4  5  6  7  8  9      2  3  4  5  6  7  8      6  7  8  9 10 11 12 
     10 11 12 13 14 15 16      9 10 11 12 13 14 15     13 14 15 16 17 18 19 
     17 18 19 20 21 22 23     16 17 18 19 20 21 22     20 21 22 23 24 25 26 
     24 25 26 27 28 29        23 24 25 26 27 28 29     27 28 29 30 
                              30 31 

           May 2008                June 2008                July 2008      
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
                  1  2  3      1  2  3  4  5  6  7            1  2  3  4  5 
      4  5  6  7  8  9 10      8  9 10 11 12 13 14      6  7  8  9 10 11 12 
     11 12 13 14 15 16 17     15 16 17 18 19 20 21     13 14 15 16 17 18 19 
     18 19 20 21 22 23 24     22 23 24 25 26 27 28     20 21 22 23 24 25 26 
     25 26 27 28 29 30 31     29 30                    27 28 29 30 31
Programação das aulas: (tentativa) 
   
 1 Probabilidade discreta
 2 Identidade polinomial
 3 Probabilidade condicional e Independência
 4 Espaço produto
 5 Identidade polinomial revisitada
 6 Igualdade do produto de matrizes
 7 Teorema de Bayes
 8          Sigilo perfeito
 9          Filtros anti-Spam
10 Variáveis aleatórias discretas
11 Distribuições de Bernoulli, binomial, geométrica e uniforme
12 MAX 3-SAT
13 Quicksort aleatorizado e Análise de caso médio
14 Gerador de prováveis primos
   Modelos de Computação. 
15          Máquinas de Turing; Circuitos booleanos; RAM; Algoritmos aleatorizados. M.T. probabilística off-line
16 Classes de complexidade
17 BPP está na Hierarquia Polinomial
18 Desaleatorização de BPP usando geradores pseudoaleatórios
19 Construções de sequencias k-a-k independentes
20 Hash Universal
21 Grafos expansores e redução eficiente de erro
22 Desigualdades, desvios e momentos
23 Grandes desvios
24          Existência de PRGs
25          Cupon Collector, Balls and bins
26 Estruturas de dados. Treap e Skip lists
27 Hashing
   Algortimos distribuídos aleatorizados
28          O Jantar dos Filósofos
29          Eleição de Líder
30          Generais Bizantinos
Diversão:
Let's make a deal
Buffon's Nededle experiment
Optimizing Your Wife
Matching Nuts and Bolts
http://www.betweenwaters.com/probab/probab.html
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
FIM