Авторизация
Поиск по указателям
Li M., Vitanyi P. — An introduction to Kolmogorov complexity and its applications
Обсудите книгу на научном форуме Нашли опечатку?
Название: An introduction to Kolmogorov complexity and its applicationsАвторы: Li M., Vitanyi P. Аннотация: Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in computer science, mathematics, cognitive sciences, philosophy, artificial intelligence, statistics, and physics. It is self-contained in that it contains the basic requirements from mathematics and computer science. Included are also numerous problem sets, comments, source references, and hints to solutions of problems, as well as a great deal of new material not included in the first edition.
Язык: Рубрика: Математика /Серия: Посвящена 110-летию со дня рождения Колмогорова Андрея Николаевича Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Издание: second editionГод издания: 1997Количество страниц: 637Добавлена в каталог: 10.12.2005Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Penrose, R. 198 202 Pepys, S. 23 Perennes, S. 410 411 Permutation 8 Perpetuum mobile, of the first kind 554 Perpetuum mobile, of the second kind 554 Peter, R. 45 Peterson, G. 519 Petri, N.V. 178 472 Phase space 559 Pierce, J.R. 586 Pippenger, N. 393 395 444 453 Pitt, L. 350 Place-selection rule 87 153 Place-selection rule, according to Kolmogorov 56 Place-selection rule, according to Kolmogorov — Loveland 149 Place-selection rule, according to Mises — Wald — Church 53 149 154 Place-selection rule, according to von Mises 51 149 Place-selection rule, finite-state 58 Place-selection rule, total recursive function 154 Place-selection rule, Turing machine 166 Polynomial complexity core 497 Polynomial hierarchy 40 494 Polynomial Turing reduction see “Reducibility polynomial Popper, K. 319 323 Post's Problem 44 Post, E.L. 41 43 44 86 169 Pour-El, M.B. 86 Pratt, V. 177 Predicate 29 461 Prediction error 5 55 59 327 328 331 333 373 Prediction error, expected using M 304 Price, R. 372 Principle, excluded gambling system 52 Principle, indifference 62 316 Principle, insufficient reason 316 Principle, maximum entropy 370 370—372 377 Principle, maximum likelihood 369 377 Principle, minimum description length, vi 90 115 351 351—369 371 376 377 589 Principle, minimum message length 375 Principle, multiple explanations 315 317 Principle, pigeon-hole 379 Principle, simplicity 62 Probabilistic communication complexity 396 Probabilistic method 379 388 390—392 Probability theory 18—23 86 Probability, a priori see “Probability prior” Probability, algorithmic 252 253 Probability, conditional 19 69 Probability, inferred see “Probability posterior” Probability, inverse 59 Probability, joint 68 Probability, posterior 20 59 63 64 321 322 Probability, prior 20 59 63 319 321 322 325 333 370—372 Probability, prior continuous 276—280 Probability, uniform 268 Probability, universal prior 62 63 87 90 185 190 237 252 253 255 262 275 280 308—311 319 335 511 Program-size complexity see “Complexity” QUEUE 439 Quicksort 268 Quinlan, J.R. 368 376 ra-cell 570 Rabin, M.O. 118 452 455 Rado, T. 45 Ragde, P. 447 453 Ramsey number 392 Random variable 22 Random variable, (in)dependent 22 Random variable, continuous 22 Random variable, discrete 22 Randomness deficiency 103 113 112—115 118 119 130 132 185 210 259 267 294 304 305 331 386—388 397 Ratner, M. 88 Razborov, A. 456 Recursion theory see “Computability theory” Recursively uniform limit 122 Reducibility, many-to-one 43 169 177 495 Reducibility, one-to-one 43 Reducibility, polynomial many-to-one 38 493 518 Reducibility, polynomial truth-table 495 Reducibility, polynomial Turing 38 492 Reducibility, self 499 Reducibility, truth-table 495 Reducibility, Turing 43 169 175 176 495 Reducibility, weak truth-table 176 Regan, K.W. 310 457 518 520 Regular language 421 Reisch, S. 396 452 Reischuk, R. 310 442 443 455 509 520 Relation, binary 7 Relation, encoding 71 Relation, n-ary 7 Relative frequency stabilization 135 Renyi, A. 392 453 Resource-bounded Kolmogorov complexity 459—520 Reversible, ballistic computer 531—533 586 Reversible, Boolean gate 530 536 587 Reversible, circuit 530—531 586 Reversible, computation 528—537 586 Reversible, Turing machine 533—537 586 Reznikova, Zh.I. 589 Richards, J.I. 86 Riemann's hypothesis 218 Rissanen, J.J. 82 83 89 351 361 362 375—377 Rivest, R. 350 368 374 376 430 Robinson, R.M. 45 Rockford Research 309 Rogers, H., Jr. 41—44 46 47 86 104 Rosenberg, A. 430 Routing in networks 404—411 Routing table 405 Rozenberg, G. 420 Rubinstein, R. 517 Rudich, S. 486 Ruelle, D. 589 Run of zeros 110 Russell, B. 170 317 Russo, D. 517 Ryabko, B.Ya. 589 Sakoda, W.J. 431 Sample space 5 18 Sample space, continuous 18 20 Sample space, discrete 18 Sankoff, D. 420 SAT 39 486 489 490 492 493 497 498 500 503 Satisfiable 39 Savitch, W.J. 494 Schack, R. 527 586 589 Schaffer, R. 454 Schay, G 453 Schindelhauer, C. 310 509 520 Schmidhuber, J. 519 Schmidt-Goettsch, K. 46 Schnitger, G. 396 440 442 452 Schnorr's Thesis 156 Schnorr, C.P. 58 108 154—156 187 197 212 222 238 311—313 Schoning, U. 499 501 502 518 519 Schumacher, J. 588 Sedgewick, R. 448 454 Seiferas, J.I. 430 442 443 452 453 455 Semenov, A.L. 150 187 238 Semimeasure 244 242—245 308 311 Semimeasure, conditional 326 Semimeasure, discrete 245 245—268 Semimeasure, enumerable 244 Semimeasure, enumerable continuous 272—280 305 Semimeasure, enumerable discrete 245—268 Semimeasure, extension- 302 Semimeasure, maximal see “Semimeasure universal” Semimeasure, maximal enumerable see “Semimeasure universal Semimeasure, normalization of 280 300 301 310 311 Semimeasure, recursive 244 Semimeasure, recursive continuous 304 Semimeasure, relative enumerable 268 Semimeasure, Solomonoff normalization of 280 300 328 Semimeasure, universal 246 272 Semimeasure, universal enumerable 237 300 310 311 Semimeasure, universal enumerable conditional 255 Semimeasure, universal enumerable continuous 272 272—276 280 301 303 Semimeasure, universal enumerable discrete 247 248 253 255 265 353 Semimeasure, universal relative enumerable 268 Sequence, 216 221 221 Sequence, see “Sequence normal” Sequence, see “Sequence random” Sequence, 156 Sequence, Bernoulli 59 135 155 331 Sequence, Champernowne's 53 58 87 158 Sequence, DNA 510 Sequence, effectively unpredictable 223 Sequence, enumerable see “Characteristic sequence of recursively enumerable set” Sequence, finite see “String” Sequence, hyperarithmetically random 157 Sequence, incompressible 217 Sequence, infinite see “Sequence” Sequence, k-distributed 58 Sequence, Kolmogorov-Loveland random 150 Sequence, Martin — Loef random see “Sequence random” Sequence, Mises — Wald — Church random 53 55 57 149 150 153 154 223 313 473 Sequence, nonrecursive 220 Sequence, normal 58 158 223 Sequence, pararecursive 153 Sequence, pseudo-random 86 Sequence, random 55 92 142 136—158 176 186 190 210—212 214 215 217—219 221—223 294 304 311 Sequence, recursive 47 106 118 124 125 153 220 242 268 300 302 466 Sequence, Schnorr random 156 Sequence, Solovay random 152 212 221 Sequence, strongly Chaitin random 221 238 Sequence, typical 54 Sequence, universal recursive 268 Sequence, von Mises random see “Collective” Sequence, weakly Chaitin random 221 238 Set, arithmetic 222 Set, Borel 157 222 Set, CD[f(n), t(n), s(n)] 471 Set, complete 230 Set, continuous 7 Set, countable 7 Set, CU[f(n), t(n), s(n)] 473 Set, cylinder see “Cylinder” Set, C[f(n), t(n), s(n)] 469 469—476 488—495 Set, diagonal halting 34 36 44 81 175 Set, effectively immune 168 175 Set, effectively simple 168 175 Set, empty 6 Set, enumerable without repetitions 43 Set, exponentially low 490 Set, fractal 126 Set, halting 34 44 169 170 173 177 Set, hyperarithmetic 157 Set, hyperimmune 178 Set, immune 43 174 177 Set, intuitionistic measure zero 156 Set, Kolmogorov 175 Set, m-complete 169 170 177 Set, meager 112 186 Set, P-printable 491 505 Set, Q-immune 471 Set, r-complete (r = 1, m, T) 44 Set, r-hard (r = 1, m, T) 44 Set, RAND 168 174 Set, recursive 32 Set, recursively enumerable 32 171—173 Set, recursively enumerable-complete 489 Set, relative enumerable 268 Set, semirecursive 176 Set, simple 43 44 167 169 174 177 Set, sparse 186 472 482 485 491—493 Set, tally 491 Set, Turing complete 175 177 Set, weak truth-table complete 176 Shakespeare, W. 105 Shallit, J. 457 Shamir, A. 118 487 Shannon, C.E. 48 65 70 75 81 84 85 88 89 92 93 185 191 308 588 Shen', A.Kh. 108 119 150 152 185 187 197 238 313 457 Sherman, A.T. 537 587 Shiryaev, A.N. 91 92 Shortest common supersequence 417 420 Shortest program 102 110 204 205 208 235 236 256 282 Shortest program, prefix complexity of 204 Simon, J. 442 452 453 Simons, G. 56 Simple DNF 349 Singh, B.S. 376 Sipser, M. 126 151—153 431 482 486 516 517 Sivakumar, D. 518 Skiena, S.S. 86 Sleator, D. 416 Slotine, J.J. 589 Smith, C. 373 Snell, J.L. 313 Snir, M. 157 Sobolev, S.L. 90 Solomonoff normalization see “Semimeasure Solomonoff Solomonoff's induction theory 324—335 Solomonoff's Inductive Formula 331 372 Solomonoff, R.J. 59 62 87 89—92 96 185 186 191 237 280 281 301—303 308—311 323 324 335 372 519 Solovay, R.M. 92 125 152 174 177 195 206 211 212 220—222 226 238 267 301 311 sophistication 100 185 589 Source sequence 72 Source word 13 71 Space-energy tradeoff 537 Spencer, J.H. 87 390 394 453 454 STACK see “Pushdown store” Stanat, D. 420 State space 559 Statistical properties, of graphs 400—403 Statistical properties, of sequences 158—166 187 Stearns, P. 390 Stearns, R. 438 455 460 476 Stimm, H. 58 Stirling's formula 17 67 134 180 403 Stirling, J. 17 Stochastic complexity vi 375 Stochastic source 67 String 12 String, 118 166 String, (k, 114 185 String, absolutely nonrandom 119 String, binary 12—15 String, c-incompressible 109 133 String, C-random 210 String, compressibility of 108 String, cyclic shift 154 204 String, empty 12 String, incompressibility of substring 110 String, incompressible 117 127 135 203 208 String, incompressible w.r.t. K 203 209 String, infinite see “Sequence” String, K-random 210 String, length of 13 String, n-string see “n-string” String, random 90 113 133 127—136 186 208—211 String, reverse of 12 101 String, self-delimiting 13 String, typical 119 Submartingale 296 Submartingale, universal enumerable 296 295—297 Sudborough, H. 430 Svetlova, N.D. 88 Symmetry of information 233 385
Реклама
-definable 
-distributed 
-random 
-random 
-random 
|
|
О проекте