Название: Computability and Complexity
Автор: Hubie Chen
Издательство: The MIT Press
Год: 2023
Страниц: 416
Язык: английский
Формат: epub (true)
Размер: 12.6 MB

A clear, comprehensive, and rigorous introduction to the theory of computation.

What is computable? What leads to efficiency in computation? Computability and Complexity offers a clear, comprehensive, and rigorous introduction to the mathematical study of the capabilities and limitations of computation. Hubie Chen covers the core notions, techniques, methods, and questions of the theory of computation before turning to several advanced topics. Emphasizing intuitive learning and conceptual discussion, this textbook’s accessible approach offers a robust foundation for understanding both the reach and restrictions of algorithms and computers.

Extensive exercises and diagrams enhance streamlined, student-friendly presentation of mathematically rigorous material
Includes thorough treatment of automata theory, computability theory, and complexity theory—including the P versus NP question and the theory of NP-completeness
Suitable for undergraduate and graduate students, researchers, and professionals

Audiences:
This book is targeted to multiple audiences:
First, this book aspires to be useable in a Computer Science curriculum at the upper undergraduate level, and above. In particular, it was designed to be accessible to computer science undergraduates having a basic mathematical maturity—namely, comfort working with mathematical notation, definitions, and proofs.

At the same time, this book aims to serve as a thorough, rigorous initiation into the theory of computation which may be used by students, researchers, and workers in disciplines that draw on or depend upon this theory. This initiation should provide its users with the ability to begin engaging with research literature that employs the theory of computation, and a point of departure for learning more about this theory. This book could serve as a primary text or as a reference for both undergraduate-level and graduate-level courses that cover or contact the theory of computation. For all use cases, the crucial background is the aforementioned basic mathematical maturity.

This book’s presentation assumes familiarity with basic set-theoretic notions (such as those of set, subset, power set, intersection, and union), functions, and propositional logic. On the part of the reader, some acquaintance with graph theory and with computer programming would be helpful, but is not strictly required.




ОТСУТСТВУЕТ ССЫЛКА/ НЕ РАБОЧАЯ ССЫЛКА ЕСТЬ РЕШЕНИЕ, ПИШИМ СЮДА!