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



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


Эти тонкие различия затрудняют обращение с недетерминированными выражениями.

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

Введением failure

определяется так называемый «бэктрекинг-недетерминизм» (недетерминированный поиск с возвратом). Недетерминированные ветви вычисления, которые ведут к failure, отсекаются, т. e. не принимаются в качестве результата. Неуспех фиксируется только в том случае, когда все ветви приводят к failure.

Использование failure (выбор по-прежнему является недетерминированным) позволяет организовать поиск в недетерминированно-выбранном дереве вычислений.

Пример (алгоритмы с недетерминированным поиском).

Сортировка недетерминированным выбором. Рассмотрим систему вычислительных предписаний

fct ndsort == ( seq nat s, seq nat r ) scq nat:

    if s = e   then  r

                  else nat x == any(s);

                          if x > first®    then failure

                                                 else ndsort(drop(s, x), <x> * r)

                          fi                 

        fi

    fct any = (seq nat

s) nat:

   if s=e   then failure

       else   first(s)  any(rest(s))

        fi

fct drop = (seq nat s, nat x) seq nat:

   if   s == є       then  failure

   elif   first(s) = x  then   rest(s)

                              else append(first(s), drop(rest(s), x))

   fi

fct sort = ( seq nat s)

seq nat:

   if s = є        then s

                      else nat x = any(s);

                             ndsort(drop(s,x),<x>?є

При вызове sort(s) порождается отсортированная по неубыванию версия s.

Обратим внимание: если затраты времени простого (т.e. недетерминированного) выбора составляют z, то затраты бэктрекинг-недетерминизма в самом неблагоприятном случае имеют порядок 2^z.


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