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:

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

    3. Bibliografia Complementar:

  3. 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
  4. Matemática concreta, Knuth, Graham e Pataschinik
  5. Concentration of measure for randomized algorithms: techniques and analysis, D. Dubhashi e S. Sen.
  6. Randomized algorithms - Lecture notes, M. Goemans.
  7. Lecture notes on Probabilistic Methods in Computer Science, S. Naor
  8. On randomization in sequential and distributed algorithms, R. Gupta, S. Smolka, and S. Bhaskar.
  9. Randomized Methods in Computation, O. Goldreich
  10. Some elements of probability theory, B. Reed
  11. Probabilistic Algorithms and Pseudorandom Generators, M. Tompa
  12. Coloring random graphs - an algorithmic perspective, M. Krivelevich.
  13. Optimizing Your Wife
  14. 15-859(M): Randomized Algorithms, Anupam Gupta and Shuchi Chawla

Sistema de avaliação:

1 prova
1 lista
1 lista

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