Материалы для подготовки коллоквиуму
Задания билетов коллоквиума, относящиеся к базовому уровню, составляются в соответствии с программой аттестации модуля I «Элементы теории множеств и комбинаторики. Алгебра логики». Для подготовки к сдаче коллоквиума на базовом уровне студенту рекомендуется изучить материал раздел «Базовые понятия и утверждения» лекций 1-8 (лекции написаны в точном соответствии с этой программой). При сдаче коллоквиума на базовом уровне проверяется знание теоретических фактов, способность иллюстрировать теоретические понятия и утверждения на примерах, а также умение решать типовые упражнения, аналогичные тем, которые приведены в п.5 данного файла.
Задания билетов коллоквиума, относящиеся к повышенному уровню, составляются в соответствии с программой аттестации курса повышенного уровня модуля I «Множества, бинарные отношения, комбинаторика. Алгебра логики». Для подготовки к сдаче коллоквиума на повышенном уровне студенту рекомендуется изучить в полном объеме материал лекций 1-8.
Вопросы к коллоквиуму № 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. Критерий полноты системы булевых функций (теорема Поста).
P.S. Объем подготовки по каждому вопросу определяется уровнем сдачи коллоквиума. Вопросы, выделенные курсивом, изучаются только на повышенном уровне.
Описание структуры билета коллоквиума и схемы оценивания
Каждый билет коллоквиума состоит из двух частей: части I и части II. Часть I ориентирована на проверку качества усвоения курса на базовом уровне, часть II – повышенного уровня.
Если студент изучал курс на базовом уровне, то он готовит ответ только по вопросам части I. Часть I может сдаваться как в письменной, так и в устной форме.
Если студент изучал курс на повышенном уровне, то он вначале готовит ответ на вопросы части I, а затем, при условии положительный оценки (получения не менее восьми баллов), готовит ответ и отвечает на вопрос части II. Часть II сдается только в форме традиционного устного экзамена.
Часть I содержит 6 теоретико-практических заданий.
Максимальное количество баллов, которое студент может получить за часть 1 составляет 12 баллов.
Часть 2 содержит один вопрос из списка вопросов к коллоквиуму. За ответ по второй части студент может получить до 8 баллов. Таким образом, максимальное число баллов при сдаче коллоквиума на повышенном уровне равно 20 баллам.
Образец билета коллоквиума
Дата добавления: 2018-02-18; просмотров: 568; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!