*https://www.youtube.com/watch?v=vIzoP7iolNw
**https://300.ya.ru/summary
таймкоды
Введение в комбинаторику
- Комбинаторика изучает комбинации и их применение в различных областях.
- Примеры комбинаций: пароли, номера автомобилей, чтение текста.
- Важность расположения символов в тексте.
История комбинаторики
- Комбинаторика началась с игральных костей и подсчета монет.
- Примеры простых задач: выбор монет из шкатулки.
Основная формула комбинаторики
- Формула позволяет разделять сложные задачи на простые.
- Пример: выбор монет разного номинала.
Выборки и их обозначения
- Выборки могут быть с повторением и без повторения, с порядком и без порядка.
- Примеры: сочетание без повторений, размещение с повторениями.
Применение комбинаторики
- Расчет количества автомобильных номеров.
- Оценка числа автомобилей в Москве и Московской области.
- Вероятность получения определенного номера.
Вероятность выиграть в лотерею
- Расчет вероятности для последовательности из 10 чисел.
- Факториалы больших чисел и формула Стирлинга.
Пароли и их надежность
- Зависимость количества комбинаций от длины пароля.
- Важность длинных и сложных паролей.
Генетическое кодирование
- ДНК состоит из 3 млрд пар нуклеотидов и 4 видов оснований.
- Число комбинаций ДНК значительно больше общего числа атомов во Вселенной.
Критический комментарий биохимиков и генетиков
- Не все комбинации ДНК программируют жизнеспособный организм
- Примерно половина генома человека похожа на геном других живых существ
- 5% ДНК являются общими для всех млекопитающих
Проект «Геном Человека»
- Ученые работают над расшифровкой кода ДНК с 1990х годов
- Главная задача — понять назначение каждого участка ДНК
- Полное назначение генетического шифра до сих пор неизвестно
Исследование возможного числа людей
- Обнаружено огромное число разных генов у разных групп людей
- Протестировано около 1 тысячи человек из разных стран
- Возможное число разных вариантов ДНК больше числа атомов во Вселенной
Уникальность каждого человека
- Огромное количество вариантов человеческой ДНК означает огромное число генотипов
- Каждый человек уникален, особенно с учетом личного опыта
- Комбинаторика подтверждает, что каждый человек — единичное событие во Вселенной
Будущее генетики и математики
- Впереди нас ждут грандиозные открытия в области генетики и математики
- Путь к новым открытиям проложен простыми математическими формулами комбинаторики
В этом видео
Эпизоды
Расшифровка видео
Поиск по видео
Введение
0:00
Все люди такие разные и одновременно такие одинаковые. В этом видео мы поговорим о
0:04
математическом разделе комбинаторики, откроем базовые принципы шифрования и основы Генетики.
0:10
Благодарю клуб нумизматов Физтеха за предоставленный реквизит.
Примеры комбинаций
0:14
Итак, комбинаторика, исходя из названия, это наука о комбинациях. С комбинациями мы встречаемся
0:19
повсеместно: когда вводим пароли, когда смотрим на номера автомобилей, когда просто читаем.
0:24
Ведь когда вы читаете, вы расшифровываете информацию, которая содержится в тексте.
0:29
При этом всё многообразие языка фактически, заложено в его алфавите. Из 33 русских букв
0:34
можно составить любой текст. Но важны не сами символы,
0:38
а их расположение в тексте. Из букв можно составить самые разные слова,
0:42
но лишь немногие из этих комбинаций будут иметь смысл. Например, точно известно, что в Русском
0:47
языке есть всего-навсего около 130 тысяч слов. Получается, что всё важное и полезное кроется не
0:53
в самих буквах, а именно в их комбинациях. Но у комбинаторики есть огромное значение
0:57
не только для языка, но и вообще для любой науки об информации. И чтобы понять базовые
С чего начиналась комбинаторика?
1:02
основы кодирования информации, начнем с того же самого, с чего начиналась наука
1:06
комбинаторики около 400 лет назад. А начиналась она с игральных костей
1:11
и подсчета монеток. Давайте начнем также. Попробуем посчитать число возможных исходов
Первые шаги и логика простых задач
1:16
вытащить одну монетку из шкатулки. Допустим внутри находится всего
1:20
2 одинаковые монеты. Очевидно, что существует всего 2 возможных исхода:
1:25
можно выбрать первую или вторую монетку. Добавим еще 3 монетки, и теперь выбрать 1
1:31
монетку из 5 возможно 5 разными способами. Пока всё, надеюсь, очевидно и интуитивно понятно.
1:37
Но усложним задачу: попробуем вытащить 2 монетки из пяти. Здесь мы можем вручную посчитать все
1:43
возможные варианты. Можно вытащить эту пару, эту, эту и тд. Всего получится 10 разных вариантов.
1:52
То есть крошечное изменение условия задачи сильно эту задачу усложнило. А что, если мы
Основная формула комбинаторики
1:57
возьмём большое число монет разного номинала. Конечно, можно посчитать все варианты вручную,
2:02
но это займет много времени. Но прелесть математики в том, что она позволяет
2:06
всё сложное разделять на простые шаги. И для наших целей идеально подходит основная
2:11
формула комбинаторики, которая позволяет любую сложную задачу разделять на несколько простых.
2:13
Так мы можем выделять любые признаки и распределять объекты по этим признакам.
2:17
Например, монеты удобно распределить по номиналам, посчитать выборку отдельно для каждого номинала,
2:22
а затем просто перемножить результаты. Пусть у нас есть такой набор монет и
2:27
нам нужно выбрать 2 цента и 1 четвертак. Вариантов выбрать 1 четвертак всего 3. И,
2:34
как мы считали ранее, выбрать 2 цента из 5 можно 10 способами. Перемножим,
2:39
получим конечный ответ: 30 вариантов. Еще раз подчеркну, сложная задача разделилась
2:44
на две простые. И Эту схему мы можем применять для любого количества монет, номиналов,
2:50
да и вообще для любых множеств любых объектов. Мы с вами на этом канале уже видели очень похожую
2:55
формулу перемножения вероятностей, Мы говорили, что по этой формуле продавцы ищут клиентов,
3:00
парни ищут девушек, а политические деятели ищут единомышленников.
3:05
Эти формулы очень похожи и буквально выводятся друг из друга для независимых событий.
3:09
Попробуем формализовать наши эксперименты. Наш эксперимент с пятью центами называется выборкой
Выборки и их обозначения
3:15
ДВУХ из ПЯТИ и записывается так. Буква m означает сколько мы выбираем, а n – из скольки мы выбираем.
3:25
А вот буква С означает то, как мы выбираем. И существует несколько способов выборки.
3:31
Эти способы называются «комбинаторная конфигурация». Но несмотря на кажущуюся
3:35
сложность термина, всё крайне легко. Мы уже рассмотрели самый простой способ выборки.
3:41
Если нам не важен порядок монет, то эта выборка обозначается буквой C/
3:46
Если нам всё-таки важен порядок монет, или например, мы раскладываем монеты в определенном
3:50
порядке, то такие выборки обозначаются буквой A. Также можно поставить условие, что один и тот же
3:57
элемент может использоваться несколько раз. Тогда наше обозначение дополняется тильдой сверху.
Все комбинаторные конфигурации подробно
4:02
Рассмотрим все способы подробно. Наверное, самый простой способ – это
4:06
сочетание без повторений. Здесь нам не важен порядок выпадения предметов, а предметы не могут
4:12
повторяться, так как мы их изымаем из коробки. Если же мы повторим то же самое, но каждый
4:17
предмет будет возвращаться в шкатулку, то это будет сочетание с повторениями,
4:22
формула немного другая. Здесь одна и таже монетка может выпасть несколько раз.
4:27
Теперь другой эксперимент, будем записывать порядок выпадения монет. Очевидно,
4:32
в таком случае порядок элементов важен, а повторов быть не может. Это размещение без повторений.
4:40
Если же мы станем записывать элементы и возвращать их обратно, то это размещение с повторениями,
4:45
что описывается самой простой формулой. Фактически, для решения любой задачи надо просто
Та самая таблица
4:49
ответить на 2 вопроса: важен ли порядок элементов? И можно ли повторять один и тот же элемент?
4:56
Всё очень легко. Обратите внимание, что для некоторых подсчетов используется факториал,
5:01
в котором тоже нет ничего сложного. Давайте посчитаем сколько всего может
Сколько может быть автомобильных номеров?
5:05
существовать российских автомобильных номеров. Пока будем считать без кода региона.
5:10
Номера состоят из 3 букв и 3 цифр, и есть ограничения на
5:14
использование некоторых сочетаний. По основной формуле комбинаторики,
5:18
цифры и буквы можно считать отдельно. Порядок здесь важен, а повторять
5:22
символы можно, то есть это размещение с повторениями. Всего комбинаций цифр столько,
5:26
а комбинаций букв столько. Перемножаем и получаем практически 2 млн номеров.
5:31
В России есть города, где этого числа номерных знаков не хватает,
5:34
рекордсменами здесь являются Москва и Московская Область. Мы можем даже из этих данных оценить
Сколько в Москве и области автомобилей?
5:38
максимальное число автомобилей в Столице. Если на каждый код региона приходится по 1.7
5:41
млн легковых и грузовых автомобилей, то в Москве И Московской области принципиально
5:46
возможно зарегистрировать 27.6 млн автомобилей. Есть данные по устаревшим номерным кодам,
5:53
их 13 штук, а значит в Москве и Области автомобили регистрировались 22.4 млн раз.
6:01
Конечно, это не значит, что в Москве столько автомобилей, но
6:04
цифры в любом случае катастрофически большие. Так известно, что ежедневно на улицы Москвы выезжают
6:10
700 тысяч автомобилей, которые ежедневно устраивают около 300 серьёзных ДТП.
6:15
Но это еще не всё. Если мы посчитаем вероятность получения определенного автомобильного госномера,
Редкость и цена автомобильных номеров.
6:21
то окажется, что вероятность ничтожна мала. Если вы хотите получить определенную комбинацию,
6:23
то случайно получить её практически невозможно, поэтому в России существует очень непонятный
6:26
для меня рынок автомобильных номеров, люди готовы платить огромные деньги за
6:30
цифры на бампере. Много это или мало? Сравним с чем-нибудь. Зарплата молодого
Сколько зарабатывает российский ученый?
6:33
ученого в России составляет около 20 тысяч рублей в месяц, с грантами и надбавками выходит около
6:39
60-80 тысяч рублей. Также для потомков приведу стоимость аренды жилья в Москве.
6:47
То есть чтобы получить прикольный номер на бампер молодому кандидату наук нужно работать 2 года,
6:53
нигде не жить и ничего не кушать. Вывод такой: Кандидаты наук с
6:57
такими номерами не ездят. Но не будем о грустном и вернемся
Вероятность выиграть в лотерею
7:01
к комбинаторике. Еще парочка задач. Посчитаем вероятность выиграть в лотерею.
7:04
Допустим, нам нужно собрать определенную последовательность из 10 чисел, причем
7:08
числа могут быть от 1 до 100. В лотереях чаще всего последовательность важна, значит важен
7:14
порядок. При этом числа не могут повторяться. Значит формула и вероятность будут такими.
7:19
Не играйте в лотереи, вероятность победить нулевая, а всё, что вам
7:23
говорят про лотереи – это просто наглая реклама. Обратите внимание, что один из факториалов в этом
Как считать факториалы больших чисел?
7:29
решении даёт огромное значение. Некоторые калькуляторы не способны считать факториалы
7:34
больших чисел. В таком случае используют приближенную формулу Стирлинга.
Зачем нужны длинные надежные пароли?
7:38
И если мы уже познакомились с большими числами, то давайте поговорим о паролях. Обычно пароли состоят
7:44
из определенных знаков, которых насчитывается 128 штук. На этом графике приведена зависимость общего
7:50
количества вариантов комбинаций от числа знаков в пароле. Очевидно, что чем больше знаков в пароле,
7:56
тем сложнее злоумышленникам перебрать все варианты. Посмотрите, сколько комбинаций
8:01
может быть для пароля из 24 символов, перебрать их все практически невозможно.
8:06
Именно поэтому многие сайты заставляют вас придумывать длинные сложные пароли.
8:11
А теперь дадим ответ на животрепещущий вопрос: Каков твой генетический код?
Генетическое кодирование и число комбинаций ДНК
8:17
ДНК, как вы знаете – это спиральная молекула, которая хранит генетическую информацию.
8:21
Известно, что в ДНК есть чуть больше 3 млрд пар нуклеотидов, которые могут состоять из
8:26
4х видов оснований. Если по-простому, в ДНК существует 3 миллиарда ячеек, которые могут
8:31
быть заполнены 4 возможными значениями. Очевидно, что повторы элементов возможны,
8:36
а порядок элементов важен. В Итоге мы получаем вот такое число.
8:41
Представьте себе, что это число значительно больше общего числа
8:45
атомов в обозримой части Вселенной. Конечно, биохимики и генетики уже пишут
8:50
критический комментарий! Ведь не все комбинации программируют жизнеспособный организм. Здесь как
8:56
в русском языке – не все комбинации имеют смысл. Действительно, вот в этой статье утверждается,
9:02
что примерно половина нашего генома – очень похожа на геном любого другого живого существа,
9:06
то есть она практически не может меняться. Еще 5% ДНК являются общими для всех млекопитающих. Также
9:13
многое можно сказать о не кодирующих генах, которых в нашем организме достаточно.
9:18
И к сожалению, пока никто не может оценить точное значение работоспособных вариантов
Проект «Геном Человека»
9:22
генома. С 1990х годов ученые работают над проектом генома человека, а также проектом транскриптома
9:28
человека. Главной задачей учёных является полная расшифровка кода ДНК. Они пытаются понять,
9:34
какие участки ДНК что программируют. К сожалению, даже спустя десятилетия мы точно не знаем полное
9:40
назначение нашего генетического шифра, хотя кое-какие успехи, конечно, есть.
Исследование возможного числа людей
9:45
Например, в этой статье обнаружили огромное число разных генов у разных групп людей.
9:50
Было протестировано около 1 тысячи людей из разных стран и показано, что только среди этих
9:54
людей потенциально может быть вот такое гигантское число разных вариантов ДНК.
9:59
Хоть эта оценка значительно меньше, чем грубый подсчет комбинаций, но это всё равно больше,
10:04
чем то самое число атомов во вселенной. И Да, воспринимайте это число как минимальную оценку.
10:11
Огромное количество вариантов человеческой ДНК означает,
10:14
что возможное число генотипов людей огромно. Каждый из вас абсолютно уникален, особенно
10:19
если дополнительно учесть ваш личный опыт. Комбинаторика прямо говорит, что вы — это
10:24
единичное событие во Вселенной, которого никогда не было и никогда больше не будет.
10:29
Уважайте себя и других людей, ведь каждый из нас — неповторим.
10:33
Мы многое еще не знаем, и впереди нас ждут грандиозные открытия в области
10:37
генетики и математики, в будущем мы сможем узнать еще больше о самих себе. Но путь
10:42
уже абсолютно ясен – он проложен простыми математическими формулами комбинаторики.
10:49
Спасибо. Кстати, книга, которую я
10:53
демонстрировал в начале, скоро будет разобрана на этом канале. Поэтому присоединяйтесь!
