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

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Калининградский государственный технический университет»

Кафедра систем управления и вычислительной техники

Топоркова О.М.

КОНСПЕКТ ЛЕКЦИЙ ПО ОСНОВАМ ТЕОРИИ АЛГОРИТМОВ

(по материалам учебного пособия проф. Пономарева В.Ф.

«Основы теории алгоритмов»)

Калининград 2012

Оглавление

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

2. Основные понятия теории алгоритмов. 4

3. Рекурсивная функция. 5

3.1. Базовые функции. 6

3.2. Элементарные операции. 6

4. Машина Тьюринга. 9

4.1. Описание машины Тьюринга. 10

4.2. Примеры машин Тьюринга. 12

5. Нормальный алгоритм Маркова. 14

6. Вычислимость и разрешимость. 16

7. Сложность вычислений. 17

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

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

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

Следовательно, существование алгоритма (компьютерной программы) для решения задачи – вовсе не признак того, что эта проблема является разрешимой с практической точки зрения.

Обобщая результаты различных разделов теории алгоритмов, можно выделить следующие цели и соотнесенные с ними задачи, решаемые в теории алгоритмов:

· формализация понятия «алгоритм» и исследование формальных алгоритмических систем;

· формальное доказательство алгоритмической неразрешимости ряда задач;

· классификация задач, определение и исследование сложностных классов;

· анализ сложности алгоритмов;

· исследование и анализ рекурсивных алгоритмов;

· получение явных функций трудоемкости в целях сравнительного анализа алгоритмов;

· разработка критериев сравнительной оценки качества алгоритмов.

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

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

2. Практический аспект - методы и методики теории алгоритмов позволяют осуществить:

a. рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти);

b. получение временных оценок решения сложных задач;

c. получение достоверных оценок невозможности решения некоторой задачи за определенное время, что важно для криптографических методов;

d. разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации на основе практического анализа.