Ҳисоблаш тизимсининг ахборот асослари

12.3. Функционал алоқалар кетма-кетлигини ўзгартирилиши. 
Агар ФА кетма-кетлиги фақат бир ўлчамли алоқалардан ташкил топган 
бўлса, унда у ўзгартиришни талаб қилмайди. Агар кетма-кетликда кўп 
ўлчамли ФАлар аниқланган бўлса, унда бу алоқаларни оддийроқ кўринишига 
ўзгартириш керак бўлади. Ушбу ўзгартириш ва уларни ўтказиш алгоритмини 
кўриб чиқамиз. Даставвал бир қатор таърифларни киритамиз. 
1-таъриф. ФА тўпламининг иккита 
F
1
, F
2
, ... , F
k
ва F
1
'
, F
2
'
, ..., F
m
' 
тўплами айниятли дейилади, агар улар бажарилиши натижалари, сўровда 
берилган объект экземплярларга мос келади 
F
1
, F
2
, ... , F
k
F
1
'
, F
2
'
, ..., F
m
' 
2-таъриф. А
1
, А
2
, ... , А
k
объектларнинг тартибланган тўплами 
объектлар занжири дейилади, агар исталган i 1 i k-1 учун 
Т ( А
i
, A
i+1
) = 1 : M 
бажарилг ан бўлса. 
Масалан, УНИВЕРСИТЕТ, ФАКУЛЬТЕТ, СТУДЕНТ объектлари 
занжирни ташкил этадилар. 
 
 
3-таъриф.

---

84 
A
1
A
2
A
k-1
F , F , . . . , F 
A
2
A
3
A
k 
кўринишидаги ФА тартибланган тўплами, ФА занжири дейилади, агар А
1
, 
А
2
, ... , А
k
- объектлар занжири бўлса. 
ФА кетма-кетлигини ўзгартириш жараёни ушбу кетма-кетликни 
айниятлига алмаштиришдан иборат. ФА кетма-кетлигини ўзгартириш 
алгоритмнинг блок-схемаси 4-расмда келтирилган. 
1-ўзгартириш. Агар кўп ўлчамли 
А
1
, А
2
, ... , А
N
F (1) 
B 
ФА бошланғич объектлари орасида А
1
, А
2
, ... , А
N
объектлар занжирини 
белгилаш мумкин бўлса, унда бундай кўп ўлчамли ФАни айният ФА 
тўпламига таққослаш мумкин: 
А
1
, А
2
, ... , А
N
А
1
А
2
А
k-1
А
k
, А
k+1
, ... , А
N
F F , F , ... , F , F 
B А
2
А
3
А
k
B 
Бошланғич объектлар занжирини белгилаш учун мувофиқлик типлари 
жадвали тузилади. Унда мисол қуйида келтирилаётган 4та бошланғич 
объектлари учун, масала қуйида келтирилган (4-жадвал). 
Бошланиши 
ФАни таҳлили 
Йўқ бошлан- 
ғич занжиз бор- 
ми? 
Ҳа 
1-ўзгартириш 
Ҳа Барча- Йўқ 

---

85 
A си бир ўлчам- 
лими? 
ФАни таҳлилини 
давом эттириш 
Йўқ Т(бош,ох) 
=1:М 
Ҳа 
1-ўзгартириш 
2-ўзгартириш 
Ҳа Бар- Йўқ 
А часи бир ўлчам 
лими? 
 
 
ФАни таҳлилини 
давом эттириш 
 
Йўқ бошл. 
А занжири бор 
эдими? 
Ҳа 
3-ўзгартириш 
 
А  
Тамом 
4-расм. Кўп ўлчамли ФАни айниятли алоқалар тўпламига 
ўзгартириш алгоритмнинг блок-схемаси. 
4-жадвал. 

---

86 
Бошланғич объектлар А
2
А
3
А
4
А
1
Т(А
1
, А
2
) Т(А
1
, А
3
) Т(А
1
, А
4
) 
А
2
Т(А
2
, А
3
) Т(А
2
, А
4
) 
А
3
Т(А
3
, А
4
) 
Ушбу жадвалининг ҳеч бўлмаганда битта катагида мувофиқлик типи М 
: М дан фарқ қилса, унда бошланғич объектлар орасида занжирни танлаш 
мумкин. Ҳақиқатдан ҳам, А
i
ва А
j
(1 i < j N) объектлари учун Т(А
i
, A
j
) = 
1 : M берилган бўлса, унда таъриф бўйича улар занжирни ташкил этадилар. 
Агар Т(А
i
, A
j
) = М : 1 бўлса, унда Т(А
j
, A
i
) = 1 : M ва бундай А
j
, A
i
- занжир.
Дастлабки кўп ўлчамли ФАни (1) кўринишига келтириш учун, уни 
бошланғич объектларни қайта қўйиш натижасида олинган айниятли алоқа 
билан таққослаш етарлидир. 
2-ўзгартириш. Агар кўп ўлчамли ФАнинг бошланғич объектлари
А
1
, А
2
, ... , А
N
F
B 
орасида шундай объект мавжуд бўлса, унинг учун Т(А
1
, В) = 1 : М 
мувофиқлик типи бўлса, бунда бу кўп ўлчамли алоқа айниятли ФА тўплами 
билан таққосланади: 
А
1
, А
2
, ... , А
N
А
2
, ... , А
N
В 
F F , F
B B А
1
Агарда бошланғич ФА фақат икки бошланғич объектларидан иборат 
бўлса, унда унга икки айният тўпламидан бирини таққослаш мумкин: 
А
1
, А
2
А
1
В А
2
В
F F , F F , F
B B А
2
B А
1
Юқорида келтирилган ўзгаришларни бажариш натижасида кўп 
ўлчамли ФА олинган бўлса, агар у кейинги ўзгартиришларга йўл қўйилмаса, 
унда бошланғич объектлар орасида мувофиқлик типи фақат М : Мга тенг 
бўлади, исталган бошланғич ва охирги объектлар орасида 1 : Мга тенг эмас. 
Бундай кўп ўлчамли ФАни каноник кўринишга келтирилган деб атаймиз. 
4-таъриф. Қўйидаги ФА занжири берилган бўлсин:
А
1
А
2
А
k-1

---

87 
F , F , ... , F
А
2
А
3
А
k
Унда 
А
k
А
3
А
2
F , ... , F , F
А
k-1
А
2
А
1
кўринишидаги тартибланган алоқалар тўпламини юқорида кўрган ФА 
занжирига тескари деб атаймиз. 
3-ўзгартириш. Агар баъзи бир кўп ўлчамли ФАни ўзгартириш 
жараёнида бошланғич объектларнинг бирдан кўп занжири белгиланган 
бўлса, унда ФАдаги кетма-кетликда натижавий бўлиб ушбу занжирлардан 
бири сақланади, қолганлари эса тескари тўпламига алмаштирилади. 
Иккинчи ўзгартириш бажарилгандан кейин, А
i
объекти бошланғич 
объектлар занжири
B 
F га 
А
i
кирганлиги текширилади. Агар кирган бўлса, унда бу объектлар занжирига 
мувофиқлик ФА занжири алоқаларининг тескари тўплами билан 
алмаштирилади.