Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

eyJpZCI6IjZlOTUxNmYyODQ2ODk3NjA5NjQzODk5MDljNTQzMGU0LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=3462574136b181ca27c72fba9f51102975a203904efe620f9a97556a344edc04

На этом курсе будем изучать комбинаторику — очередной раздел дискретной математики.

Комбинаторика изучает сочетания, перестановки, размещения и перечисления отдельных объектов и множеств. Эта дисциплина помогает глубже понять алгебру, геометрию и теорию вероятностей. Еще без нее не обойтись в генетике, информатике, статистической физике.

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

Что такое комбинаторика

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

Множество: Элементы множества: , и

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

Комбинации:

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

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

  • Представим, что мы создали сайт и выбираем правила, каким должен быть пароль пользователя

  • Решили не усложнять жизнь пользователю и поставили такие правила «Пароль должен состоять только из цифр, длина пароля — 4 символа»

  • Пока не очевидно, насколько надежным получится такой пароль. Чтобы это понять, надо вычислить, сколько возможно комбинаций. Ответить на этот вопрос помогает комбинаторика

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

  • Комбинаторные формулы

  • Динамическое программирование

  • Рекурсивные алгоритмы полного или частичного перебора

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

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

Комбинаторные задачи и инструменты

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

Тип

Пример

Перечисление

Cколько существует различных структур заданного размера?

Существование

Cуществует ли структура с нужными нам свойствами?

Экстремальные проблемы

Если мы рассматриваем только структуры с определенным свойством, насколько большими мы можем их сделать?

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

  • Способы подсчета

  • Счет через биекцию

  • Принцип включения и исключения

  • Теорема Рамсея

  • Порождающие функции

  • «Принцип голубятни»

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

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

Основные обозначения в комбинаторике

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

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

Множество неотрицательных целых чисел

Конечное множество целых чисел

Размер множества , количество элементов в нем

Множество мощности ,то есть множество

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

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

Пара , где — конечное множество, а

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

Характеристика

Пример

Семейства множеств с определенными свойствами

Все множества внутри семейства имеют одинаковый размер

Семейства множеств, члены которых имеют определенные пересечения

Никакие два множества внутри семейства не являются непересекающимися

Семейства множеств, замкнутые при определенных операциях

Замкнуто при взятии супермножества — множества, состоящего из множеств. Множество называется замкнутым, если оно содержит все свои предельные точки, (например, любой отрезок — замкнутое множество)

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

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

Графы

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

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

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

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

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

Выводы

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

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


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

Задавайте вопросы, если хотите обсудить теорию или упражнения. Команда поддержки Хекслета и опытные участники сообщества помогут найти ответы и решить задачу