Основные понятия и определения дисциплины.
Теория алгоритмов, как наука, непосредственно связана с предметами математической логики и теории конечных автоматов. В Древней Греции Аристотель и его ученик Платон сформулировали основные правила логики, которые используются до нашего времени для доказательства правильности и решения логических задач.
Математическая логика – это наука о правилах формального логического мышления.
Теория автоматов изучает модели конечных автоматов, описывающие вычислительные узлы и элементы управления ЭВМ и других технических устройств.
История развития теории алгоритмов.
Начало развития теории алгоритмов связывают с именем узбекского математика Аль-Хорезми (IX в.), который сформулировал правила умножения и деления чисел в десятичной системе счисления.
В 1936 году английский ученый Тьюринг разработал модель вычислительной машины для решения задач на основе алгоритмов и доказал:
возможность автоматического решения задач с помощью алгоритмов, реализуемых в виде программы;
реальность создания универсальных вычислительных машин.
На основе этой модели («машина Тьюринга») была построена классическая теория алгоритмов.
В Древней Греции Платон сформулировал основные правила логики.
В XX веке начали развиваться науки, направленные на создание ЭВМ. Их работу было принято описывать в виде алгоритмов. В начале ХХ века понятие алгоритма стало объектом математического изучения, а развитие ЭВМ и языков программирования способствовало выделению теории алгоритмов как самостоятельной дисциплины.
Сегодня понятие алгоритма вышло за пределы математики и используется в различных областях, где алгоритм – это точно сформулированное правило, являющееся руководством для достижения необходимого результата. Кроме того, алгоритмы являются первоосновой для программирования задач на ЭВМ.
Роль алгоритмов в науке и технике.
Было выявлено, что если удается получить алгоритм решения какой-либо задачи, то эту задачу можно решать автоматически с помощью технических устройств.
Таким образом, алгоритмы являются:
формой изложения научных результатов;
руководством к действию при решении уже изученных проблем;
средством автоматического решения задач;
инструментом, используемым при исследовании и решении новых проблем;
средством обоснования в математике;
одним из средств описания сложных процессов.
Хотя алгоритмы важны для практики, практическая потребность не является первичной при изучении и разработке алгоритмов. Часто они разрабатываются для решения задач, которые не имеют пока практического применения. Однако многие научные результаты, полученные без практики, рано или поздно находят свое практическое применение.
Понятие алгоритма и алгоритмического процесса.
Существуют 2 основных понятия алгоритма:
1 – интуитивное;
2 – формальное.
1. Алгоритм в интуитивном смысле – это точное предписание о выполнении в определенном порядке некоторой последовательности операций для решения всех задач некоторого заданного типа.