Złożoność obliczeniowa

Nowe wydanie klasycznego podręcznika!

Złożoność obliczeniowa jest działem informatyki poświęconym badaniu przyczyn, które sprawiają, że komputery nie do końca radzą sobie z rozwiązywaniem pewnych problemów. Teraz masz przed sobą najlepszy podręcznik z teorii złożoności obliczeniowej. Znajdziesz w nim praktyczne informacje na temat algorytmów i ich wydajności.

Dowiesz się, jak ocenić i obliczyć ich złożoność oraz jakie pułapki czekają na Ciebie. Ponadto możesz zdobyć szczegółowe informacje dotyczące problemów, których przy obecnym stanie wiedzy nie da się rozwiązać w zadowalającym czasie (wśród nich nie brak klasycznego problemu komiwojażera). Autor zwraca również uwagę na obliczenia równoległe, hierarchię wielomianową oraz obliczenia zliczające.

Książka ta jest przeznaczona dla studentów informatyki i świetnie sprawdzi się na przedmiotach poświęconych algorytmom. Powinni po nią sięgnąć również programiści odpowiedzialni za implementację kluczowych algorytmów.

Zagadnienia podejmowane w tej książce:

• maszyny Turinga
• logika
• relacje między klasami złożoności
• problemy NP-zupełne
• kryptografia

Przyjazne przedstawienie problemów świata informatyki!

Rozdziały:

I. ALGORYTMY (17)
1. Problemy i algorytmy (19)

• 1.1. Osiągalność w grafie (19)
• 1.2. Maksymalny przepływ (23)
• 1.3. Problem komiwojażera (27)
• 1.4. Uwagi, literatura i problemy (27)

2.Maszyny Turinga (33)

• 2.1. Podstawy maszyn Turinga (33)
• 2.2. Maszyny Turinga jako algorytmy (37)
• 2.3. Maszyny Turinga z wieloma napisami (40)
• 2.4. Przyspieszanie liniowe (43)
• 2.5. Ograniczenia przestrzenne (45)
• 2.6. Maszyny o dostępie swobodnym (47)
• 2.7. Maszyny niedeterministyczne (54)
• 2.8. Uwagi, literatura i problemy (58)

3. Nierozstrzygalność (65)

• 3.1. Uniwersalna maszyna Turinga (65)
• 3.2. Problem stopu (66)
• 3.3. Więcej nierozstrzygalności (68)
• 3.4. Uwagi, literatura i problemy (72)

II. LOGIKA (77)
4. Logika boolowska (79)

• 4.1. Wyrażenia boolowskie (79)
• 4.2. Spełnialność i prawomocność (82)
• 4.3. Funkcje i układy boolowskie (84)
• 4.4. Uwagi, literatura i problemy (88)

5. Logika pierwszego rzędu (91)

• 5.1. Składnia logiki pierwszego rzędu (91)
• 5.2. Modele (93)
• 5.3. Wyrażenia prawomocne (98)
• 5.4. Aksjomaty i dowody (103)
• 5.5. Twierdzenie o zupełności (108)
• 5.6. Konsekwencje twierdzenia o zupełności (111)
• 5.7. Logika drugiego rzędu (114)
• 5.8. Uwagi, literatura i problemy (117)

6. Nierozstrzygalność w logice (123)

• 6.1. Aksjomaty teorii liczb (123)
• 6.2. Obliczenie jako koncepcja teorioliczbowa (126)
• 6.3. Nierozstrzygalność i niezupełność (130)
• 6.4. Uwagi, literatura i problemy (132)

III. P I NP (135)
7. Relacje między klasami złożoności (137)

• 7.1. Klasy złożoności (137)
• 7.2. Twierdzenie o hierarchii (140)
• 7.3. Metoda osiągalności (143)
• 7.4. Uwagi, literatura i problemy (149)

8. Redukcje i zupełność (155)

• 8.1. Redukcje (155)
• 8.2. Zupełność (160)
• 8.3. Charakterystyki logiczne (165)
• 8.4. Uwagi, literatura i problemy (169)

9. Problemy NP-zupełne (173)

• 9.1. Problemy w NP (173)
• 9.2. Odmiany spełnialności (175)
• 9.3. Problemy teoriografowe (179)
• 9.4. Zbiory i liczby (188)
• 9.5. Uwagi, literatura i problemy (193)

10. Klasa coNP i problemy funkcyjne (207)

• 10.1. Klasy NP i coNP (207)
• 10.2. Prymarność (209)
• 10.3. Problemy funkcyjne (214)
• 10.4. Uwagi, literatura i problemy (219)

11. Obliczenia losowe (225)

• 11.1. Algorytmy losowe (225)
• 11.2. Klasy złożoności losowej (236)
• 11.3. Źródła losowe (241)
• 11.4. Złożoność układu (247)
• 11.5. Uwagi, literatura i problemy (250)

12. Kryptografia (259)

• 12.1. Funkcje jednokierunkowe (259)
• 12.2. Protokoły (266)
• 12.3. Uwagi, literatura i problemy (271)

13. Aproksymowalność (277)

• 13.1. Algorytmy aproksymacyjne (277)
• 13.2. Aproksymacja i złożoność (286)
• 13.3. Nieaproksymowalność (294)
• 13.4. Uwagi, literatura i problemy (296)

14. O przeciwstawności klas P i NP (303)

• 14.1. Mapa NP (303)
• 14.2. Izomorfizm i gęstość (305)
• 14.3. Wyrocznie (311)
• 14.4. Układy monotoniczne (315)
• 14.5. Uwagi, literatura i problemy (320)

IV. WNĘTRZE P (325)
15. Obliczenia równoległe (327)

• 15.1. Algorytmy równoległe (327)
• 15.2. Równoległe modele obliczeń (335)
• 15.3. Klasa NC (341)
• 15.4. Algorytmy RNC (345)
• 15.5. Uwagi, literatura i problemy (348)

16. Przestrzeń logarytmiczna (359)

• 16.1. Problem L=NL (359)
• 16.2. Naprzemienność (362)
• 16.3. Osiągalność nieskierowana (364)
• 16.4. Uwagi, literatura i problemy (366)

V. WYCHODZĄC POZA NP (371)
17. Hierarchia wielomianowa (373)

• 17.1. Problemy optymalizacji (373)
• 17.2. Hierarchia wielomianowa (384)
• 17.3. Uwagi, literatura i problemy (390)

18. Obliczenia zliczające (395)

• 18.1. Permanent (395)
• 18.2. Klasa ⊕P (402)
• 18.3. Uwagi, literatura i problemy (405)

19. Przestrzeń wielomianowa (407)

• 19.1. Naprzemienność i gry (407)
• 19.2. Gry przeciw naturze i protokoły interakcyjne (418)
• 19.3. Więcej problemów PSPACE-zupełnych (427)
• 19.4. Uwagi, literatura i problemy (433)

20. Spoglądając jeszcze dalej (437)

• 20.1. Czas wykładniczy (437)
• 20.2. Uwagi, literatura i problemy (443)