ВПнМ, примеры задач/Задача 5

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск
м (→Задача 2 - добавлен шаблонный вариант)
(→Задачи (инв-ные))
Строка 116: Строка 116:
=== Задача 5 ===
=== Задача 5 ===
-
...
+
 
 +
Между событиями 'процесс p находится на метке iter_begin' и 'процесс p находится на метке iter_end' верно: если наступило событие 'в канал c отправляется сообщение req', то до него было событие 'из канала d принимается сообщение ack'
 +
 
 +
#define p_b p@iter_begin
 +
#define p_e p@iter_end
 +
#define c_r c!req
 +
#define d_a d?ack
 +
 
 +
[]( (p_b && !p_e && <>p_e) -> ((!c_r U p_e) || (!c_r U d_a)) )
 +
 
 +
(Источник: практикум, задание 4, вариант 117, сдано не Савенкову)
 +
 
 +
 
 +
=== Задача 6 ===
 +
 
 +
Между событиями 'значение глобальной переменной state равно enter' и 'значение глобальной переменной state равно leave' верно: после события 'в канал c отправляется сообщение req' рано или поздно наступит событие 'из канала d принимается сообщение ack'
 +
 
 +
#define s_e state == enter
 +
#define s_l state == leave
 +
#define c_r c!req
 +
#define d_a d?ack
 +
 
 +
[]( (s_e && !s_l && <>s_l) -> ((!s_l U c_r) -> (!s_l U d_a)) )
 +
 
 +
(Источник: практикум, задание 4, вариант 117, сдано не Савенкову)
 +
 
 +
=== Задача 7 ===
 +
 
 +
До наступления события 'процесс p находится на метке iter_end' верно: после события 'значение глобальной переменной x равно 3' рано или поздно наступит событие 'значение глобальной переменной y равно 5'
 +
 
 +
#define p_e p@iter_end
 +
#define x_3 x == 3
 +
#define y_5 y == 5
 +
 
 +
(!p_e U x_3) -> (!p_e U y_5)
 +
 
 +
(Источник: практикум, задание 4, вариант 117, сдано не Савенкову)
{{Курс ВПнМ}}
{{Курс ВПнМ}}

Версия 14:02, 6 июня 2010

Содержание

Как решать эти задачи?

Для решения этих задач обязательно знать определения, а так же следующие шаблоны.

Задачи, по сути делятся на инвариантные к прореживанию и не обязательно инвариантные.

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

Будьте готовы к тому, что вам скажут, что в формуле применять слабый until нельзя, поэтому здесь следующие форм-лы экв-ти: 

p W q = ([]p) | (p U q)
p W q = <>(!p) -> (p U q)
p W q = p U (q | []p)


Задачи (не инв-ные)

Втаких задачах можно спокойно применять оператор Next (X).

Задача 1

После события 'процесс p находится на метке iter_begin' и до наступления события 'процесс p находится на метке iter_end' верно: сразу за событием 'значение глобальной переменной y равно 5' наступает событие 'значение глобальной переменной x равно 3' (полученное свойство не обязательно может быть инвариантным к прореживанию) 

#define p_begin (p@iter_begin)
#define p_end (p@iter_end)
#define global5 (g==5)
#define global3 (g==3)

[](<>p_begin && p_begin -> X <> (global5 -> X global3 ))

TeX'ом: 

\Box (\Diamond p \And p \rightarrow X \Diamond (g1 \rightarrow g2))

(по-моему, в формуле вообще нету p_end. такого быть не должно.)

Задача 2

До наступления события 'значение глобальной переменной state равно leave' верно: событие 'процесс p находится на метке sent' наступает не более одного раза 

#define state_leave (state==leave)
#define p_sent (p@sent)

[](p_sent -> X (!p_sent U state_leave))

Задача 3

Между событиями 'значение глобальной переменной state равно enter_critical' и 'значение глобальной переменной state равно leave_critical' верно: если наступило событие 'процесс p находится на метке lock', то до него было событие 'значение глобальной переменной state равно locked' 

#define state_enter (state==enter_critical)
#define state_leave (state==leave_critical)
#define state_locked (state==locked)
#define p_lock (p@lock)

[]( state_enter -> X((!p_lock U state_leave) || (<>p_lock && !p_lock U state_locked) )

Задача 4

После наступления события 'значение глобальной переменной state равно enter_critical' верно: событие 'процесс q находится на метке received' наступает ровно один раз 

#define S "state == enter_critical"
#define was_received Q@received

[](S -> (<>was_received && [](was_received -> X([]!was_received))))

Задача 5

До наступления события 'значение глобальной переменной state равно leave' верно: событие 'процесс p находится на метке sent' наступает не менее одного раза 

#define R "state == leave"
#define was_sent P@sent

([]!R) || (!R U (was_sent && !R))

Задачи (инв-ные)

Задача 1

После события 'процесс p находится на метке iter_begin' и до наступления события 'процесс p находится на метке iter_end' верно: после события 'в канал c отправляется сообщение req' рано или поздно наступит событие 'из канала d принимается сообщение ack' 

#define begin P@iter_begin
#define end P@iter_end
#define R ...@C_send_req
#define S ...@D_send_ack

[]((begin) -> [](R -> (!end U (S && !end))))


Задача 2

После события p и до наступления события q событие r наступает не более одного раза. (полученное свойство должно быть инвариантным к прореживанию)


1й вариант: 

[] (p && !q -> !r W (q || (r W (q || !r W q))))

2й вариант: 

\Box \Biggl( p \rightarrow \biggl( \Bigl( r \rightarrow (\text{r U !r}) \Bigr) \ || \ \Bigl( \text{(!r U q) } || \text{ (!q U (r U (!r U q)))} \Bigr) \biggr) \Biggr)

ps. пояснение формулы:

  1. до первого || — случай, когда q не факт, что произойдёт (после того, как произойдёт r, оно длится до тех пор, пока не прекратится)
  2. после первого || — случай, когда q обязательно произойдет
    • до второго || — r встречается 0 раз
    • после второго || — r встречается 1 раз, записано с помощью трёх вложенных циклов (описание промежутков)

Задача 3

В одной итерации вычисления между метками Start и End операция R всегда предшествует (не обязательно непосредственно) выполнению операции S (полученное свойство должно быть инвариантным к прореживанию). 

\Box \biggl( Start \And \ !End \And \Diamond End \biggr) \rightarrow \biggl( \Bigl( \text{(!S U R)} \And !(S \And R) \And !End \Bigr) \ || \ \text{(!R U End)} \biggr)


Задача 4

В ходе итерации, начинающейся меткой START и заканчивающейся меткой END, выполнение оператора x==1 всегда влечет за собой приём сообщения, помеченного меткой S. 

[] (START & !END & <>END -> ( (!P U END)||((P -> (!END U S))U END) )


Задача 5

Между событиями 'процесс p находится на метке iter_begin' и 'процесс p находится на метке iter_end' верно: если наступило событие 'в канал c отправляется сообщение req', то до него было событие 'из канала d принимается сообщение ack' 

#define p_b p@iter_begin
#define p_e p@iter_end
#define c_r c!req
#define d_a d?ack

[](  (p_b && !p_e && <>p_e) -> ((!c_r U p_e) || (!c_r U d_a))  )

(Источник: практикум, задание 4, вариант 117, сдано не Савенкову)


Задача 6

Между событиями 'значение глобальной переменной state равно enter' и 'значение глобальной переменной state равно leave' верно: после события 'в канал c отправляется сообщение req' рано или поздно наступит событие 'из канала d принимается сообщение ack' 

#define s_e state == enter
#define s_l state == leave
#define c_r c!req
#define d_a d?ack

[](  (s_e && !s_l && <>s_l) -> ((!s_l U c_r) -> (!s_l U d_a))  )

(Источник: практикум, задание 4, вариант 117, сдано не Савенкову)

Задача 7

До наступления события 'процесс p находится на метке iter_end' верно: после события 'значение глобальной переменной x равно 3' рано или поздно наступит событие 'значение глобальной переменной y равно 5' 

#define p_e p@iter_end
#define x_3 x == 3
#define y_5 y == 5

(!p_e U x_3) -> (!p_e U y_5)

(Источник: практикум, задание 4, вариант 117, сдано не Савенкову)


Верификация программ на моделях

01 02 03 04 05 06 07 08 09 10

Календарь

пт пт пт пт пт
Февраль
   08 15 22 29
Март
  14 21 28
Апрель
04 11 18

Материалы по курсу
Список вопросов к экзамену | Примеры задач: 1 2 3 4 5 | Теормин

Получено с http://esyr.org/wiki/%D0%92%D0%9F%D0%BD%D0%9C%2C_%D0%BF%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_5
Личные инструменты
Разделы