logo
Курс лекций КИТ

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

При работе с компьютером пользователи часто употребляют фразы «программное обеспечение», «программа». Мы уже знаем, что программное обеспечение представляет собой совокупность программ. Но что такое программа? Можно сказать, что это последовательность инструкций для решения некоторой задачи, записанная на каком-либо языке программирования. Тогда возникает вопрос: «Как создаются программы?». На деле это очень сложная интеллектуальная деятельность, конечным результатом которой является работающая программа. Но на пути к этому результату необходимо пройти несколько этапов, которые называют этапами решения задачи на ЭВМ:

  1. Постановка задачи – выделение известных для решения задачи данных и выделение того, что будет результатом решения задачи. На первый взгляд это очень просто. Но повспоминайте свои проблемы в решении задач по математике в школе – наверняка бывали ситуации, кода вы задачу решили, но получили не тот ответ. Почему? Потому что неправильно поняли условие задачи! То есть неправильно выполнили постановку задачи. То есть, в конечном счете, была решена другая задача.

На этом же этапе все данные обозначаются (именуются), оговариваются их возможные значения, единицы измерения.

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

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

  2. Конструирование алгоритма – описание последовательности действий для решения задачи на естественном языке. Понятие алгоритма разберем чуть позднее.

  3. Разработка программы – фактически это преобразование алгоритма в команды на языке программирования.

  4. Отладка программы – выявление ошибок в программе посредством многократного запуска программы на исполнение с различными исходными данными. Это наиболее длительный этап (около 90% времени подготовки задачи для решения на ЭВМ) и очень влияющий на качество программы. Все «дыры» в программном обеспечении (о которых регулярно пишут в прессе и на которые ориентируются хакеры) образуются в результате некачественной отладки программ.

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

  6. Решение задачи – эксплуатация программы заказчиком.

Теперь более подробно разберемся с понятием «алгоритм».

Человек регулярно в жизни сталкивается с алгоритмами – это разнообразные инструкции (например, правила пользования междугородним телефоном), рецепты, правила (например, порядок действий при пожаре) и др.

Термин «алгоритм» произошёл от имени среднеазиатского учёного IX века Мухаммеда ибн Муса ал-Хорезми (в переводе с арабского означает «Мухамед сын Мусы из Хорезма»), который описал десятичную систему счисления и впервые сформулировал правила выполнения арифметических действий над целыми числами и простыми дробями. Правила эти и сегодня служат простейшими примерами математических алгоритмов.В латинском переводе эти правила начинались словами «Алгоризми сказал». Постепенно люди забыли, что Алгоризми — это автор правил, и стали сами эти правила называть алгоритмами.

Большой вклад в теорию алгоритмизации внес английский ученый Алан Тьюринг (1912-1954) - разработал понятие абстрактной цифровой вычислительной машины (получившей впоследствии название машины Тьюринга), способной имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому. Неоценим вклад в развитие теории алгоритмизации советского ученого Андрея Маркова, предложившего нормальный алгоритм (названный нормальным алгоритмом Маркова), демонстрирующий работу идеальной машины, разработавшего теорию сложности алгоритмов Впоследствии теория алгоритмов была разработана американским ученым Дональдом Кнутом (род в 1938 г.), семитомный труд которого «Искусство программирования для ЭВМ» и в наше время многократно переиздается и изучается специалистами. В советской школе изучение информатики началось с 1985 года, благодаря деятельности А.П. Ершова.

Строгого математического определения алгоритма не существует. Используются понятия, которые в различной степени детализируют понятие алгоритма. Так, под алгоритмом понимается упорядоченная последовательность действий, приводящая к получению результата (точное предписание, определяющее вычислительный процесс, ведущее от начальных данных к искомому результату).

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

Алгоритм должен обладать следующими свойствами:

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

- конечность – число шагов для достижения результата обязательно должно быть конечным;

- результативность - после завершения алгоритма должен быть получен результат или сообщение о невозможности его получения;

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

Рассмотрим алгоритм открывания двери ключом:

  1. Вставить ключ в замочную скважину.

  2. Повернуть 2 раза против часовой стрелки.

  3. Вынуть ключ.

  4. Потянуть дверь на себя.

Обладает ли этот алгоритм свойством массовости?

Необходимо разобрать еще уже упоминавшиеся понятия: