Introduction to the Theory of Computation, Second Edition.pdf

(21201 KB) Pobierz
INTRODUCTION TO THE
THEORY OF COMPUTATION,
SECOND EDITION
MICHAEL SIPSER
MassachusettsInstitute of Technology
THOMSON
COURSE TECHNOLOGY
Australia * Canada * Mexico * Singapore * Spain * United Kingdom * United States
THOIVISON
COURSE TECHNOLOGY
Introduction to the Theory of Computation,
Second Edition
by Michael Sipser
Senior Product Manager:
Alyssa Pratt
Executive Editor:
Mac Mendelsohn
Associate Production Manager:
Aimee Poirier
Senior Marketing Manager:
Karen Seitz
COPYRIGHT
©
2006 Thomson
Course Technology, a division of
Thomson Learning, Inc. Thomson
LearningTM is a trademark used herein
under license.
Printed in the United States of America
1 2 3 45 67 89 QWT 0908070605
For more information, contact
Thomson Course Technology
25 Thomson Place
Boston, Massachusetts, 02210.
Or find us on the World Wide Web at:
www.course.com
ALL RIGHTS RESERVED. No part of
this work covered by the copyright
hereon may be reproduced or used in
any form or by any means graphic,
electronic, or mechanical, including
photocopying, recording, taping, Web
distribution, or information storage and
retrieval systems without the written
permission of the publisher.
Associate Product Manager:
Mirella Misiaszek
Editorial Assistant:
Jennifer Smith
Senior Manufacturing Coordinator:
Trevor Kallop
Cover Designer:
Steve Deschesne
For permission to use material from this
text or product, submit a request online
at http://www.thomsonrights.com
Any additional questions about
permissions can be submitted by e-mail to
thomsonrights~thomson.com
Disclaimer
Thomson Course Technology reserves
the right to revise this publication and
make changes from time to time in its
content without notice.
ISBN 0-534-95097-3
To Ina, Rachel, and Aaron
CONTENTS
Preface to the First Edition
xi
To the student ....
......................................
xi
To the educator .....................................
xii
The first edition .....
.................................... xiii
Feedback to the author ...............................
xiii
Acknowledgments ......
.................................. xiv
Preface to the Second Edition
0
Introduction
0.1 Automata, Computability, and Complexity . . . . . . . . . . . . .
Complexity theory ...................................
Computability theory .................................
Automata theory .....................................
0.2 Mathematical Notions and Terminology .....................
Sets ...
..............................................
Sequences and tuples .....
..................................
Functions and relations .....
................................
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Strings and languages . . . . . . . . . . . . . . . . . . . . . . .
Boolean logic ..........
.....................
Summary of mathematical terms . . . . . . . . . . . . . . . . .
0.3 Definitions, Theorems, and Proofs .. ........................
Finding proofs . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.4 Types of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Proof by construction ..........................
Proof by contradiction . . . . . . . . . . . . . . . . . . . . . . .
Proof by induction ..............................
Exercises, Problems, and Solutions .......................
..
v
xvii
1
1
2
2
3
3
3
6
7
10
13
14
16
17
17
21
221
21
22
25

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin