AEDs III 06/06/2011

Hoje a aula falou sobre algoritimos aproximados.

CONCEITO:
Um algoritimo aproximado é um algoritimo que resolve um problema semelhante ao problema desejado, dessa forma voce pode conseguir uma solução que apesar de não ser
ótima para o problema desejado é próxima da ótima.

Portanto um algoritimo aproximado seguro é um algoritimo cuja qualidade da solução possuí um limite inferior de qualidade que garante que ele será
próximo da solução ótima desejada.

Esse limite inferior é expresso como um fator por exemplo.

Para efeitos praticos então um algoritmo aproximado é um algoritimo cujo o fator da qualidade de sua solução sobre a qualidade da solução ótima é mensuravel.

Nota da Professora:
Se voce não for capaz de encontrar o fator exato de perda de qualidade tenha a tendencia de escolher um fator pior que o que voce terá, pois caso contrário
seu fator pode ser por demais otimista e não irá realmente garantir que seu algoritimo tem uma solução próxima da ótima.

A aula teve um grande exemplo de uso, e foi só.