Математический анализ алгоритмов

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

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

     F_a (D) = F_a (|D|) = F_a (N)

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

     2. Параметрически-зависимые по трудоемкости алгоритмы. Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:

     F_a (D) = F_a (d₁,…,d_n) = F_a (P₁,…,P_m), m £ n

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

     а) Вычисление x^k последовательным умножением  F_a(x, k) = F_a (k).

     б) Вычисление e^x=(xⁿ/n!), с точностью до F_a = F_a (x)

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

     F_a (D) = F_a (||D||, P₁,…,P_m) = F_a (N, P₁,…,P_m)

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

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

     Пусть множество D состоит из элементов (d₁,…,d_n), и ||D||=N, определим D_p = {(d₁,…,d_n)}-множество всех упорядоченных N-ок из d₁,…,d_n, отметим, что |D_p|=n!. Если

     F_a (_iD_p) > F_a (_jD_p),

где _iD_p, _jD_p > D_p, то алгоритм будем называть порядково-зависимым по трудоемкости.

     Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. Рассмотрим более подробно алгоритм поиска максимума в массиве S, содержащим n элементов:

     MaxS (S,n; Max)

     Max < S1

     For i>2 to n

         if Max < Si

     then Max > S_i (количество выполненных операций присваивания зависит от порядка следования элементов массива) 

     Тезис Чёрча -- Тьюринга и алгоритмически неразрешимые проблемы 

     Алан Тьюринг высказал предположение (известное как Тезис Чёрча -- Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

     В течение первого десятилетия истории теории алгоритмов неразрешимые массовые проблемы были обнаружены лишь внутри самой этой теории (сюда относится описанная выше проблема применимости), а также внутри математической логики (проблема выводимости в классическом исчислении предикатов). Поэтому считалось, что теория алгоритмов представляет собой обочину математики, не имеющую значения для таких её классических разделов, как алгебра или анализ. Положение изменилось после того, как А. А. Марков и Э. Л. Пост в 1947 году установили алгоритмическую неразрешимость известной в алгебре проблемы равенства для конечнопорождённых и конечноопределённых полугрупп (т. н. проблемы Туэ). Впоследствии была установлена алгоритмическая неразрешимость и многих других «чисто математических» массовых проблем. Одним из наиболее известных результатов в этой области является доказанная Ю. В. Матиясевичем алгоритмическая неразрешимость десятой проблемы Гильберта.

     Алгоритмически неразрешимая задача

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

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

     * Аналог десятой проблемы Гильберта для уравнений степени 3

     * Аналог десятой проблемы Гильберта для уравнений в рациональных числах

         * Проблема умирающей матрицы для матриц порядка 2

     Проблема остановки

     В теории вычислимости проблема остановки -- это проблема разрешимости, которая может неформально быть поставлена в виде:

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

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

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

     Эйлер

     Перемены, произошедшие за последующие полвека, отражены в обширном трактате Эйлера. Изложение анализа открывает двухтомное «Введение», где собраны изыскания о различных представлениях элементарных функций. Термин «функция» впервые появляется лишь в 1692 у Лейбница, однако на первые роли его выдвинул именно Эйлер. Изначальная трактовка понятия функции состояла в том, что функция -- это выражение для счёта (нем. Rechnungsausdrϋck) или аналитическое выражение. Функция переменного количества есть аналитическое выражение, составленное каким-либо образом из этой переменного количества и чисел или постоянных количеств.

     Подчёркивая, что «основное различие функций лежит в способе составления их из переменного и постоянных», Эйлер перечисляет действия, «посредством которых количества могут друг с другом сочетаться и перемешиваться; действиями этими являются: сложение и вычитание, умножение и деление, возведение в степень и извлечение корней; сюда же следует отнести также решение [алгебраических] уравнений. Кроме этих действий, называемых алгебраическими, существует много других, трансцендентных, как-то: показательные, логарифмические и бесчисленные другие, доставляемые интегральным исчислением». Такая трактовка позволяла без труда обращаться с многозначными функциями и не требовала пояснения, над каким полем рассматривается функция: выражение для счёта определено для комплексных значений переменных даже тогда, когда для рассматриваемой задачи это не нужно.

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

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

     Современное состояние теории алгоритмов 

В настоящее время теория алгоритмов развивается, главным образом, по трем направлениям.

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

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

Для каждого класса существует категория задач, которые являются «самыми сложными». Это означает, что любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе. Такие задачи называют полными задачами для данного класса. Наиболее известными являются NP-полные задачи.

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

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

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

Интервальный анализ

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

* Величины, значения которых известны только приближённо, то есть определён конечный интервал, в котором эти значения содержатся.

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

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

Операции над интервалами

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

    * Сложение: [a,b] + [c,d] = [a + c, b + d]