DRAKON.SU
https://forum.drakon.su/

Алгоритм уважаемого Дейкстра
https://forum.drakon.su/viewtopic.php?f=166&t=3946
Страница 1 из 2

Автор:  ==== [ Пятница, 20 Апрель, 2012 18:34 ]
Заголовок сообщения:  Алгоритм уважаемого Дейкстра

отсюда http://walwalru.blogspot.com/2012_04_01_archive.html
Вложение:
%D0%B4%D0%B5%D0%B9%D1%81%D1%82%D1%80%D0%B01[1].png

Автор:  Валерий Лаптев [ Суббота, 21 Апрель, 2012 02:57 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Блеск! Вывод: Дракон надо всерьез осваивать и давать студентам.

Автор:  Info21 [ Суббота, 21 Апрель, 2012 11:37 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Валерий Лаптев писал(а):
Блеск! Вывод: Дракон надо всерьез осваивать и давать студентам.
Мне сообщили, мол, посмотри.
Честно скажу, не вполне понимаю, чем впечатляться.

Автор:  Валерий Лаптев [ Суббота, 21 Апрель, 2012 15:00 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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

Автор:  Info21 [ Суббота, 21 Апрель, 2012 17:47 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Не вижу, как заниматься верификацией алгоритма по этакой картинище.

Автор:  ==== [ Суббота, 21 Апрель, 2012 19:03 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Картинка служит не для верификации алгоритма, а для его записи, и используется исполнителем при выполнении алгоритма.

Автор:  Info21 [ Суббота, 21 Апрель, 2012 19:56 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Для верификации алгоритма он должен быть представлен в записанном виде.

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

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

Автор:  ==== [ Суббота, 21 Апрель, 2012 20:23 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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

Пример верификации алгоритма на конкретных данных приведен на указанной ссылке.

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

Автор:  Info21 [ Суббота, 21 Апрель, 2012 21:12 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Геннадий Тышов писал(а):
Пример верификации алгоритма на конкретных данных приведен на указанной ссылке.
В процитированном предложении термин "верификация" использован некорректно.

Автор:  ==== [ Суббота, 21 Апрель, 2012 21:35 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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

Заменим в цитате термин "верификация" на "исполнения".

Рассуждения о верификации являются уходом от предложения Вам -
Цитата:
Мне сообщили, мол, посмотри.

Предложение, вероятно, связано с Вашим проектом о "спецназе" в котором алгоритмика является ключевым моментом, но при этом отсутствует выбор средства. Язык ДРАКОН и ИС Дракон являются таким средством. Преподаватель школы меньше Вас знаком с языком ДРАКОН, но выбор сделал раньше.

Автор:  Сергей Прохоренко [ Суббота, 21 Апрель, 2012 22:10 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Валерий Лаптев писал(а):
Блеск! Вывод: Дракон надо всерьез осваивать и давать студентам.

Вовсе не надо:
1. Нет никакой необходимости. Современные языки программирования позволяют даже новичкам обойтись вообще без блок-схем, включая Дракон.
2. Неудобно. Дракон-схемы плохо поддаются масштабированию (при росте алгоритма не влезают в экран, и поэтому плохо воспринимаются).
3. Закрепляет вредные навыки у студентов. Дракон содержит в себе как важнейшую составную часть неструктурированные переходы (аналог GOTO), от которых всеми силами пытаются избавиться разработчики языков программирования и серьезные программисты. Правда, при автоматической генерации кода по Дракон-схеме это безопасно, но учить этому студентов для (в дальнейшем) программирования на других языках программирования - нехорошо. Дракон с автоматической кодогенерацией не может полностью заменить ни один из языков программирования (не содержит многих необходимых вещей), и поэтому обучать ему как средству разработки бессмысленно.
4. Создает ненужную конкуренцию гораздо более многообещающему графическому (как и Дракон) средству программирования - структурному (семантическому) редактору. Когда же, наконец, мы его увидим? :roll: (это риторический вопрос)

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

Автор:  ==== [ Воскресенье, 22 Апрель, 2012 01:05 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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

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

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

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

Валерий Лаптев писал(а):
Блеск! Вывод: Дракон надо всерьез осваивать и давать студентам.
Правильный вывод, надо учить студентов мыслить, графически отображать и передавать свои мысли, алгоритмически обеспечивать свою и коллективную деятельность. Обучение алгоритмизации должно быть всеобщим.

Автор:  Валерий Лаптев [ Воскресенье, 22 Апрель, 2012 06:52 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Сергей Прохоренко писал(а):
Валерий Лаптев писал(а):
Блеск! Вывод: Дракон надо всерьез осваивать и давать студентам.

Вовсе не надо:
1. Нет никакой необходимости. Современные языки программирования позволяют даже новичкам обойтись вообще без блок-схем, включая Дракон.
2. Неудобно. Дракон-схемы плохо поддаются масштабированию (при росте алгоритма не влезают в экран, и поэтому плохо воспринимаются).
3. Закрепляет вредные навыки у студентов. Дракон содержит в себе как важнейшую составную часть неструктурированные переходы (аналог GOTO), от которых всеми силами пытаются избавиться разработчики языков программирования и серьезные программисты. Правда, при автоматической генерации кода по Дракон-схеме это безопасно, но учить этому студентов для (в дальнейшем) программирования на других языках программирования - нехорошо. Дракон с автоматической кодогенерацией не может полностью заменить ни один из языков программирования (не содержит многих необходимых вещей), и поэтому обучать ему как средству разработки бессмысленно.
4. Создает ненужную конкуренцию гораздо более многообещающему графическому (как и Дракон) средству программирования - структурному (семантическому) редактору. Когда же, наконец, мы его увидим? :roll: (это риторический вопрос)

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

1. Абсолютно не согласен. Обратные графические средства нужны как воздух. Вот сейчас у нас в редакторе - 6 проектов, каждый из которых занимает несколько тысяч строк. По тексту разобраться (вдруг главный пацан свалит ?!) - можно, но не начинающему программеру. А графиченское представление взаимосвязей - сильно облегчает восприятие.
2. Алгоритмы должны быть МАЛЕНЬКИЕ. Весь рефакторинг на это направлен. Поэтому это замечание не актуально.
3. Блоксхемы тоже содержат переходы. Однако мы проводили небольшое исследование. Есть ряд народа (в основном девочки), которые блок-схемы воспринимают гораздо легче текста. У мальчиков текст воспрнимается нормально.
Но есть в настоящее время некоторое подмножество студентов, которые вообще не изучали программирование. Для таких студентов графическая нотация может помочь освоить основы.
4. Не конкуренцию, а взаимодополнение.

Автор:  Info21 [ Воскресенье, 22 Апрель, 2012 09:58 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Геннадий Тышов писал(а):
Заменим в цитате термин "верификация" на "исполнения".

Рассуждения о верификации являются уходом от предложения Вам -
Цитата:
Мне сообщили, мол, посмотри.
Предложение, вероятно, связано с Вашим проектом о "спецназе"
Нет, предложение не было с этим связано.

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

Геннадий Тышов писал(а):
в котором алгоритмика является ключевым моментом, но при этом отсутствует выбор средства. Язык ДРАКОН и ИС Дракон являются таким средством. Преподаватель школы меньше Вас знаком с языком ДРАКОН, но выбор сделал раньше.
Нет, ДРАКОН таким средством не является. Утверждаю это по уже многолетнему (как время летит) опыту.

А преподавателями школы я уже, честно скажу, наелся.
Среди них можно найти любителей любой практически дряни, которая плавает в "сфере ИТ".

Автор:  Сергей Прохоренко [ Воскресенье, 22 Апрель, 2012 10:25 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Валерий Лаптев писал(а):
Сергей Прохоренко писал(а):
Валерий Лаптев писал(а):
Блеск! Вывод: Дракон надо всерьез осваивать и давать студентам.

Вовсе не надо:
1. Нет никакой необходимости. Современные языки программирования позволяют даже новичкам обойтись вообще без блок-схем, включая Дракон.

1. Абсолютно не согласен. Обратные графические средства нужны как воздух. Вот сейчас у нас в редакторе - 6 проектов, каждый из которых занимает несколько тысяч строк. По тексту разобраться (вдруг главный пацан свалит ?!) - можно, но не начинающему программеру. А графиченское представление взаимосвязей - сильно облегчает восприятие.


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

1. Схема взаимосвязей в структурном редакторе вынужденно должна быть иерархической: проекты состоят из модулей (объединенных в подсистемы и слои), модули из процедур и функций, процедуры и функции состоят из блоков, которые могут быть вложенными, а блоки содержат ветви алгоритма. Соответственно, связи между высокоуровневыми объектами (от процедур и функций до проектов) не являются просто переходами в программном коде, и, соответственно, не описываются Драконом - он является лишь конкурирующим способом отображения блочной структуры кода и переходов. В структурном редакторе могут быть оба возможных варианта схемы взаимосвязей:
(1) одномерная схема в виде вертикальных списков влияющих и зависимых объектов для выбранного объекта - легко объединяет объекты разных уровней (от проекта до функции или процедуры),
(2) двумерная схема - в ней отображение объектов разного уровня представляет собой трудную творческую задачу, но объекты одного уровня отображаются без особого труда:
Вложение:
MYOB-AccountRight-Plus-v2011-Home-Screen.png
MYOB-AccountRight-Plus-v2011-Home-Screen.png [ 55.32 КБ | Просмотров: 23004 ]


2. В структурном редакторе необходимы собственные средства отображения блочной структуры кода и переходов - Скобка операторного блока и графические элементы для свертки/развертки, буксировки, вставки и удаления ветвей алгоритма в многоветочных конструкциях. Это является развитием структурной парадигмы, а не шагом назад в сторону GOTO, что мы видим в Драконе.

Автор:  ==== [ Воскресенье, 22 Апрель, 2012 12:22 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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


На форуме развитие языка Дракон в части иерархического представления алгоритмов уже было.
Язык расширен добавлением схемы "Дерево", реализовано в ИС Дракон. Смотрите -
http://forum.oberoncore.ru/viewtopic.php?p=22669#p22669
Цитата:
Выпуск от 23.12.2011 помещен здесь - заменен, Файл DragonMax можно использовать для работы со схемой "Дерево" (иерархическое представление алгоритма, программы). Смотрите тему Альтернативный ВИЗУАЛЬНЫЙ СТРУКТУРНЫЙ ПОДХОД К АЛГОРИТМАМ
http://forum.oberoncore.ru/viewtopic.php?p=52854#p52854
http://forum.oberoncore.ru/viewtopic.php?p=68866#p68866

Автор:  TAU [ Воскресенье, 22 Апрель, 2012 22:53 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Сергей Прохоренко писал(а):
4. Создает ненужную конкуренцию гораздо более многообещающему графическому (как и Дракон) средству программирования - структурному (семантическому) редактору.

Ничего не понял.

Семантический редактор - графическое средство?

Где графика?

Валерий, может, Вы поясните?

Автор:  TAU [ Воскресенье, 22 Апрель, 2012 22:54 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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

Ну-ну. Современные IDE включают средства работы с графическим языком UML, будь это Java, C# или С++.
А наиболее продвинутые - средства работы с диаграммами деятельности и диаграммами автоматов UML, и даже - генерацией программ по ним.

Автор:  TAU [ Воскресенье, 22 Апрель, 2012 22:59 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

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

1. Навыки визуального программирования не могут быть вредными, за визуальным программированием - будущее.
2. ГРАФИТ - методология СТРУКТУРНОГО графического программирования, вставляются сразу законченные блоки БЕЗ возможности произвольной передачи управления в общем случае.
3. От GOTO настоящие высокопрофессиональные программисты никогда не пытались "всеми силами избавиться" :!: Настоящие профессионалы всегда писали о случаях, в которых применение GOTO оправданно.

Автор:  Степан Митькин [ Понедельник, 23 Апрель, 2012 02:19 ]
Заголовок сообщения:  Re: Алгоритм уважаемого Дейкстра

Вот мой вариант алгоритма Дейкстры на языке ДРАКОН-Питон.
Постарался выделить основные элементы алгоритма:
1. подготовка
2. основной цикл
- сбор информации о текущем узле
- оценка соседей
- выбор следующего узла
3. выход
Вложение:
dijkstra.png
dijkstra.png [ 106.14 КБ | Просмотров: 22951 ]


Вложения:
dijkstra.drn [32 КБ]
Скачиваний: 651

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/