Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Обсуждение невозможности полного перебора
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
761 оценки
Из урока
Выравнивания
Насколько похожими являются "кролик" и "икра"? А "хорёк" и "суслик"? Ответы на эти вопросы мы получим в течение этой недели, обсуждая практическое применение комбинаторики в биологии.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Ну вот давайте в завершение вот этой вот науки,
скажем так, биоинформатической вставки, что ли, давайте в завершение этой
биоинформатической вставки, этого приложения замечательного, обсудим
насколько все ж на самом деле плохо, почему нельзя делать полный перебор.
Ну вот давайте представим себе, например, что n равняется m,
равняется 1000, ну вот так, для примера.
Как бы нам осознать, насколько вообще много тогда выравниваний получится?
Мы с вами знаем, что g от (1000, 1000), ну что ж такое, зачем я запятые рисую,
g от (1000, 1000), это есть C из
2000 по 1000, а много это или мало?
Нет, ну есть, конечно, у нас всегда программисты, которые сейчас запустят
прогу какую-нибудь простенькую, она примерно выдаст — чему это равняется,
но это не наш путь, так сказать, это не спортивно,
надо научиться математически оценивать такие выражения, и это, на самом деле,
совсем не сложно смотрите, ясно же, а это мы тоже с вами проходили,
что если сложить все биномиальные коэффициенты,
включая вот этот вот — С из 2000 по 1000.
Так, С из 2000 по 2000,
если вообще все такие биномиальные коэффициенты просуммировать,
то получиться 2, я прошу прощения, в 2000 степени.
Но, конечно, вы мне на это можете возразить: ну так их куча, этих слагаемых,
черт его знает, как устроено вот это вот, оно вообще какое?
Оно большое, оно маленькое, нет, ну понятно совершенно, что каждое слагаемое
положительно, поэтому С из 2000 по 1000 уж никак не больше, или даже строго меньше,
чем 2 в 2000 степени, и вообще говоря, оно могло бы оказаться сильно меньше.
Например, вот это последнее слагаемое равняется 1,
то есть оно не сопоставимо меньше, чем общая сумма.
Но радость заключается в том для нас, или наоборот горе,
потому что очень большое вычисление получится в итоге для биоинформатики.
Горе состоит в том, что вот эта то величина в перечне всех слагаемых, она,
конечно, самая большая.
Это такой совершенно классический факт, его очень легко получить.
Ну как, например?
Давайте посмотрим, что такое С из
2000 по какому-нибудь k,
поделить на С из 2000 по какому-нибудь k + 1,
где k у нас будет не превосходить 999.
Ну то есть мы посмотрим отношение предыдущего
слагаемого в этой сумме к последующему в случае,
когда k не больше 999, то есть самое последнее отношение будет включать в
себя вот это вот предшествующее слагаемое и собственно С из 2000 по 1000.
Давайте посмотрим, как это отношение устроено.
Понятно, что здесь стоит 2000 факториал, здесь стоит k факториал,
2000 минус k факториал.
В знаменателе тоже вылезает 2000 факториал благополучно, 2000 факториал,
здесь k + 1 факториал, вот он перекинулся в числитель,
и 2000 − (k − 1) факториал Так, k + 1 факториал
благополучно практически «кокается» совместно с вот этим k факториалом.
То есть здесь пропадает факториал, а здесь вообще все пропадает,
сверху «выживает» только k + 1, 2000 умирает полностью, без остатка.
И вот эти вот два факториала то же очень-очень хорошо сокращаются,
а именно вот это все пропадает, а здесь пропадает факториал.
Итого у меня остается k + 1, поделенное на (2000 − k).
Так?
И теперь я вспоминаю, что k не превосходит 999,
значит это точно не больше,
чем 1000 поделить на (2000 − k).
Снова k не превосходит 999,
значит (2000 − k) ≥ нежели 1001, а дробь,
соответственно, снова не превосходит 1000 поделить на 1001.
И это меньше строго единицы, то есть мы получаем, что вот эти вот слагаемые,
они благополучно возрастают, а С из 2000 по нулю до С из 2000 по 1000.
Ну я думаю, товарищи, что вы уже достаточно хорошо научились комбинаторике,
что б понять, что дальше все происходит симметрично,
то есть они до сюда возрастают, а потом начинают убывать.
Картинка выглядит вот так: вот здесь находится самое большое слагаемое,
С из 2000 по 1000.
Вот здесь вот где-то находится С из 2000 по 0,
а здесь симметричные ему С из 200 по 2000,
которое ему равно, равно 1 просто.
И тут вот они как-то, вот так вот возрастают, а дальше начинают убывать.
И это не тема, конечно, моей сегодняшней лекции, это,
конечно, самое классическое приложение биномиальных коэффициентов, какое бывает.
Н это так, на вырост, в другом курсе обязательно об этом расскажу сильно
подробнее, но так просто, раз к слову пришлось, я сейчас то же замечу,
это классическая Гауссовская кривая, которая возникает в теории вероятности,
если вы об этом когда-то слышали, классическая Гауссовская кривая, она
появляется просто из того, как соотносится друг с дружкой различные биномиальные
коэффициенты, последовательные биномиальные коэффициенты вот в этом ряду,
суммарно дающим два, там, в какой то n-й степени, например 2000-ой.
В общем, это так, забегая вперед, но это совершенно классическая вещь,
которая работает и в вероятности, и в статистике, и в тех курсах,
которые мы будем предлагать на эту тему, она эта Гуассовская кривая,
будет обязательно возникать неоднократно.
Ну короче говоря, мы выяснили, что вот это вот слагаемое,
оно самое большое среди всех слагаемых, которые присутствуют в сумме.
Но смотрите, всего-то слагаемых 2001 штука,
от 0 до 2000, то есть получается,
что С из 2000 по 1000, но точно никак не меньше,
чем 2 в 2000 степени поделить на 2001.
Просто по принципу Дирихле, раз оно самое большое,
значит оно точно не меньше этой величины.
Ну давайте попробуем прикинуть — чего это в свою очередь не меньше,
и какая катастрофа ожидает любого биолога,
который захочет перебирать все возможные выравнивания.
Вы, конечно, не думайте, что я над кем-то издеваюсь, биологи прекрасно знают,
как обойти это проблему, но для того чтоб нужно было ее обходить,
надо было сначала понять, что ее вообще обходить нужно.
А чтобы это понять, вот надо посчитать количество выравниваний целиком.
Дальше эта задача, конечно, теряет смысл.
Ну давайте скажем, например, что это больше чего?
2001 больше, чем, нет, меньше, извините, меньше, чем 2 в 11 степени.
Значит у нас получается 2 в 2000-ой поделить на 2 в 11-ой.
Это 2 в степени 1989, очень красиво.
Вот, друзья, на самом деле плевать,
я не хочу мучиться и считать аккуратно 2 в 1989-ой степени,
можно сделать при желании очень аккуратно, конечно, но это примерно...
Давайте перейдем просто к основанию 10, чтобы понять, сколько знаков в этом числе.
Давайте перейдем к десятичному нашему обычному исчислению.
Это 10 в степени 1000, нет, это, в точности давайте напишем,
10 в степени 1989 умножить на десятичный логорифм двойки,
а десятичный логорифм двойки, ну это уже результат подсчета на калькуляторе,
или как там вы умеете, приближенного, это что-то типа: 0,3, ну там, ...,
0,301, 0,299, я не помню точно, но в общем 0,3.
Вот. Мне ужасно лень с вашего позволения
считать 1989 умноженное на 0,3.
Но смысл такой, знаков в этом числе,
знаков в это числе, то есть в числе выравнивания,
в этом числе 1989 умножить на 0,3.
Ну примерно, не точно, конечно, но примерно столько.
Ну не буду я это умножать, ясно, что это там больше, чем ну скажем, 500.
Уж точно больше, чем 500.
С огромным запасом.
Я что хочу сказать, число, в котором больше, чем 500 знаков,
это число которое заведомо превосходит, ну я буду издеваться,
вот сейчас я издевался в каком-то смысле над биологами,
которые смеются надо мной и думают — ну зачем такое считать, да.
А теперь я издеваюсь над физиками в какой то степени.
Вот представьте себе, что электрон — такая частичка, да, элементарная?
Это самая такая маленькая частичка, да?
Такой шарик, ну электрон — это, конечно, не шарик,
это я понимаю, что не так жизнь устроена, представьте себе, что это шарик.
И эти шарики плотненько-плотненько так лежат в объеме видимой вселенной,
то есть вот есть огромная вселенная за, там, 10 миллиардов лет расширившаяся
до 10 миллиардов световых лет видимости, так сказать,
вот мы видим звезды или какие-то объекты, которые находятся на расстоянии 10 или
даже больше миллиардов световых лет от нас, и вот эта вся видимая вселенная
плотно-плотно напихана крошечными шариками-электрончиками радиуса,
там, в 10 минус 13 степени сантиметра или что-то такое.
Я не буду сейчас проводить эту дурацкую выкладку, она смешная, конечно,
но я думаю, что вы сами можете ее проделать благополучно.
Примерно прикиньте, сколько получится электрончиков, вот в таком вот,
в такой вот плотной упаковке.
Я уверяю вас, что их меньше, чем 10 в 100-й степени, то есть их меньше,
чем число, которое выражается сотней знаков в десятичной системе исчисления.
А у нас получилось число, в котором больше, чем 500 знаков.
То есть это совершенно необозримое количество.
Конечно, столько операций проделать невозможно.
Это больше, чем количество вот таких вот крошечных шариков, упакованных в объем
всей вселенной, которую мы в принципе можем увидеть, это что-то запредельное.
Поэтому, конечно, надо придумывать какие то дальнейшие соображения,
как комбинаторного, так и иного характера, и эти соображения биологи,
естественно, придумали, эта задача решена, но это уже,
скажем так, материал другого курса.
Это материал на будущее изучение.
Моя цель сегодня была просто продемонстрировать вам, что у той науки,
которую мы изучали, казалось бы очень простой и совершенно развлекательной,
есть замечательные содержательные приложения.
И вот все эти тождества, которые мы, казалось бы, доказывали просто для того
чтобы развлечься, нет, они работают, и они вполне себе свидетельствуют о том,
как растут какие-то вот содержательные величины, необходимые просто для практики.
Надеюсь, что в какой-то степени я убедил вас в этом,
ну а возвращаясь к моей философии, я еще раз скажу, практика — это прекрасно, но
она появилась, и возможность использовать эти задачи появилась на практике только
потому что эти задачи содержательны сами по себе, очень красивые,
и я надеюсь, что в следующих курсах по комбинаторики или по теории вероятности,
или по каким-то другим смежным дисциплинам, которые мы вам предложим,
вы с радостью нас еще послушаете в более продвинутых контекстах.
Ну а на сегодня все.
Спасибо.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
