|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J.V. — Handbook of Theoretical Computer Science: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Machine model 6 73—75
Machine, array processing 51
Machine, Kolmogorov — Barzdin 50
Machine, Kolmogorov — Uspenskii 32
Machine, LPRAM 57
Machine, MIMD — RAM 55
Machine, parallel 9 (see also parallel machine)
Machine, pointer 32 303
Machine, PRAM 58
Machine, probabilistic 9
Machine, random-access (see also random-access machine) 4 23
Machine, random-access stored-program 24
Machine, reasonable 4
Machine, reference 198 210
Machine, register 22
Machine, sequential 9
Machine, shared-memory 869
Machine, SIMDAG 50
Machine, storage modification 32
Machine, Turing (see also Turing machine) 4 17
Machine, universal 198 210
Machine, vector 45
Machine, WRAM 58
Machine-based complexity 181 182
machine-dependent 5
Machine-independent 5
Machine-independent complexity theory 163
majority 15
Majority function 141 772
manual 843
Many-one reduction 15
Marriage problem 662
Martingale 211
Master reduction 16
Matching (in graphs, parallel) 872 922—924 929 930
Matching keywords 262
Matching problem 780
matching regular expressions 282
Matching sets of keywords 273
Matching, Euclidean minimum 358
Matching, lexicographic 132
Matching, maximum 580
Matching, maximum cardinality 580
Matching, maximum weight 133 580
Matching, perfect 108 133 134 580
Matrix inversion 923 650
Matrix multiplication 650 872 912—913 916—917
Matrix multiplication, Boolean 786
Matrix multiplication, Coppersmith — Winograd 656
Matrix multiplication, exponent of 650
Matrix problem (in VLSI theory) 864
Matrix representation 661
Max-flow min-cut theorem 590 592
Maximal independent set 872 907 917—919 927—928 930
Maximum cardinality matching 580
maximum distance 360
Maximum finding 888—890
Maximum flow (parallel) 924 928—929
Maximum flow algorithm 593
Maximum flow problem 588
Maximum matching 580 583
Maximum multicommodity flow 609
Maximum weight matching 580
Maze searching 418
McNaughton — Yamada algorithm 286
MDLP see Minimum Description Length Principle
Measure problem 369
Median 330 889
Mellin transform 453 469 479 481 489 490 492 499
Memory 7
Memory, initialization of 24
Memory, input section 7
Memory, local 9
Memory, output section 7
Memory, shared 9
Menger’s theorem 529
Mental poker 743
Merge sort 467 471 892—893
Merge, odd-even 949
Merger 816
Merging 331 871 886—890 892—893
Merging network 816
Merging, two-way 331
Meromorphic function 450 454
Mesh network 864
Mesh-of-trees network 864 950
Message digest 726
Metacharacter 259 260 261
Meyer — Stockmeyer hierarchy 664
Min-flow max-cut theorem 592
Minimum cost flow problem 592 603
Minimum cost flow theorem 592
Minimum Description Length Principle (MLDP) 217 218
Minimum equivalent graph 540
Minimum Spanning Tree (MST) 555
Minimum spanning tree, Euclidean 358
Minkowski difference 411
Minkowski sum 411
Minor (of a graph) 547
Minor containment problem 547
Minor-closed 547
Minor-minimal 547
Minsky’s multicounter machine 4
Minterm 767
Mises — Wald — Church random sequence 193
MOD function 774
MOD gate 774
Model (in VLSI), multiswitch 841
Model (in VLSI), uniswitch 841 858
Module 650
Moment generating function 456
Monotone basis 787
Monotone circuit 773 780
Monotone circuit complexity 780
Monotone circuit value problem 926—929
Monotone formula 787
Monotone function 780
Monotone projection 780
Monotonicity over prefixes 205
Monte Carlo algorithm 115 904
Motion planning 393
Motion planning, adaptive 418
Motion planning, compliant 420
Motion planning, constrained 420
Motion planning, coordinated 405
Motion planning, exploratory 418
Motion planning, for a convex object 409 411
Motion planning, for a disk 408
Motion planning, for a ladder 397 406
Motion planning, in the presence of obstacles 419
Motion planning, kinodynamic 420
Motion planning, lower bounds 404
Motion planning, optimal 395 415
Motion planning, potential field approach to 394
Motion planning, projection technique for 405
Motion planning, retraction technique for 407
Motion planning, with uncertainty 420
Movable separability 420
Move-to-front rule 321
MST (minimum spanning tree) 555
MST family 555
Multi-output function 785
Multicommodity flow 609
Multicommodity flow, maximum 609
Multidimensional search 368 486
Multidimensional Turing machine 18
Multihead  -dimensional machine 228
Multihead tree machine 228
Multihead Turing machine 228
Multiple polynomials 697 704
| Multiplication 905 907—908 915—916
Multiplication (in VLSI theory) 865
Multiplication of matrices 650 656
Multiplication of numbers 660
Multiplication of polynomials 641
Multiswitch model 841
Multitape Turing machine 226
Multiterminal flow 605
Mutual recursion 168
Myhill — Nerode theorem 233
Naming theorem 184
NC 38 129 766 872 898
NC-reduction 132
NDTM see nondeterministic Turing machine
Nearest common ancestor 328
Nearest neighbor 356
NETIME 103
Network 36
Network (for sorting) 467 472
Network flow see flow
Network topology 862
Network, binary  -dimensional cube 947
Network, butterfly 863 947
Network, circuit switching 808
Network, classifying 817
Network, communication 807
Network, comparator 887—888 891 931
Network, cube-connected cycles 863
Network, directed butterfly 952
Network, homogeneous 809
Network, hypercube 863 947
Network, logical 36
Network, merging 816
Network, mesh 864
Network, mesh-of-trees 864 950
Network, packet switching 808
Network, self-routing 808
Network, shifting 815
Network, shuffle-exchange 862 948
Network, sorting 811 887 890—892 894
Network, tree-of-meshes 864
Newton step 639
NEXPSPACE 12
NEXPTIME 12 103
nl 127
NLIN — SPACE 100
NLOGSPACE 12
Node (of a graph) 528
Node cover 581
Noncritical region 406
Nondeterminism 8 761
Nondeterminism, bounded 8
Nondeterminism, unbounded 8
Nondeterministic algorithm 847
Nondeterministic finite automaton 282
Nondeterministic Turing machine (NDTM) 73
Nonuniform circuit family 75
Nonuniform complexity class 75 116
Nonuniform model 35
Nonuniformity 762
Normal form, disjunctive 764
Normal form, Kronecker 658
Normal form, prenex 778
Normal number 193 219
NP 12 83 762
NP-complete 15 84
NP-complete in the strong sense 86
NP-completeness 661
NP-easy 92
NP-equivalent 92
NP-hard 91
NP\poly 763
NSPACE[ ] 98
NTIME[ ] 98
Number of elements (of finite set) 196
Number, normal 193 219
Numerical analysis 664
Oblivious 226
Oblivious transfer 744
Obliviousness 762
Obstacles 394
Obstacles, expanded 410
Obstacles, in general position 411
Obstacles, moving 419
Obstacles, polygonal 397 416
Obstacles, polyhedral 397 416
Obstacles, rectangular 397
Obstruction set 547
Occam’s razor 214
Occupancy distribution 493 517
Odd-even merge 949
Off-line 227
Off-line computation 7
On-line 227
On-line computation 7
One-sided error algorithm 904 923
One-tape Turing machine 223
one-time pad 720
One-way function 112 117 725
One-way input 227
One-way predicate 726
Open addressing 507
Operation (of a switching network) 807
Operation, nonblocking 808
Operation, rearrangeable 808
Optimal algorithm 638
Optimal compression 243
Optimal computation 638 657
Optimal parallel algorithm 874—881 888—890 892-894
Optimal specification method 197
Optimum tree 319
OptP 110
Oracle 74 128 136 241 243 776
Oracle Turing machine (OTM) 74
Oracle, random 82
Oracle-augmented Boolean circuit 136
Orbit variety 658
Order of magnitude symbols 198
Order type 378
Orthogonal query 371
Ostrowski’s conjecture 637
OTM see oracle Turing machine
Output format 647
Output section 7
Output-sensitive algorithm 349
OVERHEAD 13
Overhead factor 3
Overhead, polynomial-time bounded 4 14
P 12 77 762
P-complete 906—907 926
P-equivalent 108
P-printable 242
P-versus — NP question 5 236
Packet route length 958
Packet switching 808 950
Packet-switching network 808
Padding Lemma 169 179
Pairing function 199
Pairing heap 328
Palindromes 223 290
Paradox of asignment 32
Parallel addition 224
Parallel algorithm, efficient 871 873 874—894 920 924
Parallel algorithm, optimal 874—881 888—890 892-894
Parallel communication 950
Parallel comparison model 887—890
Parallel computation thesis 5 905—906
Parallel computation, general purpose 945 959
Parallel computer 945 959
Parallel machine 9 (see also PRAM)
|
|
|
| Реклама |
|
|
|
|
|
О проекте