|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J. (ed.), Meyer A.R., Nivat M. — Algorithms and Complexity, Volume A |
|
|
|
| Предметный указатель |
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
Machine, PRAM 58
Machine, probabilistic 9
Machine, random-access 4 23
Machine, random-access stored-program 24
Machine, reasonable 4
Machine, reference 198
Machine, register 22
Machine, sequential 9
Machine, shared-memory 869
Machine, SIMDAG 50
Machine, storage modification 32
Machine, Turing 4 17
Machine, universal 198
Machine, vector 45
Machine, WRAM 58
Machine-based complexity 181
machine-dependent 5
Machine-independent 5
Machine-independent complexity theory 163
majority 15
Majority function 141
manual 843
Many-one reduction 15
Marriage problem 662
Martingale 211
Master reduction 16
Matching (in graphs, parallel) 872
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
Matching, perfect 108
Matrix inversion 923
Matrix multiplication 650
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
Maximal independent set 872 927—928
Maximum cardinality matching 580
maximum distance 360
Maximum finding 888—890
Maximum flow (parallel) 924
Maximum flow algorithm 593
Maximum flow problem 588
Maximum matching 580
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
Mellin transform 453
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
Merge, odd-even 949
Merger 816
Merging 331
Merging network 816
Merging, two-way 331
Meromorphic function 450
Mesh network 864
Mesh-of-trees network 864
Message digest 726
Metacharacter 259
Meyer — Stockmeyer hierarchy 664
Min-flow max-cut theorem 592
Minimum cost flow problem 592
Minimum cost flow theorem 592
Minimum Description Length Principle (MLDP) 217
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
Module 650
Moment generating function 456
Monotone basis 787
Monotone circuit 773
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
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
Motion planning, for a disk 408
Motion planning, for a ladder 397
Motion planning, in the presence of obstacles 419
Motion planning, kinodynamic 420
Motion planning, lower bounds 404
Motion planning, optimal 395
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
Multidimensional Turing machine 18
Multihead  -dimensional machine 228
Multihead tree machine 228
Multihead Turing machine 228
Multiple polynomials 697
Multiplication 905
| Multiplication (in VLSI theory) 865
Multiplication of matrices 650 (see
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
NC-reduction 132
NDTM see Nondeterministic Turing machine
Nearest common ancestor 328
Nearest neighbor 356
NETIME 103
Network 36
Network (for sorting) 467
Network flow see Flow
Network topology 862
Network, binary  -dimensional cube 947
Network, butterfly 863
Network, circuit switching 808
Network, classifying 817
Network, communication 807
Network, comparator 887—888
Network, cube-connected cycles 863
Network, directed butterfly 952
Network, homogeneous 809
Network, hypercube 863
Network, logical 36
Network, merging 816
Network, mesh 864
Network, mesh-of-trees 864
Network, packet switching 808
Network, self-routing 808
Network, shifting 815
Network, shuffle-exchange 862
Network, sorting 811
Network, tree-of-meshes 864
Newton step 639
NEXPSPACE 12
NEXPTIME 12
nl 127
NLIN-SPACE 100
NLOGSPACE 12
Node (of a graph) 528
Node cover 581
Noncritical region 406
Nondeterminism 8
Nondeterminism, bounded 8
Nondeterminism, unbounded 8
Nondeterministic algorithm 847
Nondeterministic finite automaton 282
Nondeterministic Turing machine (NDTM) 73
Nonuniform 778
Nonuniform circuit family 75
Nonuniform complexity class 75
Nonuniform model 35
Nonuniformity 762
Normal form, disjunctive 764
Normal form, Kronecker 658
Normal form, prenex 778
Normal number 193
NP 12 83
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
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
Obstacles, polyhedral 397
Obstacles, rectangular 397
Obstruction set 547
Occam’s razor 214
Occupancy distribution 493
Odd-even merge 949
Off-line 227
Off-line computation 7
On-line 227
On-line computation 7
One-sided error algorithm 904
One-tape Turing machine 223
one-time pad 720
One-way function 112
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
Optimal parallel algorithm 874—881 892—894
Optimal specification method 197
Optimum tree 319
OptP 110
Oracle 74
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
P-complete 906—907
P-printable 242
P-versus-NP question 5
Packet route length 958
Packet switching 808
Packet-switching network 808
Padding Lemma 169
Pairing function 199
Pairing heap 328
Palindromes 223
Paradox of asignment 32
Parallel addition 224
Parallel algorithm, efficient 871
Parallel algorithm, optimal 874—881
Parallel communication 950
Parallel comparison model 887—890
Parallel computation thesis 5
Parallel computation, general purpose 945
Parallel computer 945
Parallel machine 9 (see also PRAM)
Parallel machine,  -PRAM 52
|
|
|
| Реклама |
|
|
|
|
|
О проекте