Понятие алгоритма. Свойства алгоритма. Исполнители алгоритмов (назначение, среда, режим работы, система команд). Компьютер как формальный исполнитель алгоритмов (программ).

Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика.

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

Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач...). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако, чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения:
1. Достать ключ из кармана.
2. Вставить ключ в замочную скважину.
3. Повернуть ключ два раза против часовой стрелки.
4. Вынуть ключ.

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

Свойства алгоритмов:
1. Дискретность (алгоритм должен состоять из конкретных действий, следующих в определенном порядке);
2. Детерминированность (любое действие должно быть строго и недвусмысленно определено в каждом случае);
3. Конечность (каждое действие и алгоритм в целом должны иметь возможность завершения);
4. Массовость (один и тот же алгоритм можно использовать с разными исходными данными);
5. Результативность (отсутствие ошибок, алгоритм должен приводить к правильному результату для всех допустимых входных значениях).

Виды алгоритмов:
1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке);
2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено задание);
3. Разветвляющий алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий)
4. Вспомогательный алгоритм (алгоритм, который можно использовать в других алгоритмах, указав только его имя).

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

Вид стандартного графического объекта	Назначение
	Начало алгоритма
	Конец алгоритма
	Выполняемое действие записывается внутри прямоугольника
	Условие выполнения действий записывается внутри ромба
	Счетчик кол-во повторов
	Последовательность выполнения действий.

Стадии создания алгоритма:
1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает.
2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия.

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

Исполнитель - объект, который выполняет алгоритм.

Идеальными исполнителями являются машины, роботы, компьютеры...

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

Исполнитель, как и любой объект, находится в определенной среде и может выполнять только допустимые в нем действия. Если исполнитель встретит в алгоритме неизвестную ему команду, то выполнение алгоритма прекратится.

Компьютер – автоматический исполнитель алгоритмов.

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой.

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

 

 

 

2 Структу́рноепрограмми́рование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом.

В соответствии с данной методологией

1. Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

· последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;

· ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;

· цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла).

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

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

3. Разработка программы ведётся пошагово, методом «сверху вниз».

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

 

2.1 Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления: последовательной (англ. sequence), ветвлений (англ. selection) и повторов или циклов (англ. repetition, cycle).

1. В последовательной структуре инструкции выполняются в том порядке, как они записаны в программе, то есть одна за другой.

· Например:

Подпрограмма 1 /* последовательное выполнение инструкций 1, 2 ..N…...*/

Инструкция 1;

 

Инструкция 2;

 

...

 

Инструкция N;

 

Конец Подпрограммы 1.

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

· Например:

Подпрограмма 2 /* ветвлений – Выбор инструкции согласно условию */

 

Если условие 1 то Инструкция 1; /* выполняется, если истинно условие 1 */

 

Если условие 2 то Инструкция 2; /* выполняется, если истинно условие 2 */

 

...

 

Иначе Инструкция N; /* выполняется, если ни одно из условий не является истинным */ .

 

Конец Подпрограммы 2.

3. В циклах инструкции повторяются до тех пор, пока не изменится некое условие, например значение логической переменной.

· Например:

Подпрограмма 3 /* цикл */

 

Пока условие N выполнить Инструкция N /* цикл повторяется пока верно условие N */

 

Инструкция N + 1 /* выход из цикла по нарушению условия N */

 

Конец Подпрограммы 3

Теорема была сформулирована и доказана итальянскими математиками КоррадоБёмом и Джузеппе Якопини (GiuseppeJacopini) в их статье 1966 года^[1]. В статье также описывались методы преобразования неструктурированных алгоритмов в структурированные на примере созданного Бёмом языка программирования P′′.

Публикация теоремы была толчком к началу дебатов о структурном программировании. Спустя 2 года вышла статья ЭдсгераДейкстры «GoToStatementConsideredHarmful»^[2], в которой он критиковал использование оператора GOTO и высказывался в пользу улучшения стиля программного кода за счёт использования структур управления и отказа от других инструкций, управляющих ходом алгоритма.

 

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

 

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

Разветвленный алгоритм (условие, структура выбора) - в классическом варианте эта структура рассматривается как выбор действий в случае выполнения или невыполнения заданного условия. Ветвления бывают полными и неполными.
Полное ветвление - это ветвление, в котором определенные действия определены и при выполнении, и в случае невыполнения условия. Неполное ветвление - это разветвление, в котором действия определены только при выполнении (или в случае невыполнения) условия.
Циклический алгоритм (цикл, структура повторения) - это алгоритм, в котором предусмотрено повторения некоторой серии команд. С помощью этой структуры описываются однотипные повторяющиеся несколько раз. Такие алгоритмы обеспечивают выполнение длинной последовательности действий, записанных сравнительно короткой последовательностью команд. Именно использование циклов позволяет в полной мере реализовать быстродействие компьютеров.
Основная особенность базовых алгоритмических структур - это их полнота, то есть этих структур достаточно для создания сложного алгоритма.

 

 

Оператор присваивания

Для того чтобы задать то или иное значение переменной используется оператор присваивания, который записывается как знак ‘=’. Работу этого оператора представим на следующем примере:

intlength = 5;

Здесь переменной с именем length присваивается значение 5, т.е. элемент слева от знака равенства является именем переменной, а элемент справа – это значение, присвоенное этой переменной. Сам символ ‘=’ называется оператором присваивания.

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

int i=2;
i=i+1;

С математической точки зрения такая операция не имеет смысла, т.к. переменная i не может быть равна i+1. Однако данная запись в смысле операции присваивания вполне приемлема. Действительно, компьютер сначала определит значение переменной i, а затем прибавит 1 к этому значению и полученный результат присвоит снова переменной i. Таким образом, исходное значение переменной i увеличится на 1.

Так как оператор присваивания задает значение переменной, то оператор типа

20 = i;

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

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

shortagr_short = -10;
long arg_long;

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

arg_long = arg_short;

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

floatagr_f = 8.7;
intarg_long;
arg_long = arg_f;

в операторе присваивания произойдет потеря данных, т.к. целое число не может представлять числа, стоящие после запятой (точки). В результате переменная arg_long будет иметь значение 8. Для корректного преобразования одного типа данных в другой используется операция приведения типов, имеющая следующий синтаксис:

<имя_переменной_1> = (тип_данных)<имя_переменной_2>;

Например,

arg_long = (long )arg_f;