OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Понедельник, 11 Декабрь, 2017 08:40

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




Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1 ... 5, 6, 7, 8, 9  След.
Автор Сообщение
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 21:37 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1010
Илья Ермаков писал(а):
Детерминированный вариант ЦД

есть оксюморон.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Понедельник, 14 Декабрь, 2009 21:40 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 8880
Откуда: Россия, Орёл
Тогда этот оксюморон from Oberon-07, не так ли?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Вторник, 15 Декабрь, 2009 09:59 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7724
Откуда: Троицк, Москва
Trurl писал(а):
Илья Ермаков писал(а):
Детерминированный вариант ЦД

есть оксюморон.
Да ла-а-адно уж... до этаких высот дорасти еще нужно...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 14 Сентябрь, 2011 20:52 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4466
Откуда: Россия, Орёл
Очередной раз убедился в полезности:
- начал городить вложенные WHILE/REPEAT, подзапутался
- вспомнил про ЦД и .. почти сам собой получился "двухтактный" конечный автомат.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 14 Сентябрь, 2011 21:12 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Евгений Темиргалеев писал(а):
Очередной раз убедился в полезности:
- начал городить вложенные WHILE/REPEAT, подзапутался
- вспомнил про ЦД и .. почти сам собой получился "двухтактный" конечный автомат.
Э-э-э, Вы поосторожнее, ЦД существует сам по себе, а не вместо вложенных WHILE/REPEAT. То есть существуют алгоритмы описываемые ЦД, а есть (другие) алгоритмы описываемые вложенными WHILE/REPEAT.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 14 Сентябрь, 2011 21:32 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Сергей Губанов писал(а):
...
То есть существуют алгоритмы описываемые ЦД, а есть (другие) алгоритмы описываемые вложенными WHILE/REPEAT.
Т.е. предполагается, что не каждый алгоритм можно описать через ЦД? Из чего это следует?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 14 Сентябрь, 2011 22:38 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 14 Сентябрь, 2011 23:06 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Драконограф писал(а):
Сергей Губанов писал(а):
...
То есть существуют алгоритмы описываемые ЦД, а есть (другие) алгоритмы описываемые вложенными WHILE/REPEAT.
Т.е. предполагается, что не каждый алгоритм можно описать через ЦД? Из чего это следует?
Не алгоритм, а цикл. Нет, такого не предполагается. Дело в другом. Я думаю по аналогии с квантовой механикой, что есть циклы допускающие факторизацию, а есть циклы запутанные (в к. м. это строгий научный термин). Вот ЦД - для запутанных, то есть когда на каждом шаге цикла будет переход каждый раз на разную ветку. А ежели писать ЦД просто от балды, то может оказаться, что в нём какая-то ветка будет крутится много раз подряд, это может говорить о том, что на самом-то деле этот большой цикл может быть подвергнут декомпозиции, скажем, на два совсем простых цикла с вложением одного в другой.

Приведу пример когда использование ЦД не обосновано. Будем парсить вложенные комментарии: (* уровень1 (* уровень2 (* уровень3 *) уровень2 *) уровень1 *). Конечно это можно сделать с помощью ЦД. А можно сделать проще и эффективнее с помощью двух простых циклов. Внешний цикл проверяет не стал ли уровень вложенности равен нулю, а внутренний цикл делает линейный поиск завершения текущего или начала ещё более вложенного комментария. Всё! Чистая факторизация на два элементарных цикла.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 15 Сентябрь, 2011 11:24 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7724
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Приведу пример когда использование ЦД не обосновано. Будем парсить вложенные комментарии: (* уровень1 (* уровень2 (* уровень3 *) уровень2 *) уровень1 *). Конечно это можно сделать с помощью ЦД. ...
Четто подозревается, что и тут ЦД проще.

Сергей Губанов писал(а):
может оказаться, что в нём какая-то ветка будет крутится много раз подряд
Ну и пусть себе крутится.
Зато строить и верифицировать ЦД -- легко и приятно. И единообразно.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 15 Сентябрь, 2011 11:31 

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 15 Сентябрь, 2011 12:28 
Модератор
Аватара пользователя

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 15 Сентябрь, 2011 15:52 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7724
Откуда: Троицк, Москва
Илья Ермаков писал(а):
я могу вложенный упрятать в процедуру (я обычно так и делаю, избегаю вложенных циклов, за исключением многомерных переборов).
А такая декомпозиция часто выглядит проще.
Ну да. На 5-классниках мы это прошли :)
http://www.inr.ac.ru/~info21/troitsklic ... etap10.htm

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 15 Октябрь, 2014 01:32 

Зарегистрирован: Вторник, 05 Январь, 2010 21:31
Сообщения: 1101
Откуда: Харків, Данилівка
Давайте снова поднимем дело Дейкстры. На этот раз о его цикле. (Раньше, если кто не помнит, рассматривалось дело о goto). И снова ведь наврано! И опять всплывает Дейкстра. Вот что сказано в Википедии:
Цитата:
Хотя цикл Дейкстры был изобретён ещё в 1970-х годах, специальных конструкций для его создания в языках программирования не содержится. Единственным исключением стал недавно созданный Оберон-07 — первый реальный язык программирования, явно поддерживающий цикл с несколькими охраняемыми ветвями. Впрочем, цикл Дейкстры может быть без больших затруднений смоделирован с помощью традиционных конструкций структурных языков программирования.

В APL герундий был, когда Дейкстра еще пешком под стол ходил. Т.е. в середине 50-х, а цикл дейкстры появился в середине 70-х. Чувствуете, куда я клоню? Я обещал Дейкстру на чистую воду вывести...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 15 Октябрь, 2014 01:38 

Зарегистрирован: Воскресенье, 06 Апрель, 2008 14:43
Сообщения: 557
Прошу уточнить. В каком году APL появился?
Моло вероятно, что бы существовал в середине 50-х.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 15 Октябрь, 2014 16:12 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7724
Откуда: Троицк, Москва
В середине 50-х был только фортран.
Потом появились кобол и лисп.

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

Только где там ц.Д.? Надо бы пример.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 16 Октябрь, 2014 00:19 

Зарегистрирован: Вторник, 05 Январь, 2010 21:31
Сообщения: 1101
Откуда: Харків, Данилівка
Википедия:
"Язык APL был разработан Кеном Айверсоном (преподававшем тогда в Гарвардском университете), как система обозначений для описания вычислений. В 1957 выходит его книга «A Program Language»,[5] в которой эта нотация была описана. В 1960 Айверсон продолжает работу над APL в IBM. Здесь этот язык использовался для описания машинной архитектуры.[6][7]"
----------------------------------------------------------------------------------
http://www.vspu.ac.ru/~chul/dijkstra/

Цитата:
Дейкстра обладал незаурядным чувством юмора и едко критиковал неудавшиеся труды
программистов. Однажды, к примеру, он назвал Фортран (FORTRAN) <младенческим расстройством> с двадцатилетним стажем, а APL - языком будущего для программистской техники прошлого.

----------------------------------------------------------------------------------


Последний раз редактировалось Рыжий Четверг, 16 Октябрь, 2014 02:37, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 16 Октябрь, 2014 05:08 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7724
Откуда: Троицк, Москва
Спасибо, интересно, не знал про книгу 1957.

Всё-таки в боксе справа в Википедии говорится, что "появился" в 1964 г.

Кобол и лисп "появились" на несколько лет раньше.
А в 1964 г. уже шел мутный поток -- включая PL/1 и т.п. (этот поток отражен в книжке Баррона).

***

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

***

Всё-таки в АПЛ ц.Д. нет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 16 Октябрь, 2014 19:25 

Зарегистрирован: Вторник, 05 Январь, 2010 21:31
Сообщения: 1101
Откуда: Харків, Данилівка
Я сдулся, но не окончательно. В J-то герундий есть. Но это как-то все не то. Хочется большей, "построковой" выразительности. Конкретно с APL давно не возился, а сегодня поставил NARS (бесплатная версия под виндовс) и решил проверить свои смутные идеи по этому поводу. Но там придется разобраться со средой. По-моему ц.Д. в APL есть, "должон быть", но ручаться за это трудно. :D
P.S. В наличии не только книга 1957 года. Имеется еще и Тьюринговская премия за это самое дело.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Четверг, 16 Октябрь, 2014 20:50 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 332
Откуда: Москва
Передо мной лежит книга: Лекции лауреатов премии Тьюринга за первые двадцать лет 1966-1985. В ней опубликована (в частности) Тьюринговская лекция К. Айверсона. Он получил премию в 1979 году.

Цитата:
Айверсон К.Е. Нотация как средство мышления — Пер. с англ. / Под ред. Эшенхерста. — М.: Мир, 1993. — С. 392-450. — 560 с. — (Лекции лауреатов премии Тьюринга). — ISBN 5-03-002130-2.


Цитата:
1979

Нотация как средство мышления.
К.Е. Айверсон.
Исследовательский центр Томаса Уотсона фирмы IBM


======================
https://ru.wikipedia.org/wiki/%D0%90%D0 ... 0%B5%D1%82
Цитата:
Кеннет Юджин Айверсон (англ. Kenneth Eugene Iverson; 17 декабря 1920 — 19 октября 2004, Канада) — канадский учёный в области теории вычислительных систем, программист, автор языка программирования APL, получивший за эту разработку в 1979 году премию Тьюринга Ассоциации компьютерной техники (ACM).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Пятница, 17 Октябрь, 2014 08:30 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Рыжий писал(а):
... По-моему ц.Д. в APL есть, "должон быть", но ручаться за это трудно. :D
...
Ага, тогда к списку здесь надо будет добавить... или хотите сказать, что тогда это надо будет называть "циклом Айверсона"?.. :)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 165 ]  На страницу Пред.  1 ... 5, 6, 7, 8, 9  След.

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


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

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


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

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