Probabilistic Methods for Algorithmic Discrete Mathematics

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

The book gives an accessible account of modern pro- babilistic methods for analyzing combinatorial structures and algorithms. Each topic is approached in a didactic manner but the most recent developments are linked to the basic ma- terial. Extensive lists of references and a detailed index will make this a useful guide for graduate students and researchers. Special features included:
- a simple treatment of Talagrand inequalities and their applications
- an overview and many carefully worked out examples of the probabilistic analysis of combinatorial algorithms
- a discussion of the "exact simulation" algorithm (in the context of Markov Chain Monte Carlo Methods)
- a general method for finding asymptotically optimal or near optimal graph colouring, showing how the probabilistic method may be fine-tuned to explit the structure of the underlying graph
- a succinct treatment of randomized algorithms and derandomization techniques