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

Первым дошедшим до нас алгоритмом считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел - алгоритм Евклида
Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя 1931 год - теорема о неполноте символических логик
Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом
В 1950-е годы существенный вклад в теорию алгоритмов внесли работы Колмогорова и Маркова.

К 1960-70-ым годам оформились следующие направления в теории алгоритмов:
Классическая теория алгоритмов
Теория асимптотического анализа алгоритмов
Теория практического анализа вычислительных алгоритмов

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

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

Понятие алгоритма
Определение 1.1: Алгоритм - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.
Определение 1.2 (Колмогоров): Алгоритм – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Определение 1.3 (Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.