Избранные главы дискретной математики

ul>

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

• В зависимости от функции, описывающей параметры сигнала, выделяют:

• непрерывные (аналоговые), описываемые непрерывной функцией;
• дискретные, описываемые функцией отсчетов, взятых в определенные моменты времени;
• квантованные по уровню;
• дискретные сигналы, квантованные по уровню (цифровые).

 

     Детерминированность

     Детерминированность  — определяемость. Детерминированность может подразумевать определяемость на общегносеологическом уровне или для конкретного алгоритма. Под детерминированностью процессов в мире понимается однозначная предопределённость.

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

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

     Интерполяция

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

     Определение интерполяции

     Рассмотрим  систему несовпадающих точек  x_i () из некоторой области D. Пусть значения функции f известны только в этих точках: 

     Задача  интерполяции состоит в поиске такой  функции F из заданного класса функций, что 

• Точки x_i называют узлами интерполяции, а их совокупность — интерполяционной сеткой.
• Пары (x_i, y_i) называют точками данных или базовыми точками.
• Разность между «соседними» значениями — шагом интерполяционной сетки. Он может быть как переменным так и постоянным.
• Функцию F(x) — интерполирующей функцией или интерполянтом.

 

     Экстраполяция

     Экстраполяция, экстраполирование — в математике — особый тип аппроксимации (приближения), при котором функция аппроксимируется не между заданными значениями, а вне заданного интервала.

     Экстраполяция — приближённое определение значений функции f(x) в точках x, лежащих вне отрезка [x₀,x_n], по её значениям в точках x₀ < x₁ < ... < x_n 

     Сплайны

     Кусочно-заданная функция — функция, определённая на множестве действительных чисел, заданная на каждом из интервалов, составляющих область определения, отдельной формулой: 
 
 

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

     Классический  сплайн одной переменной строится так: область определения разбивается  на конечное число отрезков, на каждом из которых сплайн совпадает с  некоторым алгебраическим полиномом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна  и получившейся гладкостью называется дефектом сплайна. Например, непрерывная  ломаная есть сплайн степени 1 и дефекта 1.

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

 

   §9 Теория сложности алгоритмов

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

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

     Теория  сложности алгоритмов является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной проблемы. Стоимость обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами. Время определяется количеством элементарных шагов, необходимых для решения проблемы, тогда как пространство определяется объёмом памяти или места на носителе данных. Таким образом, в этой области предпринимается попытка ответить на центральный вопрос разработки алгоритмов: «как изменится время исполнения и объём занятой памяти в зависимости от размера входа и выхода?». Здесь под размером входа понимается длина описания данных задачи в битах (например, в задаче коммивояжера длина входа пропорциональна количеству городов и дорог между ними), а под размером выхода — длина описания решения задачи (оптимального маршрута в задаче коммивояжера).

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

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

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

     Аналогично  понятию временной сложности  в худшем случае определяется понятие  временная сложность алгоритма  в наилучшем случае. Также рассматривают  понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят  просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма  в худшем, наилучшем или среднем  случае (в зависимости от контекста).

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

   §10 Теория конечных автоматов

     Теория  конечных автоматов, часть теоретической кибернетики, объектом исследования которой являются различные преобразователи дискретной информации; возникла в начале 50-х гг. 20 в. в связи с требованиями практики проектирования вычислительных машин и с разработкой математических моделей процессов переработки информации в биологических, экономических и других системах. Теория конечных автоматов — самостоятельный раздел математики, имеющий разнообразную проблематику и приложения.

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

     Теория конечных автоматов состоит  из ряда разделов.

   Один  из разделов: абстрактно-алгебраическая теория конечных автоматов. В этом разделе абстрактные автоматы изучаются с точки зрения исследования их свойств и различных способов задания.

   Абстрактным автоматом называют объект А = А (U, X, Y, d, l), состоящий из трёх непустых множеств: U — состояний, Х — входных сигналов, Y — выходных сигналов, и двух функций, осуществляющих однозначное отображение множества U´Х в U, d (а, х) переходов и множества U´Х в Y, l (а, x) выходов. Абстрактный автомат называется конечным, если множества U, X, Y — конечны. В абстрактно-алгебраической теории конечных автоматов можно выделить теорию конечных автоматов и теорию бесконечных автоматов. Основные вопросы теории конечных автоматов можно считать решенными. Наиболее интересными результатами теории конечных автоматов являются: теорема анализа и синтеза конечных автоматов, которая даёт характеристику событий, представленных в конечных автоматах, теоремы об определяющих соотношениях в алгебре регулярных событий, оценки длины экспериментов с конечными автоматами, а также ряд результатов по исследованию алгебраических свойств абстрактных автоматов. В теории бесконечных автоматов рассматриваются различные концепции бесконечных автоматов, точнее выделяются классы бесконечных автоматов специального вида. Этот раздел важен тесной связью с общей теорией формальных языков и грамматик а также с теорией алгоритмов. В рамках абстрактно-алгебраической теории конечных автоматов наметился (конец 60-х гг.) подход к решению проблемы создания алгебры алгоритмов и построения аппарата для формальных преобразований выражений в этой алгебре, что позволяет совершенно по-новому подойти к решению такого рода задач, как эквивалентность схем алгоритмов, и даёт возможность эффективно решать оптимизационные задачи в проектировании дискретных устройств.

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

     Третьим разделом теории конечных автоматов является теория вероятностных автоматов и самоорганизующихся систем.

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

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

     Автомат Мили

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

     Конечным  детерминированным автоматом типа Мили называется совокупность пяти объектов

, 

где S, X и Y — конечные непустые множества, а δ и λ — отображения вида: 
 

    

со связью элементов множеств S, X и Y в абстрактном времени T = {0, 1, 2, …} уравнениями: