UFC - Bacharelado em Ciência da Computação

Algoritmos Aproximativos (graduação CK132, pós CKP8099)

Semestre: 2017.1
Horário: Terças e Quintas 14:00-16:00
Local: Sala 10 - Bloco 950
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:

2 provas e 2 listas de exercicios

Livro-texto:

V.V.Vazirani, Approximation Algorithms, Springer, 2001, disponivel aqui

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