|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J.V. — Handbook of Theoretical Computer Science: Algorithms and Complexity |
|
|
|
| Предметный указатель |
Parallel machine,  — PRAM 52
Parallel machine, LPRAM 57
Parallel machine, MIMD — RAM 55
Parallel machine, parallel Turing 54
Parallel machine, SIMDAG 50
Parallel machine, WRAM 58
Parallel prefix operation 965
Parallel random-access machine (see also PRAM) 75 129 134 871 873
Parallel Turing machine 54
Parallelism 5
Parallelism, recursive 52
Parallelism, true 49
Parameter theorem (see  Theorem) 179
Parity 141 231
Parity function 772
Parity Turing machine (®TM) 110
Parsimonious reduction 16
Parsimonious transformation 107
Partial -tree 549
Partial fraction 639
Partial persistence 323
Partial recursive function 197 207
Partial recursive function, universal 198 210
Partition 86
Partition of a point set 372
Partition of a polygon 364
Password 726
Path compression 325
Path covering number 572
Path length 474
Path searching 396
Path, alternating 582
Path, augmenting 589
Path, collision-free 393
Path, disjoint connecting 561 562
Path, Eulerian 565
Path, Hamiltonian 567
Path, longest 561
Path, of length 561
Path, shortest 415 557 919
Patricia trie 290 491
Pattern matching 230 232 480
Pay-off function 211
PDA see pushdown automaton
Perfect hash function 30
Perfect hashing 288 318
Perfect matching 108 133 134 580
Period 840
Period (of a string) 272
Permanent 108
PERMANENT COMPUTATION 107—108 144
Permutation 442 459 855
Permutation group 636
Permutation, partial 950
Permutation, pseudo-random 738
Persistence, full 323
Persistence, partial 323
Persistent structure 323
Ph see polynomial hierarchy
Piano mover’s problem 406
Pigeon Hole Principle 848
Pipelining 840 865
Pl cker coordinates 346
placement 395
Placement, forbidden 396
Placement, free 396
Placement, semifree 410
Plaintext 719
Planar embedding 529 530
Planar graph 529
Planar point location 366
Planar Separator Theorem 574
Planarity 886 920 924
Planarity testing 529
Planarization 531
Plane graph 529
Planning, grasp 421
Planning, motion (see also motion planning) 393
Planning, task 420
Pocklington’s theorem 707
Point location, planar 366
Pointer jumping 876 882
Pointer machine 32 303
Pollard’s  method 697
Pollard’s rho method 687
Poly log 873 886 892
Polygon containment 423
Polygon, simple 415 416
POLYLOG — SPACE 125
Polylogarithmic bound 76
Polynomial 401
Polynomial bound 76
Polynomial division with remainder 641
Polynomial evaluation 637
Polynomial factorization 636
Polynomial hierarchy (PH) 96 109
Polynomial ideal 636
Polynomial multiplication 641
Polynomial sequence, complete P-definable 663
Polynomial sequence, P-bounded 662
Polynomial sequence, P-computable 662
Polynomial sequence, P-definable 662
Polynomial transformation 78
Polynomial-time hierarchy 762
Polynomial-time isomorphism 87
Polynomial-time reduction 15
Polynomial-time simulation 13 14
Polynomial-time solvable problems (P) 77
Polynomial-time transformation 78
Polynomial-time Turing reduction 79
Port 842
Position tree 290
Post-office problem 352
Postman problem, Chinese 566
Postman’s walk 566
Postman’s walk, minimum weight 567
Potency 237 240
Potential 237—238 240
Power sum 644
Powering 909—910 920 930
PP 119
PPSPACE 121
PR-completeness 246—247
PR-reducibility 246—247
PRAM (see also parallel random-access machine) 224 871 873
PRAM, ARBITRARY CRCW 873 877 882 886
PRAM, COMMON CRCW 873 894—896
PRAM, comparison 888 989
PRAM, concurrent-read concurrent-write 960
PRAM, CRCW 872 873
PRAM, CREW 872 873
PRAM, EREW 872 873
PRAM, exclusive-read exclusive-write 960
PRAM, ideal 895—897 900
PRAM, priority 224 230
PRAM, PRIORITY CRCW 873 894—897 900
Prefix code 202 212 222
Prefix sums 875—881 885 907—908 931
Prefixer 814
Prefixsquares$ 290
Preflow 599
Prenex normal form 778
Preparation of coefficients 640
Primality testing 675 706 723
Primality testing using elliptic curves 708
Prime form 683 702
Prime number 88 90 114—115
Prime number theorem 221—222
Prime number, probable 706 707
Principle of excluded gambling system 192
| Printed circuit board 837
Priority PRAM 224 230
Priority queue 326 471 487
Priority search tree 369
Privacy 719 728
Probabilistic algorithm 554
Probabilistic algorithm, Las Vegas 554
Probabilistic algorithm, Monte Carlo 554
Probabilistic analysis 518
Probabilistic argument 235 767
Probabilistic circuit 773
Probabilistic compositeness test 706
Probabilistic digital signature 741
Probabilistic encryption 732
Probabilistic public-key cryptosystem 730
Probabilistic Turing machine 9 74 119
probability 211—213
Probability density, regular 313
Probability density, smooth 313
Probability, a priori 210 213
Probability, computable 213
Probability, universal (a priori) 210
Probable prime 706 707
Problem 69 70
Problem, answer 69 70
Problem, counting 71
Problem, criticality 93
Problem, decision 71
Problem, exact answer 93
Problem, instance 69
Problem, promise 118
Problem, uniqueness 93
Processing element 838
Processor 7
Processor allocation 874—875 880 890
PROGRAM 6 23 198
Program codes, equivalent 168
Program size 165 171
Program, (in network context) 810
Program, code 167
Program, straight-line 635
Programming language 7
Programming system 178
Projection 663 780
Projection, monotone 780
Promise Problem 118
Proof, zero-knowledge 744
Prospective space complexity 177
Protocol, cryptographic 723
Protocol, multi-party 746
Protocol, ping-pong 747
Protocol, two-party 742
Protocol, zero-knowledge 744
Pseudo-random bit sequence 736
Pseudo-random function generator 738
Pseudo-random number generator 240
Pseudo-random permutation 738
Pseudo-random sequence generator 736
Pseudopolynomial-time 85
PSPACE 12 98—101 121 143—144 240
PSPACE-complete 15
Public-key cryptosystem 729
Pumping lemma 233
Pushdown automaton (PDA) 229
Pushdown store 226
P\poly 116 763
QBF see QUANTIFIED BOOLEAN FORMULAS
QH see query hierarchy
QR-decomposition 650
Quad tree 486
Quadratic form 639 681
Quadratic form, binary 681
Quadratic residuousity problem 724
Quadratic sieve algorithm 697 703
Quadratic sieve algorithm, multiple polynomial Variation 697 704
QUANTIFIED BOOLEAN FORMULAS (QBF) 40 96 99
Quantifier elimination 636
Query, half-space 371
Query, hierarchy (QH) 94
Query, orthogonal 371
Query, range 370
QUEUE 227
Queueing discipline 956
Quicksort 470 484
R 113
Radix-exchange sort 470 491
RAM see random-access machine
RAM program 23
Ramsey theorem 224 230 771
Ramsey theory 897
Random bit sequence 735
Random curve test 709
Random finite string 201 214
Random infinite string 205—206 220 221
Random mate 877
Random oracle 82
Random reduction 246
Random restriction 767 792
Random sampling 347
Random squares algorithm 700
Random Turing machine (RTM) 74 113
Random-access machine (RAM) 4 23 75 303
Random-access machine (RAM), BRAM 25
Random-access machine (RAM), MBRAM 24
Random-access machine (RAM), MRAM 24
Random-access machine (RAM), real 348
Random-access machine (RAM), SBRAM 25
Random-access machine (RAM), SRAM 24
Random-access Turing machine 139
Randomization 847
Randomized algorithm 233 535 570
Randomized routing 951
Randomness 190 201
Randomness deficiency 213
Range query 370
Range search 370
Range tree 370
Rank 650 849
Rank, asymptotic 652
Rank, Boolean matrix 225
Rank, border 651
Rank, of matrix 872 915
Rank, typical 658
ranking 246
Ranking function 242 246
Reachability 403
Read/write head 17
Real-time 226
Realizable space complexity 177
Reciprocal 909—910
Recognition 227 228
Recognition of graphs 545
Recognition, language 227 228
Recognized language 8
Recursion 168
Recursion theorem 168 179
Recursion, mutual 168
Recursive convergence 206
Recursive function 193 197 207
Recursive real 219
Recursive set 204
Recursive — Relatedness Theorem 181
Recursively enumerable set 202 233
Red-black tree 309
Reduced form 681
Reducibility, PR 246—247
Reduction 15 78—79
Reduction,  112
Reduction,  136
Reduction,  90 117
|
|
|
| Реклама |
|
|
|
|
|
О проекте