Как проверить блок схему на ошибки

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

1. На вкладке Процесс в группе Проверка схемы щелкнем на кнопке Проверить схему, чтобы выполнить используемый по умолчанию набор набор правил проверки блок-схемы.

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

2. В окне Вопросы щелкнем один раз на проблеме Соединитель не приклеен с обоих концов. Выделяется несоединенная соединительная линия.

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

3. В окне Вопросы щелкнем один раз на проблеме Фигура решения должна иметь более одного исходящего соединителя .

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

4. В окне Вопросы щелкнем один раз на проблеме Блок-схема не заканчивается начальной или завершающей фигурой.

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

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

На схеме выделяется фигура Подготовить описание вакансии и отсеивающие вопросы. Эта ошибка обусловлена несоединенной соединительной линией, которая описывалась в шаге 2.

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

Выделяется фигура Нанять кандидата, поскольку на схеме нет фигуры конца.

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

Сообщение об ошибке корректно. Фигура документа не имеет ни одной исходящей соединительной линии. Однако для данной фигуры это приемлемо, поскольку документ — это не шаг процесса, а представление артефакта процесса. Следовательно, мы укажем Visio игнорировать это правило для данной фигуры.

8. Щелкнем правой кнопкой мыши на уже выбранном описании проблемы и выберем команду Пропустить этот вопрос.

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

9. В окне Вопросы щелкнем один раз на проблеме Фигура блок-схемы не имеет текстовой подписи.

Эта проблема относится к фигуре документа. Мы добавим в фигуру текст.

10. Дважды щелкнем на фигуре документа, введем Руководство по проведению интервью, а затем нажмем клавишу Esc.

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

11. Щелкнем один раз на соединительной линии между фигурами Подготовить описание вакансии и отсевающие вопросы  и Прорекламировать открытую вакансию, а затем приклеим ее концы к этим фигурам.

12. Нарисуем соединительную линию из фигуры Кандидат принимает? к фигуре Выбрать кандидата. Не снимая выделения с соединительной линии, введем Нет и нажмем клавишу Esc.

13. Добавим фигуру Начало/конец после фигуры Нанять кандидата и нарисуем соединительную линию из фигуры Нанять кандидата к фигуре начала/конца.

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

Схема — это абстракция какого-либо процесса или системы, наглядно отображающая наиболее значимые части. Схемы широко применяются с древних времен до настоящего времени — чертежи древних пирамид, карты земель, принципиальные электрические схемы. Очевидно, древние мореплаватели хотели обмениваться картами и поэтому выработали единую систему обозначений и правил их выполнения. Аналогичные соглашения выработаны для изображения схем-алгоритмов и закреплены ГОСТ и международными стандартами.

На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем» [1]. Не смотря на то, что описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п., в настоящей статье описана лишь разработка схем алгоритмов программ.

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.

Содержание:

1. Элементы блок-схем алгоритмов
2. Примеры блок-схем
3. Нужны ли блок-схемы? Альтернативы

Элементы блок-схем алгоритмов

Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа.

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

	Терминатором начинается и заканчивается любая функция. Тип возвращаемого значения и аргументов функции обычно указывается в комментариях к блоку терминатора.
	В ГОСТ определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях.
	В блоке операций обычно размещают одно или несколько (ГОСТ не запрещает) операций присваивания, не требующих вызова внешних функций.
	Блок в виде ромба имеет один вход и несколько подписанных выходов. В случае, если блок имеет 2 выхода (соответствует оператору ветвления), на них подписывается результат сравнения — «да/нет». Если из блока выходит большее число линий (оператор выбора), внутри него записывается имя переменной, а на выходящих дугах — значения этой переменной.
	Вызов внешних процедур и функций помещается в прямоугольник с дополнительными вертикальными линиями.
	Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня — оператор с предусловием (while) или постусловием (do … while).
	Символ «подготовка данных» в произвольной форме (в ГОСТ нет ни пояснений, ни примеров), задает входные значения. Используется обычно для задания циклов со счетчиком.
	В случае, если блок-схема не умещается на лист, используется символ соединителя, отражающий переход потока управления между листами. Символ может использоваться и на одном листе, если по каким-либо причинам тянуть линию не удобно.
	Комментарий может быть соединен как с одним блоком, так и группой. Группа блоков выделяется на схеме пунктирной линией.

Примеры блок-схем

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

Сортировка вставками

Массив в алгоритме сортировки вставками разделяется на отсортированную и еще не обработанную части. Изначально отсортированная часть состоит из одного элемента, и постепенно увеличивается.

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

В приведенной блок-схеме для организации цикла используется символ ветвления. В главном цикле (i < n) перебираются элементы необработанной части массива. Если все элементы обработаны — алгоритм завершает работу, в противном случае выполняется поиск позиции для вставки i-того элемента. Искомая позиция будет сохранена в переменной j в результате выполнения внутреннего цикла, осуществляющем сдвиг элементов до тех пор, пока не будет найден элемент, значение которого меньше i-того.

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

Сортировка пузырьком

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

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

Сортировка выбором

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

На блок-схеме приведен пример использования блока «подготовка», а также показано, что в ряде случаев можно описывать алгоритм более «укрупнённо» (не вдаваясь в детали). К сортировке выбором не имеют отношения детали реализации поиска индекса минимального элемента массива, поэтому они могут быть описаны символом вызова внешней процедуры. Если блок-схема алгоритма внешней процедуры отсутствует, не помешает написать к символу вызова комментарий, исключением могут быть функции с говорящими названиями типа swap, sort, … .

На блоге можно найти другие примеры блок-схем:

• блок-схема проверки правильности расстановки скобок арифметического выражения [2];
• блок-схемы алгоритмов быстрой сортировки и сортировки слиянием [3].

Часть студентов традиционно пытается рисовать блок-схемы в Microsoft Word, но это оказывается сложно и не удобно. Например, в MS Word нет стандартного блока для терминатора начала и конца алгоритма (прямоугольник со скругленными краями, а не овал). Наиболее удобными, на мой взгляд, являются утилиты MS Visio и yEd [5], обе они позволяют гораздо больше, чем строить блок-схемы (например рисовать диаграммы UML), но первая является платной и работает только под Windows, вторая бесплатная и кроссплатфомренная. Все блок-схемы в этой статье выполнены с использованием yEd.

Частные конторы никакие блок-схемы не используют, в книжках по алгоритмам [6] вместо них применяют словесное описание (псевдокод) как более краткую форму. Возможно блок-схемы применяют на государственных предприятиях, которые должны оформлять документацию согласно требованиям ЕСПД, но есть сомнения — даже для регистрации программы в Государственном реестре программ для ЭВМ никаких блок-схем не требуется.

Тем не менее, рисовать блок-схемы заставляют школьников (примеры из учебников ГОСТ не соответствуют) — выносят вопросы на государственные экзамены (ГИА и ЕГЭ), студентов — перед защитой диплом сдается на нормоконтроль, где проверяется соответствие схем стандартам.

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

Появляются подозрения, что система образования прогнила и отстала лет на 20, однако аналогичная проблема наблюдается и за рубежом. Международный стандарт ISO 5807:1985 мало чем отличается от ГОСТ 19.701-90, более нового стандарта за рубежом нет. Там же производится множество программ для выполнения этих самых схем — Dia, MS Visio, yEd, …, а значит списывать их не собираются. Вместо блок-схем иногда применяют диаграммы деятельности UML [6], однако удобнее они оказываются, разве что при изображении параллельных алгоритмов.

Периодически поднимается вопрос о том, что ни блок-схемы, ни UML не нужны, да и документация тоже не нужна. Об этом твердят программисты, придерживающиеся методологии экстремального программирования (XP) [7], ходя даже в их кругу нет единого мнения.

В ряде случаев, программирование невозможно без рисования блок-схем, т.к. это один процесс — существуют визуальные языки программирования, такие как ДРАКОН [8], кроме того, блок-схемы используются для верификации алгоритмов (формального доказательства их корректности) методом индуктивных утверждений Флойда [9].

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

Список использованных источников:

1. ГОСТ 19.701–90 (ИСО 5807–85) «Единая система программной документа­ции».
2. Алгоритм. Свойства алгоритма https://pro-prof.com/archives/578
3. Алгоритмы сортировки слиянием и быстрой сортировки https://pro-prof.com/archives/813
4. yEd Graph Editor https://www.yworks.com/products/yed
5. Книги: алгоритмы https://pro-prof.com/books-algorithms
6. Рамбо Дж., Якобсон А., Буч Г. UML: специальный справочник. -СПб.: Питер, 2002. -656 с.
7. Кент Бек Экстремальное программирование: разработка через тестирование – СПб.: Питер – 2003
8. Визуальный язык ДРАКОН https://drakon.su/
9. Шилов Н.В. Верификация шаблонов алгоритмов для метода отката и метода ветвей и границ. Моделирование и анализ информационных систем, ISSN 1818 – 1015, т.18, №4, 2011
10. Брукс Ф., Мифический человеко — месяц или как создаются программные системы. СПб. Символ Плюс, 1999 — 304 с. ил.

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

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

Перед
компиляцией следует выполнить настройки
функций контроля. Настройки выполняются
в диалоге, активизируемом командой
главного меню Project>>Document
Options. Открывается
диалоговое окно Options
for Project<имя
проекта>.PrjPcb с десятью панелями-вкладками,
на которых перечислены все возможные
признаки, по которым выявляются ошибки
проекта.

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

На
вкладке Error Reporting назначается характер
реакции программы на обнаруженные
нарушения:

• No
Report – не включать обнаруженное нарушение
в отчет;

•
Warning – вывести
предупреждение;

•
Error – вывести
сообщение об ошибке;

•
Fatal Error – вывести
сообщение о фатальной ошибке, при которой
невозможно выполнение операции.

Чтобы
установить уровень всех нарушений в
значение Error следует
нажать правой кнопкой мыши в любом месте
окна и выбрать All Error.

Все
типы нарушений на вкладке Error
Reporting разбиты на группы,
по отношению к определенному типу
объектов, варианты их отображения и
рекомендуемые настройки:

1.
Violations Associated
with Buses —
предупреждения, связанные с шинами.

2.
Violations Associated
with Components –
предупреждения, связанные с компонентами.

3.
Violations Associated
with Configuration
Constrains – предупреждения,
связанные с ограничениями конфигурации.

4.
Violations Associated
with Documents –
предупреждения, связанные с документами.

5.
Violations Associated
with Harnesses –
предупреждения, связанные со жгутами.

6.
Violations Associated
with Nets –
предупреждения, связанные с цепями.

7.
Violations Associated with Others, Violations Associated with
Parameters – предупреждения,
связанные с
параметрами и
другие.

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

Вкладка
Class Generation
– правила формирования классов цепей
и компонентов. При желании можно отключить
формирование комнат и классов компонентов
согласно подлистам схемы.

На
вкладке Comparator настраиваются правила
проверки соответствия имен одинаковых
объектов, цепей на листах многолистового
проекта и целого ряда других возможных
ошибок.

Вкладка
ECO Generation –
настройки отчета о перечне изменений.
Выбираются те изменения, которые следует
включить в отчет; по умолчанию включены
все опции – изменять эти данные
нецелесообразно.

Вкладка
Options – группа дополнительных
настроек проекта. Здесь задаются
директории сохранения отчета о компиляции,
компарации и т.д. В группе Output
Options выбираются действия,
которые следует применить после
выполнения процесса компиляции.

Вкладка
Multi Channel –
задает порядок номерации компонентов
при реализации многоканальных и
иерархических проектов.

Вкладка
Default Prints –
настройки распечатки документации
проекта.

Вкладка
Search Puths –
расположение библиотек, в которых по
умолчанию будет проводиться поиск
компонентов.

Вкладка
Parameters – параметры проекта,
которые могут быть использованы для
составления текстовых надписей,
являющихся общими для всех документов
проекта.

Вкладка
Device Sheets –
расположение директорий, содержащих
схемы, которые используются в проекте
в качестве готовых решений (подсхем) в
иерархии нижних уровней.

Компиляция
проекта выполняется по команде главного
меню Project>> Compile Document <имя_схемы>.SchDoc.
Если при компиляции обнаружены ошибки,
сообщения об ошибках выводятся на панель
Messages. В этом случае следует проанализировать
сообщения, внести в схемный документ
необходимые изменения и повторить
компиляцию проекта. Схемный документ,
откомпилированный без ошибок, может
быть передан на проектирование печатной
платы.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #