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.

Аннотация:

Michael Sipser's emphasis on unifying computer science theory - rather than offering a collection of low-level details - sets the book apart, as do his intuitive explanations. Throughout the book, Sipser builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own.

Язык:

Рубрика: Computer science/

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

ed2k: ed2k stats

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

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

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

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

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

Recursion theorem      197—203
Recursion theorem, fixed-point version      203
Recursion theorem, terminology for      201
Recursive language      see "Decidable language"
Recursively enumerable      see "Turing-recognizable"
Recursively enumerable language      130
Reducibility      171—194
Reducibility, mapping      190—194
Reducibility, polynomial time      250
Reducibility, via computation histories      176—189
Reduction      171 191
Reduction, mapping      191
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—83
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      152—156
Regular language, defined      40
Regular operation      44
Rejecting computation history      176
Rejecting configuration      129
Relation      8 204
Relation, binary      8
Relatively prime      238
Relativization      318—321
RELPRIME      238
Reverse of a string      14
Rice's theorem      175 196
Rinooy Kan, A. H. G.      383
Rivest, Ronald L.      382 384
Robinson, Julia      143
Roche, Emmanuel      384
Root in a tree      11
Root of a polynomial      143
Rule in a context-free grammar      92 94
Rumely, Robert S.      381
Ruzzo, Walter L.      383
SAT      254 282
Satisfiability problem      249
Satisfiable formula      249
Savitch's theorem      279—281
Schabes, Yves      384
Schaefer, Thomas J.      384
Scope      284
Scope, of a quantifier      205
Secret key      372
Sedgewick, Robert      384
Self-reference      198
Sentence      284
SEQUENCE      6
Sequential computer      366
Set      3
Set, countable      161
Set, uncountable      162
Sethi, Ravi      381
Shallit, Jeffrey      382
Shamir, Adi      384
Shen, Alexander      384
Shmoys, David B.      383
Simple path      11
Sipser, Michael      384 385
Size complexity      367
Small-o notation      228
Space complexity      277—304
Space complexity class      278
Space complexity of nondeterministic Turing machine      277
Space constructible function      306
Space hierarchy theorem      307
SPACE(f(n))      278
Spencer, Joel H.      381
STACK      101
Star operation      44 62—63 272
Start configuration      129
Start state      34
Start variable, in a context-free grammar      92 94
State diagram, finite automaton      34
State diagram, pushdown automaton      104
State diagram, Turing machine      132
Stearns, Richard E.      383
Steiglitz, Kenneth      384
Stinson, Douglas R.      385
String      13
Strongly connected graph      12 304
Structure      205
Subgraph      11
Subset      4
Subset of a set      3
Subset-Sum      246 268
Substitution rule      92
Substring      14
Sudan, Madhu      381
Symmetric difference      155

Symmetric relation      9
Szegedy, Mario      381
Tableau      325
Tarjan, Robert E.      385
Tautology      350
Term, in a polynomial      142
Terminal      92
Terminal in a context-free grammar      94
Th( $\mathcal{M}$ )      206
Theorem      17
Theory, of a model      206
Tic-tac-toe, game of      302
Time complexity      225—271
Time complexity class      245
Time complexity of nondeterministic Turing machine      233
Time complexity, analysis of      226—231
Time constructible function      310
Time hierarchy theorem      311
TIME(f(n))      229
TM      see "Turing machine"
TQBF      284
Transducer, finite state      87
Transducer, log space      297
Transition      34
Transition function      3 5
Transitive closure      368
Transitive relation      9
Trapdoor function      377
TREE      11
Tree, leaf      11
Tree, parse      92
Tree, root      11
Triangle in a graph      272
Tuple      6
Turing machine      125—142
Turing machine, alternating      348
Turing machine, comparison with finite automaton      126
Turing machine, defined      128
Turing machine, describing      144—147
Turing machine, examples of      130—135
Turing machine, marking tape symbols      134
Turing machine, multitape      136—138
Turing machine, nondeterministic      138—140
Turing machine, oracle      211
Turing machine, schematic of      126
Turing machine, universal      160
Turing reducibility      211—212
Turing, Alan M.      2 125 143 385
Turing-decidable language      130
Turing-recognizable language      130
Turing-unrecognizable language      167—168
Turing-unrecognizable language, $EQ_{TM}$       194
Two dimensional finite automaton      196
Two headed finite automaton      196
Ullman, Jeffrey D.      381 383 385
Unary function      8
Uncountable set      162
Uncut edge      335
Undecidability of $A_{TM}$       5 160
Undecidability of $EQ_{CFG}$       158
Undecidability of $EQ_{TM}$       175
Undecidability of $E_{LBA}$       179
Undecidability of $E_{TM}$       173
Undecidability of $HALT_{TM}$       172
Undecidability of $REGULAR_{TM}$       175
Undecidability of Post correspondence problem      184
Undecidability, diagonalization method      160—167
Undecidability, via computation histories      176—189
Undirected graph      10
UNION operation      4 44 45 59—60
Unit rule      99
Universal quantifier      284
Universal state      348
Universal Turing machine      160
Universe      205 284
Useless state in PDA      170
Useless state in TM      195
Valiant, Leslie G.      381
van Leeuwen, Jan      385
Variable in a context-free grammar      92 94
Variable, Boolean      249
Variable, bound      284
Variable, start      92 94
Venn diagram      4
Verifier      243 355
Vertex of a graph      10
VERTEX-COVER      261
virus      202
Vitanyi, Paul      383
Wegman, Mark      382
Well-formed formula      204
Williamson, David P.      383
Window, in a tableau      256
Winning strategy      288
Wire in a Boolean circuit      322
Worst-case analysis      226
XOR operation      15 324
Yannakakis, Mihalis      384
Zuckerman, Herbert S.      384

1 2 3

О проекте