Авторизация
Поиск по указателям
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
Предметный указатель
Complexity, worst-case space- 269 307 Complexity, worst-case time- 269 307 Computability theory 24—47 86 Computable majorants 463—468 Computational complexity viii 36—40 488—502 517 Computational learning theory vii 6 339—350 Concatenation 12 Context-free language 505 Convergence, apparent, of relative frequency 135 Convergence, recursive, of series 145 148 151 154 219 Convergence, regulator of 152 Cook, S.A. 518 Copolov, D.L. 376 counting method 390 Cover, T.M. 88 89 91 105 134 185 204 206 208 237 300 302 314 372 373 376 526 527 586 Crossing sequence 380 447 Csiszar, I. 117 Culik II, K. 416 Cutler, C.C. 586 CU[f(n), t(n), s{n)] 473 Cylinder 14 21 55 137 141 349 C[f(n), t(n), s(n)] 469 d(A): cardinality of set A 6 Daley, R.P. 149 153 154 176 472—474 516 de Bruijn, N.G. 455 de Fermat, P. 23 172 de Leeuw, K. 178 de Mere, Chevalier 23 Decision list 349—350 Decision tree 364—368 Degree of unsolvability 44 Dekker, J.C.E. 43 44 DeSantis, A. 373 Descriptional complexity see “Complexity” Dewdney, A.K. 46 DFA see “Finite automaton” Diagonalization method 34 Diaz, J. 86 Dietzfelbinger, M. 440 441 Dimension, Hausdorff 126 Dimension, topological 126 Dimension, Vapnik — Chervonenkis 349 Diophantine equation 172 173 224 238 Distance, max 539 Distance, picture 541 Distance, reversible 544 Distance, sum 546 Distribution, binomial 61 322 Distribution, Bose — Einstein 11 260 Distribution, computable universal 506—509 Distribution, conditional universal 255 Distribution, distribution-free learning 339—350 Distribution, Fermi — Dirac 11 260 Distribution, malign 509 Distribution, Maxwell — Boltzmann 11 Distribution, normal 362 364 Distribution, of description length 202 205 238 257 266 Distribution, simple 343 Distribution, uniform 21 68 76 129 131 Distribution, uniform continuous 23 Distribution, uniform discrete 23 262 Distribution, universal 6 253 246—280 307 319 523 Distribution, universal time-limited 506—509 Dix, T.I. 376 DNF formula 344 Doob, J.L. 298 313 Dowe, D.L. 376 377 Drexler, K.E. 587 Duns Scotus, John 62 Duris, P. 442 455 D’Ariano, G.M. 589 Edgoose, T. 376 Edmonds, J.E. 39 Effective enumeration 29 Ehrenfeucht, A. 349 374 420 Element distinctness problem 438 Elias, P. 56 82 88 Ensemble 65 564 entropy 65 67 75 78 80 149 180 181 184 187 190 191 231 522—528 Entropy, algorithmic 571 565—583 588 Entropy, Boltzmann 578 Entropy, classical 554 Entropy, coarse-grained algorithmic 572 573 578 Entropy, complexity 565 566 Entropy, conditional 69 231 Entropy, Gibbs 564 566 572 Entropy, joint 231 Entropy, n-cell algorithmic 571 Entropy, of English 105 Entropy, of Russian 88 Entropy, physical 588 Entropy, relation with complexity 522—528 Epicurus 315 317 319 323 372 Erdos, P. 87 390 392 394 453 454 Event 18 Event, certain 18 21 Event, impossible 18 21 Event, mutually independent 20 Event, probability of 18 Fano, R.M. 88 Feder, M. 377 Felker, J.H. 586 Feller, W. 10 11 22 23 63—65 86 308 Ferguson, T.S. 56 Fermi, E. 89 588 Feynman, R.P. 532 Fich, F. 447 Field 19 Field, Borel 20 Field, Borel extension 21 Field, probability 19 Fine, T.L. 87 90 135 372 Finetti, B. de 372 Finite automaton, deterministic (DFA) 317 385 431 Finite automaton, k-head DFA 430 Finite automaton, k-pass DFA 431 Finite automaton, nondeterministic (NFA) 385 Finite automaton, sweeping two-way DFA 431 Fisher, R.A. 369 370 377 Floyd, R.W. 412 454 Ford, J. 589 Fortnow, L. 117 456 485 499—501 517 518 Foulser, D. 420 Fractal 125 126 Fredkin gate 530 532 Fredkin, E. 586 587 Freeman, P.R. 375 Freivalds, R.V. 373 385 452 frequency 66 Frequency interpretation of probability 50 87 Frequency, a priori 268 Frequency, lower 267 Frequency, relative 50 Friedberg, R.A. 42 44 Fu, B. 495 Function, Ackermann 45 82 285 Function, additively optimal see “Function universal” Function, additively optimal partial recursive prefix 193 Function, Busy Beaver 45 123 178 301 Function, characteristic 7 32 33 339 495 Function, co-enumerable 35 303 Function, complexity- 196 Function, composition of 7 Function, computable see “Function partial Function, consistent 495 Function, convergence of 7 Function, decoding 13 71 Function, distribution 22 Function, divergence of 7 Function, encoding 71 Function, enumerable 35 35—36 86 108 240—242 308 Function, factorial 8 17 Function, generalized exponential 45 Function, honest 488 489 Function, inverse of 7 Function, many-to-one 7 Function, monotone 277 278 279 Function, noncomputable see “Nonrecursive” Function, nonrecursive 45 167 178 226 Function, one-to-one 7 Function, pairing 7 Function, parity 451 Function, partial 7 Function, partial recursive 29 Function, partial recursive prefix 192 Function, payoff 263 262—265 296 Function, predicate 29 Function, predictor 58 Function, primitive recursive 83 Function, probability 22 303 Function, probability density 22 Function, ranking 491 Function, real-valued enumerable 36 Function, real-valued recursive 36 Function, recursive 29 35—36 40 46 53 108 126 240—242 308 Function, recursive real 35 Function, regular 277 Function, semicomputable see “Function enumerable” Function, shape 126 Function, successor 29 Function, total 7 Function, total recursive see “Function recursive” Function, universal 95 96 97 Function, universal co-enumerable 241 Function, universal enumerable 241 Function, universal partial recursive 31 Fundamental inequality 356—359 Gabarro, J. 86 Gacs, P. 91 107 108 134 166 175 176 178 184 186 187 197 204 205 208 210 223 226 230 235 237 238 266 267 281 284 300 303 311 313 314 373 517 519 520 526 527 586—588 Gaifman, H. 157 Galil, Z. 430 439 442 455—457 Gallager, R.G. 82 88 Gallaire, H. 455 Gao, Q. 376 Garbage bits 530 Gardner, M. 218 238 Garey, M.R. 86 Gasarch, W. 175 176 452 453 486 Gavalda, R. 374 494 Gavoile, C 410 411 Gell-Mann, M. 587 589 Generalized Kolmogorov complexity 459—520 Genericity 92 Gereb-Graus, M. 431 Gibbs, J.W. 564 Gnedenko, B.V. 90 Godel number 30 Godel numbering see “Numbering acceptable” Godel, K. 3 33 34 89 168 170 187 Gold, E.M. 335 373 Goldbach's conjecture 218 Goldberg, A. 482 486 517 Goldstine, H.H. 382 452 Good, I.J. 372 Graham, R. 17 Gray, R.M. 91 134 314 526 527 586 Grossman, J.W. 45 Gurevitch, Yu. 519 H: entropy stochastic source 67 Hahn, E.L. 588 Halting probability 217 216—219 221 223 237 238 242 252 514 Halting problem 33 33—35 42 178 217 Hamiltonian equations 561 Hammer, D. 108 457 Hancock, T. 368 Hanson, N.R. 318 Hardy, G.H. 16 Harrison, M.A. 426 431 454 Hartle, J.B. 589 Hartmanis, J. 86 126 438 455 476 493 516 517 Hastad, J. 456 Haussler, D. 349 374 Heapsort 412—417 454 Heim, R. 135 313 Hellinger distance 303 Hemachandra, L. 486 487 517 519 Hemaspaandra, E. 494 Hennie, F.C. 452 455 460 Hermo, M. 519 Heyting, A. 156 Hiihne, M. 440 Hilbert's tenth problem 173 Hilbert, D. 45 172 Hoeffding, W. 56 Hoepman, J.H. 405 409 454 homer 93 Hopcroft, J.E. 454 Hume, D. 323 Hunter, L. 376 Hurewicz, W. 126 Huynh, D.T. 486 488 Hwang, K. 453 Ibarra, O.H. 430 431 Immune, biimmune 487 Immune, P/poly 487 Incompressibility method 379—457 Induction 315 Induction, in recursion theory 335—338 Inductive inference 315 Inductive inference, Gold paradigm 335 336 373 Inductive reasoning vii 6 59 89 90 308 315—372 Inductive reasoning, using M 326—332 information 65 Information theory 48 65—84 88 179 180 Information theory, algorithmic 179—185 191 229—237 522—528 Information, algorithmic 179 Information, dispersal of 118 Information, Fisher 305 Information, in x about y 231 233 576 Information, mutual 70 236 267 580 Information, mutual using K 235 Information, symmetry of algorithmic 182 188 229 234 235 238 Instance complexity conjecture 496 Irreversible computation 528 529 Israeli, A. 456 Itai, A. 348 374 Itoh, S. 376 Jaffe, J. 420 Jagota, A.K. 310 520 Jakoby, A. 310 509 520 Jaynes, E.T. 370 377 Jiang, T. 368 374 395 420 431 443 454 Jockusch, C.G. 176 Johnson, D.S. 86 374 Johnson, Dr. Samuel 239 307 Jones, J.P. 224 225 Joseph, D. 500 Juedes, D.W. 518 520 Juergenson, H. 219 Jurka, J. 377 K(K(x)|x): complexity of the complexity function 227 K(x): prefix complexity 194 K: diagonal halting set 34 Kahn, J. 453 Kalyanasundaram, B. 396 Kamae, T. 58 174 204 Kanefsky, F. 376 Kannan, R. 439 456 Kanovich, M.I. 177 Karp, R.M. 486
Реклама
|
|
О проекте