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

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

#SAT      359
$ALL_{cfg}$       181
$A_{CFG}$       156
$A_{DFA}$       152
$A_{LBA}$       177
$A_{NFA}$       153
$A_{rex}$       154
$A_{tm}$       159
$EQ_{cfg}$       158
$EQ_{DFA}$       155
$EQ_{REX \uparrow}$       314
$EQ_{tm}$ , Turing-unrecognizability      194
$EQ_{tm}$ , undecidability      175
$E_{cfg}$       157
$E_{lba}$       179
$E_{NFA}$       278 282
$E_{TM}$ undecidability      173
$HALT_{TM}$       172
$NP^{A}$       318
$P^{A}$       318
$REGULAR_{TM}$       174
2DFA      see "Two headed finite automaton"
2DIM-DFA      see "Two dimensional finite automaton"
2SAT      275
3COLOR      275
3SAT      329
Accept state      34 35
Acceptance problem for CFG      156
Acceptance problem for DFA      152
Acceptance problem for LBA      177
Acceptance problem for NFA      153
Acceptance problem for TM      159
Accepting computation history      176
Accepting configuration      129
Accepts a language, meaning of      36
Acyclic graph      344
Adjacency matrix      237
Adleman, Leonard M.      381 384
Aho, Alfred V.      381 385
Akl, Selim G.      381
Algorithm, complexity analysis      226—231
Algorithm, decidability and undecidability      151—168
algorithm, defined      142—144
Algorithm, describing      144—147
Algorithm, Euclidean      239
Algorithm, polynomial time      234—241
Algorithm, running time      226
Allen, Robin W.      382
Alon, Noga      381
Alphabet, defined      13
Alternating Turing machine      348
Alternation      348—354
Ambiguity      97—98
Ambiguous grammar      97 196
Amplification lemma      337
AND operation      14
Angluin, Dana      381
Anti-clique      27
Approximation algorithm      333—335
Argument      8
Arithmetization      361
Arity      8 205
Arora, Sanjeev      381
ASPACE(f(n))      349
Asymptotic analysis      226
Asymptotic notation, big-O notation      226—228
Asymptotic notation, small-o notation      228
Asymptotic upper bound      227
ATIME(t(n))      349
Atomic formula      205
Automata theory      3 see "Regular
Average-case analysis      226
Baase, Sara      381
Babai, Laszlo      381
Bach, Eric      382
Balcazar, Jose Luis      382
Basis of induction      2 3
Beame, Paul W.      382
Big-O notation      226—228
binary function      8
Binary relation      8 9
Bipartite graph      304
Blum, Manuel      382
Boolean circuit      321—329
Boolean circuit, depth      367
Boolean circuit, gate      322
Boolean circuit, size      367
Boolean circuit, uniform family      367
Boolean circuit, wire      322
Boolean formula      249 283
Boolean formula, minimal      319
Boolean formula, quantified      284
Boolean logic      14—15
Boolean matrix multiplication      368
Boolean operation      14 204 249
Boolean variable      249
Bound variable      284
Branching program      343
Branching program, read-once      345
Brassard, Gilles      382
Bratley, Paul      382
Breadth-first search      234
Brute-force search      235 238 241 248
Cantor, Georg      160
Carmichael number      340
Carmichael, R.D.      382
Cartesian product      6 46
CD-ROM      294
Certificate      243
CFG      "Context-free grammar"
CFL      see "Context-free language"
Chaitin, Gregory J.      215
Chandra, Ashok      3 82
Characteristic sequence      164
Checkers, game of      294
Chernoff bound      338
Chess, game of      294
Chinese remainder theorem      339
Chomsky normal form      98—101 121 156 240
Chomsky, Noam      382
Church — Turing thesis      143—144 231
Church, Alonzo      2 143 206
CIRCUIT-SAT      328
Circuit-satisfiability problem      328
CIRCUIT-VALUE      371
Circular definition      65
Clause      251
CLIQUE      27 245
Closed under      45
Closure under complement P      271
Closure under complementation, context-free languages, non-      120
Closure under complementation, regular languages      85
Closure under concatenation, context-free languages      121
Closure under concatenation, NP      271
Closure under concatenation, P      271
Closure under concatenation, regular languages      47 60
Closure under intersection, context-free languages, non-      120
Closure under intersection, regular languages      46
Closure under star, context-free languages      121
Closure under star, NP      272
Closure under star, P      272
Closure under star, regular languages      62
Closure under union, context-free languages      121
Closure under union, NP      271
Closure under union, P      271
Closure under union, regular languages      45 59
CNF-formula      251
Co-Turing-recognizable language      167
Cobham, Alan      382
Coefficient      143

Coin-flip step      336
Complement operation      4
Complexity class, ASPACE(f(n))      349
Complexity class, ATIME(t(n))      349
Complexity class, coNL      300
Complexity class, coNP      247
Complexity class, EXPSPACE      310
Complexity class, EXPTIME      282
Complexity class, L      295
Complexity class, NC      369
Complexity class, NL      295
Complexity class, NP      241—248
Complexity class, NPSPACE      281
Complexity class, NSPACE(f(n))      278
Complexity class, NTIME(f(n))      245
Complexity class, P      234—241 247—248
Complexity class, PH      354
Complexity class, PSPACE      281
Complexity class, SPACE(f(n))      278
Complexity class, TIME(f(n))      229
Complexity theory      2
Complexity theory, Church — Turing thesis      143—144 231
Composite number      242 339
Compositeness witness      341
COMPOSITES      242
Compressible string      218
Computability theory      2
Computability theory, decidability and undecidability      151—168
Computability theory, recursion theorem      197—203
Computability theory, reducibility      171—194
Computability theory, Turing machines      12 5—142
Computable function      190
Computation history, context-free languages      181—182
Computation history, defined      176
Computation history, linear bounded automata      177—180
Computation history, Post correspondence problem      183—189
Computation history, reducibility      176—189
Computational model      31
Computer virus      202
Concatenation of strings      14
Concatenation operation      44 47 60—61
Configuration      128 129 296
Conjunction operation      14
Conjunctive normal form      251
coNL      300
Connected graph      11 145
CONp      247
Context-free grammar, ambiguous      97 196
Context-free grammar, defined      94
Context-free language, decidability      156—158
Context-free language, defined      93
Context-free language, efficient decidability      240—241
Context-free language, inherently ambiguous      98
Context-free language, pumping lemma      115—119
Cook — Levin theorem      249—330
Cook, Stephen A.      248 382
Cormen, Thomas      382
Corollary      17
Correspondence      161
Countable set      161
Counterexample      18
Counting problem      359
Cross product      6
Cryptography      372—377
Cut edge      334
Cut, in a graph      273 334
CYCLE      11
Davis, Martin      143
Decidability      see also "Undecidability"
Decidability of $A_{CFG}$       156
Decidability of $A_{DFA}$       152
Decidability of $A_{REX}$       154
Decidability of $EQ_{DFA}$       155
Decidability of $E_{CFG}$       157
Decidability, context-free language      156—158
Decidability, regular language      152—156
Decidable language      130
Decider, deterministic      130
Decider, nondeterministic      140
Decision problem      334
Definition      17
Degree of a node      10
DeMorgan's laws, example of proof      20
Depth complexity      367
Derivation      92
Derivation, leftmost      98
Descriptive complexity      215
Deterministic computation      47
Deterministic finite automaton, acceptance problem      152
Deterministic finite automaton, defined      35
Deterministic finite automaton, emptiness testing      154
Deterministic finite automaton, minimization      275
DFA      see "Deterministic finite automaton"
Diagonalization method      160—167
Diaz, Josep      382
Difference hierarchy      276
Digital signatures      374
Directed graph      12
Directed path      12
Disjunction operation      14
Distributive law      15
Domain of a function      7
Dynamic programming      240
Edge of a graph      10
Edmonds, Jack      382
Element distinctness problem      135
Element of a set      3
Emptiness testing for CFG      157
Emptiness testing for DFA      154
Emptiness testing for LBA      179
Emptiness testing for TM      173
Empty set      4
Empty string      13
Enderton, Herbert B.      382
Enumerator      140—141
Equality operation      15
Equivalence relation      9
Equivalent machines      54
Erdoes, Paul      381
Error probability      336
Euclidean algorithm      239
Even, Shimon      382
Exclusive or operation      15
Existential state      348
Exponential bound      228
Exponential, versus polynomial      234
EXPSPACE      310
EXPSPACE-completeness      313—319
EXPTIME      282
Factor of a number      339
Feller, William      382
Fermat test      340
Fermat's little theorem      340
Feynman, Richard P.      382
Final state      35
Finite automaton      278
Finite automaton, automatic door example      32
Finite automaton, computation of      40
Finite automaton, decidability      152—156
Finite automaton, defined      35
Finite automaton, designing      41—44
Finite automaton, transition function      35
Finite automaton, two dimensional      196
Finite automaton, two headed      196
Finite state machine      see "Finite automaton"
Finite state transducer      87
Fixed point theorem      203
Formal proof      209
Formula      204 249
FORMULA-GAME      288

1 2 3

О проекте