OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 19 Сентябрь, 2019 14:03

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




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

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


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

Зарегистрирован: Суббота, 06 Июнь, 2009 07:52
Сообщения: 329
Между серединой 50-ых и началом 70-ых – это время за которое пришло осознание открытия. До кого-нибудь просто не доходит. До кого-то не доходит из-за отсутствия информации или её намеренного искажения, до кого-то не доходит премия и т.д. Вы обсуждаете разные алгоритм и цикл? Хорошо, когда интернет уже общедоступен: можно просто спросить.


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

Зарегистрирован: Вторник, 05 Январь, 2010 21:31
Сообщения: 1101
Откуда: Харків, Данилівка
Info21 писал(а):
Спасибо, интересно, не знал про книгу 1957.

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

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

***

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

***

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

Да, Федор Васильевич, отсутствует в APL конструкция синтаксически подобная циклу Дейкстры. Но, ведь это APL, и рассуждая в рамках данной нотации, понимаешь, что в таком цикле нет необходимости. Допустим есть два массива: массив условий и массив действий, установим между ними некоторое взаимно однозначное соответствие, необязательно тривиальное.. и т.д. :D Мне кажется. что такие "коммутационные щиты", частным случаем которых выступют ц.Д. или decision tables на APL лепить - проще пареной репы.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Цикл Дейкстры
СообщениеДобавлено: Среда, 18 Март, 2015 13:39 

Зарегистрирован: Суббота, 02 Февраль, 2013 16:19
Сообщения: 16
Почитал ветку от начала до конца. Возникли две мысли.

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 есть практически во всех языках программирования.


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

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

Спасибо за очередной пример. Их нужно постоянно новые давать, по возможности.

В ФЯ все-таки эмуляция. Так же легко он эмулируется в старом Обероне/КП.


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

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


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

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


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

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