Lewis H.R., Papadimitriou C.H. — Elements of the Theory of Computation :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Lewis H.R., Papadimitriou C.H. — Elements of the Theory of Computation

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

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

Название: Elements of the Theory of Computation

Авторы: Lewis H.R., Papadimitriou C.H.

Аннотация:

Lewis and Papadimitriou present this long awaited Second Edition of their best-selling theory of computation. The authors are well-known for their clear presentation that makes the material accessible to a a broad audience and requires no special previous mathematical experience. In this new edition, the authors incorporate a somewhat more informal, friendly writing style to present both classical and contemporary theories of computation. Algorithms, complexity analysis, and algorithmic ideas are introduced informally in Chapter 1, and are pursued throughout the book. Each section is followed by problems.

Язык:

Рубрика: Computer science/

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

ed2k: ed2k stats

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

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

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

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

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

$\ast$ -free regular expressions      329
$\epsilon$ -approximation algorithm      335
$\lambda$ -change neighborhood      347
$\mathcal{EXP}$ , or exponential time      296—297
$\mathcal{NP}$       293
$\mathcal{NP}$ -complete problems      301—350
$\mathcal{P}$       275—277
$\mu$ -recursive function      239
2-change neighborhood      347
2-head finite automaton      91 262
2-SATISFIABILITY      290—292 313—315 323 333
2-tape finite automaton      62—63
3-Coloring      308
3-Satisfiability      313 317 323 326 333
4-change neighborhood      347
Acceptance      57
Acceptance by empty store      136
Acceptance by final state      135
Acceptance by finite automata      57 66
Acceptance by nondeterministic finite automata      66
Acceptance by nondeterministic Turing machines      222
Acceptance by pushdown automata      132
Acceptance by random access Turing machines      216
Acceptance by Turing machines      194
Accepting configuration      194
Aho, A.V.      177
Algorithms      2—4 31—41
Algorithms approximation, or $\epsilon$ -approximation      335—339
Algorithms backtracking and branch-and-bound      339—345
Algorithms dynamic programming      154 334
Algorithms for context-free grammars      150—158
Algorithms for finite automata      102 110
Algorithms local improvement and simulated annealing      345—349
Algorithms polynomial-time      276 92
Algorithms, efficient      275 292
Alphabet      42 116 181
Ambiguous grammar      128
Antisymmetric relation      15
Approximation algorithm      335—337
Arguments of a function      11
Arithmetic progression      89
Backtracking algorithm      341—343
Bar-Hillel, V.      110 176
Basic functions      234
Bijection      11
Bin packing      332
Binary alphabet      42
BINARY BOUNDED TITLING      316
Binary relation      10
Binary representation of the integers      196—197 219—220 284—285 316
Bird, M.      111
Blank symbol, $\bigsqcup$       181
Boolean connectives      288
Boolean formula      288—289
Boolean formula in conjunctive normal form      288
Boolean logic      288
Boolean variable      288
Bottom-up parsing      169—172
Bounded Tiling      310—312 315—316
Boustrophedon language      259
Brainerd, W.S.      244
Branch-and-bound algorithm      343—345
Brassard, G.      53
Bratley, P.      53
Busy-beaver function      253
Cantor, G.      27 53
Cartesian product      10
Certificate, or witness      297
Chomsky hierarchy      272
Chomsky N.      175—177 273
Chomsky normal form      151
Church-Turing thesis      245—247
Church-Turing thesis quantitative refinement      276
Clause      288
CLIQUE      283 326—327 333 336
Closure      30 37—39
Closure property      39 75—77 143—145
Cobham, A.      299
Compatible transitions      158
Compiler      2 56 117 162—170
Complement of a set      45
Complement of a set, $\mathcal{P}$ closed under      76
Complement of a set, context-free languages not closed under      147
Complement of a set, recursive languages closed under      199—200
Complement of a set, recursively enumerable languages not closed under      253
Complement of a set, regular languages closed under      76
Composite number      223 298—299
Composition of functions      234
Computation      1—4
Computation by a random access Turing machine      216—218
Computation by a Turing machine      185 194—200
Computation by grammars and other systems      232
Concatenation of languages      45
Concatenation of strings      42
Configuration of a finite automaton      57 66
Configuration of a pushdown automaton      131
Configuration of a random access Turing machine      211
Configuration of a Turing machine      202—204
Consistent strings      158
context      115 228 232
Context-free grammar      114—115
Context-free grammar, ambiguous      128
Context-free grammar, self-embedding      149
Context-free grammars and pushdown automata      136—142
Context-free grammars weak precedence      173
Context-free grammars, undecidability of problems about      259—262
Context-free language      115—175
Context-free language, deterministic      157
Context-free language, inherently ambiguous      129
Context-sensitive language      271
Cook's theorem      312—313
Cook, S.A.      244 350
Cormen, T.H.      53
Countable set      21
Countably infinite set      21
Counter machine      258
Cycle in a graph      18
Cycle in a graph Euler cycle      281—282
Cycle in a graph Hamilton cycle      282 320—324
Davis — Putnam procedure      342
Davis, M.      243—244
de Fermat, P.      299
Dead-end configuration      160—161
Decides      195 216 222
Definite language      85
Definition by induction      43
Derivation      116 228
Derivation, leftmost      127
Derivation, rightmost      127
Deterministic context-free language      159
Deterministic finite automaton      57
Deterministic finite-state transducer      60
Deterministic pushdown automaton      158
Difference of sets      7
Directed graph      14
Disjoint sets      8
Disjunctive normal form of a regular expression      52
Domain of a function      11
Dominating set      333 349
Dynamic programming algorithm      154 278 334
Earley, J.      176
Edge of a graph      14
Edmonds, J.      299
Element of a set      5
Empty set      5
Empty string      42
Enumerating Turing machine      268
Equinumerous sets      20
Equivalence class      16
EQUIVALENCE OF DETERMINISTIC FINITE AUTOMATA      286

EQUIVALENCE OF NONDETERMINISTIC FINITE AUTOMATA      286 295 328
EQUIVALENCE OF REGULAR EXPRESSIONS      287 328
Equivalence relation      16
Equivalent finite automata      69
Equivalent strings with respect to L      94
Equivalent strings with respect to M      95
Erasing move of a Turing machine      182
Euler cycle      281—282
Euler, L.      281 299
Eulerian graph      281
Evey, J.      176
Exact cover      318—321 324—325 331
Exponentially bounded Turing machine      296
False, $\bot$       289
Fanout of a context-free grammar      145
Final states      57 66 131
Finite automaton      55
Finite automaton, 2-head      91 262
Finite automaton, 2-tape      62—63
Finite automaton, nondeterministic      65
Finite automaton, two-way      101
Finite control      56
Finite set      20
Finite-state machine      55
Fully approximate problem      336
Function      10
Function, $\mu$ -recursive      239
Function, basic      234
Function, defined by cases      236
Function, defined recursively      234
Function, primitive recursive      234
Gadget      320
Garey M.R.      351
Generalization of a problem      315
Generates      115
Ginsburg, S.      111 177
Grammar, or unrestricted grammar      228—232
Grammatically computable function      232
Graph      15
Graph coloring      318
Greibach normal form      149
Greibach, S.      177
Halmos, P.      52
Halted configuration      183 211
Halting problem      279—280
Halting problem for Turing machines      251—254
Halting states      181
Hamilton cycle      282—286 292 295 302—304 309 320 323 331 333 338 342—343
Hamilton path      309 331 333
HAMILTON PATH BETWEEN TWO SPECIFIED NODES      331
Hamilton, W.R.      282
Harrison, M.A.      53 177
Hartmanis, J.      299
Height of a parse tree      145
Hennie, F.C.      243
Hermes, H.      244
Hitting Set      332
Hochbaum, D.      351
Homomorphism      85 148 316
Homomorphism, nonerasing      299
Hopcroft, J.E.      111 244
Horn clause      349
Ichbiah, J.D.      177
Identity function      234
Image of a function      11
In-place acceptor, or linear-bounded automaton      271
Inapproximable problem      336
Independent set      283 286 292 296 298 301—302 318 326—328 332—336
INDUCED SUBGRAPH ISOMORPHISM      332
INEQUIVALENCE OF $\ast$ -FREE REGULAR EXPRESSIONS      329
INEQUIVALENCE OF REGULAR EXPRESSIONS      328
Infinite set      21
Inherently ambiguous language      129
Initial configuration      194 216
Initial state      56—57 66 131 181
Input alphabet      194
Input symbols      131
Input tape      56
Instructions of a random access Turing machine      211
Integer programming      332
Intersection of sets      6
Inverse of a function      12
Johnson, D.S.      351
k-tape Turing machine      202
Karp, R.M.      350
Kasami, T.      176
Kleene star      45
Kleene, S.C.      110 244
Knapsack      305—307 324—326
Knuth, D.E.      53 111 177
Label      123
Landweber, L.H.      244
Language      44—52
Language generator      51 113
Language recognition device      51 113
Language, accepted by a finite automaton      57 66
Language, accepted by empty store      136
Language, accepted by final slate      135
Language, context-free      114—175
Language, deterministic context-free      159—175
Language, generated by a grammar      115 228
Language, recursive      195 199 267—271
Language, recursively enumerable      199 267—271
Language, regular      47—51 77—80
Languages vs. problems      279—281
Leaves of a parse tree      123
Left factoring      165
Left recursion      166
Left-end symbol, $\triangleright$       181
Left-linear grammar      122
Leftmost derivation      127
Leiserson, C.E.      53
Length of a computation      132 145 185
Length of a derivation      116
Length of a path      18
Length of a sequence      10
Length of a siring      42
Levin, L.A.      350
Lewis, P.M.      II 177
Lexicographic enumeration      269
Lexicographic ordering      44
Lexicographically Turing-enumerable language      269
Lin — Kernighan algorithm      347
Linear      143
Linear-bounded automaton      271
Literal, positive and negative      288
Liu, C.L.      52
LL(1)-context-free grammar      167
LL{1) grammar      167
Longest cycle      332
Machtey, M.      244
Markov system, or Markov algorithm      232
Markov, A.A.      244
MAX 2-SAT      316—317
MAX SAT      314—316 336 347
McNaughton, R.      110
Mealy, G.H.      110
Member, or element, of a set      5
Miller, G.A.      175
Minimal element of a partial order      18
Minimalizable function      239
Minimalization      238
Minimum equivalent finite automaton      105 330—331
Minimum spanning tree      350
Minsky, M.L.      243
Moore, E.F.      110
Morris, J.H., Jr.      111
Morse, S.P.      177
n-ary relation      10
n-fold Cartesian product      10

1 2

О проекте