- Что такое комбинаторика
- Комбинаторные задачи и инструменты
- Основные обозначения в комбинаторике
- Графы
- Выводы
На этом курсе будем изучать комбинаторику — очередной раздел дискретной математики.
Комбинаторика изучает сочетания, перестановки, размещения и перечисления отдельных объектов и множеств. Эта дисциплина помогает глубже понять алгебру, геометрию и теорию вероятностей. Еще без нее не обойтись в генетике, информатике, статистической физике.
В этом уроке мы выясним, что такое комбинаторика и чем она полезна в программировании. Мы познакомимся с базовой терминологией и узнаем об основных инструментах комбинаторики. Эти знания помогут нам погрузиться в новую дисциплину и подготовиться к решению комбинаторных задач.
Что такое комбинаторика
Комбинаторика тесно связана с понятием множество — это набор чисел, переменных или других элементов. Вспомним, как оно выглядит:
Множество: Элементы множества: , и
Из любого множества можно составить разные сочетания — комбинации. В нашем примере множество состоит из трех элементов ( , и ), из которых можно составить шесть трехзначных комбинаций:
Комбинации:
В программировании комбинаторика помогает тестировать программы и анализировать алгоритмы. Она автоматизирует расчеты количества возможных ситуаций. Другими словами, с помощью комбинаторики можно ответить на вопрос: «Сколько комбинаций можно собрать из конкретных элементов и по конкретным правилам?».
Этот вопрос часто встает в реальных задачах программиста, особенно когда речь идет о работе с большими данными или таблицами. Даже с перебором паролей без комбинаторики не справится:
-
Представим, что мы создали сайт и выбираем правила, каким должен быть пароль пользователя
-
Решили не усложнять жизнь пользователю и поставили такие правила «Пароль должен состоять только из цифр, длина пароля — 4 символа»
-
Пока не очевидно, насколько надежным получится такой пароль. Чтобы это понять, надо вычислить, сколько возможно комбинаций. Ответить на этот вопрос помогает комбинаторика
Подобные задачи можно решить с помощью трех методов:
-
Комбинаторные формулы
-
Динамическое программирование
-
Рекурсивные алгоритмы полного или частичного перебора
В этом курсе будем рассматривать решение с помощью комбинаторных формул. Динамическое программирование и рекурсивные алгоритмы перебора подробнее рассмотрены в других курсах Хекслета.
Также в курсе будет еще одна особенность — мы будем уделять внимание разным методам вычисления одного и того же результата. В этом нет ничего необычного, потому что это особенность комбинаторики: задачу можно решать разными способами.
Комбинаторные задачи и инструменты
В этом курсе мы сосредоточимся на трех типах комбинаторных задач:
Тип |
Пример |
Перечисление |
Cколько существует различных структур заданного размера? |
Существование |
Cуществует ли структура с нужными нам свойствами? |
Экстремальные проблемы |
Если мы рассматриваем только структуры с определенным свойством, насколько большими мы можем их сделать? |
Такие задачи можно решить различными методами. В этом курсе мы рассмотрим следующие комбинаторные инструменты:
-
Способы подсчета
-
Счет через биекцию
-
Принцип включения и исключения
-
Теорема Рамсея
-
Порождающие функции
-
«Принцип голубятни»
Подробнее перечисленные типы и инструменты будем разбирать в отдельных уроках.
А сейчас познакомимся с основными обозначениями, которые будут часто встречаться на курсе. Они помогут легче понимать теорию и проходить практику.
Основные обозначения в комбинаторике
Многие обозначения в комбинаторике нам уже знакомы: они используются в математической логике и теории множеств. Поэтому в этом курсе мы не будем разбирать их подробно, но сосредоточимся на неизвестных понятиях.
Перечислим ключевые понятия для комбинаторики:
|
Множество неотрицательных целых чисел |
|
Конечное множество целых чисел |
|
Размер множества , количество элементов в нем |
|
Множество мощности ,то есть множество |
Еще одно важное понятие — это семейства множеств (или системы множеств).
Для примера рассмотрим семейство множеств :
Пара , где — конечное множество, а
У разных семейств множеств могут быть разные характеристики, на которые мы должны обращать внимание:
Характеристика |
Пример |
Семейства множеств с определенными свойствами |
Все множества внутри семейства имеют одинаковый размер |
Семейства множеств, члены которых имеют определенные пересечения |
Никакие два множества внутри семейства не являются непересекающимися |
Семейства множеств, замкнутые при определенных операциях |
Замкнуто при взятии супермножества — множества, состоящего из множеств. Множество называется замкнутым, если оно содержит все свои предельные точки, (например, любой отрезок — замкнутое множество) |
Подробнее о множествах и их характеристикам мы говорили в курсе «Теория множеств» — можете обратиться к нему, чтобы освежить знания.
Еще в комбинаторике часто работают с графами, чтобы визуализировать задачу. Разберем, что это такое и как они выглядят.
Графы
Графы — это инструмент, который помогает подсчитывать и перебирать различные комбинации в задаче. Это совокупность точек, которые соединены линиями. Точки называются вершинами или узлами, а линии — ребрами, которые обозначают, какие узлы связаны между собой. Например:
Граф — это пара , где — конечное множество, а — набор подмножеств размера из . Члены — вершины, члены — ребра.
Например, если — ребро, то и — его конечные точки. Мы говорим, что и смежны, и что и инцидентны .
Степень вершины , которая обозначается как — это количество ребер, где — конечная точка. Вершина со степенью называется изолированной.
С помощью графов можно визуализировать задачу, что поможет понять и решить ее легче и быстрее.
Выводы
В этом вводном уроке мы обсудили особенности комбинаторики и узнали, в каких практических задачах она применяется.
Еще мы рассмотрели основные символы, которые встречаются в большинстве случаев, и графы, которые помогают визуализировать задачу. Остальные обозначения изучим, когда будем разбирать инструменты и комбинаторные задачи подробнее.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.