- 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
-
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....(14.90 zł najniższa cena z 30 dni)
21.95 zł
39.90 zł(-45%) -
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...(14.90 zł najniższa cena z 30 dni)
21.95 zł
39.90 zł(-45%) -
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 ...(52.92 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
(24.90 zł najniższa cena z 30 dni)27.20 zł
34.00 zł(-20%) -
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...(34.90 zł najniższa cena z 30 dni)
43.20 zł
54.00 zł(-20%) -
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
(28.90 zł najniższa cena z 30 dni)48.00 zł
64.00 zł(-25%) -
Książka „Smartfon również dla seniora” dedykowana jest wszystkim osobom chcącym w pełni poznać i wykorzystać możliwości współczesnego smartfona. Zdarza się, że nowoczesne telefony użytkujemy już od dawna ale bardzo często ograniczamy się tylko do podstawowych czynności j...(19.90 zł najniższa cena z 30 dni)
33.75 zł
45.00 zł(-25%) -
- Prosta nauka podstawowych zadań - Duże demonstracje - Pliki ćwiczeń do budowy umiejętności Szybka nauka programu PowerPoint! Nauka nigdy nie była tak łatwa. Osiągnij produktywność przy pracy z PowerPoint 2016 i znajdź odpowiedzi na wszystkie pytania energiczne ćwiczenia i zrzuty ...
Microsoft PowerPoint 2016 Krok po kroku. Plus Pliki ćwiczeń do pobrania Microsoft PowerPoint 2016 Krok po kroku. Plus Pliki ćwiczeń do pobrania
(52.92 zł najniższa cena z 30 dni)52.92 zł
58.80 zł(-10%)
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
-
Światowy bestseller, który uczy, jak tworzyć bezpieczne systemy informatyczne. Podręcznik obejmuje nie tylko podstawy techniczne, takie jak kryptografia, kontrola dostępu i odporność na manipulacje, ale także sposób ich wykorzystania w prawdziwym życiu. Realne studia przypadków dotyczące bezpie...(93.12 zł najniższa cena z 30 dni)
111.20 zł
139.00 zł(-20%) -
Za każdym razem w psychoterapii pracujemy z konkretną, niepowtarzalną w swoim indywidualizmie osobą metodami pochodzącymi z wiedzy ogólnej. I, co niezwykle doniosłe, praca ta niejednokrotnie okazuje się skuteczna. W jaki sposób jest to możliwe? W pracy psychoterapeutycznej wszystkie drogi prowadz...
Konceptualizacja w terapii poznawczo-behawioralnej Konceptualizacja w terapii poznawczo-behawioralnej
(52.93 zł najniższa cena z 30 dni)63.20 zł
79.00 zł(-20%) -
David Attenborough jest najbardziej znanym popularyzatorem wiedzy przyrodniczej na świecie, twórcą filmów przyrodniczych, który z kamerą objechał świat, pokazał nam całe królestwo zwierząt i przeanalizował każdą większą grupę w kontekście roli, jaką odegrała w długim spektaklu życia, od jego pocz...(39.90 zł najniższa cena z 30 dni)
47.20 zł
59.00 zł(-20%) -
"Gdzie przebiega granica między tym, co nas krzywdzi, a tym, co powoduje wzrost? Skąd mamy wiedzieć, które wydarzenie traumatyczne zbuduje nasz charakter, a które nas wyniszczy? Czy prawdą jest, że to, co nas nie zabije, uczyni nas silniejszymi? Jak możemy zmienić trajektorię, którą podążamy po t...(33.90 zł najniższa cena z 30 dni)
39.20 zł
49.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...(52.93 zł najniższa cena z 30 dni)
63.20 zł
79.00 zł(-20%) -
Nowe wydanie światowego bestsellera literatury popularnonaukowej, część pasjonującej serii: 50 idei, które powinieneś znać Kto wynalazł liczbę zero i dlaczego był to jeden z największych wynalazków w historii matematyki? Czy można zmierzyć nieskończoność? Dlaczego minuta trwa akurat 60 sekun...(39.90 zł najniższa cena z 30 dni)
38.35 zł
59.00 zł(-35%) -
Jak ważne jest bezpieczeństwo systemów, osób i instytucji w dobie trwających wojen, również tych cybernetycznych, nie trzeba nikogo przekonywać. Jest to bardzo ważna kwestia, dlatego istotne jest również przygotowanie się instytucji i społeczeństw na czyhające już od dawna zagrożenia z tym związa...
Bezpieczeństwo osób i systemów IT z wykorzystaniem białego wywiadu Bezpieczeństwo osób i systemów IT z wykorzystaniem białego wywiadu
(71.20 zł najniższa cena z 30 dni)71.20 zł
89.00 zł(-20%) -
Książka Susan Young i Jessiki Bramham to praktyczny przewodnik, który wskazuje, jak za pomocą terapii poznawczo-behawioralnej radzić sobie z objawami ADHD występującymi u młodzieży i osób dorosłych. Program Young i Bramham: dostarcza praktycznych strategii radzenia sobie z codziennymi trudnoś...
Psychoterapia poznawczo-behawioralna ADHD nastolatków i dorosłych Psychoterapia poznawczo-behawioralna ADHD nastolatków i dorosłych
(46.23 zł najniższa cena z 30 dni)55.20 zł
69.00 zł(-20%) -
Pierwsze w polskiej literaturze wszechstronne ujęcie zagadnienia komunikacji politycznej w amerykańskich kampaniach wyborczych! Książka: - przedstawia amerykański system medialny; - ukazuje praktykę oraz ocenę kampanii z perspektywy jej głównych uczestników: konsultantów politycznych, dziennikar...
Komunikacja polityczna w amerykańskich kampaniach wyborczych Komunikacja polityczna w amerykańskich kampaniach wyborczych
(49.58 zł najniższa cena z 30 dni)59.20 zł
74.00 zł(-20%) -
Książka prezentuje niezwykle różnorodne środowisko przedwojennych przemysłowców i biznesmenów w czasach Drugiej Rzeczypospolitej. Przedstawia je na tle ówczesnych uwarunkowań ekonomicznych, politycznych i społecznych. Opisuje sytuację kraju po odzyskaniu niepodległości, a także załamanie gospodar...(52.93 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.