Sipser Michael. Introduction to The Theory of Computation, Second Edition

формат djvu
размер 6.57 МБ
добавлен 30 октября 2009 г.

Книга профессора прикладной математики из Массачу?сетского технологи?ческого институ?та. Русского преревода, к сожалению, не существует (или я не нашел).
Очень полезная книжка. В Маи по ней читаются лекции по Сппо.

Michael Sipser

Welcome!
You are about to embark on the study of a fascinating and important subject.
the theory of computation. It comprises the fundamental mathematical proper.
ties of computer hardware, software, and certain applications thereof. In study.
ing this subject we seek to determine what can and cannot be computed, how.
quickly, with how much memory, and on which type of computational model.
The subject has obvious connections with engineering practice, and, as in many.
sciences, it also has purely philosophical aspects.
Part One: Automata and Languages.
Regular Languages.
Context-Free Languages.
Part Two: Computability Theory.
The Church-Turing Thesis.
Decidability.
Reducibility.
Advanced Topics in Computability Theory.
Part Three: Complexity Theory.
Time Complexity.
Space Complexity.
Intractability.
Advanced topics in complexity theory.

Купить и скачать книгу

Похожие разделы

Смотрите также

Atallah M.J., Blanton M. (eds.) Algorithms and Theory of Computation Handbook. General Concepts and Techniques

Справочник

формат pdf
размер 8.46 МБ
добавлен 30 января 2012 г.

Издательство Chapman&Hall/CRC Press, 2010, -990 pp. The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are introduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of al...

Atallah M.J., Blanton M. Algorithms and Theory of Computation Handbook: Special Topics and Techniques

формат pdf
размер 10.74 МБ
добавлен 22 августа 2011 г.

Chapman and Hall/CRC, 2009. - 950 pages. Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems. Along with updating and revising many of the existing chapters, this second edition contains mo...

Bogdanov A., Trevisan L. Average-Case Complexity

формат pdf
размер 737.3 КБ
добавлен 05 октября 2011 г.

Computing Research Repository, 2008, -81 pp. We survey the average-case complexity of problems in NP. We discuss various notions of good-on-average algorithms, and present completeness results due to Impagliazzo and Levin. Such completeness results establish the fact that if a certain specific (but somewhat artificial) NP problem is easy-on-average with respect to the uniform distribution, then all problems in NP are easy-on-average with respect...

Cormen T.H. Introduction to algorithms

формат chm
размер 17.81 МБ
добавлен 12 июня 2009 г.

This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor.Each chapter presents an algorithm, a design technique, an application area, or a related topic. Algorithms are...

Flum J., Grohe M. Parameterized Complexity Theory

формат pdf
размер 3.68 МБ
добавлен 08 февраля 2012 г.

Издательство Springer, 2006, -494 pp. Parameterized complexity theory provides a framework for a refined analysis of hard algorithmic problems. Classical complexity theory analyzes and classifies problems by the amount of a resource, usually time or space, that is required by algorithms solving them. It was a fundamental idea, going back to the work of Hartmanis and Stearns in the early 1960s, to measure the required amount of the resource as a...

Goldreich O. Computational Complexity. A Conceptual Perspective

формат pdf
размер 3.3 МБ
добавлен 31 октября 2011 г.

Издательство Cambridge University Press, 2008, -632 pp. The quest for efficiency is ancient and universal, as time and other resources are always in shortage. Thus, the question of which tasks can be performed efficiently is central to the human experience. A key step toward the systematic study of the aforementioned question is a rigorous definition of the notion of a task and of procedures for solving tasks. These definitions were provided by...

Hopcroft John E., Motwani Rajeev, Ullman Jeffrey D. Introduction to Automata Theory, Languages, and Computation (2nd Edition)

формат djvu
размер 8.64 МБ
добавлен 29 марта 2011 г.

This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications.

Kozen D.C. Theory of Computation

формат pdf
размер 2.75 МБ
добавлен 08 декабря 2011 г.

Издательство Springer, 2006, -405 pp. The course serves a dual purpose: to cover core material in the foundations of computing for graduate students in computer science preparing for their PhD qualifying exams, and to provide an introduction to some more advanced topics in the theory of computational complexity for those intending to pursue further study in the area. The course is thus a mixture of core and advanced material. Most of the course...

Lipton R.J. The P=NP Question and G?del’s Lost Letter

формат pdf
размер 2.34 МБ
добавлен 07 октября 2011 г.

Издательство Springer, 2010, -222 pp. Does P=NP?. In just five symbols Dick Karp –in 1972–captured one of the deepest and most important questions of all time. When he first wrote his famous paper, I think it’s fair to say he did not know the depth and importance of his question. Now over three decades later, we know P=NP is central to our understanding of computation, it is a very hard problem, and its resolution will have potentially tremendou...

Van Leeuwen J. (ed.) Handbook of Theoretical Computer Science. Volume A. Algorithms and Complexity

формат djvu
размер 12.2 МБ
добавлен 11 мая 2011 г.

Издательсто Elsiever/MIT Press, 1990, -1010 pp. Всеобъемлющий справочник о различных типах сложности алгоритмов и вычислений Machine Models and Simulations A Catalog of Complexity Classes Machine-Independent Complexity Theory Kolmogorov Complexity and its Applications Data Structures Computational Geometry Algorithmic Motion Planning in Robotics Average-Case Analysis of Algorithms and Data Structures Graph Algorithms Algorithms in Number Theory...