Вопросы по курсу Дополнительные главы дискретной математики
Описание файла
PDF-файл из архива "Вопросы по курсу Дополнительные главы дискретной математики", который расположен в категории "". Всё это находится в предмете "дополнительные главы дискретной математики" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
ÂÎÏÐÎÑÛ ÏÎ ÊÓÐÑÓ"ÄÎÏÎËÍÈÒÅËÜÍÛÅ ÃËÀÂÛ ÄÈÑÊÐÅÒÍÎÉ ÌÀÒÅÌÀÒÈÊÈ"(3 êóðñ, 2 ïîòîê, ëåêòîð ïðîôåññîð Ñ.Ñ. ÌÀÐ×ÅÍÊÎÂ)I. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ-ÐÀÑÏÎÇÍÀÂÀÒÅËÈ1. Êîíå÷íûé àâòîìàò-ðàñïîçíàâàòåëü, êîíå÷íî-àâòîìàòíîå ìíîæåñòâî.2. Ïðàâîèíâàðèàíòíîå îòíîøåíèå ýêâèâàëåíòíîñòè, ñâÿçü ñ êîíå÷íî-àâòîìàòíûìèìíîæåñòâàìè.3. Çàìêíóòîñòü êëàññà êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ îòíîñèòåëüíî òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé.4. Íåäåòåðìèíèðîâàííûå àâòîìàòû, ïðîöåäóðà äåòåðìèíèçàöèè.5.
Îïåðàöèè ïðîèçâåäåíèÿ è èòåðàöèè. Çàìêíóòîñòü êëàññà êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ îòíîñèòåëüíî îïåðàöèé ïðîèçâåäåíèÿ è èòåðàöèè.6. Ðåãóëÿðíûå âûðàæåíèÿ è ðåãóëÿðíûå ìíîæåñòâà.7. Òåîðåìà Êëèíè, îñíîâíàÿ èäåÿ äîêàçàòåëüñòâà.II. ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÂÛ×ÈÑËÈÌÛÅ ÔÓÍÊÖÈÈ8. Ìàøèíû Òüþðèíãà. Ôóíêöèè, âû÷èñëèìûå íà ìàøèíàõ Òüþðèíãà.9. Îïåðàöèè êîìïîçèöèè è èòåðàöèè íàä ìàøèíàìè Òüþðèíãà.10. Ìîäåëèðîâàíèå ìàøèí Òüþðèíãà.11. Îïåðàöèè ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèè è ìèíèìèçàöèè íàä ÷àñòè÷íûìèôóíêöèÿìè.12. Çàìêíóòîñòü êëàññà ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà, îòíîñèòåëüíîîïåðàöèé ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèè è ìèíèìèçàöèè.13. Êëàññ ïðèìèòèâíî-ðåêóðñèâíûõ ôóíêöèé. Ïðîñòåéøèå ïðèìèòèâíî-ðåêóðñèâíûåôóíêöèè.14. Îïåðàöèÿ ìèíèìèçàöèè.
Êëàññ ÷àñòè÷íî-ðåêóðñèâíûõ ôóíêöèé. Ïðèìåðû÷àñòè÷íî-ðåêóðñèâíûõ ôóíêöèé.15. ×àñòè÷íàÿ ðåêóðñèâíîñòü âû÷èñëèìûõ ôóíêöèé. Ôîðìóëà Êëèíè.16. Óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà. Óíèâåðñàëüíàÿ ÷àñòè÷íî-ðåêóðñèâíàÿôóíêöèÿ.17. Êëàññû18.19.20.PèNP .Ïðèìåðû çàäà÷ èç êëàññàN P -ïîëíîòà. Òåîðåìà Êóêà, îñíîâíàÿN P -ïîëíîòà çàäà÷è 3-ÂÛÏ.N P -ïîëíîòà çàäà÷è ¾ÊËÈÊÀ¿.NP .èäåÿ äîêàçàòåëüñòâà.21. Ïîëèíîìèàëüíàÿ ðàçðåøèìîñòü çàäà÷è 2-ÂÛÏ.III. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ-ÏÐÅÎÁÐÀÇÎÂÀÒÅËÈ8. Äåòåðìèíèðîâàííûå ôóíêöèè. Çàäàíèå äåòåðìèíèðîâàííûõ ôóíêöèé äåðåâüÿìè.Âåñ äåðåâà.22.
Êàíîíè÷åñêèå óðàâíåíèÿ, âåêòîðíàÿ è ñêàëÿðíàÿ ôîðìû êàíîíè÷åñêèõ óðàâíåíèé.23. Çàìêíóòîñòü êëàññà êîíå÷íî-àâòîìàòíûõ ôóíêöèé îòíîñèòåëüíî îïåðàöèè ñóïåðïîçèöèè, îñíîâíàÿ èäåÿ äîêàçàòåëüñòâà.24. Çàâèñèìîñòü ñ çàïàçäûâàíèåì. Îïåðàöèÿ ââåäåíèÿ îáðàòíîé ñâÿçè.25. Ñóùåñòâîâàíèå êîíå÷íûõ ïîëíûõ ñèñòåì â êëàññå êîíå÷íî-àâòîìàòíûõ ôóíêöèé.26. Íåñâîäèìîñòü îïåðàöèè ââåäåíèÿ îáðàòíîé ñâÿçè ê îïåðàöèè ñóïåðïîçèöèè,îñíîâíàÿ èäåÿ äîêàçàòåëüñòâà.ËÈÒÅÐÀÒÓÐÀ1. Ìàð÷åíêîâ Ñ.Ñ.
Èçáðàííûå ãëàâû äèñêðåòíîé ìàòåìàòèêè. Ì.: ÌÀÊÑ Ïðåññ,2016. 133 ñ.2. ßáëîíñêèé Ñ.Â. Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó. Ì.: Âûñøàÿ øêîëà, 2003.384 ñ..
