OberonCore https://forum.oberoncore.ru/ |
|
Цикл Дейкстры https://forum.oberoncore.ru/viewtopic.php?f=30&t=1225 |
Страница 9 из 9 |
Автор: | Info21 [ Пятница, 17 Октябрь, 2014 11:33 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Владимир Паронджанов писал(а): Цитата: Айверсон К.Е. Нотация как средство мышления — Пер. с англ. / Под ред. Эшенхерста. — М.: Мир, 1993. — С. 392-450. — 560 с. — (Лекции лауреатов премии Тьюринга). — ISBN 5-03-002130-2. Но отсюда не следует, что конкретный, скажем, АПЛ -- оптимальная нотация для мышления. |
Автор: | id_ler [ Воскресенье, 19 Октябрь, 2014 13:05 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Между серединой 50-ых и началом 70-ых – это время за которое пришло осознание открытия. До кого-нибудь просто не доходит. До кого-то не доходит из-за отсутствия информации или её намеренного искажения, до кого-то не доходит премия и т.д. Вы обсуждаете разные алгоритм и цикл? Хорошо, когда интернет уже общедоступен: можно просто спросить. |
Автор: | Рыжий [ Суббота, 25 Октябрь, 2014 16:55 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Info21 писал(а): Спасибо, интересно, не знал про книгу 1957. Всё-таки в боксе справа в Википедии говорится, что "появился" в 1964 г. Кобол и лисп "появились" на несколько лет раньше. А в 1964 г. уже шел мутный поток -- включая PL/1 и т.п. (этот поток отражен в книжке Баррона). *** Чувство юмора как у Дейкстры -- признак мощно рефлексирующего мозга. Что, впрочем, в случае Дейкстры доказывать не надо. *** Всё-таки в АПЛ ц.Д. нет. Да, Федор Васильевич, отсутствует в APL конструкция синтаксически подобная циклу Дейкстры. Но, ведь это APL, и рассуждая в рамках данной нотации, понимаешь, что в таком цикле нет необходимости. Допустим есть два массива: массив условий и массив действий, установим между ними некоторое взаимно однозначное соответствие, необязательно тривиальное.. и т.д. Мне кажется. что такие "коммутационные щиты", частным случаем которых выступют ц.Д. или decision tables на APL лепить - проще пареной репы. |
Автор: | Маздайщик [ Среда, 18 Март, 2015 13:39 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Почитал ветку от начала до конца. Возникли две мысли. 1. В начале дискуссии участники требовали реальные примеры использования цикла Дейкстры. Реальный пример у меня есть. Писал как-то я парсер DNS-запросов на Си. Формат его довольно мудрёный и мне не сразу приходила мысль, как сформулировать алгоритм. Записал его через эмулированный цикл Дейкстры (while (true) { if (…) else if (…) else break; }) — сразу стала понятна логика. Затем чутка оптимизировал. Вот что получилось. Код: while (offset < data_length && data[offset] != '\0') { if ((data[offset] & 0xC0) == 0) { uint8_t length = (uint8_t) data[offset]; ++offset; if (offset + length > data_length || dnp + length + 1 > DNS_MAX_DOMAIN_NAME) return false; memcpy(domain_name + dnp, data + offset, length); offset += length; dnp += length; domain_name[dnp] = '.'; ++dnp; } else if ((data[offset] & 0xC0) == 0xC0) { // Компрессия: если установлены оба старших бита, // то пара октетов, состоящая из текущего байта и следующего // образует смещение остатка имени ранее в этом пакете. size_t new_offset = ntohs(*(const uint16_t*)(data + offset)) & ~0xC000; if (new_offset >= *data_offset) return false; if (end_of_first_segment == 0) end_of_first_segment = offset + sizeof(uint16_t); offset = new_offset; } else break; } Вывод: если некий алгоритм сложный, то сначала стоит попробовать сформулировать его через алгоритм Дейкстры, а потом оптимизировать. 2. Утверждается, что первый язык, реализующий цикл Дейкстры — это Оберон-07. Поправка: первый императивный язык. Ведь в языках функционального программирования (особенно pattern-matching-языки типа Хаскеля, Рефала или Эрланга) цикл Дейкстры реализуется просто и естественно. Если цикл WHILE это func f(x) = if c(x) then f(x’) else y, то ЦД — func f(x) = if c1(x) then f(x') elif c2(x) then f(x'') … else y. Ведь конструкции типа if-elif-else есть практически во всех языках программирования. |
Автор: | Info21 [ Среда, 18 Март, 2015 17:36 ] |
Заголовок сообщения: | Re: Цикл Дейкстры |
Маздайщик писал(а): Почитал ветку от начала до конца. Возникли две мысли. Спасибо за очередной пример. Их нужно постоянно новые давать, по возможности. В ФЯ все-таки эмуляция. Так же легко он эмулируется в старом Обероне/КП. |
Страница 9 из 9 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |