Introduction to the Theory of Computation
Námskeið
- TÖL301G Formleg mál og reiknanleiki
- T-519-STOR Stöðuvélar og Reiknanleiki / Theory of Computation
Ensk lýsing:
Gain a clear understanding of even the most complex, highly theoretical computational theory topics in the approachable presentation found only in the market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E, International Edition. The number one choice for today’s computational theory course, this revision continues the book’s well-known, approachable style with timely revisions, additional practice, and more memorable examples in key areas.
A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR grammars. You gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E, International Edition’s comprehensive coverage makes this a valuable reference for your continued studies in theoretical computing.
Lýsing:
Gain a clear understanding of even the most complex, highly theoretical computational theory topics in the approachable presentation found only in the market-leading INTRODUCTION TO THE THEORY OF COMPUTATION, 3E. The number one choice for today's computational theory course, this revision continues the book's well-know, approachable style with timely revisions, additional practice, and more memorable examples in key areas.
A new first-of-its-kind theoretical treatment of deterministic context-free languages is ideal for a better understanding of parsing and LR(k) grammars. You gain a solid understanding of the fundamental mathematical properties of computer hardware, software, and applications with a blend of practical and philosophical coverage and mathematical treatments, including advanced theorems and proofs. INTRODUCTION TO THE THEORY OF COMPUTATION, 3E's comprehensive coverage makes this a valuable reference for your continued studies in theoretical computing.
Annað
- Höfundur: Michael Sipser
- Útgáfa:3
- Útgáfudagur: 2021-01-29
- Hægt að prenta út 2 bls.
- Hægt að afrita 2 bls.
- Format:Page Fidelity
- ISBN 13: 9781285401065
- Print ISBN: 9780357670583
- ISBN 10: 1285401069
Efnisyfirlit
- Title
- Statement
- Copyright
- Dedication
- Contents
- Preface to the First Edition
- Preface to the Second Edition
- Preface to the Third Edition
- Ch 0: Introduction
- 0.1 Automata, Computability, and Complexity
- 0.2 Mathematical Notions and Terminology
- 0.3 Definitions, Theorems, and Proofs
- 0.4 Types of Proof
- Exercises
- Problems
- Selected Solutions
- Part 1: Automata and Languages
- Ch 1: Regular Languages
- Introduction
- 1.1 Finite Automata
- 1.2 Nondeterminism
- 1.3 Regular Expressions
- 1.4 Nonregular Languages
- Exercises
- Problems
- Selected Solutions
- Ch 2: Context-Free Languages
- Introduction
- 2.1 Context-Free Grammars
- 2.2 Pushdown Automata
- 2.3 Non-Context-Free Languages
- 2.4 Deterministic Context-Free Languages
- Exercises
- Problems
- Selected Solutions
- Ch 1: Regular Languages
- Ch 3: The Church–Turing Thesis
- Introduction
- 3.1 Turing Machines
- 3.2 Variants of Turing Machines
- 3.3 The Definition of Algorithm
- Exercises
- Problems
- Selected Solutions
- Ch 4: Decidability
- Introduction
- 4.1 Decidable Languages
- 4.2 Undecidability
- Exercises
- Problems
- Selected Solutions
- Ch 5: Reducibility
- Introduction
- 5.1 Undecidable Problems From Language Theory
- 5.2 A Simple Undecidable Problem
- 5.3 Mapping Reducibility
- Exercises
- Problems
- Selected Solutions
- Ch 6: Advanced Topics in Computability Theory
- Introduction
- 6.1 The Recursion Theorem
- 6.2 Decidability of logical theories
- 6.3 Turing Reducibility
- 6.4 A Definition of Information
- Exercises
- Problems
- Selected Solutions
- Ch 7: Time Complexity
- Introduction
- 7.1 Measuring Complexity
- 7.2 The Class P
- 7.3 The Class NP
- 7.4 NP-completeness
- 7.5 Additional NP-complete Problems
- Exercises
- Problems
- Selected Solutions
- Ch 8: Space Complexity
- Introduction
- 8.1 Savitch’s Theorem
- 8.2 The Class PSPACE
- 8.3 PSPACE-completeness
- 8.4 The Classes L and NL
- 8.5 NL-completeness
- 8.6 NL equals coNL
- Exercises
- Problems
- Selected Solutions
- Ch 9: Intractability
- Introduction
- 9.1 Hierarchy Theorems
- 9.2 Relativization
- 9.3 Circuit Complexity
- Exercises
- Problems
- Selected Solutions
- Ch 10: Advanced Topics in Complexity Theory
- Introduction
- 10.1 Approximation Algorithms
- 10.2 Probabilistic Algorithms
- 10.3 Alternation
- 10.4 Interactive Proof Systems
- 10.5 Parallel Computation
- 10.6 Cryptography
- Exercises
- Problems
- Selected Solutions
UM RAFBÆKUR Á HEIMKAUP.IS
Bókahillan þín er þitt svæði og þar eru bækurnar þínar geymdar. Þú kemst í bókahilluna þína hvar og hvenær sem er í tölvu eða snjalltæki. Einfalt og þægilegt!Rafbók til eignar
Rafbók til eignar þarf að hlaða niður á þau tæki sem þú vilt nota innan eins árs frá því bókin er keypt.
Þú kemst í bækurnar hvar sem er
Þú getur nálgast allar raf(skóla)bækurnar þínar á einu augabragði, hvar og hvenær sem er í bókahillunni þinni. Engin taska, enginn kyndill og ekkert vesen (hvað þá yfirvigt).
Auðvelt að fletta og leita
Þú getur flakkað milli síðna og kafla eins og þér hentar best og farið beint í ákveðna kafla úr efnisyfirlitinu. Í leitinni finnur þú orð, kafla eða síður í einum smelli.
Glósur og yfirstrikanir
Þú getur auðkennt textabrot með mismunandi litum og skrifað glósur að vild í rafbókina. Þú getur jafnvel séð glósur og yfirstrikanir hjá bekkjarsystkinum og kennara ef þeir leyfa það. Allt á einum stað.
Hvað viltu sjá? / Þú ræður hvernig síðan lítur út
Þú lagar síðuna að þínum þörfum. Stækkaðu eða minnkaðu myndir og texta með multi-level zoom til að sjá síðuna eins og þér hentar best í þínu námi.
Fleiri góðir kostir
- Þú getur prentað síður úr bókinni (innan þeirra marka sem útgefandinn setur)
- Möguleiki á tengingu við annað stafrænt og gagnvirkt efni, svo sem myndbönd eða spurningar úr efninu
- Auðvelt að afrita og líma efni/texta fyrir t.d. heimaverkefni eða ritgerðir
- Styður tækni sem hjálpar nemendum með sjón- eða heyrnarskerðingu
- Gerð : 208
- Höfundur : 18170
- Útgáfuár : 2021
- Leyfi : 380
