Дискретная математика. Лекция 2. Метод математической индукции

Метод математической индукции
Рассуждения бывают общие и частные.
Натуральное число, сумма цифр которого делится на 3, делится на 3 - общее.
Число 741 делится на 3 - частное.
Переход от общего утверждения к частному называется дедукцией. Дедукция широко используется в математике.

Переход от частных утверждений к общему называется индукцией. Индукция лежит в основе получения нового знания.
Индукция бывает полной (все частные случаи рассмотрены) и неполной (на основании ряда частных случаев делается общий вывод). Неполная индукция может привести к ошибкам.
Рассмотрим пример полной индукции.

Существуют правильные многогранники следующих видов (таб. 1).
Таб. 1 Правильные многогранники
Пусть В, Г, Р — число вершин, граней и ребер правильного многогранника. Перебором легко доказать, что В+Г=Р+2. Это полная индукция

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

Пример. Студенту требуется начать работу с языком Python. Он может воспользоваться услугами двух облачных сервисов (Google Colaboratory или RStudio Cloud) или установить на своем компьютере среду разработки (Anaconda, PyCharm, Visual Studio с нагрузкой Python, RStudio). Сколькими способами он может начать работу с Python, если он выбирает только один вариант: или использует облачную среду, или устанавливает среду разработки на свой компьютер?

Размещения, сочетания, перестановки

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

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

Начнем с вычисления факториала. Тем более, что вычисление факториала – классический пример при изучении рекурсии.
Рис. 2. Программа для вычисления факториала и примеры ее использования
Вместо рекурсии можно использовать цикл.
Отметим, что факториал от аргумента 15 – это весьма большая величина.

Выполним те же вычисления с помощью функции из пакета NumPy (рис. 3).
Рис. 3. Вычисление факториала с помощью функции из пакета NumPy
В реальных задачах использование пакетов предпочтительнее.
Язык Python не ограничивает длину целого числа. Всегда ли это хорошо?
Найдем количество перестановок для 50 объектов, равное 50! (рис. 4).

Рис. 4 Вычисление количества перестановок для 50 объектов
Мы получили целое число перемещений – точное, но малополезное. Преобразовав это число в вещественное, мы получили возможность оценить его. С помощью форматирования мы сделали вывод более удобным для оценки.

Более интересный подход к вычислению факториала реализован в научном пакете scipy.special (рис. 5)
Рис. 5. Вычисление факториала функцией пакета scipy.special
Функция scipy.special.factorial принимает 2 аргумента. Первый аргумент – неотрицательное целое число, факториал которого вычисляется.