Учебно-методические комплексы

Подробнее

дизъюнкция (∨), отрицание (¬), импликация (→), эквиваленция (↔), сложение по модулю 2 (⊕);
✓ Таблицы истинности для формул алгебры высказываний;
✓ Равносильные преобразования формул (законы логики);
✓ Дизъюнктивная и конъюнктивная нормальные формы (ДНФ, КНФ);
✓ Совершенные нормальные формы (СДНФ, СКНФ) — алгоритм построения;
✓ Минимизация булевых функций (метод неопределенных коэффициентов, карты Карно);
✓ Полином Жегалкина;
✓ Булевы функции и их способы задания.
Раздел 2. Теория множеств:
✓ Основные понятия теории множеств (способы задания, мощность);
✓ Операции над множествами (объединение, пересечение, дополнение, разность);
✓ Диаграммы Эйлера-Венна (графическое изображение множеств);
✓ Декартово произведение множеств.
Раздел 3. Предикаты и логика предикатов:
✓ Понятие предиката (область определения, область истинности);
✓ Кванторы существования (∃) и общности (∀);
✓ Отрицание предикатов, содержащих кванторы;
✓ Конъюнкция, дизъюнкция и отрицание предикатов.
Раздел 4. Бинарные отношения:
✓ Определение и свойства бинарных отношений (рефлексивность, симметричность, транзитивность);
✓ Исследование свойств бинарных отношений.
Раздел 5. Теория графов:
✓ Основные понятия теории графов (вершины, ребра);
✓ Виды графов (ориентированные, неориентированные);
✓ Способы задания графов (матрица смежности, матрица инциденций);
✓ Эйлеровы и гамильтоновы графы;
✓ Деревья.
Раздел 6. Теория алгоритмов:
✓ Понятие алгоритма (массовая и индивидуальная задача);
✓ Основные свойства алгоритмов (дискретность, определенность, результативность, массовость);
✓ Исполнитель алгоритма и его характеристики;
✓ Машина Тьюринга (принцип работы).
3. ТИПЫ ОЦЕНОЧНЫХ ЗАДАНИЙ
Для текущего контроля (практические работы):
✓ Определение истинности высказываний, построение составных высказываний;
✓ Построение таблиц истинности для формул (вручную и с использованием Excel);
✓ Приведение формул к ДНФ и КНФ с помощью равносильных преобразований;
✓ Построение СДНФ и СКНФ для булевых функций;
✓ Проверка булевой функции на принадлежность к классам T₀, T₁, S, L, M;
✓ Определение полноты множеств функций (теорема Поста);
✓ Операции над множествами (диаграммы Эйлера-Венна);
✓ Исследование свойств бинарных отношений;
✓ Построение отрицаний к предикатам, содержащим кванторные операции;
✓ Исследование отображений и свойств бинарных отношений с помощью графов;
✓ Составление алгоритмов, работа машины Тьюринга.
Для промежуточной аттестации (экзамен):
✓ Теоретические вопросы (52 вопроса) по всем темам курса;
✓ Практические задания (23 задания) по построению таблиц истинности, минимизации функций, работе с предикатами и графами;
✓ Итоговый тест (20 вопросов).
4. СИСТЕМА ОЦЕНИВАНИЯ
Практические работы:
✓ Всего 14 работ, распределенных по 3 рейтинг-контролям;
✓ Максимальный балл за работу: 3 или 6 баллов;
✓ Рейтинг-контроль №1 — 21 балл; №2 — 21 балл; №3 — 18 баллов; всего — 60 баллов.
Итоговый тест (20 вопросов):
✓ 18–20 баллов → высокий уровень; 14–17 → продвинутый; 11–13 → пороговый; менее 10 → неудовлетворительно.
Экзамен (оценка):
✓ Текущая работа (60 баллов) + ответы на теоретические вопросы и практические задания (40 баллов);
✓ 91–100 баллов → "отлично"; 74–90 → "хорошо"; 61–73 → "удовлетворительно"; менее 60 → "неудовлетворительно".
5. ПРИМЕРЫ ТЕСТОВЫХ ЗАДАНИЙ
✓ Термин, обозначающий предложение, рассматриваемое лишь в связи с его истинностью — высказывание;
✓ Соединение двух высказываний с помощью союза "и" — конъюнкция;
✓ Конъюнкция переменных или их отрицаний — минтерм;
✓ Функция, аргументы которой принимают значения из {0,1} — булева функция;
✓ Множество, не содержащее элементов — пустое;
✓ Ребро, инцидентное одной вершине — петля;
✓ Маршрут без повторяющихся ребер — цепь.
6. ПРАКТИЧЕСКАЯ НАПРАВЛЕННОСТЬ
Дисциплина ориентирована на формирование фундаментальных знаний дискретной математики, необходимых для специальности в сфере разработки компьютерных игр, дополненной и виртуальной реальности:
✓ Математическая логика — основа проектирования логических схем, работа с условиями в игровых движках;
✓ Булевы функции — основа цифровой электроники, алгоритмов сжатия и шифрования;
✓ Теория множеств — работа с базами данных, группами объектов в игровом пространстве;
✓ Теория графов — построение маршрутов, поиск путей, моделирование связей, работа с деревьями решений;
✓ Алгоритмы — разработка эффективных алгоритмов для игровой логики и ИИ;
✓ Машина Тьюринга — понимание основ вычислимости и алгоритмических процессов;
✓ Предикаты и кванторы — формализация условий и правил в игровых системах.