Złożoność obliczeniowa (ebook)(audiobook)(audiobook)

Spis treści

Od tłumacza (11)


Przedmowa (13)


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)

Skorowidz (453)


Indeks autorów (463)

pokaż cały spis treści

ukryj recenzje