An Introduction to Kolmogorov Complexity and Its Applications

این کتاب پرفروش در حال انجام، که اکنون در نسخه سوم خود قرار دارد، مرجع استاندارد پیچیدگی کولموگروف، نظریه مدرن اطلاعات است که به اطلاعات در اشیاء منفرد مربوط می شود.

ویژگی های کلیدی جدید و موضوعات در ویرایش سوم:

* نتایج جدید در مورد تصادفی

* تابع ساختار کولموگروف، انتخاب مدل، و MDL

* روش تراکم ناپذیری: شمارش نمودارهای بدون برچسب، مرتب سازی پوسته، پیچیدگی ارتباط

* تصادفی سازی

* پیچیدگی کلموگروف در مقابل اطلاعات شانون، اعوجاج نرخ، فشرده سازی با تلفات، نویز زدایی

* نتایج نظری در مورد فاصله اطلاعات

* سنجه تشابه با کاربردهای ژنومیک، فیلوژنی، خوشه بندی، طبقه بندی، معنای معنایی، سیستم های پرسش و پاسخ

*پیچیدگی کوانتومی کولموگروف

نوشته شده توسط دو متخصص در این کتاب برای دانشجویان پیشرفته مقطع کارشناسی، دانشجویان کارشناسی ارشد و محققان در تمام زمینه های علمی ایده آل است. این خودکفا است: شامل الزامات اساسی از ریاضیات، نظریه احتمالات، آمار، نظریه اطلاعات و علوم کامپیوتر است. شامل تاریخچه، تئوری، پیشرفت‌های جدید، طیف وسیعی از کاربردها، مجموعه‌های متعدد (جدید) مسائل، نظرات، منابع منبع، و نکاتی برای راه‌حل‌های مشکلات است. این تنها درمان جامع ایده‌های اصلی پیچیدگی کولموگروف و کاربردهای آن است.

`«لی و ویتانی کتابی ایده‌آل برای کاوش در بخش عمیق، زیبا و مهم علوم رایانه ارائه کرده‌اند.» "

-- یوریس هارتمانیس، برنده جایزه تورینگ 1993، دانشگاه کورنل، ایتاکا، نیویورک.

" احتمالاً این کتاب برای مدت طولانی درمان استاندارد پیچیدگی کولموگروف خواهد بود. .''

-- Jorma J. Rissanen، IBM Research، کالیفرنیا.

``"کتاب لی و ویتانی بی نظیر است."

- - Ray J. Solomonoff، تحقیقات آکسبریج، کمبریج، ماساچوست

\"کتاب فوق العاده است... نویسندگان کار خود را به طرز باورنکردنی خوب انجام دادند... خواندن ضروری برای همه نوع خوانندگان از دانشجویان کارشناسی تا بالاتر مقامات در این زمینه.\"

-- ولادیمیر آ. اوسپنسکی و الکساندر کی. شن، مجله منطق نمادین [مرور]

`` مقدمه دقیق و روشن برای یک کتاب ظریف و میدان عمیق.''

--David G. Stork، Ricoh Innovations، کالیفرنیا، آمازون [بررسی]

``"کتاب در مورد پیچیدگی کولموگروف."

This ongoing bestseller, now in its third edition, is considered the standard reference on Kolmogorov complexity, a modern theory of information that is concerned with information in individual objects.

New key features and topics in the 3rd edition:

* New results on randomness

* Kolmogorov's structure function, model selection, and MDL

* Incompressibility method: counting unlabeled graphs, Shellsort, communication complexity

* Derandomization

* Kolmogorov complexity versus Shannon information, rate distortion, lossy compression, denoising

* Theoretical results on information distance

* The similarity metric with applications to genomics, phylogeny, clustering, classification, semantic meaning, question-answer systems

*Quantum Kolmogorov complexity

Written by two experts in the field, this book is ideal for advanced undergraduate students, graduate students, and researchers in all fields of science. It is self-contained: it contains the basic requirements from mathematics, probability theory, statistics, information theory, and computer science. Included are history, theory, new developments, a wide range of applications, numerous (new) problem sets, comments, source references, and hints to solutions of problems. This is the only comprehensive treatment of the central ideas of Kolmogorov complexity and their applications.

``Li and Vitányi have provided an ideal book for the exploration of a deep, beautiful and important part of computer science.''

-- Juris Hartmanis, Turing Award Winner 1993, Cornell University, Ithaca, NY.

``The book is likely to remain the standard treatment of Kolmogorov complexity for a long time.''

-- Jorma J. Rissanen, IBM Research, California.

``The book of Li and Vitányi is unexcelled.''

-- Ray J. Solomonoff, Oxbridge Research, Cambridge, Massachusetts

"The book is outstanding...the authors did their job unbelievably well...necessary reading for all kinds of readers from undergraduate students to top authorities in the field."

-- Vladimir A. Uspensky and Alexander K. Shen, Journal of Symbolic Logic [Review]

``Careful and clear introduction to a subtle and deep field.''

--David G. Stork, Ricoh Innovations, California, Amazon [Review]

``THE book on Kolmogorov Complexity.''

--Lance Fortnow, University of Chicago, IL, Amazon [Review]