Li M., Vitanyi P. — An introduction to Kolmogorov complexity and its applications :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Li M., Vitanyi P. — An introduction to Kolmogorov complexity and its applications

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: 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

Предметный указатель

$(k, \delta)$ -stochasticity      see “String \delta)$"/>-stochastic”
: number of variations      8
$(^{n}_{k})$ : number of combinations      9
$A^{=n}$ : set of all words of length n in A      476
$A^{\infty}$ : set of one-way infinite sequences over set A      13
$A^{\leq n}$ : set of words of length $\leq n$ in A      112
$CD^{s}$ : space-bounded version of $CD^{t,s}$       462
$CD^{t,s}$ : time-space-bounded accepting complexity      461
$CD^{t}$ : time-bounded version of $CD^{t,s}$       462 463
: space-bounded version of $C^{s,t}$       462
: time-bounded version of $C^{s,t}$       462
$C^{+}$ : monotone upper bound on C-complexity      207
$C^{s,t}$ : time-space-bounded C complexity      460
$C_{r}$ :complexity of r-ary strings      107
$C_{\phi}$ : complexity with respect to $\phi$       97
: instance complexity      495
$I_{c}(x:y)$ : algorithmic information in x about y      179
$KD^{t,s}$ : K version of $CD^{t,s}$       463
$K^{+}$ : monotone upper bound on K-complexity      224
$K^{s,t}$ : time-space-bounded K complexity      463
: halting set      34
$M_{norm}$ : Solomonoff measure      281 300 301
: i-th letter of x      12
: reverse of string x      12
$x_{1:n}$ : first n letters of x      12
$\bar{x}$ : prefix-code $1^{l(x)}0x$ for x      13
$\Delta_{i}^{p}$ : class in polynomial hierarchy      40
$\Delta_{n}^{0}$ : class in arithmetic hierarchy      46
$\ell*(x)$ : lower bound on l*(x)      80
$\emptyset$ : empty set      6
$\exists$ : there exists      8
$\exists^{\infty}$ : there exist infinitely many      8
$\forall$ : for all      8
$\forall^{\infty}$ : for all but finitely many      8
$\Gamma_x$ : cylinder generated by x      14
$\lambda(\omega)$ : uniform continuous distribution on [0, 1)      23
$\langle\cdot\rangle$ : pairing function      7
$\lceil\cdot\rceil$ : ceiling of a number      8
$\lfloor\cdot\rfloor$ : floor of a number      8
$\mathcal{B}$ : basic elements      12 242
$\mathcal{N}$ : the nonnegative integers      6
$\mathcal{Q}$ : the rational numbers      6
$\mathcal{R}$ : the real numbers      6
$\mathcal{Z}$ : the integers      6
$\Omega$ : halting probability      217 427
$\omega$ : infinite sequence of elements of $\mathcal{B}$       13
$\Omega(f(x))$ : at least of order of magnitude f(x)      15
$\phi(x) < \infty$ : $\phi(x)$ converges      7
$\phi(x) = \infty$ : $\phi(x)$ diverges      7
$\Pi^{n}_P{0}$ : class in arithmetic hierarchy      46
$\Pi_{i}^{p}$ : class in polynomial hierarchy      40
$\rho_0$ : universal integral test      214
$\sigma$ -algebra      20
$\Sigma^{0}_{n}$ : class in arithmetic hierarchy      46
$\Sigma^{p}_{i}$ : class in polynomial hierarchy      40
$\Theta(f(x))$ : of order of magnitude f(x)      16
$|\cdot|$ : absolute value of a number      8
0': Turing degree halting problem      220
A*: set of all finite sequences of elements of set A      12
Aanderaa, S.O.      452 455
Abel, N.H.      83
Acceptable numbering      41 104
Accepting a language      37
Ackermann, W.      45
Adleman, L.      516 519
Agafonov, V.N.      58 178
Aleksandrov, P.S.      90
algorithmic complexity      see “Complexity”
Algorithmic complexity theory      vii 93—238
Algorithmic probability theory      239—314
Allender, E.      494 505 517 519 520
Allison, L.      376
Alon, N.      394 453 454
Andrews, J.      177
Angluin, D.      87 373 374
Anthony, M.      374
Ants      583
Archimedes      48
Arithmetic hierarchy      46
Asarin, E.A.      166
Asmis, E.      372
Asymptotic notation      15—17
Atlan, H.      100 185
Average-case, adder design      382—383
Average-case, complexity      268—272 307 310 382—383 385—389 396—420
Average-case, Heapsort      412—417
Average-case, longest common subsequence      417—419
Average-case, routing in networks      408—409
Average-case, shortest common supersequence      420
Avogadro's number      558
Bachman, P.      15
Bacon, F.      585 589
Baker's Map      575
Balcazar, J.L.      86 350 494 517 519
Baranyai, Zs.      403
Barendregt, H.P.      198
Barron, A.R.      376
Barzdins's Lemma      171 173 174 187 224 230 426 427 463 466 514
Barzdins, J.M.      108 171 173 178 187 373 427 466 472 516
Basic element      12 242 272
Bayes's rule      20 19—20 59 62 63 87 89 300 308 309 319—324 333 335 353 370 372 375
Bayes, T.      59 319 323 372
Bayesian reasoning      319—323
Beigel, R.      452
Ben-Amram, A.M.      457
Benedek, G.      348 374
Benioff, P.A.      157 532
Bennett, C.H.      176 187 218 238 510 515 520 532 536 537 567 586—588
Berman — Hartmanis conjecture      489
Berman, P.      5 84 493
Bernoulli process      59 63—65 184 263 300
Bernoulli, J.      59 63
Berry, G.G.      170
Betting      262—265
Biggs, N.      374
Binary interval      254 283
Binomial coefficient      9
Bit: binary digit      v
Blum, M.      476
Blumer, A.      349 374
Bogolyubov, N.N.      90
Bollobas, B.      454
Boltzmann constant      528 561
Boltzmann, L.      558
Bolyai, J.      89
Bolyai, W.      89
Book, R.V.      457 494 517 518 520
Boolean formula      344 492
Boolean matrix rank      383
Boppana, R.      454
Borel — Cantelli Lemmas      64 151
Borel, E.      20 158 223
Boswell, J.      239 307
Boulton, D.M.      375
Brady, A.H.      46
Brebner, G.      396
Breitbart, Y.      457
Brewer, R.G.      588
Briley, B.E.      453
Brouwer, L.E.J.      156
Brownian computer      532
Bruijn sequence      455
Buhrman, H.M.      117 403 405 409 453 454 485 494 501 517 518
Burks, A.W.      382 452 586
C(x;n): uniform complexity      124
C(x|l(x)): length-conditional C      111
C: complexity      98
Cai, J.-Y.      126 487
Calude, C      150 151 219
Cantelli, F.P.      64

Cantor, D.G.      392
Cantor, G.      40
Cardano      23
Cardinality      6 13
Carnap, R.      89 308 323
Carnot cycle      555
Carnot, N.L.S.      554
Cartesian product      6
Castro, J.      350
Cauchy — Schwartz inequality      457
Caves, C.M.      527 586 589
CD[f(n), t(n), s(n)]      471
Chaitin, G.J.      84 89 92 96 125 152 179 185—187 197 198 204 212 214 219 220 222—225 237 238 302 311 375 424 520
Champernowne's number      see “Sequence Champernowne's”
Champernowne, D.G.      53 87
Chaos      579 580
Characteristic sequence      119 171 464
Characteristic sequence of       173 230
Characteristic sequence of a language      423 426 427 487 520
Characteristic sequence of high Turing degree set      176
Characteristic sequence of hyperimmune set      178
Characteristic sequence of immune set      177
Characteristic sequence of nonrecursively enumerable set      172 174
Characteristic sequence of recursively enumerable set      153 171 173 176 224 230 463 466 472 514
Characteristic sequence of semirecursive set      176
Characteristic sequence, random      224 494
Chater, N.      377
Cheeseman, P.      376
Chernoff bounds      61 159 322 397 406
Chernoff, H.      87
Chervonenkis, A.Ya.      374
Chitescu, I.      150 151
Chomsky hierarchy      420
Chomsky, N.      309
Chrobak, M.      431
Church random sequence      see “Sequence Mises
Church's thesis      24 29 53
Church, A.      24 35 41 51 53 87 149
Chvatal, V.      374 420
Clause      344
CLIQUE      392 394
Cn: normalized complexity for reals      125
CNF formula      344
Coarse-graining      560
Code sequence      72
Code word      13 71
Code, additively optimal universal      236
Code, ASCII      72
Code, asymptotically optimal universal      78 79
Code, average word length      75 88 191
Code, fixed-length      72
Code, Hamming      117
Code, instantaneous      see “Code prefixcode”
Code, Morse      66 70
Code, optimal prefixcode      75
Code, prefixcode      5 13 15 68 72 71—84 88 191
Code, self-delimiting      76
Code, Shannon — Fano      67 76 80 88 253 259 303 353 375 513 523 527
Code, two-part      99—100 589
Code, uniquely decodable      72 75 81 82
Code, universal      78 77—80 82 88 257
Code, variable-length      72
Cohen, P.      92
Coin-weighing problem      392
Collective      50 51 53 55 57 87 136 148 149 155
Combination      8
Combinatorics      8—11 86 389—396
Combinatory logic      198 237
Complexity class, #P      486
Complexity class, $\Delta^{E}_2$       493
Complexity class, $\Delta^{p}_i$       40
Complexity class, $\Pi^{p}_i$       40 517
Complexity class, $\Sigma^{p}_i$       40 517
Complexity class, BPP      480 517 518
Complexity class, DSPACE      38 472 476 517
Complexity class, DTIME      37 474 487 489 490 494 518
Complexity class, E      490 491 493 495 518
Complexity class, ESPACE      517
Complexity class, EXPTIME      494
Complexity class, IC[log, poly]      497
Complexity class, NE      493
Complexity class, NP      38 462 481 486 489 493 498 505 518
Complexity class, NSPACE      38 494
Complexity class, NTIME      37
Complexity class, P      38 486 489 493 498 505 518
Complexity class, P/log      500
Complexity class, P/poly      485 500
Complexity class, PSPACE      38 486 494
Complexity class, R      481
Complexity oscillation      92 136 136—140 148 151 152 186 187 190 208 211 215 223
Complexity oscillation, of K-      216 219—221
Complexity oscillation, of Km-      216 311
Complexity, $CD^{s}$       462
Complexity, $CD^{t,s}$       461 461—463 472
Complexity, $CD^{t}$       462 476—488 496
Complexity, $C^{s}$       462 468
Complexity, $C^{t,s}$       460 460—463 469
Complexity, $C^{t}$       462—468 472 476—488
Complexity, $KD^{s}$       472
Complexity, $KD^{t,s}$       463 472
Complexity, $K^{s,t}$       463 472
Complexity, $K_{\mu}-$       303
Complexity, additivity of      101 111 184 189 194 229 231 233
Complexity, additivity of C-      188
Complexity, additivity of K-      233 234
Complexity, additivity of Kc-      235
Complexity, algorithmic      1 65 90 180
Complexity, alternative approach to define it      196
Complexity, approximation of      118 121
Complexity, average-case      268—272 307 310
Complexity, C-      98 95—188 197
Complexity, conditional C-      98 111
Complexity, conditional K-      194
Complexity, continuity of      116 122
Complexity, Ct      505
Complexity, expected C-      116 181 522—528
Complexity, expected K-      181 231 522—528
Complexity, extension-      206
Complexity, fluctuation of      122
Complexity, instance-      495 495—502
Complexity, K-      see “Complexity prefix”
Complexity, Kc-      235 236 237
Complexity, KM-      282 303
Complexity, Kt      502—505
Complexity, length-conditional      111 116 120 123 153 154 186
Complexity, length-conditional K-      195 204 207
Complexity, lower bound on C(x|l(x))-      120 123
Complexity, lower bound on C-      119
Complexity, lower bound on K-      206
Complexity, majorant of      241 463
Complexity, monotone      197 212 216 282 282—285 303 306 311 312
Complexity, monotonic upper bound on K-      207 224 225 226
Complexity, monotonicity on prefixes      111 189 191 211
Complexity, noncomputability of      121 185
Complexity, normalized for real numbers      125
Complexity, number of states-      177
Complexity, of complexity function      175 227 226—230 237 238
Complexity, of function      108 227
Complexity, prefix      96 125 194 189—238 310 372
Complexity, r-ary strings C-      107
Complexity, relation between C and K      205
Complexity, resource bound hierarchies      469—472
Complexity, resource-bounded      viii 90 459—520
Complexity, space      37
Complexity, state-symbol product      84 84—85 89 92
Complexity, stochastic      vi 375
Complexity, time      37
Complexity, time-bounded uniform      473
Complexity, time-space-bounded      460—463
Complexity, uniform      124 152 154 186 189 197 285 473 516

1 2 3 4 5

О проекте