МФСП, 08 лекция (от 22 октября)

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

Версия от 16:59, 6 декабря 2008; Bronikkk (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

В след раз консультация. Потом коллоквиум.

Фундированное множество. Что такое част. упор. мн-во, мы помним. Фундир. —- част упорядоченное, в котором не сущ. беск. упорядоченной посл.: (w, -<), в котором не сущ. беск. уб. посл.

Пример:

+----------------------------------------+
| START:                                 |
| (y_1, y_2) ← (0_λ, x_1)    |
+----------------------------------------+
               |                    
+----------->  Vi---------------------------+ F
|          (----------------)               |
|   +------(  y_2 ≥ x_2  )               HALT:
|   |      (----------------)               (z_1, z_2) ← (y_1, y_2)
|   V
+-(y_1, y_2) ← (y_1+1, y_2-x_2)

Шаг 1. Точка сечения. На этом же шаге ваыбир. индукт. утв. q_i(-x-, -y-), которые обычно совп. ..., которые выб. при метод. доказ. част. корректности

Шаг 2. Мы должгы выбрать оценочную функцию. Нам надо выбр. фундированное множество (w, -<), и для каждой точки сечения задать оценочную функцию u_i(-x-, -y-): D_-x- × D_-y- → w

Шаг 3. Условие завершимости. На котором для каждого промежуточного бащового пути должны выписать усл. завершимости, которое выглядмт следующим образом: ∀-x-, &forall-y- q_i(-x-, -y-) ∧ R_α(-x-, -y-) ⇒ (u_i(-x-, -y-) >- u_j(-x-, r_α(-x-, -y-))). Неформ. объясн: если в нач. точке сеч. выбр инвар. и поудйм по пути α, то когда приддём в конец, то оценочная функция даст на знач. строго меньшее, чем оценосчная функция в начале. Тем самым у нас уменьш. знач. функции, и, поск. мн-во фундированное, мы не сможем юеск. зодить по базовым путям и в конце уконцов выйдем на заверш. оператор.

Можно заметить, что мы форм. условие только для промежуточных базовых путей.

Какие есть ньюансы:

То, что при опр. оценочных функций и фунир. мн-ве неоюбх. показывать, что оценоч. функция опр. корректно. Что это значит: посм. на примере: у нас был инвар. определён следующего вида: q_i(-x-, -y-) = (x_1 = y_1 x_2 + y_2) ∧ (y_2 ≥ 0) ∧ (x_2 > 0). Оценоч. функцию, когда док., выбирали u_i(-x-, -y-) = y_2. При этом в кач-ве фундир. мн-ва мы выбирали просто мн-во нат. чисел. Когда лектор говорит о томм, что необх. показать корректность, то лектор говорит о том, что в каждой точке сечения там, где мы опр. u_i, у нас фактически вып. след. условие, условия корректности определения оценочной функции, уоторое говорит, что для любых x, y, для которых выполнен инвариант точки сечения, оценочсная функция действ. явл. значение, принадл. фундир. множеству: ∀ -x-, ∀ -y- q_i(-x-, -y-) ⇒ u_i(-x-, -y-) ∈ w. Соотв., когда опр. оцекноч. функцию, необх. также форм. усл. корректности опр. оценоч. функции, и именно это влечёт второй ньюанс, который состит в том, что
Жти инвар. q_i иногда отл. от инвар., исп. в методе док. част. корректности, потому, что там необх. добавить какой-то коньюнкт о том,Ю что какая-то переменная больше нуля. А это озн., то, что если q_i у нас отл. от того, что исп. на пред. шаге, то нам необх. вып. все усл. вериф., которые выпис. на осн .... . Поэтому лучше модиф. доказ., чтобы два разане выпис очень похожие условия.

Опять же, существует теорема, которая утв. корректность этого метода:

Теорема. Если у нас выбр. программа P и некий входной предикат φ, то после вып. всех трёх шагов метода, у нас будет следовать завершимость программы, заданной своей блок-схемой, на входном предикате φ.

Если мыпосмотрим то, что у нас происзодит с прим. жтого метиода к нашему примеру с целочисл. делением, то происз.ж то же самое, что и на пред. олекции, когда док. заверш. схеми без исп. метода фунд. множеств., а именно:

Выбир точку, выбир индуктивное утв. q_i, затем выбир. фунд. мн-во, совп. с мн-вом нат. числе, опред. точки и записываем усл. корректности этой точки сечения, оно выгл. дост. очевидно, поск. в индукт. утв. есть y_2 ≥ 0, поэтому принадл. мн-ва зн. функции очевидно. После этого .... прохождение по циклу из точки сечения i в точку сечения i выгл. очевидно:

i-i: ∀ -x- ∀ -y- (x_1 = y_1 x_2 + y_2) ∧ (y_2 ≥ 0) &and (x_2 > 0) ∧ (y_2 ≥ x_2) ⇒ y_2 > y_2 - x_2

Несложно видеть, что данное усл. завершимости явл. корректным, поск. (x_2 > 0) ∧ (y_2 ≥ x_2), и из этого следует y_2 > y_2 - x_2.

Двинемся дальше.

Мы с помощбю метода индукт. утв. доказали част. корр. программы ({φ} P {ψ}), с помощью метода фунд. мн-в доказали завершимость (<φ> P <T>) , из этого след. полная корр. отн. спец., заданной предикатами φ и ψ: <φ> P <ψ>

Далее введём опр. эквивалентности программ относительно предиката φ, задающего обл. ... значений программ. Прежде всего, программы P_1, P_2 характеризуются 3 доменами: D^1_-x-, D^1_-y-, D^1_-z- (домены входных, промежуточных, выходных перем), аналогичные домены есть у второй программы. Программы сравнимы., если у них совп. домены входных и выходных данных.

Опр. P_1 сравнима с P_2, если D^1_-x- = D^2_-x-, D^1_-z- = D^2_-z-

Соответственно, P_1 ~ P_2 относитлеьно φ: D^1_-x- → {T, 1}, если для ∀ -x- ∈ D_-x- при условии, что вып предикат φ(-x-) ⇒ вычисления совпадают: M[P_1](-x-) = M[P_2](-x-). M[P] возвр. либо знач. из вых домена, либо ω, если выч. не завершается.

Рассмотрение программ с массивами.

Если мы попробуем добавить в наши сущ. методы вериф. работу с массивами, то в блок-схемах факт. появляется некий новый тип переменных, наз. массивы неокотрой фик. размерности, которые могут участвовать во всех выр., опр. функци, припис. к усл. опер., опер. присваивания, нач., заверш. оператору... Собственно говоря, можно считать, сильно нового ничего не появляется. Наиболее интересный аспект получается связан с необх контролировать невыход за границы массива при индекс его эементами. Если у нас где-то встр. выражение x[i+j], а x — массив целых числер разм. 10, то для док. корр. программы необх. будет показывать, что в этом выр. i+j лежит в диапазоне между 0 и 10, то есть, явл. корр. индексом, чтобы программа вып. также корректно.

Соответственно, сейчас надо опр., как появл. данное изм. на соотв. шаги метода Флойда.

Cajhv/ vjlba/ vtnjlf Akjqlf? rjnjhst gjnh/ lkz hf,jns c vfccbdjv/ Gthtl 'nbv лектор хотел бы сказать, что товарищ МакКарти можно задать как две операции и аксиомы работы с ними:

x: Nat[N]
c(x,i): Nat[N] × [x, N-1] → Nat
a(x, i_1, n_1, ..., i_n, n_k): Nat[N](×[0,N-1]×Nat)^{1..N} → Nat[N]

Этих опер. дост. Аксиомы, соотв., такие:

∀x ∀i ∈ [0, N-1] (i_1 ≠ i) ∧ ... (i_k ≠ i) ⇒ c(a(x, i_1, n_1, ..., i_k, n_k), i) = c(x_i, i)
∀ x ∀ i (i=i_j) ⇒ c(a(x, i_1, n_1, ..., i_k, n_k), i) = n_j

Для метода инд. утверждение у нас ост. всё то же самое:

Ш1.
Ш2.
Ш3. Добавл. усл. корр., связанное с невыходом за гр. массива. Усл. корр. опр. для всех операторов всех видов, кроме join. Для всех операторов, в которых встреччается инд. некоего массива: x[y], необх. ∀ путей, нач. во всех точках сечения i и зак. в операторе n (i-n), на котором нет других точек сечения, необх. сформ. усл. корректности: ∀ -x- &forall -y- p_i(-x-, -y-) ∧ R_α(-x-, -y-) ⇒ 0 ≤ y < N. Если говорить более форм., то в качестве инд. исп. f(-x-, -y-), соотв., если писать форм., то надо писать f(-x-, r_α(-y-)). Соответственно, аналогично требование для путей, которые нач. в начальном операторе: в любом опер., в котором есть разым., в любом путе, в котором есть нач. оператор, и которое не сод. точек сечения, будет аналог. сформ. выражение: ∀ -x- φ(-x-) ∧ R'_α(-x-) ⇒ 0 ≤ f('x', r_α(-x-)) < N

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

В касестве примера рассм. программу, которая выч. реверсирование массива.

Допустьим, есть вх. массив x: N[10]. Есть промеж. переменные y : N[10], i : N. Домен вых. переменных: z : N[10]. Вообще, это делается в одно присв.. Но мы простым путём не пойдём и нарис. программу с циклом:

START:
(y, i) ← (x, 0)
       |<---+
       |-i  |
  T    V    |    F
+-----i<5 -------------------+
|           |                 |
|           |                 |
V           |                 V
(y[i], y[9-i], i) ←    HALT:
(y[0-i, y[i]], i+1)         z ← y

Теперь необх. сформю спецификацию:

Предусловие: φ ≡ true
Постусловие: ψ ≡ ∀ i ∈ {0..9}: z[i] = x[9-i]

Ш1. Выберем точку сечения: i.

Ш2. На втором шаге необх. сформ. инд. утверждение: ∀ j ∈ N: 0 ≤ j ≤ i ⇒ (y[j]=x[9-j])∧(y[9-j]=x[j])

Ш3. Необх. сформ. усл. вериф. для всех базовых путей. ∀ x ∀ j ∈ N 0 ≤ j ≤ 0 → x[j] = x[9-j] ∧ x[9-j]=x[j]. Условие зап. корр., но оно не явл. истиной. То есть инв., который мы выбрали, явл. не совсем корр., поск на 1 проходе он не вып. Соотв., нам надо подкорр. эжтот инв., чтобы он действ. описывал точку сечения, или передвинуть точку сечения. Но лектор предл. подпр. инв. На самом деле, 0 ≤ j < i. Соотв., теперь, кода мы модиф. инвариант, левая часть импл. становится ложью и импл. становится истиной. Посмотрим на след. базовый путь. Рассм.п базовы йпуть, который нач. с т. с., проходит итерацию цикла и в неё возвр.: ∀ x ∀ y ∀ i: (∀j ∈ N, 0 ≤ j < i ⇒ y[j] = x[9-j] ∧ y[9-j]=x[j]) ∧ i < 5 → (∀ j ∈ N 0 ≤ j < i+1 ⇒ y'[j] = x[9-j] ∧ y'[9-j]=x[j]), y' = a(y, i, y[9-i], 9-i, y[i]). Это не есть тожд. истина. В данном случае, когда мы пис. инв., мы бкзусл .написали, что для частиЮ, которую мы прошли, перест. произошла, но мы забыли важный момент: конец массива сод. неизм. массив x. Именно это знание и необх. отразить. Необх. написать, что для i <= j < 9-i y[j]=x[j]. Тогда слева появится конъюнкция и это тогда действ. будет тожд. истина.

Тем самым лектор зотел проилл. момент, что когда пишете инв., не забывайте вносить вещи, которые как бы очевидны. Это же отн. к огр. на обл. значений перем.

Ссылки: