|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Дополнительные главы дискретной математики и кибернетикиучебный курс
- Авторы: Марченков С.С., Ложкин С.А.
- Год создания: 2018
- Организация: МГУ имени М.В. Ломоносова
- Описание: Курс состоит из трех частей. В первой части "Конечные автоматы" рассматриваются конечные автоматы-распознаватели и конечные автоматы-преобразователи. Множества, допускаемые конечными автоматами-распознавателями, характеризуются тремя различными способами: непосредственно через автоматы, с помощью правоинвариантного отношения эквивалентности и посредством регулярных выражений Клини. Доказывается, что недетерминированные конечные автоматы не расширяют класса множеств, допускаемых конечными автоматами. Для класса конечно-автоматных функций, реализуемых конечными автоматами-преобразователями, даются определения с помощью бесконечных нагруженных деревьев, через диаграммы Мура и с помощью канонических уравнений. Определяется операция введения обратной связи и доказывается, что класс конечно-автоматных функций имеет конечный базис относительно операций суперпозиции и введения обратной связи. Во второй части "Машины Тьюринга и вычислимые функции" вводится понятие машины Тьюринга, рассматриваются операции композиции и итерации для машин Тьюринга и доказывается существование универсальной машины Тьюринга. Определяется класс функций, вычислимых на машинах Тьюринга, и устанавливается его замкнутость относительной операций суперпозиции, примитивной рекурсии и минимизации. Изучаются классы примитивно-рекурсивных и частично-рекурсивных функций. Устанавливается формула Клини и доказывается совпадение классов частично-рекурсивных функций и функций, вычислимых на машинах Тьюринга. Определяются классы P и NP, вводится понятие NP-полноты и доказывается теорема Кука о NP-полноте проблемы ВЫПОЛНИМОСТЬ. Устанавливается полиномиальная разрешимость проблемы 2-ВЫПОЛНИМОСТЬ. В третьей части "Сложность реализации функций алгебры логики" рассматривается сложность схем из функциональных элементов для функций из специальных классов. Приводятся асимптотически наилучшие методы синтеза для функций из ненулевых квазиинвариантных классов и для не всюду определенных функций. Излагается метод локального кодирования О.Б. Лупанова. Доказывается теорема Сэвиджа, рассматривается метод забивающих констант и его применение для линейной и некоторых других функций. Определяется сложность линейной и близких к ней функций в классе контактных схем и самокорректирующихся контактных схем. Доказывается теорема В.М.Храпченко о сложности линейной функции в классе п-схем.
- Добавил в систему: Марченков Сергей Серафимович
Преподавание курса
- 1 сентября 2023 - 31 декабря 2023 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2023 - 31 декабря 2023 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 24 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2023 - 31 декабря 2023 Ложкин Сергей Андреевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 12 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2022 - 31 декабря 2022 Ложкин Сергей Андреевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 13 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2022 - 31 декабря 2022 Бухман Антон Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, семинары, 64 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2022 - 31 декабря 2022 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 108 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2022 - 31 декабря 2022 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 16 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2022 - 30 декабря 2022 Нагорный Александр Степанович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 108 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2021 - 31 декабря 2021 Селезнева Светлана Николаевна
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 12 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2021 - 31 декабря 2021 Ложкин Сергей Андреевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 18 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2021 - 31 декабря 2021 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 24 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2021 - 31 декабря 2021 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 72 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2020 - 31 декабря 2020 Ложкин Сергей Андреевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 27 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2020 - 31 декабря 2020 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2019 - 31 декабря 2020 Марченков С.С.
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 27 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2019 - 31 декабря 2020 Марченков С.С.
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 27 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2019 - 30 декабря 2020 Марченков Сергей Серафимович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, лекции, 27 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2019 - 31 декабря 2019 Ложкин Сергей Андреевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 27 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2019 - 31 декабря 2019 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2019 - 31 декабря 2019 Нагорный Александр Степанович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, семинары, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2018 - 31 декабря 2018 Селезнева Светлана Николаевна
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, семинары, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2018 - 31 декабря 2018 Бухман Антон Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, семинары, 72 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2018 - 31 декабря 2018 Марченков Сергей Серафимович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики
- обязательная, базовой части, лекции, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2018 - 31 декабря 2018 Ложкин Сергей Андреевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, лекции, 18 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2018 - 31 декабря 2018 Вороненко Андрей Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, семинары, 72 часов
- Авторы: Марченков С.С., Ложкин С.А.
- 1 сентября 2018 - 31 декабря 2018 Нагорный Александр Степанович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, базовой части, семинары, 36 часов
- Авторы: Марченков С.С., Ложкин С.А.