Программа повышенного уровня

2018-06-29

254

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

0.00 из 5.00 0 оценок

⇐ Предыдущая 12

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