3. Интуитивное и формальное определение алгоритма.

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

Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи. Пусть D – область (множество) исходных данных задачи, а R – множество возможных результатов, тогда мы можем говорить, что алгоритм осуществляет отображение D → R. Поскольку такое отображение может быть не полным, то вводятся следующие понятия: Алгоритм называется частичным алгоритмом, если мы получаем результат только для некоторых d є D и полным алгоритмом, если алгоритм получает правильный результат для всех d є D.

Современное формальное определение алгоритма было разработано в 30–50-х гг. XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А.А. Маркова. Несмотря на усилия исследователей, отсутствует одно исчерпывающе строгое определение понятия алгоритм, в теории алгоритмов были введены различные формальные определения алгоритма.

Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову:

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

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

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

• алгоритм должен выполнять конечное количество шагов при решении задачи;

• алгоритм должен быть единым для всех допустимых исходных данных, т.е. быть универсальным;

• алгоритм должен приводить к правильному по отношению к поставленной задаче решению;

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

3. Теория сложности в теории алгоритмов.

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

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

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

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

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

Классы сложности.

Классами сложности – множества вычислительных задач, примерно одинаковых по сложности вычисления.

1. Класс P (от англ. polynomial) – класс алгоритмов, работающих за полиноминальное время, время работы не существенно зависит от размера входных данных. Стандартные алгоритмы целочисленного сложения, перемножения матриц и др.

2. Класс NP (от англ. non-deterministic polynomial) – класс алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (сертификат решения), то он сможет достаточно быстро решить задачу. Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Сертификат — такой набор. Существование целочисленного решения у заданной системы линейных неравенств. Сертификат — решение.

3. Класс BPP (от англ. bounded-error, probabilistic, polynomial) – класс алгоритмов, быстро (за полиномиальное время) вычислимых и дающих ответ с высокой вероятностью (причём, жертвуя временем, можно добиться сколь угодно высокой точности ответа). Решение СЛАУ методом половинного деления, методом хорд и др.