Çàî÷íîå äèñòàíöèîííîå îáðàçîâàíèå ñ ïîëó÷åíèåì ãîñóäàðñòâåííîãî äèïëîìà ÷åðåç Internet










Ïîëó÷èòü èíôîðìàöèþ î ïîñòóïëåíèè
 
Ãëàâíàÿ Íîâîñòè Êàðòà ñàéòà Ôîòîàëüáîì Ãîñòåâàÿ êíèãà Êîíòàêòû

Òåîðåòè÷åñêèé ìàòåðèàë
Ïðàêòè÷åñêèé ìàòåðèàë
Îáúåêò èíôîðìàòèêè
Ïðåäìåòíàÿ îáëàñòü èíôîðìàòèêè êàê íàóêè
Öåëü è çàäà÷è êóðñà «èíôîðìàòèêà»
Èñòîðèÿ ðàçâèòèÿ èíôîðìàòèêè

 

Ïîíÿòèÿ òåîðèè àëãîðèòìîâ

Òåîðèÿ àëãîðèòìîâ — ðàçäåë ìàòåìàòèêè, èçó÷àþùèé îáùèå ñâîéñòâà àëãîðèòìîâ. Ïîíÿòèå «àëãîðèòì» ñôîðìèðîâàëîñü â ìàòå­ìàòèêå â 20-õ ãîäàõ XX â. Íà÷àëîì ñèñòåìàòè÷åñêîé ðàçðàáîòêè òåîðèè àëãîðèòìîâ ìîæíî ñ÷èòàòü 1936 ã. è ñâÿçûâàþò ýòî íà÷àëî ñ ïóáëèêàöèåé ðàáîòû À.À. ×åð÷à.

Ïîä àëãîðèòìîì âñåãäà (è äî âîçíèêíîâåíèÿ ñòðîãîé òåîðèè) ïîíèìàëàñü ïðîöåäóðà, êîòîðàÿ ïîçâîëÿëà ïóòåì âûïîëíåíèÿ ïîñëå­äîâàòåëüíîñòè ýëåìåíòàðíûõ øàãîâ ïîëó÷àòü îäíîçíà÷íûé ðåçóëüòàò (íåçàâèñÿùèé îò òîãî, êòî èìåííî âûïîëíÿë ýòè øàãè) èëè çà êîíå÷íîå ÷èñëî øàãîâ ïðèéòè ê âûâîäó î òîì, ÷òî ðåøåíèÿ íå ñóùåñòâóåò.

Êîíå÷íî æå ýòî íåñòðîãîå îïðåäåëåíèå ïîíÿòèÿ àëãîðèòìà è èìåííî ïîïûòêè ñôîðìóëèðîâàòü òàêîå ïîíÿòèå ïðèâåëè ê âîçíèê­íîâåíèþ òåîðèè àëãîðèòìîâ. Ïðè÷èíîé ðàçâèòèÿ ýòîé òåîðèè áûëè âíóòðåííèå ïðîáëåìû ìàòåìàòèêè è ëèøü ñ âîçíèêíîâåíèåì è ðàçâèòèåì âû÷èñëèòåëüíîé òåõíèêè è ñìåæíûõ íàóê âûÿñíèëîñü, ÷òî â îñíîâå ýòèõ íàóê äîëæíà ëåæàòü òåîðèÿ àëãîðèòìîâ. Òàê ñòàëî î÷åâèäíûì ïðèêëàäíîå çíà÷åíèå íîâîé íàóêè.

 îñíîâå ôîðìàëèçàöèè ïîíÿòèÿ «àëãîðèòì» ëåæèò èäåÿ ïîñòðîåíèÿ àëãîðèòìè÷åñêîé ìîäåëè. Ñîñòàâëÿþùèìè òàêîé ìîäåëè äîëæíû áûòü êîíêðåòíûé íàáîð ýëåìåíòàðíûõ øàãîâ, ñïîñîáû îïðåäåëåíèÿ ñëåäóþùåãî øàãà è ò.ä. Îò ìîäåëè òàêæå òðåáóåòñÿ ïðîñòîòà è óíèâåðñàëüíîñòü. Òðåáîâàíèå ïðîñòîòû âàæíî äëÿ òîãî, ÷òîáû âûäåëèòü äåéñòâèòåëüíî íåîáõîäèìûå ýëåìåíòû è ñâîéñòâà àëãîðèòìà è îáëåã÷èòü äîêàçàòåëüñòâà îáùèõ óòâåðæäåíèé îá ñâîéñòâàõ. Óíèâåðñàëüíîñòü íåîáõîäèìà äëÿ òîãî, ÷òîáû ìîäå ïîçâîëÿëà îïèñàòü ëþáîé àëãîðèòì.

Ðåçóëüòàòàìè òåîðåòè÷åñêèõ èññëåäîâàíèé ÿâèëèñü òðè îñíîâíûõ êëàññà àðèôìåòè÷åñêèõ ìîäåëåé.

Ïåðâûé êëàññ ìîäåëåé îñíîâàí íà àðèôìåòèçàöèè àëãîðèòìîâ. Ïðåäïîëàãàåòñÿ, ÷òî ëþáûå äàííûå ìîæíî çàêîäèðîâàòü ÷èñëàìè, êàê ñëåäñòâèå - âñÿêîå èõ ïðåîáðàçîâàíèå ñòàíîâèòñÿ â ýòîì ñëó÷àå àðèôìåòè÷åñêèì âû÷èñëåíèåì, àëãîðèòìîì â òàêèõ ìîäåëÿõ åå âû÷èñëåíèå çíà÷åíèÿ íåêîòîðîé ÷èñëîâîé ôóíêöèè, à åãî ýëåìåíò» òàðíûå øàãè - àðèôìåòè÷åñêèå îïåðàöèè. Ïîñëåäîâàòåëüíîñòü øà­ãîâ îïðåäåëÿåòñÿ äâóìÿ ñïîñîáàìè. Ïåðâûé ñïîñîá - ñóïåðïîçèöèÿ, ò.å. ïîäñòàíîâêà ôóíêöèè â ôóíêöèþ, à âòîðîé - ðåêóðñèÿ, ò.å. îïðåäåëåíèå çíà÷åíèÿ ôóíêöèè ÷åðåç «ðàíåå» âû÷èñëåííûå çíà÷åíèÿ ýòîé æå ôóíêöèè. Ôóíêöèè, êîòîðûå ìîæíî ïîñòðîèòü èç öåëûõ ÷èñåë è àðèôìåòè÷åñêèõ îïåðàöèé ñ ïîìîùüþ ñóïåðïîçèöèé ðåêóðñèâíûõ îïðåäåëåíèé, íàçûâàþòñÿ ðåêóðñèâíûìè ôóíêöèÿìè. Ïðîñòåéøèì ïðèìåðîì ðåêóðñèâíîé ôóíêöèè ÿâëÿåòñÿ ôàêòîðèàë.

Âòîðîé êëàññ ìîäåëåé ïîðîæäåí ñëåäóþùåé èäååé. Äëÿ òîã ÷òîáû àëãîðèòì ïîíèìàëñÿ îäíîçíà÷íî, à åãî êàæäûé øàã ñ÷èòàëñÿ ýëåìåíòàðíûì è âûïîëíèìûì, îí äîëæåí áûòü ïðåäñòàâëåí ÷òîáû åãî ìîãëà âûïîëíÿòü ìàøèíà, ê êîòîðîé ïðåäúÿâëÿþòñÿ óæå óïîìÿíóòûå òðåáîâàíèÿ ïðîñòîòû è óíèâåðñàëüíîñòè. Îäíîé èç ìàøèí ÿâèëàñü àáñòðàêòíàÿ ìàøèíà Òüþðèíãà. Ìàøèíà Òüþðèíãà ñîñòîèò èç òðåõ ÷àñòåé ëåíòû, ãîëîâêè è óïðàâëÿþùåãî óñòðîéñòâà (ÓÓ). Ëåíòà áåñêîíå÷íà â îáå ñòîðîíû è ðàçáèòà íà ÿ÷åéêè. Ýëåìåíòàðíûé øàã ìàøèíû Òüþðèíãà ñîñòîèò èç ñëåäóþùèõ äåéñòâèé:

ãîëîâêà ñ÷èòûâàåò ñèìâîë, çàïèñàííûé â ÿ÷åéêå, íàä êîòîðîé îíà íàõîäèòñÿ;

ñ÷èòàííûé ñèìâîë è òåêóùåå ñîñòîÿíèå ãîëîâêè îäíîçíà÷íî îïðåäåëÿþò íîâîå ñîñòîÿíèå, íîâûé çàïèñûâàåìûé ñèìâîë è ïåðåìåùåíèå ãîëîâêè (êîòîðîå ìîæåò èìåòü çíà÷åíèå íà ÿ÷åéêó âëåâî, íà ÿ÷åéêó âïðàâî, îñòàòüñÿ íà ìåñòå).

Óñòðîéñòâî óïðàâëåíèÿ õðàíèò è âûïîëíÿåò êîìàíäû ìàøèíû.

Òðåòèé êëàññ ìîäåëåé àëãîðèòìîâ î÷åíü áëèçîê ê ïðåäûäóùåìó, íî íå îïåðèðóåò êîíêðåòíûìè ìàøèííûìè ìåõàíèçìàìè. Íàèáîëåå èçâåñòíàÿ àëãîðèòìè÷åñêàÿ ìîäåëü ýòîãî òèïà - íîðìàëüíûå àëãîðèòìû Ìàðêîâà.

Äëÿ íîðìàëüíîãî àëãîðèòìà çàäàåòñÿ àëôàâèò, íàä êîòîðûì îí ðàáîòàåò, êîíå÷íîå ìíîæåñòâî äîïóñòèìûõ ïîäñòàíîâîê è ïîðÿäîê èõ ïðèìåíåíèÿ. Åñëè â êà÷åñòâå àëôàâèòà âçÿòü àëôàâèò ðóññêîãî ÿçûêà, à â êà÷åñòâå ìíîæåñòâà ïîäñòàíîâîê òî, èñïîëüçóÿ ïðàâèëà 1—3:

1) ïðîâåðèòü âîçìîæíîñòü ïîäñòàíîâîê â ïîðÿäêå âîçðàñòàíèÿ èõ íîìåðîâ, è åñëè îíà âîçìîæíà (ëåâàÿ ÷àñòü ïîäñòàíîâêè îáíàðóæåíà â èñõîäíîì ñëîâå), ïðîèçâåñòè ïîäñòàíîâêó (çàìåíèâ ëåâóþ ÷àñòü íà ïðàâóþ);

2) åñëè â ïðèìåíåííîé ïîäñòàíîâêå èìååòñÿ ñèìâîë «!», òî ïðåîáðàçîâàíèÿ ïðåêðàùàþòñÿ, à åñëè íåò, òî òåêóùåå ñîñòîÿíèå ñòàíîâèòñÿ èñõîäíûì è âåñü ïðîöåññ íà÷èíàåòñÿ çàíîâî;

3) åñëè íè îäíà ïîäñòàíîâêà íå ïðèìåíèìà, òî ïðîöåññ ïðåîáðàçîâàíèÿ çàâåðøåí, ìîæíî îáíàðóæèòü, ÷òî ïî çàäàííîìó àëãîðèòìó èñõîäíîå ñëîâî.

 òåîðèè àëãîðèòìîâ ñòðîãî äîêàçàíî, ÷òî ïî ñâîèì âîçìîæíîñòÿì ïðåîáðàçîâàíèÿ íîðìàëüíûå àëãîðèòìû ýêâèâàëåíòíûå ìàøèíå Òüþðèíãà è äðóãèì ìîäåëÿì, óòî÷íÿþùèì ïîíÿòèÿ àëãîðèòìà.

Ïîÿâëåíèå òî÷íîãî ïîíÿòèÿ àëãîðèòìà ïîçâîëèëî ñôîðìóëèðîâàòü àëãîðèòìè÷åñêè íå ðàçðåøèìûå ïðîáëåìû, ò.å. çàäà÷è, äëÿ; ðåøåíèÿ êîòîðûõ íåâîçìîæíî ïîñòðîèòü àëãîðèòì. Çàäà÷à íàçûâàåòñÿ àëãîðèòìè÷åñêè íåðàçðåøèìîé, åñëè íå ñóùåñòâóåò ìàøèíû Òüþðèíãà (èëè ðåêóðñèâíîé ôóíêöèè, èëè íîðìàëüíîãî àëãîðèòìå Ìàðêîâà), êîòîðàÿ åå ðåøàåò. Íàïðèìåð, íåðàçðåøèìîé îêàçàëàñü ïðîáëåìà ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè àëãîðèòìîâ: íåëüçÿ ïîñòðîèòü àëãîðèòì, êîòîðûé ïî ëþáûì äâóì àëãîðèòìàì (ïðîãðàììàì) âûÿñíÿë áû, âû÷èñëÿþò îíè îäíó è òó æå ôóíêöèþ èëè íåò. Çíàíèå îñíîâíûõ íåðàçðåøèìîñòåé òåîðèè àëãîðèòìîâ íåîáõîäèìî äëÿ ñïåöèàëèñòà ïî èíôîðìàòèêå. Îíî ïðåäîñòåðåæåò åãî îò óâëå÷åíèÿ ãëîáàëüíûìè ïðîæåêòàìè âñåîáùåé àëãîðèòìèçàöèè òî÷íî òàê êàê çíàíèå îñíîâíûõ çàêîíîâ ôèçèêè ïðåäîñòåðåãàåò îò ïîïûòîê ñîçäàíèÿ âå÷íîãî äâèãàòåëÿ.



 
     
   
 


Ïðèãëàøàåì ïðèíÿòü ó÷àñòèå â êðóãëîì ñòîëå!
ïîäðîáíåå   >>>
 

Èíñòèòóò Ìåíåäæìåíòà, Ýêîíîìèêè è Èííîâàöèé íà÷èíàåò íàáîð íà êóðñû ïîâûøåíèÿ êâàëèôèêàöèè!
ïîäðîáíåå   >>>
 

Óâàæåìûå ñòóäåíòû ÀÍÎ ÂÏÎ ÈÌÝèÈ!
ïîäðîáíåå   >>>
 

Íà÷èíàåòñÿ íàáîð íà êóðñû ïîâûøåíèÿ êâàëèôèêàöèè!
ïîäðîáíåå   >>>
 

Ïðèãëàøàåì ïðèíÿòü ó÷àñòèå â êîíôåðåíöèÿõ!
ïîäðîáíåå   >>>
 


âñå íîâîñòè...

 


Ðàññûëêè Subscribe.Ru
Ñîâðåìåííîå îáðàçîâàíèå
Ïîäïèñàòüñÿ ïèñüìîì