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

СОДЕРЖАНИЕ

1.Теория алгоритмов и их возникновение 3

2. Модели вычислений 9

3. Операторные методы 12

3. Сравнительные оценки алгоритмов 20

4. Система обозначений в анализе алгоритмов 24

5. Классификация алгоритмов по виду функции трудоёмкости 31

6. Асимптотический анализ функций 34 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Теория алгоритмов

Определения алгоритма

     Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм -- это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

«Алгоритм -- это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

«Алгоритм -- это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

«Алгоритм -- точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)

«Алгоритм -- строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)

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

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

«Алгоритм -- это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».

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

«Алгоритм -- это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».

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

«Алгоритм -- это точное предписание, которое задаёт вычислительный (алгоритмический) процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определяемым этим исходным данным результата».

«Алгоритм -- это описание последовательности действий, которое ведёт к конечному результату».

Формальные свойства алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

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

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

    * Понятность -- алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

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

    * Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.

* Результативность -- завершение алгоритма определёнными результатами.

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

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

    * Алгоритм содержит множество значений, в определенном порядке.

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

Возникновение теории алгоритмов

Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.

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

Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом. Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.

Нормальный алгоритм Маркова (НАМ) -- один из стандартных способов формального определения понятия алгоритма, так же как и машина Тьюринга. Понятие нормального алгоритма введено А.А. Марковым в конце 1940-х годов. Традиционно, когда говорят об алгоритмах Маркова, используют слово "алгоритм".

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

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

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

Рекурсивные функции играют важную роль в теории алгоритмов, так как многие алгоритмы имеют рекурсивную структуру. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Модели вычислений

* Машина Тьюринга

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

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ -- состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

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

Лямбда-исчисление (λ-исчисление, лямбда-исчисление) -- формальная система, разработанная американским математиком Алонзо Чёрчем, для формализации и анализа понятия вычислимости.

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

λ-исчисление реализовано Джоном Маккарти в языке Лисп. В начале реализация идеи _ - исчисления была весьма громоздкой. Но по мере развития ЛИСП-технологии (прошедшей этап аппаратной реализации в виде Лисп-машины) идеи получили ясную и четкую реализацию.

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

1. Категориальная комбинаторная логика

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

2. Иллативная комбинаторная логика

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

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

Операторные методы

Вычет (комплексный анализ)

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

История

Теория вычетов одного комплексного переменного была в основном разработана О. Коши в 1825--1829 гг. Кроме него, важные и интересные результаты были получены Ш. Эрмитом, Ю. Сохоцким, Э. Линделёфом и многими другими.

В 1887 году А. Пуанкаре обобщил интегральную теорему Коши и понятие вычета на случай двух переменных,^* с этого момента и берёт своё начало многомерная теория вычетов. Однако, оказалось, что обобщить это понятие можно различными способами.

Одномерный комплексный анализ

Определение

Пусть f(z) -- комплекснозначная функция в области , голоморфная в некоторой проколотой окрестности точки . Вычетом функции f(z) в a называется число

.

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

В некоторой окрестности точки a функция f(z) представляется сходящимся рядом Лорана по степеням z − a. Нетрудно показать, что вычет совпадает с коэффициентом ряда c _{− 1} при (z − a) ^{− 1}. Часто это представление принимают за определение вычета функции.

Вычет в «бесконечности»

Для возможности более полного изучения свойств функции вводится понятие вычета в бесконечности, при этом она рассматривается как функция на сфере Римана. Пусть бесконечно удалённая точка является изолированной особой точкой f(z), тогда вычетом в бесконечности называется комплексное число, равное

.

Цикл интегрирования в этом определении ориентирован положительно, то есть против часовой стрелки.

Аналогично предыдущему случаю вычет в бесконечности имеет представление и в виде коэффициента лорановского разложения в окрестности бесконечно удалённой точки:

.

Вычет дифференциальной формы

С точки зрения анализа на многообразиях вводить специальное определение для некоторой выделенной точки сферы Римана (в данном случае, бесконечно удалённой) неестественно. Более того, такой подход затруднительно обобщить на более высокие размерности. Поэтому понятие вычета вводится не для функций, а для дифференциальных -форм на сфере Римана:

.

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

Логарифмические вычеты

Интеграл называется логарифмическим вычетом функции f(z) относительно контура L.

Понятие логарифмического вычета используется для доказательства теоремы Руше и основной теоремы алгебры

Способы вычисления вычетов

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

В устранимой особой точке , так же как и в точке регулярности, вычет функции f(z) равен нулю. В то же время для бесконечно удалённой точки это утверждение не верно. Например, функция имеет в бесконечности нуль первого порядка, однако, . Причина этого в том, что форма имеет особенность как в нуле, так и в бесконечности.

В полюсе a кратности n вычет может быть вычислен по формуле:

,

частный случай n = 1

.

Если функция имеет простой полюс в точке a, где g(z) и h(z) голоморфные в окрестности a функции, h(a) = 0, , то можно использовать более простую формулу:

.

Очень часто, особенно в случае существенно особых точек, удобно вычислять вычет пользуясь разложением функции в ряд Лорана. Например, , так как коэффициент при z ^{− 1} равен

Приложения теории вычетов

В большинстве случаев теория вычетов применяется для вычисления разного рода интегральных выражений с помощью основной теоремы о вычетах. Часто полезной в данных случаях бывает лемма Жордана.

Вычисления определённых интегралов от тригонометрических функций

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

.

Вычисление несобственных интегралов

Для вычисления несобственных интегралов с применением теории вычетов используют следующие две леммы:

1. Пусть функция f(z) голоморфна в верхней полуплоскости и на вещественной оси за исключением конечного числа n полюсов, не лежащих на вещественной оси и . Тогда

.

2. Пусть функция f(z) голоморфна в верхней полуплоскости и на вещественной оси за исключением конечного числа n полюсов, не лежащих на вещественной оси, и α > 0. Тогда

При этом интегралы в левых частях равенств не обязаны существовать и поэтому понимаются только лишь в смысле главного значения (по Коши).

Метод перевала

Метод перевала -- метод, использующийся для аппроксимации интегралов вида

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

Алгоритм решения

Свести интеграл к виду

Поскольку при поведение I(λ) определяется показателем экспоненты, то необходимо исследовать следующим образом функцию φ(z) :

Найти точки перевала, т. е. такие точки где выполняется соотношение: φ'(z) = 0

Построить линии наискорейшего убывания.

Деформировать контур γ по линиям наискорейшего убывания.

Получить асимптотику интеграла используя Метод Лапласа. 

Пример: Асимптотика функции Эйри

Функция Эйри задается следующим интегралом:

В качестве контура γ будем использовать тот, который представлен на рисунке справа. Сделаем замену и получим:

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

Хеширование

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