OberonCore https://forum.oberoncore.ru/ |
|
Цикл Дейкстры https://forum.oberoncore.ru/viewtopic.php?f=30&t=1225 |
Страница 8 из 9 |
Автор: | Trurl [ Понедельник, 14 Декабрь, 2009 21:37 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Илья Ермаков писал(а): Детерминированный вариант ЦД есть оксюморон. |
Автор: | Илья Ермаков [ Понедельник, 14 Декабрь, 2009 21:40 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Тогда этот оксюморон from Oberon-07, не так ли? |
Автор: | Info21 [ Вторник, 15 Декабрь, 2009 09:59 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Trurl писал(а): Илья Ермаков писал(а): Детерминированный вариант ЦД есть оксюморон. |
Автор: | Евгений Темиргалеев [ Среда, 14 Сентябрь, 2011 20:52 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Очередной раз убедился в полезности: - начал городить вложенные WHILE/REPEAT, подзапутался - вспомнил про ЦД и .. почти сам собой получился "двухтактный" конечный автомат. |
Автор: | Сергей Губанов [ Среда, 14 Сентябрь, 2011 21:12 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Евгений Темиргалеев писал(а): Очередной раз убедился в полезности: Э-э-э, Вы поосторожнее, ЦД существует сам по себе, а не вместо вложенных WHILE/REPEAT. То есть существуют алгоритмы описываемые ЦД, а есть (другие) алгоритмы описываемые вложенными WHILE/REPEAT.
- начал городить вложенные WHILE/REPEAT, подзапутался - вспомнил про ЦД и .. почти сам собой получился "двухтактный" конечный автомат. |
Автор: | Владислав Жаринов [ Среда, 14 Сентябрь, 2011 21:32 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Сергей Губанов писал(а): ... Т.е. предполагается, что не каждый алгоритм можно описать через ЦД? Из чего это следует?
То есть существуют алгоритмы описываемые ЦД, а есть (другие) алгоритмы описываемые вложенными WHILE/REPEAT. |
Автор: | Valery Solovey [ Среда, 14 Сентябрь, 2011 22:38 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Потому что ЦД - это цикл. Им не описать, скажем, процедуру. Цикл заключает в себе последовательность команд. В частном случае одной из команд будет цикл. В ещё более частном случае внутренний цикл можно будет вынести параллельной веткой внешнего цикла. |
Автор: | Сергей Губанов [ Среда, 14 Сентябрь, 2011 23:06 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Драконограф писал(а): Сергей Губанов писал(а): ... Т.е. предполагается, что не каждый алгоритм можно описать через ЦД? Из чего это следует?То есть существуют алгоритмы описываемые ЦД, а есть (другие) алгоритмы описываемые вложенными WHILE/REPEAT. Приведу пример когда использование ЦД не обосновано. Будем парсить вложенные комментарии: (* уровень1 (* уровень2 (* уровень3 *) уровень2 *) уровень1 *). Конечно это можно сделать с помощью ЦД. А можно сделать проще и эффективнее с помощью двух простых циклов. Внешний цикл проверяет не стал ли уровень вложенности равен нулю, а внутренний цикл делает линейный поиск завершения текущего или начала ещё более вложенного комментария. Всё! Чистая факторизация на два элементарных цикла. |
Автор: | Info21 [ Четверг, 15 Сентябрь, 2011 11:24 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Сергей Губанов писал(а): Приведу пример когда использование ЦД не обосновано. Будем парсить вложенные комментарии: (* уровень1 (* уровень2 (* уровень3 *) уровень2 *) уровень1 *). Конечно это можно сделать с помощью ЦД. ... Четто подозревается, что и тут ЦД проще.Сергей Губанов писал(а): может оказаться, что в нём какая-то ветка будет крутится много раз подряд Ну и пусть себе крутится. Зато строить и верифицировать ЦД -- легко и приятно. И единообразно. Возникнут реальные проблемы с производительностью -- тогда и будем курочить. ЦД -- это легкость развития. Задачи, мы знаем, во времени меняются. Любая оптимизация -- включая "простые вложенные циклы" -- неустойчивая штука, хрупкая. А где хрупко, там можно и порезаться. |
Автор: | Владислав Жаринов [ Четверг, 15 Сентябрь, 2011 11:31 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Обоснованно/необоснованно - это конечно. Цикл Дейкстры - это, по большому счёту, распознаватель для выбора одного из тел своих ветвей в качестве "следующего знака для текста", которым можно представить развёртку исполнения алгоритма. Другой вопрос - что да, выбор в виде ЦД-шапки, наверное, м.б. сконструирован не всегда внешне оптимально по сравнению с обычным решением через следования/ветвления/обычные циклы (можно посмотреть этот пример "ухода от гнезда")... однако Фёдор Васильевич уже привёл определённые резоны "за" в общем случае. |
Автор: | Илья Ермаков [ Четверг, 15 Сентябрь, 2011 12:28 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
2 Info21: С другой стороны, если я естественным образом разложил на внешний и вложенный цикл, я могу вложенный упрятать в процедуру (я обычно так и делаю, избегаю вложенных циклов, за исключением многомерных переборов). А такая декомпозиция часто выглядит проще. |
Автор: | Info21 [ Четверг, 15 Сентябрь, 2011 15:52 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Илья Ермаков писал(а): я могу вложенный упрятать в процедуру (я обычно так и делаю, избегаю вложенных циклов, за исключением многомерных переборов). Ну да. На 5-классниках мы это прошли А такая декомпозиция часто выглядит проще. http://www.inr.ac.ru/~info21/troitsklic ... etap10.htm С другой стороны, в главе 1.9 АиСД, где про поиск слов, видно, как приходится переходить к циклу Дейкстры при настоящей (идейной) оптимизации алгоритма -- в отличие от тривиальной тыр-пыр-перестановочной. |
Автор: | Рыжий [ Среда, 15 Октябрь, 2014 01:32 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Давайте снова поднимем дело Дейкстры. На этот раз о его цикле. (Раньше, если кто не помнит, рассматривалось дело о goto). И снова ведь наврано! И опять всплывает Дейкстра. Вот что сказано в Википедии: Цитата: Хотя цикл Дейкстры был изобретён ещё в 1970-х годах, специальных конструкций для его создания в языках программирования не содержится. Единственным исключением стал недавно созданный Оберон-07 — первый реальный язык программирования, явно поддерживающий цикл с несколькими охраняемыми ветвями. Впрочем, цикл Дейкстры может быть без больших затруднений смоделирован с помощью традиционных конструкций структурных языков программирования. В APL герундий был, когда Дейкстра еще пешком под стол ходил. Т.е. в середине 50-х, а цикл дейкстры появился в середине 70-х. Чувствуете, куда я клоню? Я обещал Дейкстру на чистую воду вывести... |
Автор: | ==== [ Среда, 15 Октябрь, 2014 01:38 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Прошу уточнить. В каком году APL появился? Моло вероятно, что бы существовал в середине 50-х. |
Автор: | Info21 [ Среда, 15 Октябрь, 2014 16:12 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
В середине 50-х был только фортран. Потом появились кобол и лисп. АПЛ -- в последовавшем мутном потоке изобретательства. Игрушка забавная, тренажер такой, почему нет -- между латынью и спортивным программированием. Вместе с дозой функционального программирования -- лично я бы посоветовал для продвинутых. Только где там ц.Д.? Надо бы пример. |
Автор: | Рыжий [ Четверг, 16 Октябрь, 2014 00:19 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Википедия: "Язык APL был разработан Кеном Айверсоном (преподававшем тогда в Гарвардском университете), как система обозначений для описания вычислений. В 1957 выходит его книга «A Program Language»,[5] в которой эта нотация была описана. В 1960 Айверсон продолжает работу над APL в IBM. Здесь этот язык использовался для описания машинной архитектуры.[6][7]" ---------------------------------------------------------------------------------- http://www.vspu.ac.ru/~chul/dijkstra/ Цитата: Дейкстра обладал незаурядным чувством юмора и едко критиковал неудавшиеся труды программистов. Однажды, к примеру, он назвал Фортран (FORTRAN) <младенческим расстройством> с двадцатилетним стажем, а APL - языком будущего для программистской техники прошлого. ---------------------------------------------------------------------------------- |
Автор: | Info21 [ Четверг, 16 Октябрь, 2014 05:08 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Спасибо, интересно, не знал про книгу 1957. Всё-таки в боксе справа в Википедии говорится, что "появился" в 1964 г. Кобол и лисп "появились" на несколько лет раньше. А в 1964 г. уже шел мутный поток -- включая PL/1 и т.п. (этот поток отражен в книжке Баррона). *** Чувство юмора как у Дейкстры -- признак мощно рефлексирующего мозга. Что, впрочем, в случае Дейкстры доказывать не надо. *** Всё-таки в АПЛ ц.Д. нет. |
Автор: | Рыжий [ Четверг, 16 Октябрь, 2014 19:25 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Я сдулся, но не окончательно. В J-то герундий есть. Но это как-то все не то. Хочется большей, "построковой" выразительности. Конкретно с APL давно не возился, а сегодня поставил NARS (бесплатная версия под виндовс) и решил проверить свои смутные идеи по этому поводу. Но там придется разобраться со средой. По-моему ц.Д. в APL есть, "должон быть", но ручаться за это трудно. P.S. В наличии не только книга 1957 года. Имеется еще и Тьюринговская премия за это самое дело. |
Автор: | Владимир Паронджанов [ Четверг, 16 Октябрь, 2014 20:50 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Передо мной лежит книга: Лекции лауреатов премии Тьюринга за первые двадцать лет 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).
|
Автор: | Владислав Жаринов [ Пятница, 17 Октябрь, 2014 08:30 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Рыжий писал(а): ... По-моему ц.Д. в APL есть, "должон быть", но ручаться за это трудно. Ага, тогда к списку здесь надо будет добавить... или хотите сказать, что тогда это надо будет называть "циклом Айверсона"?..
... |
Страница 8 из 9 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |