И технологии программировании

6.1. Понятие алгоритма и его сВойстВа

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

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

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

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

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

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

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

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

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

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

мально (не думая) поочередно исполняет предложенные команды и получает необходимый результат.

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

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

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

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

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

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

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

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

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

Блок, характеризующий нача­ло/конец алгоритма (для под­программ — вызов/возврат):

Блок — процесс, предназначен­ный для описания отдельных дей­ствий:

с

Начало

<Действие>

Г

Блок — предопределенный про­цесс, предназначенный для обраще­ния к вспомогательным алгоритмам (подпрограммам):

Блок - ввода/вывода с неопре­деленного носителя:

Блок — ввод с клавиатуры:

Блок — вывод на монитор:

Блок — вывод на печатающее устройство:

Блок — решение (проверка усло­вия или условный блок):

Блок, описывающий цикл с па­раметром:

Т

<тело цикла>

Блок — границы цикла, описыва­ющий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»:

<тело цикла>

Соединительные блоки

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

Программа — описание структуры алгоритма на языке алгорит­мического программирования. С другой стороны, понятие «програм­ма» нельзя трактовать только таким образом, как уже говорилось в главе 5 (п. 5.5.2), программа на языке декларативного программиро­вания представляет собой совокупность описанных знаний и не со­держит явного алгоритма исполнения.

6.3, ОсноВные алгоритмические конструкиии

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

6,3,1, Линейная алгоритмическая конструкиия

Линейной называют алгоритмичес­кую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого /-го действия (шага) выполняется (/+1)-е действие (шаг), если /-е дей­ствие — не конец алгоритма.

Поиск по сайту: