Комбинаторика_презентация

1.

Т ЕО Р И Я В Е Р О Я Т Н О С Т Е Й И М АТ Е М АТ И Ч ЕС К А Я С ТАТ И С Т И К А
Введение в теорию
вероятностей. Упорядоченные
выборки. Перестановки
Раздел 1. Элементы комбинаторики
n!
Решетняк Анастасия Николаевна
1

2.

Зачем это программисту
Стойкость паролей
Тестирование
Сколько существует паролей заданной длины и за какое
время их можно перебрать
Сколько конфигураций нужно проверить и какие из них
можно не проверять
Надёжность систем
Анализ данных
Вероятность отказа узла, резервирование, оценка времени
безотказной работы
Оценка качества моделей, A/B-тесты, выводы по выборке
Общее у всех четырёх задач одно: сначала нужно посчитать, сколько всего существует вариантов. Именно этим и
занимается комбинаторика — раздел математики о подсчёте числа комбинаций.
2

3.

01
БЛОК 1
Введение в теорию
вероятностей
Что она изучает и почему начинается с комбинаторики
3

4.

Два типа явлений
Детерминированные
Случайные
Результат однозначно определён условиями. При тех же
условиях он повторится точно.
При одних и тех же условиях результат может оказаться
разным, и заранее он неизвестен.
Пример: Тело падает с высоты 20 м — время падения
вычисляется по формуле
Пример: Бросок монеты, отказ сервера, число посетителей
сайта за час
Теория вероятностей — раздел математики, изучающий закономерности случайных явлений.
Отдельный случайный исход предсказать нельзя. Но при большом числе повторений случайные явления обнаруживают
устойчивые закономерности — их и описывает теория вероятностей.
4

5.

Как появилась наука
1654
Паскаль и Ферма
Переписка о задачах азартных игр: как справедливо разделить ставку, если игра
прервана. Принято считать началом теории вероятностей
1713
Якоб Бернулли
Труд «Искусство предположений»: закон больших чисел — устойчивость частоты
при многих испытаниях
XIX век
Лаплас, Гаусс, Чебышёв
Теория выходит за пределы игр: астрономия, теория ошибок измерений,
демография
1933
А. Н. Колмогоров
Строгое аксиоматическое построение теории вероятностей — она становится
полноценной математической дисциплиной
5

6.

Почему нужна комбинаторика
В следующем разделе курса появится классическое определение вероятности:
P(A) = m / n
n
общее число всех возможных равновероятных
исходов
m число исходов, благоприятствующих событию A
Чтобы найти вероятность, нужно уметь посчитать n и m. В простых задачах исходы можно перечислить вручную, но
их бывают миллионы. Комбинаторика даёт формулы, позволяющие посчитать количество вариантов, не
выписывая их.
6

7.

Когда перечислить уже нельзя
Бросок монеты
Бросок кости
Два броска кости
PIN-код из 4 цифр
Пароль из 6 символов
2
6
36
10 000
≈ 5,7 · 10¹⁰
Орёл, решка. Легко
выписать
Шесть граней. Тоже
несложно
Уже нужна таблица
Вручную не выписать
Только по формуле
7

8.

02
БЛОК 2
Правило суммы и правило
произведения
Два основных принципа подсчёта
8

9.

Правило суммы
Если объект A можно выбрать m способами, а объект B — n способами, причём эти выборы взаимно исключают
друг друга, то выбрать «A или B» можно m + n способами.
N=m+n
ПРИМЕР
ГЛАВНОЕ УСЛОВИЕ
В группе 12 юношей и 8 девушек. Сколькими способами
можно выбрать одного дежурного?
Выборы не должны пересекаться. Нельзя выбрать
одновременно и юношу, и девушку: дежурный один.
12 + 8 = 20
Если множества пересекаются, простое сложение даст
завышенный результат.
Слово-подсказка в условии задачи: «или».
9

10.

Правило произведения
Если объект A можно выбрать m способами и после каждого такого выбора объект B — n способами, то пару «A и
B» можно выбрать m · n способами.
N=m·n
напиток 1
суп 1
ПРИМЕР
напиток 2
В меню 3 супа и 2 напитка. Сколько разных
обедов можно составить?
напиток 1
старт
суп 2
напиток 2
3·2=6
напиток 1
суп 3
напиток 2
3 супа
× 2 напитка
На схеме слева показан упрощённый случай без
вторых блюд.
= 6 обедов
Слово-подсказка в условии задачи: «и». Правило распространяется на любое число этапов выбора.
10

11.

Как не перепутать: «и» или «или»
Признак
Правило суммы
Правило произведения
Ключевое слово
«или», «либо»
«и», «затем», «после этого»
Что происходит
Выбираем что-то одно из нескольких групп
Выбираем по одному из каждой группы
Действие
Складываем
Умножаем
Пример
Взять яблоко или грушу
Взять яблоко и грушу
Условие применения
Группы не пересекаются
Число вариантов на этапе не зависит от
предыдущего выбора
?
Проверьте себя: в кафе 5 видов кофе и 3 вида чая. Сколькими способами можно выбрать один напиток? А
сколькими — взять один кофе и один чай?
11

12.

ПРИМЕР ИЗ ПРАКТИКИ
Матрица тестирования
Веб-приложение нужно проверить на всех сочетаниях браузера, операционной системы и разрешения экрана.
Браузеры
3
Chrome, Firefox, Safari
Операционные системы
×
4
Windows, macOS, Linux, Android
Разрешения экрана
×
2
десктопное и мобильное
3 · 4 · 2 = 24 конфигурации
Если на каждую конфигурацию уходит 40 минут ручного тестирования, полная проверка займёт 16 часов. Отсюда практический
вывод: полный перебор конфигураций обычно невозможен, и его заменяют выбором наиболее значимых сочетаний.
12

13.

Факториал
Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n включительно.
n! = 1 · 2 · 3 · … · n
0! = 1
ЗНАЧЕНИЯ
1!
1
2!
2
3!
6
4!
24
5!
120
6!
720
7!
5 040
8!
40 320
9!
362 880
10!
3 628 800
Полезное свойство: n! = n · (n − 1)! Поэтому 8! / 6! = 8 · 7 = 56 — сокращать факториалы проще, чем вычислять их полностью
13

14.

04
БЛОКИ 4–5
Размещения и перестановки
Упорядоченные выборки: порядок элементов имеет значение
14

15.

Два вопроса к любой задаче на подсчёт
1
Важен ли порядок?
2
Возможны ли повторения?
Различаются ли выборки, состоящие из одних и тех же
элементов, но расположенных иначе?
Может ли один и тот же элемент попасть в выборку
несколько раз?
Пароль «АБВ» и «ВБА» — разные. Набор призёров без
указания мест — одинаковый
В PIN-коде цифра может повторяться. Один человек не
может занять два места сразу
15

16.

Размещения без повторений
Размещением из n элементов по k называется упорядоченная выборка k различных элементов из n имеющихся.
Akn = n! / (n − k)!
Akn = n(n−1)…(n−k+1)
ОТКУДА БЕРЁТСЯ ФОРМУЛА
1-й элемент
n способов
·
2-й элемент
n − 1 способ
·
3-й элемент
n − 2 способа
·
k-й элемент
n − k + 1 способ
По правилу произведения перемножаем число способов на каждом шаге. Каждый выбранный элемент выбывает, поэтому множители
убывают на единицу.
16

17.

ПРИМЕРЫ
Размещения без повторений
ПРИМЕР 1
ПРИМЕР 2
В соревновании участвуют 10 человек. Сколькими
способами могут распределиться первое, второе и третье
места?
В отделе 7 разработчиков. Сколькими способами можно
поручить им 3 разные задачи, по одной каждому?
A310 = 10 · 9 · 8 = 720
A37 = 7 · 6 · 5 = 210
Порядок важен: золото и серебро — разные результаты.
Задачи разные, поэтому порядок назначения имеет значение.
КАК РАССУЖДАТЬ
Есть ли повторения?
Важен ли порядок?
Вывод
нет: один человек не займёт два места
да: первое место и третье — не одно и то же
размещения без повторений
Ответ: 720 и 210 способов соответственно
17

18.

Размещения с повторениями
Если элементы разрешено повторять, то на каждом из k мест доступны все n элементов — выбывания не
происходит.
Āk
n
= nk
По правилу произведения: n · n · … · n, где множитель
повторяется k раз.
ПРИМЕР 3
СРАВНИТЕ
Сколько существует PIN-кодов из четырёх цифр?
А сколько PIN-кодов с неповторяющимися цифрами?
104 = 10 000
A410 = 10 · 9 · 8 · 7 = 5 040
Цифры могут повторяться: код 1111 допустим.
Почти вдвое меньше — запрет повторений сильно
сокращает число вариантов.
18

19.

ПРИМЕР ИЗ ПРАКТИКИ
Стойкость пароля к перебору
Пароль составляется из латинских строчных и прописных букв и цифр: 26 + 26 + 10 = 62 символа. Пароль длины k — это
размещение с повторениями.
Длина
Число паролей
Формула
Время перебора
4 символа
14 776 336
62⁴
доли секунды
6 символов
56 800 235 584
62⁶
около 1 минуты
8 символов
218 340 105 584 896
62⁸
около 2,5 суток
10 символов
≈ 8,4 · 10¹⁷
62¹⁰
около 27 лет
Расчёт при скорости 1 миллиард вариантов в секунду. Каждый добавленный символ увеличивает время перебора в 62
раза — именно поэтому длина пароля важнее его «сложности» на вид.
19

20.

Перестановки
Перестановкой из n элементов называется упорядоченная выборка, в которую входят все n элементов. Это частный
случай размещения при k = n.
Pn = n!
Ann = n! / 0! = n!
ПРИМЕР 4
ПРИМЕР 5
Сколькими способами можно расставить 5 разных книг на
полке?
Сколькими способами можно составить порядок
выполнения 6 разных задач?
P5 = 5! = 120
Все книги используются, меняется только порядок.
P6 = 6! = 720
Отсюда видно, почему полный перебор порядков не
применяют.
20

21.

Перестановки с повторяющимися элементами
Если среди n элементов есть одинаковые, часть перестановок неотличима друг от друга. Их число нужно исключить из
общего количества.
P(n1, n2, …, nk) = n! / (n1! · n2! · … · nk!)
где n — общее число элементов, а n₁, n₂, …, n_k — сколько раз повторяется каждый из них
ПРИМЕР 6
Сколько различных буквосочетаний можно получить перестановкой букв слова МАТЕМАТИКА?
Всего букв
10
А
3 раза
М
2 раза
Т
2 раза
Е, И, К
по 1 разу
10! / (3! · 2! · 2!) = 3 628 800 / 24 = 151 200
21

22.

Четыре типа выборок
Тип выборки
Без повторений
С повторениями
Выбор k элементов из n
Все n элементов
Размещения
Перестановки
Akn = n! / (n − k)!
Pn = n!
Размещения с повторениями
Перестановки с повторениями
nk
n! / (n1! · n2! · … · nk!)
Алгоритм выбора формулы: ответьте на два вопроса — возможны ли повторения и все ли элементы участвуют в выборке — и
найдите нужную клетку таблицы
22

23.

Задачи
1
Сколько трёхзначных чисел можно составить из цифр 1, 2, 3, 4, 5, если цифры не повторяются?
2
Тот же вопрос, но цифры повторять можно.
3
Сколькими способами 7 студентов могут встать в очередь?
4
Сколько различных буквосочетаний получится перестановкой букв слова АНАНАС?
23

24.

Задача со звездочкой
Сколько трёхзначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, если цифры не повторяются?
ТИПИЧНЫЙ ОТВЕТ
ВЕРНЫЙ ОТВЕТ
A310 = 10 · 9 · 8 = 720
9 · 9 · 8 = 648
Формула применена верно — но ответ неправильный.
Число не может начинаться с нуля.
ПОЧЕМУ ТАК
Первая цифра
Вторая цифра
Третья цифра
9 способов: любая, кроме нуля
9 способов: ноль вернулся, но одна цифра
занята
8 способов: две цифры уже использованы
24

25.

Что нужно запомнить
1
Теория вероятностей
изучает закономерности случайных явлений; для расчёта вероятностей нужно уметь считать
число исходов
2
Правило суммы
«или», выборы не пересекаются: складываем
3
Правило произведения
«и», выбор по одному из каждой группы: умножаем
4
Размещения
Akn = n!/(n−k)! без повторений; nk с повторениями
5
Перестановки
Pn = n!; с повторениями n!/(n1!·…·nk!)
6
Алгоритм
два вопроса: важен ли порядок и возможны ли повторения
25

26.

Домашнее задание
Письменно, к следующему занятию. В каждой задаче укажите правило или тип выборки и запишите формулу.
1
Вычислите: 6!; 8!/6!; 0!+1!+2!+3!; 10!/(7!·3!)
6
Сколько существует четырёхзначных PIN-кодов?
Сколько среди них кодов, в которых все цифры
различны?
2
В отделе работают 6 программистов и 4 тестировщика.
Сколькими способами можно выбрать одного
сотрудника для участия в конференции?
7
Сколькими способами 8 разных книг можно
расставить на одной полке?
3
В гардеробе 3 рубашки, 2 пиджака и 4 пары брюк.
Сколькими способами можно составить комплект из
рубашки, пиджака и брюк?
8
Сколько различных буквосочетаний можно получить
перестановкой букв слова КОЛОКОЛ?
4
В группе 15 студентов. Сколькими способами можно
выбрать старосту и его заместителя?
9
Автомобильный номер состоит из трёх букв (12
допустимых букв) и трёх цифр. Сколько существует
различных номеров?
5
Сколько трёхзначных чисел можно составить из цифр
1, 3, 5, 7, 9, если цифры не повторяются?
10
Сколько четырёхзначных чисел можно составить из
цифр 0, 1, 2, 3, 4, 5, если цифры не повторяются?
26