UFC - Bacharelado em Ciência da Computação
Algoritmos Aproximativos (graduação CK132, pós CKP132)
Semestre: 2011.2
Horário: Terças e Quintas 14:00-16:00
Local: Sala 1435 - Bloco 915
Atendimento: Na minha sala, em qualquer horário, desde que com reserva antecipada. Uma reserva pode ser feita via correio eletrônico ou na sala de aula.
Plano de Aula e Notas
Listas de Exercícios
Ementa:
Um algoritmo aproximativo é um algoritmo que retorna um valor não necessariamente ótimo, mas um agrantia de proximidade do ótimo.
Por exemplo, um algoritmo de minimização (maximização) é 2-aproximativo se sua resposta é no pior caso duas vezes maior (menor) que o ótimo.
O conteúdo deste curso é formado por diversos exemplos e técnicas de algoritmos aproximativos.
A ementa do curso é a seguinte:
- Classificação de Problemas
- Classe APX
- Classe PTAS
- Classe FPTAS
- Problemas Inaproximáveis
- Algoritmos Combinatórios
- Cobertura de Vértices
- Caixeiro Viajante
- Árvore de Steiner
- Corte Mínimo
- Problema da Mochila
- Bin Packing
- MAXSAT
- Algoritmos de Programação Linear
- Cobertura de Vértices
- MAXSAT
- k-Mediana
- Localização de Facilidades
- Dificuldade de Aproximação
- MAX3SAT
- Cobertura de Vértices
- Árvore de Steiner
- Clique
Avaliação:
- primeira parcial em ??/??/2011, às 14:00h (inclui toda a matéria vista até então)
- segunda parcial em ??/??/2011, às 14:00h (inclui toda a matéria vista desde a primeira prova)
- terceira parcial em ??/??/2011, às 14:00h (inclui toda a matéria vista desde a segunda prova)
- AF em ??/??/2011 às 14:00 (inclui toda a matéria)
- 2o chamada das parciais em ??/??/2011 às 14:00 (inclui toda a matéria - será ao final do semestre)
- 2o chamada da AF em ??/??/2011 às 14:00 (inclui toda a matéria)
Livro-texto:
Bibliografia adicional:
- Carvalho, Cerioli, Dahab, Feofiloff, Fernandes, Ferreira, Guimarães, Miyazawa, Pina Jr, Soares, Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, IMPA, 2001, disponivel aqui