С.С. Марченков - Избранные главы дискретной математики

PDF-файл С.С. Марченков - Избранные главы дискретной математики Дополнительные главы дискретной математики (38900): Книга - 5 семестрС.С. Марченков - Избранные главы дискретной математики: Дополнительные главы дискретной математики - PDF (38900) - СтудИзба2019-05-102019-05-10zzyxelСтудИзба

С.С. Марченков - Избранные главы дискретной математики638

Описание файла

PDF-файл из архива "С.С. Марченков - Избранные главы дискретной математики", который расположен в категории "". Всё это находится в предмете "дополнительные главы дискретной математики" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст из PDF

ÌÎÑÊÎÂÑÊÈÉ ÃÎÑÓÄÀÐÑÒÂÅÍÍÛÉ ÓÍÈÂÅÐÑÈÒÅÒèìåíè Ì. Â. ËÎÌÎÍÎÑÎÂÀÔàêóëüòåò âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÑ. Ñ. Ìàð÷åíêîâÈÇÁÐÀÍÍÛÅ ÃËÀÂÛ ÄÈÑÊÐÅÒÍÎÉ ÌÀÒÅÌÀÒÈÊÈÓ÷åáíîå ïîñîáèåÌîñêâà 2015ÓÄÊ 519.71(075.8)ÁÁÊÏå÷àòàåòñÿ ïî ðåøåíèþ ðåäàêöèîííî-èçäàòåëüñêîãî ñîâåòàôàêóëüòåòà Âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêèÌÃÓ èìåíè Ì.Â.

ËîìîíîñîâàÐåöåíçåíòû:, ä.ô.-ì.í., ïðîôåññîð;, ê.ô.-ì.í., äîöåíòÂ.À. ÇàõàðîâÄ.Ñ. ÐîìàíîâÌàð÷åíêîâ Ñ.Ñ.Ó÷åáíîå ïîñîáèå. Ì.: Èçäàòåëüñêèé îòäåë ôàêóëüòåòà ÂÌèÊ ÌÃÓ èì. Ì.Â. Ëîìîíîñîâà(ëèöåíçèÿ ÈÄ 05899 îò 24.09.2001); ÌÀÊÑ Ïðåññ, 2015. 134 ñ.ISBNISBNÈçáðàííûå ãëàâû äèñêðåòíîé ìàòåìàòèêè:Ïîñîáèå íàïèñàíî íà îñíîâå ïîòîêîâîãî êóðñà ¾Äîïîëíèòåëüíûå ãëàâû äèñêðåòíîé ìàòåìàòèêè¿, êîòîðûé àâòîð íà ïðîòÿæåíèè ðÿäà ëåò ÷èòàåò íà ôàêóëüòåòå âû÷èñëèòåëüíîéìàòåìàòèêè è êèáåðíåòèêè ÌÃÓ. Ïîñîáèå ñîñòîèò èõ ÷åòûðåõ ãëàâ. Â ãëàâå 1 ¾Ôóíêöèèìíîãîçíà÷íîé ëîãèêè¿ äàþòñÿ ïåðâîíà÷àëüíûå ñâåäåíèÿ ïî ôóíêöèÿì ìíîãîçíà÷íîé ëîãèêè.

×àñòü èç íèõ èñïîëüçóåòñÿ â ãëàâàõ 2 è 3. Ãëàâà 2 ¾Êîíå÷íûå àâòîìàòû-ðàñïîçíàâàòåëè¿ïîñâÿùåíà îïèñàíèþ êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ â òåðìèíàõ êîíå÷íûõ àâòîìàòîâ, ñ èñïîëüçîâàíèåì ïðàâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè è íà îñíîâå ðåãóëÿðíûõ âûðàæåíèé. Â ãëàâå 3 ¾Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè¿ ðàññìàòðèâàåòñÿ êëàññ êîíå÷íîàâòîìàòíûõ ôóíêöèé, îïðåäåëåííûõ íà áåñêîíå÷íûõ ïîñëåäîâàòåëüíîñòÿõ. Äîêàçûâàåòñÿêîíå÷íàÿ ïîðîæäàåìîñòü ýòîãî êëàññà îòíîñèòåëüíî îïåðàöèé ñóïåðïîçèöèè è îáðàòíîé ñâÿçè è íåâîçìîæíîñòü îáîéòèñü òîëüêî îïåðàöèåé ñóïåðïîçèöèè. Â ãëàâå 4 ¾Ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè¿ îïðåäåëÿþòñÿ ìàøèíû Òüþðèíãà è ôóíêöèè, âû÷èñëèìûå íàìàøèíàõ Òüþðèíãà.

Äîêàçûâàåòñÿ ñîâïàäåíèå äàííîãî êëàññà ôóíêöèé ñ êëàññîì ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Ââîäÿòñÿ ïîíÿòèÿ P-ñâîäèìîñòè è NP-ïîëíîòû. Óñòàíàâëèâàåòñÿñóùåñòâàíèå NP-ïîëíûõ ïðîáëåì. Êàæäûé ïàðàãðàô ñíàáæåí çàäà÷àìè è óïðàæíåíèÿìè.Äëÿ ñòóäåíòîâ, àñïèðàíòîâ è íàó÷íûõ ñîòðóäíèêîâ, ñïåöèàëèçèðóþùèõñÿ â îáëàñòè äèñêðåòíîé ìàòåìàòèêè è êèáåðíåòèêè.ÑÎÄÅÐÆÀÍÈÅÏðåäèñëîâèå .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.......................... 7Îñíîâíûå ïîíÿòèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Ñòàíäàðòíûå ïîëíûå ñèñòåìû . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . 11Àëãîðèòì ðàñïîçíàâàíèÿ ôóíêöèîíàëüíîé ïîëíîòû . . . . . . . . . 16Òåîðåìà Êóçíåöîâà î ôóíêöèîíàëüíîé ïîëíîòå . . . . . . . . . . . . . .19Çàìêíóòûå êëàññû, íå èìåþùèå êîíå÷íûõ áàçèñîâ . . . . . . . . . . 22Ãëàâà 1. Ôóíêöèè ìíîãîçíà÷íîé ëîãèêè1.2.3.4.5.Ãëàâà 2. Êîíå÷íûå àâòîìàòû-ðàñïîçíàâàòåëè . . . . . . . . . . . . . . .

. . . . 25 1. Êîíå÷íûé àâòîìàò áåç âûõîäà. Êîíå÷íî-àâòîìàòíûåìíîæåñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 2. Ïðàâîèíâàðèàíòíàÿ ýêâèâàëåíòíîñòü. Òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè íàä êîíå÷íî-àâòîìàòíûìè ìíîæåñòâàìè . . . . . .29 3. Íåäåòåðìèíèðîâàííûå àâòîìàòû . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . 34 4. Îïåðàöèè ïðîèçâåäåíèÿ è èòåðàöèè . . . . . . . . . . . . . . . . . . . . . . . . . 36 5. Ðåãóëÿðíûå ìíîæåñòâà. Òåîðåìà Êëèíè . . . . . . . . . . . . . . . . . . . . . 40Ãëàâà 3. Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè . . . . . . . . . . . . . . . . . .441.2.3.4.5.Êîíå÷íûé àâòîìàò ñ âûõîäîì. Òåîðåìà Ìóðà . . . . . . . . .

. . . . . . 44Îñòàòî÷íûå ôóíêöèè. Âåñ ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . 48Êîíå÷íûå àâòîìàòû íà ñâåðõñëîâàõ . . . . . . . . . . . . . . . . . . . . . . . . . .51Îïåðàöèè ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè . . . . .

. . . . 56Êîíå÷íàÿ ïîðîæäàåìîñòü êëàññà êîíå÷íî-àâòîìàòíûõôóíêöèé. Íåñâîäèìîñòü îïåðàöèè ââåäåíèÿ îáðàòíîé ñâÿçèê îïåðàöèè ñóïåðïîçèöèè . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60. . . . . . . . . 65Ìàøèíà Òüþðèíãà . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Êîìïîçèöèÿ è èòåðàöèÿ ìàøèí Òüþðèíãà . . . . . . . . . . . . . . . . . . . 70Ìîäåëèðîâàíèå ìàøèí Òüþðèíãà . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74Îïåðàöèè ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèèè ìèíèìèçàöèè . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77Óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Êëàññû P è NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.89Ãëàâà 4. Ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè1.2.3.4. 5. 6.7. NP-ïîëíîòà. Òåîðåìà Êóêà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 948. Ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè . . . . . . . . . . . . . . . . . . . . . . . . . 1029. Êëàññ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé . . . . . . . . . . . . . . . . . . . . . 10810. ×àñòè÷íàÿ ðåêóðñèâíîñòü âû÷èñëèìûõ ôóíêöèé.Ôîðìóëà Êëèíè . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114Îòâåòû, ðåøåíèÿ, óêàçàíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117Ñïèñîê ëèòåðàòóðû. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . 1324ÏÐÅÄÈÑËÎÂÈÅÂ êóðñàõ äèñêðåòíîé ìàòåìàòèêè, ÷èòàåìûõ â ðîññèéñêèõ óíèâåðñèòåòàõ (à òàêæå â çíà÷èòåëüíîì ÷àñòè òåõíè÷åñêèõ âóçîâ), ñëîæèëñÿ îïðåäåëåííûé êðóã îáÿçàòåëüíûõ ðàçäåëîâ, áåç êîòîðûõ èçëîæåíèå äèñêðåòíîéìàòåìàòèêè íå ìîæåò ñ÷èòàòüñÿ ïîëíîöåííûì. Ê òàêèì ðàçäåëàì ñëåäóåò â ïåðâóþ î÷åðåäü îòíåñòè ðàçäåëû, ïîñâÿùåííûå áóëåâûì ôóíêöèÿìè èõ îáîáùåíèÿì ôóíêöèÿì ìíîãîçíà÷íîé ëîãèêè, êîíå÷íûì àâòîìàòàì, ìàøèíàì Òüþðèíãà è âû÷èñëèìûì ôóíêöèÿì.

Â ðàçëè÷íûõ êóðñàõ äèñêðåòíîé ìàòåìàòèêè äàííûå ðàçäåëû ìîãóò áûòü ïðåäñòàâëåíûïî-ðàçíîìó: ýòî êàñàåòñÿ íå òîëüêî îáúåìà ìàòåðèàëà, âêëþ÷åííîãî âðàçäåëû, íî è ñòåïåíè ïîäðîáíîñòè è ïðîðàáîòêè âõîäÿùèõ â íèõ òåì.Â Ìîñêîâñêîì ãîñóäàðñòâåííîì óíèâåðñèòåòå îáÿçàòåëüíûé êóðñ äèñêðåòíîé ìàòåìàòèêè âïåðâûå áûë ïðî÷èòàí Ñ.Â.

ßáëîíñêèì íà ôàêóëüòåòå âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè â 1971 ãîäó. Â 1979 ã. ïîÿâèëîñü ïåðâîå èçäàíèå ó÷åáíèêà Ñ.Â. ßáëîíñêîãî ¾Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó¿ [?], à äâóìÿ ãîäàìè ðàíåå ïåðâîå èçäàíèå ñáîðíèêà¾Çàäà÷è è óïðàæíåíèÿ ïî äèñêðåòíîé ìàòåìàòèêå¿ [?] Ã.Ï. Ãàâðèëîâà èÀ.À. Ñàïîæåíêî. Âïîñëåäñòâèè ýòè êíèãè íåñêîëüêî ðàç ïåðåèçäàâàëèñüè ïåðåâîäèëèñü íà äðóãèå ÿçûêè. Íå áóäåò ïðåóâåëè÷åíèåì ñêàçàòü, ÷òîîíè âíåñëè çíà÷èòåëüíûé âêëàä â ñòàíîâëåíèå è ðàçâèòèå äèñêðåòíîéìàòåìàòèêè â íàøåé ñòðàíå.Íà ôàêóëüòåòå âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè ÌÃÓ êóðñäèñêðåòíîé ìàòåìàòèêè ðàçáèò íà äâå ÷àñòè: ïåðâàÿ áàçîâàÿ ÷èòàåòñÿ âñåì ïîòîêàì ïåðâîãî êóðñà; âòîðàÿ ¾Äîïîëíèòåëüíûå ãëàâûäèñêðåòíîé ìàòåìàòèêè¿ â ïÿòîì ñåìåñòðå íà âòîðîì ïîòîêå. È åñëè áàçîâàÿ ÷àñòü íå ïðåòåðïåëà ñóùåñòâåííûõ èçìåíåíèé ïî ñðàâíåíèþñ êóðñîì (è ó÷åáíèêîì) Ñ.Â.

ßáëîíñêîãî (ñîâðåìåííîå èçëîæåíèå ýòîé÷àñòè èìååòñÿ â êíèãå [?] Â.Á. Àëåêñååâà), òî âî âòîðîé ÷àñòè ïðîèçîøëè çíà÷èòåëüíûå èçìåíåíèÿ. Ïîÿâèëàñü ïîòðåáíîñòü â èçëîæåíèè ýòîé÷àñòè â âèäå îòäåëüíîãî ó÷åáíîãî ïîñîáèÿ.Â íàñòîÿùåì ó÷åáíîì ïîñîáèè ïðåäñòàâëåíû òðè ðàçäåëà äèñêðåòíîéìàòåìàòèêè: ôóíêöèè ìíîãîçíà÷íîé ëîãèêè, êîíå÷íûå àâòîìàòû, ìàøèíû Òüþðèíãà è âû÷èñëèìûå ôóíêöèè.

Ïîñëåäíèå äâà ðàçäåëà ñîñòàâëÿþò êóðñ ¾Äîïîëíèòåëüíûå ãëàâû äèñêðåòíîé ìàòåìàòèêè¿, êîòîðûéàâòîð íà ïðîòÿæåíèè ðÿäà ëåò ÷èòàåò íà ôàêóëüòåòå âû÷èñëèòåëüíîé ìàòåìàòèêè è êèáåðíåòèêè. Ðàçäåë ¾Ôóíêöèè ìíîãîçíà÷íîé ëîãèêè¿ âêëþ÷åí â ïîñîáèå, ÷òîáû îáåñïå÷èòü ïîëíîòó è íåçàâèñèìîñòü äîêàçàòåëüñòâ5íåêîòîðûõ óòâåðæäåíèé äëÿ êîíå÷íûõ àâòîìàòîâ. Â ïîñîáèå íå âêëþ÷åíà ãëàâà ïî áóëåâûì ôóíêöèÿì, ïîñêîëüêó â íàñòîÿùåå âðåìÿ èìååòñÿíåñêîëüêî äîñòóïíûõ êíèã (ñì., íàïðèìåð, [?, ?, ?]), â êîòîðûõ ýòà òåìàèçëîæåíà äîñòàòî÷íî ïîäðîáíî.Ðàçäåë ¾Êîíå÷íûå àâòîìàòû¿ â ïîñîáèè ðàçáèò íà äâå ãëàâû: ¾Êîíå÷íûå àâòîìàòû-ðàñïîçíàâàòåëè¿ è ¾Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè¿.Â ïåðâîé èç ýòèõ ãëàâ ñîäåðæèòñÿ ìàòåðèàë, êîòîðûé ñðàâíèòåëüíî ðåäêî âñòðå÷àåòñÿ â ó÷åáíèêàõ ïî äèñêðåòíîé ìàòåìàòèêå.

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

Поделитесь ссылкой:

Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.

Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.

Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.

Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.

Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.

Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.

Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.

Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.

Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.

Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.

Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.

Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.