Составители:
Рубрика:
34
1.5. Ðåàëèçàöèÿ àëãîðèòìîâ òåîðèè ãðàôîâ íà ÝÂÌ
Ðåøåíèå çàäà÷ ñ ïðèìåíåíèåì ìåòîäîâ òåîðèè ãðàôîâ äîëæíî ïîä-
÷èíÿòüñÿ îáùåé ïîñëåäîâàòåëüíîñòè ýòàïîâ ðåøåíèÿ çàäà÷ ñ ïðèìåíå-
íèåì ÝÂÌ.
1-é ýòàï ïîñòàíîâêà çàäà÷è. Äàåòñÿ ôîðìóëèðîâêà çàäà÷è, öåëåé åå
ðåøåíèÿ è îãðàíè÷åíèé íà ñîäåðæàòåëüíîì åñòåñòâåííîì ÿçûêå.
2-é ýòàï ôîðìàëèçàöèÿ çàäà÷è. Ñîäåðæàòåëüíîå îïèñàíèå çàäà÷è
ïåðåâîäèòñÿ íà ôîðìàëèçîâàííûé ÿçûê èñïîëüçóåìîé ìàòåìàòè÷åñêîé
òåîðèè, ò. å. ñîçäàåòñÿ ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è.
3-é ýòàï âûáîð ÷èñëåííîãî ìåòîäà ðåøåíèÿ çàäà÷è â ñîîòâåòñòâèè
ñ çàäàííûìè êðèòåðèÿìè, íàïðèìåð ïðè èñïîëüçîâàíèè ÝÂÌ òàêèìè
êðèòåðèÿìè ìîãóò áûòü âðåìÿ ðåøåíèÿ è îáúåì çàíèìàåìîé ïàìÿòè.
4-é ýòàï àëãîðèòìèçàöèÿ. Ïðè ïîñòðîåíèè àëãîðèòìîâ îáðàáîòêè
ãðàôîâ äîëæíû ñîáëþäàòüñÿ îáùèå ñâîéñòâà àëãîðèòìîâ.
1. Äèñêðåòíîñòü. Ïðèìåíåíèå àëãîðèòìà îñóùåñòâëÿåòñÿ â äèñêðåò-
íîì âðåìåíè â ñîîòâåòñòâèè ñ ïîñëåäîâàòåëüíîñòüþ ïðàâèë, äåéñòâèé,
îïåðàöèé, øàãîâ, ïðîöåäóð ïî îáðàáîòêå ãðàôîâ.
2. Äåòåðìèíèðîâàííîñòü. Äåéñòâèÿ íàä ãðàôîì â ñîîòâåòñòâèè ñ ïðà-
âèëàìè îáðàáîòêè äîëæíû áûòü ïðîñòûìè è îïðåäåëåííûìè, ïðè ýòîì
ìîãóò èñïîëüçîâàòüñÿ èçâåñòíûå ïðîöåäóðû.
3. Ðåçóëüòàòèâíîñòü. Àëãîðèòì ñîñòîèò èç ñîâîêóïíîñòè êîíå÷íî-
ãî ÷èñëà ïðàâèë è äåéñòâèé, êîòîðûå äîëæíû îò èñõîäíûõ äàííûõ ïðè-
âåñòè ê èñêîìîìó ðåçóëüòàòó çà êîíå÷íîå ÷èñëî øàãîâ. Âûáîð ïðàâèë è
äåéñòâèé çàâèñèò òîëüêî îò ðåçóëüòàòîâ ïðåäûäóùèõ øàãîâ, íàïðèìåð
îò ðåçóëüòàòà àíàëèçà âåðøèí ñìåæíûõ ñ äàííîé âåðøèíîé.
4. Ìàññîâîñòü. Àëãîðèòì äîëæåí ïðèìåíÿòüñÿ äëÿ öåëîãî êëàññà
çàäà÷, à íå îäíîé çàäà÷è.
Îäíàêî, åñëè ðåøåíèå çàäà÷è ïðåäñòàâëåíî â âèäå àëãîðèòìà ñ ñî-
áëþäåíèåì ñâîéñòâ 14, îí ìîæåò èìåòü ñâîþ ñïåöèôèêó, ñâÿçàííóþ ñ
ÿçûêîì òåîðèè ãðàôîâ è îòðàæàþùóþñÿ â åãî ôîðìóëèðîâêå. Èìååòñÿ
îïðåäåëåííîå ðàçëè÷èå â ñòåïåíè ïîäãîòîâëåííîñòè çàïèñè àëãîðèò-
ìîâ äëÿ èõ ðåàëèçàöèè íà ÝÂÌ. Ïîýòîìó íåîáõîäèìî ïðèâåñòè àëãî-
ðèòì, íàïèñàííûé íà ñîäåðæàòåëüíîì óðîâíå è íà óðîâíå àáñòðàêöèé
òåîðèè ãðàôîâ, ê âèäó ìàøèííî-îðèåíòèðîâàííûõ àëãîðèòìîâ.
Ìàøèííî-îðèåíòèðîâàííûìè, ò. å. êîìïüþòåðíûìè, ÿâëÿþòñÿ àëãî-
ðèòìû, êîòîðûå ìîæíî çàïèñûâàòü â âèäå ïðîãðàììû äëÿ ÝÂÌ.
5-é ýòàï ïðîãðàììèðîâàíèå. ÝÂÌ ìîæåò áûòü ïðèìåíåíà äëÿ ðå-
øåíèÿ çàäà÷è òåîðèè ãðàôîâ òîëüêî ïîñëå òîãî, êàê åå àëãîðèòì áóäåò
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
