Модулна структура
При създаването на една голяма програмна система отделните програмни фрагменти са групирани в M модула. Фрагментите ще означаваме с естествените числа 1,2,...,N, а модулите – със списъците на фрагментите им. Между някои модули, както и между някои фрагменти на един модул съществуват ориентирани връзки, на които са присвоени цели положителни тегла, определящи доколко “сложна” е връзката. На Фиг. 1 е показана модулната структура на една система, която се състои от четири модула (правоъгълници) и девет фрагмента (кръгчета). Както се вижда от фигурата, във вътрешността на един модул са възможни две организации на фрагментите – последователна, например в модулите “1,3,2” и “9,4”, или паралелна, например в модула “5,6,8”. Когато един модул съдържа само един фрагмент, например модула “7”, неговата организация е неутрална и може да се счита както за последователна, така и за паралелна. Списъкът на последователен модул следва наредбата на фрагментите, докато в списъка на паралелен модул елементите са подредени в нарастващ ред на номерата. Когато една връзка “влиза” в последователен модул, тогава тя отива в първия от фрагментите му, а когато “излиза” – излиза от последния. Когато една връзка “влиза” в паралелен модул, тогава тя отива във всеки от фрагментите му, а когато “излиза” – излиза от всичките.
фиг.1 фиг.2
За модулната структура на програмата са важни две противоположни една на друга статични (не свързани с изпълнението на програмата) характеристики – кохезия C и обвързаност O. Колкото по-малко е средното количеството фрагменти за модул, толкова по-добра е кохезията. Колкото по-малка е сумата от теглата на междумодулните връзки – толкова по-добра е обвързаността. Ако всеки фрагмент е разположен в отделен модул, тогава кохезията е най-добра, а обвързаността – най-лоша. Ако всички фрагменти са разположени в един и същ модул, тогава кохезията е най-лоша, а обвързаността – най-добра. Разбира се, че една програмна система се счита за добре структурирана, ако двете характеристики са разумно балансирани. Задачата е да се направи програма BALANS.EXE, която по зададена модулна структура на програмна система да намери еквивалентна модулна структура с колкото може по-добър баланс.
При балансиране на зададената структура са възможни следните преобразования:
- разбиване на модул (последователен или паралелен) на два модула. Преобразованието се задава с оператора split f, където f е номер на фрагмент, който не е последен в списъка на модула. При последователна организация (вж. Фиг. 3.а), в единия модул остават фрагментите, които предхождат f и самият f, а във втория модул – фрагментите, които са след f в списъка. При разбиване на последователен модул всички връзки, влизащи в него остават да влизат в първия модул на резултата, а всички излизащи – излизат от втория. Връзката между фрагмента f и следващия в списъка g става връзка между новите два модула. При паралелна организация (вж. Фиг. 3.б) в първия модул остават фрагментите с номера по-малки или равни на f, а във втория – фрагментите с номера по-големи от f. При разбиване на паралелен модул всички връзки, влизащи в него се дублират и влизат и в двата модула на резултата, а всички излизащи се дублират и излизат от двата модула на резултата.
- обединяване на два модула (или и двата последователни или и двата паралелни) в нов модул – последователен, ако се обединяват последователни модули и паралелен, ако се обединяват паралелни. Преобразованието се задава с оператора join f g, където f и g са номера на фрагменти от различни модули. При обединяване на модули всички връзки, влизащи в поне един от двата модула влизат в резултата, като еднотипните (с едно и също начало) се обединяват в една нова с тегло равно на сумата от теглата на старите. Всички връзки, излизащи от поне един от двата модула излизат от резултата, като еднотипните (с един и същ край) се обединяват в една нова с тегло, равно на сумата от теглата на старите.
Фиг. 3.а Фиг. 3.б
Можем да обединим два последователни модула или последователен и неутрален (вж. Фиг. 4.а), само когато имаме връзка от единия към другия. При обединението на последователни модули f е номер на фрагмент, който е последен в списъка на първия модул, а g е номер на фрагмент, който е първи в списъка на втория модул. При обединяването връзката между f и g престава да бъде междумодулна, но остава междуфрагментна връзка. Можем да обединим два паралелни модула или паралелен и неутрален (вж. Фиг. 4.б), когато няма връзки между тях, но съществуват връзки от трети модул към двата. При обединяване на паралелни модули фрагментите от обединението на двата списъка се сортират, за да се получи списъкът на резултата. Ако се обединяват неутрални (еднофрагментни) модули между които има връзка, резултатът е последователен модул, като наредбата на двата фрагмента следва ориентацията на връзката. Когато се обединяват неутрални модули, между които няма връзки (но съществуват връзки от трети модул към двата), тогава резултатът е паралелен, като двата фрагмента в резултата се сортират.
фиг. 4.а фиг. 4.б
За оценяване
на баланса се използват следните формули. Нека M
е текущия брой на модулите, като n1 модула на структурата са
с по i1 фрагмента, n2 модула са с по i2
фрагмента,…, nk модула са с по ik
фрагмента. Тогава кохезията на структурата е 
. Нека Sm е сумата от
теглата на всички междумодулни връзки на структурата, а S е сумата от
теглата на всички връзки. Тогава обвързаността на структурата е 
. Балансът измерваме
със сумата C+O на двете характеристики. За структурата от Фиг. 1
кохезията е 
,
а обвързаността 
.
Значи балансът й е 
.
Да приложим към структурата от Фиг. 1 операциите split 9 и join
2 9. Получаваме структурата от Фиг. 2, балансът на която е 
, т.е. значително
по-добър.
Входните данни са зададени в текстов файл BALANS.INP. Първият съдържа целите положителни числа N (3<=N<=1000) и М (3<=M<=N), разделени с един интервал. Всеки от следващите M реда описва един от модулите. Ако модулът е с паралелна структура, редът започва с буквата P, последвана от броя B на фрагментите и списъка от B фрагменти, подредени в нарастващ ред на номерата. Ако модулът е последователен, редът започва с буквата S, последвана от броя B на фрагментите и списъка от 2.B–1 цели положителни числа – B фрагменти и B–1 тегла на връзките, като теглото на два съседни фрагмента е поставено между номерата им. Следващият ред на входа съдържа само броя L на междумодулните връзки. Всеки от последните L реда на файла описва една междумодулна връзка и съдържа три положителни цели числа F, T и W, където F и T са номерата на началния и крайния модул, а W е теглото на връзката. Теглата не надвишават 1000. Номерата на модулите се присвояват (започвайки от 1) в реда, по които описанията им са поставени във входния файл.
Програмата трябва да извежда в текстовия файл BALANS.OUT последователност от коректни оператори (всеки на отделен ред) за преобразуване на структурата. Последователността трябва да завършва с оператора stop.
При некоректна последователност от преобразуващи оператори, точки за съответния тест не се присъждат. При коректна последователност се пресмята балансът на резултата. Програмите, които са получили най-малка балансова стойност ще получат пълния брой точки, определен за теста. Останалите програми ще получат брой точки, пропорционален на големината на резултата.
Пример
Вход – BALANS.INP:
9 4
S 3 1 4 3 1 2
P 3 5 6 8
S 2 9 1 4
P 1 7
4
1 2 2
1 3 5
2 3 3
2 4 4
Възможен Изход – BALANS.OUT:
split 9
join 2 9
stop