Требования к выполнению реферативной работы и схема оценивания

Тема реферативной работы выбирается студентами из списка (см. 4.2.4.1) и уточняется (и, в большинстве случаев, конкретизируется) по согласованию с преподавателем.

Реферативная работа включает:

1. Изложение теории по теме.

2. Изложение содержательных примеров по теме.

Содержание реферативной работы и ее объем согласовывается с преподавателем на консультациях.

Реферативная работа должна обязательно защищаться (защита реферативной работы является необходимым условием получения баллов за реферативную работу).

Реферативная работа оценивается по следующим критериям:

1) Полнота и качество изложения теоретического материала по теме.

2) Полнота и качество изложения содержательных примеров по теме.

3) Понимание изложенного материала (выявляется в процессе защиты реферативной работы).

Комплект КИМ к коллоквиуму модуля 1

Вопросы к коллоквиуму

Для подготовки к сдаче коллоквиума по модулю 1 на базовом уровне вместо списка вопросов студенту выдается программа промежуточной аттестации курса «Дискретная математика», Модуль I «Множества, бинарные отношения, комбинаторика. Алгебра логики». Задания билета составляются в точном соответствии с этой программой и базовыми частями лекций (также написанными в точном соответствии с этой программой). Электронные варианты лекций выдаются студентам в начале изучения модуля. При сдаче коллоквиума на базовом уровне проверяется знание теоретических фактов, способность иллюстрировать теоретические понятия и утверждения на примерах, а также умение решать типовые упражнения, аналогичные тем, которые приведены в электронном варианте лекций.

Для подготовки к сдаче коллоквиума по модулю 1 на повышенном уровне студенту выдается: (а) программа промежуточной аттестации курса повышенного уровня «Дискретная математика», Модуль I «Множества, бинарные отношения, комбинаторика. Алгебра логики», (б) список вопросов, составленный в соответствии рабочей программой курса повышенного уровня «Дискретная математика», Модуль I «Множества, бинарные отношения, комбинаторика. Алгебра логики».

Вопросы к коллоквиуму по курсу «Дискретной математики», Модуль 1

1. Множества и операции над ними. Свойства операций над множествами. Правило суммы, правило включений-исключений. Разбиение множества.
2. Бинарные отношения на множестве. Свойства бинарных отношений. Отношение эквивалентности, отношение порядка. Теорема о свойствах классов эквивалентности.
3. Элементы комбинаторики. Правило произведения и правило суммы. Сочетания и размещения. Сочетания и размещения с повторениями. Биномиальные коэффициенты, треугольник Паскаля.
4. Булевы векторы и булевы функции от переменных. Элементарные булевы функции. Задание булевых функций формулами. Основные равносильности.
5. Существенные и фиктивные переменные булевых функций. Операция удаления (введения) фиктивной переменной.
6. Двойственные функции. Принцип двойственности.
7. Разложение булевых функций по переменным.
8. Совершенная дизъюнктивная нормальная форма функции.
9. Совершенная конъюнктивная нормальная форма функции.
10. Постановка задачи о минимизации ДНФ. Минимальная ДНФ. Сокращенная ДНФ. Тупиковые ДНФ.
11. Алгоритм поиска сокращенных, тупиковых и минимальных ДНФ.
12. Представление функций в виде полинома Жегалкина (существование и единственность). Поиск полинома Жегалкина методом равносильных преобразований и методом неопределенных коэффициентов.
13. Класс функций, сохраняющих 0. Класс функций, сохраняющих 1. Класс самодвойственных функций. Класс монотонных функций. Класс линейных функций
14. Замыкание системы булевых функций. Свойства замыкания. Теорема о замкнутости классов Поста.
15. Полные системы булевых функций. Теорема о полноте двух систем. Примеры полных систем. Базисы.
16. Лемма о функции, не сохраняющей 0. Лемма о функции, не сохраняющей 1.
17. Лемма о несамодвойственной функции.
18. Лемма о немонотонной функции.
19. Лемма о нелинейной функции.
20. Критерий полноты системы булевых функций (теорема Поста).