Введение — Комбинаторика

Комбинаторика тесно связана с понятием множество — это набор чисел, переменных или других элементов. Вспомним, как оно выглядит:

Из любого множества можно составить разные сочетания — комбинации. В нашем примере множество состоит из трех элементов ( , и ), из которых можно составить шесть трехзначных комбинаций:

В программировании комбинаторика помогает тестировать программы и анализировать алгоритмы. Она автоматизирует расчеты количества возможных ситуаций. Другими словами, с помощью комбинаторики можно ответить на вопрос: «Сколько комбинаций можно собрать из конкретных элементов и по конкретным правилам?».

Этот вопрос часто встает в реальных задачах программиста, особенно когда речь идет о работе с большими данными или таблицами. Даже с перебором паролей без комбинаторики не справится:

Подобные задачи можно решить с помощью трех методов:

В этом курсе будем рассматривать решение с помощью комбинаторных формул. Динамическое программирование и рекурсивные алгоритмы перебора подробнее рассмотрены в других курсах Хекслета.

Также в курсе будет еще одна особенность — мы будем уделять внимание разным методам вычисления одного и того же результата. В этом нет ничего необычного, потому что это особенность комбинаторики: задачу можно решать разными способами.

В этом курсе мы сосредоточимся на трех типах комбинаторных задач:

Такие задачи можно решить различными методами. В этом курсе мы рассмотрим следующие комбинаторные инструменты:

Подробнее перечисленные типы и инструменты будем разбирать в отдельных уроках.

А сейчас познакомимся с основными обозначениями, которые будут часто встречаться на курсе. Они помогут легче понимать теорию и проходить практику.

Многие обозначения в комбинаторике нам уже знакомы: они используются в математической логике и теории множеств. Поэтому в этом курсе мы не будем разбирать их подробно, но сосредоточимся на неизвестных понятиях.

Перечислим ключевые понятия для комбинаторики:

Еще одно важное понятие — это семейства множеств (или системы множеств).

Для примера рассмотрим семейство множеств :

У разных семейств множеств могут быть разные характеристики, на которые мы должны обращать внимание:

Подробнее о множествах и их характеристикам мы говорили в курсе «Теория множеств» — можете обратиться к нему, чтобы освежить знания.

Еще в комбинаторике часто работают с графами, чтобы визуализировать задачу. Разберем, что это такое и как они выглядят.

Графы — это инструмент, который помогает подсчитывать и перебирать различные комбинации в задаче. Это совокупность точек, которые соединены линиями. Точки называются вершинами или узлами, а линии — ребрами, которые обозначают, какие узлы связаны между собой. Например:

Граф — это пара , где — конечное множество, а — набор подмножеств размера из . Члены — вершины, члены — ребра.

Например, если — ребро, то и — его конечные точки. Мы говорим, что и смежны, и что и инцидентны .

Степень вершины , которая обозначается как — это количество ребер, где — конечная точка. Вершина со степенью называется изолированной.

С помощью графов можно визуализировать задачу, что поможет понять и решить ее легче и быстрее.

В этом вводном уроке мы обсудили особенности комбинаторики и узнали, в каких практических задачах она применяется.

Еще мы рассмотрели основные символы, которые встречаются в большинстве случаев, и графы, которые помогают визуализировать задачу. Остальные обозначения изучим, когда будем разбирать инструменты и комбинаторные задачи подробнее.