Prof. Carlos Martinhon -  IC/UFF

Disciplina de Algoritmos Randômicos e Aproximativos
      a)  Programa:
  1. Tópicos em complexidade de Algoritmos: Maquina RAM probabilistíca, complexidades local e assintótica, recorrência probabilística, etc.
  2. Tópicos em Probabilidade: Espaço de probabilidade, Variáveis Aleatórias Discretas, Distribuições Binomial e Geométrica, Desigualdade de Tchebyshev, etc.
  3. Métodos de Monte Carlo e Las Vegas: Conceitos Básicos, Aplicações em Algoritmos em Grafos, Ordenação, Estrutura de Dados, Criptografia, Biologia Computacional, Geometria Computacional, etc.
  4. Classes de Complexidade: Problemas de decisão, Algoritmos randômicos com erro zero, unilateral e bilateral, Classes, P, NP, ZPP, RP, co-RP, BPP, PP.
  5. Algoritmos Aproximativos Determinísticos: Definições Básicas, Aplicações em Escalonamento de Tarefas, Caixeiro Viajante, Mochila 0/1, Problemas de Recobrimento, Alguns resultados de não-aproximação.
  6. Algoritmos Randômicos Aproximativos: Definições básicas, Desigualdades de Chernoff-Hoffding, Método probabilístico, Arredondamento Randômico, Técnicas de derandomização, Aplicações.
 
   
      b) Bibliografia:
  1. R. Motwani, P. Raghavan, [1995],  Randomized algorithms, Cambridge University Press.
  2. D.S Hochbaum [1997], Approximation algorithms for NP-hard problems, PWS Publishing Company.
  3. M. Mitzenmacher, E. Upfal [2005], Probability and Computing: Randomized Algorithms and Probabilistic Analysis,  Cambridge University Press.
  4. N. Alon, J. Spencer [1992], The Probabilistic Method, Wiley, New York.
  5. C. Martinhon [2002], Algoritmos Randômicos em Otimização Combinatória, Apostila do XXXIV Simpósio Brasileiro de Pesquisa Operacional, (PDF Files) 122 págs.

     c) Outros
  1. Avaliação: (Aprovação acima de 6,0)
            - Cada lista corresponde a 20% da nota.
            - 80% de presença: 10% da nota
            - Apresentação do Trabalho: 30% da nota    
  2. Transparências (PDF File)
  3. Listas de Exercícios (em PDF):  Lista1, Lista2, Lista3, Lista4
  4. Algumas sugestões para Trabalho:
            (a) Random Skip Lists,
            (b) Algoritmos Aproximativos p/ o TSPB (Traveling Salesman Problem with Backhauls),
            (c) Algoritmo Randômico p/ o Problema do Corte Mínimo em Grafos,
            (d) O problema da Seleção Randômica,
            (e)  Impressão Digital (Fingerprinting),                                                                                                                       (f)  Problema da Sequência mais Próxima (Closest String Problem), etc.
  5. Links Interessantes: Algoritmos Randômicos.

NOTA: O Acrobat Reader pode ser encontrado aqui !!