 |
Свойства алгоритмов (требования к алгоритмам).
|
|
|
|
1. Дискретность. Свойство алгоритма “дискретность” определяется как – возможность разбиения алгоритма на отдельные элементарные действия. Процесс решения задачи должен быть разбит на последовательность отдельных шагов. Так формируется упорядоченная совокупность отделенных друг от друга команд (предписаний). Образованная структура алгоритма оказывается прерывной (дискретной): только выполнив одну команду, исполнитель может приступать к следующей.
2. Понятность. Свойство алгоритма “понятность ” определяется как – включение в алгоритм команд только из системы команд исполнителя. Алгоритм должен быть понятен исполнителю, и исполнитель должен быть в состоянии выполнить его команды. Следовательно, алгоритм нужно разрабатывать с ориентацией на определенного исполнителя, то есть в алгоритм можно включать команды только из системы команд данного исполнителя.
3. Детерминированность (определенность). Свойство алгоритма “детерминированность ” определяется как – однозначность получения результата при одних и тех же исходных данных. Будучи понятным, алгоритм не должен содержать команды, смысл которых может восприниматься неоднозначно. (Например, автомат будет поставлен в тупик командой “взять две – три ложки песка”; что означает “две – три ложки”?, какого песка?). Недопустимы ситуации, когда после выполнения очередной команды, исполнителю не ясно, какую команду выполнять на очередном шаге. Нарушение составителем алгоритма этих требований (называемых требованием определенности или детерминированности) приводит к тому, что одна и та же команда, при выполнении разными исполнителями, дает неодинаковый результат.
|
|
|
4. Результативность. Свойство алгоритма “результативность” определяется как – получение за конечное число шагов результата, определенного постановкой задачи. Смысл этого обязательного требования состоит в том, что при точном исполнении всех команд алгоритма процесс решения задачи должен прекратиться за конечное число шагов и при этом должен быть получен определенный постановкой задачи результат.
5. Массовость. Свойство алгоритма “массовость ” определяется как – возможность получения искомого результата при решении всего класса задач данного типадля любых допустимых исходных данных. Разработка алгоритма – процесс творческий, но не простой, требующий многих усилий и затрат времени. Поэтому предпочтительно разрабатывать алгоритмы, обеспечивающие решение всего класса задач данного типа. Например, если составляется алгоритм решения квадратного уравнения
AX2 + BX + C = 0, он должен быть вариативен, то есть обеспечивать возможность решения для любых допустимых значений коэффициентов A, B, C. Про такой алгоритм говорят, что он удовлетворяет требованию массовости.
Формальное исполнение алгоритма.
Алгоритмы могут описывать процессы преобразования самых разных объектов.
Алгоритм позволяет формализовать выполнение информационного процесса. Если исполнителем алгоритма является человек, то он может выполнять алгоритм формально, не вникая в содержание поставленной задачи, а только строго выполнять последовательность действий, предусмотренных алгоритмом.
! Формальное выполнение алгоритма не требует рассуждений, он выполняется автоматически.
Представление информационного процесса в форме алгоритма позволяет поручить его автоматическое исполнение различным техническим устройствам, среди которых особое место занимает компьютер. При этом говорят, что компьютер исполняет программу (последовательность команд), реализующую алгоритм.
|
|
|
Работа компьютера моделирует информационные процессы, Но, компьютер – техническое устройство, поэтому для того, чтобы он выполнил определенные действия, им нужно управлять. Компьютер действует как автоматический формальный исполнитель алгоритмов обработки информации.
Алгоритм, записанный на понятном компьютеру языке, называется программой.
Компьютерная программа – это закодированная информация о действиях, которые предписывается выполнить компьютеру, алгоритм для выполнения компьютером, записанный на языке машинных двоичных кодов, или на специальном языке программирования.
! Язык программирования – это средство описания алгоритма, ориентированное на исполнителя – ЭВМ.
Пользователь вводит в компьютер команды компьютерной программы, написанной на языке программирования. Компьютер воспринимает программу на языке машинных кодов, поэтому, команды компьютерной программы, написанной на языке программирования, автоматически переводятся в машинные коды благодаря программе-переводчику – транслятору.
! Трансляторы – это комплекс программ, обеспечивающий перевод программ, которые написаны на языке программирования, в совокупность машинных кодов.
Структуры алгоритмов
При изучении алгоритмов важно осознать, что существует много различных возможностей для представления (описания) одного и того же алгоритма.
Алгоритм можно представить как некоторые жесткие структуры, состоящие из отдельных базовых элементов. Основные структуры алгоритмов – это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей действий.
Алгоритм любой степени сложности можно построить с помощью блоков основного базового набора. Каждая из этих структур имеет только один вход и только один выход, что позволяет соединять их между собой в любой последовательности. В результате графической формы представления алгоритмов получаем блок-схему.
Приводимые ниже структуры рекомендуются при использовании, так называемого, структурного подхода к разработке алгоритмов и программ. Структурный подход предполагает использование только нескольких основных структур, комбинация которых, дает все многообразие алгоритмов и программ.
|
|
|
В1969 году Эдстер В. Дийкстра в статье «Структуры данных и алгоритмы» доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: линейных (последовательных), ветвящихся, циклических.
! Важнейший принцип структурного программирования базируется на утверждении: алгоритм любой сложности можно построить с помощью следующих базовых структур: линейной, ветвящейся, циклической.
На практике чаще встречаются алгоритмы смешанного типа, у которых можно выделить участки (блоки), имеющие структуру линейного, ветвящегося или циклического типа.
I. Линейный алгоритм – это алгоритм, в котором команды выполняются последовательно одна за другой (Рис. 3). Такая последовательность команд называется серией. В линейной структуре имеем последовательное размещение блоков и групп блоков. В программе реализуется последовательным размещением операторов.
! Алгоритм называется линейным, если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий.
II. Алгоритмическая структура «ветвление»
В алгоритмическую структуру “ветвление” входит условие, в зависимости от выполнения или невыполнения которого реализуется та или иная последовательность команд (серия).
Условие – это логическое выражение, которое
может принимать значение «да», если условие верно,
и «нет», если условие не выполняется. Рис. 4.
В алгоритмической структуре “ветвление” та или иная серия команд выполняется в зависимости от истинности того или иного условия (Рис 4).
! Алгоритм включает в себя ветвление, если ход его выполнения зависит от истинности тех или иных условий.
Ветвление организуется с помощью логического элемента (ромб с записанным внутри условием), имеющего один или несколько (в простейшем случае – два) выходов.
Назначение логического элемента – проверка заданного условия. В зависимости от выполнения (истинности) или невыполнения (ложности) проверяемого условия возможен выход соответственно на ветвь “Да” или “Нет”.
|
|
|
Условия бывают простыми, они включают в себя два числа, две переменных или два арифметических выражения, которые сравниваются между собой с помощью операторов сравнения: =; <; >; <=; >=; <>.
Сложное условие – это последовательность простых условий, объединенных между собой знаками логических операций: Not (Не); And (И); Or (Или).
На естественном языке ветвлению соответствует последовательность операторов:
Если <условие справедливо>
то < выполнить действие 1>
иначе <выполнить действие 2>
Конец ветвления
II a. Алгоритмическая структура «выбор» (Рис. 5)применяется для ветвления со многими вариантами серий команд.
Такая структура может иметь несколько условий, их проверка происходит в строгой последовательности их записи в команде. При истинности одного их условий выполняется соответствующая последовательность команд. В алгоритмической структуре «выбор» выполняется одна из нескольких последовательностей команд при истинности соответствующего условия
|
|
|
