Książka ALGORYTMY APROKSYMACYJNE jest poświęcona algorytmom aproksymacyjnym, czyli algorytmom jak najlepiej przybliżającym dokładne rozwiązanie zadań optymalizacyjnych.Składa się z trzech części.

Pierwsza dotyczy aproksymacyjnych algorytmów kombinatorycznych dla wielu ważnych problemów, druga - zastosowania programowania liniowego w projektowaniu algorytmów aproksymacyjnych, a trzecia - trudności związanych z aproksymacjami i zliczaniem.

Jest to doskonały podręcznik, o wielkich walorach dydaktycznych, napisany z dużym znawstwem tematu. Każdy rozdział kończy się ćwiczeniami do samodzielnego rozwiązania i rysem historycznym dotyczącym poruszanych w rozdziale problemów, wzbogacającym wiedzę Czytelnika. Książka jest przeznaczona dla studentów informatyki. Przyda się również pracownikom naukowym i informatykom tworzącym nowoczesne oprogramowanie.

Spis treści:

Rozdział 1. Wstęp 1.1. Ograniczenie dolne OPT1.1.1. Algorytm aproksymacyjny dla licznościowego problemu pokrycia wierzchołkowego1.1.2. Czy można poprawić gwarancję aproksymacji?1.2. Problemy dobrze określone i zależności minimaksowe1.3. Zadania1.4. UwagiCzęść I. Algorytmy kombinatoryczneRozdział 2. Pokrycie zbioru2.1. Algorytm zachłanny2.2. Rozwarstwianie2.3. Zastosowanie problemu najkrótszego nadsłowa2.4. Zadania2.5. UwagiRozdział 3. Drzewo Steinera i problem komiwojażera3.1. Metryczny problem drzewa Steinera 3.1.1. Algorytm z wykorzystaniem minimalnego drzewa rozpinającego3.2. Metryczny problem komiwojażera3.2.1. Prosty algorytm o współczynniku 23.2.2. Poprawianie współczynnika aproksymacji do 3/23.3. Zadania3.4. UwagiRozdział 4. Przekrój wielokrotny i k-przekrój4.1. Problem przekroju wielokrotnego4.2. Problem minimalnego k-przekroju4.3. Zadania4.4. UwagiRozdział 5. Problem k-centrum5.1. Zastosowanie odcinania parametrycznego do metrycznego problemu /.-centrum5.2. Wersja ważona5.3.Zadania5.4.UwagiRozdział 6. Rozcyklający zbiór wierzchołków6.1. Cyklomatyczne funkcje -wagowe6.2. Zastosowanie rozwarstwiania do problemu rozcyklającego zbioru wierzchołków6.3. Zadania6.4. UwagiRozdział 7. Najkrótsze nadsłowo7.1. Algorytm 4-aproksymacyjny7.2. Algorytm 3-aproksymacyjny7.2.1. Algorytm osiągający połowę optymalnej kompresji 7.3. Zadania7.4. Uwagi Rozdział 8. Problem plecakowy8.1. Algorytm pseudowielomianowy dla problemu plecakowego8.2. Algorytm FPTAS dla problemu plecakowego8.3. Silna NP-trudność a istnienie algorytmu FPTAS8.3.1. Czy algorytm FPTAS jest najlepszym algorytmem proksymacyjnym?8.4. Zadania8.5. Uwagi Rozdział 9. Pakowanie9.1. Asymptotyczny schemat PTAS9.2. Zadania9.3. UwagiRozdział 10. Najkrótsze uszeregowanie10.1. Algorytm 2-aproksymacyjny10.2. Algorytm PTAS dla problemu najkrótszego uszeregowan10.2.1. Problem pakowania z ustaloną liczbą rozmiarów przedmiotów10.2.2. Redukcja problemu najkrótszego szeregowania do ograniczonego problemu pakowania10.3. Zadania10.4. Uwagi

Rozdział 11. Euklidesowy problem komiwojażera

11.1. Algorytm11.2. Dowód poprawności11.3. Zadania11.4. UwagiCzęść II. Algorytmy oparte na programowaniu liniowym Rozdział 12. Wprowadzenie do dualności programowania liniowego12.1. Twierdzenie o dualności PL12.2. Zależności minimaksowe i dualność PL12.3. Dwie podstawowe techniki12.3.1. Porównanie technik oraz pojęcie luki całkowitości12.4. Zadania12.5. UwagiRozdział 13. Dopasowanie dualne dla problemu pokrycia zbioru 13.1. Analiza algorytmu zachłannego dla problemu pokrycia, zbioru wykonana metodą dopasowania dualnego13.1.1. Czy można poprawić gwarancję aproksymacji?13.2. Uogólnienia problemu pokrycia zbioru13.2.1. Zastosowanie dopasowania dualnego do problemu ograniczonego multipokrycia zbioru13.3. Zadania13.4. UwagiRozdział 14. Zastosowanie zaokrąglania do problemu pokrycia zbioru14.1. Prosty algorytm zaokrąglania14.2. Zaokrąglanie randomizowane14.3. Półcałkowitoliczbowość problemu pokrycia wierzchołkowego14.4. Zadania14.5. UwagiRozdział 15. Schemat prymalno—dualny dla problemu pokrycia zbioru15.1. Ogólny opis schematu15.2. Zastosowanie schematu prymalno-dualnego do problemu pokrycia zbioru15.3. Zadania15.4. UwagiRozdział 16. Maksymalna spełnialność16.1. Algorytm dla dużych klauzul16.2. Derandomizacja metodą warunkowej wartości oczekiwanej16.3. Algorytm zaokrąglania dla małych klauzul16.4. Algorytm 3/4-aproksymacyjny16.5. Zadania16.6. Uwagi

Rozdział 17. Szeregowanie zadań na niezależnych maszynach17.1. Odcinanie parametryczne w kontekście programowania liniowego17.2. Własności rozwiązań ekstremalnych17.3. Algorytm17.4. Inne własności rozwiązań ekstremalnych17.5. Zadania17.6. UwagiRozdział 18. Multiprzekrój i całkowitoliczbowy przepływ wielotowarowy w drzewach18.1. Problemy i ich relaksacje18.2. Algorytm oparty na schemacie prymalno-dualnym18.3. Zadania18.4. UwagiRozdział 19. Przekrój wielokrotny19.1. Interesująca relaksacja PL19.2. Randomizowany algorytm zaokrąglania19.3. Półcałkowitoliczbowość problemu wierzchołkowego przekroju wielokrotnego19.4. Zadania19.5. UwagiRozdział 20. Multiprzekrój w dowolnych grafach20.1. Sumaryczny przepływ wielotowarowy20.2. Algorytm zaokrąglania20.2.1. Wzrost obszaru: proces ciągły20.2.2. Proces dyskretny20.2.3. Algorytm znajdujący obszary20.3. Trudny przypadek20.4. Zastosowania problemu minimalnego multiprzekroju20.5. Zadania20.6. UwagiRozdział 21. Najbardziej rozrzedzony przekrój21.1. Wymagany przepływ wielotowarowy21.2. Sformułowanie w postaci zadania PL21.3. Metryki, upakowania przekrojów i ℓ1-zanurzalność21.3.1. Upakowania przekrojów21.3.2. ℓ1-zanurzalność metryk21.4. Mało zniekształcające ℓ1-zanurzenia metryk21.4.1. Zagwarantowanie, by pojedyczna krawędź nie była za bardzo skracana21.4.2. Zagwarantowanie, by żadna krawędź nie była za bardzo skracana21.5. Algorytm zaokrąglania21.6. Zastosowania21.6.1. Ekspansywność krawędziowa21.6.2. Przewodność21.6.3. Przekrój zrównoważony21.6.4. Uporządkowanie o minimalnych przekrojach21.7. Zadania21.8. UwagiRozdział 22. Las Steinera22.1. Relaksacja PL i zadanie dualne22.2. Schemat prymalno-dualny z jednoczesnymi zmianami22.3. Analiza22.4. Zadania22.5. UwagiRozdział 23. Sieć Steinera23.1. Relaksacja PL i półcałkowitoliczbowość23.2. Technika zaokrąglania iterowanego23.3. Charakteryzacja rozwiązań ekstremalnych23.4. Dowód przez zliczanie23.5. Zadania23.6. UwagiRozdział 24. Problem lokalizacji24.1. Interpretacja zadania dualnego24.2. Osłabianie prymalnych komplementarnych warunków swobody24.3. Algorytm oparty na schemacie prymalno-dualnym24.4. Analiza24.4.1. Złożoność czasowa24.4.2. Trudny przypadek24.5. Zadania24.6. UwagiRozdział 25. Problem k-mediany25.1. Relaksacja PL i zadanie dualne 25.2. Zarys algorytmu25.3. Zaokrąglanie randomizowane25.3.1. Derandomizacja25.3.2. Złożoność czasowa25.3.3. Trudny przypadek25.3.4. Luka całkowitości25.4. Zastosowanie relaksacji Lagrange'a w algorytmach aproksymacyjnych25.5. Zadania25.6. UwagiRozdział 26. Programowanie półokreślone26.1. Zadania ściśle kwadratowe i zadania wektorowe26.2. Własności macierzy półokreślonych dodatnio26.3. Problem programowania półokreślonego26.4. Algorytm zaokrąglania randomizowanego26.5. Poprawianie gwarancji aproksymacji dla problemu MAX-2SAT26.6. Zadania26.7. UwagiCzęść III. Inne zagadnienia Rozdział 27. Najkrótszy wektor27.1. Bazy, wyznaczniki i defekt ortogonalności27.2. Algorytm Euklidesa i algorytm Gaussa27.3. Ograniczenie dolne OPT za pomocą ortogonalizacji Grama-Schmidta27.4. Rozszerzenie na n wymiarów27.5. Krata dualna i jej zastosowanie algorytmiczne27.6. Zadania27.7. UwagiRozdział 28. Zliczanie28.1. Zliczanie rozwiązań DNF-formuły28.2. Niezawodność sieci28.2.1. Ograniczenie górne liczby przekrojów bliskich minimalnemu28.2.2. Analiza28.3. Zadania28.4. UwagiRozdział 29. Trudność aproksymacji29.1. Redukcje, luki i współczynniki trudności29.2. Twierdzenie PCP29.3. Trudność problemu MAX-3SAT29.4. Trudność problemu MAX-3SAT z ograniczoną liczbą wystąpień zmiennych29.5. Trudność problemów pokrycia wierzchołkowego i drzewa Steinera29.6. Trudność problemu kliki29.7. Trudność problemu pokrycia zbioru29.7.1. Charakteryzacja NP — jednorundowy system dowodów z dwoma rzecznikami29.7.2. Gadżet29.7.3. Zmniejszanie prawdopodobieństwa błędu poprzez wykonania równolegle29.7.4. Redukcja29.8. Zadania29.9. UwagiRozdział 30. Problemy otwarte30.1. Problemy z rozwiązaniami o stałym współczynniku aproksymacji30.2. Inne problemy optymalizacyjne30.3. Problemy zliczania30.4. UwagiRozdział A. Przegląd teorii złożoności obliczeniowejA.l. Świadectwa i klasa NPA.2. Redukcje i NP-zupełnośćA.3. Problemy NP-optymalizacyjne i algorytmy aproksymacyjneA.3.l. Redukcje zachowujące współczynnik aproksymacjiA.4. Randomizowane klasy złożonościA.5. SamoredukowalnośćA.6. UwagiRozdział B. Podstawowe fakty z teorii prawdopodobieństwa B.l. Wartość oczekiwana i momentyB.2. Odchylenia od wartości oczekiwanejB.3. Podstawowe rozkłady prawdopodobieństwaB.4. Uwagi

Podobne książki:

Elementy teoretycznych podstaw informatyki W książce "Elementy teoretycznych podstaw informatyki" przedstawiono ważniejsze zagadnienia teoretycznych podstaw informatyki należące do standardu kształcenia informatyków. Omawiane zagadnienia należą do warstwy wolnozmiennych zagadnień informatyki i...

 

Niezawodność oprogramowania To właśnie programista może w znacznym stopniu przyczynić się do tego, iż wykrywanie błędów i walka z nimi staną się zadaniami łatwiejszymi i bardziej skutecznymi - tę właśnie tezę Autor stara się udowodnić w niniejszej książce, ilustrując...

 

Pakiet dwóch książek: Rational Unified Process od strony praktycznej i Rational Unified Process od strony teoretycznej Pakiet składa się z dwóch książek: "Rational Unified Process od strony praktycznej" oraz "Rational Unified Process od strony teoretycznej" Rational Unified Process®  od strony teoretycznej: Mówimy, że dane przedsięwzięcie programistyczne...