Введение в дискретную математику

Вводная лекция для дисциплин «Дискретная математика», «Математическая логика и теория алгоритмов», «Теория графов и комбинаторные методы», «Аналоговое и дискретное моделирование», «Компьютерное моделирование».

Часть 1

Все системы, процессы, сигналы, модели принято делить на непрерывные и дискретные, то есть прерывистые.

Система – это нечто сложное, состоящее из частей, но воспринимаемое нами как единое целое, например, компьютер - вычислительная система.

Процесс – это что-то, развивающееся во времени, например, вычислительный процесс.

Сигнал – это любая функция времени, например, информационный сигнал.

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

Системы непрерывного времени

Мы живем в мире, где время и пространство непрерывны, любая функция времени или координат непрерывная функция.

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

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

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

Сложности использования аналоговых моделей.

Простая задача – движение материальной точки: F = ma, где F – внешняя сила. Учтем также сопротивление среды (-hv) и силу упругости (-kx).

Получаем уравнение ma = F-hv –kx.

Учтем, что скорость v=x' (первая производная), ускорение a=x" (вторая производная), а сила может меняться со временем F=f(t).

Получаем дифференциальное уравнение m x" + h x' + kx = f(t).

Задача: зная f(t), начальное положение x(0) и начальную скорость x'(0), требуется найти x(t) – положение частицы в любой момент времени.

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

Поэтому от непрерывного времени часто переходят к прерывистому дискретному времени.

Системы дискретного времени

Вместо непрерывного времени t процессы рассматриваются только в определенные моменты, следующие через интервал t. Получаем системы дискретного времени t = t  n, где n= 0, 1, 2…

Таким образом, t = 0, t, 2 t…

Говорят, что сигнал задается на счетном множестве (элементы множества можно пересчитать).

При этом непрерывные функции x(t) переходят в последовательности x_n :

x₀ =x(0) , x₁ = x(t) x₂ = x(2t)

А дифференциальные уравнения типа a x" + b x' + cx = f(t) превращаются в разностные уравнения a x_n+2 + b x _n+1 + c x _n = f _n .

ПРИМЕР ДИСКРЕТНОЙ СИСТЕМЫ И МОДЕЛИ.

С дискретными процессами мы часто сталкиваемся, например, любые банковские операции.

Пусть, взят кредит в размере S, который требуется вернуть за N месяцев. Банк начисляет ежемесячный процент от невозвращенной суммы - k , ежемесячные выплаты f _n могут быть постоянными, а могут меняться.

Пусть x _n невозвращенная сумма, в начальный момент x ₀ = S , а в последний месяц он должен стать x _N = 0.

Составим разностное уравнение. Оставшийся долг x _n+1 равен сумме долга за предыдущий месяц x _n плюс набежавшие проценты за этот месяц k x _n минус ежемесячные выплаты.

Получаем x _n+1 = x _n + k x _n - f _n .

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

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

ПРИМЕР ДИСКРЕТНОЙ ЧИСЛЕННОЙ (КОМПЬЮТЕРНОЙ) МОДЕЛИ.

Пусть имеется уравнение, которое мы хотим решить для произвольного вида известной правой части, то есть найти реакцию системы x(t) по известному, но произвольному стимулирующему воздействию f(t).

Пусть процесс описывается следующим дифференциальным уравнением

x'(t) + x(t) = f(t) .

К сожалению, задача не решается в общем виде. Конкретное решение зависит от вида правой части, а при некоторых видах f(t) аналитическое решение вообще не удается получить. Поэтому решим задачу численными (дискретными, «компьютерными») методами

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

Получаем уравнение x'_n + x _n = f _n

Что такое x _n и f _n понятно. Вопрос: что такое x'_n ?

По определению производной

Но в системах с дискретным временем мы не можем временной шаг устремить к нулю.

Поэтому мы вынуждены оставить конечный шаг

Тогда получаем разностное уравнение

(x_n+1 - x_n ) / t+ x_n. = f _n

Или в другой форме x_n+1 = x_n + t (f _n - x_n.)

Зная x ₀ и f _n нетрудно получить все значения x _n.

x₁ = x₀ + t (f ₀ – x₀.), x₂ = x₁ + t (f₁ - x₁.)

Такие модели, в которых дифференциальный оператор (производная) заменяется разностной схемой, называются численными моделями, так как в них используются методы «Вычислительной математики».

Другое название таких моделей - компьютерные модели, так как мы сложную задачу сводим к простым операциям, типа сложение, разность, умножение и т.д. Считается, что компьютер сам по себе ничего не умеет делать, кроме того, как хранить бит информации в ячейке, передавать её в другую ячейку, складывать содержимое двух ячеек и передавать ее в третью. Даже умножение в двоичном коде сводится к сложению. Так вот проведенные преобразования как раз и позволяют свести сложное решение дифференциального уравнения к простым арифметическим операциям.

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