|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J. (ed.), Meyer A.R., Nivat M. — Algorithms and Complexity, Volume A |
|
|
|
| Предметный указатель |
Generating function (GF) 434
Generating function (GF), exponential (EGF) 437
Generating function (GF), ordinary (OGF) 437
Generic computation 648
Geometric degree 641
Geometric transformation 346
Geometry, combinatorial 376
Geometry, computational 345
Geometry, finite-precision 378
Gold inference 216 (see also Identification by enumeration)
Goldberg — Tarjan algorithm (for maximum flows) 599
Gomory — Hu algorithm 606
Gr bner basis 636
Graph 528
GRAPH ACCESSIBILITY 128—129
Graph algorithm 532
Graph algorithm, (parallel) 881—886
Graph automorphism 577
Graph exploration 538
Graph isomorphism 69
Graph isomorphism testing 576
Graph layout 574
Graph problem (in VLSI theory) 864
Graph property, bipartite 535
Graph property, elusive 534
Graph property, evasive 534
Graph property, monotone 534
Graph property, nontrivial 534
GRAPH RELIABILITY 108
GRAPH RELIABILITY, dynamic 122
Graph theory 532
Graph,  -free 546
Graph, acyclic (directed) 538
Graph, bipartite 546
Graph, bounded genus 546
Graph, bounded treewidth 549
Graph, chordal 546
Graph, circle 546
Graph, circular arc 546
Graph, claw-free 546
Graph, comparability 546
Graph, connectivity 396
Graph, de Bruijn 948
Graph, directed 528
Graph, directed path 546
Graph, drawing 528
Graph, expander 948
Graph, generating a 544
Graph, grid 546
Graph, Halin 546
Graph, Hamiltonian 568
Graph, hierarchically defined 537
Graph, interval 537
Graph, line 546
Graph, minimum equivalent 540
Graph, outerplanar 546
Graph, perfect 546
Graph, permutation 546
Graph, planar 529
Graph, series parallel 546
Graph, split 546
Graph, strongly chordal 546
Graph, undirected 528
Graph, undirected path 546
Graph, visibility 376
Grasp planning 421
greatest common divisor (GCD) 920
Group algebra 657
Group, abelian 685
Group, class 681 (see
Group, cyclic 661
Group, dihedral 657
Group, finite abelian 85
Group, Galois 649
Group, linear algebraic 657
Group, metabelian 661
Group, permutation 636
Group, solvable 661
Group, symmetric 661
Group, transitive 855
Half-balanced tree 309
Half-space query 371
Halting probability  220
HAMILTONIAN CIRCUIT enumeration 107
Hamiltonian completion number 568
Hamiltonian cycle 86
Hamiltonian excess 568
Hamiltonian path 567
Hamiltonian walk 568
Hamming distance 294
hard 15
Hardness (for a class) 80
Harrison — Ibarra conjecture 229
Hash function 30
Hash function, perfect 30
Hash table 315
Hashing 315
Hashing, coalesced 504
Hashing, direct chaining 496
Hashing, double 508
Hashing, dynamic 318
Hashing, extendible 318
Hashing, linear probing 509
Hashing, maximum bucket occupancy 499
Hashing, open addressing 507
Hashing, perfect 288
Hashing, separate chaining 493
Hashing, universal 317
Hashing, virtual 318
Hashing, with lazy deletion 514
Hastad switching lemma 767
hB-tree 309
Head, read/write 17
Heap 328
Heap, Fibonacci 328
Heap, pairing 328
Heap, relaxed 328
Heap-ordered tree 327
Heapsort 471
Hennie — Stearns simulation 19
Hessenberg form 650
Hidden-surface removal 375
Hierarchy, Chomsky 233
Hierarchy, complexity 167
Hierarchy, depth 773
Hierarchy, log-time 111
Hierarchy, Meyer — Stockmeyer 664
Hierarchy, polynomial-time 762
history 843
History method 20
History model 512
Honest resource bound 184
Honesty theorem 184
Horner’s rule 637
Horspool’s algorithm 271
Hungarian method (for the assignment problem) 586
Hunt — Szymanski algorithm 292
Hybrid data structure 313
Hypercube network 863
Hyperelliptic curve 712
Hypothesis, Cook’s 661
Hypothesis, Valiant’s 663
Ideal method 648
Immanent 664
Implicit data structure 306
Incompressible strings 200
Independence results 88—89
INDEX 685
Index-calculus algorithm 690
Indirect addressing 23
| Induced circuit 767
Induced function 767
Inductive 214
Inductive inference 214
Inequality, Baur — Strassen 644
Inequality, Chebychev’s 212
Inequality, derivative 644
Inequality, Kraft 212
Inference, Gold 216
Inflation 239
Initialization of memory 24
Input section 7
Insertion sort 461
Instruction 7
Instruction, arithmetic 23
Instruction, bitwise Boolean 24
Instruction, branching 645
Instruction, conditional jump 23
Instruction, flow of control 23
INTEGER EXPRESSION INEQUIVALENCE 97
Integral flow theorem 590.593
Integrated cost 513
Integration 663
Interactive proof system 124
Interconnection network 9
Interpolation 642
Interpolation search 312
Interpolation theorem, Stoss’ 644
Interpretation (of the Invariance Thesis), liberal 5
Interpretation (of the Invariance Thesis), orthodox 5
Interpreter function 198
Intersection detection 421
Intersection detection, among disks 421
Intersection detection, among spheres 421
Intersection detection, red-blue 421
Intersection of convex polygons and polyhedra 351
Intersection of line segments 374
Invariance (of computational complexity) 5
Invariance Theorem 198
Invariance Thesis 5
Inverse Ackermann’s function 423
inversion 459
Inverted files 290
IP 124
Irreducible kernel 540
Isomorphism, conjecture 87—88
Isomorphism, graph 69
Isomorphism, polynomial-time 87
Isomorphism, testing (of graphs) 574
Isomorphism, theorem 179
Isomorphism, Wedderburn 661
Iterated product 909—910
Iteration procedure 643
Iteration theorem 79
Jacobi sum test 707
Jordan arc 412
Jordan curve 411
Jordan-sorting 365
Knig-Egervary theorem 581
Karp — Rabin algorithm 263
Key (in cryptography) 719
Key exchange, exponential 728
Kleene closure 259
Knapsack problem 647
Knuth — Morris — Pratt algorithm 264
Knuth — Schnhage algorithm 647
Kollektiv 192
Kolmogorov complexity 198
Kolmogorov complexity, conditional 198
Kolmogorov complexity, generalized 239—241
Kolmogorov complexity, resource-bounded 236—241
Kolmogorov complexity, space-bounded 240
Kolmogorov complexity, time-bounded 208
Kolmogorov complexity, unconditional 198
Kraft inequality 212
Kronecker normal form 658
Kuratowski’s Theorem 529
Labeled combinatorial structure 441
Lagrange — Burmann inversion 444
Lambda method 688
Language 71
Language compression 242—246
Language recognition 227
Language, accepted 8
Language, complementary 71
Language, context-free 137
Language, context-sensitive 100—101
Language, deterministic context-free 137
Language, recognized 8
Language, regular 143
Language, sparse 87
Language, universal 16
Laplace transform 456
Laplace’s method 447
Largest empty circle 359
Las Vegas algorithm 115
Las Vegas communication complexity 848
Laser method 656
Law of Information Conservation 233
layout 842
Learnability 218—219
Learning model, Valiant’s 218—219
Leftist tree 328
Length (of a string) 196
Leveling Theorem 177
Levenshtein distance 294
Limit distribution 455
Limit-computable 171
LIN-SPACE 100
Linear arrangement problem 531
Linear arrangement problem, min-cut 531
Linear bounded automaton 100
Linear disjointness 641
Linear probing 509
Linear programming 78
Linear programming, two-variable 930
Linear separability 363
Linear sieve algorithm 694
Linear system 653
Linkage 404
links 404
List ranking 876—879
Literal 763
Load factor 495
Locus approach 346
LOG -SPACE 126
Log-space transformation 79
Log-space uniformity 130
Log-time hierarchy 111
Logarithmic time measure 24
LOGCFL 137
LOGDCFL 137
Logical depth 238
logspace 12
Logspace reduction 15
Longest-common-subsequence problem 292
Low set, exponentially 241
Lower bound 635
Lower envelope 424
Lower envelope, breakpoints in 424
Lower envelope, of segments 424
Lower envelope, of triangles 424
LR-decomposition 650
MA 123
Machine architecture 838
Machine class 6
Machine class, first 6
Machine class, second 6
Machine independence 165
Machine model 6 73—75
|
|
|
| Реклама |
|
|
|
|
|
О проекте