Алгоритм и его свойства. Программы

Всякая разумная деятельность упорядочена. Это означает, что человек стремится к достижению цели через после­дова­тельность доступных ему действий.

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

По одной из версий слово «алгоритм» (от латинского algorithm) получено транслитерацией (перезаписью буквами другого алфавита) имени древневосточного математика аль-Хорезми (аль-Хорезми – из Хорезма), под которым в средневековой Европе знали величайшего математика своего времени Муххамеда бен Мусу, жившего в 783–850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком.

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

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

Исходное состояние задачи: все на левом берегу. Налагаемые ограничения: не допустить, чтобы кто-нибудь кого-нибудь съел во время перевозки.

Обозначим движущуюся лодку стрелкой, волка, козу, капусту буквами – В, КЗ, КП.

1. Первой везем козу. Другие варианты невозможны, так как приводят к нарушению условий ( КЗ).

2. Лодка возвращается обратно, забирает капусту и везет на другой берег (  КП).

3. Капусту с козой оставлять нельзя, забираем козу обратно ( КЗ).

4. Оставляем козу, забираем волка и везем его к капусте ( В).

5. Затем возвращаемся за козой и перевозим ее на другой берег(  КЗ).

6. Задача решена.

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

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

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

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

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

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

Перечисленные свойства определяют требования, предъявляемые к способам реализации и представления алгоритмов. Так, например, дискретность алгоритма дает возможность рассматривать его с требуемой степенью детализации.

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

– содержательная (текстуальная или словесная форма);

– графическая форма (схемы алгоритмов);

– представление алгоритмов на языках программирования.

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

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

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

С

Начало-конец Блок ввода-вывода Блок ариф. вычислений Блок условий

Рис. 2.1. Обозначения графических элементов блок-схем

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

Для того, чтобы компьютер понял алгоритм, его переводят на язык понятный машине, т.е. записывают на одном из языков программирования ЭВМ. Под языком программирования понимается формальный язык, воспринимаемый ЭВМ и предназначенный для общения человека с машиной. Такие языки опре­де­ля­ются как входные языки вычислительной машины.

Существуют языки программирования различного уровня. Запись алгоритма на языках высокого уровня приближается к общепринятой математической форме записи.

Правила записи алгоритмов на языках программирования определяются правилами (синтаксисом и семантикой) каждого конкретного языка.

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

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

В основу построения подавляющего большинства ЭВМ положены следующие общие принципы, сформулированные в 1945 г. американским ученым венгерского происхождения Джоном фон Нейманом:

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

– принцип программного управления. Из него следует, что программа состоит из набора команд, которые выполняются процессором автоматически друг за другом в определенной последовательности;

– принцип однородности памяти. Программы и данные хранятся в одной и той же памяти. Поэтому ЭВМ не различает, что хранится в данной ячейке памяти – число, текст или команда. Над командами можно выполнять такие же действия, как и над данными;

– принцип адресности. Структурно основная память состоит из пронумерованных ячеек; процессору в произвольный момент времени доступна любая ячейка.

Машины, построенные на этих принципах, называются фон-неймановскими.

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

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

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

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

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

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

– полученная функция должна быть реализуема на машине Тьюринга.

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

Вопросы для самоконтроля

1. Что такое алгоритм?

2. Перечислите основные свойства алгоритма и кратко раскройте содержание каждого из них.

3. Назовите наиболее часто используемые формы представления алгоритма.

4. Какая из форм представления алгоритма является более наглядной?

5. Во что превращается алгоритм, записанный на языке программирования?

6. Сформулируйте основные принципы, положенные в основу функционирования большинства ЭВМ.

7. К

   акой вид деятельности человека не может быть алгоритмизирован и почему?