Редактирование: ВПнМ, 02 лекция (от 15 февраля)

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

Перейти к: навигация, поиск

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Текущая версия Ваш текст
Строка 30: Строка 30:
У нас есть система, строим более простую модель, на ней проверяем свойства. Причин строить модели две:
У нас есть система, строим более простую модель, на ней проверяем свойства. Причин строить модели две:
-
* Программа, написанная на инженерном ЯП, предназначена для того, чтобы данные обрабатывать
+
* Программа, написанная на инженерном ЯП, она предназначена для того, чтобы данные обрабатывать
-
* Абстракция от лишних состояний
+
* Абстракция от лишних осстояний
-
Мы хотим уменьшить пространство состояний. Что же такое состояние программы?
+
Мы хотим уменьшить пространство состояний. Что же такое состояний программы?
* Состояние программы --- какой оператор выполняется, что записано в память (не только переменные, но и любые ресурсы, с которыми работает программа).
* Состояние программы --- какой оператор выполняется, что записано в память (не только переменные, но и любые ресурсы, с которыми работает программа).
Строка 40: Строка 40:
Есть три переменных и 7 операторов --- 7*2^96 состояния.
Есть три переменных и 7 операторов --- 7*2^96 состояния.
-
При этом, не все эти состояния по ходу порграммы достижимы. Число достижимых состояний меньше, чем потенциальных, и нужно понимать, что просто смотря, анализируя текст программы, мы не можем оценить достижимые состояния, поскольку эта задача алгоритмически неразрешима.
+
При этом, не все эти состояния по ходу порграммы достижимы. Число достижимых сост. меньше, чем потенциальных, и нужно понимать, что просто смотря, анализируя текст программы, мы не можем оценить достиж. сост, поскольку эта задача алгоритмически неразрешима.
второе число --- 6 * 3 * 2^64
второе число --- 6 * 3 * 2^64
-
Первая задача, которую мы получим по курсу --- будет прислан текст программы на С, и нужно будет оценить число потенциальных и достижимых состояний, оценка должна быть обоснована. По этому поводу лектор просит до следующей среды написать на адрес model-checking@cs.msu.su, ФИО и группу и попросить дать порграмму. Если есть старосты групп, лектор просит прислать списки групп.
+
Первая задача, которую мы получим по курсу --- будет прислан текст программы на С, и нужно будет оценить число потенциальных и дост. состояний, оценка должна быть обоснованная. По этому поводу лектор просит до след. среды написать на адрес model-checking@cs.msu.su, ФИО и группу и попросить дать порграмму. Если есть старосты групп, лектор просит прислать список групп
Прежде чем говорить о моделировании, нужно поговорить о модели программ. Если говорить о языке С, то в качестве примера рассмотрим программу, подсчитывающую количество строк. У этой программы может быть очень большое число состояний, посмотрим, как её можно упростить:
Прежде чем говорить о моделировании, нужно поговорить о модели программ. Если говорить о языке С, то в качестве примера рассмотрим программу, подсчитывающую количество строк. У этой программы может быть очень большое число состояний, посмотрим, как её можно упростить:
Строка 133: Строка 133:
=== Достижимость ===
=== Достижимость ===
-
Чтобы посчитать достижимость, нужно отследить все фрагменты вычислений.
+
Чтобы посчитать достижимость, нужно отслеить все фрагм. вычислений.
=== Трассы ===
=== Трассы ===
-
Последовательность разметки состояний. Мы фокусируемся на наблюдаемых свойствах системы. Свойства описываются атомарными предикатами.
+
Послдовательность разметки состояний. Мы фокусируемся на набл. свойствах системы. Свойства описываются атомар. предикатами
-
=== Свойства линейного времени (СЛВ)===
+
=== Свойства лин. времени ===
-
Проверять мы можем свойства линейного времени. СЛВ определяет множество трасс, можно сказать, что оно принадлежит множеству трасс.
+
Проверять мы можем св-ва линейного времени. СЛВ определяет мн-во трасс, можно сказать, что оно принадл. мн-ву трасс.
-
Система переходов удовлетворяет свойству линейного времени,если система трасс системы переходов включается в систему трасс свойства.
+
Система переходов удовл. свойству лин. времени,если система трасс сист. переходов. включается в сист. трасс свойства.
=== Абстракция ===
=== Абстракция ===
-
Формальное описание отношения абстракции. Трассу можно представить как интерпретацию: Множество натуральных чисел, отношение порядка и разметка кси, она для каждого порядкового номера говорит, что заданный в нём предикат истинный или ложен.
+
Формальноеописание отнош. абстр. Трассу можно представить как интерпретацию: Множ. нат числе, отношение порядка и разметка кси, она для каждого порядкового номера говорит, что заданный в нём предикат истинный или ложен.
-
Рассмотрим две трассы, нам надо определить, что они связаны отношением абстракции. Эти две трассы имеют разные функции разметки (у одной может быть больше, у другой меньше), кроме того, состояниям могут соответствовать элементы трассы с разным номером. Будем говорить, что одна трасса является абстракцией другой, если множество наблюдаемых предикатов первой является подмножеством множества второй, сохраняются свойства частичного порядка и определено отображение и если какой-то предикат наблюдается в абстрактной трассе, то значение у него должно быть точно такое же, как и в детальной.
+
Рассм. две трассы, нам надо опр., что они связ. отн. абстр. Эти две трассы имеют разные функции ращметки (у одной модет быть больше, у другой меньше), кроме того, сост. могут соотв. жл-ты трассы с разным номером. Будем говорить, что одна трасса явл. абстракцией другой, если множество набл предикатов первой явл. подмножеством множества второй, сохр. св-ва част. порядка и определно отображ. и если какой-то предикат набл. в абстр. трассе, то знач. у него должно быть точно такое же, ка к и в детальной.
Пример:
Пример:
-
мы рассмотрим свойства p и q, и есть предикаты p, q, r...
+
мы рассм. свойства p и q, и есть предикаты p, q, r...
-
Возникает вопрос, как строить системы переходов, которые генерируют трассы, которые удовлетворяют отношению абстракции.
+
Возн. вопрос, как строить системы перезодов, которые генерируют трассы, которые удовл. отн. абстракции.
-
Пусть есть система, модель, свойство ЛВ. Если свойство выполняется на модели, то оно выполняется на системе. Мы тоже переформолируем это условие как ограничение на трассы. То есть, для любой трассы, которую может сгенерировать система, существует такая, которая может сгенерировать модель такую, что она является абстракцией системы. Если свойство выполняется на всех трассах модели, то, поскольку каждой трассе системы соответствует трасса модели, то свойство выполняется на трассах системы, и система корректна. Вопрос, как такое условие проверить, поскольку оно, вообщем в соотв. с этим опр., потребует большое количество ресурсов. Давайте сформулируем достаточное условие:
+
Пусть есть мсистема, модель, свойство ЛВ. Если свойство выполн. на модели, то оно выполн. на системе. Мы може переформ. это усл. как ограничение на трассы. То есть, для любой трассы, которую может сгенер. система, существует такая, которая может сген модель такую, что она явл. абстракцией системы. Если свойство вып. на всех трассах модели, то, поскольку каждой трассе сист. соотв. трасса модели, то свойство вып. на трассах системы, и система корректна. Вопрос, как такое условие проверить, поскольку оно, во общем в соотв. с этим опр., потребует большое кол-во ресурсов. Давайте сформулируем достаточное условие:
-
Пусть у нас есть система переходов исходной программы и модели. Чем они отл.: в модели прост. сост. меньше, алфавит действий меньше, в модели другое отн. переходов, другой алфавит предикатов, соотв. поменяется разметка. Мы поменяли всё. Если абстрактно поменяяем как угодно, то всё испортится. Наложим условие, как менять: множество состояний модели (первое условие в прямоугольнике лишнее), но вот алфавит предикатов модели совершенно точно включ. в алфавит системы, .... На отобрадение накл. ограничение, что нач. сост. системы должно отобр. в нач. сост. модели. Условие на сист. переходов: (Act' ∈ Act) каждому переходу из системы переходов системы должен соответствовать переход в модели.
+
Пусть у нас есть система переходов исходной программы и модели. Чем они отл.: в модели прост. сост. меньше, алфавит действий меньше, в модели другое отн. переходов, другой алфавит предикатов, соотв. поменяется разметка. Мы поменяли всё. Если абстрактно поменяяем как угодно, то всё испортится. Наложим условие, как менять: множество состояний модели (первое условие в прямоугольнике лишнее), но вот алфавит предикатов модели совершенно точно включ. в алфавит системы, .... На отобрадение накл. ограничение, что нач. сост. системы должно отобр. в нач. сост. модели. Условие на сист. переходов: (Act' ∈ Act) каждому переходу из системы переходов системы должен соотв. переход в модели.
Пока огр. таким опр.
Пока огр. таким опр.
-
Есть изьян в этом условии: можно построить такую модель, что нарушим одно из свойств.
+
Есть изьян в этом условии: можно построить такую модель, что нарушим доно из свойств.
-
Можно назвать это условие условно правильным.
+
Можно назвать это усл. условно правильным.
Если кто-то хочет, может найти.
Если кто-то хочет, может найти.
-
Если посмотреть расписание, то увидим разные практикумы. У СП два практикума. А у АСВК практикума Петровского нет.
+
Если посм. расп., то увидим разные практикумы. У СП два практикума. А у АСВК практикума Петровского нет.
{{ВПнМ}}
{{ВПнМ}}
{{Lection-stub}}
{{Lection-stub}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Личные инструменты
Разделы