Wprowadzenie do teorii obliczeń

Michael Sipser

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

978-83-01-21099-1

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2020

Liczba stron:

500

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Sipser, Michael. Wprowadzenie do teorii obliczeń. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2020, 500 s. ISBN 978-83-01-21099-1

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Sipser, M.

T1 Wprowadzenie do teorii obliczeń

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2020

SN 978-83-01-21099-1

Bibliografia BibTex:

@Book{ 216984, author = "Sipser, Michael", editor = "", title = "Wprowadzenie do teorii obliczeń", publisher = "Wydawnictwo Naukowe PWN", year = "2020", address = "Warszawa", isbn = "978-83-01-21099-1" }

Bibliografia endNote:

TY - BOOK

AU - Sipser, Michael

ED -

TI - Wprowadzenie do teorii obliczeń

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2020

SN - 978-83-01-21099-1

ER -

Netografia (standard APA):

Sipser, Michael. Wprowadzenie do teorii obliczeń [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2020 [dostęp: 03 05 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/wprowadzenie-do-teorii-obliczen-michael-sipser-216984.

złożoność obliczeniowa, teoria obliczeń, teoria obliczalności, automaty skończone, teoria złożoności, automaty i języki, języki regularne, języki nieregularne, języki bezkontekstowe, gramatyki bezkontekstowe, hipoteza Churcha-Turinga, maszyna Turinga, języki rozstrzygalne, teoria języków

Wprowadzenie do teorii obliczeń to najpopularniejszy podręcznik do teorii obliczeń. Dotyczy podstaw informatyki, a w szczególności możliwości obliczeniowych współczesnych komputerów. Książka składa się z trzech części. Pierwsza jest poświęcona au...

Więcej

ISBN/ISSN:

978-83-01-21099-1

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2020

Liczba stron:

500

XML:ISBN/ISSN:

ONIX MARC21

Przedmowa do pierwszego wydania 10
Do studentów10
Do nauczycieli11
Pierwsze wydanie12
Podziękowania13
Uwagi do autora13
Przedmowa do drugiego wydania 15
Przedmowa do trzeciego wydania 18
0.1 Automaty, obliczalność i złożoność20
0. Wstęp 20
Teoria złożoności21
0.2 Pojęcia matematyczne i terminologia22
Teoria automatów22
Teoria obliczalności22
Zbiory22
Ciągi i krotki25
Funkcje i relacje26
Grafy29
Słowa i języki32
Logika Boole’a33
Podsumowanie terminów matematycznych34
0.3 Definicje, twierdzenia i dowody36
Znajdowanie dowodów36
0.4 Typy dowodów40
Dowód nie wprost (przez sprowadzenie do sprzeczności)40
Dowód przez konstrukcję40
Dowód indukcyjny42
Dowód43
Część I. AUTOMATY I JĘZYKI48
1.1 Automaty skończone50
1. Języki regularne 50
Formalna definicja automatu skończonego53
Przykłady automatów skończonych56
Formalna definicja obliczeń58
Projektowanie automatów skończonych59
Operacje regularne62
1.2 Niedeterminizm66
Formalna definicja niedeterministycznego automatu skończonego71
Równoważność NFA i DFA73
Zamknięcie ze względu na operacje regularne77
1.3 Wyrażenia regularne81
Formalna definicja wyrażenia regularnego82
Równoważność z automatami skończonymi84
1.4 Języki nieregularne94
Lemat o pompowaniu dla języków regularnych95
2. Języki bezkontekstowe 120
2.1 Gramatyki bezkontekstowe121
Formalna definicja gramatyki bezkontekstowej123
Projektowanie gramatyk bezkontekstowych125
Niejednoznaczność126
Postać normalna Chomsky’ego127
2.2 Automaty ze stosem130
Formalna definicja automatu ze stosem131
Przykłady automatów ze stosem133
Równoważność z gramatykami bezkontekstowymi135
2.3 Języki niebędące bezkontekstowymi143
Lemat o pompowaniu dla języków bezkontekstowych144
2.4 Deterministyczne języki bezkontekstowe149
Właściwości języków DCFL152
Deterministyczne gramatyki bezkontekstowe155
Zależności między DPDA a gramatykami DCFG166
Parsing i gramatyki LR(k)172
Część II. TEORIA OBLICZALNOŚCI 186
3.1 Maszyny Turinga188
3. Hipoteza Churcha-Turinga 188
Formalna definicja maszyny Turinga190
Przykłady maszyn Turinga193
3.2 Odmiany maszyn Turinga198
Wielotaśmowe maszyny Turinga199
Niedeterministyczne maszyny Turinga201
Enumeratory203
Równoważność z innymi modelami204
3.3 Definicja algorytmu205
Problemy Hilberta206
Konwencja opisywania maszyn Turinga208
4. Rozstrzygalność 218
4.1 Języki rozstrzygalne219
Problemy rozstrzygalne dotyczące języków regularnych219
Problemy rozstrzygalne dotyczące języków bezkontekstowych223
4.2 Nierozstrzygalność226
Metoda diagonalizacji227
Język nierozstrzygalny232
Język nierozpoznawalny w sensie Turinga235
5. Redukowalność 242
5.1 Nierozstrzygalne problemy teorii języków243
Redukcje przez historie obliczeń247
5.2 Prosty problem nierozstrzygalny254
5.3 Redukcja przez odwzorowanie261
Funkcje obliczalne261
Formalna definicja redukcji przez odwzorowanie262
6.1 Twierdzenie o rekurencji274
6. Zaawansowane zagadnienia teorii obliczalności 274
Samoodniesienie275
Posługiwanie się twierdzeniem o rekurencji278
Zastosowania279
6.2 Rozstrzygalność teorii logicznych281
Teoria rozstrzygalna284
Teoria nierozstrzygalna286
6.3 Redukowalność w sensie Turinga289
6.4 Pojęcie informacji291
Opisy minimalnej długości292
Optymalność definicji295
Słowa niekompresowalne i losowość296
Część III. TEORIA ZŁOŻONOŚCI 304
7.1 Mierzenie złożoności306
7. Złożoność czasowa 306
Notacja wielkiego O i małego o307
Analiza algorytmów309
Zależności między złożonościami modeli313
7.2 Klasa P316
Czas wielomianowy316
Przykłady problemów z klasy P318
7.3 Klasa NP324
Przykłady problemów z klasy NP328
Zagadnienie P versus NP330
7.4 NP-zupełność331
Redukowalność w czasie wielomianowym332
Definicja NP-zupełności336
Twierdzenie Cooka-Levina336
7.5 Dalsze problemy NP-zupełne343
Problem pokrycia wierzchołkowego344
Problem ścieżki Hamiltona346
Problem sumy podzbioru352
8. Złożoność pamięciowa 366
8.1 Twierdzenie Savitcha368
8.2 Klasa PSPACE371
8.3 PSPACE-zupełność372
Problem TQBF373
Strategie wygrywające w grach377
Uogólniona gra w łańcuszek379
8.4 Klasy L i NL384
8.5 NL-zupełność387
Przeszukiwanie grafów389
8.6 Klasa NL równa się klasie coNL391
9.1 Twierdzenia o hierarchii400
9. Problemy trudne 400
Zupełność pamięci wykładniczej409
9.2 Relatywizacja414
Ograniczenia stosowalności metody diagonalizacji415
9.3 Złożoność obwodów418
10.1 Algorytmy aproksymacyjne432
10. Zaawansowane zagadnienia teorii złożoności 432
10.2 Algorytmy probabilistyczne435
Klasa BPP435
Pierwszość438
Programy z rozgałęzieniami z jednokrotnym odczytem443
10.3 Alternacje448
Czas i pamięć w obliczeniach alternujących450
Wielomianowa hierarchia czasowa454
10.4 Systemy dowodów interaktywnych455
Nieizomorfizm grafów455
Definicja modelu456
IP = PSPACE458
10.5 Obliczenia równoległe468
Jednolite obwody logiczne469
Klasa NC471
P-zupełność473
10.6 Kryptografia474
Klucze tajne475
Funkcje jednokierunkowe477
Systemy szyfrowania z kluczem publicznym477
Funkcje z bocznym wejściem479
Wybrana bibliografia484
Indeks488

MICHAELSIPSER

WPROWADZENIE

DOTEORII

OBLICZEŃ

Brak wyników

Wprowadzenie do teorii obliczeń

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra