Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Технологія виділення програми – представника для класу еквівалентності




Якщо є графи Г1 і Г2, то вони гомоморфні (ізоморфні), якщо існує φ:Г1→Г2, яке являється однозначним (взаємооднозначним) і при якому зберігається орієнтація дуг. Якщо графи ізоморфні, то вони однакові. Якщо між вершинами одного і того ж графа вдається встановити ізоморфне відображення, то його можна скоротити за рахунок того, що ці лінійні зв’язки можуть бути замінені однією дугою (замість сукупності двох), які будуть мати навантаження (для відображення лінійних дуг). Вважається, що вершина графа ізольована, якщо вона не має зв’язків з іншими вершинами, але може мати зв’язок сама з собою. При підрахунку рангу цей зв’язок враховується. Важливим в аналізі є: зв’язність, ізольованість, max ранг вершини. Два автомати А1 і А2 називаються еквівалентними, якщо між графами, що відповідають цим автоматам Г1 і Г2 існує гомоморфне відображення. А1 і А2 сильно еквівалентні, якщо графи Г1 і Г2 – ізоморфні з точністю до лінійних частин. Лінійна частина графу – його шляхи. Шлях – частина графу, в якій немає петель, розгалужень і циклів. Якщо автомати еквівалентні, то їх графи можна спростити. PK=UK~, UK~ - клас еквівалентності. Нехай маємо PK, що складається з 20 процедур. По признаку еквівалентності виділили тільки 7 класів еквівалентності, тобто в кожному класі еквівалентності кожну процедуру можна взяти за представника класу еквівалентності. Скільки класів – стільки і процедур.

      K1                         K2

 


                                                          

                                                   

                                               

         

      n+1

P1 є К1, Р2 є К2, Р2 є К1

                               

                         еквівалентні











Последнее изменение этой страницы: 2018-04-12; просмотров: 580.

stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...