1610906281-d25a58898a45262b0b837c281ba962eb (Лекции Когабаев Соболева)

Íà ïðàâàõ ðóêîïèñèÍÎÂÎÑÈÁÈÐÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÌåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåòÍ. Ò. Êîãàáàåâ, Þ. Þ. ÑîêîëîâàÄÐÓÃÈÅ ËÅÊÖÈÈ ÏÎÒÅÎÐÈÈ ÀËÃÎÐÈÒÌÎÂÓ÷åáíîå ïîñîáèåÍîâîñèáèðñê2015Äðóãèå ëåêöèè ïî òåîðèè àëãîðèòìîâ: Ó÷åá.ïîñîáèå / Íîâîñèá. ãîñ. óí-ò. Íîâîñèáèðñê, 2015. 71 ñ.Êîãàáàåâ Í. Ò., Ñîêîëîâà Þ.

Þ. íàñòîÿùåì ó÷åáíîì ïîñîáèè èçëîæåíû ìàòåìàòè÷åñêèå îñíîâû òåîðèè àëãîðèòìîâ. Ïîñîáèå îòðàæàåò ñîäåðæàíèå ëåêöèé îñíîâíîãî êóðñà ¾Äèñêðåòíàÿ ìàòåìàòèêàè òåîðèÿ àëãîðèòìîâ¿ äëÿ ñòóäåíòîâ 1-ãî êóðñà ìåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòà ÍÃÓ è îõâàòûâàåò ìàòåðèàë èç íåñêîëüêèõ îáëàñòåé ìàòåìàòèêè, òàê èëè èíà÷åñâÿçàííûõ ñ ïîíÿòèåì àëãîðèòìà: òåîðèÿ àâòîìàòîâ è ðåãóëÿðíûõ ÿçûêîâ, ìàøèíûÒüþðèíãà è ÷àñòè÷íî ðåêóðñèâíûå ôóíêöèè, êëàññè÷åñêàÿ òåîðèÿ âû÷èñëèìîñòè.Ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ 1-ãî êóðñà ìåõàíèêî-ìàòåìàòè÷åñêîãî ôàêóëüòåòàÍÃÓ, èçó÷àþùèõ êóðñ ¾Äèñêðåòíàÿ ìàòåìàòèêà è òåîðèÿ àëãîðèòìîâ¿, à òàêæå äëÿâñåõ æåëàþùèõ ïîçíàêîìèòüñÿ ñ îñíîâàìè óïîìÿíóòûõ â ïîñîáèè ìàòåìàòè÷åñêèõòåîðèé.ÎãëàâëåíèåÃëàâà I.

Ïðåäâàðèòåëüíûå ñâåäåíèÿ4Ÿ 1. Íåêîòîðûå àêñèîìû òåîðèè ìíîæåñòâ . . . . . . . . . . . . . . . . . . . .Ÿ 2. Àëôàâèòû è ôîðìàëüíûå ÿçûêè . . . . . . . . . . . . . . . . . . . . . . .Ÿ 3. Ýëåìåíòû êîìáèíàòîðèêè . . . . . . . . . . . . . . . . . . . . . . . . . .Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèê蟟ŸŸŸŸ4.5.6.7.8.9.Äåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû .Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòûÍåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòûÑâîéñòâà àâòîìàòíûõ ÿçûêîâ . .

. . . . .Ðåãóëÿðíûå ÿçûêè . . . . . . . . . . . . . .Ôîðìàëüíûå ãðàììàòèêè . . . . . . . . . ...ñ...12. . . . . . . . . . . . .. . . . . . . . . . . . .ïóñòûìè ïåðåõîäàìè. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . ...................Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöè蟟ŸŸŸŸŸ10. Îïðåäåëåíèå ìàøèíû Òüþðèíãà . . . . . . . .

. . . . . .11. Áàçîâûå ìàøèíû Òüþðèíãà . . . . . . . . . . . . . . . .12. ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè . . . . . . . . . . . . . .13. Ðåêóðñèâíîñòü íåêîòîðûõ ôóíêöèé è îòíîøåíèé . . . .14. Êîäèðîâàíèå ìàøèí Òüþðèíãà . . . . . . . . . . . . . . .15. Ìàøèíû Òüþðèíãà vs ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè16. Óíèâåðñàëüíûå ôóíêöèè . . . . . .

. . . . . . . . . . . .Ãëàâà IV. Òåîðèÿ âû÷èñëèìîñòè47912141822262934...............................................................3437404450555760Ÿ 17. Òåîðåìà î ïàðàìåòðèçàöèè . . . . . . . . . . . . . . . . . . . . . . . . . . 60Ÿ 18. Òåîðåìà î íåïîäâèæíîé òî÷êå . . . . . . . . . . . . .

. . . . . . . . . . . 63Ÿ 19. Âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâà . . . . . . . . . . . . . . . . . . . . 65Ñïèñîê ëèòåðàòóðû70Ãëàâà IÏðåäâàðèòåëüíûå ñâåäåíèÿŸ 1.Íåêîòîðûå àêñèîìû òåîðèè ìíîæåñòâÂñå îáúåêòû, èçó÷àåìûå â äàííîì êóðñå, ÿâëÿþòñÿ ìíîæåñòâàìè.

Ìíîæåñòâàìè ÿâëÿþòñÿ ñèìâîëû, àëôàâèòû è ÿçûêè. Ìíîæåñòâàìè ÿâëÿþòñÿ ÷èñëà, êîðòåæè è ïîñëåäîâàòåëüíîñòè. Ìíîæåñòâàìè ÿâëÿþòñÿ ïðåäèêàòû, ôóíêöèè è îïåðàòîðû. Äàæåàâòîìàòû, ìàøèíû è àëãîðèòìû, èçó÷åíèþ êîòîðûõ ïîñâÿùåí íàñòîÿùèé êóðñ, ÿâëÿþòñÿ ìíîæåñòâàìè.Äëÿ ðàáîòû ñ ìíîæåñòâàìè è ôîðìàëèçàöèè îïðåäåëåííûõ ïîíÿòèé íàì ïîòðåáóþòñÿ íåêîòîðûå àêñèîìûZF. Òåîðèÿ ZF ÿâëÿåòñÿ ôîðìàëüíîé (ñèíòàêñè÷åñêîé) òåîðèåé â ÿçûêå ñ îäíèì ñèìâîëîì äâóõìåñòíîãîïðåäèêàòà ∈ è ñèìâîëîì ðàâåíñòâà ≈. Îäíàêî ìû áóäåì ôîðìóëèðîâàòü ïîíÿòèÿè àêñèîìû äàííîé òåîðèè íà åñòåñòâåííîì (îáùåìàòåìàòè÷åñêîì) ÿçûêå.

Ïîäîáíàÿ¾íåñòðîãîñòü¿ íå äîëæíà ïóãàòü ÷èòàòåëÿ, ïîñêîëüêó ïðè æåëàíèè âñå ôîðìóëèðîâêè ìîæíî ¾ïåðåâåñòè¿ íà ôîðìàëüíûé ÿçûê ZF, íî â ðàìêàõ äàííîãî êóðñà â ýòîìíåò íåîáõîäèìîñòè. Äëÿ áîëåå ãëóáîêîãî è ïîäðîáíîãî îçíàêîìëåíèÿ ñ ñèñòåìîé ZFìîæíî ïîðåêîìåíäîâàòü êíèãè [2], [3].Ïîíÿòèÿè∈ ÿâëÿþòñÿ íåîïðåäåëÿåìûìè ÷åðåç äðóãèå ìàòåìàòè÷åñêèå îáúåêòû. Íåôîðìàëüíî ìíîæåñòâî ýòî íåêîòîðàÿ ñîâîêóïíîñòü îáúåêòîâ A, îòíîøåíèå x ∈ A îçíà÷àåò, ÷òî îáúåêò x ÿâëÿåòñÿýëåìåíòîì ñîâîêóïíîñòè A. Ìû òàêæå áóäåì èñïîëüçîâàòü òåðìèíûèäëÿ îïèñàíèÿ íåêîòîðûõ ìíîæåñòâ.òåîðèè ìíîæåñòâ Öåðìåëî-Ôðåíêåëÿìíîæåñòâà îòíîøåíèÿ ïðèíàäëåæíîñòèñîâîêóïíîñòüñåìåéñòâîïîäìíîæåñòâîìÃîâîðÿò, ÷òî ìíîæåñòâî A ÿâëÿåòñÿìíîæåñòâà B ,è ïèøóò A ⊆ B , åñëè ∀x(x ∈ A → x ∈ B).

Äðóãèìè ñëîâàìè, A ⊆ B , åñëè êàæäûéýëåìåíò ìíîæåñòâà A ÿâëÿåòñÿ ýëåìåíòîì ìíîæåñòâà B .Îïðåäåëåíèå.Ðàâåíñòâî äâóõ ìíîæåñòâ A è B îïðåäåëÿåòñÿ ñëåäóþùåé àêñèîìîé.A = B òîãäà è òîëüêî òîãäà, êîãäà ∀x(x ∈ A ↔. Òàêèì îáðàçîì, ìíîæåñòâà A è B ðàâíû, åñëè A ⊆ B è B ⊆ A.Àêñèîìà ýêñòåíñèîíàëüíîñòè:x ∈ B)Ñëåäóþùàÿ åñòåñòâåííàÿ àêñèîìà ïîñòóëèðóåò ñóùåñòâîâàíèå íàèìåíüøåãî ïîâêëþ÷åíèþ ìíîæåñòâà.ñóùåñòâóåò ïóñòîå ìíîæåñòâî ∅, ò.

å. ìíîæåñòâî, íå ñîäåðæàùåå íè îäíîãî ýëåìåíòà.Àêñèîìà ïóñòîãî ìíîæåñòâà:Ñëåäóþùèå ÷åòûðå àêñèîìû ïîçâîëÿþò èç îäíèõ ìíîæåñòâ ñòðîèòü äðóãèå, áîëååñëîæíûå ïî ñâîåé ñòðóêòóðå.åñëè A è B ìíîæåñòâà, òî ñóùåñòâóåò íåóïîðÿäî÷åííàÿ ïàðà, ñîñòàâëåííàÿ èç ýòèõ ìíîæåñòâ.Àêñèîìà ïàðû:{A, B}Ÿ 1. Íåêîòîðûå àêñèîìû òåîðèè ìíîæåñòâ5åñëè A ìíîæåñòâî, òî ñóùåñòâóåò ìíîæåñòâî ∪A = {x |x ∈ y äëÿ íåêîòîðîãî y ∈ A}, êîòîðîå íàçûâàåòñÿ îáúåäèíåíèåì ìíîæåñòâà A.åñëè A ìíîæåñòâî, òî ñóùåñòâóåò ìíîæåñòâî P (A) = {B |B ⊆ A} âñåõ ïîäìíîæåñòâ ìíîæåñòâà A.åñëè A ìíîæåñòâî, à Φ(x) íåêîòîðîå óñëîâèå íà ìíîæåñòâî x, òî ñóùåñòâóåò ìíîæåñòâî {x ∈ A | Φ(x)}.Àêñèîìà ñóììû:Àêñèîìà ñòåïåíè:Àêñèîìà âûäåëåíèÿ:Íàïðèìåð, èç àêñèîìû ïàðû è àêñèîìû îáúåäèíåíèÿ ñëåäóåò, ÷òî åñëè x ìíîæåñòâî, òî {x} ìíîæåñòâî, à çíà÷èò è x ∪ {x} òîæå ÿâëÿåòñÿ ìíîæåñòâîì, êîòîðîåìû áóäåì îáîçíà÷àòü ÷åðåç x + 1.Èç àêñèîìû ïóñòîãî ìíîæåñòâà ñ ïîìîùüþ ââåä¼ííîé îïåðàöèè x + 1 ïîëó÷àåìñóùåñòâîâàíèå ìíîæåñòâ âèäà ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}} è ò.

ä. (êàæäîåñëåäóþùåå ñîñòîèò èç âñåõ ïðåäûäóùèõ), ýòè ìíîæåñòâà ìû áóäåì íàçûâàòüè îáîçíà÷àòü èõ ñîîòâåòñòâåííî ÷åðåç 0, 1, 2, 3 è ò. ä.Çàìåòèì, ÷òî èñïîëüçóÿ òîëüêî òå ïÿòü àêñèîì ¾ñóùåñòâîâàíèÿ¿, êîòîðûå ñôîðìóëèðîâàíû âûøå, ìîæíî ïîëó÷èòü ëèøü êîíå÷íûå ìíîæåñòâà.  ÷àñòíîñòè, èç ýòèõïÿòè àêñèîì íåâîçìîæíî âûâåñòè, ÷òî ¾ñîâîêóïíîñòü¿ âñåõ íàòóðàëüíûõ ÷èñåë îáðàçóåò ìíîæåñòâî. Äëÿ ðàçðåøåíèÿ ýòîãî âîïðîñà ââîäèòñÿ ñëåäóþùàÿíàòó-ðàëüíûìè ÷èñëàìèÀêñèîìà áåñêîíå÷íîñòè:, òî x ∪ {x} ∈ A.x∈Añóùåñòâóåò ìíîæåñòâî A òàêîå, ÷òî ∅ ∈ A è åñëèÌíîæåñòâî A, ñóùåñòâîâàíèå êîòîðîãî ïîñòóëèðóåòñÿ àêñèîìîé áåñêîíå÷íîñòè,îáÿçàíî ñîäåðæàòü âñå íàòóðàëüíûå ÷èñëà è, ñëåäîâàòåëüíî, áåñêîíå÷íî. Áîëåå òîãî,èç àêñèîìû áåñêîíå÷íîñòè ñëåäóåò, ÷òî ñóùåñòâóåò ìíîæåñòâî ω = {0, 1, 2, 3, . . .} âñåõíàòóðàëüíûõ ÷èñåëÒåïåðü, ðàñïîëàãàÿ êàíîíè÷åñêèì áåñêîíå÷íûì ìíîæåñòâîì ω , ìîæíî ñòðîèòüäðóãèå áåñêîíå÷íûå ìíîæåñòâà.

 ñëåäóþùåì îïðåäåëåíèè ââîäÿòñÿ ñòàíäàðòíûåòåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè îáúåäèíåíèÿ, ïåðåñå÷åíèÿ, ðàçíîñòè è äîïîëíåíèÿ (äî íåêîòîðîãî ìíîæåñòâà).îáúåäèíåíèåìÅñëè A è B ìíîæåñòâà, òî èõíàçûâàåòñÿ ìíîæåñòâîA ∪ B = {x | x ∈ A èëè x ∈ B}, ìíîæåñòâî A ∩ B = {x | x ∈ A è x ∈B}, ìíîæåñòâî A \ B = {x | x ∈ A è x ∈/ B}.Åñëè ðàññìàòðèâàåìûå ìíîæåñòâà ÿâëÿþòñÿ ïîäìíîæåñòâàìè íåêîòîðîãî ôèêñèA = U \ A ìíîæåñòâà Aðîâàííîãî ìíîæåñòâà U , òî ìîæíî ãîâîðèòü î(äî ìíîæåñòâà U ).ñåìåéñòâà ìíîæåñòâ A íàçûâàåòñÿ ìíîæåñòâî ∪A = {x | ∃B ∈A(x ∈ B)}.íåïóñòîãî ñåìåéñòâà ìíîæåñòâ A íàçûâàåòñÿ ìíîæåñòâî∩A = {x | ∀B ∈ A(x ∈ B)}.Îïðåäåëåíèå.ðàçíîñòüþïåðåñå÷åíèåìäîïîëíåíèèÎáúåäèíåíèåìÏåðåñå÷åíèåìÈç ïåðå÷èñëåííûõ âûøå àêñèîì ñëåäóåò, ÷òî ïðèìåíÿÿ ýòè îïåðàöèè ê ìíîæåñòâàì, ìû ñíîâà ïîëó÷àåì ìíîæåñòâà.

Íàïðèìåð, åñëè A, B ìíîæåñòâà, òî â ñèëóàêñèîìû ïàðû ñóùåñòâóåò íåóïîðÿäî÷åííàÿ ïàðà {A, B}, à â ñèëó àêñèîìû ñóììûñóùåñòâóåò îáúåäèíåíèå A ∪ B = ∪{A, B}. Çàòåì, èñïîëüçóÿ àêñèîìó âûäåëåíèÿ,çàêëþ÷àåì, ÷òî ñóùåñòâóåò ïåðåñå÷åíèå A ∩ B = {x ∈ A ∪ B | x ∈ A è x ∈ B}.Àêñèîìà ïàðû ïîñòóëèðóåò ñóùåñòâîâàíèå ìíîæåñòâà {a, b}. Îäíàêî ïîðÿäîê ðàñïîëîæåíèÿ ýëåìåíòîâ â ïàðå ôîðìàëüíî íèêàê íå çàäà¼òñÿ, ïîñêîëüêó {a, b} = {b, a}.Áîëåå òîãî, åñëè a = b, òî ïàðà {a, b} ïðåâðàùàåòñÿ â îäíîýëåìåíòíîå ìíîæåñòâî {a}.×òîáû âñ¼-òàêè óïîðÿäî÷èòü ýëåìåíòû ïàðû, ââîäèòñÿ ñëåäóþùåå6Ãëàâà I.

Ïðåäâàðèòåëüíûå ñâåäåíèÿÎïðåäåëåíèå.Óïîðÿäî÷åííîé ïàðîé ýëåìåíòîâ a è b íàçûâàåòñÿ ìíîæåñòâî ha, bi ={{a}, {a, b}}.  óïîðÿäî÷åííîé ïàðå ìû çàäàåì ñòðîãèé ïîðÿäîê ðàñïîëîæåíèÿ ýëåìåíòîâ: a ïåðâûé, b âòîðîé. Ñëåäóåò ðàçëè÷àòü ha, bi =6 {a, b}!Äëÿ ëþáûõ ýëåìåíòîâ a, b, c, d èìååò ìåñòî: ha, bi = hc, di òîãäàè òîëüêî òîãäà, êîãäà a = c è b = d.Äîêàçàòåëüñòâî. Ïðåäëàãàåòñÿ ÷èòàòåëþ â êà÷åñòâå óïðàæíåíèÿ.Ïóñòü n ∈ ω, n > 1. Óïîðÿäî÷åííàÿ n-êà (êîðòåæ äëèíû n) îïðåäåëÿåòñÿ ïî èíäóêöèè: ha1 i = a1 , ha1 , . . . , an−1 , an i = hha1 , . . .

, an−1 i, an i.Ïóñòîå ìíîæåñòâî ∅ ïî îïðåäåëåíèþ íàçûâàåì êîðòåæåì äëèíû 0.ha1 , . . . , an i = hb1 , . . . , bn i òîãäà è òîëüêî òîãäà, êîãäà èìååò ìåñòîa1 = b 1 , . . . , a n = b n .Äîêàçàòåëüñòâî. Ñëåäóåò èç ïðåäûäóùåãî ïðåäëîæåíèÿ ïî èíäóêöèè.Äåêàðòîâûì ïðîèçâåäåíèåì ìíîæåñòâ A1, . . . , An íàçûâàåòñÿ ìíîÏðåäëîæåíèå 1.Îïðåäåëåíèå.Ñëåäñòâèå 2.Îïðåäåëåíèå.æåñòâîA1 × . . . × An = {ha1 , . . .

, an i | a1 ∈ A1 , . . . , an ∈ An }.n-îé äåêàðòîâîé ñòåïåíüþ ìíîæåñòâà A íàçûâàåòñÿ ìíîæåñòâî An = |A × .{z. . × A}.nÏðè n = 0 ïî îïðåäåëåíèþ ïîëàãàåì A0 = {∅}.Ëþáîå ïîäìíîæåñòâî R ⊆ A1 × . . . × An íàçûâàåòñÿ îòíîøåíèåì(ïðåäèêàòîì) íà ìíîæåñòâàõ A1, . . . , An. Åñëè hx1, . . . , xni ∈ R, òî ãîâîðÿò, ÷òî ïðåäèêàò R èñòèííåí íà ýëåìåíòàõ x1, .