Тема 24. Элементы теории алгоритмов. Цели и задачи теории алгоритмов. Формализация понятия алгоритмов: определение Колмогорова, определение Маркова

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

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

Среди других определений рассматривают определение Колмогорова.

Определение.Алгоритм – всякая система вычислений по определенным данным, которые после числа шагов приводят к решению задачи.

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

Определения не являются математически строгими и характеризуют набор свойств алгоритма.

Свойства алгоритма:

• Дискретность информации. Каждый алгоритм имеет дело с входными, промежуточными, выходными данными, которые представлены в виде конечных слов в некотором формате.
• Дискретность работы алгоритма. Алгоритм выполняется по шагам. На каждом шаге выполняется только одна операция.
• Выполнимость операций. В алгоритме не должно быть невыполнимых операций.
• Конечность алгоритма. Описание алгоритма должно быть конечным.
• Детерминированность алгоритма. Каждый шаг алгоритма строго определен. После каждого шага указывается какой шаг сделать следующим или указывается, что алгоритм должен закончить работу.
• Массовость алгоритма. Алгоритм должен решать задачи из данного класса задач. Если найдется задача, для которой алгоритм не применим, то последовательность нельзя назвать алгоритмом.

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

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

Цели и задачи теории алгоритмов

Обобщение результатов позволяет выделить цели и соотнесенные задачи:

1. Формализация понятия алгоритма и исследование формальных алгоритмических систем.
2. Формальные доказательства неразрешимости ряда задач.
3. Классификация задач, исследование сложных классов.
4. Алгоритмический анализ сложности алгоритма.
5. Исследование и анализ рекурсивных алгоритмов.
6. Получений явных функций трудоемкости алгоритма с целью их сравнительного анализа.
7. Разработка критериев оценки качества алгоритма.

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

Теоретики, оценивая сложность алгоритма, строят математическую модель машины Тьюринга. Тогда количество шагов для машины Тьюринга определяет его сложность.