Тема 1. Основные понятия и определения дисциплины.

1.1 История развития теории алгоритмов.

Начало развития теории алгоритмов связывают с именем узбекского математика Аль-Хорезми (IX в.), который сформулировал правила умножения и деления чисел в десятичной системе счисления.

В 1936 году английский ученый Тьюринг разработал модель вычислительной машины для решения задач на основе алгоритмов и доказал:

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

• реальность создания универсальных вычислительных машин.

На основе этой модели («машина Тьюринга») была построена классическая теория алгоритмов, основу которой составляли формальные описания следующих понятий:

1 – алгоритм;

2 – алгоритмический процесс;

3 – взаимосвязь между 1-м и 2-м.

В Древней Греции Платон сформулировал основные правила логики. Он доказал, что математическая логика – это наука о правилах формального логического мышления.

В XX веке начали развиваться науки, направленные на создание ЭВМ. Их работу было принято описывать в виде алгоритмов. В начале ХХ века понятие алгоритма стало объектом математического изучения, а развитие ЭВМ и языков программирования способствовало выделению теории алгоритмов как самостоятельной дисциплины.

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

Сегодня понятие алгоритма вышло за пределы математики и используется в различных областях, где алгоритм – это точно сформулированное правило, являющееся руководством для достижения необходимого результата. Кроме того, алгоритмы являются первоосновой для программирования задач на ЭВМ.

1.2 Роль алгоритмов в науке и технике.

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

Таким образом, алгоритмы являются:

• формой изложения научных результатов;

• руководством к действию при решении уже изученных проблем;

• средством автоматического решения задач;

• инструментом, используемым при исследовании и решении новых проблем;

• средством обоснования в математике;

• одним из средств описания сложных процессов.

Хотя алгоритмы важны для практики, практическая потребность не является первичной при изучении и разработке алгоритмов. Часто они разрабатываются для решения задач, которые не имеют пока практического применения. Однако многие научные результаты, полученные без практики, рано или поздно находят свое практическое применение.

1.3 Понятие алгоритма.

Существуют 2 основных понятия алгоритма:

1 – интуитивное;

2 – формальное.

1. Алгоритм в интуитивном смысле – это точное предписание о выполнении в определенном порядке некоторой последовательности операций для решения всех задач некоторого заданного типа.

Содержание алгоритма, удобного для решения какой-либо задачи, позволяет использовать его даже человеку-непрофессионалу. Кроме того, его можно техническим устройством, выполняющим алгоритм автоматически (ЭВМ по заданной программе).

Формализация понятия алгоритма не должна учитывать ограниченность ресурсов, необходимых для его реализации, но требовать конечности этих ресурсов, т. е. возможной реализации как таковой.

2. Формальное определение алгоритма дается на основе математических методов и основывается либо на других понятиях, имеющих математическое определение, либо на понятиях-аксиомах.

На основе свойств алгоритма можно сформулировать формальное определение. Алгоритм – это правило, сформулированное на некотором языке и определяющее процесс преобразования исходных данных в искомые результаты (алгоритмический процесс). При этом допустимые исходные данные представлены как предложения на языке исходных данных.

Алгоритм характеризуется:

• понятностью;

• массовостью;

• детерминированностью

и др.

В тех случаях, когда правило применимо к допустимым исходным данным, оно потенциально осуществимо.

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

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

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

• язык;

• понятность;

• точность.

интуитивные понятия,

смысл которых ясен, а научные

определения не составлены.