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

Osoby które kupowały "Złożoność obliczeniowa", wybierały także:

• Ruby on Rails. Ćwiczenia 18,75 zÅ‚, (3,00 zÅ‚ -84%)
• Zen Steve'a Jobsa 29,67 zÅ‚, (8,90 zÅ‚ -70%)
• ASP.NET MVC. Kompletny przewodnik dla programistów interaktywnych aplikacji internetowych w Visual Studio 86,77 zÅ‚, (26,90 zÅ‚ -69%)
• TDD. Sztuka tworzenia dobrego kodu 48,54 zÅ‚, (19,90 zÅ‚ -59%)
• GitHub. Przyjazny przewodnik 32,90 zÅ‚, (16,45 zÅ‚ -50%)

Spis treści

Złożoność obliczeniowa -- 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)