Курс лекцій з дисципліни
«Матричний аналіз»
для студентів II курсу
математичного факультету спеціальності
"Економічна кібернетика"
(Лектор Дмитрук Марія Олександрівна)
Розділ 3. Функції від матриць.
1. Визначення функції.
Df. Нехай 
- Функція скалярного аргументу. Потрібно визначити, що розуміти під f(A), тобто. Необхідно поширити функцію f(x) на матричне значення аргументу.
Розв'язання цього завдання відоме, коли f(x) – багаточлен: , тоді .
Визначення f(A) у випадку.
Нехай m(x) – мінімальний многочлен А і він має таке канонічне розкладання 
, – власні значення А. Нехай багаточлени g(x) та h(x) приймають однакові значення.
Нехай g(A)=h(A) (1), тоді многочлен d(x)=g(x)-h(x) – анулюючий многочлен для А, оскільки d(A)=0, отже, d(x ) ділиться на лінійний многочлен, тобто. d(x)=m(x)*q(x) (2).
Тоді, тобто. (3), 
, 
, .
Умовимося m чисел для таких f(x) називати значеннями функції f(x) на спектрі матриці А, а безліч цих значень будемо позначати .
Якщо безліч f(Sp A) визначено для f(x), то функція визначена спектрі матриці А.
З (3) випливає, що багаточлени h(x) та g(x) мають однакові значення на спектрі матриці А.
Наші міркування оборотні, тобто. із (3) Þ (3) Þ (1). Отже, якщо задана матриця А, значення многочлена f(x) цілком визначається значеннями цього многочлена на спектрі матриці А, тобто. всі многочлени g i (x), що приймають однакові значення на спектрі матриці, мають однакові матричні значення g i (A). Потрібно, щоб визначення значення f(A) у випадку підпорядковувалося такому ж принципу.
Значення функції f(x) на спектрі матриці повинні повносильно визначити f(A), тобто. функції, що мають одні й ті самі значення на спектрі повинні мати те саме матричне значення f(A). Очевидно, що для визначення f(A) у загальному випадку, досить знайти багаточлен g(x), який приймав ті ж значення на спектрі А, що і функція f(A)=g(A).
Df. Якщо f(x) визначено на спектрі матриці А, то f(A)=g(A), де g(A) – багаточлен, який приймає на спектрі ті ж значення, що й f(A), 
Df. Значенням функції від матриці А назвемо значення багаточлена від цієї матриці при .
Серед многочленів із С[x], що приймають однакові значення на спектрі матриці А, що і f(x), ступеня не вище (m-1), що приймає однакові значення на спектрі А, що і f(x) – це залишок від поділу будь-якого многочлена g(x), що має ті ж значення на спектрі матриці А, що і f(x), мінімальний многочлен m(x)=g(x)=m(x)*g(x)+r(x) .
Цей багаточлен r(x) називають інтерполяційним багаточленом Лагранжа-Сільвестра для функції f(x) на спектрі матриці А.
Зауваження. Якщо мінімальний многочлен m(x) матриці А немає кратних коренів, тобто. то значення функції на спектрі.
Знайти r(x) для довільної f(x), якщо матриця
. Побудуємо f(H1). Знайдемо мінімальний многочлен H 1 - останній інваріантний множник:
, d n-1 = x 2; d n-1 = 1;
m x = f n (x) = d n (x) / d n-1 (x) = x n = 0 - n -кратний корінь m (x), тобто. n-кратні власні значення H1.
R(0)=f(0), r'(0)=f'(0),…,r (n-1) (0)=f (n-1) (0) Þ .
Трійка є рішенням гри<=>, коли є рішенням гри, де а – будь-яке речове число, к>0 РОЗДІЛ 2. Ігри з нульовою сумою в чистих стратегіях 2.1 Обчислення оптимальних стратегій на прикладі розв'язання задач Використовуючи теорему про мінімакс, можна стверджувати, що кожна антагоністична гра має оптимальні стратегії. Теорема: нехай А – матрична гра та рядки даної...
Картину, що не відповідають їй, є кандидатами на виключення із сфери діяльності корпорації. 5. Розробка корпоративної стратегії Попередній аналіз підготував ґрунт для розробки стратегічних кроків щодо покращення діяльності диверсифікованої компанії. Основний висновок про те, що робити залежить від висновків, що стосуються всього набору видів діяльності в господарському...
Історично першою моделлю корпоративного стратегічного планування прийнято вважати так звану модель зростання - частки, яка більше відома як модель Бостонської консалтингової групи (BCG).
Ця модель є своєрідним відображенням позицій конкретного виду бізнесу в стратегічному просторі, що визначається двома осями (x, y), одна з яких використовується для вимірювання темпів зростання ринку відповідного продукту, а інша - для вимірювання відносної частки продукції організації на ринку продукту, що розглядається.
Поява моделі BCG стала логічним завершенням однієї дослідницької роботи, Проведеної свого часу фахівцем консалтингової компанії Boston Consulting Group.
У процесі вивчення різних організацій, що виробляють 24 основні види продуктів у 7 галузях промисловості (електроенергетика, виробництво пластмас, промисловість кольорових металів, виробництво електрообладнання, виробництво бензину та ін.), були встановлені емпіричні факти того, що при подвоєнні обсягів виробництва змінні витрати на виробництво одиниці виробленої продукції зменшуються на 10-30%.
Також було встановлено, що ця тенденція має місце майже у будь-якому ринковому секторі.
Ці факти стали підставою висновків, що змінні витрати виробництва одна із основних, а то й головним, чинником ділового успіху і визначає конкурентні переваги однієї організації перед іншою.
Статистичними способами було виведено емпіричні залежності, описують взаємозв'язок витрат виробництва, одиниці виробленої продукції і обсяги виробництва. І один з основних факторів конкурентної переваги був поставлений у однозначну відповідність до обсягу виробництва продукції, а отже, про те, яку частку на ринку відповідних продуктів займає цей обсяг.
Основна увага в моделі BCG зосереджується на потоці готівки підприємства, яка спрямовується, або на проведення операції в окремо взятій бізнес - області, або виникає в результаті таких операцій. Вважається, що рівень доходу або витрати готівки знаходиться в дуже сильній функціональній залежності від темпів зростання ринку та відносної частки організації на цьому ринку.
Темпи зростання бізнесу організації визначають темп, в якому організація буде використовувати готівку.
Прийнято вважати, що на стадії зрілості та на заключній стадії життєвого циклу будь-якого бізнесу успішний бізнес генерує готівку, тоді як на стадії розвитку та зростання бізнесу відбувається поглинання готівки.
Висновок:для підтримки безперервності успішного бізнесу грошова маса, що з'являється в результаті здійснення «зрілого» бізнесу, частково має бути інвестована в нові сфери бізнесу, які в майбутньому обіцяють стати генераторами доходів організації.
У моделі BCG основними комерційними цілями організації передбачається зростання і норми прибутку. При цьому набір допустимих стратегічних рішень щодо того, як можна досягти цих цілей - обмежується 4 варіантами:
- 1) збільшення частки бізнесу організації над ринком;
- 2) боротьба збереження частки бізнесу організації ранку;
- 3) максимальне використання становища бізнесу над ринком;
- 4) звільнення від цього виду бізнесу.
Рішення, які передбачає модель BCG, залежить від положення конкретного виду бізнесу організації, стратегічному просторі, утвореному двома координатними осями. Використання цього параметра в моделі BCG можливе з трьох причин:
Зростаючий ринок, як правило, обіцяє в найближчому майбутньому віддачу інвестицій у даний вид бізнесу.
підвищені темпи зростання ринку впливають на обсяг готівки зі знаком «-» навіть у разі досить високої норми прибутку, оскільки вимагає підвищених інвестицій у розвиток бізнесу.
Існує дві моделі BCG: класична та адаптована. Розглянемо Класичну модель:
Структура Класичної моделі:
На осі абсцис виставляється вимір деяких конкурентних позицій організації у цьому бізнесі як відношення обсягів продажів організації у цьому бізнесі до обсягу продажів найбільшого у цій бізнес - області конкурента.
В оригінальній версії BCG шкала абсцис є логарифмічною. Таким чином, модель BCG є матрицею 2*2, на якій області бізнесу відображаються колами з центрами на перетині координат, що утворюються відповідними темпами зростання ринку і величинами відносної частки організації на відповідному ринку.
Кожне завдане коло характеризує лише 1 бізнес - область, характерну для цієї організації.
Розмір кола пропорційна загальному обсягу всього ринку. Найчастіше цей розмір визначається простим додаванням бізнесу організації та відповідного бізнесу її конкурентів.
Іноді кожному колі виділяється сегмент, характеризує відносну частку у бізнес - області організації цьому ринку, хоча отримання стратегічних висновків у цій моделі - це обов'язково.
Розподіл осей на 2 частини зроблено невипадково. У верхній частині матриці виявляються бізнес області, що відносяться до темпів зростання вище за середні. У нижній відповідно нижчим.
В оригінальній моделі BCG прийнято, що межею високих та низьких темпів зростання є 10% збільшення продажів на рік.
Кожному із цих квадратів даються образні назви (наприклад: матрицю BCG називають «Зоопарком»).
«Зірки»: це нові бізнес - області, що займають відносно велику частку ринку, що бурхливо розвивається, на якому приносять високі прибутки. Це бізнес-області можна назвати лідерами своїх галузей, оскільки вони приносять організації дуже високий дохід. Однак головна проблема пов'язана з визначенням правильного балансу між доходом та інвестиціями в цю галузь для того, щоб у майбутньому гарантувати повернення останніх.
«Дійні корови»: це бізнес – області, які в минулому отримали відносно велику частку ринку, проте згодом зростання відповідної галузі помітно сповільнилося, потік готівки в цій позиції добре збалансований, оскільки для інвестицій у таку бізнес – область потрібен найнеобхідніший мінімум. Така бізнес-область може принести хороший дохід організації (Це колишні «Зірки»).
«Важкі діти»: ці бізнес-області конкурують у галузях, що ростуть, але займають відносно невелику частку ринку. Це поєднання обставин призводить до необхідності збільшення інвестицій з метою захисту своєї частки ринку. Високі темпи зростання вимагають значної готівки, щоб відповідати цьому зростанню.
«Собаки»: це бізнес - області з відносно невеликою часткою на ринку в галузях, що повільно розвиваються. Потік готівки незначний, часом навіть негативний.
Але не багато хто використовують Класичну модель, оскільки вона непрактична через необхідність отримання актуальних даних про стан ринку та частки, яку займає компанія та її конкурент. Тому для розрахунків використовуємо
Адаптовану модель:
Адаптована матриця BCG будується з урахуванням внутрішньої інформації компанії. Необхідні дані - обсяги продажів продукції за певний період, який не може бути меншим за 12 місяців, надалі, для відстеження динаміки, необхідно додавати дані за наступні 3 місяці (тобто дані за 12, 15, 18, 21, 24 місяці) . Дані необов'язково мають починатися із січня місяця, але мають бути по місяцях. Також важливо враховувати сезонність продажу товарів чи послуг для продукції вашої компанії. У компанії товарний портфель складається з 5 груп товарів, а також є дані про їх продаж за період січень - грудень 2013р.
Таблиця 5. Дані з продажу підприємства ТОВ «НордВест»
|
Керамічна плитка |
|||||||||||||
|
Пористий бетон |
 |
||||||||||||
|
Крупно форматна цегла |
Другий підхід до аналізу мереж Петрі ґрунтується на матричному поданні мереж Петрі. Альтернативним по відношенню до визначення мережі Петрі у вигляді (Р, Т, I, О) є визначення двох матриць D - і D +, що представляють вхідну та вихідну функції. Кожна матриця має m рядків (по одному на перехід) та n стовпців (по одному на позицію). Визначимо D - = # (p i, I (t j)), a D + = # (p i, O (t j)). D – визначає входи в переходи, D+ – виходи.
Матрична форма визначення мережі Петрі (Р, Т, D - , D +) еквівалентна стандартній формі, що використовується нами, але дозволяє дати визначення термінах векторів і матриць. Нехай e[j] - m-вектор, що містить нулі скрізь, винятком j-йкомпоненти, що дорівнює одиниці. Перехід t j представляється m-вектором-рядком е[j].
Тепер перехід t j у маркуванні µ дозволений, якщо µ > e[j] D - , а результат запуску переходу t j у маркуванні µ, записується як:
δ(t j) = µ - e[j] D - + e[j] D + = µ + e[j] D
де D = D + - D - - Складова матриця змін.
Тоді для послідовності запуску переходів σ = t j 1 , t j 2 , … , t jk маємо:
δ(σ) = µ + e D + e D + … + e D =
= µ + (e + e + … + e)D = µ + f(σ) D
Вектор f(σ) = e + e + ... + e називається вектором запусків послідовності σ = t j 1 , t j 2 , … , t jk , f(σ) j p - це число запусків переходу t p у послідовності t j 1 , t j 2 , …, t jk. Вектор запусків f(σ), отже, є вектором з цілими невід'ємними компонентами. (Вектор f(σ) - це відображення Париха послідовності σ = t j 1 , t j 2 , … , t jk).
Для того щоб показати корисність такого матричного підходу до мереж Петрі, розглянемо, наприклад, завдання збереження: чи є ця маркована мережа Петрі зберігає? Для того щоб показати збереження, необхідно знайти (ненульовий) вектор зважування, для якого зважена сума за всіма маркуванням постійна.
Нехай w = (w 1, w 2, …, w n) - Вектор-стовпець. Тоді, якщо µ - початкове маркування, а µ" - довільне досяжне маркування, тобто µ" належить R(C,µ), необхідно, щоб µ w = µ" w. Тепер, оскільки µ" досяжна, існує послідовність запусків переходів σ = t j 1 , t j 2 , … , t jk , яка переводить мережу з µ в µ". Тому
µ" = µ + f(σ) D
Отже,
µ w = µ" w = (µ + f(σ) D) w = µ w + f(σ) D w, тому f(σ) D w = 0.
Оскільки це має бути вірним для всіх f(σ) , маємо D w = 0.
Таким чином, мережа Петрі зберігає тоді і тільки тоді, коли існує такий позитивний вектор w, що D w = 0.
Це забезпечує простий алгоритм перевірки збереження, а також дозволяє отримувати вектор зважування w.
Розвинена матрична теорія мереж Петрі є інструментом вирішення проблеми досяжності. Припустимо, що маркування µ" можна досягти з маркування µ. Тоді існує послідовність (можливо, порожня) запусків переходів σ, яка призводить з µ до µ". Це означає, що f(σ) є цілим невід'ємним рішенням наступного матричного рівняння для х:
µ" = µ + x D
Отже, якщо µ" досяжна з µ, тоді дане рівняння має рішення в невід'ємних цілих; якщо дане рівняння не має рішення, тоді µ" недосяжна з µ.
Розглянемо, наприклад, марковану мережу Петрі, зображену на рис.1:
Рис. 1. Мережа Петрі, що ілюструє метод аналізу, заснований на матричних рівняннях
Матриці D- та D+ мають вигляд:
t 1 t 2 t 3 t 1 t 2 t 3
p 1 1 0 0 p 1 1 0 0
D - = p 2 1 0 0 D + = p 2 0 2 0
p 3 1 0 1 p 3 0 1 0
p 4 0 1 0 p 4 0 0 1
а матриця D:
У початковому маркування µ = (1, 0, 1, 0) перехід t 3 дозволений і призводить до маркування µ" = (1, 0, 0,1).
µ" = µ + e D = (1, 0, 1, 0) + (0, 0, 1) D =
= (1, 0, 1, 0) + (0, 0, -1, 1) = (1, 0, 0, 1).
Послідовність σ = t 3 , t 2 , t 3 , t 2 , t 1 представляється вектором запусків f(σ) = (1, 2, 2) і отримує маркування µ":
µ" = (1, 0, 1, 0) + (1, 2, 2) D = (1, 0, 1, 0) + (0, 3, -1, 0) = (1, 3, 0, 0)
Для визначення того, чи є маркування (1, 8, 0, 1) досяжним з маркування (1,0, 1, 0), маємо рівняння:
(1, 8, 0, 1) = (1, 0, 1,0)+ x D
яке має рішення х =(0, 4, 5). Це відповідає послідовності σ = t3, t2, t3, t2, t3, t2, t3, t2, t3
(1, 7,0, 1)=(1, 0, 1, 0) + x D
немає рішення.
Матричний підхід до аналізу мереж Петрі дуже перспективний, але має деякі труднощі. Зауважимо насамперед, що матриця Dяк така в повному обсязі відбиває структуру мережі Петрі. Переходи, що мають як входи, так і виходи з однієї позиції (петлі), є відповідними елементами матриць D+і D - , але потім взаємно знищуються в матриці D = D + - D -.Це відображено в попередньому прикладі позицією p 4 і переходом t 3 .
Інша проблема - відсутність інформації про послідовність у векторі запуску. Розглянемо мережу Петрі на рис. 2. Припустимо, ми хочемо визначити, чи є маркування (0, 0, 0, 0, 1) досяжним (1, 0, 0, 0, 0). Тоді маємо рівняння
(1, 0, 0, 0, 0)=(0, 0, 0, 0, 1) + x D
Рис. 2. Інша мережа Петрі, що служить для ілюстрації матричного аналізу
Це рівняння немає однозначного рішення, але зводиться до безлічі рішень (a f (o) =(1, х 2, х 6 - 1, 2х 6, х е - 1, х 6)).Воно визначає взаємозв'язок між запусками переходів. Якщо покладемо х 6= 1 і х 2= 1, то /(о) = (1, 1, 0, 2, 0, 1), але цьому вектору запуску відповідають як послідовність 44444. запуску невідомий.
Ще одна проблема полягає в тому, що рішення рівняння є необхідним для досяжності, але недостатнім. Розглянемо просту мережу Петрі, наведену на рис. 3. Якщо ми хочемо визначити, чи є (0, 0, 0, 1) досяжним із (1, 0, 0, 0), необхідно вирішити рівняння
Рис. 3. Мережа Петрі, що показує, що розв'язання матричного рівняння-необхідна, але недостатня умова для вирішення задачі досяжності
Це рівняння має розв'язок /(а) = (1, 1), що відповідає двом послідовностям: tit 2і / 3 / t. Але жодна з цих двох послідовностей переходів неможлива, оскільки в (1,0, 0, 0) t itні 4 не дозволені. Отже, рішення рівняння замало докази досяжності.
Контрольні питаннята завдання
1. Побудуйте граф мережі Петрі для наступної мережі Петрі:
P=(p 1 ,p 2 ,p 3 ,p 4 ), T=(t 1 ,t 2 ,t 3 ,t 4 ,t 5 ),
I(t 1)=(), O(t 1)=(p 1 ),
I(t 2)=(p 1 ), O(t 2)=(p 2 ),
I(t 3)=(p 2 ,p 2 ,p 4 ), O(t 3)=(p 1 ,p 3 ),
I(t 4)=(), O(t 4)=(p 3 ),
I(t 5)=(p 3 ), O(t 5)=(p 4 ,p 4 ).
2. Побудуйте граф мережі Петрі для наступної мережі Петрі:
P=(p 1 ,p 2 ,p 3 ,p 4 ), T=(t 1 ,t 2 ,t 3 ,t 4 ),
I(t 1)=(), O(t 1)=(p 1 ,p 1 ,p 1 ,p 1 ,p 2 ),
I(t 2)=(p 2 ), O(t 2)=( p 1 ,p 1 p 1 ,p 1 ,p 1 ,p 1 ,p 3 ),
I(t 3)=(p 1 ,p 1 ,p 1 ,p 1 ,p 1 ,p 1 ), O(t 3)=( p 2 ,p 2 p 2 ,p 2 p 4 ,p 4 ),
I(t 4)=( p 2 ,p 3 p 4 ,p 4 ), O(t 4)=(p 3 ).
3. Для мережі Петрі з упр.1 маркування m=(5,4,0,0) вказати дозволені переходи.
4. Для мережі Петрі з упр.2 для маркування m=(7,12,2,1) вказати дозволені переходи.
5. Покажіть, що ER(C,m)=N n , де mÎN n .
6. Доведіть, що якщо m'Î R(C,m), то R(C,m')I R(C,m).
7. Доведіть, що m'Î R(C,m) тоді і тільки тоді, коли R(C,m')I R(C,m).
8. Побудуйте безліч досяжності мережі Петрі з упр.1.
9. Побудуйте безліч досяжності мережі Петрі з упр.2.
10. Мережі Петрі зі своїми фішками і правилами запусків багато в чому нагадують ігри, що мають ігрове поле: шашки, нарди, ним, го та ін. та набору фішок. Фішки розподілені за позиціями мережі Петрі, і гравці по черзі вибирають дозволені переходи та запускають їх. Визначте правила гри, що передбачають:
a Як визначено початкове розташування фішок? (Наприклад, кожен гравець починає гру, маючи одну фішку в будиночку або кожен гравець отримує n фішок на всьому полі за бажанням тощо).
b Якою є мета гри? (Захопити фішки свого супротивника; отримати найбільшу кількість фішок; якнайшвидше позбутися своїх фішок і т.д.).
c Чи не потрібно розфарбувати фішки для різних гравців? (Відповідно до цього визначте правила запуску переходів).
d Чи не варто присвоїти окуляри різним переходам? (Тоді очки гравця визначаються сумою переходів, запущених ним).
На основі цього опишіть гру, наведіть приклад гри.
11. Розробте програму, яка реалізує гру з упр.10, де як вашого супротивника виступає комп'ютер для заданої мережі Петрі.
12. Побудуйте систему моделювання для виконання мережі Петрі. Запуск дозволених переходів визначається користувачем системи моделювання.
13.Мудрці сидять за великим круглим столом, на якому багато страв китайської кухні. Між сусідами лежить одна паличка для їжі. Однак для прийому китайської їжі необхідні дві палички, отже, кожен мудрець має взяти палички праворуч та ліворуч. Проблема полягає в тому, що якщо всі мудреці візьмуть палички зліва і потім чекатимуть, коли звільняться палички з правого боку, то вони чекатимуть вічно і помруть з голоду (стан глухого кута). Необхідно побудувати таку мережу Петрі, яка задає стратегію проведення обіду і не має глухих кутів.
14.Побудувати мережу Петрі, що представляє кінцевий автомат, що обчислює доповнення до двох двійкового числа.
15. Побудувати мережу Петрі, що представляє кінцевий автомат визначення парності вхідного двійкового числа.
16.Побудувати мережу Петрі, що представляє кінцевий автомат, який визначає тригер з рахунковим входом.
17.Побудувати мережу Петрі, що представляє кінцевий автомат, який визначає тригер із роздільними входами.
18. Розробити алгоритм моделювання блок-схем мережею Петрі.
19.PERT-діаграма є графічним поданнямвзаємозв'язків між різними етапами, що становлять проект. Проект є сукупністю великої кількості робіт, при цьому роботи повинні завершитися перш, ніж почнуть виконуватися інші. Крім того, на виконання кожної роботи потрібна певна кількість часу. Роботи графічно видаються вершинами, а дуги використовуються для відображення причинно-наслідкових зв'язків між ними. PETR - діаграма є спрямований граф зі зваженими дугами. Завдання полягає у тому, щоб визначити мінімальний час виконання проекту. Розробити алгоритм моделювання PERT-діаграм за допомогою мереж Петрі.
20. Розробте модель, засновану на мережах Петрі, для моделювання хімічних реакцій.
21. Розгляньте побудову не дерева, а графа досяжності. Якщо вершина x породжує наступну вершину z з m[z]=m[y] для деякої неграничної вершини y, вводиться позначена дуга від x до y. Опишіть алгоритм побудови графа досяжності.
22.Покажіть, що алгоритм побудови графа досяжності сходиться, та досліджуйте його властивості, порівнюючи його з алгоритмом побудови дерева досяжності.
23.Дерево досяжності не можна використовуватиме вирішення проблеми досяжності, т.к. втрачається інформація у зв'язку із запровадженням поняття символу w. Він вводиться, коли приходимо до маркування m і на шляху від кореня до m є таке маркування m, що m m. У цьому випадку можна отримати всі маркування виду m+n(m'-m). Досліджуйте можливість використання виразу a+bn i замість w, щоб представити значення компонент. Якщо ви зможете визначити дерево досяжності, в якому всі вектори маркувань видаються виразами, тоді розв'язання задачі досяжності визначається просто розв'язуванням системи рівнянь.
24. Узагальнюйте визначення збереження, дозволяючи негативні ваги. Що можна було б вважати розумною інтерпретацією негативної ваги? Чи можна вирішити завдання визначення збереження мережі Петрі, якщо дозволені негативні ваги?
25. Розробте за допомогою матричного підходу до аналізу алгоритм визначення обмеженості мережі Петрі.
26. Розробте алгоритм розв'язання задачі рівності двох мереж Петрі. Мережа Петрі C 1 =(P 1 ,T 1 ,I 1 ,O 1) з маркуванням m 1 дорівнює мережі Петрі C 2 =(P 2 ,T 2 ,I 2 ,O 2) з маркуванням m 2 , якщо R(C 1 ,m 1) = R(C 2 ,m 2).
27. Розробте алгоритм розв'язання задачі підмножини двох мереж Петрі. Мережа Петрі C 1 =(P 2 ,T 2 ,I 2 ,O 2) з маркуванням m 2 є підмножина мережі Петрі C 1 =(P 1 ,T 1 ,I 1 ,O 1) з маркуванням m 1 , якщо R( C 1 ,m 1) R (C 2 ,m 2).
28. Розробте алгоритм розв'язання задачі досяжності. У мережі Петрі C=(P,T,I,O) з маркуванням m маркування m досяжна з m, якщо m‘ÎR(C,m).
29. Розробте алгоритм завдання досяжності підмаркування. Для підмножини P' Í P і маркування m' чи існує m''ÎR(C,m), така, що m''(p i)=m'(p i) для всіх p i ÎP'?.
30. Розробте алгоритм завдання досяжності нуля. Чи виконується m'ÎR(C,m), де m'(p i)=0 для всіх p i ÎP?
31. Розробте алгоритм завдання досяжності нуля в одній позиції. Для цієї позиції p i ÎP чи існує m'ÎR(C,m) з m'(p i)=0?
32. Розробте алгоритм розв'язання задачі активності мережі Петрі. Чи активні усі переходи t j ÎT?
33. Розробте алгоритм розв'язання задачі активності одного переходу. Чи активний цей перехід t j ÎT?
34. Мережа Петрі називається оборотною, якщо для кожного переходу t j ÎT знайдеться перехід t k ÎT, такий, що
#(p i ,I(t j))=#(pi ,O(t k)), #(pi ,O(t j))=#(pi ,I(t k)),
тобто. для кожного переходу існує інший перехід зі зворотними входами та виходами. Розробте алгоритм розв'язання задачі досяжності для оборотних мереж Петрі.
35. Розробіть алгоритм розв'язання задачі рівності для оборотних мереж Петрі.
36. Завдання про курців. Кожен із трьох курців безперервно виготовляє сигарету та палить її. Щоб зробити сигарету, необхідні тютюн, папір та сірники. Один із курців завжди має папір, інший – сірники, третій – тютюн. Агент має нескінченні запаси паперу, сірників та тютюну. Агент кладе дві складові на стіл. Курець, що має третій відсутній інгредієнт, може зробити і закурити сигарету, сигналізуючи про це агенту. Тоді агент містить інші два з трьох інгредієнтів, і цикл повторюється. Запропонуйте активну мережуПетрі, яка моделює завдання про курців.
37. Автоматна мережу Петрі - це мережа Петрі, у якій кожен перехід може мати точно один вихід і один вхід, тобто. для всіх t j ÎT ½I(t j)½=1 та ½O(t j)½=1. Розробте алгоритм побудови кінцевого автомата, який еквівалентний заданій автоматній мережі Петрі.
38. Маркований граф є мережу Петрі, у якій кожна позиція є входом точно одного переходу і виходом точно одного переходу, тобто. для кожного переходу p i ÎP ½I(p i)½=1 та ½O(p i)½=1. Розробте алгоритм розв'язання задачі досяжності для маркованих графів.
39. Розгляньте клас мереж Петрі, які є і маркованими графами, і автоматними мережами Петрі.
40. Побудуйте мережу Петрі, яка моделює системи, описані в додатку 8. Опишіть події, що відбуваються в системі, та умови, які описують систему. Побудуйте дерево досяжності збудованої мережі Петрі. Опишіть стан, у якому може бути система.
Дозволяє визначити оптимальну послідовність вивчення навчальних предметів, включених до навчального плану. Кожен предмет у навчальному плані має власний номер.
Нехай навчальний план містить 19 предметів. Будуємо квадратну матрицю з основою, що дорівнює числу предметів у навчальному плані (19).
Методом експертної оцінки досвідченими викладачами визначаються найістотніші взаємозв'язки між навчальними предметами. Стовпці матриці вважаються споживачами, а рядки – носіями інформації. Наприклад, для стовпця 10 важливими носіями інформації є рядки 7, 9, 11, тобто знання з предметів із цими номерами. Ці рядки у стовпчику відображені одиницями (1), відсутність готівкового зв'язку – нулями (0). В результаті проведеного аналізу була утворена матриця дев'ятнадцятого порядку. Аналіз матриці полягає у послідовному видаленні стовпців та рядків. До стовпців, заповнених нулями, не надходить інформація з інших предметів, т. е. вивчення їх грунтується на логічного взаємозв'язку коїться з іншими предметами, хоча вони своєю чергою може бути носіями первинної інформації. Отже, предмети, які мають номери цих стовпців, можуть вивчатися насамперед. Рядки, заповнені нулями, не вважаються носіями інформації та не будуть основою для вивчення інших предметів, а отже, можуть вивчатися останніми.
Спочатку викреслюються стовпці 7,8, 9,18 та відповідні їм рядки. Отримуємо першу скорочену матрицю п'ятнадцятого порядку, яка у свою чергу має нульові стовпці 4, 16, 17. Позбавившись їх, отримуємо другу скорочену матрицю. Провівши, таким чином, усі наступні скорочення, отримуємо матрицю, в якій відсутні стовпці без одиниць, але є нульові рядки, які також викреслюються разом із відповідними стовпцями. Послідовно виконавши подібні дії, приходимо до матриці такого виду, як показано на схемі.
Утворена матриця відповідає графу, наведеному малюнку 3.2. У цьому графі три замкнуті подвійні контури (13-15), (5-6), (11-10). З деяким наближенням можна вважати, що предмети, які увійшли до цих контурів, повинні вивчатися паралельно, причому спочатку вивчаються предмети з номерами 13 і 15, а потім предмети 5, 6, 10, 11.
У результаті проведеного матричного аналізу стає можливим створити схематичну (блочну) модель вивчення предметів у навчальному плані:
Схема показує комбіновану систему підключення навчальних предметів. У осередках містяться номери предметів із паралельним вивченням. Утворену систему підключення слід розуміти як обов'язкову послідовність підключення однієї групи предметів лише після закінчення попередньої, лише як необхідність випередження у тому вивченні. Вона лише свідчить про загальну тенденцію у підключенні предметів.
Матричний аналіз програми
Дає можливість оцінити логічну послідовність розташування навчального матеріалуусередині навчального предмета та відповідним чином удосконалювати її.
Нехай навчальний предмет включає 6 тем. Матриця А! складено за тематичним планом цього навчального предмета. Номери тим, що при складанні матриці розглядаються в плані їх використання щодо інших тем, розташовані по вертикалі, номери, розташовані по горизонталі, відповідають темам, розглянутим у плані використання ними інформації з інших тем.
Для виявлення замкнутих контурів, наявність яких свідчить про неможливість встановлення проходження послідовності проходження окремих тем, проводимо перетворення (укорочування) матриці Аі. Видаляємо рядок 5, що складається з нулів, і стовпець, що відповідає йому, а також нульовий стовпець 3 з відповідним рядком. Утворюється матриця А2.
У матриці А2 рядки, що відсутні, і стовпці, що складаються з одних нулів. Для встановлення замкнутих контурів наводимо відповідний матриці А2 граф (див. рис. 3.3 а).
З вивчення графа слід, наявність замкнутих контурів викликано взаємозв'язком між змістом навчального матеріалу тем 1 і 6, і навіть тим 4 і 6. Причиною зазначеного взаємозв'язку є невдалий перерозподіл змісту навчального матеріалу між зазначеними темами. Переглянувши зміст цих тем, можна усунути наявні замкнуті контури графа. Таким чином утворюється новий граф (рис. 3.3 б) і відповідна йому матриця А3.
Скорочення цієї матриці дає нову матрицю А4.
Після видалення дуг(6, 4), (6, 1) та (1, 6) отримуємо нову вихідну матрицю В1, граф якої немає замкнутих контурів.
Тепер, коли замкнуті контури розірвані, приступимо до коригування порядку розташування тем. Для цього послідовно видалятимемо стовпці, що складаються з нулів, і однойменні з ними рядки. При вивченні тем, що відповідають таким стовпцям, не використовуються відомості з інших тем, тому їх можна вивчати в першу чергу.
У матриці! нульовими є стовпці 1 і 3. Таким чином, тема 1 може зайняти своє місце у тематичному плані. При вивченні причин, що вимагають постановки теми 3 перед темою 2, з'ясовується, що деякі відомості з теми 2 мають місце в темі 3. Однак їх логічніше та корисніше залишити їх у темі 3.
Після перестановки навчального матеріалу замість дуги (3, 2) отримуємо дугу (2, 3); видалимо стовпець 1 - отримуємо матрицю В2.
Темі 2 присвоюємо колишній номер 2. Видаляємо стовпець 2 рядок 2. Отримуємо матрицю В3.
Теми 3 та 4 залишаються з колишніми номерами. Видаляємо стовпці 3, 4 з відповідними рядками; отримаємо матрицю В4
Темі 6 присвоюємо номер 5, а темі 5 – номер 6.
Складаємо матрицю С1 згідно з новим розподілом тем.
Проведемо перетворення матриці, послідовно видаляючи нульові рядки та однойменні з ними стовпці. Відповідні їм теми переміщуємо наприкінці низки, оскільки інформацію цих тем використовують при вивченні інших тем. Темі 5 надається номер 6.
Видаляємо рядок та стовпець 6. Привласнюємо темі 6 номер 5.
Видаляємо рядки 4 та 3 та темам, що їм відповідають, присвоюємо колишні номери 4 та 3.
За темами 1 та 2 залишаються колишні номери у тематичному плані. В результаті проведеної матричної обробки виходить таке остаточне розташування тем у структурі навчального предмета:
З наведеної послідовності видно, що після матричної обробки структури тематичного плану помінялися місцями теми 5 і 6. Крім того, виникла необхідність переміщення навчального матеріалу на тему 5 в тему 1, а також з теми 2 в тему 3.
Як видно з наведеного прикладу, матричний аналіз структури навчального матеріалу дає можливість певною мірою впорядкувати його та вдосконалити взаємне розташуваннятеми навчальної програми.
Слід враховувати, що матричний аналіз навчальних планів та програм вимагає від виконавців великого практичного досвідута глибокого знання змісту навчання. Насамперед це стосується складання вихідної матриці, точніше, до визначення зв'язків між навчальними предметами чи навчальними темами всередині предмета. Зв'язків між такими великими елементами, як теми програми, існує багато, але виконавці матричного аналізу повинні вміти "читати між рядками" (знайти приховані, але реально існуючі зв'язки), визначити значущість різних зв'язків щодо цілей матричного аналізу, а іноді й критично ставитись до змісту тем навчальних предметів.
Матричний аналіз чи матричний метод знайшов стала вельми поширеною за порівняльної оцінці різних господарських систем (підприємств, окремих підрозділів підприємств, і т.п.). Матричний метод дозволяє визначити інтегральну оцінку кожного підприємства за декількома показниками. Ця оцінка називається рейтингом підприємства. Розглянемо застосування матричного методу поетапно на конкретному прикладі.
1. Вибір оціночних показників та формування матриці вихідних даних a ij, тобто таблиці, де по рядках відбиваються номери систем (підприємств), а, по стовпцям номери показників (i=1,2….n) - системи; (j=1,2…..n) - показники. Вибрані показники повинні мати однакову спрямованість (що більше, тим краще).
2. Упорядкування матриці стандартизованих коефіцієнтів.У кожному стовпчику визначається максимальний елемент, а потім усі елементи цього стовпця поділяються на максимальний елемент. За наслідками розрахунку створюється матриця стандартизованих коефіцієнтів.
Виділяємо у кожному стовпці максимальний елемент.