|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Модели вычисленийучебный курс
- Авторы: Захаров В.А., Подловченко Р.И.
- Год создания: 2015
- Организация: МГУ имени М.В. Ломоносова
- Описание: Цель учебного курса – ознакомить студентов, специализирующихся в области прикладной математики и информатики, с основными понятиями, моделями и методами решения задач таких разделов теории вычислений как теория автоматов, теория формальных языков, формальные методы верификации, прикладные логики; все перечисленные модели, методы их построения и анализа используются для решения прикладных задач программирования и информатики. Содержание лекций Раздел 1. Конечные автоматы и регулярные языки Детерминированные и недетерминированные конечные автоматы. Преобразование конечного автомата к детерминированному виду. Минимизация детерминированных автоматов. Автоматные языки и их алгебраические свойства. Лемма о разрастании для автоматных языков. Регулярные выражения и их свойства. Уравнения в регулярных выражениях. Теорема Клини. Двусторонние конечные автоматы. Многоленточные автоматы. Применение конечных автоматов для решения прикладных задач программирования и информатики Раздел 2. Универсальные модели вычислений Машины Тьюринга. Рекурсивные и рекурсивно перечислимые множества. Универсальные модели вычислений: ассоциативные вычисления, машины Минского, многоголовочные автоматы. Примеры алгоритмически неразрешимых задач алгебры и комбинаторики. Раздел 3. Автоматы-преобразователи и рациональные отношения. Свойства замкнутости рациональных отношений. Проблема эквивалентности для автоматов-преобразователей. Автоматы над бесконечными словами и темпоральные логики Автоматы над бесконечными словами (автоматы Бюхи, Рабина, Мюллера) и их свойства. -регулярные языки. Монадическая логика 2-го порядка S1S и ее взаимосвязь с автоматами над бесконечными словами. Детерминизация автоматов над бесконечными словами. Раздел 4. Формальные грамматики и автоматы с магазинной памятью Автоматы с магазинной памятью и их свойства. Алгоритмически неразрешимые проблемы анализа поведения автоматов с магазинной памятью. Формальные грамматики и иерархия языков Хомского. Контекстно-свободные языки. Нормальные формы контекстно-свободных грамматик. Лемма о разрастании для контекстно-свободных языков. Характеризация контекстно-свободных языков автоматами с магазинной памятью. Задачи синтаксического анализа и табличные методы синтаксического разбора. Детерминированные автоматы с магазинной памятью и LL(1) грамматики.
- Добавил в систему: Захаров Владимир Анатольевич
Преподавание курса
- 7 февраля 2023 - 1 мая 2023 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 12 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 7 февраля 2023 - 1 мая 2023 Савицкий Игорь Владимирович
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 24 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 7 февраля 2022 - 17 апреля 2022 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 32 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 8 февраля 2021 - 18 апреля 2021 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 32 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 10 февраля 2020 - 19 апреля 2020 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 32 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 7 февраля 2018 - 20 мая 2018 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 24 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 7 февраля 2017 - 20 мая 2017 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 24 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 7 февраля 2016 - 20 мая 2016 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, семинары, 26 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 7 февраля 2016 - 20 мая 2016 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 26 часов
- Авторы: Захаров В.А., Подловченко Р.И.
- 9 февраля 2015 - 15 апреля 2015 Захаров Владимир Анатольевич
- МГУ имени М.В. Ломоносова, Факультет вычислительной математики и кибернетики, Кафедра математической кибернетики
- обязательная, вариативной части, лекции, 26 часов
- Авторы: Захаров В.А., Подловченко Р.И.