|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J.V. — Handbook of Theoretical Computer Science: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Cube-connected cycles network 863 948
Cubic sieve algorithm 705
Curve, constraint 398
Curve, elliptic 677 697 708
Curve, hyperelliptic 712
Curve, Jordan 411
Cut see  cut
Cut, capacity of 589
Cutpoint 552
Cutwidth 531
Cycle basis 562
Cycle basis of smallest weight 564
Cycle covering 567
Cycle separator 574
Cycle, edge-disjoint 567
Cycle, Eulerian 565
Cycle, Hamiltonian 567
Cycle, least cost 564
Cycle, length  564
Cycle, length of 563
Cycle, longest 564
Cycle, minimum mean weight 564
Cycle, negative 565
Cycle, odd /even 564
Cycle, shortest 563
Cycle, weighted 564
Cyclic shift 855
Cylindrical algebraic decomposition 401
D-tree 320
Darboux’s method 450
Data Encryption Standard (DES) 721
Data model 433
Data model, dynamic 511
Data structure 301 433
Data structure, comparison-based 305
Data structure, explicit 307
Data structure, hybrid 313
Data structure, maximum size of 499 517
Data structure, representation-based 311
Davenport — Schinzel sequence 377 412 422
DCFL 232 234
de Bruijn graph 948
De Bruijn sequences 235
De Groote — Heintz classification 657
Decision problem 71
Decision problem, algebraic 647
Decision problem, Tarski 401
Decision procedure 636
Decision tree, algebraic 347
Decoding function 198
Decomposable searching problem 332
Decomposition 570
Decomposition of polygon 364
Decomposition, box 357
Decomposition, cell 401
Decomposition, cylindrical algebraic 401
Decomposition, ear 881—882 883—886
Decomposition, LR 650
Decomposition, QR 650
Decomposition, tree 549
Decryption algorithm 719
Deflation 239
Degeneration 653
Degree bound 641
Degree of freedom 394
Degree of transcendency 640
Degree-constrained subgraph 581
Delaunay triangulation 353
Delay (in VLSI theory) 840
DeMorgan basis 787
DeMorgan formula 787
Depth (of a Boolean circuit) 75 760
Depth (of a network) 809
Depth hierarchy 773
Depth, logical 238
Depth-first search (DFS) 538 881—883 924—925 929
Derivative inequality 644
DES see Data Encryption Standard
Descriptive set theory 799
DET 137—138
Determinant 650 872 913—915 922—923
DETERMINANT COMPUTATION 108 138
Determinant, symbolic 922
Determinant, Vandermonde 644
Determinism 761
Deterministic algorithm 846 853
Deterministic coin-tossing 878
Deterministic context-free language (DCFL) 137
Deterministic finite automaton 285
Deterministic machine 8
Deterministic Turing machine (DTM) 18 73
DFA 229
DFS see depth-first search
DFS tree 539
DFT see Discrete Fourier Transform FFT
Diagonal map 653
Diagonalization 167 241 246
Diameter 351 862
Dictionary problem 305
Differentiation 663
Digital search 488 491 502
Digital signature, probabilistic 739
Dijkstra’s algorithm 559
Diophantine equation 208 221
Direct chaining 496
Dirichlet tessellation 352
Discrete Fourier transform (DFT) 660 863 864
Discrete logarithm 111 675 685
Discrete logarithm problem 725
Discriminant 644 681
Disjunctive normal form 764
Distance, edit 290
Distance, Hamming 294
Distance, Levenshtein 294
Distribution sort 496
Distribution, Solomonoff — Levin 210 213
Distribution, universal 210 213
Divide-and-conquer 345
Divide-and-query 346
Division 907 909—911 917
Division algebra 657
Division points method 679 709
Division, complex 658
Division, polynomial with remainder 641
DLOGTIME 140
Double hashing 508
Dovetailing 220
DPDA 229
DPDA theorem 272
DSPACE[ ] 98
DTIME[ ] 98
DTM see deterministic Turing machine
Dual 766
Dynamic data model 511
Dynamic fractional cascading 311
Dynamic hashing 318
Dynamization 351
Dynamization technique 332
Ear decomposition 881—882 883—886
Eavesdropper 719
Edge (of a graph) 528
Edge connectivity 554
Edge cover 581
Edit distance 290
EDITRAM 46
Effective operator 172 (see also computable operator)
Effective speed-up 175
Effectively computable function 193
Efficiency 945 961
Efficient parallel algorithm 871 873 874—894 920 924
| EH 104
Element distinctness function 797
Elementary 105
Elementary symmetric function 641
Elliptic curve 677 697 708
Elliptic curve method 697 698
Elliptic curve smoothness test 698 699
Elliptic curve, addition algorithm see elliptic curve Group
Elliptic curve, group law 678
Elliptic curve, random selection 681 709
Elliptic curve, set of points 680
Embedding, F ry 530
Embedding, planar 529
Encryption algorithm 719
Encryption function, commutative 743
Encryption, multiple 734
Encryption, probabilistic 732
Endgame analysis 41
Energy 839 857
Energy, switching 839 857
entropy 210 647
Enumeration 434 436
Ephemeral structure 323
EPRAM 961
Equivalent complexities 177
Equivalent program codes 168
Equivalent Turing machines 166
EREW PRAM 134
etime 102
Euclidean expansion 646
Euclidean minimum matching 358
Euclidean minimum spanning tree 358
Euclidean travelling salesman 359
Euclid’s algorithm 646
Euler circuit problem 86 108
Euler tour technique 880 882—883
Euler — Maclaurin summation formula 446
Eulerian cycle 565
Eulerian path 565
Evaluation at many points 642
Evaluation of continued fractions 639
Evaluation of polynomials 637
Evaluation of rational functions 639
Evaluation, expression 879—881 906 911—912
Evaluation, polynomial 637
EX PLTIME 15
Exact answer problem 93
Expander 818
Explicit construction 795
Explicit data structure 307
Explicit problem 763
Exponential bound 76
Exponential hierarchy 104
Exponentiation, modular integer 930
Exponentiation, modular polynomial 930
Expression evaluation 879—881 906 911—912
EXPSPACE 12 104
EXPTIME 12 102
Extended regular expression 260
Extendible hashing 318 502
Fry embedding 530
F 92
FA 229
Face (of a planar graph) 529
Face (of a planar graph), exterior 529
Factor (of a graph) 572
Factoring integers 675 697
Factorization 236 237 238
Factorizationof polynomials 636
Failure function 275
Fan-in 76 140 760
Fan-out 76 760
Fast Fourier transform (FFT) 456 949
Feasibility 4
FEEDBACK Vertex Set 564
Fermat’s theorem 706
FewP 113
FFT see Fast Fourier Transform also
Fibonacci heap 328
Fibonacci string 266
Field, algebraically closed 641
Field, complex multiplication 679 709
Field, extension 639
Field, finite 643
Field, infinite 638
File-difference problem 290
Finger search tree 310
Fingerprint 726
Finite abelian group, algorithms 685
Finite abelian group, algorithms for groups with smooth Order 688
Finite abelian group, exponential algorithms 686
Finite abelian group, subexponential algorithms 689
Finite automaton, deterministic 285
Finite automaton, nondeterministic 282
Finite control 6
Finite object 196
Finite-precision geometry 378
First-order definability 778
First-order definability, nonuniform 778
First-order sentence 777
Fixed-point theorem 168
Flow, 589
Flow, maximum 588
Flow, minimum cost 592
Flow, muliicommodity 609
Flow, multiterminal 605
Flow, with lower bounds 602
FNC 131
Folding 865
Forbidden region 396
Ford’s algorithm 558
Forgery, existential 741
Forgery, selective 741
Forgery, universal 741
Formula 760 786
Formula complexity 36 787
Formula, binary 787
Formula, Boolean 760 786
Formula, DeMorgan 787
Formula, monotone 787
Four-connectivity 882 886
Fourier transform, discrete see DFT
Fourier transform, fast see FFT
FP 77
Fractional cascading 311
Fractional cascading, dynamic 311
Frequency interpretation (of probability) 191
FRNC 133—134
Full persistence 323
Function 71
Functional equation 434 444 448 450 473
Fundamental set (of cycles) 562
Fundamental theorem of complexity theory 177 181
FUP 111
G del number 167 (see also program code)
Gdel’s Theorem 214 215
Galois group 649
Gambling system, principle of excluded 192
Game, Arthur — Merlin 122
Games, complexity of 41
Gap theorem 172 183
Gate 760 842
Gate elimination method 764
Gaussian elimination 683
GCD see greatest common divisor
General-purpose architecture 839
General-purpose computer 945 959
Generalized Kolmogorov complexity 239—241
Generalized Voronoi diagram 409
Generalizer 812
|
|
|
| Реклама |
|
|
|
|
|
О проекте