Używamy cookies, aby ułatwić korzystanie z Portalu. Możesz określić warunki przechowywania, dostępu do plików cookies w Twojej przeglądarce. Dowiedz się więcej.
strona główna Strona główna | Nowości | Promocje | Zapowiedzi Twoje konto | Zarejestruj | Schowek | Kontakt | Pomoc
mapa działów
Szukaj: szukanie zaawansowane
Koszyk
Książki

Złożoność obliczeniowa Język: 1

978-83-246-3235-0

Cena Brutto: 79.00

Cena netto: 75.24

Ilość:
Wersja: Drukowana
Autor Christos H. Papadimitriou
Liczba_stron 472
Wydawnictwo Helion
Oprawa twarda
Data_Wydania 2012-09-01
Poziom All Levels

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

Książka dla wnikliwych.

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)
powrót
 
Produkty Podobne
Access 2019 PL. Biblia
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Bezpieczeństwo systemu Linux w praktyce. Receptury. Wydanie II
Bezpieczeństwo systemu Linux w praktyce. Receptury. Wydanie II
Python. Uczymy się programowania
CorelDRAW 2018 PL. Ćwiczenia praktyczne
WordPress 5 dla początkujących
Deep Learning. Receptury
ABC CorelDRAW 2018 PL
AWS Certified Cloud Practitioner (CLF-C01) Cert Guide
Więcej produktów