Составители:
Рубрика:
35
çàïèñàí â âèäå ïðîãðàììû, ò. å. äåòàëüíûõ èíñòðóêöèé ïî îáðàáîòêå
ãðàôà íà ÿçûêå, ïîíÿòíîì ÝÂÌ.
 ïðîãðàììå äîëæíî áûòü ïðåäóñìîòðåíî, êàêèå äàííûå è â êàêîì
âèäå äîëæíû áûòü ââåäåíû â ÝÂÌ äëÿ èõ ïîñëåäóþùåé îáðàáîòêè.
×àùå âñåãî ãðàô ââîäèòñÿ â ÝÂÌ ñ ïîìîùüþ ìàòðèöû ñìåæíîñòè âåð-
øèí. Íàïðèìåð, äëÿ ãðàôà G=(V,U) áåç ïàðàëëåëüíûõ äóã ìàòðèöà ñìåæ-
íîñòè ýòî êâàäðàòíàÿ áóëåâà ìàòðèöà ||S
ij
|| ðàçìåðîì n×n, ãäå n ÷èñëî
âåðøèí ãðàôà. Ýëåìåíò S
ij
= 1,
åñëè äóãà(v
i
, v
j
)∈ U, è S
ij
= 0 â ïðîòèâíîì
ñëó÷àå. Êðîìå òîãî, ìîæåò ïîòðåáîâàòüñÿ ââåäåíèå äîïîëíèòåëüíîé
èíôîðìàöèè î ãðàôå â âèäå ìàññèâîâ (ìàòðèö è âåêòîðîâ). Âîçìîæíî
äóãàì è/èëè âåðøèíàì ìîãóò áûòü ïðèïèñàíû íåêîòîðûå ÷èñëà (óñëîâ-
íî ãîâîðÿ, äëèíû äóã, âåñà âåðøèí), îòðàæàþùèå äîïîëíèòåëüíûå ñâîé-
ñòâà ñâÿçåé ìåæäó âåðøèíàìè. Íàïðèìåð, äëèíà äóãè ýòî ðàññòîÿíèå
ìåæäó óäàëåííûìè îáúåêòàìè, ïðåäñòàâëåííûìè âåðøèíàìè ãðàôà.
Ïðîãðàììà äîëæíà ÷åòêî ïðåäïèñàòü ïîñëåäîâàòåëüíîñòü îïåðàöèé,
êîòîðûå íóæíî ïðîèçâåñòè íàä ìàòðèöåé ñìåæíîñòè ãðàôà, äðóãèìè
âõîäíûìè äàííûìè è ïðîìåæóòî÷íûìè ðåçóëüòàòàìè (ìàòðèöàìè, âåê-
òîðàìè, ÷èñëàìè), ôîðìèðóåìûìè â ïðîöåññå ðåøåíèÿ, ÷òîáû ïîëó-
÷èòü âûõîäíûå ðåçóëüòàòû, à òàêæå ïðåäóñìîòðåòü, â êàêîì âèäå ýòè
ðåçóëüòàòû áóäóò âûäàíû ÝÂÌ äëÿ ïîëüçîâàòåëÿ.
6-é ýòàï îòëàäêà, ò. å. ïîèñê è èñïðàâëåíèå ñèíòàêñè÷åñêèõ (ôîð-
ìàëüíûõ) îøèáîê, à òàêæå ñåìàíòè÷åñêèõ (ñìûñëîâûõ) îøèáîê ñ èñ-
ïîëüçîâàíèåì ñïåöèàëüíûõ òåñòîâûõ äàííûõ.
7-é ýòàï èñïîëüçîâàíèå îòëàæåííîé ïðîãðàììû äëÿ ðàñ÷åòîâ ñ ðå-
àëüíûìè èñõîäíûìè äàííûìè.
8-é ýòàï èíòåðïðåòàöèÿ ðåçóëüòàòîâ, ïîëó÷åííûõ â õîäå ðàáîòû
ïðîãðàììû è ðåêîìåíäàöèè ïî èõ èñïîëüçîâàíèþ.
Ïîñëå ýòèõ êðàòêèõ çàìå÷àíèé íåòðóäíî ïîíÿòü, êàêàÿ áîëüøàÿ äèñ-
òàíöèÿ, êàê ïðàâèëî, èìååòñÿ ìåæäó ôîðìóëèðîâêîé àëãîðèòìà íà ÿçû-
êå òåîðèè ãðàôîâ è ïðîãðàììîé äëÿ ÝÂÌ. Èìåííî ðàçðàáîòêà êîìïüþ-
òåðíîãî àëãîðèòìà äîëæíà áûòü ðåçóëüòàòîì ýòàïîâ ôîðìàëèçàöèè è
àëãîðèòìèçàöèè ïðè ðåøåíèè ïðèêëàäíûõ çàäà÷ ñ ïðèìåíåíèåì òåîðå-
òè÷åñêèõ ìîäåëåé òåîðèè ãðàôîâ.
Íèæå áóäåò ðàññìîòðåíî ðåøåíèå íåêîòîðûõ çàäà÷ ñ èñïîëüçîâàíè-
åì àëãîðèòìîâ òåîðèè ãðàôîâ ñ âîçìîæíûì ïðèìåíåíèåì êîìïüþòåð-
íûõ àëãîðèòìîâ.
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »
