Қазақстан республикасы білім және ғылым министрлігі «АҚпараттық ЖҮйелер және моделдеу»



бет16/56
Дата09.06.2022
өлшемі1.96 Mb.
#267237
1   ...   12   13   14   15   16   17   18   19   ...   56
Байланысты:
354184 (1)
Негізгі әдебиеттер: 1 осн. [16-35], 13 доп. [45-51], 4 осн. [181-259, 109-179]
Бақылау сұрағы:

  1. Уақыт бойынша бөліну қатынауы әдісін сипатта және қандай жағдайда берілген әдіс қолданылады?

  2. Маркер дегеніміз не?

  3. Қандай жағдайда жұмыс істеу станциясы мәліметтерді жіберу қатынауының әдісі бойынша бастайды?

  4. Өкілділік қатынау әдісімен берілуді сипаттаңыз?

  5. Жиілік бөлінуі бойынша берілген қатынауды сипаттаңыз?

  6. Бөлшекті қатынау көптігінің нұсқалары қандай?

11, 12 Дәріс. Желілерді құру әдістері.
Дәрістің мақсаты: Желілерді құру әдістерімен танысу
Тақырыпта қарастырылатын сұрақтар:

  1. Бұтақ тәріздес желіні құру әдісі. С-алгоритмы

  2. Жұлдызша тәріздес желіні құру әдісі

  3. Сақиналық құрылымға С-алгоритмінің модификациясы (ССМ)

1 Бұтақ тәріздес желіні құру әдісі.


С-алгоритмы келесідегідей жұмыс істейді. Біріншіден негізгі минималды ішкі графигі құрылады, әрі қарай Xi (i M) әрбір төбесі үшін жақын тұрысын байлансқан ақпаратты беру кезінде минималды шығын жіберетін.
Xj(j i.j M) төбелерін табамыз. Бұл кезде алгоритмның барлық операциялары шығындар матрицасында өңделеді.
Егер минималды ішкі графиктағы Xi және Xj төбелері байлансқан болса, онда айнымалы Xij=1 болады, кері жағдайда Kij=0. Алынған минималды негізді Gp ішкі графы осы графтың ең қысқа негізі болатындығын анықтау факты үшін, Х айнымалысын бірге тең мәндерінің санын анықтасақ жеткілікті, ол келесі шарт бойынша тексеріледі N=2 (m-1).
Егер теңдік орындалса, онда алынған шкі граф G графигінің ең қысқа негіз болып табылады. Басқа жағдайда төбелердің ең қысқа негіз графпен байланысы, яғни берілген шарт тексеріледі, онда берілген графтың төбесінің кез-келгені тек бір ғана тізбекпен байланысуы керек шарты орындалуы керек. Ол үшін біріншіден граф төбесінің дәрежесі есептеледі, содан кейін дәрежесі бірден үлкен саны бар төбелер байланысы тексеріледі. Егер лоардың арасында байланыспаған төбелер кездессе, онда олар байланыстыратын көптеген жолдар арасынан (циклға алып келетін жолдар есептелмейді) бірғана салмағы минималды жол таңдалады. Бұл кезде осы жолға сәйкес келетін айнымалылыар бірге теңестіріледі.
Әрі қарай, байланыспаған төбелердің барлығымен осылай істейміз. Содан кйін N=2(m-1) шартын қайтадан тексереміз. Егер бұл шарт орындалмаса онда изоляцияланған қабырғаларды іздеу жүргіземіз ондағы, ақарлы төбелер дәрежесі бірге тең және графтың басқа төбелерімен байланспаған болуы керек. Бүл жағдайда төбелер келесі
Шартты қанағаттандруы керек, Xij=Xij=1, ал қалған айнымалылар Xir=Xjl=0
(k i,j=l,k Mi,l Mj).
Изоляцияланған қабырға болған жағдайда оның әр төбелеріне мөлшері ең аз төбелер табылады,содан кейін min(Cik*,Cjl*)=Cik* және Хі-2-ші төбе
Хк-и-ші төбемен қосылады. Осы әдісті басқада изаляцияланған қабырғаларға қолданылады. Осы процесс N=2(m-1) болғанша жалғаса береді.
С-алгоритмді мысал бойынша қарастырайық. 1-ші суретте көрсетілген желіні С-алгоритмі көмегімен аптимизация жасау керек



1-сурет. Негізгі граф

Осы желі үшін салмақ матрицасын құрайық (1 кесте). Салмақ матрицасы екілік массив болып табылады. Осы матрицаның элементтері аөпарат беру жылдамдығы болып табылады. Әр элемент өз-өзімен байланыс жасай алмағандықтан бас диоганалда жатқан элементтер 0-ге тең болады. Салмақ матрицасының әр бағанынан минималды элемент таңдалады, содан кейін қарастырылатын баған элементі ақпарат беру жылдамдығы минималды болатын элементпен қосылады.


1 кесте





1

2

3

4

5

6

7

8

9

10

11

12

1

0

1







1






















2

1

0

2




5

2

3
















3




2

0

3







4
















4







3

0







5

1













5

1

5







0

1







4

4







6




2







1

0

2







5







7




3

4

5




2

0

3




1

5

3

8










1







3

0










5

9













4










0

3







10













4

5

1




3

0

2




11



















5







2

0

1

12



















3

5







1

0

1кесте. Салмақ матрицасы.

2-ші суретте минималды байланыс қорытындысы көрсетілген. 2-і сызықпен 2-ші өту, 3 сызықпен 3-ші өту, 4 сызықпен 4-ші өту көрсетілген
1-өту

2 -сурет. Орындаудың нәтижесі

2-өту
{11;12}


min(11;10)=2
min(12;7)=3
3-өту
{4;8}
min(4;3)=3
min(8;3)=3
4-өту
{6;5;1;2;3}
min(6;7)=2
min(5;9)=4
min(2;6)=2-цикл
min(3;7)=4
Екілік және үштік байланыстар келесі түрде пайда болады.
Егер бірінші өтуден кейін байланыспаған элементтер қалса онда қалған элементтердің мүмкін бола алатын байланыстарды қарастырып минималды байланыс тандалады. Егер байланыспаған элементтер қайтадан қалып жатса оған қалған элементтердің мүмкін болатын байланыстар қайтадан қарастырылады. Минималды байланыс тандалады. Ол үшінші өту болып табылады. Үшінші суретте алгоритмді орындау нәтижесі көрсетілген.
2-ші бөлім:<<Прима Алгоритмі>>
Алгоритмнің 1-ші этабында тек 1 ішкі тармақтын ретті өсуі өндіріледі, мысалы құрамындағы бір төбеден артық Ts(X i,Xj) қабырғаларының қосылу арқасында ішкі тармақ жәймен өседі, мұндағы
Xi Ts,Xj Ts, ал қосылатын қабырғаның салмағы Cij=Lij Cij ең аз болу керек және Cij*=Cji* теңдігі орындалу керек.
Ts-тің қабырғалар саны n–1-ге тең болғанша процесс жалғаса береді.Тs қабырғаларының саны n-1-ге тең болғанда ішкі тармақ Тs керекті ең қысөа негізгі графа болып табылады.
Xj Ts әр төбелеріне / / тамбаларын меншіктеуден алгоритм басталады мұнда Ts ішкі бұтақтын әр қадамдағы ең жақын төбесі болып табылады, ал s / j, j/ қабырғанығ салмағы. Алгоритмді орындаудың әр қадамында / *j, *j/ қабырғалардың қосылу арқасында j белгілеуі ең аз X*j төбесі Ts-қа қосылады. Ts–қа жаңа X*j төбесі қосылғандықтан, кейбір Xj Ts төбелердің / j, j/ белгілеуін өзгертіп (егер, мысалы C(Xj,X*j) j белгілеуінен аз болса), процесті жалғастыру жөн.
Мысал үшін с алгоритмді шешуде қолданған графты алайық.

  1. кез-келген төбені 4 деп алайық.

  2. ең аз салмақты қабырғаны табайық-(4;8). (4;8) қабырғаны ең қысқа негіз графқа қосайық.

  3. таңдалмаған төбелерді қарастырайық. 4 немесе 8 төбесіне дейін салмағы ең аз қабырғаны таңдайық-(3;4)=3.

  4. таңдалған және таңдалмаған төбелерді қосатын келесі ең аз қабырға (2;3)=2 болып табылады. Осындай әдіспен (1;2)=1, (1;5)=1,(5;6)=1,(6;7)=2,(1;2)=1,(7;10)=1,(9;10)=3,(10;11)=2, (11;12)=1 деген төбелерді белгілейік. Нәтижесі 4.4-ші суретте көрсетілген




3- сурет. Прима алгоритмінің орындалу нәтижесі.

2.Жұлдызша тәріздес желіні құру әдісі


Жұлдызша тәріздес желіде коммуникациялық станция тек біреу болады. Оған барлық автоматтандырылған жүйенің (АЖ) қосуымен қайталанбас ортаның мәлімет алмасуы. АЖ-ң сұрауы бойынша коммуникациялық станция (КС) әрбір сұрау сұрапталады. Сондықтан ЛЕЖ-ң шапшаңдығына байланысты КС-ң жұмыс істеуіне байланысты.
Берілген жұмыс бойынша медиананы іздеу G графасының толығымен теңгестірілген матрица //M// (i,j M0 ) таразылығымен оның әрбір жоғарғы салмағының өлшемі ал бәріне j M0. G медиана графигінің жоғарғы шыңы. Бұл санның қысқа қашықтығы басқа шыңдық графикалық шыңдардың минимальді аралығы. Әрбір шыңға екі санақ берілген, оларды беру сандары деп атайды:
ν1(xi )=Σ ωi d(xi,xj) және ν2(xi )=Σ ωi d(xi,xj)
j M0 j M0
мұндағы, d(xi,xj) - шыңдардың xi-ң xj-ға шейін қысқа аралығы. Бұл жағдайда d(xi,xj) = Cij. ν1(xi ) және ν2(xi ) сандары сәйкесінше аталуы сыртқы және ішікі берілу сандарының шыңдағы xi шыңы, мұндағы шың x/. Оған:
ν1(x2)= min{ ν1(xi )}
i M0
G графының медиананың аталуы осының шыңы, оған:
ν2(x2)= min{ ν2(xi )} - медиананың ішкі құрылысы.
i M0
Егер G графы симметриялы матрица салмағы болса, онда ол кандай да желі болмасын, мәлімет алмасады және мәлімет алуын да солай (мысалы, ЛЕЖ сияқты), сонда ν1(x/ )=ν2(x// ). Сондай-ақ КС-ң шыңы ретінде х1,2 алуға болады. Ол сыртқы-ішкі медиана болып табылады. КС-ң таңдайуын біз былай шешеміз, оның құрылуы минимальді түрде құрылып шартпен орындалуы:
( Σ λi / m0)≤ ωj (r) (j M0, r R),
бұл жерде ωj (r) r-ң өткізу қасиеті КС-қа шамалас, j-ң орналасқан пунктіне байланысты. Әріқарай, біз бұл тәсілдің жұлдызша түріндегі ЖЕЖ-дік мысал келтіреміз. ЖЕЖ “ә шыңмен көрсетілген (сурет 1). Орталық шыңың бастысы деп - . шыңды аламыз. Әріқарай біз минимальді медиананы табамыз. Медианалар орналасқан жері 1-ші суретте таблица салмағымен көрсетілген. Жұмыс нәтижесі алгоритм суретінде көрсетілген:


4 - сурет. ЖЕЖ-ң алгоритм түріндегі жұмыс нәтижесі.
3. Сақиналық құрылымға С-алгоритмінің модификациясы (ССМ)
ССМ алгоритмінің жұмысы төберелді аыйптау алгоритмінің қолдануына және ең қысқа гамильтон тізбекшесін іздегендегі МСД-алгоритмына негізделеді. МСМК-алгоритмін қолдвну арқылы туындаған ішкі графтың ең қысқа гамильтон тізбекшесін құруға болады, кейін осы тізбекшеге екі ең қысқа қабырғалары бар изоляцияланған төбелерді қосу арқылы минималды гамильтон циклын алуға болады. Бұл мынадан туындайды, МСМК-алгоритмі, алынған ақырғы төбелердің арасындағы графтың ең қысқа гамильтон тізбекшесін алуды қамтамасыз етеді, сонымен қатар оны циклдық тұықтауға мүмкіндік беретін, осы тізбекшеге қосылған изоляцияланған төбелер жауаптың оптималдығының бұзылуына соқтырмайды. Өйткені изоляциялаған төбелерден шығатын екі қабырға, қалған барлық қабырғалардың арасында әрқашан минималды салмаққа ие.
Осы әдіс арқылы алынатын гамильтондық циклдың оптималдығы изоляциялнған төбелердің таңдалуына байланысты. Берілген ақырғы төбелерден табылған гамильтондық тізбекше тек қана осы жағдайда оптималды болып табылады. Изоляцияланған төбелердің дұрыс таңдалуы іздеу итерациясын айтарлықтай қысқарта алады және ең қысқа гамильтондық циклді алуды қамтамасыз етеді.
ССМ-алгоритмінде изоляцияланған төбелерді таңдау алғашқы G графының алдын ала ең қысқа негізін құру жолымен жүзеге асыру ұсынылады. Кейін изоляцияланған төбелер есебінде максималды дәрежеге ие ең қысқа негіздің төбесін таңдау ұсынылады. Бұл мынадан туындайды, екі сәйкес қабырғаларымен мұндый төбелер графтың барлық гамильтондығ циклына кіруі керек.
Мысалға сол грфті алайық. Алгоритмге берілген салмақтар матрицасы 1-ші кестеде көрсетілген. Берілген графтың ең қысқа негізі 3-ші суретте көрсетілген.
10-ші төбе ең үлкен дәрежеге ие, ол үшін d(x10)=3. Осы жағдайда 10-ші төбені изоляцияланған деп қараймыз, ал салмақтары С910=3, С1011=2 қабырғалардың соңын (х9, х10) және (х10, х11), яғни х9 және х10 төбелерін таңбаланған гамильтондық тізбекшенің соңы деп қараймыз.
9 және 11 жолдарда және бағаналарда тұрған әр элементке 10 санын қосамыз, ал 10 төбеге сійкес жол мен бағананы салмақтар матрицасынан алып тастап, осы салмақтар матрицасынан ең қысқа негізді табамыз. Бұл жағдайдағы салмақтар матрицасы 6-шы кестеде көрсітелген. Нәтиже 5-ші суретте көрсетілген.

2- кесте






1

2

3

4

5

6

7

8

9

10

11

12

1

0

1







1






















2

1

0

2




5

2

3
















3




2

0

3







4
















4







3

0







5

1













5

1

5







0

1







14










6




2







1

0

2
















7




3

4

5




2

0

3







15

3

8










1







3

0










5

9













14










0










10





































11



















15










0

11

12



















3

5







11

0

5-ші сурет.





Берілген негіз гамильтондық тізбекше болып табылмайды, өйткені төбе дәрежесі 5=3. {5, б}=100 байланысын айыптаймыз және жаңа салмақтар матрицасына ең қысқа негізді табамыз. Бұл жағдайдағы салмақтар матрицасы 3-ші кестеде көрсетілген, ал нәтиже 6-шы суретте.


3- кесте.




1

2

3

4

5

6

7

8

9

10

11

12

1

0

1







1






















2

1

0

2




5

2

3
















3




2

0

3







4
















4







3

0







5

1













5

1

5







0

100







14










6




2







100

0

2
















7




3

4

5




2

0

3







15

3

8










1







3

0










5

9













14










0










10





































11



















15










0

11

12



















3

5







11

0

6- сурет.



Берілген негіз гамильтондық тізбекше болып табылмайды, өйткені төбе дәрежесі 2=3. {2, 3}=200 байланысын айыптаймыз және жаңа салмақтар матрицасына ең қысқа негізді табамыз. Бұл жағдайдағы салмақтар матрицасы 4-ші кестеде көрсетілген, ал нәтиже 7-ші суретте.


4- кесте.




1

2

3

4

5

6

7

8

9

10

11

12

1

0

1







1






















2

1

0

200




5

2

3
















3




200

0

3







4
















4







3

0







5

1













5

1

5







0

100







14










6




2







100

0

2
















7




3

4

5




2

0

3







15

3

8










1







3

0










5

9













14










0










10





































11



















15










0

11

12



















3

5







11

0

7- сурет.



Берілген негіз гамильтондық тізбекше болып табылмайды, өйткені төбе дәрежесі 7=3. {7, 8}=300 байланысын айыптаймыз және жаңа салмақтар матрицасына ең қысқа негізді табамыз. Бұл жағдайдағы салмақтар матрицасы 5-ші кестеде көрсетілген, ал нәтиже 8-ші суретте.


5- кесте.




1

2

3

4

5

6

7

8

9




11

12

1

0

1







1






















2

1

0

200




5

2

3
















3




200

0

3







4
















4







3

0







5

1













5

1

5







0

100







14










6




2







100

0

2
















7




3

4

5




2

0

300







15

3

8










1







300

О










5

9













14










О

















































11



















15










О

11

12



















3

5







11

О

.

8-ші сурет

Берілген негіз гамильтондық тізбекше болып табылмайды, өйткені төбе дәрежесі 7=3. {7, 12}=301 байланысын айыптаймыз және жаңа салмақтар матрицасына ең қысқа негізді табамыз. Бұл жағдайдағы салмақтар матрицасы 6-шы кестеде көрсетілген, ал нәтиже 9-шы суретте.


6- кесте.




1

2

3

4

5

6

7

8

9




11

12

1

0

1







1






















2

1

0

200




5

2

3
















3




200

0

3







4
















4







3

0







5

1













5

1

5







0

100







14










6




2







100

0

2
















7




3

4

5




2

0

300







15

301

8










1







300

0










5

9













14










0

















































11



















15










0

11

12



















301

5







11




9-шы суреттен негіз гамильтондық тізбекше екені көренеп тұр. Онда тізбекшеге екі қаьырғасы С910=3, C1011=2 бар изоляциялнған төбені қосу арқылы ең қысқа гамильтондық циклды алуға болады.


Достарыңызбен бөлісу:
1   ...   12   13   14   15   16   17   18   19   ...   56




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
рсетілетін қызмет
Жалпы ережелер
жиынтық бағалаудың
республикасы білім
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
Қазақстан республикасының
мерзімді жоспар
арналған жиынтық
қызмет стандарты
болып табылады
жалпы білім
арналған әдістемелік
бағалаудың тапсырмалары
Мектепке дейінгі
оқыту әдістемесі
Қазақ әдебиеті
нтізбелік тақырыптық
пәнінен тоқсанға
Зертханалық жұмыс
Инклюзивті білім
Әдістемелік кешені
республикасының білім
білім берудің
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
қазақ тілінде
қазіргі заман
туралы хабарландыру
атындағы жалпы