Дерево процессов Обзор главы Дерево процессов




НазваниеДерево процессов Обзор главы Дерево процессов
Дата конвертации04.03.2013
Размер485 b.
ТипОбзор


Глава 3. Дерево процессов




Обзор главы 3. Дерево процессов

  • Вводятся понятие дерева процессов и алгоритм построения дерева процессов— базовое понятие и базовый алгоритм метавычислений.



Определение дерева конфигураций tree

  • Дерево конфигураций tree: ориентированное (возможно бесконечное) дерево, каждому узлу n которого приписана некоторая конфигурация c; каждому ребру a, выходящему из некоторого узла n с конфигурацией c, приписано сужение cnt; причем, если из узла n с конфигурацией c выходит k ≥ 1 ребер a1,. . . ak с сужениями cnt1,... cntk, то множества попарно не пересекаются, а их объединение совпадает с .



Дерево конфигураций



Определение множества для пути w из tree

  • Путь w в дереве конфигураций tree представляет множество последовательностей P переходов из одного состояния si вычисления в языке TSG к другому: = { P | P отождествимо с w }, где «P отождествимо с w» (или, «w представляет P») означает, что: cnt0 cnt1 cnt2 w = c0 → c1 → c2 → ...cn... P = s0  s1  s2  ...sn...

    • P и w имеют одинаковые длины
    • для каждого si выполнено: si  , и если si не последнее в P, то si  .




Определение множества

  • Дерево tree представляет множество последовательностей состояний вычислений: = [ | w путь из корня tree и w нельзя продлить ] объединение всех , где w — путь в tree из корневой вершины, который нельзя продлить:

    • либо w имеет бесконечную длину
    • либо w завершается в листовой вершине дерева tree


Определение множества процессов вычисления

  • Множество процессов вычисления p на данных из некоторого класса C (на обобщенном данном программы p): P(p, C) = { process(p, d) | d  }



Определение дерева процессов

  • Пусть p — программа на TSG; C — класс, обобщенное данное для p; tree — некоторое дерево конфигураций. Тогда:

    • treeдерево процессов вычисления p на данных из , если P(p, C)  .
    • Если при этом для каждой вершины дерева существует d, такое, что эта вершина используется в представлении process(p,d), то tree — перфектное дерево (совершенное, нет лишних вершин)




Далее в Главе 3. Дерево процессов

  • Приводятся и обосновываются:

  • алгоритм ptr построения дерева процессов вычисления p на данных из : tree = ptr p C

  • алгоритм xptr построения перфектного дерева процессов вычисления p на данных из : ptree= xptr p C



3.1 Синтаксис представления дерева процессов

  • tree ::= (LEAF conf ) | (NODE conf [branch1,... branchn]) — n ≥ 0

  • branch ::= (contr, tree)



3.2 Вспомогательные функции в алгоритме ptr

  • mkCAVar, mkCEVar :: FreeIndx -> (CVar, FreeIndx) mkCEVar i = ((CVE i), i+1 ) mkCAVar i = ((CVA i), i+1 )

  • splitA :: CVar -> CExp -> Split splitA cv@(CVA _) caexp = ( S [cv:->caexp], R (RESTR[cv:=/=:caexp]) )



3.2 Вспомогательные функции в алгоритме ptr

  • splitE :: CVar -> FreeIndx -> (Split,FreeIndx) splitE cv@(CVE _) i = ( (S[cv:-> (CONS cvh cvt)], S[cv:-> cva]), i’) where (cvh, i1) =mkCEVar i (cvt, i2) =mkCEVar i1 (cva, i’) =mkCAVar i2



3.2 Вспомогательные функции в алгоритме ptr

  • freeindx :: FreeIndx -> Class -> FreeIndx freeindx i c = 1 + maximum(i:(map index (cvars c))) where index (CVA i) = i index (CVE i) = i



Идея алгоритма ptr

  • Мы имеем программу p и класс C — «обобщенные данные» для p.

  • Нам надо «отследить» process(p, d) для всех d, понятие process(p, d) определено через int p d

  • В некотором смысле требуется выполнить программу p на множестве : process(p, ) или int p

  • Это и делается в ptr p C — для обобщенных данных C для p мы пытаемся делать те же преобразования, что и для обычных данных для p делают в int



Идея алгоритма ptr

  • В начале для p и C строится начальная конфигурация c0 так же, как строится начальное состояние s0 в int p d

  • Начальная конфигурация c0 записывается в корень дерева

  • Далее для любой граничной и нетерминальной конфигурации делается попытка выполнить «следующий шаг вычисления программы p» так же, как это сделал бы int



Идея алгоритма ptr

  • Для некоторых конфигураций c наличие c-переменных в с-состоянии не мешают однозначно выполнить шаг вычисления программы p (так же, как это сделал бы int), построить следующее с-состояние и следующую конфигурацию c’. В этом случае мы делаем шаг вычисления c  c’ и в дереве проводим ребро c idC→ c’



Идея алгоритма ptr

  • Для других конфигураций c наличие c-переменных в с-состоянии мешают однозначно выполнить шаг вычисления программы p (так же, как это сделал бы int):

  • Некоторые состояния из «выбирает один вариант» продолжения вычислений, а другие— другой вариант.

  • В этом случае удается построить разбиение sp=(cnt’, cnt’’) такое, что для и шаг уже можно сделать однозначно, перейдя к c’ и c’’, соответственно.

  • В дереве проводим два ребра c cnt’→ c’ и c cnt’’→ c’’.







Интерпретатор языка TSG

  • int :: ProgR -> [EVal] -> EVal int p ds = eval s p where (DEFINE f prms _) : p' = p e = mkEnv prms ds s = ((CALL f prms), e)



3.3 Алгоритм ptr

  • ptr :: ProgR -> Class -> Tree ptr p cl@(ces, r) = evalT c p i where (DEFINE f prms _) : p’ = p ce = mkEnv prms ces c = ((CALL f prms, ce), r) i = freeindx 0 cl



Интерпретатор языка TSG

  • eval :: State -> ProgR -> EVal eval s@((CALL f args), e) p = eval s' p where DEFINE _ prms t' = getDef f p e' = mkEnv prms (args/.e) s' = (t',e')



3.4 Алгоритм ptr (функция evalT)

  • evalT ::Conf->ProgR->FreeIndx -> Tree evalT c@(( CALL f args , ce), r) p i = NODE c [ (idC, evalT c’ p i) ] where DEFINE _ prms t’ = getDef f p ce’ = mkEnv prms (args/.ce) c’ = ((t’,ce’),r)



Интерпретатор языка TSG

  • eval s@((ALT c t1 t2), e) p = case cond c e of TRUE ue -> eval (t1,e+.ue) p FALSE ue -> eval (t2,e+.ue) p



3.4 Алгоритм ptr (функция evalT)

  • evalT c@(( ALT cnd t1 t2 , ce), r) p i = NODE c [ (cnt1,evalT c1’ p i’), (cnt2,evalT c2’ p i’) ] where ((cnt1,cnt2), uce1, uce2, i’) = ccond cnd ce i ((_,ce1),r1) = c/.cnt1 c1’ = ((t1, ce1+.uce1), r1) ((_,ce2),r2) = c/.cnt2 c2’ = ((t2, ce2+.uce2), r2)



Интерпретатор языка TSG

  • eval s@(exp,e) p = exp/.e



3.4 Алгоритм ptr (функция evalT)

  • evalT c@((exp,ce),r) p i = LEAF c



Интерпретатор языка TSG (функция cond)

  • cond :: Cond -> Env -> CondRes cond (EQA? x y) e = let x' = x/.e; y' = y/.e in case (x', y') of (ATOM a, ATOM b) | a==b -> TRUE [ ] (ATOM a, ATOM b) -> FALSE[ ]



3.5 Алгоритм ptr (функция ccond)

  • ccond :: Cond->CEnv->FreeIndx ->(Split,CEnv,CEnv,FreeIndx) ccond (EQA’ x y) ce i = let x’ = x/.ce; y’ = y/.ce in case (x’, y’) of (a, b )|a==b ->((idC ,emptC), [],[],i) (ATOM a, ATOM b)->((emptC, idC), [],[],i) (CVA _, a ) ->( splitA x’ a , [],[],i) (a, CVA _ ) ->( splitA y’ a , [],[],i)



Интерпретатор языка TSG (функция cond)

  • cond (CONS? x vh vt va) e = let x' = x/.e in case x' of CONS h t ->TRUE [vh:=h,vt:=t] ATOM a ->FALSE[va:=x']



3.5 Алгоритм ptr (функция ccond)

  • ccond (CONS’ x vh vt va) ce i = let x’ = x/.ce in case x’ of CONS h t ->((idC,emptC), [vh:=h,vt:=t], [], i ) ATOM a ->((emptC,idC), [], [va:=x’], i ) CVA _ ->((emptC,idC), [], [va:=x’], i ) CVE _ ->( split, [vh:=ch,vt:=ct], [va:=ca], i’) where (split, i’) = splitE x’ i (S[_:->(CONS ch ct)], S[_:->ca]) = split



Свойства ptr

  • Теорема 30. Пусть p — программа на языке TSG; C = (ces, r) — класс, обобщенное данное для p. Тогда, определенное алгоритмом ptr дерево tree = ptr p C является деревом процессов программы p для класса C.

  • Доказательство: разобрать самостоятельно (стр. 48 ̶ 52).



Наша цель — совершенство

  • Множество достижимости некоторой вершины в дереве: множество данных из C, которые «проходят» через данную вершину

  • Перфектное дерево — все множества достижимости непустые

  • Можно ли построить множества достижимости?



Множества достижимости



3.6 Алгоритм xptr

  • Сухие ветви, причины возникновения сухих веток. Обрезание сухих веток в дереве.

  • Перфектное дерево процессов — неперфектное, в котором удалены «сухие ветви».



3.6 Алгоритм xptr

  • Как распознать, пустое ли множество ? Работает класс!

  • При любом sr имеем = Ø

  • Если cleanRestr r ≠ INCONSISTENT то ≠ Ø, для бесконечного Atoms (или «в Atoms достаточно много элементов»)

  • Для конечных Atoms конечным перебором можно понять пустоту FVS(sr,r)



3.6 Алгоритм xptr

  • Рестрикции в конфигурации и в классе достижимости — одни и те же! (по индукции)

  • Перфектное дерево процессов.

  • xptr :: ProgR -> Class -> Tree xptr p cl = NODE c (cutT brs) where tree = ptr p cl NODE c brs = tree



3.6 Алгоритм xptr

  • cutT :: [Branch] -> [Branch] cutT [ ] = [ ] cutT (b@(cnt, tree) : bs) = case tree of LEAF (_, INCONSISTENT) -> cutT bs NODE (_, INCONSISTENT) _ -> cutT bs LEAF c -> (b :cutT bs) NODE c bs’ -> (b’:cutT bs) where tree’ = NODE c (cutT bs’) b’ = (cnt, tree’)



3.6 Алгоритм xptr

  • Теорема 32. Пусть p — программа на языке TSG; C = (ces, r) — класс, обобщенное данное для p. Тогда, определенное алгоритмом xptr дерево tree = xptr p C является перфектным деревом процессов программы p для класса C.

  • Доказательство: разобрать самостоятельно (стр. 52—53).





Обзор главы 3. Дерево процессов

  • Дерево конфигураций

  • Путь w в дереве конфигураций tree представляет множество последовательностей P переходов из одного состояния si вычисления в языке TSG к другому

  • Дерево tree представляет множество последовательностей состояний вычислений: = [ | w путь из корня tree и w нельзя продлить ]



Обзор главы 3. Дерево процессов

  • Множество процессов вычисления p на данных из некоторого класса C (на обобщенном данном программы p): P(p, C) = { process(p, d) | d  }

  • Дерево процессов вычисления p на данных из : дерево конфигураций tree, такое что P(p, C) 



Обзор главы 3. Дерево процессов

  • Дерево tree процессов вычисления p на данных из перфектное, если для каждой вершины дерева существует d, такое, что эта вершина используется в представлении process(p,d)



Обзор главы 3. Дерево процессов

  • Приводятся и обосновываются:

  • алгоритм ptr построения дерева процессов вычисления p на данных из : tree = ptr p C

  • алгоритм xptr построения перфектного дерева процессов вычисления p на данных из : ptree= xptr p C



Похожие:

Дерево процессов Обзор главы Дерево процессов iconДерево вывода (или дерево разбора) в кс-грамматике g = (T, N, P, S) – дерево, для которого выполнены следующие условия
Кс-грамматике g = (T, N, P, S) дерево, для которого выполнены следующие условия
Дерево процессов Обзор главы Дерево процессов iconЭто глагол наст врем., 1 спр., 1-го лица
На могучее дерево, давняя встреча, увидеть дерево, пойти на встречу, колючие кусты, летнее облако, спрятаться в кустах, смотреть...
Дерево процессов Обзор главы Дерево процессов iconЗахват пакетной передачи, выбросов, переходных процессов при переключении
Анализ динамических процессов во временной и спектральной области с захватом сигнала по переходным процессам 20 нс
Дерево процессов Обзор главы Дерево процессов iconУнификация процессов Унификация процессов
Достоверность и непротиворечивость информации (в том числе, для внеших пользователей)
Дерево процессов Обзор главы Дерево процессов iconРастет это удивительное дерево в Африке, в Австралии, а также на тропических островах. В сезон дождей древесина Баобаба впитывает в себя воду как губка.
В засушливый период, дерево расходует накопленную воду и сбрасывает с себя всю листву. Местное население вовсю использует Баобабы...
Дерево процессов Обзор главы Дерево процессов iconТо, на чем записывали информацию – камень, глина, дерево, папирус, пергамент, бумага то, на чем записывали информацию – камень, глина, дерево, папирус, пергамент, бумага
Появление компьютеров изменило технологию письма. С помощью специальных компьютерных программ можно набрать любой текст, внести в...
Дерево процессов Обзор главы Дерево процессов iconМоделирование процессов потребления. Моделирование процессов потребления
Повседневная жизнь человека связана с решением целого ряда задач, в которых необходимо принимать решения о выборе поведения
Дерево процессов Обзор главы Дерево процессов iconТемпература. Автор презентации
Это удобно, так как большинство климатических процессов, процессов в живой природе и т д связаны с этим диапазоном. Изменение температуры...
Дерево процессов Обзор главы Дерево процессов iconАвтоматизация большинства лабораторных процессов: Автоматизация большинства лабораторных процессов
Возможность работать с большим объемом исследований (от 10000 до 50000 образцов биоматериалов в день)
Дерево процессов Обзор главы Дерево процессов iconКедр-дерево жизни кедр-дерево жизни

Разместите кнопку на своём сайте:
hnu.docdat.com


База данных защищена авторским правом ©hnu.docdat.com 2012
обратиться к администрации
hnu.docdat.com
Главная страница