Alexander Sayapin Teacher's site

Дополнительные главы дискретной математики для МИТ19-01 / осень 2020

Posted on Mon 07 September 2020

In Архив.

tags: дискретная математика мит

Курс дискретной математики рассчитан на 1 семестр, в конце курса предусмотрен экзамен.

Итоговая оценка выставляется в соответствии с требованиями балльно-рейтинговой системы (см. критерии оценки на экзамене). Для допуска к экзамену необходимо выполнить и защитить все практические работы (ориентировочно 12 штук) и получить не менее 51 балла в течение семестра.

Начать изучение курса можно с неформального введения в формальные грамматики.

Список заданий:

• Формальные грамматики. При выполнении работы можно использовать следующие материалы: текст по формальным грамматикам, Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010, стр. 77, В.С. Фомичев Формальные языки, грамматики и автоматы[электр]. Для выполнения работы так же необходима программа JFLAP, так же доступная с этого сайта, для запуска необходима установленная на компьютере JAVA. Описание работы с программой имеется в методичке.
  • Список адресов для самопроверки, допустимые:
    • a@a.a
    • aa@a.a
    • a@aaaa.a
    • a@a.aaaa
    • a.a@a.a
    • a.a@a.a.a
    • a.a.a@a.a
    • a@a.aa.a
    • a@aa.aa.aa
  • Список адресов для самопроверки, недопустимые:
    • a
    • aa
    • a@
    • @a
    • a@a
    • a@a.
    • a@.a
    • a@a.
    • a.@a.a
    • .a@a.a
    • a..a@a.a
    • a.a@a..a
    • a.a@a.a.a.
  • Список так же доступен в виде файла, можно использовать для проверки в JFLAP, выбрав в меню пункты Input/Multiple Brute Force Parse, и нажав кнопку Load Inputs. Учтите, проверка потребует времени, поскольку производится методом брутфорса (фактически, полного перебора всех правил с проверкой их применимости на каждом этапе разбора)
• Классификация грамматик и их представления. При выполнении работы можно использовать следующие материалы: Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010, стр. 86-88, В.С. Фомичев Формальные языки, грамматики и автоматы (1.3. Типы формальных грамматик, 1.4.1. Форма Бекуса-Наура, 1.4.3. Синтаксическая диаграмма)
• Конечные автоматы-распознаватели. При выполнении работы можно использовать следующие материалы: Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010, стр. 102-105., Дискретная математика: учебное пособие/ В.М. Пестриков, В.С.Дудкин, Г.А.Петров. - Санкт-Петербург: 2013, стр. 1-6.

Список заданий будет расширен.

Решение заданий вам необходимо прислать в виде ссылки на Google Docs.

Для этого вам необходимо:

1. Иметь учетную запись Google (например, почту на gmail).
2. Войти в учетную запись Google
3. Перейти по ссылке на задание, расположенной ниже
4. Нажать кнопку Создать копию
5. Выполнить задание непосредственно в браузере, записывая ответы в предназначенные для них ячейки
6. Нажать кнопку Настройки доступа и выбрать пункт Комментирование
7. В поле Введите имена или адреса эл. почты введите alstutor@gmail.com и нажмите кнопку Отправить

Если работа принята, в блокноте появится комментарий Принято, в противном случае будет указано, где именно имеются ошибки.

При изучении курса так же можно использовать следующую литературу:

При выполнении заданий можно использовать следующие источники:

• Дискретная математика: учебное пособие/ А. В. Саяпин, Т. А. Сливина. - Красноярск: СибГАУ, 2010

• Ф. А. Новиков Дискретная математика. 2-е изд. – С-Пб.: Питер, 2013 г.

• Эвнин А. Ю. Дискретная математика. Конспект лекций. – Челябинск: ЮУрГУ, 1998.

• В.С. Фомичев Формальные языки, грамматики и автоматы[электр].

• Мозговой М.В. Программирование. Классика программирования: алгоритмы, языки, автоматы.- М.: Наука и техника, 2006.

Примерный список вопросов к экзамену (состав и количество вопросов могут быть откорректированы):

1. Формальные языки, грамматики и автоматы. Язык, строка, алфавит. Основные понятия.

2. Формальные языки. Понятие формальной грамматики.

3. Формальная грамматика. Вывод (цепочка вывода). Вывод, непосредственный вывод, отношение выводимости, язык, порождаемый грамматикой

4. Формальная грамматика. Классификация грамматик. Примеры грамматик.

5. Формальная грамматика. Вывод в КС-грамматиках и правила построения дерева вывода. Синтаксический разбор, левый и правый вывод.

6. Формальная грамматика. Неоднозначные грамматики. Неоднозначные и эквивалентные грамматики.

7. Формальные языки и грамматики. Рекурсия в языке. Рекурсивные правила, их классификация.

8. Формальные языки и грамматики. Способы описания правил в грамматиках. БНФ и РБНФ.

9. Формальные языки, грамматики и автоматы. Регулярный язык и его особенности.

10. Формальная грамматика. Способы описания правил в грамматиках. Синтаксическая диаграмма. как способ описания грамматики.

11. Автоматные грамматики и конечные автоматы. Распознаватель.

12. Конечные автоматы. Детерминированные и недетерминированные конечные автоматы.

13. Детерминированные и недетерминированные конечные автоматы. Преобразования автоматов. Эквивалентные состояния и автоматы. Минимизация конечного автомата.

14. Теория автоматов. Связь недетерминированных и детерминированных автоматов. Переход из НКА без переходов по пустой строке в ДКА.

15. Теория автоматов. Конечные автоматы. Синтез и анализ конечного автомата. Преобразование регулярной грамматики в конечный автомат. Примеры.

16. Теория автоматов. Автоматы с магазинной памятью. Их связь с КС-грамматиками.

17. Теория автоматов. Формальные языки, грамматики и автоматы. Контекстно-свободные грамматики и МП-автоматы. Синтаксический анализ.

18. Теория автоматов. Контекстно-свободные грамматики и МП-автоматы. Синтаксический анализ. LL(1)-грамматика.

По всем вопросам можно писать на электронную почту (ссылка mail me справа).