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

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

blank
blank
blank
Красота
blank
Lewis H.R., Papadimitriou C.H. — Elements of the Theory of Computation
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.


Язык: en

Рубрика: Computer science/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Naur, P.      175
Negative literal      288
Neighborhood, or neighborhood relation      345
Nerode, A.      111
Node      14 123
Node cover      284 327—328 335—337
Nondeterminism      2 63 158 221 292
Nondeterministic 2-tape finite automaton      85
Nondeterministic finite automaton      65
Nondeterministic polynomial time, or $\mathcal{NP}$      293
Nondeterministic Turing machine      221
Nonerasing homomorphism      299
Nonterminal      115 228
Occurrence      42
Oettinger, A.G.      175
Ogden, W.G.      176
One-to-one function      11
Onto function      11
Or, $\vee$      289
Order of a function, $\mathcal{O}(\cdot)$      32
Ordered pair      9
Ordered triple      10
Ordered tuple      10
Output of a machine      196
Papadimitriou, C.H.      244 300 351
Parse tree      123
Parser      58 163—170
Partial order      17
Partition      285—287 295 299 301 305—307 326—327
Partition of a set      8
Partly approximate problem      336
Path      18 145
Perles, M.      110 176
Polynomial reduction between two languages, or problems      302
Polynomial Turing reduction      309
Polynomial-time algorithm      276
Polynomially balanced language      298
Polynomially bounded Turing machine      276 293
Polynomially decidable      276
pop      131
Positive literals      288
Post correspondence system      262
Post, E.L.      243 273
Power set      8
Pratt, V.R.      111
Precedence relation      172
Precedes, $\prec$      124—126
Prefix      43 83
Primitive recursive function      234
Primitive recursive predicate      236
Problem      279
Program counter      211
Program of a random access Turing machine      211
Proper subset      6
Purge algorithm for 2-SAT      291 342
push      131
Pushdown automaton      131—139
Pushdown automaton and context-free languages      136—142
Pushdown automaton, deterministic      158—175
Pushdown automaton, simple      139—141
Pushdown store, or stack      131
Quadruple      10
Quintuple      10
Quotient of languages      98
Rabin, M.0.      110
Random access Turing machine      211
Range of a function      11
Rate of growth of a function      32
Reachability      279—280
Reading head      56
Reckhow, R.A.      244
Recursive function      196
Recursive language      195
Recursively enumerable language      198
Reduce move of a parser      171
Reduction from a language to another      254
Reduction, polynomial      302
Reeves, C.R.      351
Refinement of an equivalence relation      20 95
Reflexive relation      14
Reflexive transitive closure      30
Register of a random access Turing machine      211
Regular expression      48
Regular language      50 75—91 119
Rejecting configuration      194
Rejects      194 216
RELIABLE GRAPH      332
Reversal, $^{R}$      43
Rewriting system      228
Right quotient of languages      83 148
Right-linear grammar      122
Rightmost derivation      127
Rivest, R.L.      53
Rogers, H., Jr.      244
Root of a parse tree      123
Root of a tree      334
Rule of a grammar      114—115 227—228
Salomaa, A.      53
Satisfiability      290—298 301—304 308—318
Satisfiable Boolean formula      289
Satisfying truth assignment      289
Schutzenberger, M.P.      176—177
Scott, D.      110
Self-embedding grammar      149
Self-reducibilityy      287 340
Semidecides      198 216 222
SEQUENCE      10
Set      5
SET COVER      332
Sethi, R.      177
Sextuple      10
Shamir, E.      110 176
Shepherdson, J.C.      111
Shift move of a parser      171
Similar      125
SIMPLE      139
Simulated annealing      348—349
Single-turn pushdown automaton      143
Singleton      5
Sipser, M.      244
Solution of a problem      340—349
Stack symbols      131
Standard automaton for a regular language      96
Standard derivation      259
Star height of a regular expression      52
Start symbol      115 228
State      56—57 65 115 131 181
State diagram      59
Stearns, R.E.      177 299
Steiglitz, K.      351
STEP      116 132 185 276
String      42
String matching      108
Subgraph Isomorphism      332
Subsequence      83
Subset      6
Substring      43
Successor function      234
Suffix      43 83
Symbol      42
Symmetric relation      14
Tape      57 180 201—209 212
TAXICAB RIPOFF      332
Temperature      349
Terminal symbol      115 228
Ternary relation 10 item Thompson, K.      111
Tile      262
Tiling problem      263—267 310—313
Tiling system      262
Top-down parser      163
Total order      18
Transformation of a configuration      189
Transition      66 131
Transition function      57 181 202
Transition relation      66 131 222
Transitive relation      16
Traveling salesman problem      276 282—283 297—298 301 318 324 338—339 345—349
TREE      333
True, $\top$      289
Truth assignment      289
Turing machine      179—226
Turing machine as algorithm      179 245—247
Turing machine with multiple heads      208
Turing machine with random access      210—219
Turing machine with two-dimensional tapes      208
Turing machine, efficient      275—292
Turing machine, exponentially bounded      296
Turing machine, k-tape      201—208
Turing machine, nondeterministic      221—226 292—294
Turing machine, polynomially bounded      276—292
Turing machine, universal      247—250
Turing machines as algorithms      179 245-247
Turing, A.M.      2 179 243
Turing-enumerable language      268
TWO-MACHINE SCHEDULING      305—307 326 336—337
Two-way finite automaton      101
Ullian, J.S.      177
Ullman, J.D.      177 244
Unary function      10
Unary notation      90
UNARY PARTITION      286
Uncountable set      21 28—29
Undecidable language      254—271
Undirected graph      15
UNDIRECTED HAMILTON CYCLE      322—324
Unicursal      281
Union of sets      6
Universal Turing machine      247—250
Unrestricted grammar      228
Unsatisfiable Boolean formula      290
Unsolvable problem      254—271
Valiant, L.G.      176
Value of a function      11
Wang, H.      273
Warshall, S.      53
Weak precedence grammar      173
Witness, or certificate      297
Yamada, H.      110
Yield of a parse tree      123
Yields in one step, $\vdash$      66 132 212
Yields, $\vdash^{*}$      58 185 212
Young, P.R.      244
Younger, D.H.      176
Zero function      234
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте