Fundamentals Of The Theory Of Computation: Principles And Practice
Raymond Greenlaw, H. James Hoover · 1998
From the Publisher: This innovative textbook presents the key foundational concepts that can be covered in a one semester undergraduate course in the theory of computation. It offers the most accessible and motivational course material available for undergraduate computer theory classesand is directed at the typical undergraduate who may have difficulty understanding the relevance of the course to their future careers. The text helps make students more comfortable with techniques required for the deeper study of computer science. To successfully practice computer science, it is necessary to understand its theoretical roots. Simple tools like regular expression matching, complex tools like compilers and fundamental ideas like cryptography all result from a thorough understanding of theory. On the other hand, theory is motivated by practical problems like the need for authentication and secure communication. This text bridges theory and practice. Features: Contains coverage of contemporary topics: languages and problems, machine models, grammars, reductions, resource consumption, syntax vs. semantics, sequential vs. parallel computation, feasible vs. intractable problems Motivates students by clarifying complex theory with many examples, exercises, and detailed proofs Offers an integrated review of discrete math concepts, defining each concept where it is first used Unifies notation for describing machine models Emphasizes computational complexity