ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6582
Скачиваний: 50
36
Для ориентированного графа
G,
имеющего
N
вершин можно рассмотреть матрицу
дости-
жимости
C(G)
размера
N
х
N,
элементы которой определяются так: С(
I
,
J)
= 1, если вершина
vj
достижима из
vi; C(I, J)
= 0 в противном случае. Ниже приведен пример ориентированного графа и
его матрицы достижимости, рис. 1.10.
Рис. 1.10.
Матрица достижимости ориентированного графа
Контрольные вопросы
1. Каким образом определяется граф?
2. Что является путем в графе?
3. Как определяется такой вид графа, как дерево?
4. Какими способами можно задать граф?
§ 6. АЛГОРИТМ И ЕГО СВОЙСТВА
6.1. РАЗЛИЧНЫЕ ПОДХОДЫ К ПОНЯТИЮ «АЛГОРИТМ»
Понятие алгоритма - одно из фундаментальных понятий информатики. Алгоритмизация
наряду с моделированием выступает в качестве общего метода информатики. К реализации опре-
деленных алгоритмов сводятся процессы управления в различных системах, что делает понятие
алгоритма близким и кибернетике.
Алгоритмы являются объектом систематического исследования пограничной между мате-
матикой и информатикой научной дисциплины, примыкающей к математической логике -
теории
алгоритмов.
Особенность положения состоит в том, что при решении практических задач, предпола-
гающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на прак-
тике информационных технологий, можно, как правило, не опираться на высокую формализацию
данного понятия. Поэтому представляется целесообразным познакомиться с алгоритмами и алго-
ритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения
основных его свойств. При таком подходе алгоритмизация более выступает как набор определен-
ных практических приемов, особых специфических навыков рационального мышления в рамках
заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмот-
ренным выше подходом к измерению информации: тонкие математические построения при «ки-
бернетическом» подходе не очень нужны при использовании гораздо более простого «объемного»
подхода при практической работе с компьютером.
Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени ве-
ликого математика IX века аль-Хорезми, который сформулировал правила выполнения арифмети-
ческих действий. Первоначально под алгоритмами и понимали только правила выполнения четы-
рех арифметических действий над многозначными числами.
6.2. ПОНЯТИЕ ИСПОЛНИТЕЛЯ АЛГОРИТМА
Понятие исполнителя невозможно определить с помощью какой-либо формализации. Ис-
полнителем может быть человек, группа людей, робот, станок, компьютер, язык программирова-
ния и т.д. Важнейшим свойством, характеризующим любого из этих исполнителей, является то,
что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выпол-
нять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык про-
граммирования Бейсик - команды PRINT, END, LIST и другие аналогичные. Вся совокупность ко-
37
манд, которые данный исполнитель умеет выполнять, называется системой команд
исполнителя
(СКИ).
В качестве примера (рис. 1.11) рассмотрим исполнителя-робота, работа которого состоит в
собственном перемещении по рабочему полю (квадрату произвольного размера, разделенному на
клетки) и перемещении объектов, в начальный момент времени находящихся на «складе» (правая
верхняя клетка).
Рис. 1.11.
Исполнитель-робот
Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл
того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель
действует
формально,
т. е. отвлекается от содержания поставленной задачи и только строго вы-
полняет некоторые правила, инструкции.
Это - важная особенность алгоритмов. Наличие алгоритма формализует процесс решения
задачи, исключает рассуждение исполнителя. Использование алгоритма дает возможность решать
задачу формально, механически исполняя команды алгоритма в указанной последовательности.
Целесообразность предусматриваемых алгоритмом действий обеспечивается точным анализом со
стороны того, кто составляет этот алгоритм.
Введение в рассмотрение понятия «исполнитель» позволяет определить алгоритм как по-
нятное и точное предписание исполнителю совершить последовательность действий, направлен-
ных на достижение поставленной цели. В случае исполнителя-робота мы имеем пример алгоритма
«в обстановке», характеризующегося отсутствием каких-либо величин. Наиболее же распростра-
ненными и привычными являются алгоритмы работы с величинами - числовыми, символьными,
логическими и т.д.
6.3. ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ АЛГОРИТМОВ
Алгоритм, составленный для некоторого исполнителя, можно представить различными
способами: с помощью графического или словесного описания, в виде таблицы, последовательно-
стью формул, записанным на алгоритмическом языке (языке программирования). Остановимся на
графическом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ
благодаря наглядности, обеспечивающей, в частности, высокую «читаемость» алгоритма и явное
отображение управления в нем.
Прежде всего определим понятие блок-схемы. Блок-схема - это ориентированный граф,
указывающий порядок исполнения команд алгоритма; вершины такого графа могут быть одного
из трех типов (рис. 1.12).
38
Рис. 1.12.
Три типа вершин графа
На рис. 1.12 изображены «функциональная» (
a
) вершина (имеющая один вход и один вы-
ход); «предикатная»
(б)
вершина, имеющая один вход и два выхода (в этом случае функция
Р
пе-
редает управление по одной из ветвей в зависимости от значения
Р (Т,
т.е. true, означает «истина»,
F,
т.е. false - «ложь»); «объединяющая» (в) вершина (вершина «слияния»), обеспечивающая пере-
дачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +),
вместо
F-
«нет» (либо знак -).
Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 1.13),
имеющих особое значение для практики алгоритмизации.
Рис. 1.13.
Основные алгоритмические структуры
На рис. 1.13 изображены следующие блок-схемы:
а -
композиция,
или следование;
б -
аль-
тернатива,
или
развилка,
в
и
г -
блок-схемы, каждую из которых называют
итерацией,
или
цик-
лом
(с предусловием (
в
), с постусловием (
г
)).
S1
и
S2
представляют собой в общем случае некото-
рые серии команд для соответствующего исполнителя,
В -
это условие, в зависимости от истинно-
сти
(Т)
или ложности
(F)
которого управление передаётся по одной из двух ветвей. Можно дока-
зать, что для составления любого алгоритма достаточно представленных выше четырех блок-схем,
если пользоваться их последовательностями и/или суперпозициями.
Блок-схема «альтернатива» может иметь и сокращенную форму, в которой отсутствует
ветвь
S2
(рис. 1.14,
а).
Развитием блок-схемы типа альтернатива является блок-схема «выбор»
(рис. 1.14, б).
39
Рис. 1.14.
Развитие структуры типа «альтернатива»;
о) - неполная развилка;
б) -
структура «выбор»
На практике при составлении блок-схем оказывается удобным использовать и другие гра-
фические знаки (некоторые из них приведены на рис. 1.15).
Рис. 1.15.
Некоторые дополнительные конструкции для изображения блок-схем алгоритмов
6.4. СВОЙСТВА АЛГОРИТМОВ
Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого
он создан, мог однозначно и точно следовать командам алгоритма и эффективно получать опреде-
ленный результат. Это накладывает на записи алгоритмов ряд обязательных требований, суть ко-
торых вытекает, вообще говоря, из приведенного выше неформального толкования понятия алго-
ритма. Сформулируем эти требования в виде перечня свойств, которым должны удовлетворять
алгоритмы, адресуемые заданному исполнителю.
1. Одно из первых требований, которое предъявляется к алгоритму, состоит в том, что опи-
сываемый процесс должен быть разбит на последовательность отдельных шагов. Возникающая в
результате такого разбиения запись представляет собой упорядоченную совокупность четко раз-
деленных друг от друга предписаний (директив, команд, операторов), образующих прерывную
(или, как говорят, дискретную) структуру алгоритма. Только выполнив требования одного пред-
писания, можно приступить к выполнению следующего. Дискретная структура алгоритмической
записи может. Например, подчеркиваться сквозной нумерацией отдельных команд алгоритма, хо-
тя это требование не является обязательным. Рассмотренное свойство алгоритмов называют дис-
кретностью.
2. Используемые на практике алгоритмы составляются с ориентацией на определенного ис-
полнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель
может понять и исполнить, а какие - не может. Мы знаем, что у каждого исполнителя имеется своя
система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно
использовать лишь те команды, которые имеются в его СКИ. Это свойство алгоритмов будем на-
40
зывать понятностью.
3. Будучи понятным, алгоритм не должен содержать предписаний, смысл которых может
восприниматься неоднозначно, т.е. одна и та же команда, будучи понятна разным исполнителям,
после исполнения каждым из них должна давать одинаковый результат.
Запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у
исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных соста-
вителем алгоритма. Говоря иначе, алгоритм не должен оставлять места для произвола исполните-
ля. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной
команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на сле-
дующем шаге.
Отмеченное свойства алгоритмов называют
определенностью
или
детерминированно-
стью.
4. Обязательное требование к алгоритмам -
результативность.
Смысл этого требования со-
стоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратить-
ся за конечное число шагов и при этом должен получиться определенный результат. Вывод о том,
что решения не существует - тоже результат.
5. Наиболее распространены алгоритмы, обеспечивающие решение не одной конкретной
задачи, а некоторого класса задач данного типа. Это свойство алгоритма называют
массовостью.
В простейшем случае массовость обеспечивает возможность использования различных исходных
данных.
6.5. ПОНЯТИЕ АЛГОРИТМИЧЕСКОГО ЯЗЫКА
Достаточно распространенным способом представления алгоритма является его запись на
алгоритмическом
языке,
представляющем в общем случае систему обозначений и правил для
единообразной и точной записи алгоритмов и исполнения их. Отметим, что между понятиями «ал-
горитмический язык» и «языки программирования» есть различие; прежде всего, под исполните-
лем в алгоритмическом языке может подразумеваться не только компьютер, но и устройство для
работы «в обстановке». Программа, записанная на алгоритмическом языке, не обязательно пред-
назначена компьютеру. Практическая же реализация алгоритмического языка -отдельный вопрос в
каждом конкретном случае.
Как и каждый язык, алгоритмический язык имеет свой словарь. Основу этого словаря составляют
слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алго-
ритма. Такие команды называют простыми командами. В алгоритмическом языке используют слова, смысл
и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование
служебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов -
единообразной.
Алгоритм, записанный на алгоритмическом языке, должен иметь название. Название жела-
тельно выбирать так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для
выделения названия алгоритма перед ним записывают служебное слово АЛГ (АЛГоритм). За на-
званием алгоритма (обычно с новой строки) записывают его команды. Для указания начала и кон-
ца алгоритма его команды заключают в пару служебных слов НАЧ (НАЧало) и КОН (КОНец).
Команды записывают последовательно.
Последовательность записи алгоритма:
АЛГ название алгоритма
НАЧ
серия команд алгоритма
КОН
Например, алгоритм, определяющий движение исполнителя-робота, может иметь вид:
АЛГ в_склад
НАЧ
вперед
поворот на 90° направо
вперед