księgarnia informatyczna

Książka informatyczna wydawnictw: BTC Edition Exit Helion Help Microsoft Press Mikom Nakom PJWSTK Read Me Robomatic Skalmierski Tortech Translator WKŁ WNT WSISIZ

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)

adobe algorytmy apache asp autocad asembler bsd c++ c# delphi dtp excel flash html java javascript linux matlab mysql office php samba voip uml unix visual studio windows word

Księgarnia Informatyczna  zaprasza.