DRAKON.SU

Текущее время: Четверг, 28 Март, 2024 19:10

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 18 ] 
Автор Сообщение
 Заголовок сообщения: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:54 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Уважаемые коллеги!

Предлагаю вашему вниманию
главу 36 из моей новой, пока еще не законченной из книги

Цитата:
Паронджанов В.Д. Учись писать, читать и понимать алгоритмы.
Основы алгоритмизации.

В данной главе я учел критические замечания, высказанные в мой адрес в теме «Эдсгер Дейкстра и язык Дракон»
viewtopic.php?f=62&t=2902

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


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 15:31, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:55 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Глава 36
ВИЗУАЛЬНЫЙ СТРУКТУРНЫЙ ПОДХОД
К АЛГОРИТМАМ И ПРОГРАММАМ (ШАМПУР-МЕТОД)

§1. ВВЕДЕНИЕ


Напомним, что книга посвящена алгоритмам. Вопросы программирования
в ней не рассматриваются. Данная глава отчасти является исключением.

В главе встречается классическое понятие «структурное программирование».
Мы будем использовать это понятие в первую очередь применительно
к алгоритмам. И лишь иногда — к программам.

§2. ТЕРМИНОЛОГИЯ

Введем понятие «визуальный структурный подход к алгоритмам
и программам». Определим его как набор правил, совпадающий
с визуальным синтаксисом языка ДРАКОН.

В концентрированном виде эти правила изложены в главе 33.

Данный подход предназначен для решения двух задач:
• создания наглядных, понятных и удобных для человеческого
восприятия алгоритмов и программ;
• автоматического доказательства правильности шампур-схем
(то есть графической части дракон-схем).

Наряду с термином «визуальный структурный подход к алгоритмам
и программам» мы будем для краткости (в качестве синонима)
использовать термин «шампур-метод».
Можно сказать, что данная книга — это подробное описание
шампур- метода.

§3. ДВА СТРУКТУРНЫХ ПОДХОДА

Как показано в работе [1], следует различать два структурных подхода:

• одномерный (текстовый) подход;
• двумерный (визуальный) подход.

Первый подход создан основоположниками компьютерной науки
и уточнен их последователями. Одномерный структурный подход
известен под названием «структурное программирование».
Он широко используется в мировой практике программирования.

Второй подход разработан автором, изложен в этой книге и других
работах (см. раздел «Основная литература по языку ДРАКОН» на стр. ).

§4. ПОСТАНОВКА ПРОБЛЕМЫ

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

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

• Традиционный (текстовый) структурный подход является,
по-видимому, наилучшим решением соответствующей задачи для
традиционного (текстового) структурного программирования

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

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

• Принципы структуризации, положенные в основу визуального
синтаксиса языка ДРАКОН, являются искомым решением.

В данной главе сделана попытка обосновать заявленные выводы.

Примечание. [1] означает:
1. Ермаков И.Е., Жигуненко Н.А. Двумерное структурное
программирование; класс устремлённых графов (теоретические
изыскания из опыта языка «Дракон») // Сборник докладов
конференции «Современные информационные технологии и
ИТ-образование». V Международная научно-практическая
конференция. 8—10 ноября 2010 г. Москва, МГУ.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 14:29, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:55 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§5. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

Понятие «структурное программирование» во многом связано с именем
Эдсгера Дейкстры. Данное понятие охватывает две темы:

• доказательство правильности программ (program correctness
proof);
• метод структуризации программ.

Ниже рассмотрены обе темы. Первая тема изложена в §§6 и 7. Вторая
излагается начиная с §8.

§6. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
КАК ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ ПРОГРАММ


В середине ХХ века появились компьютеры и компьютерные программы.
В ту раннюю эпоху теория программирования еще не существовала.

Разработка программ велась методом проб и ошибок. И выглядела
примерно так: «написать код программы — проверить код на компьютере
(протестировать) — найти ошибки — исправить код— снова протести-
ровать — снова найти ошибки — снова исправить и т.д.».

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

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

В «Заметках по структурному программированию» Дейкстра пишет:
Цитата:
«…необходимость продуманной структурной организации программы
представляется как следствие требования о доказуемости правильности
программы» [2, с. 52].


В толковом словаре читаем:
Цитата:
«Основным назначением общего метода структурного
программирования, разработанного в значительной степени Э. Дейкстрой,
является обеспечение доказательства правильности программы…
(program correctness proof)» [3, с. 463].


Таким образом, согласно Дейкстре, структурное программирование
подразумевает доказательство правильности программ.

§7. ЧЕМ РАЗЛИЧАЮТСЯ НАШ ПОДХОД К ДОКАЗАТЕЛЬСТВУ
ПРАВИЛЬНОСТИ И ПОДХОД ДЕЙКСТРЫ?


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

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

В чем отличие от подхода Дейкстры? Во-первых, мы говорим
не о полном, а о частичном доказательстве правильности.

Во-вторых, Дейкстра предлагает программистам доказывать
правильность программ не автоматически, а вручную с помощью
разработанных им математических методов (преобразование
предикатов и др.) [4].

Мы же предлагаем доказывать правильность не вручную,
а автоматически.

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

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

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

Так что полученный результат (безошибочное автоматическое
проектирование графики алгоритмов) следует признать заметным
шагом вперед.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 11:20, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:55 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§8. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
КАК МЕТОД СТРУКТУРИЗАЦИИ ПРОГРАММ


Основные положения метода общеизвестны:

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

§9. РАЗВИТИЕ КОНЦЕПЦИИ СТРУКТУРНОГО
ПРОГРАММИРОВАНИЯ


Работы основоположников структурного программирования
послужили исходной идеей для разработки шампур-метода
и языка ДРАКОН.

Предлагаемый нами двумерный структурный подход — это
непосредственное развитие классического одномерного
структурного программирования.

Почему возникла необходимость в таком развитии, то есть
в существенной доработке классических идей.

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

• Создатели структурного программирования недооценили
потенциальные возможности блок-схем (flow-charts). И не сумели дать
блок-схемам строгое математическое обоснование, пригодное
для трансляции блок-схем в объектные коды.

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

§10. ПЕРЕХОД ОТ ОДНОМЕРНОГО ТЕКСТА К ДВУМЕРНОЙ
ГРАФИКЕ РОЖДАЕТ НОВЫЕ ВОЗМОЖНОСТИ


Текстовые структурные управляющие конструкции сыграли позитивную
роль. Они позволили улучшить структуру и удобочитаемость программ,
уменьшить число ошибок и т.д. В сочетании с другими средствами
они помогли, как иногда говорят, «превратить программирование
из шаманства в науку».

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

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

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

Задача состоит в том, чтобы значительно уменьшить число запретов
и ограничений. То есть предоставить алгоритмистам и программистам
дополнительную свободу действий.

Эту задачу и решает язык ДРАКОН. Следуя по мудрому пути, начертанному
основоположниками структуризации, визуальный язык ДРАКОН устраняет
ненужные барьеры и препятствия. И позволяет совершить прыжок из царства
необходимости в царство свободы.

Каким образом? Благодаря замене одномерного (текстового) структурного
подхода на двумерный (визуальный) структурный подход. Последний,
разумеется, также является системой правил. Но в «двумерной» системе
правил значительная часть запретов снимается. То, что раньше было нельзя,
теперь можно.

Многие запреты (неизбежные при текстовом структурном программировании)
«перегибают палку». Они противоречат здравому смыслу и затрудняют
понимание алгоритмов и программ.

§11. УПРАВЛЯЮЩИЕ СТРУКТУРЫ, КОТОРЫЕ ЗАПРЕЩЕНЫ
В ТЕКСТОВОМ СТРУКТУРНОМ ПРОГРАММИРОВАНИИ
И РАЗРЕШЕНЫ В ВИЗУАЛЬНОМ


В книге приведено большое количество примеров таких структур.
Здесь нет необходимости их повторять. Поэтому мы приведем
только один пример. Рассмотрим схему на рис. 252.

В классическом структурном программировании управляющая структура
на рис. 252 и многие другие запрещены. Они считаются неструктурными.
Но такие алгоритмы часто встречаются на практике.

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

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

Недопустимо запрещать правильный процесс мышления. Его надо разрешить.
И ДРАКОН разрешает.

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

Поэтому наши предложения нельзя считать полностью новыми.
Они лишь развивают разработанные классиками идеи и снимают
ограничения, которые в ту эпоху (которая, кстати, еще не закончилась)
были неизбежными.
Вложение:
Рис._252_png.png
Рис._252_png.png [ 54.05 КБ | Просмотров: 17857 ]


§12. НОВАЯ ФИЛОСОФИЯ ПРОЦЕДУРНОГО
ПРОГРАММИРОВАНИЯ


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

Потому что в языке ДРАКОН применяется совершенно другой понятийный
аппарат (атомы, валентные точки и т.д.) — см. главы 32 и 33.

Смена понятийного аппарата — это переход к новому пониманию глубинной
сущности вещей. То есть к новому мировоззрению в области процедурного
программирования.

ДРАКОН — это не просто новый язык (новое семейство языков). Это новый
взгляд на процедурное программирование. Если угодно — новое мировоззрение.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 14:38, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:56 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§13. ЗАМЕНИТЕЛИ GOTO

Согласно классической теореме Бома и Джакопини, всякий реальный
алгоритм (программа) может быть построена из функциональных
блоков (операций) и двух конструкций: цикла и дихотомического
выбора (развилки) [5].

Эдсгер Дейкстра обогатил и усилил эту идею, предложив отказаться
от оператора безусловного перехода goto и ограничиться тремя
управляющими конструкциями: последовательность, выбор, цикл
[2, с. 25—28].

Дональд Кнут подверг критике тезис Дейкстры о полном исключении goto,
продемонстрировав случаи, где goto полезен [6].

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

Таблица 1
Позиция...........Используются три.....Используются......Используются
участников.......структурные..............заменители .........goto?
дискуссии........конструкции?.............goto?
Вариант 1.........Да.............................Нет......................Нет
Вариант 2.........Да.............................Нет......................Да
Вариант 3.........Да.............................Да........................Да
Вариант 4.........Да.............................Да........................Нет

Вариант 1 описывает ортодоксальную позицию Дейкстры, согласно
которой оператор goto имеет «гибельные последствия» и поэтому
«должен быть исключен из всех языков программирования
высокого уровня». Исходя из этого, были разработаны языки
без goto: Ява, Оберон и др.

Вариант 2 отражает мнение ранних критиков Дейкстры, позиция
которых выражается словами:
Цитата:
«использование оператора GOTO может оказаться
уместным в лучших структурированных программах» [7];
«всегда были примеры программ, которые не содержат
GOTO и аккуратно расположены лесенкой в соответствии
с уровнем вложенности операторов, но совершенно
непонятны, и были другие программы, содержащие goto
и все же совершенно понятные» [8, с. 134].
Нужно «избегать использования goto всюду, где это возможно,
но не ценой ясности программы» [8, c. 137—138].


Как известно, полемика по goto «растревожила осиное гнездо»
и всколыхнула «весь программистский мир».
Варианты 1 и 2 выражают крайние позиции участников дискуссии,
между которыми, как казалось вначале, компромисс невозможен.
Однако ситуация изменилась с изобретением и широким
распространением заменителей goto, примерами которых
являются:

• в языке СИ — операторы break, continue, return и функция еxit ( );
• в языке МОДУЛА-2 — операторы RETURN, EXIT, процедура HALT и т. д.

Заменители — особый инструмент, который существенно отличается
как от трех структурных управляющих конструкций, так и от goto.

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

Вариант 3 описывает языки Си, Паскаль в среде Дельфи, Ада, и др.,
где имеются заменители и на всякий случай сохраняется goto.

Вариант 4 соответствует языкам Модула-2, Ява, где также есть
заменители, однако goto исключен. Следует подчеркнуть, что при
наличии заменителей сфера применения goto резко сужается.
Так что удельный вес ошибок, связанных с его применением,
заметно уменьшается. Поэтому вопрос об исключении goto,
по-видимому, теряет прежнюю остроту.

Идея структуризации оказала большое влияние на разработку
алгоритмов и программ. Практически во все процедурные языки
(точнее, во все процедурные фрагменты языков) были введены
структурные конструкции цикла и ветвления, а также различные
заменители goto.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 11:58, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:56 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§14. ЧЕТЫРЕ ПРИНЦИПА СТРУКТУРИЗАЦИИ БЛОК-СХЕМ,
ПРЕДЛОЖЕННЫЕ Э. ДЕЙКСТРОЙ


Попытаемся еще раз заглянуть в темные переулки истории и
внимательно перечитаем классический труд Дейкстры
«Заметки по структурному программированию» [2].

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

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

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

Эти принципы таковы.

1. Принцип ограничения топологии блок-схем.
Структурный подход должен приводить
Цитата:
«к ограничению топологии блок-схем по сравнению с различными
блок-схемами, которые могут быть получены, если разрешить
проведение стрелок из любого блока в любой другой блок.
Отказавшись от большого разнообразия блок-схем и ограничившись
...тремя типами операторов управления, мы следуем тем самым
некоей последовательностной дисциплине» [2, с. 28].


2. Принцип вертикальной ориентации входов и выходов блок-схемы.
Имея в виду шесть типовых блок-схем (if-do, if-then-else, case-of, while-do,
repеat-until, а также «действие»), Дейкстра пишет:
Цитата:
«Общее свойство всех этих блок-схем состоит в том, что у каждой из них один вход вверху и один выход внизу» [2, с. 27].


3. Принцип единой вертикали.
Вход и выход каждой типовой блок-схемы должны лежать на одной вертикали.

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

Хотя Дейкстра не дает словесной формулировки третьего и четвертого
принципов, они однозначно вытекают из имеющихся в его работе
иллюстраций [2, с. 25—28].

Чтобы у читателя не осталось сомнений, мы приводим точные копии
подлинных рисунков Дейкстры (рис. 253, средняя и левая графа).

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

Однако этих близнецов ожидала разная судьба — судьба принца
и нищего.
Вложение:
Комментарий к файлу: Рисунки Дейкстры
Рис. 253.png
Рис. 253.png [ 38.58 КБ | Просмотров: 17857 ]


§15. ПОЧЕМУ НАУЧНОЕ СООБЩЕСТВО НЕ ПРИНЯЛО
ВИДЕОСТРУКТУРНУЮ КОНЦЕПЦИЮ Э. ДЕЙКСТРЫ?


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

Неприятность в том, что изложенные выше рекомендации Дейкстры
не были приняты во внимание разработчиками национальных и
международных стандартов на блок-схемы (ГОСТ 19.701–90,
стандарт ISO 5807–85 и т. д.).

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

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

В чем причина этой более чем странной ситуации?

Здесь уместно сделать отступление. Американский историк и философ
Томас Кун в книге «Структура научных революций» говорит о том, что
в истории науки время от времени появляются особые периоды, когда выдвигаются «несоизмеримые» с прежними взглядами научные идеи.
Последние он называет парадигмами [9].

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

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

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

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

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

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

Однако в 1972 году, в момент публикации работы Дейкстры [2], визуальное
программирование как термин, понятие и концепция фактически еще
не существовало.

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

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

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

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

Справедливости ради добавим, что и сам отец-основатель (Э. Дейкстра),
обычно весьма настойчивый в продвижении и популяризации своих идей,
отнесся к своему видеоструктурному детищу с удивительным безразличием.
И ни разу не выступил с предложением о закреплении структурной идеи
в стандартах на блок-схемы.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 15:13, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:57 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§16. ПАРАДОКС СТРУКТУРНОГО ПРОГРАММИРОВАНИЯ

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

В литературе по этому вопросу наблюдается редкое единодушие.
Да, они несовместимы. Вот несколько отзывов.
По мнению многих авторов, блок-схемы:
Цитата:
«не согласуются со структурным программированием,
поскольку в значительной степени ориентированы на использование
goto» [8, с. 150].

Они «затемняют особенности программ, созданных по правилам
структурного программирования» [3, с. 193].

«C появлением языков, отвечающих принципам структурного
программирования,... блок-схемы стали отмирать» [10].


Парадокс в том, что приведенные высказывания основываются
на недоразумении. Чтобы логический дефект стал очевидным,
сопоставим две цитаты по методу «очной ставки»:


Мнение критиков, убежденных в невозможности
структуризации блок-схем:

Цитата:
«Основной недостаток блок-схем заключается в том, что они
не приучают к аккуратности при разработке алгоритма.
Ромб можно поставить в любом месте блок-схемы, а от
него повести выходы на какие угодно участки.
Так можно быстро превратить программу в запутанный
лабиринт, разобраться в котором через некоторое время
не сможет даже сам ее автор» [10].


Предложение Э. Дейкстры о структуризации блок-схем
Структуризация блок-схем с неизбежностью приводит
Цитата:
«к ограничению топологии блок-схем по сравнению
с различными блок-схемами, которые могут быть получены,
если разрешить проведение стрелок из любого блока в любой
другой блок. Отказавшись от большого разнообразия блок-схем
и ограничившись... тремя операторами управления, мы следуем
тем самым некоей последовательностной дисциплине» [2, с. 28]


Сравнивая мнение современных авторов с позицией Дейкстры,
нетрудно убедиться, что описываемый критиками изъян
действительно имеет место.

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



§17. ПЛОХИЕ БЛОК-СХЕМЫ ИЛИ ПЛОХИЕ СТАНДАРТЫ?

Проведенный анализ позволяет сделать несколько замечаний.

• Обвинения, выдвигаемые противниками блок-схем,
неправомерны, потому что ставят проблему с ног на голову.
Дело не в том, что блок-схемы по своей природе противоречат
принципам структуризации. А в том, что при разработке стандартов
на блок-схемы указанные принципы не были учтены.
На них просто не обратили внимания, поскольку в ту пору —
именно в силу парадигмальной слепоты — считалось,
что на практике структурный подход следует применять
к текстам программ, а отнюдь не к блок-схемам.

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

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

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

________________________________________________________

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

Язык ДРАКОН позволил эффективно решить эту задачу. Одновременно
была решена задача эргономизации блок-схем, то есть задача
приспособления блок-схем для наиболее удобного человеческого
восприятия и понимания.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 13:25, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:57 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§18. ВИЗУАЛЬНОЕ И ТЕКСТОВОЕ СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

Можно предложить ряд правил, устанавливающих соответствие
между понятиями двумерного (визуального) и (одномерного)
текстового структурного подхода.

1. Макроикона «развилка» (рис. 242), в которую произведен
ввод функционального атома в левую или обе критические точки,
эквивалентна конструкциям if-then и if-then-else соответственно
[11, с. 120, 121]. См. также две верхние графы на рис. 253.

2. Макроикона «обычный цикл» (рис. 242), в которую
произведен ввод функционального атома в одну или обе критические
точки, эквивалентна конструкциям do-until, while-do, do-while-do
соответственно [11, с. 120, 121]. См. также две нижние графы
на рис. 253.

3. Непустая макроикона «переключатель» (рис. 242),
в которую введено нужное число икон «вариант» с помощью
операции «добавление варианта», эквивалентна конструкции
case [2, с. 27]. См. также рис. 253.

4. Непустая макроикона «цикл ДЛЯ» (рис. 242) эквива-
лентна циклу for языка СИ.

5. Непустая макроикона «переключающий цикл» (рис. 242),
в которую введено нужное число икон «вариант», эквивалентна
циклу с вложенным оператором саse, используемым, например,
при построении рекурсивных структурированных программ
по методу Ашкрофта—Манны [11, с.141, 142].

6. Шампур-блок — видеоструктурный эквивалент понятия
«простая программа» [11, с. 102].

7. Атом — общее понятие для основных составляющих блоков,
необходимых для построения программы согласно структурной
теореме Бома и Джакопини [5]. Оно охватывает также все
элементарные конструкции структурного подхода, кроме
последовательности [11, с. 119—121].
(Последняя в визуальном структурном подходе считается
неэлементарной структурой).

8. Операция «ввод атома» позволяет смоделировать две
операции:

• построить последовательность из двух и более атомов;

• методом заполнения критических точек осуществить
многократное вложение составных операторов друг в друга.

Благодаря этому единственный функциональный блок
«постепенно раскрывается в сложную структуру основных
элементов».
Вложение:
Рис. 242.png
Рис. 242.png [ 56.34 КБ | Просмотров: 17856 ]


§19. СТРУКТУРНЫЕ, ЛИАННЫЕ И АДРЕСНЫЕ БЛОКИ

Введем понятие «базовые операции» для обозначения операций
«ввод атома», «добавление варианта» и «боковое присоединение»
(см. главу 33).

Применяя к заготовке-примитив базовые операции любое число раз,
мы всегда получим структурную дракон-схему в традиционном
смысле слова (рис. 254).

Введем три понятия.

Структурный блок — шампур-блок, построенный только с помощью
базовых операций, без использования действий с лианой (рис. 254).

Лианный блок — шампур-блок, полученный из структурного блока
с помощью операции «пересадка лианы» (рис. 255).

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

В примитиве могут использоваться только структурные и лианные блоки
(рис. 254, 255).

В силуэте применяются все три типа блоков: структурные, лианные и
адресные (рис. 256, 257).

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

Чтобы смоделировать полезные функции оператора goto, в шампур-
методе предусмотрены операции «пересадка лианы» и «заземление
лианы».

И последнее. Силуэт на рис. 257 можно интерпретировать как детер-
минированный конечный автомат (рис. 258). Каждую ветку при желании
можно характеризовать как состояние автомата. Переход с ветки на
ветку означает переход из одного состояния в другое.




§20. ОПЕРАЦИИ С ЛИАНОЙ И ОПЕРАТОР GOTO

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

Однако они не приводят к хаосу, вызванному бесконтрольным
использованием goto.

С эргономической точки зрения, действия с лианой на порядок
эффективнее и удобнее, чем goto и заменители. Кроме того, они
весьма эффективно корректируют недостатки классического
(текстового) структурного программирования.

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

Как построить указанные схемы? Теперь мы имеем возможность
осветить этот вопрос. Схема на рис. 61 представляет собой структурный
блок, полученный с помощью операции «ввод атома».

В отличие от нее схема на рис. 62 — это лианный блок, построенный
методом пересадки лианы.

Уместно вспомнить предостережение Гленфорда Майерса:
Цитата:
«Правила структурного программирования часто предписывают
повторять одинаковые фрагменты программы в разных участках
модуля, чтобы избавиться от употребления операторов GOTO.
В этом случае лекарство хуже болезни. Дублирование резко
увеличивает возможность внесения ошибок при изменении
модуля в будущем» [8, с. 138].


Как видно на рис. 53, 56, 62 пересадка лианы позволяет элегантно
и без потерь решить эту непростую проблему, одновременно
улучшая наглядность и понятность программы, обеспечивая
более эффективное топологическое упорядочивание маршрутов.

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

Запрет на образование нового цикла вызван тем, что переход
на оператор, расположенный выше (раньше) в тексте программы,
считается «наихудшим применением оператора GOTO» [8, с. 135].
Указанный запрет вводится, чтобы выполнить требование: использовать
goto только для передачи управления вперед по программе, которое
считается более приемлемым

Запрет на образование второго входа в цикл соответствует требованию
структурного программирования, согласно которому цикл, как и любая
простая программа, должен иметь не более одного входа.

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

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

В визуальном структурном подходе аналогом goto и заменителей
служат формальные операции «пересадка лианы» и «заземление
лианы».


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 15:27, всего редактировалось 5 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 10:58 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
§21. ПОЧЕМУ САМОЛЕТ НЕ МАШЕТ КРЫЛЬЯМИ?

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

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

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

Это значит, что столь тщательно обоснованная Дейкстрой коллекция
ключевых слов структурного программирования (if, then, else, case, of,
while, do, repeat, until, begin, end [2, с. 22, 26, 27]) при переходе
к визуальному подходу становится ненужной. Для программиста
она просто перестает существовать!

В равной степени становятся лишними и отмирают и другие ключевые
слова, используемые оппонентами Дейкстры в различных вариантах
расширения структурного подхода: goto, continue, break, exit и т. д.

Поскольку в визуальном варианте структурного подхода ключевое
слово goto не используется, теряют смысл и все споры относительно
законности или незаконности, опасности или безопасности его
применения.

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

Предвижу возражения: хотя названные ключевые слова действительно
исчезают, однако выражаемые ими понятия сохраняют силу и для
визуального случая. Например, два визуальных алгоритма на рис. 60, 62
можно построить с помощью понятий if-then-else и goto.

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

Что касается собственно визуальных программ, то они, будучи
«выполнимой графикой», строятся из «выполняемых» икон и
«выполняемых» соединительных линий. Подчеркнем еще раз —
при построении алгоритма (программы) с помощью дракон-
конструктора пользователь не применяет понятия if-then-else и goto,
ибо в этом нет никакой необходимости.

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

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

Очевидно, что использование понятий, выражаемых ключевыми
словами текстового структурного программирования, не является
самоцелью. Оно служит для того, чтобы «делать наши программы
разумными, понятными и разумно управляемыми» [4, с. 272].

Указанные понятия решают эту задачу не во всех случаях,
а только в рамках текстового программирования.

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

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

§22. ЗАМЕЧАНИЯ

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

2. До появления компьютерной графики методология
текстового структурного программирования была наилучшим
решением.

3. Слабое место текстового представления алгоритмов
и программ заключается в недостатке выразительных средств.
Следствием являются ограничения и запреты. Эти ограничения
и запреты вытекают из природы текста, из природы текстового
представления управляющих структур.

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

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

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

7. Недопустимо запрещать правильный процесс
мышления. Его надо разрешить. Шампур-метод и язык ДРАКОН
устраняют этот недостаток.

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

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

11. ДРАКОН — это не просто новый язык (новое семейство языков).
Это новый взгляд на процедурное программирование. Если угодно —
новое мировоззрение.

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

13. Язык ДРАКОН позволил эффективно решить эту задачу.
Одновременно была решена задача эргономизации блок-схем,
то есть задача приспособления блок-схем для наиболее удобного
человеческого восприятия и понимания.

ЛИТЕРАТУРА К ГЛАВЕ 36

1. Ермаков И.Е., Жигуненко Н.А. Двумерное структурное
программирование; класс устремлённых графов (теоретические
изыскания из опыта языка «Дракон») // Сборник докладов
конференции «Современные информационные технологии и
ИТ-образование». V Международная научно-практическая
конференция. 8—10 ноября 2010 г. Москва, МГУ.

2. Дейкстра Э. Заметки по структурному программированию.
В кн.: Дал У., Дейкстра Э., Хоор К. Структурное программирование.
М.: Мир, 1975. — С. 7—97.

3. Толковый словарь по вычислительным системам / Под ред.
В. Иллингуорта и др.: Перевод с англ. М.: Машиностроение, 1991. — 560с.

4. Дейкстра Э. Дисциплина программирования. М.: Мир, 1978. — 275с.

5. Bohm C., Jacopini G. Flow Diagrams, Turing Machines and
Languages with Only Two Formation Rules // Comm. ACM. 1965.
Vol. 9, N 5. P. 366–371.

6. Knuth D. Structured Programming with GOTO Statements // Computing
Surves, 6 (4), 1974/ P. 261—301.
7. Ван Тассел Д. Стиль, разработка, эффективность, отладка
и испытание программ. М.: Мир, 1981. С. 89.

8. Майерс Г. Надежность программного обеспечения.
М.: Мир, 1980. — 360с.

9. Кун Т. Структура научных революций. М.: АСТ, 2003. — 608с.

10. Очков В. Ф., Пухначев Ю. В. 128 советов начинающему
программисту. М.: Энергоатомиздат, 1992. C. 21.

11. Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного
программирования. М.: Мир, 1982. — 406с.


Последний раз редактировалось Владимир Паронджанов Суббота, 23 Октябрь, 2010 14:24, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Суббота, 23 Октябрь, 2010 17:18 

Зарегистрирован: Воскресенье, 04 Ноябрь, 2007 23:01
Сообщения: 511
Владимир Паронджанов писал(а):
• Создатели структурного программирования недооценили
потенциальные возможности блок-схем (flow-charts). И не сумели дать
блок-схемам строгое математическое обоснование, пригодное
для трансляции блок-схем в объектные коды.
Утверждение неверное.

Определение блок-схем для алголоподобных языков дано в работе
    Langmaak H., Olderog E.-R., Present-day Hoare-like systems for programming languages with procedures: power, limits and most likely extensions. Lect. Notes Comput. Sci., 1979, 85, 363—373,
как полученных путём исключения процедур из определения языка. Также рассмотрены особенности построения полной и непротиворечивой системы аксиом.

Для схем с рекурсивными процедурами определения даны здесь:
    Jean H. Gallier SEMANTICS AND C0RRECTHESS OF NONDETERMINlSTIC FLOWCHART PROGRAMS WITH RECURSIVE PROCEDURES (Preliminary Report) Lecture Notes in Computer Science, 1978, Volume 62/1978, 251-267, DOI: 10.1007/3-540-08860-1_19

Не факт, что именно эти работы по теме самые первые, но как подтверждение строгих математических подходов, думаю, подойдёт.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Воскресенье, 24 Октябрь, 2010 16:26 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Владимир Паронджанов писал(а):
§5. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

Понятие «структурное программирование» во многом связано с именем
Эдсгера Дейкстры. Данное понятие охватывает две темы:

• доказательство правильности программ (program correctness
proof);
• метод структуризации программ.

Ниже рассмотрены обе темы. Первая тема изложена в §§6 и 7. Вторая
излагается начиная с §8.

§6. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ
КАК ДОКАЗАТЕЛЬСТВО ПРАВИЛЬНОСТИ ПРОГРАММ


В середине ХХ века появились компьютеры и компьютерные программы.
В ту раннюю эпоху теория программирования еще не существовала.

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

В толковом словаре читаем:
Цитата:
«Основным назначением общего метода структурного
программирования, разработанного в значительной степени Э. Дейкстрой,
является обеспечение доказательства правильности программы…
(program correctness proof)» [3, с. 463].


Таким образом, согласно Дейкстре, структурное программирование
подразумевает доказательство правильности программ.

§7. ЧЕМ РАЗЛИЧАЮТСЯ НАШ ПОДХОД К ДОКАЗАТЕЛЬСТВУ
ПРАВИЛЬНОСТИ И ПОДХОД ДЕЙКСТРЫ?


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

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

В чем отличие от подхода Дейкстры? Во-первых, мы говорим
не о полном, а о частичном доказательстве правильности.

Во-вторых, Дейкстра предлагает программистам доказывать
правильность программ не автоматически, а вручную с помощью
разработанных им математических методов (преобразование
предикатов и др.) [4].

Мы же предлагаем доказывать правильность не вручную,
а автоматически.

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

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

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

§5. Здесь две составляющие выделены, как, очевидно, и должно быть.
§6. Получается, что структурное программирование не рассматривается как более эргономичный метод по сравнению с неструктурным. Кроме того, создаётся впечатление, что надо доказывать правильность два раза. Это совершенно необязательно, когда сразу записываешь алгоритм на прогязыке.
§7. Каковы преимущества частичного доказательства правильности перед полным? Ведь реальная деятельность осуществляется не по одному "слепышу"... Это раз. Второе - Дейкстра, м.б. и предлагал только ручное доказательство - но новые методы (тот же model checking) предлагают и автоматическое, причём для деятельности в целом, а не только её маршрутной структуры.
Получаем, что опять для противопоставления смешиваются методы структуризации - текстовый с графическим - и это распространяется на метод доказательства - чисто графически доказывать хорошо (хотя бы это и частично получалось), а доказывать по тексту плохо...

Ещё раз хотелось бы обозначить - сегодняшние достижения математики и информатики, как я вижу, предоставляют пути реализовать доказательную формализацию деятельности. Для этого надо только визуализировать конкретный ЯВУ, для которого уже возможна автоматическая верификация, и заложить его стандарт в конструктор (включая и текстовый синтаксис - что даёт возможность генерации исходного текста для верификации). А чтобы не только проверка, но и уже синтез описаний был доказательным - нужно наметить визуализацию вывода программ из условий задачи ("эргономизируя математику и логику"). Да, это уже будет не для всех - но ведь и в материальном производстве не все инженеры-конструкторы? Важно, чтобы "предметник" мог принести эскиз деятельности (и изложение требований к ней, которые потом станут проверочными соотношениями) аналитику - и понимал, что тот преобразует его в расчётно-проверяемую форму - при этом либо сохранит смысл полностью, либо скажет: "извини, дорогой, твоё предложение не будет работать (вариант - непроверяемо); чтобы получить процесс, о котором известно, что он удовлетворяет желаемым тобой условиям, нужно изменить его так-то и так-то (вариант - невозможно добиться желаемых условий и их нужно изменить так-то и так-то)". И метод Дейкстры здесь поможет - в частности приведение силуэта и лианных структур к циклу Дейкстры... о котором тоже пока ничего не увидел. И опять же - Вирт много сделал в этом направлении (не говоря об усилиях Info21 по "русификации" его результатов - и в чём-то, как я понимаю, их развития) - но его результаты пока не визуализированы. Вот всё это и отразить бы в данной работе...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Воскресенье, 24 Октябрь, 2010 16:38 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Владимир Паронджанов писал(а):
[b]§22. ЗАМЕЧАНИЯ


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

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

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


ЛИТЕРАТУРА К ГЛАВЕ 36

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

К литературе добавил бы и книгу Ю.Г. Карпова...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Воскресенье, 24 Октябрь, 2010 16:49 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Владимир Паронджанов писал(а):
§18. ВИЗУАЛЬНОЕ И ТЕКСТОВОЕ СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

Можно предложить ряд правил, устанавливающих соответствие
между понятиями двумерного (визуального) и (одномерного)
текстового структурного подхода.

5. Непустая макроикона «переключающий цикл» (рис. 242),
в которую введено нужное число икон «вариант», эквивалентна
циклу с вложенным оператором саse, используемым, например,
при построении рекурсивных структурированных программ
по методу Ашкрофта—Манны [11, с.141, 142].

§19. СТРУКТУРНЫЕ, ЛИАННЫЕ И АДРЕСНЫЕ БЛОКИ

Структурный блок — шампур-блок, построенный только с помощью
базовых операций, без использования действий с лианой (рис. 254).

Чтобы смоделировать полезные функции оператора goto, в шампур-
методе предусмотрены операции «пересадка лианы» и «заземление
лианы».

§20. ОПЕРАЦИИ С ЛИАНОЙ И ОПЕРАТОР GOTO


Уместно вспомнить предостережение Гленфорда Майерса:
Цитата:
«Правила структурного программирования часто предписывают
повторять одинаковые фрагменты программы в разных участках
модуля, чтобы избавиться от употребления операторов GOTO.
В этом случае лекарство хуже болезни. Дублирование резко
увеличивает возможность внесения ошибок при изменении
модуля в будущем» [8, с. 138].

_______________________________________________________

В визуальном структурном подходе аналогом goto и заменителей
служат формальные операции «пересадка лианы» и «заземление
лианы».


§18. Наряду с другими следует ввести атом Цикл Дейкстры.
§19. Т.к. базовые операции - это ввод атома и, возможно, преобразования атомарных структур типа "прибавление/вычитание", то предлагаю назвать такой тип макроблоков "атомарным" - структурный тип макроструктурного блока даёт тавтологию.
§§19-20. Полезные функции goto можно смоделировать и при помощи цикла Дейкстры :) Чтобы не дублировать блоки на разных вертикалях - использовать подстановку. Тоже, кстати, повышает обозримость исходного (вызывающего) процесса...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Воскресенье, 24 Октябрь, 2010 16:53 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Владимир Паронджанов писал(а):
Глава 36
ВИЗУАЛЬНЫЙ СТРУКТУРНЫЙ ПОДХОД
К АЛГОРИТМАМ И ПРОГРАММАМ (ШАМПУР-МЕТОД)

§1. ВВЕДЕНИЕ


Напомним, что книга посвящена алгоритмам. Вопросы программирования
в ней не рассматриваются. Данная глава отчасти является исключением.

В главе встречается классическое понятие «структурное программирование».
Мы будем использовать это понятие в первую очередь применительно
к алгоритмам. И лишь иногда — к программам.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Вторник, 26 Октябрь, 2010 10:30 

Зарегистрирован: Понедельник, 09 Август, 2010 22:28
Сообщения: 128
Владимир, предлагаю выкладывать текст в виде Word документа, т.к. так удобнее рецензировать и вам не надо будет тратить время на публикацию множества постов.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 31 Октябрь, 2010 12:52 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1443
Ну вот, Илья Евгеньевич напомнил нам в этом сообщении, о чём это :) Соглашаясь по существу, хотелось бы снова вернуться к формам представления такого знания. Их наглядность можно и нужно повышать. Суть в том, чтобы преобразование "качественного" описания решения от предметника в доказательную форму по возможности было бы прослеживаемым для пользователя. Да, это потребует от него того же "теоретического минимума" - но формирование его облегчится.
В то же время следует излагать решение комплексно и на конкретных примерах - прежде всего "классических" задач программирования. Пока техноязыку этого недостаёт - и в этом смысле критика плодов труда его сторонников как здесь, так и на других форумах, справедлива. К этому тесно примыкает проблема со средствами визуализации - пока не будет среды, в которой можно будет:
    * от начала и до конца сочинить подобный комплексный пример и оттранслировать его "графитное" представление в части, понимаемой как программа, в исходный текст на прогязыке, готовый к дальнейшей автоматической обработке, и так же автоматически оттранслировать некий исходный текст в "графитный" проект (часть проекта);
    * вести базу компонентов и накапливать в ней те или иные фрагменты проектов, а равно и "подключить" к любому проекту компоненты из этой базы,
- любые заявления относительно возможностей визуализации будут неубедительны. Поиски средств визуального представления программ пока тоже слабо связаны с семантикой конкретных языков исходного текста - превалирует стремление к "универсальному решению".
Тенденции к наглядному изложению не следует считать лишь сегодняшними - что можно показать на таком примере:
Вложение:
Комментарий к файлу: Популярная статья о доказательной информатизации.
СоврКомп_Вирт-СтрДанИАлг-ст(ВМН84).djvu [276.93 КБ]
Скачиваний: 455

Некоторые вещи здесь изложены более наглядно, чем в одноимённой книге (в т.ч. последнего издания).
    Существенно также напоминание, что: "Большинство крупных систем ПО опирается на очень малое число глубинных алгоритмов... В то же время структуры данных, как правило, чрезвычайно сложны. В результате выбор правильного представления данных часто служит ключом к удачному программированию и может в большей степени сказываться на производительности программы, чем детали используемого алгоритма." (с. 75). Это снова возвращает нас к необходимости целостной эргономичной визуализации структур данных.
В этом смысле, думаю, представляет интерес описание в статье КМП- и БМ-алгоритмов поиска образца. В частности, иллюстрируется состояние структур данных исходно и при исполнении, используются информативные имена величин вместо литерных, с их участием целиком выписаны предикаты (по крайней мере, для КМП-алгоритма). Однако это всё только для человека - а нужен ещё язык определения структур данных.
Пока что литература по визуализации отстаёт - всё ещё не совершён переход к "визуализации доказательств" на базе "когнитивной письменности". Так кто же возьмётся за эту работу - хотя бы на примерах Вирта?
usr345 писал(а):
Владимир, предлагаю выкладывать текст в виде Word документа, т.к. так удобнее рецензировать и вам не надо будет тратить время на публикацию множества постов.
Да, тем более, что удобно иллюстрации будет смотреть и с лучшим качеством, чем обычно на страницах.

P.S. Кстати, при описании логики исполнения алгоритма в статье использован термин "пароль" - по отношению к условию ветвления. Представляется, что это удачный перевод и для нынешнего термина guard - в случае, когда он относится к условному выражению как сущности. А то, что в новой редакции Вирта называется "охрана", хорошо переводит условный выбор как явление.


Последний раз редактировалось Владислав Жаринов Вторник, 02 Ноябрь, 2010 18:30, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Воскресенье, 31 Октябрь, 2010 18:28 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
usr345 писал(а):
Владимир, предлагаю выкладывать текст в виде Word документа, т.к. так удобнее рецензировать и вам не надо будет тратить время на публикацию множества постов.

Уважаемый usr345!

Спасибо за совет. Совет принимается к исполнению.
На это уйдет 2-3 дня.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Основы алгоритмизации. Глава 36
СообщениеДобавлено: Четверг, 04 Ноябрь, 2010 10:45 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
usr345 писал(а):
Владимир, предлагаю выкладывать текст в виде Word документа, т.к. так удобнее рецензировать и вам не надо будет тратить время на публикацию множества постов.


Уважаемый usr345!

Ваш совет выполнен. См.
viewtopic.php?p=53369#p53369


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB