Методичкадля сукхова ви 1 1


ГЛАВА 4. ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ И ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.
4.1 Понятие алгоритма и его свойства
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин.
Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.
Алгоритм формулируется в расчете на конкретного исполнителя, например, человека или особую машину – автомат. Алгоритм является руководством к действию для исполнителя, поэтому значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание».
Можно дать следующее неформальное определение понятие «алгоритм»:
Алгоритм – это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения после конечного числа шагов искомого результата.
Приведенное определение не является определением в строгом математическом смысле этого слова, а лишь описывает понятие алгоритма и отражает его интуитивное понимание. Оно не является формальным, потому что в нем используются такие неуточняемые понятия, как «система предписаний», «действия исполнителя», «объект». Так как любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя, то алгоритм должен быть описан в командах того исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Значение слова «алгоритм» очень схоже по смыслу со значением слов «метод», «способ». Однако любой алгоритм, в отличие от метода или способа, обязательно должен обладать следующими свойствами:
Массовость.
Алгоритм имеет некоторое число входных величин – аргументов, задаваемых до начала его работы. Цель выполнения алгоритма это получение результатов, имеющих вполне определенное отношение к исходным данным. Можно сказать, что алгоритм указывает последовательность действий по переработке исходных данных в результаты. Для алгоритма можно брать различные наборы входных данных, т.е. можно применять один и тот же алгоритм для решения целого класса однотипных задач, различающихся набором исходных данных. Это свойство алгоритма называют массовостью. Можно считать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда свойство массовости означает применимость алгоритма ко всем объектам данного класса. Множество объектов данного класса называют областью применимости алгоритма.
Понятность.
Понятность алгоритма означает знание исполнителя о том, что надо делать для исполнения этого алгоритма. Таким образом, при формулировке алгоритма необходимо учитывать возможности и особенности исполнителя, на которого рассчитан алгоритм. Алгоритм не должен содержать предписания, смысл которых может восприниматься исполнителем неоднозначно, т.е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. Алгоритм всегда рассчитан на механическое выполнение «неразмышляющим» исполнителем.
Дискретность.
Выполнение алгоритма разбивается на последовательность законченных действий – шагов. Только выполнив одно действие, можно приступать к исполнению следующего. Произвести каждое отдельное действия исполнителю предписывает специальное указание в записи алгоритма, называемое командой.
Конечность.
Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут повторяться многократно. Однако исполнение алгоритма все же закончится за пусть очень большое, но конечное число шагов. При этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть и установление того факта, что задача решения не имеет.
В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Так как, например, можно сформулировать процедуру вычисления числа π. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же прервать ее искусственно, например, введением условия вида: «Закончить вычисление после получения n десятичных знаков числа π», то эта вычислительная процедура приобретет свойство конечности. На этом принципе основано получение многих вычислительных алгоритмов. Строится бесконечный, сходящийся к искомому решению, процесс. Он обрывается на некотором шаге при выполнении определенного условия, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближенного решения зависит от числа выполненных шагов.
Определенность.
Способ решения задачи однозначно определен в виде последовательности шагов, т.е. если алгоритм многократно применяется к одному и тому же набору исходных данных, то каждый раз получаются одни и те же промежуточные результаты и один и тот же выходной результат. Это также означает, что если один и тот же алгоритм поручить для исполнения разным исполнителям, но при одинаковых исходных данных, то они придут к одному и тому же результату.
Эффективность.
Каждый шаг алгоритма должен быть выполнен точно и за конечное время. В этом смысле говорят, что алгоритм должен быть эффективным, т.е. действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Поэтому, например, указание вида: «Если любое целое число, большее 6, можно представить в виде суммы трех простых чисел, то значение счетчика увеличить на 1, иначе счетчик уменьшить на 1», – неэффективно, так как неизвестен способ доказательства истинности или ложности утверждения, содержащегося в нем. Следовательно, исполнитель не может выполнить этот шаг алгоритма, пока не будет найдено соответствующее доказательство.
Таким образом, эффективность алгоритма связана с возможностью выполнения каждой команды за конечное время. Кроме того, эффективность означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время (обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее). Поэтому при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.
Приведем примеры двух алгоритмов из области математики, которые обладают всеми указанными выше свойствами.
Пример 1. Рассмотрим алгоритм нахождения всех простых чисел в интервале от 1 до некоторого заданного N.
Этот алгоритм носит название «Решето Эратофена», по имени древнегреческого ученого, впервые предложившего данный алгоритм.
Выпишем подряд все натуральные числа от 1 до N.
Возьмем первое число, большее 1 (это будет число 2), и зачеркнем каждое второе число, начиная отсчет со следующего за двойкой числа.
Возьмем первое оставшееся незачеркнутым число в данной числовой последовательности(при первом выполнении пункта 3 это будет число 3) и зачеркнем каждое третье число, начиная отсчет с числа следующего за этим числом (при первом выполнении пункта 3 это будет число 4), при этом ранее зачеркнутые числа участвуют в счете.
Если это незачеркнутое число окажется больше N, то выполнение алгоритма закончено, иначе перейти к выполнению пункта 3.
В результате применения этого алгоритма в анной числовой последовательности от 1 до N незачеркнутыми останутся все простые числа.
Пример 2. Дано положительное действительное число Р. Требуется вычислить его квадратный корень с заданной точностью, например, с m знаками после запятой.
Алгоритм вычисления квадратного корня можно записать в следующем виде:
Запись числа Р разделить на группы Рi по 2 цифры влево и вправо от запятой . Заметим при этом, что самая левая и самая правая группы Р1 и Рn могут состоять из одной цифры. Группу Рn в этом случае дополнить до двух цифр, приписав 0 справа.
Подобрать такую цифру х, квадрат которой не превосходит Р1. Записать х в качестве первой цифры результата.
Вычислить .
Если нерассмотренных групп в числе Р больше нет и r=0 (т.е. корень вычислен точно) или если r≠0, но точность вычисления достигнута(т.е. у искомого числа получено m знаков после запятой), то выполнение алгоритма закончено.
Если нерассмотренные группы есть, или точность вычисления не достигнута, то к r дописать справа цифры очередной Рi группы; получившееся число обозначить через b. При этом возможны следующие варианты:
если очередная группа Рi стоит в записи числа первой после запятой, то дописать справа от х десятичную запятую;
если все группы в записи числа уже обработаны, то в качестве очередной группы Рi взять 00, при этом если число Р было целым, то дописать справа от х десятичную запятую.
Подобрать такую максимальную цифру у, что , где – целое число, совпадающее по записи с х без учета десятичной запятой. Тогда у будет очередной цифрой искомого числа.
Вычислить .
Приписать у справа к результату. Получившееся число обозначить через х.
Перейти к пункту 4.
На примере этого алгоритма можно проиллюстрировать его свойства. Массовость этого алгоритма заключается в том, что его можно применить к любому положительному рациональному числу. Понятность алгоритма обеспечивается тем, что, во-первых, исполнителю известно, с чего начинать выполнение алгоритма (с пункта 1), и, во-вторых, четко описано, какие из допустимых действий исполнителя надо выполнять на каждом шаге. Дискретность выражается в том, что данный процесс разбит на отдельные пункты (шаги). Конечность этого алгоритма состоит в том, что если автоматически выполнять его пункт за пунктом, то он обязательно закончится за пусть большое, но всегда конечное число шагов. Определенность алгоритма вытекает из того, что каждый его пункт выполняется исполнителем однозначно, и каждый пункт снабжен указанием, какую команду выполнять следующей. Эффективность алгоритма указывает на то, что каждый его пункт исполнитель может выполнить точно и за конечное время.
Дадим более уточненное понятие алгоритма, которое также не является определением в математическом смысле слова, но более точно и формально описывает это понятие, раскрывая его суть.
Алгоритм – это конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами массовости, понятности, дискретности, конечности, определенности и эффективности.
Формы записи алгоритмов
Существую различные способы для описания одного и того же алгоритма. На практике наиболее распространены следующие формы представления алгоритма:
Словесная или текстовая форма записи (примеры 1 и 2).
Графическая (запись в виде блок-схем).
Псевдокоды (например, запись алгоритмов на алгоритмическом языке в русской нотации).
Программная (запись алгоритма на каком-либо алгоритмическом языке высокого уровня).
Текстовая форма записи представляет собой описание последовательных этапов обработки данных и задается в произвольном изложении на естественном языке. Эта форма записи алгоритмов не имеет широкого распространения из-за своих недостатков:
а) такие описания строго не формализуемы;
б) эти описания страдают многословностью записей;
в) они часто допускают неоднозначность толкования отдельных
предписаний.
Графическая форма записи алгоритма является более компактной и наглядной по сравнению с текстовой. Алгоритм в этом случае изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий (операторов). Такое графическое представление называется блок-схемой алгоритма. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условия, управлению повторением действий, окончанию обработки данных и т.д.) соответствует геометрическая фигура блока, представленная в виде блочного символа. Блочные символы при этом соединяются линиями переходов с указанием в виде стрелок направления движения, и тем самым определяющими очередность выполнения действий. Существуют следующие стандартные блоки, с помощью которых можно построить любой алгоритм и подробно изобразить его в виде блок-схемы:
Блоки начала и конца записи алгоритма.
55562527305 начало
00 начало

114490519494500
962660-317500363855227330конец
00конец

Блок «начало» имеет один выход.
Блок «конец» имеет один вход.
Эти блоки являются указателями соответственно начала и конца записи алгоритма.
Блок ввода данных.
2320290274955 a, b, с
00 a, b, с
10972803111500
109728019367500
Имеет один вход и один выход. Внутри блока перечислены те переменные, которые в результате выполнения этого блока получили некоторые исходные значения, причем эти значения могут быть введены как с клавиатуры компьютера, так и из некоторого файла или с других внешних устройств ввода. После выполнения этого блока переменные (a, b, c), перечисленные в этом списке, будут иметь вполне конкретные значения.
Блок ввода данных.
10972803111500
61722041910x, y
x, y

109728019367500
Имеет один вход и один выход. Внутри блока перечислены те переменные, значения которых в результате выполнения этого блока будут выведены на экран монитора, в файл или любое другое внешнее устройство вывода.
Блок вычислений.
10972803111500
47434539371
00

110680519367500
Имеет один вход и один выход. Действие блока заключается в том, что вычисляется значение выражения, стоящего справа от знака «=», и это значение присваивается переменной, стоящей слева от знака «=». Здесь следует сделать два важных замечания:
а) Для того, чтобы можно было однозначно вычислить значения выражения, стоящего справа, все переменные (a, b, c), которые присутствуют в этом выражении к этому моменту, должны иметь вполне конкретные числовые значения, т.е. либо введены с помощью блока ввода, либо вычислены через другие переменные. В частности, это выражение может состоять только из имени одной переменной или одной константы.
б) Слева от знака «=» может стоять только одно имя некоторой переменной, но не может быть константы или арифметического выражения. Это связано с тем, что знак «=» в блок-схемах понимается в смысле знака присваивания, а не в привычном для нас смысле знака математического равенства. Если математическая запись a=b эквивалентна записи b=a, что означает «левая часть a равна правой части b», или, что то же самое «левая часть b равна правой части a», то в блоке вычислений запись a=b означает, что значение переменной b присваивается переменной a. При этом старое значение переменной a пропадает. Запись b=a означает, что, наоборот, значение переменной a присваивается переменной b. В первом случае, в результате выполнения такого блока, переменные a и b будут иметь одно и то же значение, а именно то, которое до этого имела переменная b. Во втором случае переменные a и b также будут иметь одно и то же значение, но только то, которое до этого имела переменная a. Так, в вычислительном блоке часто можно встретить запись вида k=k+1, что означает увеличение значения переменной k (счетчик) на 1. Тогда как в математике запись k=k+1 просто неверна, т.к. эквивалентна 0=1. Чтобы подчеркнуть это различие, в некоторых книгах в блоке вычислений в качестве знака присваивания используется знак «:=».
302514020574000Логический блок (блок проверки условия)
729616207645Логическое выражение
00Логическое выражение

2653665188595да
00да

265366520764500
1329690140970нет
00нет
169545019939000
Блок имеет один вход и два выхода, помеченных словами «да» и «нет» (иногда «+» и «–» или «1» и «0»). Действие блока таково, что если вычисленное значение логического выражения равно «истине» (true), то выход осуществляется по ветке «да», если значение логического выражения равно «ложь» (false), то выход осуществляется по ветке «нет».
Блок организации цикла.
2059940281305i=in, ik, ih
00i=in, ik, ih
1756410463550023444203606800X= X1, … Xn,,h
00X= X1, … Xn,,h

464300529930046701450800003093720425450027317704254500
173799534290001899920111760тело
цикла
00тело
цикла

1809110225040309372064088004648202522800174498063905
17437102222500
465455273050010966452730500175260014859000174925214859000239337314680000
Блок имеет один вход и один выход. Этот блок реализует один из возможных видов цикла, а именно «цикл с заранее известным числом повторений». При этом переменная i называется переменной цикла, а in, ik, ih – параметры цикла, где in – начальное значение переменной цикла, ik – конечное значение переменной цикла, ih – шаг по переменной цикла.
Тело цикла представляет собой некоторую последовательность действий, которая повторяется многократно. Действие этого блока заключается в том, что сначала переменная i принимает значение in, и при этом значении выполняется тело цикла. Затем i принимает значение in+ ih, и вновь выполняется тело цикла, и так далее, пока i не примет значение ik. С этим значением i последний раз выполнится тело цикла и произойдет выход из цикла. При этом закон изменения переменной i полностью задан его параметрами, т.е. не может быть изменен внутри тела цикла.
Блок подпрограммы.
91630531115002101215251460 Подпрограмма
Имя(параметры)
00 Подпрограмма
Имя(параметры)

9163052159000
Блок имеет один вход и один выход. Этот блок представляет собой некий вспомогательный алгоритм, который может быть расписан более подробно отдельно от основного алгоритма. В нужный момент из основного алгоритма эта программа может быть вызвана по ее имени. При этом должна быть задана часть параметров, которые называются входными параметрами этой программы. Другая часть параметров, которая получила название выходных параметров, будут вычислены в результате работы программы. После того, как подпрограмма закончит свою работу, эти значения выходных параметров будут переданы в то место основного алгоритма, откуда эта подпрограмма была вызвана.
Здесь реализуется идея одной из наиболее широко применяемых технологий программирования, которая получила название «Структурное программирование». Структурный подход базируется на двух основополагающих принципах:
Использование процедурного стиля программирования.
Последовательная детализация алгоритма решения задачи сверху вниз.
Дело в том, что процесс решения сложной задачи довольно часто сводится к решению нескольких более простых подзадач. Соответственно, процесс разработки сложного алгоритма может разбиваться на этапы составления отдельных алгоритмов, которые называются вспомогательными. Каждый такой вспомогательный алгоритм описывает решение какой-либо подзадачи.
Процесс построения алгоритма методом последовательной детализации состоит в следующем. Сначала алгоритм формулируется в «крупных» блоках (командах), которые могут быть непонятны исполнителю (не входят в систему его команд) и записываются как вызовы вспомогательных алгоритмов. Затем происходит детализация, и все вспомогательные алгоритмы подробно расписываются с использованием команд, уже понятных исполнителю.
Запись алгоритма с помощью псевдокода занимает промежуточное место между записью алгоритма на естественном языке и его записью на формальном языке программирования высокого уровня. Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. С одной стороны он близок к обычному естественному языку, поэтому алгоритмы на нем могут записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам программирования высокого уровня, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде так же, как и в формальных языках, есть служебные слова, смысл которых определен заранее. Единого псевдокода нет, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных базовых конструкций. В качестве примера можно привести псевдокоды, которые использовались для записи различных алгоритмов в учебнике по информатике авторов А.Г. Кушниренко и другие, а также авторов А.П. Ершов и другие.
Программная форма записи алгоритма представляет собой запись алгоритма на каком-нибудь языке программирования высокого уровня. В данном учебном пособии будут представлены записи некоторых алгоритмов на языке программирования Pascal.

Приложенные файлы


Добавить комментарий