Alexander Sayapin Teacher's site

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

Posted on Mon 08 February 2021

In Архив.

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

Добрый день!

Продолжаем курс "Дополнительные главы дискретной математики".

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

В этом семестре мы продолжим рассмотрение формалльных грамматик и автоматов, а так же рассмотрим некоторые другие темы.

Список заданий на текущий семестр и список литературы будут обновлены до 15.02.2021.

Решение заданий вам необходимо прислать в виде ссылки на 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 справа).