| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

View
 

Глава 7

This version was saved 17 years, 3 months ago View current version     Page history
Saved by PBworks
on December 13, 2006 at 3:10:43 am
 

ЭРГОНОМИЧНЫЕ АЛГОРИТМЫ

 На ошибках мы горим! —

Мне сказал Алеха.

Непонятный алгоритм —

Это очень плохо.

Мы ошибки победим!

Надо сделать вот чего —

Надо сделать алгоритм

Ясным и доходчивым

Юрий Примашев

ВИЗУАЛЬНАЯ ПРОВЕРКА АЛГОРИТМОВ

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

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

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

ЧТО ТАКОЕ ЭРГОНОМИЧНЫЙ АЛГОРИТМ?

В связи с этим полезно ввести понятие эргономичный алгоритм, т. е. алгоритм, удовлетворяющий критерию сверхвысокой понимаемости. Преимущество эргономичных алгоритмов в том, что они намного понятнее, яснее, нагляднее и доходчивее, чем обычные. Если алгоритм непонятный, в нем трудно или даже невозможно заметить затаившуюся ошибку. И наоборот, чем понятнее алгоритм, тем легче найти дефект. Поэтому более понятный, эргономичный алгоритм намного лучше обычного. Лучше в том смысле, что он облегчает выявление ошибок, а это очень важно. Ведь чем больше ошибок удастся обнаружить при визуальной проверке, тем больше вероятность, что вновь созданный алгоритм окажется правильным, безошибочным, надежным. Кроме того, эргономичные алгоритмы удобнее для изучения, их проще объяснить другому человеку.

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

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

ЧЕМ ОТЛИЧАЕТСЯ ИКОНА “ВОПРОС” ОТ РАЗВИЛКИ?

На рис. 1 (позиция И4) изображена икона “вопрос”. Она называется так, потому что внутри нее пишут “да-нетный” вопрос, т. е. вопрос, на который можно ответить либо “да”, либо “нет”. Все другие ответы запрещены. Вот примеры да-нетных вопросов: утюг сломался? Тетя приехала? Вася купил хлеб? Преступника арестовали? Эта лужа больше, чем та? Температура выше нуля?

Икона “вопрос” имеет один вход сверху и два выхода: вниз и вправо. Выход влево запрещен и никогда не используется.

На рис. 2 (позиция 2) показана макроикона “развилка”. Она содержит икону “вопрос”, точку слияния и два плеча: левое и правое (рис. 14б). Левое плечо есть путь от нижнего выхода иконы-вопроса до точки слияния. Правое плечо начинается у правого выхода иконы-вопроса и заканчивается в точке слияния (рис. 15). Таким образом, плечо имеет в своем составе надпись “да” или “нет”, соединительные линии, точку слияния, а также иконы. Одно из двух плеч может быть пустым (не содержать икон).

Развилки бывают простые и сложные. Простая развилка содержит только одну икону-вопрос. Примеры простых развилок показаны на рис. 16. Развилка называется сложной, если в ее плечах имеется по крайней мере одна простая развилка. На рис. 10а показаны три сложные развилки. Например, развилка “Борщ очень вкусный?” сложная, так как ее левое плечо содержит простую развилку “Борщ сильно пересолен?”. Другие примеры сложных развилок показаны на рис. 17.

МАРШРУТЫ И ФОРМУЛЫ МАРШРУТОВ

На рис. 18а представлена дракон-схема “Охота на мамонта”. Заменим текст внутри икон буквами. Вместо “Охота на мамонта” запишем букву А, вместо “Поймай мамонта” — букву Б и т. д. В результате получим литеральную (буквенную) дракон-схему на рис. 18б. Литеральные схемы удобно использовать для описания маршрутов.

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

Линейный (неразветвленный) алгоритм имеет только один маршрут и одну формулу. Например, схема на рис. 18б описывается формулой

АБВГД

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

ЧТО ТАКОЕ РОКИРОВКА?

Рокировка — это преобразование алгоритма, при котором левое и правое плечо развилки меняются местами. Простейшие примеры рокировки показаны на рис. 8 и 21.

Два алгоритма называются равносильными, если для каждого маршрута первого алгоритма можно найти парный маршрут второго алгоритма, причем для каждой пары маршрутов их формулы совпадают. Обратимся к рис. 22. Легко убедиться, что схемы на рис. 22а и б имеют одинаковый набор маршрутов:

А да Б                    А нет

Следовательно, указанные дракон-схемы равносильны.

Формальное преобразование алгоритма А1 в алгоритм А2 называется равносильным, если алгоритмы А1 и А2 равносильны. Сказанное означает, что рокировка является равносильным преобразованием алгоритмов. При рокировке слова “да” и “нет” обязательно меняются местами.

ИСПОЛЬЗОВАНИЕ РОКИРОВКИ

ДЛЯ УЛУЧШЕНИЯ ЭРГОНОМИЧНОСТИ

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

Попытаемся обосновать аналогичный вывод для рис. 21, рассмотрев последовательно все промежуточные шаги рассуждений.

На первом шаге выдвигаем гипотезу: для сравнения двух маршрутов на рис. 21а можно использовать признак “лучше—хуже”.

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

На третьем шаге определяем главный маршрут, который по соглашению соответствует признаку “хорошо”. Следовательно, главный маршрут на рис. 21а идет через правое плечо развилки, что соответствует хорошей ситуации “брюки впору — их не надо подворачивать”.

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

На пятом шаге выполняем рокировку и получаем более эргономичный алгоритм на рис. 21б. На этом процедура заканчивается1.

Рассмотрим теперь более сложный алгоритм на рис. 10а. Этот алгоритм тоже плохой, потому что содержит три плохие (неэргономичные) развилки: 1) “В меню есть твой любимый салат?”, 2) “Борщ очень вкусный?”, 3) “Жаркое, как подошва?”. Последовательно применяя к развилкам три операции “рокировка”, получаем эргономичный алгоритм на рис. 10б.

Таким образом, на основании анализа примеров мы убедились: равносильное преобразование “рокировка” позволяет улучшить эргономичность алгоритмов. Однако этот вывод относится только к смысловым алгоритмам (где можно указать главный маршрут) и неприменим

к литеральным алгоритмам (где понятие главного маршрута теряет силу). Отсюда вытекает, что применение рокировки к литеральной схеме на рис. 22 бессмысленно, так как в данном случае рокировка не влияет на эргономичность.

ВЕРТИКАЛЬНОЕ И ГОРИЗОНТАЛЬНОЕ ОБЪЕДИНЕНИЕ

Бывает, что в дракон-схемах одинаковые иконы повторяются несколько раз. Например, на рис. 23а икона “Отдай мотоцикл в ремонт и впредь будь умнее” встречается три раза. Это плохо: навязчивые повторения раздражают читателя, которому приходится тратить лишнее время и несколько раз читать одно и то же. К счастью, некоторые повторы можно устранить. Такая возможность появляется, если одинаковые иконы соседствуют друг с другом, причем их выходы соединены между собой (рис. 23а). В этом случае действует правило “повторы запрещены”. Устранение повторов производится с помощью вертикальной линии (рис. 23б) и называется вертикальным объединением. Нетрудно доказать, что операция “вертикальное объединение” осуществляет равносильное преобразование алгоритмов.

Название “объединение” объясняется тем, что несколько одинаковых икон объединяются в одну. Последовательность действий такова: сначала входы этих икон объединяются вертикальной линией, после чего удаляются все одинаковые иконы, кроме крайней левой.

Сравнивая алгоритмы на рис. 23а и б, легко заметить, что схема на рис. 23б обладает более высоким эргономическим качеством: она стала более компактной, ясной и наглядной, поскольку освободилась от бессмысленного повторения икон. Отсюда проистекает вывод: равносильное преобразование “вертикальное объединение” позволяет улучшить эргономичность алгоритмов.

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

Рассмотрим пример на рис. 24а. Сначала с помощью горизонтального объединения устраним повторение иконы “Съешь кашу” и получим схему на рис. 24б. Затем применим вертикальное объединение и исключим повторение развилки “Есть можно?”. Окончательный результат показан на рис. 24в. Полученная схема более удобна и занимает меньше места, чем исходная схема на рис. 24а.

Разобранный пример показывает, что равносильное преобразование “горизонтальное объединение” также улучшает эргономичность алгоритмов.

П р е д о с т е р е ж е н и е: выполняя вертикальное и горизонтальное объединение, нужно следить, чтобы не появились пересечения соединительных линий (рис. 25).

ЭРГОНОМИЧНОСТЬ ЛИТЕРАЛЬНЫХ АЛГОРИТМОВ

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

Чтобы убедиться в этом, обратимся к рис. 26 и 27. В самом деле, схема на рис. 26а выглядит неоправданно громоздкой: она содержит семь вертикалей, тринадцать икон и заставляет читателя шесть раз читать идентификатор В, чтобы убедиться, что правые шесть икон одинаковые. А равносильная ей схема на рис. 26б (полученная методом вертикального объединения) свободна от этого недостатка. Она наглядна, проста и изящна, содержит только две вертикали и восемь икон, занимает втрое меньше места на листе бумаги (на экране) и к тому же имеет всего два прямоугольных излома линий (на рис. 26а — семь изломов). Таким образом, литеральная схема на рис. 26б более эргономична, чем ее соседка.

Еще более громоздкой выглядит литеральная схема на рис. 27а, в которой насчитывается 14 вертикалей. А равносильная ей схема на рис. 27б (полученная методом вертикального и горизонтального объединения) снова выигрывает: позволяет уменьшить число вертикалей почти в пять раз (с 14 до 3), сокращает число икон более чем в три раза (с 65 до 21), обеспечивает более экономное топологическое упорядочивание маршрутов, заметно сокращает суммарную длину соединительных линий.

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

ЧТО ДЕЛАТЬ, ЕСЛИ ЭРГОНОМИЧЕСКИЕ ТРЕБОВАНИЯ

ПРОТИВОРЕЧАТ ДРУГ ДРУГУ?

До сих пор мы рассматривали простейшие случаи, когда различные эргономические требования не вступали в конфликт. Однако подобные конфликты возможны. Вот два эргономических критерия, которые могут противоречить друг другу:

  • правило главного и побочного маршрутов,
  • минимизация числа вертикалей.

Чтобы исключить конфликт, следует держаться принципа: правило маршрутов имеет более высокий приоритет, нежели стремление уменьшить число вертикалей.

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

Чтобы исправить недостаток, необходимо выполнить:

  • вертикальное разъединение в точке С (эта операция обратна вертикальному объединению);
  • рокировку развилки “Заболел?”;
  • рокировку развилки “Врач помог?”.

В итоге получим схему на рис. 28б, где все маршруты упорядочены слева направо по принципу “чем правее — тем хуже”. В самом деле, левая вертикаль означает, что дела идут хорошо, ибо человек здоров; значит, главный маршрут идет по шампуру. Вторая вертикаль показывает легкое недомогание, которое можно снять таблеткой. Третья вертикаль говорит: самочувствие ухудшилось, нужен врач. Наконец, четвертая (крайняя правая) вертикаль означает, что дела обстоят плохо — пришлось лечь в больницу.

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

ИКОНА-ВСТАВКА КАК ЭРГОНОМИЧЕСКИЙ ПРИЕМ

Мы уже знаем, что язык ДРАКОН запрещает применять пересечения, обрывы и соединители. Отсюда вытекает жесткое ограничение: любая дракон-схема должна целиком размещаться на одном листе бумаги. А если она слишком большая и вылезает за рамки прокрустова ложа? Тогда можно взять бумагу больших размеров, например формата А1. А если схема громадная и все равно не помещается? На этот случай предусмотрены специальные приемы, позволяющие уменьшить габариты дракон-схемы и разрубить ее на куски. Эти приемы позволяют разместить дракон-схему на листах желаемого размера. Рассмотрим проблему на “миниатюрном” примере.

Предположим, линейный алгоритм состоит из четырнадцати икон, а бумажный лист небольшой, так что на нем можно разместить по вертикали не более десяти икон. Как быть?

На рис. 29 показаны два варианта решения проблемы. Алгоритм на рис. 29а не годится, так как на участке АВ рабочая точка движется вверх, что запрещено правилами языка ДРАКОН. Преодолеть затруднение можно двумя способами: применить конструкцию “силуэт” (о которой шла речь в гл. 6) либо разделить алгоритм на две части. Рассмотрим последний способ. Для этого удалим из алгоритма несколько связанных по смыслу икон, а вместо них нарисуем икону-заместитель, которая называется вставкой (рис. 29б). Вставка нужна, чтобы напомнить об изъятых иконах. Вставка занимает мало места — намного меньше, чем выброшенные иконы, поэтому алгоритм становится короче. Разумеется, выброшенные иконы не пропадают — они образуют новый алгоритм — алгоритм-вставку.

Икона-вставка — это команда “Передай управление в алгоритм-вставку” (рис. 30). Икона “конец” алгоритма-вставки означает: “Верни управление в основной алгоритм”. При этом управление возвращается в точку, расположенную после иконы-вставки. На языке программистов алгоритм-вставка — это процедура, а икона-вставка — это оператор “Вызов процедуры”.

ЧТО ТАКОЕ ПОДСТАНОВКА?

Операция “подстановка” связана с использованием иконы-вставки. Она выполняется за три шага.

Шаг 1. Из дракон-схемы удаляется фрагмент, имеющий один вход и один выход.

Шаг 2. Вместо него подставляется икона-вставка с именем Х.

Шаг 3. К удаленному фрагменту добавляется икона-заголовок с тем же именем Х и икона-конец; в результате получается алгоритм-вставка.

Два алгоритма на рис. 29 неравносильны: их формулы не совпадают, поскольку маршрут на рис. 29а содержит 14 икон, а на рис. 29б — 17 икон (см. также рис. 30). Вместе с тем нетрудно убедиться, что подстановка — эквивалентное преобразование алгоритмов, так как исходный и преобразованный алгоритмы дают одинаковые результаты для одних и тех же исходных данных. Попутно заметим, что равносильные алгоритмы всегда эквивалентны (обратное неверно). Таким образом, операция “подстановка” представляет собой эквивалентное (но не равносильное) преобразование алгоритмов.

УЛУЧШЕНИЕ ЭРГОНОМИЧНОСТИ АЛГОРИТМОВ

С ПОМОЩЬЮ ЦЕПОЧКИ ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ

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

Однако, чтобы сделать изложение более наглядным, лучше избрать другой путь и двигаться к цели мелкими шажками. Для начала используем визуальную формулу на рис. 32 и с ее помощью заменим нижнюю развилку на рис. 31а на икону-вставку “Приведи комнату в порядок”. Результат подстановки представлен на рис. 31б. Затем выполним рокировку и получим схему на рис. 31в. После этого произведем обратную подстановку по формуле на рис. 32 и заменим икону-вставку на развилку “Чернильница разбилась?” Полученная схема показана на рис. 31г. Наконец, делаем еще одну рокировку и приходим к искомой эргономичной схеме на рис. 31д.

Для удобства читателя на рис. 33 дана общая сводка эквивалентных преобразований.

ВЫВОДЫ

  1. Понятие эргономичного алгоритма весьма актуально. Применение достижений эргономики к теории алгоритмов позволяет значительно улучшить понимаемость алгоритмов и программ.
  2. Понятие эргономичного алгоритма задается с помощью конечного набора четко определенных правил и признаков, таких, как “главный маршрут должен идти по шампуру” и т. д. Следовательно, это понятие является строгим.
  3. Рассмотренные выше четыре эквивалентных преобразования алгоритмов подтверждают, что эргономичность алгоритмов можно улучшить с помощью простых и ясных методов, которые в некотором смысле можно считать формальными.

Comments (0)

You don't have permission to comment on this page.