Algoritmos de Aproximação

Prévia do material em texto

MO418/MC748 - Algoritmos de Aproximação - 2012 
Prof. Flávio Miyazawa 
 
Informações sobre a disciplina 
 
 Docente da Disciplina 
 Tópicos a serem vistos 
 Sobre Algoritmos de Aproximação 
 Alguns problemas que iremos considerar durante o curso 
 Avaliação 
 Notas Finais 
 Aulas e Atendimento 
 Listas de Exercício 
 Transparências 
 Apresentações 
 Datas Importantes 
 Bibliografia 
Theoretical Computer Science Cheat Sheet by Steve Seiden 
 
Docente da Disciplina 
Docente: Flávio Keidi Miyazawa 
E-mail: fkm@ic.unicamp.br 
Sala: IC-30 
Tópicos a serem vistos 
Nesta disciplina iremos estudar sobre Algoritmos de Aproximação e veremos os seguintes tópicos. 
Classes de Complexidade 
Algoritmos de Aproximação Combinatórios 
Métodos usando Programação Linear 
Métodos Probabilísticos 
Métodos usando Programação Semidefinida 
Resultados de Inaproximabilidade 
Alguns problemas que iremos considerar durante o curso 
Mochila (Knapsack) 
Empacotamento (Bin-Packing) 
Caixeiro Viajante (Traveling Salesman Problem) 
Corte Máximo (MAX-CUT) 
Árvore e Floresta de Steiner 
Escalonamento de Tarefas (Scheduling) 
Cobertura por Vértices (Vertex Cover) 
Cobertura por Conjuntos (Set Cover) 
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#docente
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#programa
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/algaprox.html
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#problemas
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#avaliacao
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/NotasAprox.html
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#horarios
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#listas
http://www.ic.unicamp.br/~fkm/lectures/aprox.pdf
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#apresentacoes
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#datas
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/index.html#bibliografia
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/cheat.pdf
http://bit.csc.lsu.edu/news/news200206121.html
http://www.dcc.unicamp.br/~fkm/
http://www.ic.unicamp.br/~fkm/problems/algaprox.html
http://www.ic.unicamp.br/~fkm/empacotamento.html
http://www.ic.unicamp.br/~fkm/escalonamento.html
Satisfatibilidade Máxima (MAX-SAT) 
Coloração de Vértices 
Outros problemas 
Avaliação da Disciplina 
A avaliação será feita através de uma Prova (P), apresentação de uma aula/seminário com entrega do texto da 
aula e participação em seminários (T) e listas de exercícios (L). 
 
A nota L será calculada a partir de t listas de exercícios. De cada lista será sorteado um exercício que o professor 
irá corrigir. A nota L será calculada pela média aritmética das listas de exercícios corrigidas. Exercícios copiados ou 
feitos em conjunto terão valor -10.0 (negativo). Mas o professor acha interessante que alunos discutam o 
exercício em conjunto (enquanto não sabem resolvê-lo). A escrita sempre deve ser individual. A avaliação da nota 
T irá considerar o conteúdo do seminário e texto, apresentação e a participação nos demais seminários. 
 
A nota da avaliação será N será igual a (P+T+L)/3. 
Nota Final Conceito 
N>=8.5 A 
7.0<=N<8.5 B 
5.0<=N<7.0 C 
N<5.0 D 
 
Listas de Exercício 
 Lista 1 p/ 20 de março as 16hs. 
 Lista 2 p/ 29 de março as 16hs. 
 Lista 3 p/ 10 de abril as 16hs. 
Datas Importantes 
Prova Teórica: 5 de Junho. 
Seminários: A partir do início de Junho. 
Listas de Exercícios: Prazo de uma a duas semanas. 
Bibliografia 
V. Vazirani. Approximation Algorithms. 2001. Springer-Verlag. 
D. P. Williamson and D. B. Shmoys. The Design of Approximation Algorithms. 2010. 
Cambridge University Press (disponível online). 
M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. 
Miyazawa, J.C. Pina Jr., J. Soares, Y. Wakabayashi. Uma introdução sucinta a algoritmos de aproximação. 
23o Colóquio Brasileiro de Matemática, IMPA, Rio de Janeiro. 
 
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/listas/lista1.pdf
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/listas/lista2.pdf
http://www.ic.unicamp.br/~fkm/disciplinas/mo418/2012s1/listas/lista3.pdf
http://www.designofapproxalgs.com/
http://www.designofapproxalgs.com/
http://www.designofapproxalgs.com/