close

Вход

Забыли?

вход по аккаунту

?

Программа аттестации по дискретной математике М1

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