- Wydawnictwo:
- Wydawnictwo Naukowe PWN
- Ocena:
- Bądź pierwszym, który oceni tę książkę
- Stron:
- 500
- Dostępne formaty:
-
ePubMobi
Opis ebooka: Wprowadzenie do teorii obliczeń
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 automatom i językom formalnym. Omówiono w niej niedeterminizm, równoważność automatów deterministycznych i niedeterministycznych, wyrażenia regularne, kryteria nieregularności języków, a także języki bezkontekstowe. Druga część dotyczy teorii obliczalności. Opisano w niej ograniczenia współczesnych komputerów, wyjaśniono pojęcia rozstrzygalności i nierozstrzygalności. Trzecia część jest poświęcona teorii złożoności. Przedstawiono w niej podstawowe klasy złożoności obliczeniowej, klasę problemów NP-zupełnych, a także klasyfikację problemów ze względu na możliwość automatycznego ich rozwiązywania przy ograniczonych zasobach. Trzecia edycja zawiera zupełnie nowy podrozdział poświęcony deterministycznym językom bezkontekstowym. Została też wzbogacona o nowe ćwiczenia, problemy i przykłady. Książka skierowana do studentów informatyki na wszystkich wyższych uczelniach.
Wybrane bestsellery
-
Мова Python сьогодні відома у всьому світі. Вона з...
Head First. Python. Легкий для сприйняття довідник Head First. Python. Легкий для сприйняття довідник
(84.16 zł najniższa cena z 30 dni)84.16 zł
103.90 zł(-19%) -
Ця книжка познайомить вас з особливостями Jav...
Head First. Програмування на JavaScript. Head First. Програмування на JavaScript Head First. Програмування на JavaScript. Head First. Програмування на JavaScript
(84.16 zł najniższa cena z 30 dni)84.16 zł
103.90 zł(-19%) -
Odkryj fascynujący świat sztucznej inteligencji (AI) bez zbędnych komplikacji! Ta książka to idealny przewodnik dla każdego, kto chce zrozumieć, jak AI zmienia nasz świat, od podstawowych pojęć po zaawansowane technologie. Dzięki jasnym wyjaśnieniom i przystępnemu językowi, autor demistyfikuje sk...
AI bez tajemnic. Sztuczna Inteligencja od podstaw po zaawansowane techniki AI bez tajemnic. Sztuczna Inteligencja od podstaw po zaawansowane techniki
-
W erze, gdy aplikacje szpiegujące takie jak Pegasus są niemal niewidzialne, a oszustwa internetowe rosną w siłę, Twoja wiedza stanowi pierwszą linię obrony. Ta książka to Twoja tarcza w walce z cyberzagrożeniami. Pegasus, znany jako jeden z najbardziej zaawansowanych narzędzi szpiego...
Pegasus. Jak chronić się przed szpiegami, scamem, phishingiem, kradzieżą tożsamości i oszustwami online Pegasus. Jak chronić się przed szpiegami, scamem, phishingiem, kradzieżą tożsamości i oszustwami online
-
Zosia, Kuba i Alex dostają trudne zadanie: pani od przyrody prosi ich o przygotowanie raportu na temat wymarłych zwierząt, które żyły kiedyś w najbliższej okolicy. Hmmm, ciężka sprawa! Na szczęście jest internet – pani Monika mówi, że można z niego korzystać podczas przygotowywania raportu....(19.95 zł najniższa cena z 30 dni)
19.95 zł
39.90 zł(-50%) -
Konkretnie – świat wirtualny. Wyszukiwarka pod adresem google.com wystartowała w roku 1997. Osiągnęła spektakularny sukces, ponieważ jej twórcy zaprojektowali algorytm, który pozwolił nie tylko wyszukiwać strony www zawierające poszukiwane przez użytkownika treści, ale także sam je selekcjo...(19.95 zł najniższa cena z 30 dni)
19.95 zł
39.90 zł(-50%) -
Skuteczna nauka programu Microsoft PowerPoint 2013 Przekonaj się, jak łatwo i szybko można tworzyć profesjonalnie wyglądające prezentacje dzięki programowi Microsoft PowerPoint 2013. Korzystając z książek serii Krok po kroku sam określasz tempo nabywania i utrwalania niezbędnych umiejętności, po ...(40.10 zł najniższa cena z 30 dni)
52.92 zł
58.80 zł(-10%) -
Europejski Certyfikat Umiejętności Komputerowych (European Computer Driving Licence ECDL) potwierdza zdobycie umiejętności w zakresie obsługi komputera i programów użytkowych po odbyciu międzynarodowego systemu szkoleń. W Polsce licencji na szkolenia udziela Polskie Towarzystwo Informatyczne (PT...
ECDL. Przeglądanie stron internetowych i komunikacja. Moduł 7 ECDL. Przeglądanie stron internetowych i komunikacja. Moduł 7
(26.18 zł najniższa cena z 30 dni)26.47 zł
34.00 zł(-22%) -
Europejski Certyfikat Umiejętności Komputerowych (European Computer Driving Licence ECDL) potwierdza zdobycie umiejętności w zakresie obsługi komputera i programów użytkowych po odbyciu międzynarodowego systemu szkoleń. W Polsce licencji na szkolenia udziela Polskie Towarzystwo Informatyczne (PT...(41.58 zł najniższa cena z 30 dni)
42.87 zł
54.00 zł(-21%) -
Książka Buduję swoją pierwszą drukarkę 3D skierowana jest dla osób, które chcą poglądowo zapoznać się z technologiami przyrostowymi, a w szczególności technologią FDM (Fused Deposition Modeling), poznać historię technologii przyrostowych na świecie, a także dowiedzieć się jak...
Buduję swoją pierwszą drukarkę 3D Buduję swoją pierwszą drukarkę 3D
Szymon Terczyński, Damian Gąsiorek, Marek Smyczek, Grzegorz Kądzielawski
(41.60 zł najniższa cena z 30 dni)43.17 zł
64.00 zł(-33%)
Ebooka "Wprowadzenie do teorii obliczeń" przeczytasz na:
-
czytnikach Inkbook, Kindle, Pocketbook, Onyx Boox i innych
-
systemach Windows, MacOS i innych
-
systemach Windows, Android, iOS, HarmonyOS
-
na dowolnych urządzeniach i aplikacjach obsługujących formaty: PDF, EPub, Mobi
Masz pytania? Zajrzyj do zakładki Pomoc »
Audiobooka "Wprowadzenie do teorii obliczeń" posłuchasz:
-
w aplikacji Ebookpoint na Android, iOS, HarmonyOs
-
na systemach Windows, MacOS i innych
-
na dowolnych urządzeniach i aplikacjach obsługujących format MP3 (pliki spakowane w ZIP)
Masz pytania? Zajrzyj do zakładki Pomoc »
Kurs Video "Wprowadzenie do teorii obliczeń" zobaczysz:
-
w aplikacjach Ebookpoint i Videopoint na Android, iOS, HarmonyOs
-
na systemach Windows, MacOS i innych z dostępem do najnowszej wersji Twojej przeglądarki internetowej
Szczegóły ebooka
- Tłumaczenie:
- Marek Włodarz
- ISBN Ebooka:
- 978-83-012-1099-1, 9788301210991
- Data wydania ebooka:
- 2020-03-19 Data wydania ebooka często jest dniem wprowadzenia tytułu do sprzedaży i może nie być równoznaczna z datą wydania książki papierowej. Dodatkowe informacje możesz znaleźć w darmowym fragmencie. Jeśli masz wątpliwości skontaktuj się z nami sklep@ebookpoint.pl.
- Numer z katalogu:
- 110534
- Rozmiar pliku ePub:
- 3.3MB
- Rozmiar pliku Mobi:
- 9.1MB
Spis treści ebooka
- Okładka
- Strona tytułowa
- Strona redakcyjna
- Spis treści
- Przedmowa do pierwszego wydania
- Do studentów
- Do nauczycieli
- Pierwsze wydanie
- Uwagi do autora
- Podziękowania
- Przedmowa do drugiego wydania
- Przedmowa do trzeciego wydania
- 0. Wstęp
- 0.1 Automaty, obliczalność i złożoność
- Teoria złożoności
- Teoria obliczalności
- Teoria automatów
- 0.2 Pojęcia matematyczne i terminologia
- Zbiory
- Ciągi i krotki
- Funkcje i relacje
- Grafy
- Słowa i języki
- Logika Boolea
- Podsumowanie terminów matematycznych
- 0.3 Definicje, twierdzenia i dowody
- Znajdowanie dowodów
- 0.4 Typy dowodów
- Dowód przez konstrukcję
- Dowód nie wprost (przez sprowadzenie do sprzeczności)
- Dowód indukcyjny
- Dowód
- CZĘŚĆ I. AUTOMATY I JĘZYKI
- 1. Języki regularne
- 1.1 Automaty skończone
- Formalna definicja automatu skończonego
- Przykłady automatów skończonych
- Formalna definicja obliczeń
- Projektowanie automatów skończonych
- Operacje regularne
- 1.2 Niedeterminizm
- Formalna definicja niedeterministycznego automatu skończonego
- Równoważność NFA i DFA
- Zamknięcie ze względu na operacje regularne
- 1.3 Wyrażenia regularne
- Formalna definicja wyrażenia regularnego
- Równoważność z automatami skończonymi
- 1.4 Języki nieregularne
- Lemat o pompowaniu dla języków regularnych
- 1.1 Automaty skończone
- 2. Języki bezkontekstowe
- 2.1 Gramatyki bezkontekstowe
- Formalna definicja gramatyki bezkontekstowej
- Przykłady gramatyk bezkontekstowych
- Projektowanie gramatyk bezkontekstowych
- Niejednoznaczność
- Postać normalna Chomskyego
- 2.2 Automaty ze stosem
- Formalna definicja automatu ze stosem
- Przykłady automatów ze stosem
- Równoważność z gramatykami bezkontekstowymi
- 2.3 Języki niebędące bezkontekstowymi
- Lemat o pompowaniu dla języków bezkontekstowych
- 2.4 Deterministyczne języki bezkontekstowe
- Właściwości języków DCFL
- Deterministyczne gramatyki bezkontekstowe
- Zależności między DPDA a gramatykami DCFG
- Parsing i gramatyki LR(k)
- 2.1 Gramatyki bezkontekstowe
- 1. Języki regularne
- CZĘŚĆ II .TEORIA OBLIZALNOŚCI
- 3. Hipoteza Churcha-Turinga
- 3.1 Maszyny Turinga
- Formalna definicja maszyny Turinga
- Przykłady maszyn Turinga
- 3.2 Odmiany maszyn Turinga
- Wielotaśmowe maszyny Turinga
- Niedeterministyczne maszyny Turinga
- Enumeratory
- Równoważność z innymi modelami
- 3.3 Definicja algorytmu
- Problemy Hilberta
- Konwencja opisywania maszyn Turinga
- 3.1 Maszyny Turinga
- 4. Rozstrzygalność
- 4.1 Języki rozstrzygalne
- Problemy rozstrzygalne dotyczące języków regularnych
- Problemy rozstrzygalne dotyczące języków bezkontekstowych
- 4.2 Nierozstrzygalność
- Metoda diagonalizacji
- Język nierozstrzygalny
- Język nierozpoznawalny w sensie Turinga
- 4.1 Języki rozstrzygalne
- 5. Redukowalność
- 5.1 Nierozstrzygalne problemy teorii języków
- Redukcje przez historie obliczeń
- 5.2 Prosty problem nierozstrzygalny
- 5.3 Redukcja przez odwzorowanie
- Funkcje obliczalne
- Formalna definicja redukcji przez odwzorowanie
- 5.1 Nierozstrzygalne problemy teorii języków
- 6. Zaawansowane zagadnienia teorii obliczalności
- 6.1 Twierdzenie o rekurencji
- Samoodniesienie
- Posługiwanie się twierdzeniem o rekurencji
- Zastosowania
- 6.2 Rozstrzygalność teorii logicznych
- Teoria rozstrzygalna
- Teoria nierozstrzygalna
- 6.3 Redukowalność w sensie Turinga
- 6.4 Pojęcie informacji
- Opisy minimalnej długości
- Optymalność definicji
- Słowa niekompresowalne i losowość
- 6.1 Twierdzenie o rekurencji
- 3. Hipoteza Churcha-Turinga
- CZĘŚĆ III.TEORIA ZŁOŻONOŚCI
- 7. Złożoność czasowa
- 7.1 Mierzenie złożoności
- Notacja wielkiego O i małego o
- Analiza algorytmów
- Zależności między złożonościami modeli
- 7.2 Klasa P
- Czas wielomianowy
- Przykłady problemów z klasy P
- 7.3 Klasa NP
- Przykłady problemów z klasy NP
- Zagadnienie P versus NP
- 7.4 NP-zupełność
- Redukowalność w czasie wielomianowym
- Definicja NP-zupełności
- Twierdzenie Cooka-Levina
- 7.5 Dalsze problemy NP-zupełne
- Problem pokrycia wierzchołkowego
- Problem ścieżki Hamiltona
- Problem sumy podzbioru
- 7.1 Mierzenie złożoności
- 8. Złożoność pamięciowa
- 8.1 Twierdzenie Savitcha
- 8.2 Klasa PSPACE
- 8.3 PSPACE-zupełność
- Problem TQBF
- Strategie wygrywające w grach
- Uogólniona gra w łańcuszek
- 8.4 Klasy L i NL
- 8.5 NL-zupełność
- Przeszukiwanie grafów
- 8.6 Klasa NL równa się klasie coNL
- 9. Problemy trudne
- 9.1 Twierdzenia o hierarchii
- Zupełność pamięci wykładniczej
- 9.2 Relatywizacja
- Ograniczenia stosowalności metody diagonalizacji
- 9.3 Złożoność obwodów
- 9.1 Twierdzenia o hierarchii
- 10. Zaawansowane zagadnienia teorii złożoności
- 10.1 Algorytmy aproksymacyjne
- 10.2 Algorytmy probabilistyczne
- Klasa BPP
- Pierwszość
- Programy z rozgałęzieniami z jednokrotnym odczytem
- 10.3 Alternacje
- Czas i pamięć w obliczeniach alternujących
- Wielomianowa hierarchia czasowa
- 10.4 Systemy dowodów interaktywnych
- Nieizomorfizm grafów
- Definicja modelu
- IP = PSPACE
- 10.5 Obliczenia równoległe
- Jednolite obwody logiczne
- Klasa NC
- P-zupełność
- 10.6 Kryptografia
- Klucze tajne
- Systemy szyfrowania z kluczem publicznym
- Funkcje jednokierunkowe
- Funkcje z bocznym wejściem
- Wybrana bibliografia
- Przypisy
- 7. Złożoność czasowa
Wydawnictwo Naukowe PWN - inne książki
-
OKIEM FILOZOFA KOMUNIKACJA CYFROWA Technologie cyfrowe spowodowały znaczące zmiany w zakresie komunikacji. Stworzyły nowe możliwości, ale jednocześnie stały się źródłem wielu istotnych problemów. Z jednej strony nowe technologie umożliwiają nam komunikację z ludźmi na całym świecie, pozwalają do...(35.10 zł najniższa cena z 30 dni)
41.58 zł
54.00 zł(-23%) -
Odporność psychiczna to zdolność do przetrwania i powrotu do równowagi po doświadczeniu przeciwności losu. Wszyscy w swoim życiu stajemy przed wyzwaniami. Większość z nas w pewnym momencie doświadczy poważnej traumy, jak nagła śmierć bliskiej osoby, wyniszczająca choroba lub klęska żywiołowa. Tym...
Odporność psychiczna Odporność psychiczna
Dennis S. Charney, Stephen M. Southwick, Jonathan M. Depierro
(38.35 zł najniższa cena z 30 dni)41.30 zł
59.00 zł(-30%) -
Wszyscy chcemy prowadzić rozmowy, które coś znaczą. Chcemy, żeby nasze rozmowy pogłębiały bliskość i prowadziły do rozwiązywania problemów. Chcemy czuć się naprawdę zrozumiani i rozumieć innych. Chcemy wreszcie, by nasi rozmówcy nie traktowali nas jednowymiarowo i dostrzegali w nas więcej niż tyl...
Siła komunikacji. Odkryj sekret rozmów, które łączą Siła komunikacji. Odkryj sekret rozmów, które łączą
(38.35 zł najniższa cena z 30 dni)41.30 zł
59.00 zł(-30%) -
Patrz, co przez ciebie zrobiłem! Dlaczego nie? Tak, ale Ja tylko próbuję ci pomóc! Będziecie jeszcze dumni, że mnie znacie! Książka Erica Bernea ukazała się po raz pierwszy sześćdziesiąt lat temu. Mimo upływu czasu jej popularność w Polsce i na świecie nie zmalała. Tysiące Czytelników sięgają p...
W co grają ludzie. Psychologia stosunków międzyludzkich W co grają ludzie. Psychologia stosunków międzyludzkich
(38.35 zł najniższa cena z 30 dni)41.30 zł
59.00 zł(-30%) -
Czy jesteśmy odpowiedzialni za wszystko, co nas spotyka? Dlaczego tak bardzo chcemy uniknąć tego, co nieuniknione? Czy naprawdę powinniśmy się nieustannie rozwijać i dążyć do wykorzystania naszego potencjału? I czy każdą traumę, porażkę w relacji czy niełatwe dzieciństwo musimy przepracować w ...(31.85 zł najniższa cena z 30 dni)
39.20 zł
49.00 zł(-20%) -
Światowy bestseller Stuarta Ritchiego! Książka, która ujawnia niepokojące i szokujące sygnały świadczące o kryzysie, jaki przechodzi współczesna nauka. Nauka to sposób, w jaki rozumiemy świat. Jednak niewłaściwa interpretacja i koloryzowane statystyki sprawiły, że ogromna liczba badań naukowych s...(44.85 zł najniższa cena z 30 dni)
55.20 zł
69.00 zł(-20%) -
Paradoks szczęścia polega na tym, że najtrudniej je osiągnąć, kiedy go szukamy. Pojawia się jednak nieoczekiwanie, gdy robimy rzeczy, które mają sens. Profesor Bruce Hood przyjrzał się temu problemowi z perspektywy nauki i doszedł do wniosków, które przeczą treści większości popularnych poradnik...(38.35 zł najniższa cena z 30 dni)
46.97 zł
59.00 zł(-20%) -
Kulisy Peerelu Mimo że od upadku PRL minęło już kilkadziesiąt lat, okres rządów komunistycznych w Polsce wciąż wzbudza kontrowersje i jest przedmiotem sporów oraz dyskusji nie tylko wśród historyków, lecz także polityków i dziennikarzy. Antoni Dudek i Zdzisław Zblewski, historycy, którzy od la...(64.35 zł najniższa cena z 30 dni)
79.20 zł
99.00 zł(-20%) -
Jak skutecznie zaplanować i zrealizować każdy projekt na czas i zgodnie z budżetem? Bent Flyvbjerg, nazwany wiodącym światowym ekspertem od megaprojektów, we współpracy z autorem bestsellerów, Danem Gardnerem, dzieli się sekretami skutecznego planowania i realizacji każdego projektu na dowolną sk...(60.83 zł najniższa cena z 30 dni)
63.20 zł
79.00 zł(-20%)
Dzieki opcji "Druk na żądanie" do sprzedaży wracają tytuły Grupy Helion, które cieszyły sie dużym zainteresowaniem, a których nakład został wyprzedany.
Dla naszych Czytelników wydrukowaliśmy dodatkową pulę egzemplarzy w technice druku cyfrowego.
Co powinieneś wiedzieć o usłudze "Druk na żądanie":
- usługa obejmuje tylko widoczną poniżej listę tytułów, którą na bieżąco aktualizujemy;
- cena książki może być wyższa od początkowej ceny detalicznej, co jest spowodowane kosztami druku cyfrowego (wyższymi niż koszty tradycyjnego druku offsetowego). Obowiązująca cena jest zawsze podawana na stronie WWW książki;
- zawartość książki wraz z dodatkami (płyta CD, DVD) odpowiada jej pierwotnemu wydaniu i jest w pełni komplementarna;
- usługa nie obejmuje książek w kolorze.
Masz pytanie o konkretny tytuł? Napisz do nas: sklep[at]helion.pl.
Książka, którą chcesz zamówić pochodzi z końcówki nakładu. Oznacza to, że mogą się pojawić drobne defekty (otarcia, rysy, zagięcia).
Co powinieneś wiedzieć o usłudze "Końcówka nakładu":
- usługa obejmuje tylko książki oznaczone tagiem "Końcówka nakładu";
- wady o których mowa powyżej nie podlegają reklamacji;
Masz pytanie o konkretny tytuł? Napisz do nas: sklep[at]helion.pl.
Książka drukowana
Oceny i opinie klientów: Wprowadzenie do teorii obliczeń Michael Sipser (0) Weryfikacja opinii następuję na podstawie historii zamówień na koncie Użytkownika umieszczającego opinię. Użytkownik mógł otrzymać punkty za opublikowanie opinii uprawniające do uzyskania rabatu w ramach Programu Punktowego.