Понятие алгоритма. Термин «алгоритм» (Algorithm) происходит от латинской формы напи­сания имени великого математика и астронома

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

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

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

1. Одно из первых требований, которое предъявляется к алгоритму, со­стоит в том, что описываемый процесс должен быть разбит на последова­тельность отдельных шагов. Возникающая в результате такого разбиения за­пись представляет собой упорядоченную совокупность четко разделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только вы­полнив требования одного предписания, можно приступить к выполнению следующего. Рассмотренное свойство алгоритмов называют дискретностью. Итак: дискретность (упорядоченность) означает, что все действия исполни­теля (компьютера) в алгоритме должны быть выстроены в четком, раз и на­всегда определенном порядке через отдельные шаги.

2. Чтобы составить алгоритм для определенного исполнителя, нужно знать, какие команды он может понять и выполнить, а какие нет. У каждого исполнителя имеется своя система команд и, очевидно, что составляя запись алгоритма для него, можно использовать лишь те команды, которые имеются в системе команд исполнителя. Это свойство алгоритмов называют понятно­стью. Итак: понятность алгоритма заключается в том, что каждый шаг ал­горитма обязательно представляет собой какое-либо допустимое действие исполнителя, т.е. алгоритм состоит только из предписаний, входящих в сис­тему команд данного исполнителя.

3. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно, т.е. одна и та же ко­манда, будучи понятна разным исполнителям, после исполнения каждым из них должна давать одинаковый результат. Запись алгоритма должна быть на­столько четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных со­ставителем алгоритма. Иначе говоря, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполни­телю неясно, какая из его команд должна выполняться на следующем шаге. Отмеченное свойства алгоритмов называютопределенностью или детерми­нированностью. Итак: детерминированность (определенность) имеет ввиду следующее - каждое правило должно быть однозначным, т.е. на каж­дом шаге однозначно определен способ действий.

4. Обязательное требование к алгоритмам - результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписа­ний алгоритма процесс должен прекратиться за конечное число шагов и при этом должен получиться определенный результат. Итак: результативность подразумевает, что каждый шаг (и алгоритм в целом) после своего заверше­ния дает однозначно определенный результат.

5. Наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной задачи, а некоторого класса задач данного типа. Это свой­ство алгоритма называютмассовостью. В простейшем случае массовость обеспечивает возможность использования различных исходных данных. Итак: массовость означает, что алгоритм должен быть как можно более уни­версальным, подходящим для решения разных типов задач.

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

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

При построении алгоритма для сложной задачи используют системный подход: использование принципов декомпозиции (нисходящее проектиро­вание «сверху-вниз») и синтеза (программирование «снизу-вверх»). Первое предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи, или модули со связями между собой) и их постепенную детализацию (пошаговое разбиение алгоритма на все бо­лее мелкие части до уровня элементарных конструкций, для которых можно составить конкретные команды). Затем (после декомпозиции) проводится сборка блоков (модулей) в единую программу (т.е. синтез). Кроме этих, при разработке алгоритмов применяется принцип «от главного к второстепен­ному», предполагающий составление алгоритма, начиная с главной конст­рукции и принцип структурирования, т.е. использования только типовых ал­горитмических структур при построении алгоритма.

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

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