Wprowadzenie do teorii obliczeń

• Kategorie:
  1. Ebooki i Audiobooki »
  2. Informatyka
• Język wydania: polski
• ISBN: 978-83-01-21099-1
• ISBN druku: 978-83-01-20926-1
• Liczba stron: 500
• Sposób dostarczenia produktu elektronicznego
  Produkty elektroniczne takie jak Ebooki czy Audiobooki są udostępniane online po uprzednim opłaceniu (PayU, BLIK) na stronie Twoje konto > Biblioteka.

  Pliki można pobrać zazwyczaj w ciągu kilku-kilkunastu minut po uzyskaniu poprawnej autoryzacji płatności, choć w przypadku niektórych publikacji elektronicznych czas oczekiwania może być nieco dłuższy.

  Sprzedaż terytorialna towarów elektronicznych jest regulowana wyłącznie ograniczeniami terytorialnymi licencji konkretnych produktów.
• Ważne informacje techniczne
• Minimalne wymagania sprzętowe:
  • procesor: architektura x86 1GHz lub odpowiedniki w pozostałych architekturach
  • Pamięć operacyjna: 512MB
  • Monitor i karta graficzna: zgodny ze standardem XGA, minimalna rozdzielczość 1024x768 16bit
  • Dysk twardy: dowolny obsługujący system operacyjny z minimalnie 100MB wolnego miejsca
  • Mysz lub inny manipulator + klawiatura
  • Karta sieciowa/modem: umożliwiająca dostęp do sieci Internet z prędkością 512kb/s
• Minimalne wymagania oprogramowania:
  • System Operacyjny: System MS Windows 95 i wyżej, Linux z X.ORG, MacOS 9 lub wyżej, najnowsze systemy mobilne: Android, iPhone, SymbianOS, Windows Mobile
  • Przeglądarka internetowa: Internet Explorer 7 lub wyżej, Opera 9 i wyżej, FireFox 2 i wyżej, Chrome 1.0 i wyżej, Safari 5
  • Przeglądarka z obsługą ciasteczek i włączoną obsługą JavaScript
  • Zalecany plugin Flash Player w wersji 10.0 lub wyżej.
• Informacja o formatach plików:
  • PDF - format polecany do czytania na laptopach oraz komputerach stacjonarnych.
  • EPUB - format pliku, który umożliwia czytanie książek elektronicznych na urządzeniach z mniejszymi ekranami (np. e-czytnik lub smartfon), dając możliwość dopasowania tekstu do wielkości urządzenia i preferencji użytkownika.
  • MOBI - format zapisu firmy Mobipocket, który można pobrać na dowolne urządzenie elektroniczne (np.e-czytnik Kindle) z zainstalowanym programem (np. MobiPocket Reader) pozwalającym czytać pliki MOBI.
  • Audiobooki w formacie MP3 - format pliku, przeznaczony do odsłuchu nagrań audio.
• Rodzaje zabezpieczeń plików:
  • Watermark - (znak wodny) to zaszyfrowana informacja o użytkowniku, który zakupił produkt. Dzięki temu łatwo jest zidentyfikować użytkownika, który rozpowszechnił produkt w sposób niezgodny z prawem.
  • Brak zabezpieczenia - część oferowanych w naszym sklepie plików nie posiada zabezpieczeń. Zazwyczaj tego typu pliki można pobierać ograniczoną ilość razy, określaną przez dostawcę publikacji elektronicznych. W przypadku zbyt dużej ilości pobrań plików na stronie WWW pojawia się stosowny komunikat.

  Więcej informacji o publikacjach elektronicznych

Przedmowa do pierwszego wydania  IX
	Do studentów   IX
	Do nauczycieli   X
	Pierwsze wydanie   XI
	Uwagi do autora    XII
	Podziękowania   XII
Przedmowa do drugiego wydania  XIV
Przedmowa do trzeciego wydania  XVII
0. Wstęp    1
0.1 Automaty, obliczalność i złożoność  1
	Teoria złożoności    2
	Teoria obliczalności   3
	Teoria automatów   3
0.2 Pojęcia matematyczne i terminologia   3
	Zbiory    3
	Ciągi i krotki   6
	Funkcje i relacje    7
	Grafy   10
	Słowa i języki   13
	Logika Boole’a   14
	Podsumowanie terminów matematycznych  15
0.3 Definicje, twierdzenia i dowody   17
	Znajdowanie dowodów  17
0.4 Typy dowodów   21
	Dowód przez konstrukcję  21
	Dowód nie wprost (przez sprowadzenie do sprzeczności)   21
	Dowód indukcyjny   23
	Dowód   24
Część I. AUTOMATY I JĘZYKI  29
1. Języki regularne   31
1.1 Automaty skończone  31
	Formalna definicja automatu skończonego   34
	Przykłady automatów skończonych  37
	Formalna definicja obliczeń  39
	Projektowanie automatów skończonych    40
	Operacje regularne   43
1.2 Niedeterminizm   47
	Formalna definicja niedeterministycznego automatu skończonego  52
	Równoważność NFA i DFA   54
	Zamknięcie ze względu na operacje regularne  58
1.3 Wyrażenia regularne  62
	Formalna definicja wyrażenia regularnego   63
	Równoważność z automatami skończonymi  65
1.4 Języki nieregularne   75
	Lemat o pompowaniu dla języków regularnych  76
2. Języki bezkontekstowe  101
2.1 Gramatyki bezkontekstowe   102
	Formalna definicja gramatyki bezkontekstowej   104
	Projektowanie gramatyk bezkontekstowych  106
	Niejednoznaczność  107
	Postać normalna Chomsky’ego  108
2.2 Automaty ze stosem  111
	Formalna definicja automatu ze stosem   112
	Przykłady automatów ze stosem  114
	Równoważność z gramatykami bezkontekstowymi  116
2.3 Języki niebędące bezkontekstowymi  124
	Lemat o pompowaniu dla języków bezkontekstowych  125
2.4 Deterministyczne języki bezkontekstowe   130
	Właściwości języków DCFL  133
	Deterministyczne gramatyki bezkontekstowe  136
	Zależności między DPDA a gramatykami DCFG  147
	Parsing i gramatyki LR(k)  153
Część II. TEORIA OBLICZALNOŚCI  167
3. Hipoteza Churcha-Turinga  169
3.1 Maszyny Turinga    169
	Formalna definicja maszyny Turinga   171
	Przykłady maszyn Turinga   174
3.2 Odmiany maszyn Turinga  179
	Wielotaśmowe maszyny Turinga  180
	Niedeterministyczne maszyny Turinga  182
	Enumeratory   184
	Równoważność z innymi modelami  185
3.3 Definicja algorytmu   186
	Problemy Hilberta   187
	Konwencja opisywania maszyn Turinga    189
4. Rozstrzygalność   199
4.1 Języki rozstrzygalne  200
	Problemy rozstrzygalne dotyczące języków regularnych  200
	Problemy rozstrzygalne dotyczące języków bezkontekstowych  204
4.2 Nierozstrzygalność  207
	Metoda diagonalizacji   208
	Język nierozstrzygalny  213
	Język nierozpoznawalny w sensie Turinga  216
5. Redukowalność   223
5.1 Nierozstrzygalne problemy teorii języków  224
	Redukcje przez historie obliczeń   228
5.2 Prosty problem nierozstrzygalny   235
5.3 Redukcja przez odwzorowanie  242
	Funkcje obliczalne   242
	Formalna definicja redukcji przez odwzorowanie  243
6. Zaawansowane zagadnienia teorii obliczalności  255
6.1 Twierdzenie o rekurencji   255
	Samoodniesienie   256
	Posługiwanie się twierdzeniem o rekurencji  259
	Zastosowania   260
6.2 Rozstrzygalność teorii logicznych  262
	Teoria rozstrzygalna  265
	Teoria nierozstrzygalna  267
6.3 Redukowalność w sensie Turinga  270
6.4 Pojęcie informacji   272
	Opisy minimalnej długości   273
	Optymalność definicji  276
	Słowa niekompresowalne i losowość  277
Część III. TEORIA ZŁOŻONOŚCI   285
7. Złożoność czasowa   287
7.1 Mierzenie złożoności  287
	Notacja wielkiego O i małego o   288
	Analiza algorytmów  290
	Zależności między złożonościami modeli   294
7.2 Klasa P   297
	Czas wielomianowy   297
	Przykłady problemów z klasy P  299
7.3 Klasa NP   305
	Przykłady problemów z klasy NP  309
	Zagadnienie P versus NP  311
7.4 NP-zupełność   312
	Redukowalność w czasie wielomianowym   313
	Definicja NP-zupełności  317
	Twierdzenie Cooka-Levina   317
7.5 Dalsze problemy NP-zupełne  324
	Problem pokrycia wierzchołkowego  325
	Problem ścieżki Hamiltona  327
	Problem sumy podzbioru  333
8. Złożoność pamięciowa  347
8.1 Twierdzenie Savitcha  349
8.2 Klasa PSPACE   352
8.3 PSPACE-zupełność  353
	Problem TQBF   354
	Strategie wygrywające w grach  358
	Uogólniona gra w łańcuszek  360
8.4 Klasy L i NL   365
8.5 NL-zupełność   368
	Przeszukiwanie grafów  370
8.6 Klasa NL równa się klasie coNL  372
9. Problemy trudne   381
9.1 Twierdzenia o hierarchii  381
	Zupełność pamięci wykładniczej  390
9.2 Relatywizacja   395
	Ograniczenia stosowalności metody diagonalizacji  396
9.3 Złożoność obwodów  399
10. Zaawansowane zagadnienia teorii złożoności  413
10.1 Algorytmy aproksymacyjne  413
10.2 Algorytmy probabilistyczne  416
	Klasa BPP   416
	Pierwszość   419
	Programy z rozgałęzieniami z jednokrotnym odczytem  424
10.3 Alternacje   429
	Czas i pamięć w obliczeniach alternujących  431
	Wielomianowa hierarchia czasowa  435
10.4 Systemy dowodów interaktywnych  436
	Nieizomorfizm grafów   436
	Definicja modelu   437
	IP = PSPACE   439
10.5 Obliczenia równoległe   449
	Jednolite obwody logiczne   450
	Klasa NC   452
	P-zupełność    454
10.6 Kryptografia    455
	Klucze tajne    456
	Systemy szyfrowania z kluczem publicznym   458
	Funkcje jednokierunkowe  458
	Funkcje z bocznym wejściem   460
Wybrana bibliografia  465
Indeks   469