DRAKON.SU

Текущее время: Пятница, 19 Январь, 2018 20:40

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




Начать новую тему Ответить на тему  [ Сообщений: 73 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
СообщениеДобавлено: Вторник, 11 Июль, 2017 14:42 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3482
Откуда: Москва
Rifat писал(а):
есть несколько цитат Энтони Хоара:
Цитата:
Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

и
Цитата:
Нужен код, совершенно очевидно свободный от ошибок, а не код, свободный от очевидных ошибок.
Рифат, спасибо. Вы не могли бы дать точное указание на литературу с указанием номера страницы


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Июль, 2017 15:24 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Вложение:
Hoare3.png
Hoare3.png [ 16.76 КБ | Просмотров: 1809 ]

Вложение:
Hoare2.png
Hoare2.png [ 11.68 КБ | Просмотров: 1809 ]

Вложение:
Hoare1.png
Hoare1.png [ 35.24 КБ | Просмотров: 1809 ]

Вложение:
Hoare5.png
Hoare5.png [ 4.06 КБ | Просмотров: 1809 ]

Вложение:
Hoare4.png
Hoare4.png [ 32.04 КБ | Просмотров: 1809 ]


Цитаты были не дословные, но смысл тот же. К тому же нужно учитывать, что Hoare говорил по-английски и возможны разные переводы.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 11 Июль, 2017 15:31 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3482
Откуда: Москва
Рифат, спасибо


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 13 Июль, 2017 08:27 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3482
Откуда: Москва
Есть тысяча просмотров
По состоянию на сегодня:
Цитата:
1004 просмотров
за подано 10 голосов
против 6


Имеется в виду:
"Неклассическая теория алгоритмов и алгоритмический язык ДРАКОН" в ИСП РАН

Доклад Владимира Паронджанова на семинаре в Институте системного программирования Российской академии наук 19 мая 2017 года

Длительность видеоролика 2 часа 38 минут
https://www.youtube.com/watch?v=MFPqCqcv7kY


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 17 Июль, 2017 20:46 

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

Со страницы 95 приводятся несколько слайдов, где, как я понял, показывается, что всё, что есть в структурном программировании, есть и в Дракон-схемах. Что как бы доказывает, что термин "двумерное структурное" программирование правильный. Но обычное структурное программирование ограничивается тремя управляющими конструкциями, а Дракон-схема не ограничивается. И вот эти излишества уже не делают Дракон-схему похожей на структурные схемы Дейкстры. Если, допустим, к структурным схема Дейкстры добавить всего один небольшой элемент: разрешить произвольные переходы внутри схемы, то это уже будет не структурная схема.

Рифат, термин "Двумерное структурное программирование" применительно к языку ДРАКОН ввели Илья Ермаков и Жигуненко в статье :
Цитата:
ДВУМЕРНОЕ СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ; КЛАСС УСТРЕМЛЁННЫХ ГРАФОВ.
(ТЕОРЕТИЧЕСКИЕ ИЗЫСКАНИЯ ИЗ ОПЫТА ЯЗЫКА «ДРАКОН»)

viewtopic.php?p=76041#p76041


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 17 Июль, 2017 23:53 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Владимир Паронджанов писал(а):
Rifat писал(а):
В презентации увидел и свой комментарий, что довольно таки лестно, как будто бы цитата известного деятеля.

Со страницы 95 приводятся несколько слайдов, где, как я понял, показывается, что всё, что есть в структурном программировании, есть и в Дракон-схемах. Что как бы доказывает, что термин "двумерное структурное" программирование правильный. Но обычное структурное программирование ограничивается тремя управляющими конструкциями, а Дракон-схема не ограничивается. И вот эти излишества уже не делают Дракон-схему похожей на структурные схемы Дейкстры. Если, допустим, к структурным схема Дейкстры добавить всего один небольшой элемент: разрешить произвольные переходы внутри схемы, то это уже будет не структурная схема.

Рифат, термин "Двумерное структурное программирование" применительно к языку ДРАКОН ввели Илья Ермаков и Жигуненко в статье :
Цитата:
ДВУМЕРНОЕ СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ; КЛАСС УСТРЕМЛЁННЫХ ГРАФОВ.
(ТЕОРЕТИЧЕСКИЕ ИЗЫСКАНИЯ ИЗ ОПЫТА ЯЗЫКА «ДРАКОН»)

viewtopic.php?p=76041#p76041


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

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

P = p^N

Если число N будет очень велико, то значение р должно быть очень и очень близко к 1, если мы хотим, чтобы значение Р существенно отличалось от нуля!

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

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

...

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

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

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

(1) перечисление;
(2) математическая индукция;
(3) абстракция.


В статье Илья Ермаков и Жигуненко есть несколько фактических ошибок относительно истории структурного программирования. Самое понятие структурного программирования рассматривается очень упрощенно. (Дейкстра писал "Apparently, IBM did not like the popularity of my text; it stole the term "Structured Programming" and under its auspices Harlan D. Mills trivialized the original concept to the abolishment of the goto statement.") Сам же Дейкстра выводит структуру программы из интеллектуальных средств, которые есть для доказательства корректности программы. Он считал, что программист должен не только написать (правильную) программу, но и обосновать ее правильность.
В статье же, где упоминается про "двумерное структурное программирование" нет этих обоснований. По сути происходит подмена понятия.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 09:30 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3482
Откуда: Москва
Рифат, я привожу цитату из Дейкстры (из того же источника):
Цитата:
Конечно, я не осмеливаюсь утверждать (по крайней мере теперь!), что программист должен предоставлять такое доказательство всякий раз, когда пишет в своей программе простой цикл. Тогда бы он вообще никогда не смог написать программу любого размера!

ЭТО было бы столь же нереально, как явное и полное сведение любого доказательства в планиметрии к аксиомам Евклида. (См. раздел "О количественной ограниченности наших возможностей".)

http://khpi-iip.mipk.kharkiv.edu/librar ... dij04.html


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 10:06 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Во-первых, Дейкстра говорит про "такое доказательство", то доказательство, которое он приводит выше и описывает его очень подробно. Смысл фразы в том, что не всегда нужно так подробно расписывать.

А далее идёт текст:
Цитата:
Хочу сделать три вывода из сказанного. Во-первых, когда программист рассматривает конструкцию типа (6) как заведомо правильную, он имеет на это право потому, что знаком с такой конструкцией. Я предпочитаю рассматривать его поведение как неосознанную ссылку на теорему, которую он знает, хотя не исключено, что он никогда не удосуживался сформулировать ее. Когда-то он убедился в ее правильности, хотя, возможно, он уже забыл свой способ доказательства и хотя этот способ (возможно) и непригоден для публикации. Тем не менее мы могли бы сформулировать свое мнение о программе (6) в виде, скажем, "теоремы линейного поиска", а зная такое название, гораздо легче (и более естественно) апеллировать к нему интуитивно.

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 14:54 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Rifat писал(а):
В статье Илья Ермаков и Жигуненко есть несколько фактических ошибок относительно истории структурного программирования. Самое понятие структурного программирования рассматривается очень упрощенно. (Дейкстра писал "Apparently, IBM did not like the popularity of my text; it stole the term "Structured Programming" and under its auspices Harlan D. Mills trivialized the original concept to the abolishment of the goto statement.") Сам же Дейкстра выводит структуру программы из интеллектуальных средств, которые есть для доказательства корректности программы. Он считал, что программист должен не только написать (правильную) программу, но и обосновать ее правильность.
В статье же, где упоминается про "двумерное структурное программирование" нет этих обоснований. По сути происходит подмена понятия.


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

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

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

Плюс, конечно, жанр статьи - техническое эссе, скажем так. Не окончательный материал, а к размышлению.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 15:53 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Предпоследний абзац статьи следующий:
Цитата:
7. Аксиоматика ДРАКОН-схем. Оказывается, что топология ДРАКОН-схем (в алгоритмах-примитивах и внутри каждой ветки алгоритмов-силуэтов) соответствует классу устремлённых (сводимых, аранжируемых) циклических ориентированных графов, с дополнительно наложенным ограничением планарности (укладки на плоскости без пересечений). Таким образом, эмпирически полученный В.Д. Паронджановым визуальный язык и его конструктивное определение оказываются эквивалентными самому общему классу графов, который обладает свойством управляемости, т. е. остаётся в достаточной мере структурированным для построения алгоритмов с легко предсказуемыми свойствами. ДРАКОН-топологию можно рассматривать как оптимальное расширение классической структурной, предназначенное для использования в двумерном визуальном программировании.

То есть, статья рассматривает не ДРАКОН-схему силуэт целиком, а только её часть. Вы с этим согласны?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 16:17 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
По сути, да.

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

Да, теоретически его можно применить в стиле GOTO, если это волнует. Но это с таким же успехом можно и с WHILE-CASE.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 17:20 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Илья Ермаков писал(а):
Да, теоретически его можно применить в стиле GOTO, если это волнует.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 19:53 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 631
Откуда: Россия, Орёл
Зато конечный автомат естественным образом описывается.
И любой реактивный алгоритм с состояниями.

Да даже просто алгоритм обработки запроса.

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

А в обычных алгоритмах - только 1 веточный цикл на схему, с одной точкой входа.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 18 Июль, 2017 21:37 

Зарегистрирован: Вторник, 27 Май, 2008 13:24
Сообщения: 153
Rifat писал(а):
В силуэте возможны переходы назад ... программист должен ломать голову и думать, как же она работает?
Силуэт для того чтобы не думать, а видеть как работает. Есть смысл думать как не работает. И для анализа последнего силуэт хорош. Почему? Предполагаю потому что исторически силуэт появился в языческие времена неструктурного набора команд ассемблера в котором джампы божества, а GOTO сам Зевес над ними- и в этом заключалась единственная естественная структурность, и силуэт внятно, "антично" изобразил этот пантеон. Это и было решением задачи структурирования без создания заведомо структурного языка.
Силуэт - это хорошо приготовленные спагетти.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 19 Июль, 2017 16:09 
Аватара пользователя

Зарегистрирован: Суббота, 29 Март, 2008 19:27
Сообщения: 906
Откуда: Россия, Чебоксары
dvuugl писал(а):
Силуэт - это хорошо приготовленные спагетти.
Именно.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 19 Июль, 2017 16:31 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Мне кажется, пора уже прекратить эти споры по поводу goto. А для этого нужно сделать специальную версию Дракона, где в силуэте нельзя будет использовать произвольные переходы на разные ветки. И в качестве положительного побочного эффекта появится симметрия между примитивом и силуэтом: все что можно будет изобразить в виде силуэта можно будет изобразить и в виде примитива (сейчас пока это не всегда возможно) и наоборот.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 19 Июль, 2017 16:37 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3482
Откуда: Москва
Rifat писал(а):
претензия к силуэту. В силуэте возможны переходы назад и, соответственно, с их помощью можно сооружать очень много разных причудливых циклических конструкций. И по сути для каждой из этих конструкций программист должен отдельно ломать голову и думать, как же она работает?
Рифат, неясно, что вы имеете в виду.

Пожалуйста, приведите пару примеров "причудливых циклических конструкций", над которыми "программист должен... ломать голову".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 19 Июль, 2017 17:38 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Пример блок-схемы:
Вложение:
Intersect.png
Intersect.png [ 28.9 КБ | Просмотров: 1716 ]

Здесь представлено два цикла, которые "пересекаются". Данную блок-схему можно изобразить и в виде силуэта (к сожалению, нет времени это делать).

И до этого приводил подобные примеры: http://forum.drakon.su/viewtopic.php?f=62&t=5902&p=98351&hilit=%D0%BD%D0%B5%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%BD%D1%8B%D0%B5#p98361


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 20 Июль, 2017 15:50 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 3482
Откуда: Москва
Рифат, я жду от вас опровергающий пример.
К сожалению, ваш материал таковым не является.

1. Блок-схема действительно плохая, но она не имеет отношения к дРАКОНу.

2. Ваш пример по ссылке (силуэт) содержит второй вход в цикл, что в ДРАКОНе запрещено.

download/file.php?id=6229


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 21 Июль, 2017 09:37 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 194
Откуда: Казань
Вложение:
DrakonIntersect.png
DrakonIntersect.png [ 148.68 КБ | Просмотров: 1683 ]

Что неправильного в данной дракон-схеме?
Справа от дракон-схемы блок-схема, по которой сделана дракон-схема, чтобы было проще сравнивать.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 73 ]  На страницу Пред.  1, 2, 3, 4  След.

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


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

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


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

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