Algorytmy przybliżone - wykład

Nasza ocena:

3
Pobrań: 49
Wyświetleń: 679
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Algorytmy przybliżone - wykład - strona 1 Algorytmy przybliżone - wykład - strona 2 Algorytmy przybliżone - wykład - strona 3

Fragment notatki:

ALGORYTMY PRZYBLIŻONE
Analiza
Analiza eksperymentalna - wygenerowanie pewnego zbioru X instancji badanego problemu Π oraz rozwiązanie wszystkich tych instancji badanym algorytmem A
Ocena jakości algorytmu - Średnia odległość od optimum, maksymalna odległość od optimum Analiza probabilistyczna
Analiza najgorszego przypadku
Współczynnik osiągalności aproksymacyjnej - współczynnik najgorszego przypadku dla problemu Π opisany wzorem: Schematy aproksymacyjne
PTAS - wielomianowe schematy aproksymacyjne
FPTAS - w pełni wielomianowe schematy aproksymacyjne
Zakres stosowalności
... zobacz całą notatkę



Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz