Настоящая книга возникла как методическое пособие к курсам лекций, которые автор в разные годы читал и до сих пор читает на факультете биоинженерии и биоинформатики МГУ, на факультете инноваций и высоких технологий МФТИ, в совместном бакалавриате Российской экономической школы и Высшей школы экономики, в Школе анализа данных Яндекса. Все эти курсы объединены наличием в них базовой составляющей по комбинаторике и теории вероятностей. Иными словами, в основе каждого из них лежит некоторое количество простых понятий и фактов, которые возникают в указанных дисциплинах и без которых невозможно понимание более специфических - так сказать, "продвинутых" - результатов. Многие из этих фактов и понятий есть в классических учебниках и монографиях. Однако, во-первых, они разбросаны по разным книгам, а во-вторых, помимо них, эти книги содержат и массу другой информации. Как следствие, оказывается, что нет удобного источника, где были бы собраны и надлежащим образом позиционированы эти и только эти факты и понятия. По сути предлагаемая книга заполняет этот пробел. В книге сжато, лаконично и достаточно неформально вводятся все необходимые объекты и даются все необходимые утверждения о них. Если доказательство теоремы имеется в стандартном учебнике, то, как правило, оно не воспроизводится; на него лишь ставится удобная ссылка. Зато если доказательство мало доступно или нигде популярно не изложено, то ему уделяется значительное внимание. Например, так сделано в отношении формулы обращения Мёбиуса, которую мало где подробно обсуждают, или в отношении задач об оценках комбинаторных величин, которые крайне важны, но обычно возникают "сами собой" в чисто профессиональной литературе, и читатель вынужден догадываться, какие идеи за этим стоят. Есть в книге и достаточно нетривиальные вещи, характерные для курсов автора. Например, в той части, которая посвящена теории вероятностей, обсуждаются формулы обращения, позволяющие выразить распределения дискретных величин через их моменты (это очень важно в приложениях: например, для случайных графов), а также мартингалы (в дискретном случае) и некоторые связанные с ними неравенства концентрации меры. Эти вещи описаны так же неформально и без чрезмерного углубления в детали, как и все остальное. Однако так и проще не потеряться в дебрях материала. По аналогичному принципу устроены задачи, которые предлагаются в конце каждой темы. Таким образом, книга позволит четко систематизировать информацию, разбросанную по разным учебникам и задачникам (а зачастую и просто недоступную), и даст тот ее минимум, который необходим для адекватного восприятия курсов по комбинаторике, информатике, теории графов, теории алгоритмов, теории вероятностей и др.
Nastoyashchaya kniga voznikla kak metodicheskoe posobie k kursam lektsiy, kotorye avtor v raznye gody chital i do sikh por chitaet na fakultete bioinzhenerii i bioinformatiki MGU, na fakultete innovatsiy i vysokikh tekhnologiy MFTI, v sovmestnom bakalavriate Rossiyskoy ekonomicheskoy shkoly i Vysshey shkoly ekonomiki, v SHkole analiza dannykh YAndeksa. Vse eti kursy obedineny nalichiem v nikh bazovoy sostavlyayushchey po kombinatorike i teorii veroyatnostey. Inymi slovami, v osnove kazhdogo iz nikh lezhit nekotoroe kolichestvo prostykh ponyatiy i faktov, kotorye voznikayut v ukazannykh distsiplinakh i bez kotorykh nevozmozhno ponimanie bolee spetsificheskikh - tak skazat, "prodvinutykh" - rezultatov. Mnogie iz etikh faktov i ponyatiy est v klassicheskikh uchebnikakh i monografiyakh. Odnako, vo-pervykh, oni razbrosany po raznym knigam, a vo-vtorykh, pomimo nikh, eti knigi soderzhat i massu drugoy informatsii. Kak sledstvie, okazyvaetsya, chto net udobnogo istochnika, gde byli by sobrany i nadlezhashchim obrazom pozitsionirovany eti i tolko eti fakty i ponyatiya. Po suti predlagaemaya kniga zapolnyaet etot probel. V knige szhato, lakonichno i dostatochno neformalno vvodyatsya vse neobkhodimye obekty i dayutsya vse neobkhodimye utverzhdeniya o nikh. Esli dokazatelstvo teoremy imeetsya v standartnom uchebnike, to, kak pravilo, ono ne vosproizvoditsya; na nego lish stavitsya udobnaya ssylka. Zato esli dokazatelstvo malo dostupno ili nigde populyarno ne izlozheno, to emu udelyaetsya znachitelnoe vnimanie. Naprimer, tak sdelano v otnoshenii formuly obrashcheniya Myebiusa, kotoruyu malo gde podrobno obsuzhdayut, ili v otnoshenii zadach ob otsenkakh kombinatornykh velichin, kotorye krayne vazhny, no obychno voznikayut "sami soboy" v chisto professionalnoy literature, i chitatel vynuzhden dogadyvatsya, kakie idei za etim stoyat. Est v knige i dostatochno netrivialnye veshchi, kharakternye dlya kursov avtora. Naprimer, v toy chasti, kotoraya posvyashchena teorii veroyatnostey, obsuzhdayutsya formuly obrashcheniya, pozvolyayushchie vyrazit raspredeleniya diskretnykh velichin cherez ikh momenty (eto ochen vazhno v prilozheniyakh: naprimer, dlya sluchaynykh grafov), a takzhe martingaly (v diskretnom sluchae) i nekotorye svyazannye s nimi neravenstva kontsentratsii mery. Eti veshchi opisany tak zhe neformalno i bez chrezmernogo uglubleniya v detali, kak i vse ostalnoe. Odnako tak i proshche ne poteryatsya v debryakh materiala. Po analogichnomu printsipu ustroeny zadachi, kotorye predlagayutsya v kontse kazhdoy temy. Takim obrazom, kniga pozvolit chetko sistematizirovat informatsiyu, razbrosannuyu po raznym uchebnikam i zadachnikam (a zachastuyu i prosto nedostupnuyu), i dast tot ee minimum, kotoryy neobkhodim dlya adekvatnogo vospriyatiya kursov po kombinatorike, informatike, teorii grafov, teorii algoritmov, teorii veroyatnostey i dr.
The book is a textbook on combinatorics and probability theory. It arose on the basis of lectures on combinatorics, computer science, probability theory, which its author in different years read and continues to read at the faculty of bioengineering and bioinformatics, Moscow state University. M. V. Lomonosov, School of Data Analysis Yandex, Moscow Institute of physics and technology and a joint undergraduate Russian Economic School and the Higher school of Economics.
The items that were the subject of the book, contained therein fairly informal, allowing the reader to quickly understand their meaning. More details in the book are stated the vehicle sections, which are rarely discussed in detail in the literature. Conversely, those sections that are easy to study by standard textbooks, the book painted a concise - with links to classical sources.
Study guide will be useful for students, beginners, professionals and anyone interested in the basics of combinatorics and probability.
Expected