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

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «Хакасский государственный университет им. Н.Ф. Катанова» (ФГБОУ ВО «ХГУ им. Н.Ф. Катанова») Институт естественных наук и математики Кафедра математики, физики и информационных технологий Направление подготовки 44.03.05 Педагогическое образование направленность (профили) Математика, Физика.

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

Выполнила: Валева Арина Алексеевна

Группа МФ-31 Курс 3

Форма обучения: очная

Научный руководитель:

Доцент, кандидат физ.-мат наук, доцент

Бекешева Ирина Сергеевна

ВВЕДЕНИЕ

• Комбинаторика возникла в XVI веке и первоначально в ней рассматривались комбинаторные задачи, связанные в основном с азартными играми. В карты и кости выигрывались золото и бриллианты, дворцы, породистые кони и дорогие украшения. Широко были распространены всевозможные лотереи. Одним из первых занялся подсчетом числа возможных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывающую, сколькими способами могут выпасть «r» костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами.

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

• Магический квадрат

• Греко-латинский квадрат или Эйлеров квадрат

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

• Задача размещения- одна из классических комбинаторных задач, в которой требуется определить чисто способ размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек.

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

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

• Бином Ньютона – формула возведения двухчлена (a + b) в целую неотрицательную степень n. Строго говоря, всю формулу нельзя назвать биномом, так как «бином» переводится как «двучлен». Кроме того, формула разложения была известна еще до Ньютона, Исаак Ньютон распространил это разложение на случай n n – дробного. Цель изучения бинома Ньютона – упрощение вычислительных действий.
• Треугольник Паскаля – это бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.

Примеры нестандартных комбинаторных задач:

• 1. Задача Паппа Александрийского

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

• 2. Задача Магавиры

О друг, найди число различных павлинов в стае, 1/16 которой, умноженная на себя, сидит на манговом дереве, а квадрат 1/9 остатка вместе с 14 другими павлинами – на дереве тамала.

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

• Перебор

• Рекурсия

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

• Графы

Примеры нестандартных методов решения задач:

Перебор:

Примеры нестандартных методов решения задач:

Дано натуральное число n. Выведите все числа от 1 до n

Рекурсия

Примеры нестандартных методов решения задач:

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

На рисунке — схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. Сколько существует различных путей из пункта А в пункт Н, не проходящих через пункт Е?

Решение: Будем также решать методом динамического программирования. Построим таблицу, в которую будем записывать количество возможных путей для каждой вершины. До вершины Е идем согласно заданию №1. Так как по условию задания нам следует исключить пути, проходящие через пункт Е, то для этой вершины не будем считать количество путей. Проще всего в таблицу в столбец Е поставить число 0. Для остальных вершин правило заполнения таблицы не изменится

Заполнив таблицу, получим количество путей из пункта А в пункт Н, равное 33.

Примеры нестандартных методов решения задач:

Графы:

ЗАКЛЮЧЕНИЕ

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

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

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

Спасибо за внимание!