Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Пример (недетерминированное вычислительное предписание) Предписание - часть 4


Гамильтонов обход через подмножество S узлов - это замкнутый путь без повторений, все узлы которого содержатся в S.

Предписание

fct hk == (set node s,

seq node q) seq node:

      if s = Æ

then if g(last(q), first(q))   then q

                                                              else failure

                           fi

                        else  node x == some node z: z e s;

                                if g(last(q), x)            then hk(s\{x}, q 0 <x>)

                                                     else failure

                fi

 fi

порождает недетерминированно-направленный Гамильтонов обход (если он существует) через узлы из конечного множества S в качестве результата вызова hk(s\{x}, <x> о є ), при любом х Î S.

Недетерминированный выбор и концепцию бэктрекинг-недетерминизма можно ввести аналогичным образом в императивные программы. Тогда справедливо: S1 ? S2 для оператора, выполнение которого происходит путем недетерминированного выбора для исполнения одного из операторов S1

и S2

.Снова может быть использовано ключевое слово

failure для обозначения неуспешной ветви (тупика).




Содержание  Назад  Вперед