eng
Содержание
Указатель обозначений.........6
Предисловие.......................9
Глава 1.
Введение...........................11
1.1.
Моделирование.............11
1.2.
Псевдокод.....................14
Набор упражнений 1..............19
Краткое содержание главы......21
Глава 2.
Логика и доказательство.........23
2.1.
Высказывания и логика.....23
2.2.
Предикаты и кванторы.......27
2.3.
Методы доказательств........30
2.4.
Математическая индукция....32
Набор упражнений 2..................35
Краткое содержание главы.........38
Приложение: Корректность алгоритмов....39
Глава 3.
Теория множеств.........................44
3.1.
Множества и операции над ними........44
3.2.
Алгебра множеств............................51
3.3.
Дальнейшие свойства множеств..........53
Набор упражнений 3................................58
Краткое содержание главы........................61
Приложение: Система с базой знаний..........63
Глава 4.
Отношения............................................68
4.1.
Бинарные отношения..........................68
4.2.
Свойства отношений
4.3.
Отношения эквивалентности и частичного порядка....77
Набор упражнений 4...................................82
Краткое содержание главы...........................85
Приложение: Системы управления базами данных...........86
Глава 5.
5.
Функции...............................................................91
5.1.
Обратные отношения и композиция отношений..........91
5.2.
Функции...............................................................96
5.3.
Обратные функции и композиция функций................102
5.4.
Принцип Дирихле...................................................105
Набор упражнений 5......................................................108
Краткое содержание главы..............................................112
Приложение: Языки функционального программирования.....113
Глава 6
Комбинаторика................................................................117
6.1.
Правила суммы и произведения....................................117
6.2.
Формулы для вычислений.............................................120
6.3.
Бином Ньютона...........................................................128
Набор упражнений 6..........................................................131
Краткое содержание главы..............................................135
Приложение. Эффективность алгоритмов............................136
Глава 7.
Графы........................................................................141
7.1.
Графы и терминология.............................................142
7.2.
Гамильтоновы графы.............................................147
7.3.
Деревья..................................................................152
Набор упражнений 7....................................................158
Краткое содержание главы.............................................163
Приложение. Сортировка и поиск...................................165
Глава 8.
8.1.
Ориентированные графы.....................................................171
8.2.
Пути в орграфах..............................................................175
8.3.
Кратчайший путь................................................................181
Набор упражнений 8..................................................................184
Краткое содержание главы.........................................................187
Приложение: Коммуникационные сети...........................................189
Глава 9
9.1.
Булева алгебра..............................................................194
9.2.
Карта Карно..................................................................200
9.3.
Функциональные схемы.............................................205
Набор упражнений 9........................................................208
Краткое содержание главы................................................211
Приложение. Проектирование 2-битного сумматора.................212
Решения упражнений...........................................................217
Дополнение к первому изданию............................................275
Д.1. генератор случайных графов...........................................275
Д.1.1. Алгоритм построения случайного неориентированного графа...277
Д.1.2. Алгоритм построения случайного ориентированного графа...278
Д.1.3. Алгоритм построения случайного неориентированного
бесконтурногографа....................................................................279
Д.2. Связность в графах...............................................................281
Д.2.1. Алгоритм Уоршелла, вычисляющий матрицу связности............282
Д.2.2. Выделение компонент связности.........................................286
Д.3. Эйлеровы циклы...................................................................288
Д.3.1. Алгоритм построения эйлерова цикла в графе.........................289
Д.3.2. Алгоритм Терри...................................................................292
Д.4. Операции над множествами......................................................294
Д.4.1. Объединение множеств.........................................................300
Дополнение ко второму изданию......................................................305
Предисловие..................................................................................305
Д.5. Дополнительные главы дискретной математики..............................305
Введение........................................................................................305
Д.5.1. Исчисление и оценка конечных сумм..........................................306
Набор упражнений Д.5.1.......................................................................317
Д.5.2. Элементы теории рекурсии.........................................................318
Набор упражнений Д.5.2...................................................................332
Д.5.3. Конечные разности. Разностный и суммирующий операторы..........333
Набор упражнений Д.5.3.....................................................................344
Д.5.4. Производящие функции и комбинаторные подсчеты.......................345
Набор упражнений Д,5.4......................................................................359
Д.6. Общая проблема перебора и некоторые точные методы решения задач целочисленного программирования........................................................359
Введение............................................................................................359
Д.6.1. Понятие m -мерного евклидова целочисленного пространства.......................................................................................361
Д.6.2. Общая постановка, типизация и примеры задач целочисленного программирования..................................................................................362
Д.6.3. NP -полные задачи и проблема перебора...........................................366
Д.6.4. Обзор точных методов решения задач целочисленного программирования..368
Д.6.5. Точное решение задачи одномерной упаковки методом динамического программирования.....................................................................................372
Д.6.6. Метод ветвей и границ и задача коммивояжера....................................381
Набор упражнений Д.6................................................................................392
Литература............................................................................................395
Предметный указатель.............................................................................397
ВВЕДЕНИЕ
Дискретная математика и логика лежат в основе любого современного изу-
чения информатики. Слово "дискретный" означает "составленный из от-
дельных частей", а дискретная математика имеет дело с совокупностями
объектов, называемых множествами, и определенными на них структу-
рами. Элементы этих множеств как правило изолированы друг от друга
и геометрически не связаны. Действительно, большинство интересующих
нас множеств конечны или, по крайней мере, счетны.
Эта область математики привлекается для решения задачи на компью-
тере в терминах аппаратных средств и программного обеспечения с при-
влечением организации символов и манипуляции данными. Современный
цифровой компьютер по существу конечная дискретная система. По-
нимания того, как такая машина работает, можно достигнуть, если пред-
ставить машину как дискретную математическую систему. Поэтому наша
главная цель при изучении дискретной математики приобрести инстру-
менты и технику, необходимые для понимания и проектирования компью-
терных систем. Когда и как использовать эти инструменты и технику основа раздела математики, известного как математическое моделирова-
ние.
В настоящей главе мы бросим взгляд на процесс моделирования и при-
меним стандартный алгоритм к решению практической задачи. Выбран-
ный пример проиллюстрирует не только вид математики, о которой идет
речь в этой книге, но и ее использование при решении насущных задач.
Затем мы разовьем паскалеподобный1 псевдокод в качестве средства вы-
ражения алгоритмов, вводимых далее, для однозначной трактовки их ко-
манд.
1.1. Моделирование
Процесс математического моделирования на диаграмме можно представить
так, как показано на рис. 1.1.
В качестве примера моделирования рассмотрим следующую задачу:
Расстояние (в милях) между шестью шотландскими городами:
Абердин, Эдинбург, Форт Уильям, Глазго, Инвернесс и Перт дано в
табл. 1.1. Требуется найти дорожную сеть минимальной длины,
связывающую все шесть городов.
1Pascal - язык программирования высокого уровня. Прим. перев.
Сама таблица является абстрактной моделью реальной задачи. Однако для
нашего решения мы преобразуем ее в геометрическую модель.
Таблица 1.1
Абердин Эдинбург Форт Уильям Глазго Инвернесс Перт
Абердин 120 147 142 107 81
Эдинбург 120 132 42 157 45
Форт Уильям 147 132 108 66 105
Глазго 142 42 108 168 61
Инвернесс 107 157 66 168 112
Перт 81 45 105 61 112
Мы нарисуем граф, чьи вершины обозначают города, а ребра - дороги
их связывающие. Более подробно о графах рассказано в главе ??. Каж-
дое ребро нашего графа, изображенного на рис. 1.2, снабжено весом, ко-
торый означает расстояние между соответствующими городами согласно
табл. 1.1.
Для решения поставленной задачи с помощью подходящего алгоритма
(последовательности однозначных инструкций, выполнение которых вле-
чет решение за конечное время), мы построим новый граф, имеющий ми-
нимальный общий вес, в котором все шесть городов будут соединены до-
рогами.
Алгоритм Прима
Шаг 1 Выберите произвольную вершину и ребро, соединяющее ее с бли-
жайшим (по весу) соседом.
Шаг 2 Найдите не присоединенную (еще) вершину, ближе всего лежа-
щую к одной из присоединенных, и соедините с ней.
Шаг 3 Повторяйте шаг 2 до тех пор пока все вершины не будут присо-
единены.
1.1. Моделирование 3
112 132
168 108
61 42
66
142
105 157
45
107 147
81 120
Глазго
Форт Уильям
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.2.
На рисунках 1.3, 1.4 и 1.5 изображена последовательность графов, которая
получается в результате применения алгоритма Прима, если начинать с
вершины Перт. Последний граф (с общим весом 339) представляет собой
минимальную сеть дорог, охватывающую все шесть городов.
42 Уильям
45
Глазго Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Уильям
45
Глазго Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.3.
Алгоритм, который мы применяли, написан на обычном русском языке.
Разговорный язык может оказаться слишком многоречивым, неоднознач-
ным и, в следствие этого, не соответствующим запутанной проблеме. Мы
могли бы написать программу для компьютера, реализующую алгоритм,
но какой язык выбрать? Кроме того, язык программирования зачастую
скрывает истинный смысл алгоритма от неопытного читателя! Подходя-
щий компромисс в этой ситуации использовать так называемый псев-
докод, состоящий из небольшого числа структурных языковых элементов
вместе с русско-подобным описанием действий реализуемого алгоритма. О
нем идет речь в следующем параграфе.
105
81 81
42 42 Уильям
45
Глазго
Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Уильям
45
Глазго
Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.4.
66
105
81
42 Уильям
45
Глазго
Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.5.
1.2. Псевдокод
Мы будем использовать псевдокод, основанный на Паскале. Алгоритм в
нем выглядит следующим образом.
begin
операторы исполняемых действий
операторы, управляющие порядком выполнения
end
Строительными блоками алгоритмического языка являются операто-
ры, которые можно разбить на две категории: операторы присваивания и
управляющие операторы.
Оператор присваивания приписывает переменным определенные величи-
ны и имеют такую общую форму:
имя переменной :=выражение
Пример 1.2.1. (Алгоритм сложения двух чисел, First и Second, и при-
своение результата переменной Sum.)
begin
Input First and Second;
Sum:=First + Second;
end
1.2. Псевдокод 5 -Управляющий оператор определяет порядок, в котором должны вы-
полняться шаги алгоритма. Операторы управления бывают трех типов:
• составные операторы;
• условные операторы;
• оператор цикла.
Составные операторы представляют собой список операторов, которые
должны выполняться как отдельная команда в том порядке, в котором они
записаны. Составные операторы имеют следующий вид:
begin
оператор 1;
оператор 2;
.........
оператор n;
end
Пример 1.2.2. (Алгоритм обмена значений двух переменных: One и
Two.)
begin
Input One and Two;
Temp :=One;
One :=Two;
Two :=Temp;
end
Чтобы проследить за работой алгоритма, предположим, что начальные
значения переменных One и Two равны 5 и 7 соответственно, и обратимся
к табл. 1.2.
Таблица 1.2
Temp One Two
Строка 1 5 7
Строка 2 5 5 7
Строка 3 5 7 7
Строка 4 5 7 5
Условные операторы позволяют делать выбор между двумя альтерна-
тивными ситуациями. Они записываются в виде if-then или if-then-else.
На псевдокоде условные операторы изображают так:
begin
if условие then оператор
end
или так:
begin
if условие then оператор 1
else оператор 2
end
Пример 1.2.3. (Алгоритм вычисления модуля числа n и присвоение ре-
зультата переменной abc.)
begin
Input n;
if n < 0 then abc :=−n
else abc :=n;
Output abc;
end
В этом алгоритме оператор, стоящий во второй строке, выполняется при
отрицательных значениях переменной n, а в третьей при положительных
(и нулевом). Можно написать и другой алгоритм, решающий ту же задачу,
но не использующий else:
begin
Input n;
if n < 0 then n :=−n;
abc :=n;
Output abc;
end
Здесь оператор во второй строчке выполняется только при отрицательных
значениях n и игнорируется при любом другом значении. В последнем слу-
чае выполняется оператор, записанный в третьей строке.
Оператор цикла или просто цикл может иметь одну из форм записи:
for X :=A to Z do оператор; (1)
while выражение do оператор; (2)
repeat
оператор 1;
оператор 2;
.............
оператор n;
until условие.
(3)
Здесь X переменная, а A и Z ее начальное и конечное значения.
В случае (1) цикл повторяется определенное число раз. Его разновид-
ность выглядит следующим образом:
for всех элементов множества do оператор
В случае (2) цикл выполняется не определенное число раз, а до тех пор, пока выражение, о котором в нем идет речь, ос
Как только выражение становится ложным, цикл заканчивается.
И наконец, в последней ситуации (3) цикл выполняется до тех пор, пока
конечное условие остается ложным. Единственное различие между (2) и
(3) заключается в том, что в последнем цикл выполнится по крайней мере
один раз, поскольку истинность условия в нем проверяется после каждого
прохода цикла.
1.2. Псевдокод 7
Пример 1.2.4. (Алгоритм вычисления суммы квадратов первых n нату-
ральных чисел.)
begin
sum:=0;
for i :=1 to n do
begin
j :=i ∗ i;
sum:=sum+ j;
end
Output sum;
end
Проследим алгоритм в случае n = 4, записав результаты в табл. 1.3
Таблица 1.3
i j Sum
Перед выполнением цикла 0
Первый проход цикла 1 1 1
Второй проход цикла 2 4 5
Третий проход цикла 3 9 14
Четвертый проход цикла 4 16 30
Выводимый результат: sum = 30.
Пример 1.2.5. (Алгоритм выделения графа с минимальным общим весом,
связывающего все вершины в данном связном взвешенном графе.)
begin
v :=произвольная вершина;
u :=ближайшая соседняя вершина;
связать v и u;
while остаются неприсоединенные вершины do
begin
u :=неприсоединенная вершина, ближайшая
к одной из присоединенных вершин;
соединить u с ближайшей
из присоединенных вершин;
end
end
Это написанная на псевдокоде версия алгоритма Прима, с которым мы
познакомились ранее.
Замечание. Связным называется такой граф, в котором существует
путь (по ребрам) между любыми двумя вершинами (подробнее об этом
см. главу ??, стр. ??).
Превращение алгоритма в работающую программу дело программи-
рования или курса структуры данных, поэтому мы не будем обсуждать
этот процесс в нашей книге. Однако мы познакомимся со множеством
8 Глава 1. Введение
алгоритмов, некоторые из которых представлены в форме псевдокода, а
другие оформлены как математические теоремы. Доказательство истинно-
сти теорем необходимая и далеко нетривиальная часть математического
процесса. Аналогично необходимо проверять корректность написанного на
псевдокоде алгоритма. Например, откуда мы можем знать, что алгоритм
из примера 1.2.5 действительно дает минимальную сеть дорог?
В том случае, когда есть несколько различных алгоритмов, решающих
одну и ту же задачу, возникает вопрос: какой из них является более эффек-
тивным? В упражнении 1.5 приведен еще один алгоритм, суммирующий
квадраты натуральных чисел (как и в примере 1.2.4). Оба работают. Но
какой это делает быстрее, использует при этом меньше памяти? Короче
говоря, какой из этих алгоритмов является наилучшим?
Обе эти проблемы: корректности и эффективности алгоритмов будут об-
суждаться в последующих главах после того, как мы освоим необходимый
для этого аппарат дискретной математики.
Набор упражнений 1
1.1. Граф на рисунке рис. 1.6 изображает сеть дорог, связывающих семь
деревень. Расстояние между деревнями задано в милях. Используя
алгоритм Прима, найдите сеть дорог минимальной общей длины,
охватывающую все деревни.
ris/Fig1-4.eps
Рисунок 1.6.
1.2. Найдите результаты вычислений следующего алгоритма в случаях
(a) n = 3;
(b) n = 5.
begin
f :=1;
Input n;
for i :=1 to n do
f :=f ∗ i;
Набор упражнений 1 9
Output f;
end
Что получится на выходе алгоритма при произвольном натураль-
ном числе n?
1.3. Проследите за изменением значений переменных i и j в следующем
алгоритме при m = 3 и n = 4:
begin
Input m, n;
i :=1;
j :=m;
while i 6= n do
begin
i :=i + 1;
j :=j ∗ m;
end
Output j;
end
Опишите на словах выходные данные этого алгоритма при произ-
вольных целых m и n > 0. Что получится при n = 0?
1.4. Найдите целые числа, получающиеся в результате работы следую-
щего алгоритма:
begin
first :=1;
Output first;
second :=1;
Output second;
next :=first + second;
while next < 100 do
begin
Output next;
first :=second;
second :=next;
next :=first + second;
end
end
Опишите полученную последовательность чисел в терминах ее чле-
нов.
1.5. Проследите эволюцию значений переменных l, sum и k в алгоритме,
приведенном на следующей странице при n = 6.
begin
Input n;
k :=1;
l :=0;
sum:=0;
while k < 2n do
begin
l :=l + k;
sum:=sum+ l;
k :=k + 2;
end
Output sum;
end
Опишите результат работы алгоритма при вводе произвольного на-
турального значения n.
1.6. Проследите работу алгоритма на примере сети дорог, из упр. 1.1.
Какой получился результат?
begin
Упорядочите ребра графа по убыванию веса
и пронумеруйте их числами: 1, 2, 3, . . . и т. д.;
m:=число вершин;
:=число ребер;
:=1;
while > m− 1 do
begin
if удаление ребра с номером не нарушает связности графа then
begin
удалить ребро ;
:= − 1;
end;
:= + 1;
end
end
Краткое содержание главы
Дискретная математика представляет собой математический аппарат и
технику, необходимую для проектирования и понимания вычислительных
систем.
Математическое моделирование это процесс, привлекающий мате-
матику для решения реальных практических задач.
Граф (модель) данной сети дорог между городами состоит из набора вер-
шин, изображающих города, соединенных друг с другом (взвешенными)
ребрами, обозначающими дороги.
Алгоритм это последовательность однозначных команд, выполнение
которых влечет решение поставленной задачи за конечное время.
Алгоритм Прима может быть использован для выделения сети ребер ми-
нимального общего веса, соединяющей все вершины данного взвешенного
графа.
Псевдокодом называется набор структурных элементов языка, подходящий
для выражения алгоритма в однозначных терминах.
Оператор присваивания присваивает переменным определенные значе-
ния.
Управляющий оператор определяет порядок, в котором должны вы-
полняться шаги алгоритма.
Составной оператор представляет собой список инструкций (операто-
ров), которые должны выполняться как отдельная команда в том порядке,
в котором они записаны.
Условный оператор дает возможность сделать выбор между альтерна-
тивными возможностями.
Оператор цикла или просто цикл позволяет выполнить определенный
набор команд подходящее число раз.
Дискретная математика и логика лежат в основе любого современного изу-
чения информатики. Слово "дискретный" означает "составленный из от-
дельных частей", а дискретная математика имеет дело с совокупностями
объектов, называемых множествами, и определенными на них структу-
рами. Элементы этих множеств как правило изолированы друг от друга
и геометрически не связаны. Действительно, большинство интересующих
нас множеств конечны или, по крайней мере, счетны.
Эта область математики привлекается для решения задачи на компью-
тере в терминах аппаратных средств и программного обеспечения с при-
влечением организации символов и манипуляции данными. Современный
цифровой компьютер по существу конечная дискретная система. По-
нимания того, как такая машина работает, можно достигнуть, если пред-
ставить машину как дискретную математическую систему. Поэтому наша
главная цель при изучении дискретной математики приобрести инстру-
менты и технику, необходимые для понимания и проектирования компью-
терных систем. Когда и как использовать эти инструменты и технику основа раздела математики, известного как математическое моделирова-
ние.
В настоящей главе мы бросим взгляд на процесс моделирования и при-
меним стандартный алгоритм к решению практической задачи. Выбран-
ный пример проиллюстрирует не только вид математики, о которой идет
речь в этой книге, но и ее использование при решении насущных задач.
Затем мы разовьем паскалеподобный1 псевдокод в качестве средства вы-
ражения алгоритмов, вводимых далее, для однозначной трактовки их ко-
манд.
1.1. Моделирование
Процесс математического моделирования на диаграмме можно представить
так, как показано на рис. 1.1.
В качестве примера моделирования рассмотрим следующую задачу:
Расстояние (в милях) между шестью шотландскими городами:
Абердин, Эдинбург, Форт Уильям, Глазго, Инвернесс и Перт дано в
табл. 1.1. Требуется найти дорожную сеть минимальной длины,
связывающую все шесть городов.
1Pascal - язык программирования высокого уровня. Прим. перев.
Сама таблица является абстрактной моделью реальной задачи. Однако для
нашего решения мы преобразуем ее в геометрическую модель.
Таблица 1.1
Абердин Эдинбург Форт Уильям Глазго Инвернесс Перт
Абердин 120 147 142 107 81
Эдинбург 120 132 42 157 45
Форт Уильям 147 132 108 66 105
Глазго 142 42 108 168 61
Инвернесс 107 157 66 168 112
Перт 81 45 105 61 112
Мы нарисуем граф, чьи вершины обозначают города, а ребра - дороги
их связывающие. Более подробно о графах рассказано в главе ??. Каж-
дое ребро нашего графа, изображенного на рис. 1.2, снабжено весом, ко-
торый означает расстояние между соответствующими городами согласно
табл. 1.1.
Для решения поставленной задачи с помощью подходящего алгоритма
(последовательности однозначных инструкций, выполнение которых вле-
чет решение за конечное время), мы построим новый граф, имеющий ми-
нимальный общий вес, в котором все шесть городов будут соединены до-
рогами.
Алгоритм Прима
Шаг 1 Выберите произвольную вершину и ребро, соединяющее ее с бли-
жайшим (по весу) соседом.
Шаг 2 Найдите не присоединенную (еще) вершину, ближе всего лежа-
щую к одной из присоединенных, и соедините с ней.
Шаг 3 Повторяйте шаг 2 до тех пор пока все вершины не будут присо-
единены.
1.1. Моделирование 3
112 132
168 108
61 42
66
142
105 157
45
107 147
81 120
Глазго
Форт Уильям
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.2.
На рисунках 1.3, 1.4 и 1.5 изображена последовательность графов, которая
получается в результате применения алгоритма Прима, если начинать с
вершины Перт. Последний граф (с общим весом 339) представляет собой
минимальную сеть дорог, охватывающую все шесть городов.
42 Уильям
45
Глазго Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Уильям
45
Глазго Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.3.
Алгоритм, который мы применяли, написан на обычном русском языке.
Разговорный язык может оказаться слишком многоречивым, неоднознач-
ным и, в следствие этого, не соответствующим запутанной проблеме. Мы
могли бы написать программу для компьютера, реализующую алгоритм,
но какой язык выбрать? Кроме того, язык программирования зачастую
скрывает истинный смысл алгоритма от неопытного читателя! Подходя-
щий компромисс в этой ситуации использовать так называемый псев-
докод, состоящий из небольшого числа структурных языковых элементов
вместе с русско-подобным описанием действий реализуемого алгоритма. О
нем идет речь в следующем параграфе.
105
81 81
42 42 Уильям
45
Глазго
Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Уильям
45
Глазго
Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.4.
66
105
81
42 Уильям
45
Глазго
Форт
Эдинбург
Абердин
Инвернесс
Перт
•
•
•
• •
•
•
Рисунок 1.5.
1.2. Псевдокод
Мы будем использовать псевдокод, основанный на Паскале. Алгоритм в
нем выглядит следующим образом.
begin
операторы исполняемых действий
операторы, управляющие порядком выполнения
end
Строительными блоками алгоритмического языка являются операто-
ры, которые можно разбить на две категории: операторы присваивания и
управляющие операторы.
Оператор присваивания приписывает переменным определенные величи-
ны и имеют такую общую форму:
имя переменной :=выражение
Пример 1.2.1. (Алгоритм сложения двух чисел, First и Second, и при-
своение результата переменной Sum.)
begin
Input First and Second;
Sum:=First + Second;
end
1.2. Псевдокод 5 -Управляющий оператор определяет порядок, в котором должны вы-
полняться шаги алгоритма. Операторы управления бывают трех типов:
• составные операторы;
• условные операторы;
• оператор цикла.
Составные операторы представляют собой список операторов, которые
должны выполняться как отдельная команда в том порядке, в котором они
записаны. Составные операторы имеют следующий вид:
begin
оператор 1;
оператор 2;
.........
оператор n;
end
Пример 1.2.2. (Алгоритм обмена значений двух переменных: One и
Two.)
begin
Input One and Two;
Temp :=One;
One :=Two;
Two :=Temp;
end
Чтобы проследить за работой алгоритма, предположим, что начальные
значения переменных One и Two равны 5 и 7 соответственно, и обратимся
к табл. 1.2.
Таблица 1.2
Temp One Two
Строка 1 5 7
Строка 2 5 5 7
Строка 3 5 7 7
Строка 4 5 7 5
Условные операторы позволяют делать выбор между двумя альтерна-
тивными ситуациями. Они записываются в виде if-then или if-then-else.
На псевдокоде условные операторы изображают так:
begin
if условие then оператор
end
или так:
begin
if условие then оператор 1
else оператор 2
end
Пример 1.2.3. (Алгоритм вычисления модуля числа n и присвоение ре-
зультата переменной abc.)
begin
Input n;
if n < 0 then abc :=−n
else abc :=n;
Output abc;
end
В этом алгоритме оператор, стоящий во второй строке, выполняется при
отрицательных значениях переменной n, а в третьей при положительных
(и нулевом). Можно написать и другой алгоритм, решающий ту же задачу,
но не использующий else:
begin
Input n;
if n < 0 then n :=−n;
abc :=n;
Output abc;
end
Здесь оператор во второй строчке выполняется только при отрицательных
значениях n и игнорируется при любом другом значении. В последнем слу-
чае выполняется оператор, записанный в третьей строке.
Оператор цикла или просто цикл может иметь одну из форм записи:
for X :=A to Z do оператор; (1)
while выражение do оператор; (2)
repeat
оператор 1;
оператор 2;
.............
оператор n;
until условие.
(3)
Здесь X переменная, а A и Z ее начальное и конечное значения.
В случае (1) цикл повторяется определенное число раз. Его разновид-
ность выглядит следующим образом:
for всех элементов множества do оператор
В случае (2) цикл выполняется не определенное число раз, а до тех пор, пока выражение, о котором в нем идет речь, ос
Как только выражение становится ложным, цикл заканчивается.
И наконец, в последней ситуации (3) цикл выполняется до тех пор, пока
конечное условие остается ложным. Единственное различие между (2) и
(3) заключается в том, что в последнем цикл выполнится по крайней мере
один раз, поскольку истинность условия в нем проверяется после каждого
прохода цикла.
1.2. Псевдокод 7
Пример 1.2.4. (Алгоритм вычисления суммы квадратов первых n нату-
ральных чисел.)
begin
sum:=0;
for i :=1 to n do
begin
j :=i ∗ i;
sum:=sum+ j;
end
Output sum;
end
Проследим алгоритм в случае n = 4, записав результаты в табл. 1.3
Таблица 1.3
i j Sum
Перед выполнением цикла 0
Первый проход цикла 1 1 1
Второй проход цикла 2 4 5
Третий проход цикла 3 9 14
Четвертый проход цикла 4 16 30
Выводимый результат: sum = 30.
Пример 1.2.5. (Алгоритм выделения графа с минимальным общим весом,
связывающего все вершины в данном связном взвешенном графе.)
begin
v :=произвольная вершина;
u :=ближайшая соседняя вершина;
связать v и u;
while остаются неприсоединенные вершины do
begin
u :=неприсоединенная вершина, ближайшая
к одной из присоединенных вершин;
соединить u с ближайшей
из присоединенных вершин;
end
end
Это написанная на псевдокоде версия алгоритма Прима, с которым мы
познакомились ранее.
Замечание. Связным называется такой граф, в котором существует
путь (по ребрам) между любыми двумя вершинами (подробнее об этом
см. главу ??, стр. ??).
Превращение алгоритма в работающую программу дело программи-
рования или курса структуры данных, поэтому мы не будем обсуждать
этот процесс в нашей книге. Однако мы познакомимся со множеством
8 Глава 1. Введение
алгоритмов, некоторые из которых представлены в форме псевдокода, а
другие оформлены как математические теоремы. Доказательство истинно-
сти теорем необходимая и далеко нетривиальная часть математического
процесса. Аналогично необходимо проверять корректность написанного на
псевдокоде алгоритма. Например, откуда мы можем знать, что алгоритм
из примера 1.2.5 действительно дает минимальную сеть дорог?
В том случае, когда есть несколько различных алгоритмов, решающих
одну и ту же задачу, возникает вопрос: какой из них является более эффек-
тивным? В упражнении 1.5 приведен еще один алгоритм, суммирующий
квадраты натуральных чисел (как и в примере 1.2.4). Оба работают. Но
какой это делает быстрее, использует при этом меньше памяти? Короче
говоря, какой из этих алгоритмов является наилучшим?
Обе эти проблемы: корректности и эффективности алгоритмов будут об-
суждаться в последующих главах после того, как мы освоим необходимый
для этого аппарат дискретной математики.
Набор упражнений 1
1.1. Граф на рисунке рис. 1.6 изображает сеть дорог, связывающих семь
деревень. Расстояние между деревнями задано в милях. Используя
алгоритм Прима, найдите сеть дорог минимальной общей длины,
охватывающую все деревни.
ris/Fig1-4.eps
Рисунок 1.6.
1.2. Найдите результаты вычислений следующего алгоритма в случаях
(a) n = 3;
(b) n = 5.
begin
f :=1;
Input n;
for i :=1 to n do
f :=f ∗ i;
Набор упражнений 1 9
Output f;
end
Что получится на выходе алгоритма при произвольном натураль-
ном числе n?
1.3. Проследите за изменением значений переменных i и j в следующем
алгоритме при m = 3 и n = 4:
begin
Input m, n;
i :=1;
j :=m;
while i 6= n do
begin
i :=i + 1;
j :=j ∗ m;
end
Output j;
end
Опишите на словах выходные данные этого алгоритма при произ-
вольных целых m и n > 0. Что получится при n = 0?
1.4. Найдите целые числа, получающиеся в результате работы следую-
щего алгоритма:
begin
first :=1;
Output first;
second :=1;
Output second;
next :=first + second;
while next < 100 do
begin
Output next;
first :=second;
second :=next;
next :=first + second;
end
end
Опишите полученную последовательность чисел в терминах ее чле-
нов.
1.5. Проследите эволюцию значений переменных l, sum и k в алгоритме,
приведенном на следующей странице при n = 6.
begin
Input n;
k :=1;
l :=0;
sum:=0;
while k < 2n do
begin
l :=l + k;
sum:=sum+ l;
k :=k + 2;
end
Output sum;
end
Опишите результат работы алгоритма при вводе произвольного на-
турального значения n.
1.6. Проследите работу алгоритма на примере сети дорог, из упр. 1.1.
Какой получился результат?
begin
Упорядочите ребра графа по убыванию веса
и пронумеруйте их числами: 1, 2, 3, . . . и т. д.;
m:=число вершин;
:=число ребер;
:=1;
while > m− 1 do
begin
if удаление ребра с номером не нарушает связности графа then
begin
удалить ребро ;
:= − 1;
end;
:= + 1;
end
end
Краткое содержание главы
Дискретная математика представляет собой математический аппарат и
технику, необходимую для проектирования и понимания вычислительных
систем.
Математическое моделирование это процесс, привлекающий мате-
матику для решения реальных практических задач.
Граф (модель) данной сети дорог между городами состоит из набора вер-
шин, изображающих города, соединенных друг с другом (взвешенными)
ребрами, обозначающими дороги.
Алгоритм это последовательность однозначных команд, выполнение
которых влечет решение поставленной задачи за конечное время.
Алгоритм Прима может быть использован для выделения сети ребер ми-
нимального общего веса, соединяющей все вершины данного взвешенного
графа.
Псевдокодом называется набор структурных элементов языка, подходящий
для выражения алгоритма в однозначных терминах.
Оператор присваивания присваивает переменным определенные значе-
ния.
Управляющий оператор определяет порядок, в котором должны вы-
полняться шаги алгоритма.
Составной оператор представляет собой список инструкций (операто-
ров), которые должны выполняться как отдельная команда в том порядке,
в котором они записаны.
Условный оператор дает возможность сделать выбор между альтерна-
тивными возможностями.
Оператор цикла или просто цикл позволяет выполнить определенный
набор команд подходящее число раз.