Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Пароль к компьютеру
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
733 оценки
Из урока
Правило сложения и умножения. Принцип Дирихле
Правило сложения. Правило умножения. Принцип Дирихле.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Так, ну давайте разберём ещё одну несложную задачу,
даже с несколькими пунктами, впрочем, которая будет ну, не знаю, на правила
умножения и на какое-то дополнительное соображение, которое позволяет быстрее
что-то посчитать, не прибегая к сложным записям, суммированиям и так далее.
Значит, задача очень естественная.
Вот есть пароль к компьютеру, как он может быть устроен,
там могут быть разные символы, конечно.
Но давайте считать, что в рамках этой задачи, пароль к компьютеру состоит из
цифр и маленьких букв латинского алфавита.
Так, давайте это напишем.
Есть пароль, и он может состоять из цифр и из маленьких букв латинского алфавита.
Это не очень хорошо, на самом деле, с точки зрения компьютерной безопасности.
Маленькие буквы латинского алфавита.
Не очень хорошо в том смысле, что зачастую требуется, чтоб была хотя бы одна большая
буква, но я просто не желаю усложнять с комбинаторной точки зрения задачу.
Для простоты разбираю тот случай, когда ничего, кроме вот этих двух вариантов,
использовано в паролях быть не может.
Вот спрашивается несколько вопросов.
Ну давайте в пункте «а» зададимся вопросом,
сколько вообще существует таких паролей длины 8.
Что вот сколько таких паролей длины восемь.
Ну давайте с этого и начнём,
Ну давайте с этого и начнём,
то есть потом позже я озвучу соответственно пункт «б» и пункт «в».
Всего будет три пункта.
Ну этот вопрос совсем простой, конечно, потому что, смотрите,
ну сколько всего цифр на свете имеется.
Понятно, что цифр на свете имеется десять штук.
У нас есть в распоряжении десять цифр и у нас есть в распоряжении,
помимо этого, маленькие буквы латинского алфавита, каковых естественно 26,
как впрочем и больших букв того же алфавита.
26 букв.
Ну поскольку большие не используются, то у нас только 26 вариантов.
Итого тот, так сказать, «пул» возможностей, которыми мы пользуемся,
он состоит из 36 символов.
Итого 36 символов,
каждый из которых мы вольны поставить на любую позицию нашего будущего пароля.
Ну а, стало быть, смотрите, на первую позицию пароля, на первую позицию пароля
мы можем поставить любую из 36, любой из 36 вот этих символов.
Итак, у нас есть 36 возможностей, как начать,
так сказать, наш пароль, с чего начать его строить.
Соответственно, если мы хотим заполнить вторую позицию,
у нас же нет никаких ограничений,
мы на вторую позицию можем спокойно поставить тоже любой из этих 36 символов.
И естественно, поскольку мы это делаем вслед за тем,
как что-то выбрали для первой позиции, то мы пользуемся правилом умножения,
которое я уже начал рисовать и домножаем на 36.
Ну и так далее.
На третью позицию у нас снова есть 36 возможностей того,
что поставить, поскольку это делается вслед за 1296 возможностями,
которые уже перечислены — вот эти 36 в квадрате,
то надо снова эти 36 в квадрате умножить на 36, и так далее,
покуда не исчерпаются все наши позиции, каковых в нашей задаче восемь штук.
То есть на каждую позицию можно поставить символ любым из 36 способов.
Это делается независимо с точки зрения позиций и мы получаем 36 в 8 степени.
Очень простой ответ, который в очередной раз иллюстрирует,
как устроено правило умножения.
Ну давайте усложним себе задачу.
Давайте рассмотрим следующий пункт «б»,
по-прежнему будем искать количество паролей, которые имеют длину 8.
То есть вот 8 мы за собою закрепим.
Но на сей раз давайте посмотрим, а сколько таких паролей длины 8,
сколько таких паролей, [ПИШЕТ
НА ДОСКЕ] если в каждом из них обязательно присутствует хотя бы одна цифра.
Если в каждом из них
обязана присутствовать цифра.
Ну так, в общем, зачастую и требуют, когда создают пароли.
Обязана присутствовать цифра, хотя бы одна, может быть, несколько.
[ПИШЕТ НА ДОСКЕ] Можно
подойти к этой задаче глупо, то есть можно начать перебирать ситуации.
И, в общем, это в каком-то смысле ловушка, в которую попадаются очень многие,
когда начинают решать подобные задачи.
То есть можно сказать так, но давайте посчитаем, сколько есть паролей, в которых
присутствует цифра 0, сколько есть паролей, в которых присутствует цифра 1.
Но там какие-то есть пересечения ситуации,
потому что может одновременно присутствовать 0 и 1.
Причём мы не оговариваем, сколько раз.
И возникает какая-то бешеная страшная сумма,
от которой у человека начинает двоиться в глазах.
Но, на самом деле, никакая сумма не нужна, а по хорошему счёту нужна разность,
А именно: вот сколько паролей, если в каждом из них присутствует цифра?
Ну а давайте проще посчитаем.
Давайте, наоборот, посчитаем, сколько есть паролей, в которых нет ни одной цифры.
Вот давайте посмотрим число
паролей без цифр.
Вот эта задача совершенно аналогична задаче из пункта «а»,
потому что, если мы не используем цифры, то это просто означает,
что на каждую позицию в нашем распоряжении имеется не 36 символов, а только 26,
ведь ни одну из цифр ни на одну из позиций мы ставить в этом случае не собираемся,
когда говорим о количестве паролей, не содержащих цифру.
Ну естественно это число просто равняется 26 в восьмой.
Ровно по тому же принципу, по которому 36 в восьмой было в пункте «а».
Итак, это число паролей без цифр.
Число всех паролей — это 36 в восьмой.
Но, стало быть, число паролей, которые содержат хотя бы одну цифру,
но это разность общего числа паролей и числа паролей,
которые напротив цифры не содержатся.
То есть вот эта величина, которая ищется в пункте «б» — это есть
просто 36 в восьмой степени − 26 в восьмой степени.
Вот знаете, друзья, в этом месте я не готов считать в уме, что получится.
Если вам очень хочется, можете это проделать,
можете написать какое-нибудь тождество с разностью квадратов,
это как вам нравится, но сути к решению это, конечно, не прибавит.
Понятно, что вот это вполне осязаемый ответ и с ним уже можно
дальше как-то работать.
Вот.
Ну и давайте ещё одну аналогичную задачу, но так,
чтобы в ней немножко по-другому использовалось правило умножения.
Пункт «в».
А сколько таких паролей, опять же длины восемь естественно,
сколько таких паролей,
если в них присутствуют совпадающие символы.
если в них присутствуют совпадающие символы.
Если в них есть ну хотя бы два, может быть и больше, конечно,
есть совпадающие символы.
если в них присутствуют совпадающие символы.
При этом, видите, мы никак не оговариваем,
присутствует в этих паролях буквы, цифры.
Всё что угодно может присутствовать, но мы требуем,
чтоб были хотя бы два совпадающих символа.
Например, две одинаковых буквы.
Или три одинаковых буквы.
Или три одинаковых буквы и две одинаковых цифры.
Опять, вот если начать в этой каше вариться, пытаться как-то напрямую
считать, то получится лабуда, получится какая-то страшная сумма,
в которой вы закопаетесь, и ничего хорошего в итоге не увидите.
Никакого света в конце тоннеля.
Вот. А если пользоваться принципом, который мы
применили, когда решали задачу из пункта «б», то всё получается совсем просто.
Действительно, давайте просто возьмём общее количество паролей,
которое как мы уже не раз проговаривали, равняется 36 в восьмой степени.
И из этого общего количества вычтем количество тех паролей,
в которых, напротив, все символы различны.
Ведь нас-то интересует количество паролей, в которых есть совпадающие символы.
Но его можно посчитать как количество всех паролей, минус количество,
давайте я так и напишу: минус количество паролей, в которых все символы различны.
В которых все
символы различны.
Ну и давайте напишем, что это такое.
36 в 8 минус… Как почитать количество паролей, в которых все символы различны?
Значит, символов по-прежнему в нашем распоряжении изначально 36 штук,
потому что в этой задаче мы никак не оговариваем: присутствуют буквы – не
присутствуют буквы, присутствуют цифры – отсутствуют цифры, — ничего не говорится.
Есть просто 36 символов и как хотите их них ляпайте свои пароли,
только бы все символы в ваших паролях, вот здесь уже после минусов, были различны.
Ну как можно такой пароль сляпать?
Мы можем на первую позицию этого пароля поставить любой из тех 36 символов,
которые, как я уже говорил, имеются в нашем распоряжении.
Что на первую позицию у нас есть 36 возможностей.
А вот на вторую позицию, на вторую позицию,
когда уже выбран какой-то символ для первой одним из вот этих 36 способов,
у нас остаётся только 35 возможностей, потому что на первую позицию какой-то
символ поставлен, а мы считаем такие пароли, у которых символы не совпадают.
То есть на вторую позицию мы обязаны выбрать какой-то новый символ из уже
меньшего количества оставшихся в нашем распоряжении.
Изначально их было 36, но мы поставили что-то на первую позицию,
и теперь мы вынуждены выбирать из оставшихся тридцати пяти,
чтобы никаких повторений не возникло.
Поскольку мы это делаем последовательно,
то естественно по правилу умножения надо написать значок «умножить».
Ну и дальше рассуждая точно так же, умножаем на 34, потому что после того,
как мы уже выбрали два разных символа на первые две позиции нашего пароля,
у нас остаётся только 34 возможности для выбора третьего символа на
третью позицию нашего пароля.
Так, на четвёртую позицию остаётся 33 возможности, на пятую — 32,
на шестую — 31, на седьмую — 30, и на восьмую — 29.
Ну давайте ещё раз перепроверим: на первую — 36, на вторую — 35,
на третью — 34, на четвёртую — 33,
на пятую — 32, на шестую —31, на седьмую — 30 и на восьмую — 29.
Да, всё правильно.
Но разумеется, в этом случае я тоже не собираюсь отыскивать численное значение
этой разности, потому что суть полностью понятна и было бы нелепо,
если б вы решали такую задачу переводом или писали какую-то жуткую сумму.
Вот вполне разумный и симпатичный ответ в такой задаче.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
