Понятие алгоритма и его свойства

АЛГОРИТМИЗАЦИЯ

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

Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

Блок-схема – описание структуры алгоритма с помощью геомет­рических фигур с линиями-связями, показывающими порядок вы­полнения отдельных инструкций. Этот способ имеет ряд преиму­ществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных ко­манд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями сово­купность фигур.

Рассмотрим некоторые основные конструкции, использующие­ся для построения блок-схем.

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

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

Программа – описание структуры алгоритма на языке алгорит­мического программирования.

Арифметический цикл

В арифметическом цикле число его шагов (повторений) одно­значно определяется правилом изменения параметра, которое зада­ется с помощью начального (N) и конечного (К) значении параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение па­раметра равно N, на втором N+h, на третьем – N+2h и т.д. На последнем шаге цикла значение параметра не больше К, но та­кое, что дальнейшее его изменение приведет к значению, большему, чем К.

Пример: Вывести 10 раз слово «Привет!».

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i = 1 будет выведено первое слово, при i = 2 будет выведено второе слова и т.д. Так как требуется вывести 10 слов, то последнее значение параметра i = 10. В заданном примере требу­ется 10 раз повторить одно и то же действие: вывести слово «Привет!».

Составим алгоритм, ис­пользуя арифметический цикл, в котором правило изменения параметра i – 1, 10, 1. То есть начальное значение параметра i = 1; конечное значение i =10; шаг изменения h = 1. На рисунке представлена блок-схема алгоритма решения данной за­дачи.

Рисунок – Блок-схема к примеру

Цикл с предусловием

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выпол­нением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь пе­редается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При пер­вом же несоблюдении условия цикл завершается.

а б

Рисунок – Блок-схема цикла с предусловием

Блок-схема данной конструкции представлена на рисунке двумя способами; с помощью условного блока а и с помощью блока гра­ницы цикла б.

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

Цикл с постусловием

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

блока а и с помощью блока управления б.

а б

Рисунок – Блок-схема цикла с постусловием

Рекурсивный алгоритм

Рекурсивным называется алгоритм, организованный таким обра­зом, что в процессе выполнения команд на каком-либо шаге он пря­мо или косвенно обращается сам к себе.

АЛГОРИТМИЗАЦИЯ

Понятие алгоритма и его свойства

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

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

Значение слова «алгоритм» очень схоже со значениями слов «ре­цепт», «метод», «процесс», Однако, в отличие от рецепта или про­цесса, алгоритм характеризуется следующими свойствами: дискрет­ностью, массовостью, определенностью, результативностью, формальность.

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

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

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

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

Формальность – это свойство указывает на то, что любой испол­нитель, способный воспринимать и выполнять инструкции алгорит­ма, действует формально, т.е. отвлекается от содержания поставлен­ной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

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

1.совокупность возможных исходных данных;

2.совокупность возможных промежуточных результатов;

3.совокупность результатов;

4.правило начала;

5.правило непосредственной переработки;

6.правило окончания;

7.правило извлечения результата.

Пример. Алгоритм вычисления корней квадратного уравнения .

Исходные данные – коэффициенты уравнения: а – при второй степени неизвестного; b – при первой степени неизвестного; с – при нулевой степени неизвестного.

Искомый результат – значения корней уравнения х₁ и х₂.

Предписание:

1. Вычислить значение дискриминанта по формуле .

2. Если , то вычислить значения корней уравнения по формулам:

3. Если , то уравнение не имеет корней.

Приведенное предписание обладает всеми свойствами алгоритма:

· дискретностью – предписание разбито на этапы (шаги выполнения);

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

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

· массовостью – в предписании составлено для общего случая (указаны не конкретные значения коэффициентов).

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

Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

Блок-схема – описание структуры алгоритма с помощью геомет­рических фигур с линиями-связями, показывающими порядок вы­полнения отдельных инструкций. Этот способ имеет ряд преиму­ществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных ко­манд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями сово­купность фигур.

Рассмотрим некоторые основные конструкции, использующие­ся для построения блок-схем.

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

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

Программа – описание структуры алгоритма на языке алгорит­мического программирования.