1610906281-d25a58898a45262b0b837c281ba962eb (824376)
Текст из файла
Íà ïðàâàõ ðóêîïèñèÍÎÂÎÑÈÁÈÐÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒÌåõàíèêî-ìàòåìàòè÷åñêèé ôàêóëüòåòÍ. Ò. Êîãàáàåâ, Þ. Þ. ÑîêîëîâàÄÐÓÃÈÅ ËÅÊÖÈÈ ÏÎÒÅÎÐÈÈ ÀËÃÎÐÈÒÌÎÂÓ÷åáíîå ïîñîáèåÍîâîñèáèðñê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, .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
