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

Комбинаторика занимается составлением из элементов данных множеств различных комбинаций с заданными свойствами и подсчетом их числа.

Тематика современной комбинаторики, как указывают математики Айгнер М.Р., Виленкин Н.Я., Антипов И.Н., разнообразна: перечислительные и экстремальные задачи, проблемы существования, выбора и расположения, геометрические и алгебраические интерпретации. Комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний, для составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики и т.д. Комбинаторика используется для составления и декодирования шифров и для решения других проблем информации.

Как указывает М. Айгнер «значительную роль комбинаторные методы играют и в чисто математических вопросах - теории групп и их представлений, изучении оснований геометрии, неоассоциативных алгебр и т. д.».

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

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

В математической литературе отмечаются три отличительные черты комбинаторных задач, которые заключаются в следующем:

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

2. Множества этих элементов конечны.

3. Преимущество отдано двум видам операций: отбор подмножеств и упорядочению элементов множества.

Комбинаторные задачи с точки зрения теории множеств - это задачи на определение числа возможных конечных множеств или кортежей с определенными свойствами, которые можно составить из данных элементов; или числа - соответствия, которые можно установить между элементами конечных множеств.

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

Способы решения комбинаторных задач, обычно делят на две группы: «формальные» и «неформальные». При «формальном» пути решения нужно определить характер выборки, выбрать соответствующую формулу или комбинаторный принцип подставить числа и вычислить результат. Результат - это количество возможных вариантов, сами же варианты в этом случае не образовываются. Основные комбинаторные правила: сложения, умножения.

Примером решения комбинаторных задач формальным способом могут служить следующие задачи:

Задача. 1. Сколько словарей надо иметь, чтобы можно было выполнять переводы непосредственно с любого из пяти языков на любой из этих пяти?

Решение. Число словарей совпадает с числом упорядоченных подмножеств, содержащих два элемента из пяти. Для такого перевода надо иметь 20 словарей.

Задача 2. На первой прямой взяты три точки, а на параллельной ей прямой четыре точки. Сколько существует треугольников, вершинами которых являются эти точки?

Решение. Треугольник однозначно определяется тремя точками-вершинами, не принадлежащими одной прямой. Если взять в качестве вершины треугольника одну из трех точек на первой прямой, то, чтобы получить треугольник, на второй прямой надо выбрать две точки из четырех имеющихся. Если одну точку - вершину из четырех выбираем на второй прямой, то две точки из трех надо выбрать на первой прямой. Применяя правила умножения и сложения, найдем 30 треугольников.

Задача 3. Сколько различных четырехзначных чисел имеется в пятиричной системе счисления?

Решение. Четырехзначное число не может начинаться с нуля. Следовательно, первое место в числе может занять одна из четырех цифр. Выбор каждой из остальных трех цифр числа можно осуществить пятью способами. Используя правило умножения, получим 500 чисел.

«Неформальный» способ решения на первый план выводит сам процесс составления различных комбинаторных конфигураций. И главная его задача быстро и правильно найти все возможные варианты.

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

Способ перебора применяется для решения задач с древнейших времен. В современной жизни он используется как в практической деятельности, так и для решения серьезных проблем в математике и информатики в связи с появлением электронно-вычислительных машин, производящих перебор с большим числом элементов в короткое время.

Помимо термина «перебор» в литературе можно встретить и другие: «метод проб и ошибок», «метод проб», «прием целенаправленных проб», «способ подбора и догадки».

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

Для этого используют комбинаторные таблицы, графы, «дерево решений».

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

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

Числовой таблицей называется таблица с числовыми характеристиками множеств (они часто подсказывают наилучший практический путь решения, какого-нибудь вопроса).

Комбинаторные таблицы удобно использовать при составлении различных конфигураций (и размещений, и перестановок, и сочетаний).

В математике считается, что граф выражает отношения между множествами и элементами множеств. «Граф» - от греческого «графо» - «пишу».

По определению Н.Я. Виленкина, граф - это «множество, состоящее из конечного числа точек, некоторые пары которых соединены дугами (такие графы называются неориентированными; если вместо дуг используются стрелки, то получится ориентированный граф, или, орграф)».

A.M. Пышкало, Стойлова Л.П., Рожденственская В.В. графом называют «особый чертеж, состоящий из точек и линий, идущих из одной точки в другую».

Иначе можно сказать, что граф - совокупность точек, стрелок, линий, петель. Как указывает Виленкин Н.Я. «точки, изображающие элементы множества, рассматриваемого в задаче, называют вершинами графа». «Стрелку на графе, у которой начало и конец совпадают, называют петлей».

Анализ особенностей комбинаторных задач и способов их решения позволяет сделать следующие выводы:

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

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

3. Можно предположить, что в качестве способов решения комбинаторных задач младшим школьникам вполне доступны способ перебора, составление таблиц и построение графов.

АВТОР: Виноградова Е.П.