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

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

* Комбинаторная логика -- трактовка вычисления сходна с _ - исчислением, но имеются и важные отличия (например, комбинатор неподвижной точки 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

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

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

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

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

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

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

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

Хеширование

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