Sipser M. — Introduction to the theory of computation :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Sipser M. — Introduction to the theory of computation

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Introduction to the theory of computation

Автор: Sipser M.

Аннотация:

This highly anticipated revision of Michael Sipser's popular text builds upon the strengths of the previous edition. It tells the fascinating story of the theory of computation-a subject with beautiful results and exciting unsolved questions at the crossroads of mathematics and computer science. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative II proof idea" sections reveal the intuition underpinning the formal proofs of theorems by explaining profound concepts in plain English.
The new edition incorporates many improvements students and professors have suggested over the years and offers completely updated, classroom-tested problem sets with sample solutions at the end of each chapter.

Язык:

Рубрика: Computer science/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: 2nd edition

Год издания: 2005

Количество страниц: 431

Добавлена в каталог: 01.04.2006

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Polynomial time, hierarchy      386
Polynomial time, verifier      265
Polynomial verifiability      265
Polynomial, versus exponential      257
Polynomially equivalent models      257
Pomerance, Carl      415 418
Popping a symbol      110
Post correspondence problem (PCP)      199—205
Post correspondence problem (PCP), modified      200
Power set      6 53
PRAM      400
Pratt, Vaughan R.      418
Prefix notation      8
Prefix of a string      89
Prefix-free language      184
Prenex normal form      225 310
Prime number      265 295 371
Private-key cryptosystem      407
Probabilistic algorithm      368—380
Probabilistic function      408
Probabilistic Turing machine      368
Processor complexity      400
Production      100
proof      17
Proof, by construction      21
Proof, by contradiction      21—22
Proof, by induction      22—25
Proof, finding      17—20
Proof, necessity for      77
Proper subset      4 328
Prover      389
Pseudoprime      372
PSPACE      308
PSPACE-complete problem, FORMULA-GAME      314
PSPACE-complete problem, GG      317
PSPACE-complete problem, TQBF      311
PSPACE-completeness      309—320
PSPACE-completeness, defined      309
Public-key cryptosystem      407
Pumping lemma, for context-free languages      123—128
Pumping lemma, for regular languages      77—82
Pumping length      77 91 123
Pushdown automaton      109—122
Pushdown automaton, context-free grammars      115—122
Pushdown automaton, defined      111
Pushdown automaton, examples      112—114
Pushdown automaton, schematic of      110
Pushing a symbol      110
Putnam, Hilary      155
Puzzle      297 330
Quantified boolean formula      311
Quantifier      310
Quantifier, in a logical sentence      225
Query node in a branching program      376
Rabin, Michael O.      418
Rackoff, Charles      417
Ramsey’s theorem      2 7
Range of a function      7
Read-once branching program      377
Real number      176
Recognizes a language, meaning of      36 40
Recursion theorem      217—224
Recursion theorem, fixed-point version      223
Recursion theorem, terminology for      221
Recursive language      see “Decidable language”
Recursively enumerable      see “Turing-recognizable”
Recursively enumerable language      142
Reducibility      187—211
Reducibility, mapping      206—211
Reducibility, polynomial time      272
Reducibility, via computation histories      192—205
Reduction      187 207
Reduction, mapping      207
Reflexive relation      9
Regular expression      63—76
Regular expression, defined      64
Regular expression, equivalence to finite automaton      66—76
Regular expression, examples of      65
Regular language      31—82
Regular language, closure under concatenation      47 60
Regular language, closure under intersection      46
Regular language, closure under star      62
Regular language, closure under union      45 59
Regular language, decidability      166—170
Regular language, defined      40
Regular operation      44
Reingold, Omer      418
Rejecting computation history      193
Rejecting configuration      141
Relation      8 225
Relation, binary      8
Relatively prime      260
Relativization      348—351
RELPRIME      261
Reverse of a string      14
Rice’s theorem      191 213 215 242 244
RinooyKan, A.H.G.      417
Rivest, Ronald L.      416 418
Robinson, Julia      155
Roche, Emmanuel      418
Root, in a tree      11
Root, of a polynomial      155
Rule in a context-free grammar      100 102
Rumely, Robert S.      415
Ruzzo, Walter L.      417
SAT      276 308
Satisfiability problem      271
Satisfiable formula      271
Savitch’s theorem      305—307
Saxena, Nitin      415
Schabes, Yves      418
Schaefer, Thomas J.      418
Scope      310
Scope, of a quantifier      225
Secret key      405
Sedgewick, Robert      418
Self-reference      218
Sentence      311
SEQUENCE      6
Sequential computer      399
Set      3
Set, countable      175
Set, uncountable      176
Sethi, Ravi      415
Shallit, Jeffrey      415
Shamir, Adi      418
Shen, Alexander      418
Shmoys, David B.      417
Shor, Peter W.      418
Shuffle operation      89 131
Simple path      11
Sipser, Michael      418 419
Size complexity      400

Small-o notation      250
Space complexity      303—333
Space complexity class      304
Space complexity of nondeterministic Turing machine      304
Space constructible function      336
Space hierarchy theorem      337
SPACE(f(n))      304
Spencer, Joel H.      415
STACK      109
Star operation      44 62—63 295
Start configuration      141
Start state      34
Start variable, in a context-free grammar      100 102
State diagram, finite automaton      34
State diagram, pushdown automaton      112
State diagram, Turing machine      144
Stearns, Richard E.      417
Steiglitz, Kenneth      418
Stinson, Douglas R.      419
String      13
Strongly connected graph      12 332
Structure      226
Subgraph      11
Subset of a set      3
Subset-Sum      268 292
Substitution rule      100
Substring      14
Sudan, Madhu      415
Symmetric difference      169
Symmetric relation      9
Synchronizing sequence      92
Szegedy, Mario      415
Tableau      355
Tarjan, Robert E.      419
Tautology      382
Term, in a polynomial      154
Terminal      100
Terminal in a context-free grammar      102
Th(M)      226
Th(M) (theory of model)      226
Theorem      17
Theory, of a model      226
Tic-tac-toe, game of      329
Time complexity      247—294
Time complexity class      267
Time complexity, analysis of      248—253
Time complexity, of nondeterministic Turing machine      255
Time constructible function      340
Time hierarchy theorem      341
TIME(f(n))      251
TM      see “Turing machine”
TQBR      311
Transducer, finite state      87
Transducer, log space      324
Transition      34
Transition function      3 5
Transitive closure      401
Transitive relation      9
Trapdoor function      410
TREE      11
Tree, leaf      11
Tree, parse      100
Tree, root      11
Triangle in a graph      295
Tuple      6
Turing machine      137—154
Turing machine, alternating      381
Turing machine, comparison with finite automaton      138
Turing machine, defined      140
Turing machine, describing      156—159
Turing machine, examples of      142—147
Turing machine, marking tape symbols      146
Turing machine, multitape      148—150
Turing machine, nondeterministic      150—152
Turing machine, oracle      232 348
Turing machine, schematic of      138
Turing machine, universal      174
Turing reducibility      232—233
Turing, Alan M.      2 137 155 419
Turing-decidable language      142
Turing-recognizable language      142
Turing-unrecognizable language      181—182
Turing-unrecognizable language, $EQ_{TM}$       210
Two-dimensional finite automaton      213
Two-headed finite automaton      212
Ullman, Jeffrey D.      415 417 419
Unary, alphabet      52 82 212
Unary, function      8
Unary, notation      259 295
Unary, operation      44
Uncountable set      176
Undecidability, diagonalization method      174—181
Undecidability, of $A_{TM}$       174
Undecidability, of $EQ_{CFG}$ .      172
Undecidability, of $EQ_{TM}$       192
Undecidability, of $E_{lba}$       195
Undecidability, of $E_{TM}$       189
Undecidability, of $HALT_{TM}$       188
Undecidability, of $REGULAR_{TM}$       191
Undecidability, of Post correspondence problem      200
Undecidability, via computation histories      192—205
Undirected graph      10
UNION operation      4 44 45 59—60
Unit rule      107
Universal quantifier      310
Universal state      381
Universal Turing machine      174
Universe      225 310
Useless state in PDA      184
Useless state in TM      211
Valiant, Leslie G.      415
Variable, Boolean      271
Variable, bound      310
Variable, in a context-free grammar      100 102
Variable, start      100 102
Venn diagram      4
Verifier      265 388
Vertex of a graph      10
VERTEX-COVER      284
virus      222
Vitanyi, Paul      417
Wegman, Mark      416
Well-formed formula      225
Williamson, David P.      416
Window, in a tableau      279
Winning strategy      314
Wire in a Boolean circuit      352
Worst-case analysis      248
XOR operation      15 354
Yannakakis, Mihalis      418
Yields, for configurations      141
Yields, for context-free grammars      102
Zuckerman, Herbert S.      418

1 2 3

О проекте