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
Microsoft Excel 2019: VBA i makra
Wprowadzenie do uczenia maszynowego według Esposito
Kubernetes. Wzorce projektowe. Komponenty wielokrotnego użycia do projektowania natywnych aplikacji chmurowych
Kubernetes. Wzorce projektowe. Komponenty wielokrotnego użycia do projektowania natywnych aplikacji chmurowych
React 16. Framework dla profesjonalistów
CFD dla inżynierów. Praktyczne ćwiczenia na przykładzie systemu ANSYS Fluent (b2b)
Programuj z .NET. Praktyka ponad teorią
Niech Cię widzą w sieci! Blog lub serwis branżowy od podstaw
Jakość oprogramowania. Podręcznik dla profesjonalistów
Zaawansowane zarządzanie pamięcią w .NET: Lepszy kod, wydajność i skalowalność
Więcej produktów