Программа базового уровня

2018-06-29

240

Обсуждений (0)

0.00 из 5.00 0 оценок

12 Следующая ⇒

Программа аттестации по модулю 1

Содержание	Планируемые результаты обучения
Знания и представления	Умения и навыки
Модуль 1. Элементы теории множеств и бинарных отношений. Функции алгебры логики.
Тема 1.1 Множества и бинарные отношения
Множества и операции над ними	Знать понятия множества, подмножества, определение равных множеств, способы задания множеств; определения операций дополнения, объединения, пересечения, разности и декартова произведения множеств, определение разбиения множества.	Уметь иллюстрировать на примерах основные понятия теории множеств и операции над множествами (в том числе с помощью диаграмм Эйлера-Вена), находить дополнение, объединение, пересечение, разность и декартово произведение конечных множеств.
Свойства операций над множествами	Знать для операций объединения, пересечения и дополнения множеств коммутативные, ассоциативные, дистрибутивные законы, законы идемпотентности, де Моргана, нуля и единицы, поглощения, дополнения.
Правила подсчета элементов конечных множеств	Знать правило суммы, правило включений и исключений для подсчета числа элементов конечных множеств, формулу для мощности декартового произведения конечных множеств.	Уметь иллюстрировать на примерах правила подсчета числа элементов конечных множеств.
Бинарные отношения на множестве и их свойства	Знать определение бинарного отношения на множестве; типы бинарных отношений (рефлексивные, симметричные, антисимметричные, транзитивные), определения отношений порядка и эквивалентности, классов эквивалентности, свойства классов эквивалентности.	Уметь иллюстрировать типы бинарных отношений на примерах, находить в случае конечного множества классы эквивалентности по бинарному отношению и разбиение множества на классы эквивалентности.
Тема 1.2. Элементы комбинаторики
Выборки Сочетания и размещения без повторений и с повторениями, перестановки.	Знать понятие выборки с повторением и без повторения, упорядоченной и неупорядоченной; определения сочетаний и размещений без повторений, перестановок, сочетаний и размещений с повторениями.	Уметь иллюстрировать типы выборок на примерах.
Правило произведения и правило суммы, формулы подсчета числа сочетаний и размещений	Знать правила произведения и суммы подсчета числа выборок, формулы подсчета числа сочетаний, размещений, перестановок.	Уметь иллюстрировать на примерах правила произведения и суммы, формулы числа сочетаний и размещений с повторениями и без повторений и применять их для решенияодношаговых задач (т.е. задач, сводящихся к использованию одной комбинаторной формулы).
Бином Ньютона. Комбинаторные соотношения.	Знать формулу бинома Ньютона, тождество Паскаля и его вывод, процедуру построения треугольника Паскаля.	Уметь находить биномиальные коэффициенты с помощью треугольника Паскаля, доказывать несложные комбинаторные тождества путем алгебраических преобразований.
Тема 1.3. Булевы функции и способы их задания
Булева функция. Задание булевой функции таблицей истинности и вектором значений. Элементарные функции.	Знать понятия булева вектора и булевой функции, способы задания булевой функции таблицей истинности и вектором значений, определения, обозначения и названия элементарных булевых функции одной и двух переменных.	Уметь находить номер булева вектора, приводить примеры булевых функций 1, 2, 3, 4-х переменных, заданных таблицей истинности и вектором значений
Задание функций формулами. Основные равносильности над множеством .	Иметь представление о понятии формулы над множеством функций, о функции, реализуемой формулой, о равносильных формулах. Знать формулировку и доказательства основных равносильностей над множеством .	Уметь приводить примеры формул над заданным множеством функций, находить таблицу истинности и вектор значений функции, заданной формулой; упрощать формулы и доказывать равносильность формул, используя для этого таблицы истинности и равносильные преобразования.
Тема 1.4. Совершенные дизъюнктивные и конъюнктивные нормальные формы
Двойственные функции	Знать определение функции, двойственной к данной, и процедуру построения двойственной функции по таблице истинности и вектору значений исходной функции.	Уметь иллюстрировать на примерах нахождение двойственной функции с использованием определения. Уметь находить двойственную функцию, применяя процедуру построения двойственной функции по таблице истинности и вектору значений исходной функции.
Принцип двойственности.	Знать формулировку принципа двойственности для формул над произвольной системой функций и для формул над множеством .	Уметь, используя принцип двойственности; задавать формулой функцию, двойственную функции, заданной формулой над множеством .
Разложение функции по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ).	Знать формулировку теоремы о представлении функции в виде СДНФ.	Уметь описать процедуру построения СДНФ заданной таблицей истинности, и представлять в виде СДНФ функцию, заданную таблицей истинности или вектором значений.
Совершенная конъюнктивная нормальная форма (СКНФ)	Знать формулировку теоремы о представлении функции в виде СКНФ.	Уметь описать процедуру построения СКНФ функции, заданной таблицей истинности, и представлять в виде СКНФ функцию, заданную таблицей истинности или вектором значений.
Тема 1.5. Минимизация дизъюнктивных нормальных форм
Дизъюнктивная нормальная форма (ДНФ), минимальные ДНФ, постановка задачи о минимизации ДНФ.	Знать определение элементарной конъюнкции, дизъюнктивной нормальной формы (ДНФ), сложности ДНФ, минимальной ДНФ, постановку задачи о минимизации ДНФ, процедуру нахождения минимальной ДНФ методом полного перебора.	Уметь определять ранг элементарной конъюнкции, сложность ДНФ.
Сокращенная ДНФ, тупиковые ДНФ	Знать определения импликанты, простой импликанты, сокращенной ДНФ, тупиковой ДНФ, иметь представления о взаимосвязях между самой функцией и ее сокращенной, тупиковыми и минимальными ДНФ.	Уметь определять, является ли элементарная конъюнкция импликантой, простой импликантой функции.
Алгоритмы построения сокращенной, тупиковых и минимальных ДНФ	Иметь представление об алгоритме Квайна построения сокращенной ДНФ из СДНФ функции, о процедуре построения тупиковых ДНФ из сокращенной с помощью импликантной таблицы, об отборе минимальных ДНФ из тупиковых.	Уметь находить сокращенную, тупиковые и минимальные ДНФ функции.
Тема 1.6. Классы Поста и замыкание
Полином Жегалкина.	Знать определение полинома Жегалкина, формулировку и доказательство теоремы о представлении функции полиномом Жегалкина.	Уметь находить полином Жегалкина методом равносильных преобразований и методом неопределенных коэффициентов.
Функции, сохраняющие 0, 1. Самодвойственные, монотонные, линейные функции.	Знать определения функций, сохраняющих 0, 1, самодвойственных, монотонных, линейных функций, определения и обозначения классов Поста: , , .	Уметь определять принадлежность функции каждому из классов Поста.
Замыкание системы булевых функций. Замкнутость классов Поста.	Знать определение операции замыкания системы булевых функций, понятие замкнутых систем, формулировку утверждения о замкнутости классов Поста.	Уметь иллюстрировать на примерах операцию замыкания системы булевых функций.
Тема 1.7. Полнота системы булевых функций
Полнота системы булевых функций. Теорема о полноте двух систем.	Знать определение полной системы булевой функции, доказательство полноты системы , формулировку и доказательство теоремы о полноте двух систем.	Уметь доказать полноту систем , .
Критерий полноты систем булевых функций (теорема Поста)	Знать формулировку критерия полноты системы булевых функций (теоремы Поста).	Уметь определять, полна или нет система булевых функций, используя критерий полноты Поста.
Базисы	Знать определение базиса, важные примеры базисов (дизъюнктивный, конъюнктивный базис Буля, базис Жегалкина, базис Шеффера, базис Пирса).	Уметь определять, является ли базисом система булевых функций.

2018-06-29

240

Обсуждений (0)

0.00 из 5.00 0 оценок

12 Следующая ⇒

Обсуждение в статье: Программа базового уровня

Обсуждений еще не было, будьте первым... ↓↓↓