Общие сведения об алгоритме

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

Свойства алгоритма:

• дискретность (прерывность, раздельность) – разбиение алгоритма на шаги;

• понятность – каждый шаг алгоритма должен быть понятен исполнителю;

• точность – указание последовательности шагов;

• результативность – получение результата за конечное число шагов;

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

Способы описания алгоритма:

• словесный (письменно или устно);

• графический (стрелками, рисунками, блок-схемами);

• программный

Блок-схема алгоритма – наглядное графическое изображение структуры алгоритма. Она строится из блоков, соединенных стрелками. Стрелки изображают последовательность вычислений.

Чаще всего используются блоки следующих типов:

- выполнение операции,

- выбор направления выполнения алгоритма в зависимости от некоторых переменных условий,

- ввод/вывод данных,

- начало и конец алгоритма.

ЛИНЕЙНЫЕ АЛГОРИТМЫ

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

Блок-схема базовой структуры.
Следование.

ЦИКЛИЧЕСКИЕ АЛГОРИТМЫ

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

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

Блок-схема базовой структуры.
Цикл с параметром.

Вход

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

Блок-схемы базовых структур.

Цикл – пока

(может не выполнятся ни разу).

Цикл – до

(выполняется хотя бы раз)

Вход

РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ

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

Блок-схемы базовых структур.

Развилка полная

Развилка неполная

Выбор

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

это такое

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

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

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

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

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

Каждый человек в своей повседневной жизни, в учебе или на работе сталкивается с необходимостью решения огромного количества задач самой разной сложности. Некоторые из них настолько трудны, что требуют длительных размышлений для поиска решений (а иногда найти его так и не удается ). Другие же, напротив, столь просты и привычны, что решаются автоматически. Решение задачи «Поступить в институт» намного труднее и требует выполнения гораздо большего количества сложных действий, чем решение задачи «Купить мороженое». При этом выполнение даже самой простой задачи обычно осуществляется в несколько последовательных этапов, или шагов. Если проанализировать ход выполнения этих задач, то окажется, что практически любое действие, которое надо при этом произвести, может быть чётко сформулировано и записано.

Например, процесс приготовления обеда можно описать так:

1. Сварить суп.

2. Приготовить второе блюдо.

3. Приготовить десерт.

Такая запись (назовём её инструкцией) малополезна на практике. Ясно, что шаги должны быть более простыми, поэтому необходимо несколько детализировать её (ограничимся первым пунктом):

1. вымыть, почистить и нарезать овощи;

2. зажечь плиту;

3. вскипятить в кастрюле воду;

4. положить в кипящую воду мясо;

5. когда мясо сварится, положить в кастрюлю овощи;

6. когда овощи сварятся, выключит плиту.

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

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

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

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

Всегда ли удаётся получить результат, применяя алгоритм к некоторому набору из множеств допустимых исходных данных? Не всегда, так, при делении 7 на 3 оба целых числа допустимы, но результат 2,333… является бесконечной десятичной дробью. Об алгоритмах такого рода говорят, что они потенциально выполнимы, но состоят из бесконечного числа шагов. В связи с этим надо вести понятие конечности алгоритма. Смысл его состоит в том, что выполнение алгоритма должно обязательно приводить к его завершению. В то же время можно привести примеры формально бесконечных алгоритмов, широко применяемых на практике. Например, алгоритм работы системы сбора метеорологических данных состоит в непрерывном повторении последовательности действий «Измерить температуру воздуха» и «Определить атмосферное давление», выполняемых с некоторой частотой (ежеминутно, ежечасно или ежедневно) всё время существования данной системы.

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

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

Отсюда вытекает следующее важное требование к алгоритму – определённость. На каждом шаге алгоритма у исполнителя должно быть достаточно информации, чтобы его выполнить. Кроме того, исполнителю нужно чётко знать, каким образом он выполняется. Легко заметить, что некоторые шаги приведённого выше алгоритма приготовления супа, в свою очередь, нуждаются в уточнении (так, пункт «Зажечь плиту» потребует выполнения последовательности действий «Взять коробок спичек», «Зажечь спичку», «Повернуть вентиль газовой плиты», «Поджечь газ»). Следовательно, чтобы выполнялось требование определённости, шаги инструкции должны быть достаточно простыми, элементарными, а исполнитель должен однозначно понимать смысл каждого шага последовательности действий.