OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Понедельник, 23 Апрель, 2018 00:57

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




Начать новую тему Ответить на тему  [ Сообщений: 12 ] 
Автор Сообщение
СообщениеДобавлено: Среда, 28 Март, 2018 12:35 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 655
Откуда: Казань
Слово недетерминированный можно было не писать, так как цикл Дейкстры, который ввел Дейкстра, он по определению недетерминированный. В языке Оберон-07 есть цикл Дейкстры, но он детерминированный, то есть он не совсем цикл Дейкстры. Ну ладно, вопрос в том, как реализовать настояций цикл Дейкстры на Оберон-07.
Я реализовал один вариант (вы его можете приспособить под свои нужды, если замените существующие модули Console и Random на свои):
Код:
MODULE Nondeterminate;

  IMPORT
    con := Console,
    Random;

  CONST
    MAX_NUM = 10;

  VAR
    permutation: ARRAY MAX_NUM OF INTEGER;

  PROCEDURE RandomPermutation(n: INTEGER);
  VAR
    i: INTEGER;
    j: INTEGER;
    rnd: INTEGER;
    choosen: ARRAY MAX_NUM OF BOOLEAN;
  BEGIN
    FOR i := 0 TO n - 1 DO
      choosen[j] := FALSE;
    END;
    FOR i := n TO 1 BY -1 DO
      IF i # 1 THEN       
        rnd := Random.Random() MOD i;
      ELSE
        rnd := 0;
      END;
      j := 0;
      WHILE choosen[j] OR (rnd # 0) DO
        IF ~choosen[j] THEN
          rnd := rnd - 1;
        END;
        j := j + 1;
      END;
      choosen[j] := TRUE;
      permutation[n - i] := j;
    END;
  END RandomPermutation;

  PROCEDURE PrintPermutation(n: INTEGER);
  VAR
    i: INTEGER;
  BEGIN
    FOR i := 0 TO n - 1 DO
      con.Int(permutation[i]); con.Str(" ");
    END;
    con.Ln;
  END PrintPermutation;

  PROCEDURE Test1(n: INTEGER);
  BEGIN
    WHILE n MOD 2 = 0 DO
      con.Int(2); con.Str(" ");
      n := n DIV 2;
    ELSIF n MOD 3 = 0 DO
      con.Int(3); con.Str(" ");
      n := n DIV 3;
    ELSIF n MOD 5 = 0 DO
      con.Int(5); con.Str(" ");
      n := n DIV 5;
    END;
    con.Ln;
  END Test1; 
 
  PROCEDURE Test2(n: INTEGER);
  VAR
    step: INTEGER;
    continue: BOOLEAN;
  BEGIN
    continue := TRUE;
    WHILE continue DO
      RandomPermutation(3);
      continue := FALSE;
      step := 0;
      WHILE (step < 3) & ~continue DO
        continue := TRUE;
        IF (permutation[step] = 0) & (n MOD 2 = 0) THEN
          con.Int(2); con.Str(" ");
          n := n DIV 2;
        ELSIF (permutation[step] = 1) & (n MOD 3 = 0) THEN
          con.Int(3); con.Str(" ");
          n := n DIV 3;
        ELSIF (permutation[step] = 2) & (n MOD 5 = 0) THEN
          con.Int(5); con.Str(" ");
          n := n DIV 5;
        ELSE
          continue := FALSE;
          step := step + 1;
        END;
      END;
    END;
    con.Ln;
  END Test2;

BEGIN
  Random.Randomize();
  Test1(466560000);
  Test2(466560000);
END Nondeterminate.

Test1 раскладывает число на множители 2, 3 и 5, используя встроенный цикл Дейкстры, и в результате получается: 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 5 5 5 5.
Test2 эмулирует недетерминированный цикл Дейкстры и в результате получается примерно такая последовательность: 3 2 3 2 2 5 3 5 3 3 5 5 2 2 3 2 2 2 2 2.

Может быть у кого-то будут идеи как можно лучше эмулировать недетерминированность.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 28 Март, 2018 15:14 

Зарегистрирован: Четверг, 08 Май, 2008 19:13
Сообщения: 610
Откуда: Киев
Было бы зачем

Код:
  Branches = RECORD
    b: ARRAY MAX_NUM OF INTEGER;
    i, j: INTEGER
  END;
 
  PROCEDURE Init(VAR b: Branches);
  BEGIN
    b.i := 0;
    b.j := 0
  END Init;
 
  PROCEDURE Put(VAR b: Branches; case: INTEGER; cond: BOOLEAN): INTEGER;
  BEGIN
    ASSERT(case = b.j);
    IF cond THEN
      b.b[b.i] := case;
      INC(b.i)
    END;
    INC(b.j);
    RETURN ORD(cond)
  END Put;
 
  PROCEDURE Rand(VAR b: Branches): INTEGER;
  VAR i: INTEGER;
  BEGIN
    i := Random.Random() MOD b.i;
    Init(b);
    RETURN i
  END Rand;
 
  PROCEDURE Test3(n: INTEGER);
  VAR branches: Branches;
  BEGIN
    Init(b);
   
    WHILE Put(branches, 0, n MOD 2 = 0)
        + Put(branches, 1, n MOD 3 = 0)
        + Put(branches, 2, n MOD 5 = 0) > 0
    DO
      CASE Rand(branches) OF
        0:
        con.Int(2); con.Str(" ");
        n := n DIV 2
      | 1:
        con.Int(3); con.Str(" ");
        n := n DIV 3
      | 2:
        con.Int(5); con.Str(" ");
        n := n DIV 5
      END
    END;
    con.Ln;
  END Test3;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 28 Март, 2018 16:39 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 655
Откуда: Казань
Как я понял, идея вашего решения в том, чтобы сначала проверить все условия, а потом случайно выбрать одно из условий, которое выполняется.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 28 Март, 2018 17:04 

Зарегистрирован: Четверг, 08 Май, 2008 19:13
Сообщения: 610
Откуда: Киев
Да. Тогда легко добиться равновероятности вызова допустимых веток и минимизировать мусорные действия.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 28 Март, 2018 23:25 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1076
Недетерменированный не значит вероятностный.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 29 Март, 2018 13:51 

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 7814
Откуда: Троицк, Москва
Речь, наверное, о стохастичности.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 29 Март, 2018 20:45 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1076
Дело в том, что случайный (в любом смысле) выбор ничем не лучше любого другого. Ситуация в некотором смысле обратная той, что в недетерминированной машине Тьюринга. Тел демон выбирает наилучший вариант, а здесь мы должны быть готовы к тому, что он будет пакостить.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 29 Март, 2018 22:36 

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

Искусственно вводить стохастичный выбор ветки может быть полезно для тестирования -- но суть дела в способствовании мыслительному процессу ДО тестирования.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 03 Апрель, 2018 18:10 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 655
Откуда: Казань
Trurl писал(а):
Дело в том, что случайный (в любом смысле) выбор ничем не лучше любого другого. Ситуация в некотором смысле обратная той, что в недетерминированной машине Тьюринга. Тел демон выбирает наилучший вариант, а здесь мы должны быть готовы к тому, что он будет пакостить.

Да, есть такая вероятность, что при случайном выборе какой-то вариант никогда не будет выбираться.
Есть такое понятие fairness (не знаю, как лучше перевести, как честность?). В книге Verification of sequential and concurrent programs говорится:
Цитата:
Fisher and Paterson [1983] have shown that any fair scheduler that is applicable for arbitrary runs of n components needs at least n! = 1*2*...*n scheduler states.
One way of organizing such a scheduler is by keeping the components in a queue. In each check the scheduler activates that enabled component which is earliest in the queue. This component is then placed at the end of the queue.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Апрель, 2018 12:07 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 655
Откуда: Казань
Вариант эмуляции недетерминированного цикла Дейкстры с очередью:
Код:
  PROCEDURE Test3(n: INTEGER);
  VAR
    queue: ARRAY 3 OF INTEGER;
    i: INTEGER;
    t: INTEGER;
    PROCEDURE Condition(cond, n: INTEGER): BOOLEAN;
    VAR
      result: BOOLEAN;
    BEGIN
      CASE cond OF
        0: result := n MOD 2 = 0;
      | 1: result := n MOD 3 = 0;
      | 2: result := n MOD 5 = 0;
      END;
      RETURN result
    END Condition;
  BEGIN
    queue[0] := 0;
    queue[1] := 1;
    queue[2] := 2;
    i := 0;
    WHILE (i < 3) & ~Condition(queue[i], n) DO
      i := i + 1;
    END;
    WHILE i < 3 DO
      CASE queue[i] OF
        0: con.Int(2); con.Str(" ");
           n := n DIV 2;
      | 1: con.Int(3); con.Str(" ");
           n := n DIV 3;
      | 2: con.Int(5); con.Str(" ");
           n := n DIV 5;
      END;
      WHILE i < 2 DO
        t := queue[i];     
        queue[i] := queue[i+1];
        queue[i+1] := t;
        i := i + 1;
      END;
      i := 0;
      WHILE (i < 3) & ~Condition(queue[i], n) DO
        i := i + 1;
      END;
    END;
  END Test3;


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Апрель, 2018 14:14 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1076
Rifat писал(а):
Да, есть такая вероятность, что при случайном выборе какой-то вариант никогда не будет выбираться.

При случайном выборе эта вероятность равна нулю. Но программа должна работать и в этом случае, недерменированность - более широкое понятие.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Среда, 04 Апрель, 2018 14:56 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 655
Откуда: Казань
Trurl писал(а):
Rifat писал(а):
Да, есть такая вероятность, что при случайном выборе какой-то вариант никогда не будет выбираться.

При случайном выборе эта вероятность равна нулю. Но программа должна работать и в этом случае, недерменированность - более широкое понятие.

Может быть около нуля и с каждой итерацией все ближе приближаться к нулю. Еще, кстати, зависит от того, как устроен генератор псевдослучайных чисел. Может так случиться, что некоторые числа никогда не генерируются.


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

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


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

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


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

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