|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J.V. — Handbook of Theoretical Computer Science: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Generating function (GF) 434 436
Generating function (GF), exponential (EGF) 437 441
Generating function (GF), ordinary (OGF) 437 438
Generic computation 648
Geometric degree 641
Geometric transformation 346
Geometry, combinatorial 376
Geometry, computational 345 393
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 893 917—920 922-925
Graph automorphism 577
Graph exploration 538
Graph isomorphism 69 88 124
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 402
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 416
Grasp planning 421
greatest common divisor (GCD) 920 930
Group algebra 657 661
Group, abelian 685 697
Group, class 681 692 697 702
Group, cyclic 661
Group, dihedral 657
Group, finite abelian 685 (see also finite abelian group)
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 239
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 315 493 962
Hash function, perfect 30
Hash table 315
Hashing 315 492 514
Hashing, coalesced 504
Hashing, direct chaining 496
Hashing, double 508
Hashing, dynamic 318
Hashing, extendible 318 502
Hashing, linear probing 509
Hashing, maximum bucket occupancy 499 517
Hashing, open addressing 507
Hashing, perfect 288 318
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 471 487 512
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 777
Hierarchy, Meyer — Stockmeyer 664
Hierarchy, polynomial-time 762
history 843
History method 20
History model 512 516
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 947
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 701
Indirect addressing 23
| Induced circuit 767
Induced function 767 789
Inductive inference 214 215—218
Inequality, Baur — Strassen 644
Inequality, Chebychev’s 212
Inequality, derivative 644
Inequality, Kraft 212
Inference, Gold 216
Inference, inductive 214 215—218
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 498
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 143—144
Irreducible kernel 540
Isomorphism, conjecture 87—88
Isomorphism, graph 69 124
Isomorphism, polynomial-time 87
Isomorphism, testing (of graphs) 574
Isomorphism, theorem 179
Isomorphism, Wedderburn 661
Iterated product 909—910
Iteration procedure 643
Iteration theorem 179 (see also  Theorem)
Jacobi sum test 707
Jordan arc 412
Jordan curve 411
Jordan-sorting 365
Knig — Egervary theorem 581
Kaltofen’s 636
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 241 242
Kolmogorov complexity, time-bounded 208 236 239 242
Kolmogorov complexity, unconditional 198
Kraft inequality 212
Kronecker normal form 658
Kuratowski’s Theorem 529
Labeled combinatorial structure 441
Lagrange — Biirmann inversion 444 476 510
Lambda method 688
Language 71 761
Language compression 242—246
Language recognition 227 228
Language, accepted 8
Language, complementary 71
Language, context-free 137 233 235
Language, context-sensitive 100—101 233 235
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 847 904
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
Lenstra — Lenstra- Lov sz 636
Leveling Theorem 177
Levenshtein distance 294
Limit distribution 455 489
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 658
Linkage 404
links 404
List ranking 876—879 881 893 931
Literal 763
Load factor 495 504
Locus approach 346
Log-space transformation 79
Log-space uniformity 130
Log-time hierarchy 777
Logarithmic time measure 24
LOGCFL 137
LOGDCFL 137
Logical depth 238
logspace 12
Logspace reduction 15 926—927
Longest-common-subsequence problem 292
Low set, exponentially 241
Lower bound 635 759 886 888 894 895—897 900—901
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 178
|
|
|
| Реклама |
|
|
|
|
|
О проекте