WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

Технологія розробки мереж Петрі та вирішення проблем які виникають при їх використанні - Дипломна робота

інтерпретації І позначимо через , а стан всієї пам'яті - .
Означення 10: Інтерпретація І0 називається вільною, якщо , тобто множиною значень є множина термів; , тобто припочатковому стані пам'яті в комірці х міститься терм х,
,
тобто використання -того оператора а до термів дає вектор із п екземплярів термів якщо останній є термом, і не визначений в супротивному випадку.
В даному випадку для інформаційного базису існує всього одна вільна інтерпретація. В випадку інших моделей, як показано нижче, існує їх може бути скінчена кількість. Вільна інтерпретація цікава тим, що її засобами встановлюється прямий зв'язок між синтаксисом та семантикою процесів, тобто правдива наступна лема.
Лема 1.5
. Доведення випливає із розгляду t-історії комірки і вмісту комірки при вільній інтерпретації.
Наслідок: . В повній мірі значимість цього наслідку буде видна при розгляді наступних моделей. Зараз же вона нам стане в нагоді доведення основного твердження цього розділу.
Теорема 1.1
.
Доведення: Твердження теореми і правда очевидне, так як вільна інтерпретація є частинним випадком М інтерпретації. Доведемо теорему в ліву сторону. Нехай при І0 в комірку х як процесу , так і процесу засилають один терм t. Ясно, що на одних і тих же початкових даних суперпозиція інтерпретованих операцій t при любій інтерпретації вийде один і той же результат. Із розгляду означення стану пам'яті , видно , що при фіксованому процесі при любій інтерпретації інформація для любого акта береться із одних і тих же виходів. Виходячи з цього при любій інтерпретації формується режим переробки інформації, який задається термом t звідки випливає рівність вмісту комірок із лівої частини теореми.
Щойно доведена теорема носить назву теорема про вільну інтерпретацію. Вона показує, що в деякому смислі вільна інтерпретація являється представником всіх інтерпретацій даного інформаційного базису. Багато подальших тверджень будемо формулювати з квантом все загальності І. Це звичайний прийом теорії моделей програм і обчислень. І для того щоб їх перевірити нема необхідності перебирати всі інтерпретації. Більш того, це неможливо. Достатньо перевірити твердження по всіх вільних інтерпретаціях. В випадку "некерованих" обчислювальних процесів вона одна, в випадку інших моделей вільних інтерпретацій може бути довільне число; головне, щоб всі вони будуть описуватись досить осяйно для перевірки потрібних тверджень. Теорема 1.1 буде при цьому модифікуватися і прийматиме специфічні відтінки, але в цілому її смисл залишиться. Вона дозволяє позбутися або різко скоротити область дії квантора все загальності для інтерпретацій.
1.2. СТРУКТУРИ КЕРУВАННЯ
Вище розглянуті процеси - послідовність деяких дій, які перетворюються при задані інтерпретації в досить конкретні акти. Означення процесу не було зв'язане з яким не будь способом генерації актів або обмеженнями на їх появу в процесі. Можна вважати, що процес являється протоколом спрацювання актів після того як на деяких початкових даних відпрацювала деяка обчислювальна система, яка виконувала який не будь контроль при обчислюванні, але цей контроль ніяк не відображений в протоколі. В даному пункті буде розглянуто ця друга складова обчислення - контроль - в "чистому" вигляді, без відношення до інформаційного складу актів, керування якими буде вестись.
Най простішою структурою контролю являється орієнтований граф, в конкретних моделях зазвичай називають управляючим графом. Якщо G=(W,A), де W - множина вершин, А - множина стрілок, то в W виділяються вхідна і вихідна вершини, а кожній стрілці співставляється символ включення або виключення деякого оператора. Таким чином любому шляху із вхідної вершини в вихідну або нескінченому співставляється послідовність включень і виключень. Множину всіх послідовностей які з'являються позначимо через Pass(a). Якщо люба така послідовність являється процесом, то граф G називається правильним.
Перше питання яке виникає - це чи існує алгоритм перевірки правильності графа. Оказується, що в випадку моделі яку ми розглядаємо множина процесів які породжуються є регулярною, і відповідь проста. Такий алгоритм є і оснований на тому, що якщо граф породжує деяку послідовність , на якій порушується люба аксіома процесу, то він породжує деякий процес , яка не являється процесом, обмеженої довжини. В якості границі для перевірки завжди можна взяти 2k|W|, де k - число простих циклів в графі G. Доведення цього твердження основане на скорочені виключенням з нього зайвих циклів.
Формування обчислювального процесу по графу G походить так, що при русі із деяких вершин ми можемо піти в довільному але тільки одному напрямку. Таким чином, контроль, який задається управляючим графом, являється не детермінованим, але не паралельним. Паралелізм досягається в наслідок розділення актів включення і виключення, і тільки. Інша більш складна модель керування отримується якщо, допустити одночасний рух по деяким стрілкам. Моделі такого типу отримали назву графових моделей паралельних програм і вивчалися найбільш інтенсивно.
Мабуть, самий популярний механізм керування - кінцевий автомат. Він відрізняється від звичайного управляючого графа тим, що при переході від вершини до вершини проходить вибір наступної вершини на основі інформації про спрацювання попереднього акта. Для вказання вибору наступної вершини приходиться вводити деяку додаткову градацію для результатів спрацювання, яка має формальний тип. Як правило, така градація задається співставленням кожному символу оператора а не одного символа оператора виключення а, а деяку множину альтернатив . При такій модифікації залишаться в силі всі поняття і результати попереднього пункту, якщо в означені процесу замінити всі слова "символ виключення а" на "деякий символ виключення аі", а в означені інтерпретації добавити ще одну складову - множина функцій, які вибирають на основі поточного стану пам'яті деяку альтернативу. Управляючий автомат над множиною символів включення і виключення
визначається як п'ятірка , де Q - деяке, зазвичай скінчена, множина станів; q0 - початковий стан; Q - множина кінцевих станів; - частинна функція переходів, . Якщо функція - визначена, то і для довільного j функція визначена. Як завжди робота автомата полягає в переході із одного стану в інший в відповідності з "вказівками" функції . Рух починається з початкового стану і закінчується в першому кінцевому стані який зустрінеться. По скінченим автоматам є великий вибір книг.
Всі моделі які розглядатимуться нижче можна представляти і порівнювати в рамках деякої мета моделі [9]. Загальним для них є те, що вони в сукупності з інформаційним базисом (M, F) вони породжують, генерують або визначають яким не будь іншим способом множину так називаємих допустимих процесів. Множина допустимих процесів, яка виникає в наслідок
Loading...

 
 

Цікаве