DRAKON.SU

Текущее время: Четверг, 20 Июнь, 2019 00:35

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




Начать новую тему Ответить на тему  [ Сообщений: 19 ] 
Автор Сообщение
СообщениеДобавлено: Понедельник, 25 Июнь, 2012 00:24 

Зарегистрирован: Понедельник, 09 Ноябрь, 2009 17:29
Сообщения: 904
Откуда: Россия, Питер
Статья в Википедии.

В очередной раз посравнивать : )
Вложение:
avl_t.png
avl_t.png [ 72.3 КБ | Просмотров: 13516 ]

Вложение:
avl_d.png
avl_d.png [ 92.65 КБ | Просмотров: 13516 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 25 Июнь, 2012 14:49 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
Ну, логика процесса нагляднее в схеме, пожалуй. Но цель его - реструктурирование в некоем пространстве данных (адресном). И для её понимания разобраться в порядке действий м.б. мало - Илья уже говорил: viewtopic.php?p=43186#p43186. А это другие типы схем - в частности, как у Лаврова или в проекте Оберон использованы...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 25 Июнь, 2012 22:14 

Зарегистрирован: Воскресенье, 09 Март, 2008 22:38
Сообщения: 342
Все очевидно - схема гораздо нагляднее


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

Зарегистрирован: Понедельник, 05 Июнь, 2006 09:49
Сообщения: 28
Откуда: Ленинград, Емельянов Алексей Николаевич
TAU писал(а):
Все очевидно - схема гораздо нагляднее

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


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 140
Откуда: Троицк, Москва
Видно, как begin-end замусоривают текст.
В значительной степени обессмысливают индентацию.

---

Элементарно:
здесь просто не хватает одного промежуточного уровня абстракции.
Типа псевдокода.

Сей факт лучше заметен на диаграмме, если смотреть на неё издалека -- но это по причине плохой структуры кода, испорченной begin-end'ами и неиспользованием белого пространства для визуальногоо разделения частей.


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

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
Info21 писал(а):
Видно, как begin-end замусоривают текст.
В значительной степени обессмысливают индентацию.
Да, конечно.

Info21 писал(а):
Элементарно:
здесь просто не хватает одного промежуточного уровня абстракции.
Типа псевдокода.
Вы имеете в виду, как сделано в "Проекте Оберон" при разборе некоторых команд (скажем, Edit, что можно видеть здесь: viewtopic.php?p=73037#p73037)?

А м.б. типа замены и BEGIN-END, и остальных "маршрутных" ключевых слов структурными скобками, как у Прохоренко?..

Да, и возникает вопрос о совмещении разных уровней. А если так:
Владислав Жаринов в viewtopic.php?p=72968#p72968 писал(а):
...
При оптимизации представления нужно учесть также иерархию по степени формализации. В связи с этим очевидно, что возможны разные варианты построения по порядку прохождения иерархии - "от качественного" или "от программного". В первом случае организуется связно текст наименее формальный, а каждое устрожение (лежащее уровнем ниже по иерархии) представляется как фрагменты, относимые к участкам вышележащего уровня. В втором случае, напротив, связен более формальный текст, а фрагментарны его непосредственное ослабление и формализации иных менее строгих уровней (лежащих выше по иерархии).

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

Примерно так. Интересны будут другие мнения.

И ещё:
Info21 писал(а):
...
Сей факт лучше заметен на диаграмме, если смотреть на неё издалека -- но это по причине плохой структуры кода, испорченной begin-end'ами и неиспользованием белого пространства для визуальногоо разделения частей.

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 26 Июнь, 2012 11:35 
Аватара пользователя

Зарегистрирован: Пятница, 25 Сентябрь, 2009 13:10
Сообщения: 46
Откуда: Tel-Aviv
Пример алгоритма на Драконе плох.
  1. Как упоминалось выше, данная диаграмма довольно громоздка
  2. Необходимо избавиться от программистских конструкций. Ведь алгоритм должен быть понятен любому (даже не программисту), не так ли?
  3. Неясно какие преимущества Дракона проявляются при данной записи алгоритма


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 26 Июнь, 2012 12:04 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
2. От каких программистских? От записей и указателей? Так тогда мы возвращаемся к качественным илллюстрациям {большого/малого; правого/левого} вращений из ВП-статьи. Они и правда больше дают для понимания решения задачи... :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 26 Июнь, 2012 12:10 
Аватара пользователя

Зарегистрирован: Пятница, 25 Сентябрь, 2009 13:10
Сообщения: 46
Откуда: Tel-Aviv
Владислав Жаринов писал(а):
2. От каких программистских? От записей и указателей? Так тогда мы возвращаемся к качественным илллюстрациям {большого/малого; правого/левого} вращений из ВП-статьи. Они и правда больше дают для понимания решения задачи... :)
От привязки к конкретной реализации на Паскале.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 26 Июнь, 2012 12:12 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
Т.е. перейти к "родному" прогязыку (псевдокоду)?.. А как со структурами данных?..


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

Зарегистрирован: Пятница, 25 Сентябрь, 2009 13:10
Сообщения: 46
Откуда: Tel-Aviv
Владислав Жаринов писал(а):
Т.е. перейти к "родному" прогязыку (псевдокоду)?.. А как со структурами данных?..
Разве в Драконе никак не решена проблема записи структур данных?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 26 Июнь, 2012 12:26 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
Ну как это... можно вот как здесь...
Изображение
А исходя из того, что данные равноправны с операциями и самостоятельно описываются - можно и как здесь...
Изображение
Вы что-то такое имели в виду?..


Последний раз редактировалось Владислав Жаринов Пятница, 29 Июнь, 2012 18:20, всего редактировалось 2 раз(а).

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

Зарегистрирован: Воскресенье, 06 Апрель, 2008 14:43
Сообщения: 1657
TAU писал(а):
Все очевидно - схема гораздо нагляднее

Не согласен
http://sharaga.org/index.php?showtopic=1953&view=findpost&p=54960 MrYuran 27.1.2012, 20:01
Цитата:
Еще одно коренное отличие - это то, что в иконах вписывается непосредственно код, а комментарии - внутри, видны при выделений иконы.
В ИС Дракон Тышова - наоборот, снаружи человеческий язык, а внутри расписание код.
И это, по-моему, правильнее.
У Ильченко Эдуард описания предметной области вообще нет.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 28 Июнь, 2012 21:03 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 112
Откуда: Беларусь, Минск
Мне так кажется, что Ваше утверждение не имеет отношения к сообщению, на которое Вы отвечали из-за отсутствия прямой логической связи между ними.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 29 Июнь, 2012 18:26 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
Ну, если отвлечься от "победной реляционности" - то зерно в том, что разные уровни формализации есть. И надо для удобства между ними переключаться. А также и показывать совмещённо - как я и делаю чаще всего (с "формальными комментариями" и/или отдельными блоками). И тут также выявляется и разная "доведённость" в различных частиях описания.
Описание предметки (неимперативная часть формализации задачи) к импер-языку, ессно не относится. Можно описывать по-разному - как раз выше примеры тому.. И там тоже разная формализованность будет...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 24 Август, 2012 15:09 

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

Здесь анализируют Ваш алгоритм АВЛ-дерево
http://oberspace.dyndns.org/index.php/topic,275.0.html


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 25 Август, 2012 14:00 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 1442
И очень быстро переходят на сам язык... прямо со второго поста...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 05 Сентябрь, 2014 23:13 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 4232
Откуда: Москва
Поздравляю Эдуарда Владимировича Ильченко, создавшего эту важную тему и инициировавшего обсуждение.

Эта инициатива имела важное продолжение. http://persons.iis.nsk.su/files/persons ... insert.pdf

Прочитав данное обсуждение В.И. Шелехов вдохновился, получил грант Российского фонда фундаментальных исследований и написал статью:
Цитата:
В.И. Шелехов
Предикатная программа вставки в АВЛ-дерево


Операции с АВЛ-деревьями компактно и элегантно представляются в языках функционального программирования, см. например [4, 5].

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

В рамках предикатного программирования делается попытка, возможно впервые, построения таких алгоритмов (рекурсивного и нерекурсивного) вставки в АВЛ-дерево, чтобы применением оптимизирующих трансформаций получить эффективные императивные программы, подобных представленным в [1–3].


Цитата:
Заключение

Предпосылкой появления данной работы стала дискуссия на форуме [3] о том, какая из программ вставки в АВЛ-дерево лучше: на языке Оберон или графическом языке Дракон [6].

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

Тем не менее, программа не выглядит проще. Причина – исходная сложность императивной программы.

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

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

В описании библиотеки libavl [2] используется однократный указатель, однако при этом дополнительно поддерживается указатель на предыдущую вершину-отца.

Как следствие, алгоритм получается более громоздким и менее эффективным в сравнении с приведенным в настоящей работе.

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

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

Работа выполнена при поддержке РФФИ, грант № 12-01-00686.

Литература

1. Википедия. АВЛ-дерево. http://ru.wikipedia.org/wiki/%D0%90%D0% ... 0%B2%D0%BE

2. Ben Pfaff. GNU libavl 2012. An Introduction to Binary Search Trees and Balanced Trees. ftp://ftp.gnu.org/pub/gnu/avl/avl-2.0.2.pdf.gz

3. АВЛ-дерево. Алгоритм добавления вершины. viewtopic.php?f=78&t=4003

4. R. Hettler, D. Nazareth, F. Regensburger, O. Slotosch. AVL trees revisited: A case study in Spectrum. LCNS, vol. 1009, 1995, pp 128-147.

5. AVL Tree in Haskell. https://gist.github.com/gerard/109729

6. Паронджанов В. Д. Язык ДРАКОН. Краткое описание. — М., 2009. — 124 с.

7. Карнаухов Н.С., Першин Д.Ю., Шелехов В.И. Язык предикатного программирования P. Версия 0.12 — Новосибирск, 2013. — 52с. http://persons.iis.nsk.su/files/persons ... lang12.pdf

8. Каблуков И. В. Реализация оптимизирующих трансформаций предикатных программ // XIV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям.  Томск, 2013.  7с. http://conf.nsc.ru/files/conferences/ym ... 69/177104/Опт.%20трансформации.pdf

Читать дальше ...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 07 Сентябрь, 2014 12:43 

Зарегистрирован: Понедельник, 09 Август, 2010 22:28
Сообщения: 128
Нет здесь никакого улучшения наглядности: просто код записали в квадратиках. Я бы и текстом прочитал.

Чтобы понять работу алгоритма нужно описать, что дано на человеческом языке, нарисовав АВЛ-дерево. И последовательно писать, как оно изменяется на каждом этапе. Тогда код все можно будет понять.


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

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


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

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


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

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