Авторизация
Поиск по указателям
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
Предметный указатель
Kasami, T. 455 Katseff, H.P. 126 151—153 186 Kc: Chaitin's conditional prefix complexity 235 Kearns, M. 374 Kemeny, J.G. 372 Keuzenkamp, H.A. 377 Keyes, R.W. 587 Keynes, J.M. 55 Khintchin, A.I. 65 81 Kieffer, J.C. 528 Kim, C.E. 430 Kim, J. 453 Kirchherr, W.W. 404 Kleene, S.C. 35 41 Km: monotone complexity 282 KM: negative logarithm of M(x) 282 Knopp, K. 83 Knuth, D.E. ix 16 17 86 187 Ko, K.-L 474 499 501 502 516 518 Kobayashi, K. 310 444 509 520 Koenig's Infinity Lemma 126 Kolmogorov axioms 18 Kolmogorov complexity see “Complexity algorithmic” Kolmogorov minimal sufficient statistic 115 114—115 119 358 Kolmogorov random graphs 396—404 Kolmogorov — Chaitin randomness see “Complexity algorithmic” Kolmogorov, A.N. 18 49 50 52 55 56 65 70 86—92 95 96 103 118 136 149 150 166 185—188 212 238 267 268 302 306—308 312 459 516 518 589 Koppel, M. 100 185 Korb, K.B. 377 Kraft inequality 74 74—76 80 82 83 88 191 195 202 213 214 220 232 254 Kraft, L.G. 74 88 Kranakis, E. 410 411 454 Kreinovich, V. 157 Krizanc, D. 410 411 454 Kt: Levin-complexity 502—505 Kullback divergence 328 Kummer, M. 117 174 485 500 502 518 K{x|l(x)): length-conditional K 195 l(x): length of string x 13 L(x): uniform discrete distribution on M 23 l*(x): optimal universal code-word length 79 Landauer, R. 528 532 586 587 Language compression 477 476—488 Language compression, optimal 477 484—485 Language compression, P-rankable 486 Language compression, probabilistic 481—484 Language compression, ranking 477 484—485 Language compression, with respect to 477—481 Language compression, with respect to 481—484 Laplace, P.S. 20 49 59 63 239 300 307 372 Laplante, S. 456 Lathrop, J.I. 520 Law of Large Numbers 54 63 140 155 263 265 Law of Probability 263 265 295 Law of Randomness 54 57 140 Law of succession 63 300 Law, 0—1 457 Law, Complete Probabilities 19 Law, High-Low Kolmogorov Complexity 457 Law, Infinite Recurrence 57 149 306 Law, Inverse Weak Law of Large Numbers 64 Law, Iterated Logarithm 54 57 65 87 140 149 223 265 306 Law, Slow Growth 514 516 Law, Strong Law of Large Numbers 64 306 Law, Weak Law of Large Numbers 59 63 64 Learning, by enumeration 336 Learning, decision list 349—350 Learning, decision tree 364—368 Learning, distribution-free 342 Learning, in the limit 336 Learning, log-decision list 350 Learning, log-DNF 345—347 Learning, log-DNF formula 344 Learning, monotone k-term DNF 350 Learning, simple DNF 349 Learning, under computable distributions 342—350 Learning, under M 347—349 Lecerf, Y. 586 Lemma, Coding 479 Lemma, Honesty 488 490 Lemma, Jamming 433 Lemma, KC-Regularity 422 Lemma, Pumping 420 Lemma, Switching 449 Leung-Yan-Cheong, S.K. 89 204 206 237 Levin, L.A. 86 125 156 178 184—188 196 197 209 212 230 235 238 281 283 300 301 303 310—314 472 504 517—519 Levine, R.Y 537 587 Levy, P. 311 313 Lewis II, P. 476 Li, M. 187 272 310 344 348—350 368 373—376 395 403 416 420 425 426 431 438—440 447 452—454 456 509 519 537 553 587 588 Likharev, K. 587 Lindstrom, B. 392 Lipton, R.J. 448 486 List, B 526 Literal 344 Littlestone, N. 373 Littlewood, J.E. 16 87 Lloyd, S. 587 589 ln: Natural logarithm 8 Lofgren, L. 185 log*x: number of terms in l*(x) 79 log-decision list 350 log-DNF 345 349 log: binary logarithm 8 Logical depth 510—516 Logical depth, (d, b)-deep 512 513 Logical depth, machine independence 516 Logical depth, of 514 Logical depth, shallow 514 Logical depth, stability 516 Longest common subsequence 417 417—419 Longpre, L. 157 440 475 476 495 517 518 520 Lopez-Ortiz, A. 438 Loui, M.C. 443 444 Lovasz, L. 374 Loveland, D.W. 117 124 125 149 153 154 186 424 427 516 Low, L.H. 376 Lower bounds 404—457 Lower bounds, Boolean matrix rank 383 Lower bounds, circuit depth 448—452 Lower bounds, converting NFA to DFA 385 Lower bounds, for Turing machines 432—444 Lower bounds, in formal language theory 420—427 Lower bounds, k-head automaton 430 Lower bounds, k-pass DFA 431 Lower bounds, k-PDA 431 Lower bounds, multihead automata 430—431 Lower bounds, one-tape Turing machine 380 Lower bounds, online CFL recognition 427—430 Lower bounds, parallel computation 445—448 Lower bounds, Ramsey theory 392 Lower bounds, routing in networks 407—408 Lower bounds, string-matching 430 431 Lower bounds, sweeping two-way DFA 431 Lower bounds, VLSI 447—448 Luccio, F.L. 411 454 Lucretius 316 Luginbuhl, D.R. 444 Luo, Z.Q. 395 Lutz, J.H. 494 517—519 M: universal enumerable continuous semimeasure 272 m: universal enumerable discrete semimeasure 247 248 Maass, W. 438—442 455 456 Machine, deterministic Turing 28 326 Machine, k-pushdown store 438 Machine, k-queue 439 Machine, k-stack 438 442 Machine, k-tape 442 Machine, Kolmogorov — Uspensky 519 Machine, monotone 276 280 283 309—312 Machine, nondeterministic 1-tape Turing 439 Machine, nondeterministic Turing 37 Machine, offline Turing 440 Machine, one-way Turing 432—444 Machine, online Turing 432 432—444 Machine, oracle Turing 38 Machine, PRAM 445 Machine, prefix 193 310 Machine, probabilistic Turing 177 177 385 480 Machine, reference monotone 280 Machine, reference prefix 194 Machine, reference Turing 98 99 Machine, reversible Turing 534 Machine, Turing 27 37 40 84—86 380 Machine, two-dimensional tape 442 Machine, universal Turing 30 84 185 Macro state 558 560 Mahaney, S. 493 Mairson, H.G. 457 Malign see “Distribution malign” Mamitsuka, H. 376 Mandelbrot, B. 126 Margolus, N. 532 Markov process 20 326 Markov's inequality 134 261 265 271 Markov, A.A. 41 185 Markowsky, G. 373 Martin-Loef, P. 54 92 113 127 136 149 151 152 154 156 157 186 210 212 313 Martingale 296 311 313 518 Marxen, H. 46 Matching 540 Matijasevich, Yu.V. 173 224 225 Matthew Effect 90 Maxwell's demon 567—570 Maxwell, J.C. 567 Mayordomo, E. 519 Mc: universal enumerable extension semimeasure 302 McAleer, M. 377 McCarthy, J. 308 McGorry, P.D. 376 McKenzie, D.P. 376 McMillan, B. 82 Measure 19 21 324 Measure, constructive 186 Measure, continuous 21 Measure, countable 21 Measure, defective 308 Measure, discrete 21 Measure, discrete enumerable 230 Measure, discrete recursive 230 Measure, Lebesgue see “Measure uniform” Measure, of random sequences 146 220 Measure, probability 243 Measure, recursive 36 244 277 300 Measure, recursive continuous 272—280 282 304 332 Measure, recursive discrete 245—268 Measure, resource-bounded 517 Measure, simple 347 Measure, Solomonoff 281 300 301 Measure, uniform 21 244 278 347 468 517 Measure, universal enumerable 347 Measure, universal recursive 265 Meertens, L. 17 86 Mehlhorn, K. 457 Merkle, R.C. 532 587 Meyer auf der Heide, F. 456 Meyer, A.R. 125 424 Micro state 558 559 Mills, W.H. 392 Milosavljevic, A. 377 Miltersen, P.B. 310 509 520 Minsky, M. 31 85 90 308 309 Miyano, S. 431 Mocas, S. 475 Monomial 344 349 Monotone k-term DNF 350 Mooers, C 309 Moran, S. 411 456 Moser, L. 392 Muchnik, A.A. 44 150 Muchnik, An.A. 150 268 Multinomial coefficient 10 Multiplication rule 19 Multiplicative domination 246 Munro, I. 412 454 n(T): index of T 30 n-string 112 116 123—125 152 186 Naik, A. 518 Natarajan, B.K. 374 476 Nelson, C.G. 430 Newman, I. 453 Newman-Wolfe, R. 442 453 Newton, I. v 9 23 317 NFA see “Finite automaton” NP-complete 39 489 NP-hard 39 Null set 140 Null set, 142 Null set, 156 Null set, constructive 142 144 145 156 Null set, total recursive 156 Number, 222 242 Number, arithmetically random real 222 Number, enumerable see “Sequence enumerable” Number, enumerable real 300 Number, nonrecursive real 219 Number, normal see “Sequence normal” Number, numbering, acceptable 104 Number, of Wisdom 218 Number, prime 4 17 32 83 Number, random real 218 222 300 Number, recursive real see “Sequence recursive” Number, transcendental 218 219 o(f(x)): asymptotically less than f(x) 15 O(f(x)): at most of order of magnitude f(x) 15 Oberschelp, A. 46 Occam algorithm 340 Occam's razor v 62 240 252 299 317 318 331 340 Occupancy number 10 Ockham, William of 62 240 317 319 323 Odifreddi, P. 41 42 45 86 175 Oliver, J.J. 376 Oracle 38 40 462 481—483 488—492 494 Oracle, Baker — Gill — Solovay 488 Order of magnitude symbols 17 Order, partial 7 Order, total 7 Orponen, P. 499 501 502 517 518 Outcome of experiment 18 256 257 263 331 Ozhegov, S.I. 88 O’Connor, M.G. 58 P-isomorphic 489 P-printability 491 Pac-learning 339 339—350 374 Pac-learning, simple 339 342—350 374 Paradox, Bertrand 316 Paradox, Richard — Berry 1 170 Paradox, Russell 170 Parberry, I. 456 Parikh, R. 420 Partition 10 Pascal, B. 23 Patashnik, O. 17 Patrick, J.D. 376 Paturi, R. 442 453 Paul, W.J. 442 443 452 455 PDA see “Pushdown automaton” Peano arithmetic 35 Pearl, J. 374 Pednault, E.P.D. 376
Реклама
|
|
О проекте