Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методичні вказівки до практичних занять
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2010
Тип роботи:
Методичні вказівки
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра автоматизованих систем управління
Методичні вказівки до практичних занять
з курсу
“Основи системного аналізу складних систем“
для студентів базової вищої освіти
за напрямком 6.0804 “Комп’ютерні науки”
Львів - 2010
ВСТУП
Методи системного аналізу базуються на вмінні представити незнайому ситуацію як певну комбінацію знайомих. Ці методи представляють довільні задачі в термінології теорії систем, що дає можливість уточнити початковий стан, системні ресурси, рушійні сили, а також мету та алгоритми її досягнення в довільній ситуації, в якій знаходиться система.
В багатьох випадках алгоритми аналізу можна замінити простішими алгоритмами розпізнавання типу ситуації і на основі цього вибрати тип необхідної дії або алгоритм. Це дозволяє в незнайомій ситуації розпізнати та застосувати давно вивчені та досліджені на практиці методи, оскільки ніколи не можна йти проти принципів, які були доведені та багато разів перевірені. Деякі з методів системного аналізу представлені у даній методичній роботі.
Тема 1. Визначення логічних залежностей в системі.
Логічною залежністю називається вплив між подіями в системі. Подія, яка залежить від інших подій позначається як F. Події, чи умови, від яких залежить появлення події F, позначаються як x1,x2,...,xn. Якщо F=1, то кажуть, що подія відбувається, якщо F=0, то подія не відбувається. Якщо xi = 1, то умова xi виконується, а якщо xi = 0, то – не виконується. Пошук логічної залежності F(x1,x2,...,xn) в системі від умов x1,x2,...,xn базується на виділенні двох множин комбінацій значень x1,x2,...,xn, при яких подія відбувається (F=1) та при яких подія не відбувається (F=0). Комбінації умов задаються двома таблицями ( F=1 та F=0 (див. рис.1).
Якщо F задана не на всіх можливих комбінаціях, то задача називається слабо визначеною. Переважна більшість задач є слабо визначеними. Якщо ж існує така комбінація x1,x2,...,xn, яка присутня одночасно в двох таблицях, то задача називається суперечливою. Суперечливість задачі є в тому, що при одних і тих умовах подія F може відбутися, чи не відбутися взагалі. Якщо система представляється у формі подій, то відбутися на половину подія не може. Суперечливість завдання події F означає, що множина умов не є повною, або не вірним є трактування події. Для визначення правильної логічної залежності необхідно ввести додаткові умови і уточнення, які розв’яжуть суперечку. Розглянемо приклад розв’язку слабо визначеної задачі пошуку логічної залежності.
F = 1
x1
X2
x3
x4
X5
1
0
0
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
0
0
F = 0
X1
X2
x3
x4
X5
1
1
1
1
0
0
0
0
0
0
0
1
0
1
0
Рис. 1. Пошук логічної залежності від умов, при яких подія відбувається або не відбувається.
Для пошуку логічної залежності необхідно перебрати всі комбінації змінних, які впливають на результат F і серед них вибрати мінімальні. Мінімальною логічною залежністю вважається залежність, яку можна виразити найпростішим логічним виразом. Іншими словами, якщо у вас є декілька гіпотез про логічну залежність події F від умов x1,x2,...,xn, то ймовірніше всього, що ця залежність є найпростішою.
Отже, в першому циклі перебираються всі варіанти, які містять один стовпець: (1; 2; 3; 4; 5), в другому циклі перебираються всі варіанти, які містять два стовпця: (1,2; 1,3; 1,4; 1,5; 2,3; 2,4; 2,5; 3,4; 3,5; 4,5) і т.д. Для заданих стовпців треба вибрати такі комбінації значень змінних xi, які б зустрічалися у таблиці F=1 і не зустрічалися б у таблиці F=0. Такі комбінації називаються інтервалами. В кожний інтервал може входити декілька комбінацій, а саме ті, які співпадають по заданих стовпцях. Наприклад, в інтервал ( - 0 - 1 - ), що належить варіанту (2,4), входять комбінації (1 0 0 1 0) та (1 0 1 1 1) з таблиці F=1, тому що вони співпадають з цим інтервалом по заданих стовпцях. Як і вимагається, в даний інтервал не входить жодна комбінація з таблиці F=0, тобто знайдений інтервал значень позитивно впливає на подію F.
Кожний знайдений таким чином інтервал необхідно записати в діаграму (див. рис.1), в якій символом “x” позначено надходження комбінації в інтервал. Наприклад, напроти інтервалу ( - 0 - 1 - ) символи “x” знаходяться в 1-му та 2-му стопці, що означає першу та другу комбінацію в таблиці F=1. Перебір закінчується тоді, коли вичерпані всі варіанти з поточною кількістю змінних і всі комбінації з F=1 входять в знайдені інтервали. В даному прикладі ми обмежились інтервалами з одною і двома змінними.
Для того, щоб знайти мінімальну логічну залежність, необхідно вибрати таку мінімальну кількість інтервалів, яка включає всі комбінації F=1. Логічна залежність знаходиться як диз’юнкція вибраних інтервалів. В даному прикладі існує декілька мінімальних множин інтервалів (див. рис.1). Розглянемо першу з них:
{10 - - -, 0 - 1 - -, 1 - - 0 -} відповідає логічному виразу: F = x1(x2 ((x1 x3 ( x1(x4.
Нуль на місті i-ї змінної в інтервалі відповідає її інверсії у логічному виразі. В результаті мінімізації в даному прикладі отримали 6 мінімальних виразів. Серед цих виразів вибираємо ті, які можна спростити, тобто, винести за дужки деякі змінні:
F = x1(x2 ((x1 x3 ( x1(x4 = x1((x2 ((x4 ) ((x1 x3
F = x1(x2 ((x1 x3 ( x3(x4 = x1(x2 ( x3 ((x1 ((x4 )
F =(x2 x4 ((x1 x3 ( x3(x4 = (x2 x4 ( x3 ((x1 ((x4 )
Ці вирази приймаємо за найбільш ймовірні логічні залежності в досліджуваній системі.
Контрольні запитання:
Що таке логічні залежності в системі?
Яка гіпотеза приймається при пошуку логічної залежності в системі?
Яка задача називається слабо визначеною?
Що таке інтервал комбінацій?
Як шукаються інтервали комбінацій?
Як знайти мінімальну множину інтервалів, що покриває задані комбінації?
Сформулювати алгоритм для знаходження слабо визначеної логічної залежності.
Тема 2. Суперечки в системах.
В попередній темі розглядався метод усунення суперечливого завдання логічної залежності в системі за допомогою введення в неї додаткових змінних. Існують також інші методи усунення суперечок в системі. Наприклад, можна знайти максимально несуперечливу множину комбінацій, які характеризують певну логічну залежність.
Множина P називається суперечливою, якщо в ній існують несумісні елементи. Поняття несумісності є базовим при дослідженні будь-якого конфлікту. Мінімально несумісною підмножиною множини P називається така несумісна підмножина, для якої виключення будь-якого елемента з цієї множини приводить до сумісної підмножини, а максимально сумісною підмножиною множини P називається така сумісна підмножина S, для якої введення будь-якого елемента з P перетворює S у несумісну підмножину.
Можна розглядати конфлікт як суперечливу множину. Цю множину можна однозначно задати переліком всіх максимально сумісних її підмножин, або переліком всіх мінімально несумісних її підмножин. Існує алгоритм, який дозволяє перетворювати максимально сумісні підмножини в мінімально несумісні, і навпаки. В системному аналізі елементами цих множин можуть бути не тільки елементи системи, але й дії, цілі, властивості.
Розглянемо решітку підмножин суперечливої множини з чотирьох елементів (рис.2).
Рис.2. Решітка підмножин 4-х елементної множини P.
Припустимо, що підмножини “1100” та “0111” є мінімально несумісними. Необхідно знайти максимально сумісні підмножини. Якщо з мінімально несумісної підмножини видалити один елемент (див. крок I на рис.3), то підмножина стане сумісною. На наступних кроках (II,III рис.3) треба добавляти елементи до тих пір, поки множина не стане несумісною. Якщо жодного елемента в комбінацію додати неможливо, то ця комбінація є максимально сумісною підмножиною. Описаний вище алгоритм представлений на рис.3.
Рис. 3. Пошук максимально сумісних підмножин через мінімально несумісні.
Нулі які з’явились в результаті заміни одиниць позначені символом “*” (зірочка). Максимально сумісні підмножини, які знайдені цим алгоритмом, виділені сірим кольором. Це комбінації: {1011, 0110, 0101}.
Алгоритм пошуку мінімально несумісних підмножин з максимально сумісних є двоїстим до алгоритму, що представлений на рис.3. Тобто, для знаходження рішення двоїстої задачі можна скористатись тим самим алгоритмом в послідовності, яка представлена на рис.4.
Рис. 4. Пошук мінімально несумісних підмножин через максимально сумісні.
Зробимо перевірку двоїстості алгоритму на прикладі отриманих раніше даних.
Рис. 5. Перевірка двоїстості алгоритму пошуку мінімально несумісних підмножин.
На рис.5 представлено знаходження мінімально несумісних підмножин через максимально сумісні, що були отримані на рис.3. Згідно зі схемою (рис.4), на першому кроці значення, які були отримані на рис.3 інвертуються. На другому кроці отримуємо комбінації за допомогою заміни одиниць на зірочки. Зірочка означає нуль, який не можна перетворювати на одиницю, інакше комбінація стане несумісною. На третьому кроці кожний нуль заміняється на одиницю і включається в граф пошуку (рис.5). В результаті утворюється частково-впорядкована структура, кінцевими елементами якої є коди, що складаються з одиниць та зірочок. В даному випадку – це (**11) та (1***). Після отримання цих кодів замінюємо всі зірочки на нулі. Для завершення двоїстого алгоритму необхідно інвертувати ці результати – отримуємо: (1100) та (0111), що співпадає з початковими даними алгоритму пошуку максимально сумісних підмножин (див. рис.3).
Контрольні запитання:
Які підходи існують до опису конфліктів?
Що таке мінімально несумісна підмножина?
Яка множина називається максимально сумісною?
Що таке двоїстість?
Як перейти від мінімально несумісної підмножини до максимально сумісної?
Як перейти від максимально сумісної підмножини до мінімально несумісної?
Що означає зірочка в пошуковому графі алгоритму?
Тема 3. Детермінізм та однозначність в системах.
Детермінованою називається така система, в якій кожний наступний стан однозначно залежить від попереднього. Однозначність в системах означає, що кінцевий стан системи однозначно залежить від початкового її стану, але однозначними можуть бути не тільки детерміновані системи. Отже, якщо система детермінована, то вона і однозначна, але не навпаки. Кінцевий стан системи може бути один і той самий, але шляхи його досягнення – різні. Система може бути однозначною навіть коли послідовність подій в системі буде випадковою.
Майже однакові на перший погляд поняття детермінованості та однозначності систем основані на абсолютно різних явищах. Детермінізм визначається одним законом чи алгоритмом функціонування системи, в якому немає місця випадковості (інакше втрачається детермінованість системи). Однозначність же задається ідеєю функціонування системи, яка може бути виражена множиною еквівалентних алгоритмів, які можна міняти при випадкових обставинах. Ідея може бути виражена правилом, яке описує всі еквівалентні алгоритми функціонування системи. Класичний приклад однозначних, але не детермінованих систем – це хімічні реакції.
Отже, система є однозначною, якщо при переході від одного стану до іншого вона не порушує певне несуперечливе правило (ідею функціонування). Тоді:
а) стійкий стан системи завжди можна трактувати як реалізацію ідеї функціонування;
б) якщо при певному початковому стані система не може перейти у стійкий стан, то ідея не є повною;
в) якщо система не є однозначною, то ідея функціонування містить протиріччя.
Розглянемо приклад абстрактної однозначної не детермінованої системи для обчислень на основі ідеї кодів Фібоначчі. Кодом Фібоначчі називається довільна послідовність символів {0,1}, в якій не зустрічається двох сусідніх одиниць. Наприклад: 010101, 010010, 1010001. Формально, такий код можна отримати зі звичайного двійкового коду, якщо дотримуватись ідеї про те, що дві сусідні одиниці заміняються однією одиницею. Тепер необхідно усунути деякі протиріччя, які можуть виникнути при реалізації такої ідеї.
Досить велику кількість задач вдається розв’язати на основі теорії чисел, тому що теорія чисел є ідею, яка не містить протиріч і багато об’єктів можна представити послідовностями чисел. Ряд Фібоначчі характеризується тим, що в ньому кожний наступний член є сумою двох попередніх, наприклад, (8 + 5 = (3, і т.д.:
{..., (21, 13, (8, 5, (3, 2, (1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21,... }
Кожний код Фібоначчі можна представляти як суму тих членів ряду, навпроти яких стоїть одиниця. Для однозначності представлення цілих чисел необхідно використовувати лише половину ряду, яка знаходиться зліва від нуля (перевірте значення у таблицях):
Додатні числа:
Від’ємні числа:
N =
13 -8 5 -3 2 -1 1
N =
13 -8 5 -3 2 -1 1
1
0 0 0 0 0 0 1
( 1
0 0 0 0 0 1 0
2
0 0 0 0 1 0 0
( 2
0 0 0 1 0 0 1
3
0 0 0 0 1 0 1
( 3
0 0 0 1 0 0 0
4
0 0 1 0 0 1 0
( 4
0 0 0 1 0 1 0
5
0 0 1 0 0 0 0
( 5
0 1 0 0 1 0 1
6
0 0 1 0 0 0 1
( 6
0 1 0 0 1 0 0
7
0 0 1 0 1 0 0
( 7
0 1 0 0 0 0 1
8
0 0 1 0 1 0 1
( 8
0 1 0 0 0 0 0
9
1 0 0 1 0 1 0
( 9
0 1 0 0 0 1 0
Якщо числа однозначно представляються кодами Фібоначчі, то однозначними повинні бути операції над ними. Ідея Фібоначчі описує нескінченну кількість еквівалентних перетворень типу: 2Fk = Fk+1+Fk(2 та Fn(2 + Fn(1 = Fn , наприклад: 5 + 5 = (3 + 13; (3 + 5 = 2.
Ці перетворення можна робити хаотично, тому система, яка буде відображати ці перетворення не є детермінованою. Незважаючи на хаотичність процесів застосування правил, жодне з застосованих правил не порушує ідею кодів Фібоначчі, і в решті решт ми отримуємо однозначний результат арифметичної операції у вигляді коду Фібоначчі.
Ідею обчислень в кодах Фібоначчі можна представити правилами на клітинній площині, на якій коди знаходяться горизонтально і один над одним (див. рис. 6):
Рис. 6. Правила обчислення суми для чисел, що представлені кодами Фібоначчі.
Приклад обчислення виразу 7+3(4 = 6 в кодах Фібоначчі наведений на рис.7.
Рис. 7. Приклад стохастичного процесу в однозначній системі.
Як видно з рис.7, на кожному кроці стохастичного процесу загальна сума відмічених одиницями членів ряду не змінюється, і в кінці залишається мінімальна кількість одиниць.
Контрольні запитання:
Що таке детермінована і не детермінована система?
Що таке однозначна система?
Чи може бути не детермінована система однозначною?
Чи є детермінована система однозначною?
Чим відрізняється ідея функціонування від закону функціонування?
Які припущення довелося зробити, щоб створити однозначну систему кодів Фібоначчі?
Що таке реалізація ідеї функціонування?
Тема 4. Причинність подій в системах.
Причинність – це залежність виникнення подій від певних причин. В стохастичній системі, де події відбуваються випадково, також існує причинність, але причини в ній є настільки складними, що події здаються випадковими. Прикладом такої системи може бути система для обчислення будь-якого розряду числа (. Теорія причинності стверджує, що випадковість з’являється там, де не вистачає інформації. Основний фактор, який заважає зрозуміти причину події – це час, який стоїть між причиною і подією. Невизначеність в часі дозволяє створити стохастичну систему лише з детермінованих елементів. Недетермінізм таких в системах виникає тоді, коли елементи спрацьовують не одночасно, і в залежності від того, який ми приймемо порядок їх спрацьовування, буде визначений подальший розвиток подій в системі (якщо система не однозначна). Найпростішою моделлю, яка відображає причинність у не детермінованих системах з детермінованими елементами, спрацьовування яких не визначено в часі, є мережі Петрі.
Мережа Петрі складається з елементів двох типів – теоретично можливих подій та необхідних умов для їх виникнення. Події та умови позначаються по різному. Теоретично можливі події позначаються як пусті кружечки і називаються місцями. На рис.8 місця позначені через змінні A1, A2, A3, A4. Умови виникнення подій позначаються як прямокутні бар’єри і називаються переходами (позначені через P1, P2, P3).
Рис. 8. Мережа Петрі, яка виражає причинність та теоретично можливі події.
Переходи та місця з’єднуються ребрами таким чином, що кожне ребро обов’язково з’єднує місця з переходами, тобто, не існує двох безпосередньо з’єднаних між собою місць або переходів. Така умова з’єднань відображає твердження про те, що кожна подія повинна мати свою умову виникнення.
Для того, щоб оживити цю модель системи необхідно ввести початкові дані, які виражають наявність причин для спрацьовування того чи іншого переходу. Такі причини позначаються через так звані фішки. На рис.8 вони позначені чорними кружечками в середині місць A1 і A3. Для кожного переходу існують як вхідні, так і вихідні місця, в залежності від того, в яку сторону (до нього чи від нього) направлено зв’язане з ним ребро. Умова для виникнення події вважається достатньою, якщо кожне вхідне місце переходу, який символізує цю умову, має свою фішку. Початкове розташування фішок на місцях називається розміткою мережі.
Спрацьовування переходу – це елементарний процес в мережі Петрі. Кожне спрацьовування змінює розмітку мережі наступним чином: з кожного вхідного місця забирається по одній фішці, а в кожне вихідне місце додається по одній фішці. Недетермінізм даної моделі полягає в тому, що переходи спрацьовують в довільному порядку. Якщо два чи більше переходів можуть спрацювати і вони не мають спільних місць, то їх спрацьовування є незалежними діями, які виконуються в довільній послідовності або одночасно. Якщо переходи мають спільне вхідне місце, то спрацьовує один з переходів. Після спрацьовування фішка забирається з вхідного місця і таким чином зникає причина для спрацьовування другого переходу. Якщо переходи можуть спрацювати та вони не мають спільних вхідних фішок, то їх спрацьовування є незалежними діями, які можуть виконуватися в будь-який момент в довільній послідовності або одночасно. Якщо декілька переходів можуть спрацювати і вони мають спільну вхідну вершину, то спрацьовує лише один з них.
Після спрацьовування може статися, що цей перехід заборонить спрацьовування інших переходів, що моделює конфліктну ситуацію в мережі, коли реалізація однієї події виключає можливість інших подій – виникає несумісна множина подій.
Розглянемо приклад. В даній мережі Петрі існує дві фішки – у вершинах A1 та A3 . В даній ситуації, яка позначається вектором (1,0,1,0) може спрацювати лише перехід P1. Після спрацьовування P1 мережа Петрі перейде в стан (1,1,0,0), тобто перехід одиниці з 3-го місця на друге означає, що фішка перейде з вершини A3 у вершину A2 . Граф функціонування мережі також представлений на рис. 8.
Мережі Петрі також можуть бути абстракцією динамічної системи в тому розумінні, що переходи відповідають подіям в системі, а місця – умовам наставання подій. Подія – це деякий факт в системі, що трактується як потенційна дія компонента системи, яка може відбутися один або декілька разів, або не відбутися взагалі.
Контрольні запитання:
Що таке причинність в системі ?
Що заважає зрозуміти причинність в системах ?
Чи може не детермінована система бути побудована з детермінованих елементів і чому ?
Що таке мережа Петрі ?
Як працює мережа Петрі ?
Що таке розмітка мережі Петрі ?
Як побудувати граф функціонування мережі Петрі ?
Тема 5. Відображення та ізоморфізм систем.
Для дослідження систем можна використовувати формальні системи правил. Якщо дві системи описуються однією системою правил, то ці системи називаються ізоморфними відносно цієї системи правил. Можна сказати, що в основі кожної реальної системи лежить певна формальна система зі своїми правилами. Правила задаються граматикою, яка визначає, чи це правило правильно побудоване. Найважливішим для системного аналізу в цьому є те, що з формальної системи можна зробити формальні висновки, які можна інтерпретувати на реальних системах, які були формалізовані.
Для прикладу дослідження ізоморфних систем розглянемо формальне представлення групи підстановок. Підстановкою називається відображення множини в себе (див.рис.9).
Коли система представляється за допомогою граматики з певними правилами Теорія груп є найпростішою алгеброю, бо має всього одну операцію. Теорія груп є одною з абстрактних алгебр що лягли в основу теорій алгоритмів і перетворень текстів програм, які значно полегшують проектування програм.
, то виникає ефект ізоморфізму, пов’язаний з тим, що граматика не відображає природу систем, а відображає лише властивості понять, з якими оперує система відносно інших понять. Ці властивості також можуть бути представлені правилами спеціалізованих граматик. Дослідження ізоморфних систем дозволяє знайти обмеження і недосконалості системи правил, що їх описує. Для розгляду ізоморфних систем візьмемо найпростіші алгебраїчні системи.
Алгебраїчна система, в якій визначена одна єдина операція “(”, що ставить у відповідність двом довільним елементам A і B системи S елемент C цієї системи ( позначається як C ( A(B ), називається групою, якщо:
Для будь-яких елементів A,B,C операція є асоціативною: (A(B)(C ( A((B(C) ( A(B(C ;
Існує один єдиний нейтральний елемент E такий, що для довільного елемента A ( A(E ( E (A ; E (E ( E ;
Для довільного елемента A існує один єдиний обернений елемент A(1 відносно операції групового множення: A((A(1 ) ( (A(1 ) (A ( E ; E(1 ( E.
Якщо для довільних A і B групове множення комутативне A (B ( B (A, то група називається абелєвою.
В теорії груп природа операції групового множення не суттєва. Завдяки цьому можна робити висновки про поведінку об’єктів одної природи, досліджуючи об’єкти зовсім іншої природи. Наприклад, більшість алгебраїчних перетворень, якими оперують в теорії чисел можна перенести для теорії матриць. Отже, для довільних груп можливі перетворення виразів за законами алгебри незважаючи ні на природу об’єктів, ні на природу операцій над ними.
Розглянемо простий приклад, який дозволяє зрозуміти що таке група, розглянувши групу комутаторів. (Див. малюнок).
В цій групі під груповим множенням комутатора A на комутатор B будемо розуміти з’єднання цих комутаторів так, як показано на малюнку. Отже, запис C ( A(B означає, що два з’єднаних комутатора A і B можна замінити одним комутатором C. Для знаходження оберненого комутатора необхідно дзеркально поміняти входи з виходами. Таким чином, якщо комутатор замінений ланцюгом інших комутаторів, то необхідно дзеркально відобразити весь ланцюг:
Формально, це відображено формулою: C(1 ( (B(1) ( (A(1). Зауважте, що в цьому прикладі B(1 ( B; A(1 ( A; C(1 ( C. Таким чином, група не абелева. Для знаходження інших елементів групи комутаторів необхідно виконати множення за ітерацією алфавіту {A, B}* = A(A, A(A(A, ...,B (B, B (B (B,...,A(B,...,A(B (A(B,...,B (A(B (A,... і включати нові елементи, що утворилися, до групи. В нашому прикладі цей процес дає ще два нових елемента:
Якщо позначити елемент C(1 через F, то можна побудувати граф утворення групи через елементи A, B. Отже, елементи A, B називаються утворюючими елементами для даної групи. Якщо з множини утворюючих елементів даної групи можна виключити один елемент, то множина утворюючих елементів є надлишковою. Групи, які можна утворити одним елементом називаються циклічними. В даній групі мінімальна кількість утворюючих елементів дорівнює 2.
Очевидно, що елемент E є нейтральним. З нього і почнемо будувати граф утворення групи, який в подальшому будемо називати діаграмою Келі:
Діаграма Келі складається з ребер двох типів: A (позначені товстими лініями) і B (тонкі лінії). В даному прикладі лінії двохсторонні, тому що B(1 ( B; A(1 ( A.
Цю ж саму групу можна отримати, якщо за утворюючі комутатори вибрати A і C. Тоді діаграма Келі зміниться наступним чином (див. малюнок). Кожна пара ребер A(B з’єднується ребром типу C, а всі ребра типу B забираються.
Після такого перетворення (малюнок зліва) можна перемалювати діаграму у більш звичному вигляді (малюнок справа), хоча симетричні властивості цих графів однакові. Для перевірки діаграми знайдемо на ній довільний замкнутий шлях, наприклад, C (A (C (A ( E і виконаємо відповідні з цим виразом з’єднання комутаторів:
Кожну діаграму Келі, можна представити у симетричному вигляді, наприклад, розмістивши її вершини на сфері. Це означає, що вона може бути суміщена сама з собою при повороті на певний кут навколо центра цієї сфери. В даному прикладі симетричні повороти можливі навколо просторових осей (, (, ( :
Повороти діаграми навколо осей (, (, ( можна розглядати як деякі операції над статичною системою, якою є діаграма. Відносно поворотів обидві діаграми володіють такими ж самими властивостями, як і комутатори, які утворили ці діаграми. Наприклад, повороти лівої діаграми можуть бути представлені наступними комутаторами:
Дані комутатори утворюють групу з 6-ти елементів:
Отримана група поворотів діаграми ізоморфна початковій групі комутаторів. Отже, поняття ізоморфізму можна сформулювати так. Якщо кожному елементу групи G1 можна поставити у відповідність один елемент групи G2 так, що результат групового множення між кожною парою елементів групи G1 відповідає результату множення відповідних їм елементів групи G2, то групи G1 і G2 ізоморфні. При тому, в групах G1 і G2 операції групового множення можуть бути зовсім іншої природи (в групі G1 – з’єднання комутаторів, а в G2 – поворот навколо осі).
Кожна група може бути представлена таблицею множення. Таблиця множення групи несе інформацію про те, який елемент утворюється при множенні двох заданих елементів. Вона повністю складається з індексів елементів групи, а саме: якщо для деяких елементів групи вірна рівність: Pk=Pi(Pj, то елемент таблиці множення з координатами (i, j) буде рівний k. Наприклад, для групи, що утворилася з елементів {A,B} таблиця множення виглядає так :
A
B
C
D
E
F
A
E
C
B
F
A
D
B
F
E
D
C
B
A
C
D
A
F
B
C
E
D
C
F
A
E
D
B
E
A
B
C
D
E
F
F
B
D
E
A
F
C
Таблиця множення групи завжди квадратна, і має розмір M x M, де M - кількість елементів групи. Кожен рядок і кожен стовпець таблиці множення містять всі індекси від 1 до M без повторень. Рядки (а також стовпці) таблиці множення не повторюються. Таблиця завжди має таку стрічку T(E,*) та такий стовпець T(*,E), який відповідає одиничному елементові: T(E,*) = T(*,E) = 1,2,3,4,...,M.
Дві таблиці однакового розміру вважаються еквівалентними, якщо одну таблицю можна отримати з другої методом одночасної перестановки рядків та стовпчиків. Таблиці множення ізоморфних груп еквівалентні.
Якщо кожен рядок або стовпець таблиці множення представляти як комутатор (або підстановку), то група, яка задається заданою таблицею за теоремою Келі ізоморфна цій групі комутаторів.
Оборотне відображення скінченої впорядкованої множини M в себе називається підстановкою елементів множини M. Підстановка позначається наступним чином:
P1 : (1 2 3 4 ( P2 : (1 2 3 4 (
(2 1 3 4 ( (1 4 2 3 (
Перша підстановка міняє місцями елементи {1,2}, а друга – переставляє по колу елементи {2,3,4}.
Ключовим поняттям в теорії підстановок є композиція елементів. Результат композиції двох довільних підстановок належить цій групі підстановок. Позначається це так: P(k)=P(i)(P(j), де групове множення означає композицію підстановок.
Декілька підстановок можуть утворювати групу підстановок.
Приклад утворення групи підстановок для N=4. Візьмемо дві довільні підстановки P(1) і P(2):
P(0): 1,2,3,4 - Тотожня перестановка ( елементів не переставляє ).
P(1): 2,1,3,4 - Перша початково вибрана перестановка (вона міняє місцями елементи 1 і 2).
P(2): 1,4,2,3 - Друга початково вибрана перестановка (переставляє по циклу елементи 2,3,4 ).
P(3): 4,1,2,3 - Перестановка, яка отримана композицією (груповим множенням) P(1) x P(2) за алгоритмом:
Взято 2 - перший елемент із P(1), знайдено другий елемент з P(2) і отримано 4 в P(3);
Взято 1 - другий елемент із P(1), знайдено перший елемент з P(2) і отримано 1 в P(3);
Взято 3 - третій елемент із P1, знайдено третій елемент з P(2) і отримано 2 в P(3);
Взято 4 - четвертий елемент із P(1), знайдено четвер. елемент з P(2) і отримано 3 в P(3);
P(4): 2,4,1,3 - перестановка, яка отримана композицією P(2) x P(1).
P(5): 4,2,1,3 - перестановка, яка отримана композицією
P(3) x P(1) = P(1) x P(2) x P(1).
P(6): 3,1,4,2 - перестановка, яка отримана композицією
P(3) x P(2) = P(1) x P(2) x P(2).
Якщо виконувати всі можливі композиції елементів, то отримаєте групу з 24 різних елементів.
4. Кожна група перестановок може бути утворена певною кількістю породжуючих перестановок. Наприклад, композицію елементів P(5) і P(4) можна представити так:
P(5) x P(4) = P(1) x P(2) x P(1) x P(2) x P(1).
Якщо вся група може бути породжена однією перестановкою, наприклад, P(1), то вона називається циклічною групою. Ми будемо далі розглядати групи, які породжуються мінімум з двох перестановок.
5. В даній лабораторній роботі ви вибираєте дві довільні породжуючі перестановки і виконуєте композиції P(k)xP(1) і P(k)xP(2) до тих пір, поки нові елементи групи (перестановки або комутатори) не будуть утворюватись. За теоремою Жозефа Луі Лагранжа кількість елементів M скінченної групи може бути тільки дільником N факторіал.
Для нашого випадку (N=4) ви можете отримати тільки групи, що скла даються з 2,3,4,6,8,12,24 елементів.
В запропонованому курсі лабораторних робіт ви зможете навчитись системно аналізувати прості алгебраїчні об’єкти та операції над ними. Ви навчитесь проводити аналогії між на перший погляд різними парадигмами: теорією перестановок і теорією матричного числення.
За допомогою Ейлеревих матриць ви зможете оперувати трьохмірним простором, а також будувати просторово симетричні графи, які лягли в основу швидкого перетворення координат в комп'ютерній графіці, аналізу молекулярних структур в хімії, архітектури обчислювальних мереж, тощо.
Автори сподіваються, що цикл лабораторних робіт не перевантажений термінологією. Алгоритми є прозорими і не складними для розуміння, при умові, що роботи виконуються послідовно.
Завдання
18.02.2013 18:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора