1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374)
Текст из файла
À.Ñ.ÌîðîçîâÂâåäåíèå â âû÷èñëèìîñòü2ÎãëàâëåíèåÏðåäèñëîâèå àâòîðà . . . . . . . . . . . . . . . . . . . . . . . . . .1 Ââåäåíèå1.11.21.3Íåêîòîðûå ïîíÿòèÿ òåîðèè ìíîæåñòâ . . . . . . . . . . . . .Àëôàâèòû è ÿçûêè . . . . . . . . . . . . . . . . . . . . . . .Îáñóæäåíèå èíòóèòèâíûõ ñâîéñòâ àëãîðèòìîâ . . . . . . .57716182 Êîíå÷íûå àâòîìàòû è ãðàììàòèêè213 Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìà452.12.22.32.42.52.63.13.23.33.43.53.63.7Äåòåðìèíèðîâàííûå àâòîìàòû . . . .
. . . . . . . . . . . . .Íåäåòåðìèíèðîâàííûå àâòîìàòû . . . . . . . . . . . . . . .Ðåãóëÿðíûå ÿçûêè . . . . . . . . . . . . . . . . . . . . . . . .Îïðåäåëåíèå ôîðìàëüíûõ ãðàììàòèê . . . . . . . . . . . .Òèïû ãðàììàòèê . . . . . .
. . . . . . . . . . . . . . . . . . .Íåêîòîðûå ñâîéñòâà ãðàììàòèê . . . . . . . . . . . . . . . .2.6.1 ßçûêè ðåãóëÿðíûõ ãðàììàòèê è àâòîìàòíûå ÿçûêè2.6.2 Ðàçðåøèìîñòü íåóêîðà÷èâàþùèõ ãðàììàòèê . . . .Ìàøèíû ؼíôèëäà . . . . . . . . .×àñòè÷íî ðåêóðñèâíûå ôóíêöèè .Êîäèðîâàíèå êîíå÷íûõïîñëåäîâàòåëüíîñòåé . . . . . . . .Êîäèðîâàíèå ìàøèí ؼíôèëäà . .Ìàøèíû Òüþðèíãà . .
. . . . . . .Íîðìàëüíûå àëãîðèôìû ÌàðêîâàÒåçèñ ×¼ð÷à . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . . . . . .....................4 Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòè4.14.2..................................................Íóìåðàöèè è àëãîðèòìè÷åñêèå ïðîáëåìû . . . . . . . . . .Òåîðåìà Êëèíè î íåïîäâèæíîé òî÷êå è òåîðåìà Ðàéñà .
. .32124333539393942455161637077798181864Îãëàâëåíèå4.34.4Åäèíñòâåííîñòü óíèâåðñàëüíîé ôóíêöèè . . . . . . . . . . .Ïåðå÷èñëèìûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . .5 Ââåäåíèå â ñëîæíîñòü àëãîðèòìîâ5.15.25.35.4Çà÷åì íóæíî èçó÷àòü ñëîæíîñòü àëãîðèòìîâ? . . . .Íåäåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà è êëàññû PÏîíÿòèå îá NPïîëíûõ ïðîáëåìàõ . . . . . . .
. . . .Ëèòåðàòóðà äëÿ äàëüíåéøåãî èçó÷åíèÿ . . . . . . . ..è..8893101. . 101NP 102. . 106. . 109Ëèòåðàòóðà109Ïðåäìåòíûé óêàçàòåëü112Ïðåäèñëîâèå àâòîðàÎäèí èç ñîçäàòåëåé òåîðèè àëãîðèòìîâ Ý. Ïîñò óòâåðæäàë, ÷òî ïîíÿòèå àëãîðèòìà ÿâëÿåòñÿ íå ìåíåå âàæíûì è ôóíäàìåíòàëüíûì, ÷åìïîíÿòèå íàòóðàëüíîãî ÷èñëà. Ñ ó÷åòîì òîé ðîëè, êîòîðóþ èãðàåò âû÷èñëèòåëüíàÿ òåõíèêà è å¼ èíòåëëåêòóàëüíàÿ ñîñòàâëÿþùàÿ àëãîðèòìû,ñåãîäíÿ ýòè ñëîâà çâó÷àò åùå áîëåå àêòóàëüíî, ÷åì âî âðåìåíà Ïîñòà.
Ïîñòåïåííî âîçíèêëî ïîíèìàíèå íåîáõîäèìîñòè ââåäåíèÿ â ïåðâîì ñåìåñòðå êóðñà òåîðèè àëãîðèòìîâ, â çàäà÷è êîòîðîãî âõîäèëî áû îçíàêîìëåíèåñòóäåíòîâ ñ ñàìûìè áàçîâûìè ïîíÿòèÿìè ýòîé òåîðèè. Äàííàÿ êíèãà èçëîæåíèå ýòîãî êóðñà ëåêöèé, ÷èòàííîãî àâòîðîì íà ìàòåìàòè÷åñêîìôàêóëüòåòå Íîâîñèáèðñêîãî ãîñóíèâåðñèòåòà â 20012003 ãîäàõ.Ýòîò ó÷åáíèê íå çàìåíÿåò è íå îòìåíÿåò äðóãèå ðóêîâîäñòâà ïî òåîðèè àëãîðèòìîâ. Åãî çàäà÷à äàòü õîðîøåå èíòóèòèâíîå ïîíèìàíèåìàòåìàòè÷åñêîãî ïîíÿòèÿ àëãîðèòìà è ñëóæèòü ââåäåíèåì äëÿ äàëüíåéøåãî èçó÷åíèÿ äðóãèõ ðóêîâîäñòâ ïî òåîðèè àëãîðèòìîâ, à òàêæå ñëóæèòü ìåòîäîëîãè÷åñêîé îñíîâîé äëÿ èçó÷åíèÿ äðóãèõ ïðåäìåòîâ, òàêèõ,êàê, íàïðèìåð, òåîðåòè÷åñêîå ïðîãðàììèðîâàíèå.Íàäåþñü, ÷òî ýòà êíèãà îêàæåòñÿ íåáåñïîëåçíîé òàêæå âñåì èíòåðåñóþùèìñÿ ìàòåìàòèêîé.ß áëàãîäàðåí ñâîåìó ó÷èòåëþ ÷ë.êîðð.
ÐÀÍ Ñ. Ñ. Ãîí÷àðîâó, èíèöèàòîðó ñîçäàíèÿ äàííîãî êóðñà, çà ïëîäîòâîðíûå îáñóæäåíèÿ è ïîääåðæêó â ðàáîòå íàä êíèãîé. ß òàêæå áëàãîäàðåí ñòóäåíòàì À. Þ. Àâäþøåíêî, À. Ñ. Âîëîøèíó, Å. À. Ãëåáîâó, Ñ. Â. Äÿòëîâó, Ò. Ä. ÇàêðåâñêîìóÈ. Ì. Êîëëåãîâó, Å. Â. Ðàáèíîâè÷ó çà íàéäåííûå ìíîãî÷èñëåííûå îïå÷àòêè è íåòî÷íîñòè, à òàêæå çà ïîëåçíûå ïðåäëîæåíèÿ ïî óëó÷øåíèþèçëîæåíèÿ.Ñ áëàãîäàðíîñòüþ ïðèìó âñå êîíñòðóêòèâíûå çàìå÷àíèÿ è ñîîáùåíèÿîá îïå÷àòêàõ è íåòî÷íîñòÿõ.
Ïèøèòå ìíå ïî àäðåñó: Èíñòèòóò ìàòåìàòèêè èì. Ñ.Ë.Ñîáîëåâà ÑÎ ÐÀÍ, ïð. Êîïòþãà 4, 630090, Íîâîñèáèðñê,Ðîññèÿ.Àíäðåé Ñåðãååâè÷ ÌîðîçîâÍîâîñèáèðñê, Àêàäåìãîðîäîê, 22 ÿíâàðÿ 2004 ãîäà6ÎãëàâëåíèåÃëàâà 1Ââåäåíèå ñîâðåìåííîì ìèðå, ïåðåæèâàþùåì èíôîðìàöèîííóþ ðåâîëþöèþ, ñâÿçàííóþ ñ èñïîëüçîâàíèåì êîìïüþòåðîâ è èíôîðìàöèîííûõ òåõíîëîãèéêàê â ïðîèçâîäñòâå òàê è â ïîâñåäíåâíîé æèçíè, ïîíÿòèå àëãîðèòìà ñòàíîâèòñÿ åäâà ëè íå ñàìûì âàæíûì èç âñåõ ìàòåìàòè÷åñêèõ ïîíÿòèé.Íåñìîòðÿ íà òî, ÷òî àëãîðèòìû êîíå÷íûå ïðåäïèñàíèÿ äëÿ ðåøåíèÿ îïðåäåëåííîãî êðóãà çàäà÷, èñïîëüçîâàëèñü ëþäüìè åùå ñ äðåâíîñòè, ñàìî ìàòåìàòè÷åñêîå ïîíÿòèå àëãîðèòìà ñôîðìèðîâàëîñü òîëüêîâ 30å ãîäû XX ñòîëåòèÿ â ðàáîòàõ À. Òüþðèíãà, Ý. Ïîñòà, À.
×¼ð÷à,À. À. Ìàðêîâà, Ñ. Êëèíè è äðóãèõ ìàòåìàòèêîâ. Çíà÷èòåëüíûé âêëàäâ èçó÷åíèå ýòîãî ïîíÿòèÿ âíåñëè ðîññèéñêèå ó÷åíûå Ï. Ñ. Íîâèêîâ,À. À. Ìàðêîâ, À. È. Ìàëüöåâ, Þ. Ë. Åðøîâ è äðóãèå.Öåëü íàñòîÿùåãî êóðñà äàòü îñíîâíûå èäåè, ñâÿçàííûå ñ ïîíÿòèÿìè àëãîðèòìà è âû÷èñëèìîñòè.Çíàê ¤ â òåêñòå îòìå÷àåò îêîí÷àíèå ïðîñòðàíñòâà êíèãè, îòâåäåííîãî íà äàííóþ ëåììó, òåîðåìó èëè ïðåäëîæåíèå.1.1 Íåêîòîðûå ïîíÿòèÿ òåîðèè ìíîæåñòâÌíîæåñòâî ýòî îäíî èç íàèáîëåå ôóíäàìåíòàëüíûõ ìàòåìàòè÷åñêèõïîíÿòèé, íà êîòîðîì ñòðîèòñÿ çäàíèå ïî÷òè âñåé ñîâðåìåííîé ìàòåìàòèêè.
Äîñòàòî÷íî ñêàçàòü, ÷òî âñå ÷èòàåìûå â íàñòîÿùåå âðåìÿ óíèâåðñèòåòñêèå ìàòåìàòè÷åñêèå êóðñû âïîëíå óñïåøíî ôîðìàëèçóåìû â ðàìêàõìèðà ìíîæåñòâ. Ïîíÿòèå ìíîæåñòâà áîëüøèíñòâîì ìàòåìàòèêîâ ñ÷èòàåòñÿ íå îïðåäåëÿåìûì ÷åðåç äðóãèå ìàòåìàòè÷åñêèå ïîíÿòèÿ.Èíòóèòèâíî, ìíîæåñòâà ïðåäñòàâëÿþò ñîáîé ñåìåéñòâà, ñîâîêóïíîñòè, êîëëåêöèè îáúåêòîâ, êîòîðûå ìû ìûñëèì, ïðåäñòàâëÿåì ñåáå êàê78Ãëàâà 1. Ââåäåíèååäèíûå îáúåêòû.Ïðèìåðàìè ìíîæåñòâ ìîãóò ÿâëÿòüñÿ ìíîæåñòâî âñåõ ñòóäåíòîâ âäàííîé àóäèòîðèè, ìíîæåñòâî âñåõ ïëàíåò ñîëíå÷íîé ñèñòåìû, ìíîæåñòâî âñåõ íàòóðàëüíûõ ÷èñåë 0, 1, 2, .
. . è ò.ï.Îñíîâíûì îòíîøåíèåì íà ìíîæåñòâàõ ÿâëÿåòñÿ îòíîøåíèå ïðèíàäëåæíîñòè, òî åñòü áûòü ýëåìåíòîì, îáîçíà÷àåìîå çíà÷êîì ∈. Òàê a ∈ Bîçíà÷àåò, ÷òî a ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà B .Âîçìîæíî, íå ñîâñåì ïðàâèëüíî áûëî áû ïðåäñòàâëÿòü ñåáå ìíîæåñòâî, êàê íàáîð åãî ýëåìåíòîâ, ñëîæåííûõ â íåêèé ìåøîê. Êàæäîå ìíîæåñòâî ýòî íîâûé îòäåëüíûé àáñòðàêòíûé îáúåêò, ñâÿçàííûé ñî ñâîèìè ýëåìåíòàìè îòíîøåíèåì ∈.Ïðèìåðû.
Còóäåíò Èâàíîâ ïðèíàäëåæèò ìíîæåñòâó âñåõ ñòóäåíòîâ âäàííîé àóäèòîðèè; Èâàí Ãðîçíûé íå ïðèíàäëåæèò ìíîæåñòâó âñåõ ñòóäåíòîâ â äàííîé àóäèòîðèè; êàðàíäàø íå ïðèíàäëåæèò ìíîæåñòâó âñåõïëàíåò ñîëíå÷íîéñèñòåìû; 2002 ïðèíàäëåæèò ìíîæåñòâó âñåõ íàòóðàëü√íûõ ÷èñåë; 2 íå ïðèíàäëåæèò ìíîæåñòâó âñåõ íàòóðàëüíûõ ÷èñåë è ò.ï.Ñâîéñòâà ìíîæåñòâ â ìàòåìàòèêå çàäàþòñÿ àêñèîìàòè÷åñêè, òî åñòüìû èõ ÿâíî ôîðìóëèðóåì è äîãîâàðèâàåìñÿ â äàëüíåéøåì íå ïîäâåðãàòüíèêàêîìó ñîìíåíèþ. Çäåñü ìû ñôîðìóëèðóåì è îáñóäèì ëèøü íåêîòîðûåèç ýòèõ ñâîéñòâ, êîòîðûå íàì áóäóò íóæíû â äàëüíåéøåì.Ðàâåíñòâî ìíîæåñòâ. Ñ÷èòàåòñÿ, ÷òî ìíîæåñòâî ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè ýëåìåíòàìè.
Ýòî îçíà÷àåò, ÷òî äâà ìíîæåñòâà ðàâíû â òîìè òîëüêî â òîì ñëó÷àå, êîãäà îíè ñîäåðæàò îäíè è òå æå ýëåìåíòû.Èíà÷å ãîâîðÿ,A = B òîãäà è òîëüêî òîãäà, êîãäà âñÿêèé ýëåìåíò ìíîæåñòâà A ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà B , è íàîáîðîò,âñÿêèé ýëåìåíò ìíîæåñòâà B ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà A.Ñïîñîáû çàäàíèÿ ìíîæåñòâ. Ìíîæåñòâà ìîæíî çàäàâàòü íåñêîëü-êèìè ñïîñîáàìè. Îäèí èç íèõ ÿâíîå ïåðå÷èñëåíèå âñåõ åãî ýëåìåíòîâ,çàêëþ÷åííûõ â ôèãóðíûå ñêîáêè.
Íàïðèìåð: {0}, {a, b, c}, {0, 1, 2, . . .}.Äðóãèì ñïîñîáîì çàäàíèÿ ìíîæåñòâ ÿâëÿåòñÿ çàäàíèå óñëîâèÿ, êîòîðîìó óäîâëåòâîðÿþò âñå ýëåìåíòû äàííîãî ìíîæåñòâà è íå óäîâëåòâîðÿåòíè îäèí ýëåìåíò íå èç äàííîãî ìíîæåñòâà. Íàïðèìåð, ìíîæåñòâî A âñåõ1.1. Íåêîòîðûå ïîíÿòèÿ òåîðèè ìíîæåñòâ9÷åòíûõ ÷èñåë ìîæíî çàäàòü êàêA = {x | x ÷åòíîå íàòóðàëüíîå ÷èñëî.}. îáùåì ñëó÷àå, êîãäà èìååòñÿ óñëîâèå Φ, êîòîðîå áûâàåò ëèáî èñòèííûì ëèáî ëîæíûì äëÿ äàííîãî ýëåìåíòà, ìîæåò áûòü îáðàçîâàíî ìíîæåñòâî âñåõ x, óäîâëåòâîðÿþùèõ óñëîâèþ Φ1 .
Ýòî ìíîæåñòâî îáû÷íîçàïèñûâàåòñÿ â âèäå{x | x îáëàäàåò ñâîéñòâîì Φ}.Äëÿ îáîçíà÷åíèÿ ìíîæåñòâà âñåõ x, ïðèíàäëåæàùèõ ìíîæåñòâó A è óäîâëåòâîðÿþùèõ óñëîâèþ Φ, òàêæå óïîòðåáëÿåòñÿ çàïèñü âèäà{x ∈ A | x îáëàäàåò ñâîéñòâîì Φ}.Ïðèìåðû.{a, a} = {a},{x | x íàòóðàëüíîå ÷èñëî íå áîëåå 2} = {0, 1, 2}.Ïóñòîå ìíîæåñòâî. Ñóùåñòâóåò ìíîæåñòâî, íå ñîäåðæàùåå âîîáùå íèîäíîãî ýëåìåíòà. Ñóùåñòâóåò âñåãî îäíî ìíîæåñòâî ñ òàêèì ñâîéñòâîì.2Îíî íàçûâàåòñÿ ïóñòûì ìíîæåñòâîì. Ó ïóñòîãî ìíîæåñòâà èìååòñÿñîáñòâåííîå îáîçíà÷åíèå: ∅.Çàìåòèì, ÷òî {∅} 6= ∅, ïîñêîëüêó â ïåðâîì èç ýòèõ ìíîæåñòâ ñîäåðæèòñÿ îäèí ýëåìåíò (à èìåííî ∅), à âî âòîðîì íè îäíîãî.Ïîíÿòèå ïîäìíîæåñòâà.
Ïóñòü A è B äâà ìíîæåñòâà. Ìû ãîâîðèì,÷òî A ÿâëÿåòñÿ ïîäìíîæåñòâîì B , åñëè âñÿêèé ýëåìåíò èç A ÿâëÿåòñÿýëåìåíòîì èç B . Ýòîò ôàêò îáîçíà÷àåòñÿ òàê: A ⊆ B . Åñëè íåîáõîäèìîïîä÷åðêíóòü, ÷òî A ⊆ B è ïðè ýòîì A 6= B , òî óïîòðåáëÿåòñÿ òàêæå1Çàìåòèì îäíàêî, ÷òî íåîãðàíè÷åííîå èñïîëüçîâàíèå òàêîãî ñïîñîáà îáðàçîâàíèÿìíîæåñòâ ïðèâîäèò ê ïðîòèâîðå÷èÿì è ïàðàäîêñàì. Ïðè èçó÷åíèè ìàòåðèàëà äàííîãî ó÷åáíèêà ýòà ïðîáëåìà íå âîçíèêàåò è ïîýòîìó çäåñü íå îáñóæäàåòñÿ. Ñîîòâåòñòâóþùèå âîïðîñû îáñóæäàþòñÿ â ëèòåðàòóðå ïî ìàòåìàòè÷åñêîé ëîãèêå è òåîðèèìíîæåñòâ.2Ïîñëåäíåå ñâîéñòâî âûâîäèìî èç ïðèâåäåííîãî âûøå ñâîéñòâà ðàâåíñòâà ìíîæåñòâ, íî äëÿ ïîíèìàíèÿ ýòîãî òðåáóåòñÿ îáñóæäåíèå íåêîòîðûõ ïðèíöèïîâ ìàòåìàòè÷åñêîé ëîãèêè, âûõîäÿùåå çà ðàìêè ýòîé êíèãè.10Ãëàâà 1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
