Formal models of computation : the ultimate limits of computing
著者
書誌事項
Formal models of computation : the ultimate limits of computing
（AMAST series in computing / managing editor: T. Rus ; advisory board; A. Arnold ... [et al.], v. 7）
World Scientific, c2001
大学図書館所蔵 件 / 全7件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references (p. 523-528) and index
内容説明・目次
内容説明
This book provides new presentations of standard computational models that help avoid pitfalls of the conventional description methods. It also includes novel approaches to some of the topics that students normally find the most challenging. The presentations have evolved in response to student feedback over many years of teaching and have been well received by students.The book covers the topics suggested in the ACM curriculum guidelines for the course on “Theory of Computation”, and in the course on “Foundations of Computing” in the model liberal arts curriculum. These are standard courses for upper level computer science majors and beginning graduate students.The material in this area of computing is intellectually deep, and students invariably find it challenging to master. This book blends the three key ingredients for successful mastery. The first is its focus on the mingling of intuition and rigor that is required to fully understand the area. This is accomplished not only in the discussion and in examples, but also especially in the proofs. Second, a number of practical applications are presented to illustrate the capacity of the theoretical techniques to contribute insights in a variety of areas; such presentations greatly increase the reader's motivation to grasp the theoretical material. The student's active participation is the third and final major element in the learning process, and to this end an extensive collection of problems of widely differing difficulty is incorporated.
目次
- Part 1 The finite state paradigm: regular expressions and acceptors
- properties of regular languages
- transducers and other variations. Part 2 Context-free grammars and automata: basic grammar definitions
- pushdown store automata
- properties of context-free languages. Part 3 General computability models: context-sensitive languages
- Turing machines and computability
- the universal machine and impossible computations.
「Nielsen BookData」 より
