Вопрос 40-41

Оценка сложности алгоритмов.

Причины анализа сложности:

1) Необходимость получения оценок или границ объема памяти, которой может потребоваться алгоритму. Выявление «узких» мест алгоритмов по времени или памяти.

2) Необходимость выработать критерии для сравнения алгоритмов:

-выработка абсолютного критерия;

-выработка критерия для сравнения двух алгоритмов.

Три направления критерия алгоритмов:

1) Поиск хорошо понимаемых оценок сложности.

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

2) Включение параметров вычислительной модели в качестве аргументов с сложностную функцию.( оценка сложности Шенона для машин Тьюринга).

3) Аксиоматический подход Блюма.

Функция сложности должна удовлетворять 2ум аксиомам:

1. V(i, x)определена тогда и только тогда, когда С(i, x) (С-функция сложности) определена.

2.Множество (<i, x, y>|C(i, х)=y) разрешимо. («|» означает «при условии») .

Теорема о рекурсивной связи различных мер сложности:

Пусть существует С1 и С2(меры сложности) для одной и той же главной функции V(i, x), тогда существует такая D, что для всех номеров i выполняется:

C1(i, x)>=D(C2(i, x)) и V(i, x) определена.

Теорема о ускорении:

Пусть С-мера сложности, R – всюду определённая вычислимая функция, тогда для любого i, существуют такое j, что справедливо неравенство:

С(i, x)<=R(C(j, x))

Оценка сложности производится для целого класса алгоритмов.

Вопрос 42

Единичная проблема состоит в требовании предъявить объект, удовлетворяющий определенным условиям и называе­мый решением проблемы; решить проблему — значит ука­зать такой объект; если решение существует, т. е. если про­блему можно решить, проблема называется решимой.

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

Задача (массовая проблема) - некоторый общий вопрос, на который должен быть дан ответ.

Как правило задача имеет 1 или несколько параметров. Фиксированное значение параметров образует исходные данные задачи, которые будем называть входом.

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

Массовая проблема характеризуется:

1) Точным описанием допустимых значений параметров (множество допустимых входов).

2) Заданием условий, которым должен удовлетворять ответ.

Пример задачи.

1. Определить наибольший общий делитель чисел X и Y.

Вход: натуральные числа X и Y.

Ответ: максимальное натуральное число Z, такое, что X%Z=0 и Y%Z=0. (Под операцией % понимается остаток от деления).

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

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

Алгоритм должен обладать следующими свойствами:

Описание алгоритма конечно, при этом предполагается, что существует объект, понимающий и выполняющий это описание. Такой объект назовем вычислителем.

1) Должны быть четко указаны условия остановки процесса и что следует считать результатом процесса. (Свойство результативности)

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

3) Процесс решения одной и той же индивидуальной задачи протекает одинаково. (Свойство называется детерминированностью.)

Не для каждого алгоритма очевидно, что он приводит в правильному решению поставленной задачи. Если правильность алгоритма не очевидна, то алгоритм нуждается в доказательстве.

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

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