Programação das aulas

Sujeito a mudanças...

Abaixo MR denota o livro de Motwani e Raghavan.

Agosto

Setembro

• 1 de setembro (Aula 7):
  • Verificação de igualdade de polinômios
  • Emparelhamentos perfeitos em grafos bipartidos
  Leitura recomendada: cap 7, secs 7.2 e 7.3 do MR.
  Alternativamente, você pode ler partes das notas de aula ([iden.ps.gz][emp.ps.gz]) do curso do Gupta.
  Para ler um pouco sobre o modelo de computação paralela, a classe NC e alguns algoritmos para esse modelo, veja o começo do cap 12 do MR. Para mais detalhes sobre isso, veja o cap 15 do livro de complexidade do Papadimitriou (Papadimitriou, Computational Complexity, Addison-Wesley, 1994 [QA810 P213c].) Lá você verá comparações entre a classe P e a classe NC e suas derivadas, entre outras coisas.
  Exercícios da lista 2 que você deve entregar até a aula de sexta da outra semana (dia 15/9): 2,7,9,10 e 11.

• 6 e 8 de setembro:
  • Não haverá aula (primeira semana de break)

• 13 de setembro (Aula 8):
  • Algoritmo de Mulmuley, Vazirani e Vazirani, para encontrar um emparelhamento perfeito (se existir) em um grafo bipartido.
    Veja uns comentários sobre a análise do algoritmo acima que fizemos na aula. [ps.gz][pdf]

• 15 de setembro (Aula 9):
  • Algoritmo de Luby para encontrar um conjunto independente maximal
    

• 20 de setembro (Aula 10):
  • Continuação da análise do algoritmo de Luby
    Resumo da aula anterior [ps.gz][pdf]
  • Desigualdade de Chebyshev e seu uso para mostrar como ampliar a probabilidade de acerto de um algoritmo BPP
  • Lista 3
  Leitura recomendada: Sec 12.3 do MR.

• 22 de setembro (Aula 11):
  • Continuação da análise do algoritmo de Luby: nova prova do fato 2, que usa apenas independência 2 a 2
  • Desaleatorização do algoritmo de Luby

• 27 de setembro (Aula 12):
  • Algoritmos de aproximação probabilísticos
  • 2-aproximação probabilística para o MAXCUT e sua desaleatorização
  Exercícios da lista 3 que você deve entregar até a aula de sexta da outra semana (dia 15/10): 2, 3, 5 e 6.

• 29 de setembro (Aula 13):
  • Uma outra construção de variáveis 2 a 2 independentes
  • Outra versão desaleatorizada do algoritmo para o MAXCUT
  • Redução da probabilidade de erro em algoritmos probabilístico usando menos bits aleatórios
  Avaliação de desempenho: na semana de 16-20 de outubro, chamarei cada um dos alunos à minha sala para avaliar o seu desempenho na disciplina até agora. Cada aluno terá que me dizer quais exercícios das três listas de exercícios fez, quais não fez, quais nem tentou, etc, e será arguido sobre esses exercícios e tópicos vistos nas aulas. O aluno pode trazer suas notas de aula, anotações, livros, etc, para a entrevista, e receberá a posteriori uma nota.
  Se você tiver exercícios atrasados das listas 1 e 2 que gostaria de me entregar, por favor, o faça até a aula de sexta da semana que vem.

Outubro

Novembro