|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Дополнительные главы дискретной математики учебный курс
- Автор: Марченков С.С.
- Год создания: 1999
- Организация: МГУ имени М.В. Ломоносова
- Описание: Курс состоит из трех частей. В первой части "Конечные автоматы-распознаватели" вводятся понятия конечного автомата без выхода и конечно-автоматного множества. Конечно-автоматные множества характеризуются в терминах правоинвариантного отношения эквивалентности. Доказывается замкнутость класса конечно-автоматных множеств относительно теоретико-множественных операций и операций произведения и итерации. Вводится понятие регулярного множества и устанавливается совпадение класса конечно-автоматных множеств с классом регулярных множеств. Во второй части "Машины Тьюринга и вычислимые функции" определяются машины Тьюринга и функции, вычислимые на машинах Тьюринга. Рассматриваются операции суперпозиции, примитивной рекурсии, минимизации и доказывается замкнутость класса вычислимых функций относительно этих операций. Определяются классы примитивно-рекурсивных и частично-рекурсивных функций, приводятся примеры функций из этих классов. С использованием формулы Клини доказывается частичная рекурсивность вычислимых функций. Устанавливается существование универсальной машины Тьюринга, выводится ряд следствий из этого факта. Определяются классы P и NP, приводятся примеры задач из этих классов. Вводится понятие NP-полноты и доказывается теорема Кука о NP-полноте проблемы выполнимости КНФ. В третьей части "Конечные автоматы-распознаватели" конечно-автоматные функции определяются с помощью бесконечных деревьев, канонических уравнений, диаграмм Мура и схем из автоматных элементов. Доказывается замкнутость класса конечно-автоматных функций относительно операций суперпозиции и обратной связи. Устанавливается конечная порождаемость класса конечно-автоматных функций относительно этих операций. Доказывается несводимость операции суперпозиции к операции обратной связи.
- Добавил в систему: Марченков Сергей Серафимович
Преподавание курса
- 1 сентября 2015 - 21 декабря 2015 Подымов Владислав Васильевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, вариативной части, семинары, 36 часов
- Автор: Марченков С.С.
- 5 сентября 2014 - 26 декабря 2015 Кафтан Дарья Владимировна
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 36 часов
- Автор: Марченков С.С.
- 1 сентября 2014 - 31 декабря 2016 Бухман Антон Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, семинары, 36 часов
- Автор: Марченков С.С.
- 1 сентября 2002 - 31 декабря 2016 Нагорный Александр Степанович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, семинары, 36 часов
- Автор: Марченков С.С.
- 1 сентября 2000 - 31 декабря 2016 Марченков Сергей Серафимович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 36 часов
- Автор: Марченков С.С.