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

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

#SAT      392
$ALL_{cfg}$       197
$A_{CFG}$       170
$A_{DFA}$       166
$A_{LBA}$       194
$A_{NFA}$       167
$A_{rex}$       168
$A_{tm}$       174
$EQ_{cfg}$       172
$EQ_{DFA}$       169
$EQ_{REX\uparrow}$       344
$EQ_{tm}$ , Turing-unrecognizability      210
$EQ_{tm}$ , undecidability      192
$E_{cfg}$       171
$E_{dfa}$       168
$E_{lba}$       195
$E_{TM}$ , undecidability      189
$HALT_{TM}$       188
      348
      348
$REGULAR_{TM}$       191
$w^{\mathcal{R}}$ (reverse of w)      14
$\cap$ (intersection operation)      4
$\circ$ (concatenation operation)      44
$\cup$ (union operation)      4 44
$\empty$ (empty set)      4
$\exists$ (existential quantifier)      310
$\forall$ (universal quantifier)      310
$\in$ (element)      3
$\langle\dot\rangle$ (encoding)      157 259
$\Leftarrow$ (reverse implication)      18
$\leftrightarrow$ (equality operation)      15
$\Leftrightarrow$ (logical equivalence)      18
$\leq_L$ (log space reduction)      324
$\leq_m$ (mapping reduction)      207
$\leq_P$ (polynomial time reduction)      272
$\leq_T$ (Turing reduction)      233
$\mathbb{N}$ (natural numbers)      4 227
$\mathbb{R}$ (real numbers)      157 176
$\mathbb{R}^+$ (nonnegative real numbers)      249
$\mathcal{P}(Q)$ (power set)      53
$\neg$ (negation operation)      14
$\notin$ (not element)      3
$\oplus$ (exclusive OR operation)      15
$\rightarrow$ (implication operation)      15
$\Rightarrow$ (implication)      18
$\Sigma$ (alphabet)      53
$\Sigma_{varepsilon}$ ( $\Sigma\cup{varepsilon}$ )      53
$\sqcup$ (blank)      140
$\subseteq$ (proper subset)      4
$\subseteq$ (subset)      3
$\times$ (Cartesian or cross product)      6
$\uparrow$ (exponentiation)      343
$\varepsilon$ (empty string)      13
$\varsubsetneq$ (proper subset)      328
$\vee$ (disjunction operation)      14
$\wedge$ (conjunction operation)      14
* (star operation)      44
+ (plus operation)      65
2DFA      see “Two-headed finite automaton”
2DIM-DFA      see “Two-dimensional finite automaton”
2SAT      299
3COLOR      297
3SAT      274 359
Accept state      34 35
Acceptance problem for CFG      170
Acceptance problem for DFA      166
Acceptance problem for LBA      194
Acceptance problem for NFA      167
Acceptance problem for TM      174
Accepting computation history      193
Accepting configuration      141
Accepts a language, meaning of      36
Acyclic graph      376
Adjacency matrix      259
Adleman, Leonard M.      415 418
Agrawal, Manindra      415
Aho, Alfred V.      415 419
Akl, Selim G.      415
Algorithm, complexity analysis      248—253
Algorithm, decidability and undecidability      165—182
algorithm, defined      154—156
Algorithm, describing      156—159
Algorithm, Euclidean      261
Algorithm, polynomial time      256—263
Algorithm, running time      248
Allen, Robin W.      416
Alon, Noga      415
Alphabet, defined      13
Alternating Turing machine      381
Alternation      380—386
Ambiguity      105—106
Ambiguous, grammar      105 212
Ambiguous, NFA      184
Amplification lemma      369
AND operation      14
Angluin, Dana      415
Anti-clique      27
Approximation algorithm      365—367
Argument      8
Arithmetization      394
Arity      8 225
Arora, Sanjeev      415
ASPACE(f(n))      382
Asymptotic analysis      248
Asymptotic notation, big-O notation      249—250
Asymptotic notation, small-o notation      250
Asymptotic upper bound      249
ATIME(t(n))      382
Atomic formula      225
Automata theory      3 (see also “Context-free language” “Regular
Average-case analysis      248
Baase, Sara      415
Babai, Laszlo      415
Bach, Eric      415
Balcazar, Jose Luis      416
Basis of induction      23
Beame, Paul W.      416
Big-O notation      248—250
binary function      8
Binary operation      44
Binary relation      8 9
Bipartite graph      332
Blank symbol $\sqcup$       140
Blum, Manuel      416
Boolean circuit      351—359
Boolean circuit, depth      400
Boolean circuit, gate      352
Boolean circuit, size      400
Boolean circuit, uniform family      400
Boolean circuit, wire      352
Boolean formula      271 310
Boolean formula, minimal      349
Boolean formula, quantified      311
Boolean logic      14—15
Boolean matrix multiplication      401
Boolean operation      14 225 271
Boolean variable      271
Bound variable      310
Branching program      376
Branching program, read-once      377
Brassard, Gilles      416
Bratley, Paul      416
Breadth-first search      256
Brute-force search      257 260 264 270
Cantor, Georg      174
Carmichael number      3 72
Carmichael, R.D.      416
Cartesian product      6 46
CD-ROM      321

Certificate      265
CFG      see “Context-free grammar”
CFL      see “Context-free language”
Chaitin, Gregory J.      236
Chandra, Ashok      416
Characteristic sequence      178
Checkers, game of      320
Chernoff bound      370
Chess, game of      320
Chinese remainder theorem      373
Chomsky normal form      106—109 130 170 263
Chomsky, Noam      416
Church — Turing thesis      155—156 253
Church, Alonzo      2 155 227
CIRCUIT-SAT      358
Circuit-satisfiability problem      358
CIRCUIT-VALUE      404
Circular definition      65
Clause      274
CLIQUE      27 268
Closed under      45
Closure under complementation, context-free languages, non-      128
Closure under complementation, P      294
Closure under complementation, regular languages      85
Closure under concatenation, context-free languages      129
Closure under concatenation, NP      295
Closure under concatenation, P      294
Closure under concatenation, regular languages      47 60
Closure under intersection, context-free languages, non-      128
Closure under intersection, regular languages      46
Closure under star, context-free languages      129
Closure under star, NP      295
Closure under star, P      295
Closure under star, regular languages      62
Closure under union, context-free languages      129
Closure under union, NP      295
Closure under union, P      294
Closure under union, regular languages      45 59
CNF-formula      274
Co-Turing-recognizable language      181
Cobham, Alan      416
Coefficient      155
Coin-flip step      368
Complement operation      4
Complexity class, ASPACE(f(n))      382
Complexity class, ATIME(t(n))      382
Complexity class, BPP      369
Complexity class, coNL      326
Complexity class, coNP      269
Complexity class, EXPSPACE      340
Complexity class, EXPTIME      308
Complexity class, IP      389
Complexity class, L      321
Complexity class, NC.      402
Complexity class, NL      321
Complexity class, NP      264—270
Complexity class, NPSPACE      308
Complexity class, NSPACE(f(n))      304
Complexity class, NTIME(f(n))      267
Complexity class, P      256—263 269—270
Complexity class, PH      386
Complexity class, PSPACE      308
Complexity class, RP      375
Complexity class, SPACE(f(n))      304
Complexity class, TIME(f(n))      251
Complexity class, ZPP      412
Complexity theory      2
Complexity theory, Church — Turing thesis      155—156 253
Composite number      265 371
Compositeness witness      373
COMPOSITES      265
Compressible string      239
Computability theory      2
Computability theory, decidability and undecidability      165—182
Computability theory, recursion theorem      217—224
Computability theory, reducibility      187—211
Computability theory, Turing machines      137—154
Computable function      206
Computation history, context-free languages      197—198
Computation history, defined      192
Computation history, linear bounded automata      193—197
Computation history, Post correspondence problem      199—205
Computation history, reducibility      192—205
Computational model      31
Computer virus      222
Concatenation of strings      14
Concatenation operation      44 47 60—61
Configuration      140 141 322
Conjunction operation      14
Conjunctive normal form      274
coNL      326
Connected graph      11 157
CONp      269
Context-free grammar, ambiguous      105 212
Context-free grammar, defined      102
Context-free language, decidability      170—172
Context-free language, defined      101
Context-free language, efficient decidability      262—263
Context-free language, inherently ambiguous      106
Context-free language, pumping lemma      123—128
Cook — Levin theorem      271—360
Cook, Stephen A.      271 359 402 416
Cormen, Thomas      416
Corollary      17
Correspondence      175
Countable set      175
Counterexample      18
Counting problem      392
Cross product      6
Cryptography      405—411
Cut edge      367
Cut, in a graph      296 367
CYCLE      11
d(x) (minimal description)      236
Davis, Martin      155
Decidability      170—172 (see also “Undecidability.context-free language”)
Decidability, of $A_{CFG}$       170
Decidability, of $A_{DFA}$       166
Decidability, of $A_{REX}$       168
Decidability, of $EQ_{DFA}$       169
Decidability, of $E_{CFG}$       171
Decidability, regular language      166—170
Decidable language      142
Decider, deterministic      142
Decider, nondeterministic      152
Decision problem      366
Definition      17
Degree of a node      10
DeMorgan’s laws, example of proof      20
Depth complexity      400
Derivation      100
Derivation, leftmost      106
Derives      102
Descriptive complexity      236
Deterministic computation      47
Deterministic finite automaton, acceptance problem      166
Deterministic finite automaton, defined      35
Deterministic finite automaton, emptiness testing      168
Deterministic finite automaton, minimization      299
DFA      see “Deterministic finite automaton”
Diagonalization method      174—181
Diaz, Josep      416
Difference hierarchy      300
Digital signatures      407
Directed graph      12
Directed path      12
Disjunction operation      14
Distributive law      15
Domain of a function      7
Dynamic programming      262

1 2 3

О проекте