"Лингвистические основы информатики" Направл.: Математика и компьютерные науки (лекции и практики)
Последнее изменение: 18/02/2025 15:30:32Семестр VI, направление Математика и компьютерные науки, отчетность - ЭКЗАМЕН
Учебные пособия
А.П.Замятин, А.М.Шур. Языки, грамматики, распознаватели
Баллы
Баллы по текущей лекционной аттестации (баллы за тесты, посещ. и активность) группы КН-301 (МЕН-320201) находятся ЗДЕСЬ
Баллы по текущей лекционной аттестации (баллы за тесты, посещ. и акт.) группы КН-302 (МЕН-320202) находятся ЗДЕСЬ
Баллы по текущей лекционной аттестации (баллы за тесты, посещ. и акт.) группы КН-303 (МЕН-320203) находятся ЗДЕСЬ
Баллы по текущей аттестации по практике (посещаемость и акт.) группы КН-301 (МЕН-320201) находятся ЗДЕСЬ
Баллы по текущей аттестации по практике (посещаемость и активность) группы КН-302 (МЕН-320202) находятся ЗДЕСЬ
Баллы по текущей аттестации по практике (посещаемость и активность) группы КН-303 (МЕН-320203) находятся ЗДЕСЬ
Баллы по домашним и контрольным работам по практике группы КН-301 (МЕН-320201) находятся ЗДЕСЬ
Баллы по домашним и контрольным работам по практике группы группы КН-302 (МЕН-320202) находятся ЗДЕСЬ
Баллы по домашним и контрольным работам по практике группы группы КН-303 (МЕН-320203) находятся ЗДЕСЬ
Информация о контрольных работах и подготовке к ним находятся находятся на Странице
Утвержденная рабочая программа дисциплины находится Странице
Online-курс находится на elearn.urfu по ССЫЛКЕ
- Способ реализации: в случае очного формата - лекция в аудитории с использованием проектора, в случае гибридного или дистанционного формата: Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (демонстрация и комментирование презентации лектором; сопровождение записями лектора и студентов на виртуальной доске Idroo, обязательная запись собрания);
- В течение семестра проводится Контрольная работа в виде Тестов и Заданий в курсе на elearn.
- В конце курса - Тест на добор баллов;
- 1 раз за курс - проверка Глоссария через игровые элементы Moodle.
Лекции (34ч)
Лекции-презентации находятся ЗДЕСЬ
Лекция 1. Порождающие грамматики. 11.02.2025
Лекция 2. Рациональные и КС языки. 18.02.2025
Тест №1 (под Moodle). Автоматы (повторение). Основные понятия. Минимальный (приведенный) автомат. Регулярные языки.
Лекция 3. Однозначные грамматики. 25.02.2025
Лекция 4. Приведенные грамматики. 4.03.2025
Тест №2 (под Moodle). Автоматы (повторение). Построение ДКА по НКА и эпсилон НКА. Построение эпсилон НКА по регулярному выражению.
Лекция 5. Эпсилон-свободные грамматики. 11.03.2025
Лекция 6. Нормальная форма Хомского. 18.03.2025
Тест №3 (под Moodle). Порождающие грамматики. Язык, распознаваемый КС-грамматикой.
Лекция 7. Алгоритм Кока-Янгера-Кассами. 25.03.2025
Лекция 8. Вопросы замкнутости класса КС языков относительно регулярных операций. 1.04.2025
Тест №4 (под Moodle). Алгоритм Кока-Янгера-Кассами. Регулярность пересечения регулярных языков.
Лекция 9. Лемма о накачке для КС-языков. 8.04.2025
Лекция 10. Теорема об унарных языках. 15.04.2025
Лекция 11. Синтаксический анализ и автомат с магазинной памятью. 22.04.2025
ТЕСТ НА ДОБОР БАЛЛОВ (под Moodle).
Лекция 12. Распознаваемость с пустым стеком. Эквивалентность двух типов распознаваемости. 29.04.2025
Лекция 13. Распознаваемость контекстно-свободных языков недетерминированными автоматами с магазинной памятью. 6.05.2025
Лекция 14-15. Множество выбора для правила, LL(1)-грамматики. 13.05.2025
Тест №5 (под Moodle). Нахождение FIRST, FOLLOW.
Лекция 16. LL-анализ. Левая факторизация и избавление от левой рекурсии. 20.05.2025
Практики (17ч)
- Способ реализации: решение задач по плану из учебного пособия А.П.Замятин, А.М.Шур. Языки, грамматики, распознаватели, предлагаемых преподавателем;
- в случае очного формата: решение задач на виртуальной доске Idroo с использованием проектора или на меловой доске, возможна запись практик по желанию студентов (организуются самими студентами);
- в случае гибридного формата: решение задач на виртуальной доске Idroo с использованием проектора или на меловой доске (для тех студентов, кто присутствует оффлайн) и трансляция доски Idroo через Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (для тех студентов, кто присутствует онлайн), производится запись собрания;
- в случае дистанционного формата: решение задач на виртуальной доске Idroo и трансляция доски Idroo через Собрание с использованием BBB в курсе "Лингвистические основы информатики" на elearn (в Moodle) (для всех студентов), производится запись собрания;
- В течение семестра назначаются Домашние работы 1-5, а также проводятся Контрольная работа в виде Заданий в курсе на elearn.
- Возможна сдача работ над ошибками с уведомлением преподавателя через чат в курсе на elearn. в течение недели после проверки.
- Общение и консультации с преподавателем вне занятий проводятся при помощи Форумов или Чатов на elearn или Telegram.
- после занятия доска Idroo сохраняется и кладется в курс на elearn.
Практика 1. Порождающие грамматики. 11.02.2025/18.02.2025
Задачи: №7 стр. 84, №6 (а,б,в) стр.84, №16 (ж,а) стр.84.
Домашнее задание №1.
Дедлайн: 24.02.2025
Практика 2. Праволинейные грамматики. КС-грамматики. 25.02.2025/4.03.2025
Задачи: № 3(а,б) стр 84, № 4(в,а) стр.84
Домашнее задание №2.
Дедлайн: 10.03.2025
Практика 3. Однозначные и неоднозначные грамматики. Приведенные грамматики. Эпсилон-свободные грамматики, ацикличные грамматики. 11.03.2025/18.03.2025
Задачи: №12(а) стр. 84, №13 стр. 85, № 1(а) стр. 98, 2(а) стр. 98, №4 стр. 98
Домашнее задание №3. стр. 98: № 1(б), 2(б), 3
Дедлайн: 24.03.2025
Практика 4. Нормальная форме Хомского. Алгоритм Кока-Янгера-Касами (CYK). 25.03.2025/1.04.2025
Задачи L1: Привести к нормальной форме Хомского (ХНФ) грамматику из № 4 стр. 98: G = {S -> SS | (S) | эпсилон}. Проанализировать цепочку длины 6, используя алгоритм Кока-Янгера-Касами (CYK).
L2(a): Привести к нормальной форме Хомского (ХНФ) грамматику, порождающую язык L = {a^n b^m a^m b^n| m,n - натуральные}. Проанализировать цепочку длины 6, используя алгоритм Кока-Янгера-Касами (CYK).
Контрольная работа №1 (домашняя)
Дедлайн: 7.04.2025
Практика 5. Лемма о накачке. 8.04.2025/15.04.2025
L3: Используя теорему о накачке доказать, что язык L не является КС (контекстно-свободным):
а) L = {ww|w - любое слово над алфавитом {a,b}}; - в аудитории
б) L = {a^n b^m c^k| m,n,k - натуральные}; - д.з.
с) L = {a^n b^(n^2)| n - натуральное} - д.з.
Домашнее задание 4. L2 b) Привести к нормальной форме Хомского (ХНФ) грамматику, порождающую язык непустых палиндромов над алфавитом {a,b}. Проанализировать любые цепочки длины 6 и 7, используя алгоритм Кока-Янгера-Касами (CYK).
Дедлайн: 21.04.2025
Практика 6. Лексический анализ. 22.04.2025/29.04.2025
L4: Записать в тетради конспект лекции на тему «Лексический анализ» по книге Замятина, Шура: Часть 2, Глава 1. - д.з.
L5: В следующем фрагменте программы (Python) найти лексемы. Преобразовать фрагмент в цепочку токенов. Какие атрибуты токенов можно использовать?
for i in range(10):
ra+= i
L6: Построить автоматы для шаблонов for, range, <константа>, <спец символы>.
Домашнее задание 5. L3: Используя теорему о накачке доказать, что язык L не является КС (контекстно-свободным): б) L = {a^n b^m c^k| m,n,k - натуральные}; с) L = {a^n b^(n^2)| n - натуральное}
L4: Записать в тетради конспект лекции на тему «Лексический анализ» по книге Замятина, Шура: Часть 2, Глава 1.
Дедлайн: 5.05.2025
Практика 7. Левая рекурсия, левая факторизация, FIRST, FOLLOW, SELECT. ДАМП: управляющая таблица, заполнение пустых ячеек - обработка ошибок. 6.05.2025/13.05.2025
L7: Для данной грамматики: G = {D -> D V C | C, C -> C & x | C & -x | x | -x }:
1) Найти эквивалентную грамматику без левой рекурсии.
2) Выполнить левую факторизацию.
3) Будет ли новая грамматика G" разделенной?
4) Найти массивы FIRST, FOLLOW, SELECT.
5) Будет ли G" LL(1) грамматикой?
6) Построить управляющую таблицу ДАМП.
7) Построить обработчик ошибок.
Контрольная работа №2 (домашняя)
Дедлайн: 21.05.2025
Практика 8. (резерв-обобщающая) 20.05.2025/27.05.2025
Техкарта БРС: 0,3*Текущ.лекц.атт.+0,7*(0,5*Текущ.практ.атт.+0,5*Промеж.практ.атт.(зачет))
Текущ.лекций=Работа на лекции (посещ. и активн.) (20б.)+Контрольная работа(тесты)(80б.)
Текущ.практ.=Работа на практике (посещ.и активн.) (20б.)+Домашняя работа (40б.)+Контрольная работа (1-я+2-я)(20б.+20б.=40б.).
Предварительные даты зачетов:
См. также