|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Leeuwen J. (ed.), Meyer A.R., Nivat M. — Algorithms and Complexity, Volume A |
|
|
|
| Предметный указатель |
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 75 (see
Parallel Turing machine 54
Parallelism 5
Parallelism, recursive 52
Parallelism, true 49
Parameter Theorem 179; see  Theorem
Parity 141
Parity function 772
Parity Turing machine ( ) 110
Parsimonious reduction 16
Parsimonious transformation 107
Partial  -tree 549
Partial fraction 639
Partial persistence 323
Partial recursive function 197
Partial recursive function, universal 198
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
Path, Eulerian 565
Path, Hamiltonian 567
Path, longest 561
Path, of length 561
Path, shortest 415
Patricia trie 290
Pattern matching 230
Pay-off function 211
PDA see Pushdown automaton
Perfect hash function 30
Perfect hashing 288
Perfect matching 108
Period 840
Period (of a string) 272
Permanent 108
PERMANENT COMPUTATION 107—108 144
Permutation 442
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
Pl cker coordinates 346
placement 395
Placement, forbidden 396
Placement, free 396
Placement, semifree 410
Plaintext 719
Planar embedding 529 (see
Planar graph 529
Planar point location 366
Planar Separator Theorem 574
Planarity 886
Planarity testing 529
Planarization 531
Plane graph 529
Planning, grasp 421
Planning, motion 393 (see also Motion planning)
Planning, task 420
Pocklington’s theorem 707
Point location, planar 366
Pointer jumping 876
Pointer machine 32
Pollard’s  method 697
Pollard’s rho method 687
Polygon containment 423
Polygon, simple 415
PolyLog 873
POLYLOG-SPACE 125
Polylogarithmic bound 76
Polynomial 401
Polynomial bound 76
Polynomial division with remainder 641
Polynomial evaluation 637
Polynomial factorization 636
Polynomial factorization, Berlekamp’s 636
Polynomial factorization, Kaltofen’s 636
Polynomial factorization, Lenstra — Lenstra-Lov sz’ 636
Polynomial hierarchy (PH) 96
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
Potential 237—238
Power sum 644
Powering 909—910
PP 119
PPSPACE 121
PR-completeness 246—247
PR-reducibility 246—247
PRAM 224 (see
PRAM, ARBITRARY CRCW 873
PRAM, COMMON CRCW 873
PRAM, comparison 888
PRAM, concurrent-read concurrent-write 960
PRAM, CRCW 872
PRAM, CREW 872
PRAM, EREW 872
PRAM, exclusive-read exclusive-write 960
PRAM, ideal 895—897
PRAM, priority 224
Prefix code 202
Prefix sums 875—881
Prefixer 814
Preflow 599
Prenex normal form 778
Preparation of coefficients 640
Primality testing 675
Primality testing using elliptic curves 708
Prime form 683
Prime number 88 90
Prime number theorem 221—222
Prime number, probable 706
Principle of excluded gambling system 192
| Printed circuit board 837
PRIORITY CRCW 873
Priority PRAM 224
Priority queue 326
Priority search tree 369
Privacy 719
Probabilistic algorithm 554
Probabilistic algorithm, Las Vegas 554
Probabilistic algorithm, Monte Carlo 554
Probabilistic analysis 518
Probabilistic argument 235
Probabilistic circuit 773
Probabilistic compositeness test 706
Probabilistic digital signature 741
Probabilistic encryption 732
Probabilistic public-key cryptosystem 730
Probabilistic Turing machine 9 74
probability 211—213
Probability density, regular 313
Probability density, smooth 313
Probability, a priori 210
Probability, computable 213
Probability, universal (a priori) 210
Probable prime 706
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
PROGRAM 6 23
Program code 167
Program codes, equivalent 168
Program size 165
Program, (in network context) 810
Program, straight-line 635
Programming language 7
Programming system 178
Projection 663
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
PSPACE-complete 15
Public-key cryptosystem 729
Pumping lemma 233
Pushdown automaton (PDA) 229
Pushdown store 226
P\poly 116
QBF see QUANTIFIED BOOLEAN FORMULAS
QH see Query hierarchy
QR-decomposition 650
Quad tree 486
Quadratic form 639
Quadratic form, binary 681
Quadratic residuousity problem 724
Quadratic sieve algorithm 697
Quadratic sieve algorithm, multiple polynomial Variation 697
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
R 113
Radix-exchange sort 470
RAM see Random-access machine
RAM program 23
Ramsey theorem 224
Ramsey theory 897
Random bit sequence 735
Random curve test 709
Random finite string 201
Random infinite string 205—206
Random mate 877
Random oracle 82
Random reduction 246
Random restriction 767
Random sampling 347
Random squares algorithm 700
Random Turing machine (RTM) 74
Random-access machine (RAM) 4 23 75
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
Randomized routing 951
Randomness 190
Randomness deficiency 213
Range query 370
Range search 370
Range tree 370
Rank 650
Rank, asymptotic 652
Rank, Boolean matrix 225
Rank, border 651
Rank, of matrix 872
Rank, typical 658
ranking 246
Ranking function 242
Reachability 403
Read/write head 17
Real-time 226
Realizable space complexity 177
Reciprocal 909—910
Recognition 227 (see
Recognition of graphs 545
Recognition, language 227
Recognized language 8
Recursion 168
Recursion theorem 168
Recursion, mutual 168
Recursive convergence 206
Recursive function 193
Recursive real 219
Recursive set 204
Recursive — Relatedness Theorem 181
Recursively enumerable set 202 (see
Red-black tree 309
Reduced form 681
Reducibility, PR- 246—247
Reduction 15 78—79
Reduction,  772
Reduction,  136
|
|
|
| Реклама |
|
|
|
|
|
О проекте