2. Model Checking. Вериф. парал. и распределенных программных систем. Карпов (2010) (2. Model Checking. Вериф. парал. и распределенных программных систем. Карпов (2010).djvu)
Описание файла
DJVU-файл из архива "2. Model Checking. Вериф. парал. и распределенных программных систем. Карпов (2010).djvu", который расположен в категории "". Всё это находится в предмете "математические методы верификации схем и программ" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла
° ° ° ю Э а ° ° в - ° ° Э ~ в Ф в Л Э 1 ° УДК 681.3.06 ББК 3297326018.2 К26 Групвю педгпвщпя нздапяпг Главный рсаащор Всавед«»ада»думы с Звм. главаогорящяюра ТявгсяаЛа«я»а ЗЗВ. рядно!ней Гя»гср» й Дед»я редвьтср Но»отья Серва»васа Квпиаперная веров» Огвг» Сгргаеяяа Каррсщор Зв»вдаД»свсямеа Дизайн сбвтгви бв»м бвсвеай Зва щюнзвщстсом Ниса»ю Тггро г иенс» иди овгз щгяяо. Неся ю выме!юла. Оаснгт П»тщг» П»щь аф»нсю. Ую есч. а в!в. твв сею °, згквз Ю авщ 'аха пссевег1»,!нхян, сг»с!па»вел». Нг свссасюВгв..ю. Свяпевяе.с»яяванв»»чв»се эвш»в нч»ь явеяап»» ю тхщеомздеетгощщ ес юла эю с. Мввв ачдвьв»за ювц ю ~юльсще Осветив»» язгв явсвввев» ев»»в ! янчев»ив.
С»в втнв е вев»к а»с»гсвг»все ° С'ЗП 'тюв,вве»г 'Нет маею, сввгммвяв, я я»»ия. ю ощея ю.г„юю о Ой!в»»в»; вы»авве 'Вхвгсвсвсзм , мю 18ВМ 978-50775040Ю.1 Карпов ВЗ. Г. К26 МООН. СНЕСКРК3. Верифщяцяа пзраллвыных н распредвюнных просраммных аисюм. — СПбс БХВ-Петербург, 2010. — 560 сс пл. + СО-КОМ 1ЗВУй 978-5-9775-0404-1 В книге рввввзывавтся о навьи результвтак в области щрифщвщщ с помощью метала ваде! сйесВий н приводвтсз примеры прилолмннй яого метода в самых разных областях, Рассматриваются проблеме вернфнявции, темпорельныс логики, акгорнтмы ваде! сйегй»8 дся СП. и ЬТ1., структуры Красим как модели реагирующих систем, апецнфикация свойств реагирующих систем формулвмн тснпорвльной аопащ, бииарнме рещвощне лисс'рвммы, снмВсльнзя щрсфкюквв, колачсстаенньсй анализ спасам и скоте мы реального времснн, а таске применение фуназмепщвьных плей алгоритма ввй! гдсгН»К в раюичных приложениях.
На прпчагаемом компакт-янеке нахолзтвс ннструвцня по установке сасюмы верифиюцин Зртйь меюднческсс поаабне по з юй аистеме и сипев. нпе куйпюкой работы по щрифнквсщн нетривизльной системы логнчесвпо уярааивпис с исскоаькюги щрнвитвмн заданий Дяв свдйе»всм еузаь Ю»я»иивгвое я яссмдаеавеюй е абсасв» Юцйнв»сан!к» УДК 681.3.06 ББК 52.9732601 82 Оглавленив Преписловве. б Структура книги.........., ...............................................................В Сопровожваюший компакг-лиск ' .............,................10 Благавариости .. ...10 Глава 1. Проблема вервфимаввв И 1Л.
Ошибки в пршраммах и ик послелствия.........................,..................................! 3 1.2. Примеры ошибочных программ .....................,.... 18 1.3. Общая схема верификаиии. Проверка ыолелей (глоде! свеса)пй) ........................... 24 1.4. Тестирование и вар ификашм........................................................,.....,............. 30 1.5. Примеры успешной верификвиии систем........,...,.........,.............,.....,.....
33 !.6, Инструменты верификапии. . ... ...... 35 1.7. Звключеиие „. ...................... ..... .,.................... .... 36 1 .8. Замечания .. ...37 3 та Задачи к главе 3 .. . ........ .. ........ ..... :.... .......... . 38 2.10. Сравнение лом!к СТ(. и СП.. 23 1. Тем поральиые логики проиоюго ...
2. 12. Моде! сйссЫпй.. 80 82 Глава 2. Хеыворвльвые логввв 2.3. Утвержлеиня, истиииость которых зависит от времени.............. 2.2, Молавьные в мюмеииые логики. Тепве (ай(с. 2.3. Тем поральиаа логика линейного времени (ПЧ.)..... 2 4. Реагирующие системы (юасд те вувюшв) 2.5, Формальное опрелелеиие 3.73. 2.6. Примеры исполноваиия формул СТ!....................... 2.7.
Соотношения межау операторами ПЪ .. 2.8, Структура Крипке . 2ВХ Расширенная темпорапышя логика ветвяшавюя вршгеии СП.Ь ....................... 4 1 ..............,...... 45 ....................... 5 1 .................. 62 ..................... 68 ,......................73 2.13.
Звкмоченне .........................................,.......................................,.... 83 2.14. Замечания ...............84 2.15. Задачи к главе 2 .... .....85 Глава 3. Алгератм азщЫ сйесИай дла Сп....91 3.1. Темпоральнвя яопгкв веюящегося времени СП................................................... 91 3,2. Ссмантнка СП. нв деревьях вычислений ......,....,,.............,...,,...........,.......,....Ж 32. Формаяьнкя семянтюа СП-.
96 3.4. Проверка формул СТЬ на развертке структуры Кринке ....-...................................9$ 3.5. Базисы СТЬ .99 3.6. Алюритм вайс! сйесй!лй лля СП... . 103 3 7. Пример выполнения алгоритма пюйе! сисой!пй ..................,...-......-,,,.............,. 111 3.8. Заключение .... 113 3.9. Замечания .. ..
113 3. 10. Залечи к главе 3 ... ...! 14 Глава 4. Алгоритм щщ1е1 сйесЫвй дли ЬТ$ .....- П7 4.1. Проверка выполнимости ЬТ1 4юрмул иа вычнслеюмх ,......,...,......,......,.. .......... 1 1 $ Поиск коптрпрнмсров . 119 Контрольный автомат.. . ....-.......... .. 1 20 4.2. Пересечение языков в теории конечных автоматов...........................,.............,...
123 123 Конечные автвяаты н автоматные языки Синхронная ком повинна автоматов и пересечение языков .................................. 125 4.3. Теоретико.автоматнмй метод проверки выпмщиьюсти ЬТ1 формулы ...,........ 128 4.4. Автеявты Бюхи — модели ллв закан ив и-язмюю ............................................... 130 в-языки н поведение реагирующих систем .........................,-.....,....,,.......,..... 131 Автомат Бюхи как коюрольный юп омат дка реаърующей системы,.......,! 34 4УП Операции над автоматамн Бюхи ................,....„,...,....,...........,........,........ 135 4.6.
Автоматы Бюхи и ЬТЬ.формулы..., ..............................................14! 4.7. Структуры Кринке и автоматы Бюхи............................... 144 4.$. Проверка модели лля формул Ь'П....,,...,....,....,....................,.,........ 146 4.9. Построение автомата Бюхи по формуле 1.Т1........,.........................................., 147 Разметка состояний вычисления формулвмн ПЧ.....ь.........................................„148 150 Атомы темиоральной формулы логам ЬТЬ Переходы менку состояниями искомого автомата Бпмн ..... 155 д у н Б 157 Построение автомата Бюхн по формуле !ЛЧ,,...,.................................................
157 4.10. Заключение....,................................, ..............164 4.11. Замечания .............................„,......,...,..... 166 4.12. Задачи к главе 4 .... . 167 Глава 5. Структуры Крвике как моделе реагирующих систем. 171 5.1. Соствюия н переходы реагирующей снсгемм. Гранулярность переходов ....... 171 52$ реагирующие сисгемм, спеинфюэрованные в виде систем псрехомю,........... 175 5.3. Рсагируюшме системы, специфицированные в пиле нескапвзж взаимодействующих сисюм переловю .............................,.......,,.........:177 5.4. Представление прозраммы с конечным числом состояний структурой Крипке................,...................................., .........
186 5.5. Предсзааление параплельимх программ структурой Кринке.:.......л...........,..;... 189 5.6. Пакеты верифнншии и с!рук!ура Кринке. Пекет вернфюмшш Вр1а ...... „. 197 5.7. Построение структуры Кринке лля протравы высового уровня ...............,.....,....ж)4 5.8. Заключение ... .........., .....,......,...206 5.9. Замечания .. ... ж)7 5. 10. Задачи к главе 5..............................................,................,..........,...................209 Глава 6. Спецификации снойстн реагнруюизнх снсзжи формулами 6.1.
Примеры амцнфнквиии свойств технических систем ...,........,.........,...,....,....,216 Причинно.следственная связь событзю .............................................................216 Примеры спепнфнзации свойств систем формуламн ЕТС .....................т..........218 Спецификация бюрмуяами 1.Т1. выполнения событив на вычиамниях.'............. 219 Спецификация формуламн (Л). отсутствия событил на вычислениях ..............219 примеры сцецифнкации свой«га систем формулами ст(.....,....,........,........219 62, Свойства дсстнжнмости(теасвя)ийзу)...........,..........,,221 63. Свойства бсюпзсиостн (за(езу)........., ........ 232 6.4.
Свойства жнжнти (йтымзз) . 227 6.5. Свойства спрммллижмти((ыпмзз) . . ......, ... .,...,.„,......229 6.6. Спецификация справедливости в яшизч СТ1................,..:,...,......,....233 6.7. Справедливая СТ1. (Гыг СП.) .. . ...,...., ....... .. 237 6.8. Заключение. .„„„„,„„„, „„,.....,..„„„...,....,...„...., ...,..244 6.9.
Замечание ...., .........„.....................................,.......,........................244 6.10. Залачн к главе 6 ...,....,.245 Глана 7. Примеры нерифниав1нн 247 7.!. Протокол перслачн данных йГС34чзсй ..........:.....-......,..-............,.......... - ......247 7.2. Протокол РАК .. ..250 7.3. Протокол двухфазной фиксации.............,....,...,........................,................... 253 7.4. Звкзюченнс. ..,... 255 7.5. Замечания ... 256 7.6. Задачи к главе 7 .......,.................................„........,..........257 Глава 8.
Применении алгоритма шобИ сйеейнй.— —. 259 82. Анализ бизнес-пронсссов........,.,...,..,,.,,......................—.,.,.....,....—..чгг,......т-: -....259 82. Проблема планирования как водИ сйесЫп8.,....,...........,,...,.............,,...„.,„.....262 8.3. Логические головоломки и воде! сйссЫпй.......,..................................,.............,.. 267 8.4. Верификаиия криптографических протоколов.....*......................, ....,....,..;п.279 8.5. Заключение. ..............., ...290 8.6. Замечания ...,......,,,........,......., ....т-............,,.29( 8.7. Залачи к главе 8 ............,.....................................................,......................... 292 60 Глава 9. Бвварвые решаюапве дваграммы .....295 9.1.
