Файл: Дискрет-ная мат-ка_УМП.pdf

86

На четвертом (заключительном) этапе получаем только од-

ну  простую  цепь.  Она  проходит  через  все  вершины  данного 
ориентированного графа: 

1 – 2 – 3 – 4 – 5. 

Таким  образом,  всего  в  ориентированном  графе,  изобра-

женном  на  рис. 15, содержится 7 простых  цепей,  ведущих  от 
вершины 1 к вершине 5. Среди них одна цепь состоит из одной 
дуги, две цепи состоят из двух дуг, три — из трех, и одна цепь 
содержит четыре дуги. 

Завершим  подраздел  следующим  замечанием.  Если  в  не-

ориентированном графе при поиске всех простых цепей, соеди-
няющих  вершину  a  с  вершиной  b,  начальной  можно  считать 
любую  из  них,  то  в  случае  ориентированного  графа  такой  сво-
боды нет. Например, из рис. 15 видно, что не существует ни од-
ной простой цепи, ведущей от вершины 5 к вершине 1, но суще-
ствует 7 вершин, которые ведут от первой вершины к пятой. 

 
3.5 Оформление решения задачи 
 
В выполненной контрольной работе решение задачи на те-

му  «Нахождение  простых  цепей  в  графе»  должно  быть  пред-
ставлено тремя пунктами со следующими сведениями. 

Поиск простых цепей: 
а) полное условие задачи, как оно сформулировано в зада-

нии; 

б) рисунок графа; 
в) перечни всех простых цепей по каждому этапу; 
г) общее число найденных простых цепей. 
Поиск простых циклов: 
а) полное условие задачи; 
б) перечни всех простых цепей по каждому этапу; 
в) общее число найденных простых цепей. 
Поиск простых цепей в орграфе: 
а) полное условие задачи, как оно сформулировано в задании; 
б) рисунок ориентированного графа; 
в) перечни всех простых цепей по каждому этапу; 
г) общее число найденных простых цепей. 

87

óÄëíú 6

ùãÖåÖçíõ íÖéêàà ÄãÉéêàíåéÇ 

1 àÌÚÛËÚË‚ÌÓ ÔÓÌflÚË ‡Î„ÓðËÚχ 

1.1 Определения понятия алгоритма 
 
Понятие  алгоритма  является  и  очень  простым,  и  одновре-

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

В  повседневной  практике  обычно  вполне  достаточно  ин-

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

 
1.2 Алгоритм нахождения наибольшего общего делителя 
 
Одна из наиболее ранних разработок в области построения 

алгоритмов относится к задаче нахождения наибольшего общего 
делителя  двух  заданных  положительных  целых  чисел.  Напри-
мер, числа 16 и 12 делятся на 1, на 2 и на 4. Из этих делителей 

88

число 4 является  наибольшим.  Следовательно,  число 4 и  есть 
наибольший общий делитель чисел 16 и 12. 

Алгоритм нахождения наибольшего общего делителя, авто-

ром  которого  считают  древнегреческого (III век  до  новой  эры) 
математика Евклида, состоит в следующем. 

Обозначим буквами a и b два целых положительных числа. 

Пусть a 

≥ b. Тогда: 

1) число a делим на число b. Получится остаток c. Если ос-

таток равен нулю, то число b есть искомый результат, и на этом 
работа алгоритма заканчивается. Если же c 

≠ 0, то переходим ко 

второму этапу; 

2) число b делим на число c. Получится остаток d. Если d = 

0, то работа алгоритма заканчивается, и искомым является число 
c. Если же d 

≠ 0, то переходим к третьему этапу; 

3) число c делим на число d. Получится остаток e. Если e = 

0, то искомым является число d, и т.д. 

Очевидно, что при любых a и b после конечного числа ша-

гов наибольший общий делитель будет найден. 

 
1.3 Пример логической задачи 
 
Пусть даны два сосуда a и b. В сосуд a входит точно пять 

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

Один  из  алгоритмов  решения  этой  задачи  состоит  в  сле-

дующей последовательности действий: 

1)  полагаем,  что  в  исходном  состоянии  сосуды  пусты.  На-

ливаем  в  сосуд  a  пять  литров.  Состояния  сосудов: 5-0 (эта  за-
пись  обозначает:  в  сосуде  a  содержится  пять литров,  а  сосуд  b 
пуст); 

2)  из  сосуда  a  переливаем  в  сосуд  b  три  литра.  Состояния 

сосудов: 2-3, т.е. в сосуде a осталось два литра, а в сосуде b на-
ходится три литра; 

3) из сосуда b выливаем воду. Состояния сосудов: 2-0; 
4) из сосуда a переливаем воду в сосуд b. Состояния: 0-2; 

89

5) наполняем сосуд a. Состояния: 5-2; 
6) в сосуд b доливаем воду из сосуда a. В сосуде a останется 

4 литра. Алгоритмический процесс на этом заканчивается. 

 
1.4 Общие свойства алгоритмов 
 
Любые  алгоритмы,  независимо  от  того,  понимаются  они  в 

интуитивном  смысле  или  математически  точном,  характеризу-
ются следующими свойствами: 

1)  наличие  исходных  данных.  Всякий  алгоритмический 

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

2)  дискретность  алгоритма.  Это  значит,  что  всякий  алго-

ритм состоит из последовательности строго различимых дейст-
вий (шагов);  

3)  детерминированность  алгоритма.  Детерминизм — (лат. 

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

4) определенность алгоритма. Все указания, определяющие 

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

5)  результативность  алгоритма.  Суть  этого  свойства  в  том, 

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

90

какого  интереса  не  представляют,  ни  практического,  ни  теоре-
тического; 

6)  массовость  алгоритма.  Под  этим  понимается  возмож-

ность  применения  алгоритма  ко  многим  исходным  данным.  В 
предыдущих подразделах показано, что в одних случаях множе-
ство исходных данных может быть бесконечным, как в алгорит-
ме Евклида, в других же случаях определение множества исход-
ных данных связано с определенными трудностями. Например, 
в  задаче  о  сосудах  кажется,  что  приведенный  алгоритм  приме-
ним только к одному варианту исходных данных. На самом же 
деле  исходные  данные  могут  быть  и  другими.  Например,  один 
сосуд  может  быть 10-литровым,  а  другой — шестилитровым. 
Если требуется отмерить 8 литров, то можно действовать по то-
му же алгоритму, что и в случае 5-литрового и 3-литрового со-
судов.  Разумеется,  существуют  задачи,  когда  можно  считать, 
что  множество  исходных  данных  есть  синглетон.  В  качестве 
примера приведем следующую задачу.  

«Дано 6 спичек. Требуется построить из них четыре равно-

сторонних треугольника. Длина стороны каждого треугольника 
равна  длине  спички.  Ломать  (а  также  расщеплять)  спички  не 
разрешается». 

Алгоритм решения этой задачи состоит в выполнении сле-

дующих  действий.  Сначала  строится  треугольник  на  плоскости, 
на  что  потребуется  три  спички.  Затем  в  каждую  вершину  тре-
угольника ставится по одной из оставшихся трёх спичек, а другие 
их  концы  соединяются  вместе.  Получится  объёмная  фигура — 
тетраэдр,  у  которого  каждая  грань  является  правильным  тре-
угольником.  Всего  у  тетраэдра  четыре  грани,  следовательно, 
задача  решена:  шестью  спичками  построено  четыре  равносто-
ронних треугольника. 

Если  считать,  что  длина  спичек  не  имеет  значения,  то  для 

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