Общие положения. 3

Теория алгоритмов 3

Абстрактная теория алгоритмов 3

Метрическая теория алгоритмов 3

Предмет и содержание читаемого курса. 5

Предмет изучения 5

Цель 5

Содержание курса 5

Исходные понятия теории алгоритмов. 5

Алгоритм 5

Конструктивный объект 5

Свойства и параметры алгоритма: 6

Основная гипотеза теории алгоритмов. 7

Формальные модели, уточнение понятия алгоритм. 7

Блок-схемы детерминированных алгоритмов. 8

Алгоритмический язык 9

Алгоритмическая система А.Тьюринга. 9

а. Разрешимость и неразрешимость языков машиной Тьюринга 10

б. Проблема остановки машины Тьюринга 10

Алгоритмическая система А.Чёрча 11

a. Базисные функции 11

1. Нуль-функция 11

2. Функция тождества 12

3. Функция следования 12

б. Операторы построения производных рекурсивных функций 12

1. Оператором суперпозиции(подстановки) 12

2. Оператором примитивной рекурсии 12

3. Оператор минимизации ( - оператор) 13

Примитивно-рекурсивные функции. 14

Алгоритмическая система А.А.Маркова. 15

Ассоциативное исчисление 17

Алгоритмически неразрешимые проблемы. 18

Теоремы алгоритмически разрешимых и неразрешимых проблем. 19

Теоремы Геделя. 19

I. Теорема о неполноте 19

II. Теорема о полноте 19

Словарь основных терминов. 21

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

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

В настоящее время теорию алгоритмов делят на дескриптивную (абстрактную) и метрическую (структурную, прикладную).

Примечаний нет.