Alexander Sayapin Teacher's site

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

Posted on Mon 07 September 2020

In Архив.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

tags

алфавит (1) архитектура ЭВМ (3) asp.net (1) бгд (22) бисв (23) бкб (22) бме (22) бпэ (23) бпэз (4) бпэзу (1) бпм (19) бпм объявления (7) certbot (1) cheatsheet (1) checkinstall (1) csv (1) дискретная математика (25) экзамен (1) embedded rust (2) english (1) формальные грамматики (1) gdb (2) язык (1) исследование операций (1) jupyter (1) критерии (2) курсовая работа (2) lighttpd (2) low-latency (1) machine learning (3) make (1) make install (1) markdown (1) машинное обучение (1) математическая лингвистика (1) математическая логика (1) математическая статистика (1) Математические основы кмпьютерной графики (1) Математические основы компьютерного моделирования (1) Математические основы компьютерной графики (1) Методы оптимизации (17) методы оптмимизации (1) методы принятия решений (1) миа (6) мии (8) мик (7) мим (7) мио (4) мип (9) мит (44) миу (13) миз (12) ml (1) mono (1) мпм (6) natural language processing (1) nlp (1) nucleo (2) объявления (31) оформление (2) openocd (2) openpgp (1) pandas (1) pgp (1) подтверждение вывода (1) programming (3) python (3) robot (1) robotics (2) setup (6) шпаргалка (1) smartcard (1) ssh (1) ssl (1) STM32 (2) streaming (1) строка (1) тб (21) teaching (1) teaching statement (1) Теоретические основы цифровой обработки изображений (2) тест (1) учебник (1) up board (1) video (1) вкр (2) xls (1)