- Что такое комбинаторика
- Комбинаторные задачи и инструменты
- Основные обозначения в комбинаторике
- Графы
- Выводы
На этом курсе будем изучать комбинаторику — очередной раздел дискретной математики.
Комбинаторика изучает сочетания, перестановки, размещения и перечисления отдельных объектов и множеств. Эта дисциплина помогает глубже понять алгебру, геометрию и теорию вероятностей. Еще без нее не обойтись в генетике, информатике, статистической физике.
В этом уроке мы выясним, что такое комбинаторика и чем она полезна в программировании. Мы познакомимся с базовой терминологией и узнаем об основных инструментах комбинаторики. Эти знания помогут нам погрузиться в новую дисциплину и подготовиться к решению комбинаторных задач.
Что такое комбинаторика
Комбинаторика тесно связана с понятием множество — это набор чисел, переменных или других элементов. Вспомним, как оно выглядит:
Множество: {2,5,8}
Элементы множества: 2, 5 и 8
Из любого множества можно составить разные сочетания — комбинации. В нашем примере множество {2,5,8} состоит из трех элементов (2, 5 и 8), из которых можно составить шесть трехзначных комбинаций:
Комбинации: 258, 285, 528, 582, 825, 852
В программировании комбинаторика помогает тестировать программы и анализировать алгоритмы. Она автоматизирует расчеты количества возможных ситуаций. Другими словами, с помощью комбинаторики можно ответить на вопрос: «Сколько комбинаций можно собрать из конкретных элементов и по конкретным правилам?».
Этот вопрос часто встает в реальных задачах программиста, особенно когда речь идет о работе с большими данными или таблицами. Даже с перебором паролей без комбинаторики не справится:
- Представим, что мы создали сайт и выбираем правила, каким должен быть пароль пользователя
- Решили не усложнять жизнь пользователю и поставили такие правила «Пароль должен состоять только из цифр, длина пароля — 4 символа»
- Пока не очевидно, насколько надежным получится такой пароль. Чтобы это понять, надо вычислить, сколько возможно комбинаций. Ответить на этот вопрос помогает комбинаторика
Подобные задачи можно решить с помощью трех методов:
- Комбинаторные формулы
- Динамическое программирование
- Рекурсивные алгоритмы полного или частичного перебора
В этом курсе будем рассматривать решение с помощью комбинаторных формул. Динамическое программирование и рекурсивные алгоритмы перебора подробнее рассмотрены в других курсах Хекслета.
Также в курсе будет еще одна особенность — мы будем уделять внимание разным методам вычисления одного и того же результата. В этом нет ничего необычного, потому что это особенность комбинаторики: задачу можно решать разными способами.
Комбинаторные задачи и инструменты
В этом курсе мы сосредоточимся на трех типах комбинаторных задач:
| Тип | Пример |
|---|---|
| Перечисление | Cколько существует различных структур заданного размера? |
| Существование | Cуществует ли структура с нужными нам свойствами? |
| Экстремальные проблемы | Если мы рассматриваем только структуры с определенным свойством, насколько большими мы можем их сделать? |
Такие задачи можно решить различными методами. В этом курсе мы рассмотрим следующие комбинаторные инструменты:
- Способы подсчета
- Счет через биекцию
- Принцип включения и исключения
- Теорема Рамсея
- Порождающие функции
- «Принцип голубятни»
Подробнее перечисленные типы и инструменты будем разбирать в отдельных уроках.
А сейчас познакомимся с основными обозначениями, которые будут часто встречаться на курсе. Они помогут легче понимать теорию и проходить практику.
Основные обозначения в комбинаторике
Многие обозначения в комбинаторике нам уже знакомы: они используются в математической логике и теории множеств. Поэтому в этом курсе мы не будем разбирать их подробно, но сосредоточимся на неизвестных понятиях.
Перечислим ключевые понятия для комбинаторики:
N |
Множество неотрицательных целых чисел {0, 1, 2, . . .} |
n |
Конечное множество целых чисел {1, 2, . . . , n} |
| `\ | X\ |
P (X) |
Множество мощности X,то есть множество {Y : Y subseteq X} |
Еще одно важное понятие — это семейства множеств (или системы множеств).
Для примера рассмотрим семейство множеств F:
Пара (X,F), где X — конечное множество, а F subseteq P (X)
У разных семейств множеств могут быть разные характеристики, на которые мы должны обращать внимание:
| Характеристика | Пример |
| Семейства множеств с определенными свойствами | Все множества внутри семейства имеют одинаковый размер |
| Семейства множеств, члены которых имеют определенные пересечения | Никакие два множества внутри семейства не являются непересекающимися |
| Семейства множеств, замкнутые при определенных операциях | Замкнуто при взятии супермножества — множества, состоящего из множеств. Множество называется замкнутым, если оно содержит все свои предельные точки, (например, любой отрезок — замкнутое множество) |
Подробнее о множествах и их характеристикам мы говорили в курсе «Теория множеств» — можете обратиться к нему, чтобы освежить знания.
Еще в комбинаторике часто работают с графами, чтобы визуализировать задачу. Разберем, что это такое и как они выглядят.
Графы
Графы — это инструмент, который помогает подсчитывать и перебирать различные комбинации в задаче. Это совокупность точек, которые соединены линиями. Точки называются вершинами или узлами, а линии — ребрами, которые обозначают, какие узлы связаны между собой. Например:
Граф G — это пара (V, E), где V — конечное множество, а E — набор подмножеств размера 2 из V. Члены V — вершины, члены E — ребра.
Например, если e = {u, v} — ребро, то u и v — его конечные точки. Мы говорим, что u и v смежны, и что u и v инцидентны e.
Степень вершины v, которая обозначается как deg(v) — это количество ребер, где v — конечная точка. Вершина со степенью 0 называется изолированной.
С помощью графов можно визуализировать задачу, что поможет понять и решить ее легче и быстрее.
Выводы
В этом вводном уроке мы обсудили особенности комбинаторики и узнали, в каких практических задачах она применяется.
Еще мы рассмотрели основные символы, которые встречаются в большинстве случаев, и графы, которые помогают визуализировать задачу. Остальные обозначения изучим, когда будем разбирать инструменты и комбинаторные задачи подробнее.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
