Контрольные вопросы к экзамену по дисциплине Дискретная математика

Министерство образования и науки Российской Федерации

федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«Северный (Арктический) федеральный университет имени М.В. Ломоносова»

Институт математики, информационных и космических технологий

Кафедра математического анализа, алгебры и геометрии

010400.62 Прикладная математика и информатика

Контрольные вопросы к экзамену

по дисциплине Дискретная математика

1 семестр

Правила суммы и произведения, их применение. Формула включений и исключений.

Перестановки, размещения, сочетания. Вывод формул для их подсчета.

Размещения и сочетания с повторениями. Вывод формулы подсчета размещений с повторениями. Таблица формул. Пример применения каждой из формул.

Свойства сочетаний (с доказательством). Формула бинома Ньютона, пример ее применения. Треугольник Паскаля.

Метод математической индукции. Пример доказательства методом математической индукции.

Булевы функции от 1 и 2 переменных. Теорема о количестве булевых функций от n переменных.

Существенные и фиктивные переменные. Законы равенства булевых функций. Выражение булевых функций через штрих Шеффера и стрелку Пирса.

Полиномы Жегалкина. Общий вид полиномов Жегалкина от 1, 2 и 3 переменных; подсчет их числа. Методы представления булевых функций полиномами.

Совершенная конъюнктивная нормальная форма: основные определения, лемма о разложении, теорема о cовершенной конъюнктивной нормальной форме. Пример построения cовершенной конъюнктивной нормальной формы.

Совершенная дизъюнктивная нормальная форма: основные определения, лемма о разложении, теорема о совершенной дизъюнктивной нормальной форме. Пример построения совершенной дизъюнктивной нормальной формы.

Полные системы булевых функций. Примеры полных систем (с доказательством полноты). Признак полноты системы.

Классы Поста и алгоритмы определения принадлежности функции классу. Примеры функций, принадлежащих и не принадлежащих каждому классу.

Классы Поста, их замкнутость. Теорема Поста (с доказательством необходимости).

Релейно-контактные схемы. Функция проводимости схемы. Схема для голосования.

Схемы из функциональных элементов. Одноразрядный двоичный сумматор.

Основные определения теории графов. Способы задания графов. Свойства матриц смежности и инцидентности. Теорема о сумме степеней вершин.

Маршруты, цепи, циклы в графе. Эйлеров и Гамильтонов циклы. Задача Эйлера о Кенигсбергских мостах. Теорема об Эйлеровом цикле.

Понятие алфавитного кодирования. Однозначно декодируемый код. Свойство префикса. Теорема о свойстве префикса.

Понятие алфавитного кодирования. Однозначно декодируемый код. Свойство суффикса. Теорема о свойстве суффикса.

Алгоритм построения графа, соответствующего алфавитному коду. Пример работы алгоритма. Критерий однозначной декодируемости.

Неравенство Макмиллана (с доказательством) и обратная теорема.

Понятие избыточности кода. Код с минимальной избыточностью. Свойство кодов с минимальной избыточностью.

Кодовое дерево префиксного кода. Пример. Насыщенное дерево. Операции, не увеличивающие избыточность. Вывод о строении кодового дерева кода с минимальной избыточностью.

Формула для числа ребер, исходящих из исключительной вершины. Алгоритм построения кода с минимальной избыточностью. Пример.

Задача исправления одной ошибки. Код Хэмминга. Алгоритм кодирования и декодирования.

Линейное кодирование. Порождающая матрица линейного кода, ее свойства. Пример построения кода по порождающей матрице. Корректирующие возможности линейного кода.

Составитель: С.Ю. Корабельщикова

← Предыдущая
Страница 1
Следующая →

Файл

12_Контрольные вопросы к экзамену 12 группа.docx

12_Контрольные вопросы к экзамену 12 группа.docx
Размер: 18.8 Кб

.

Пожаловаться на материал

Институт математики, информационных и космических технологий Кафедра математического анализа, алгебры и геометрии

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Текст, як результат і одиниця комунікації

Економічна конкуренція

Відповіді на ГОС. з економічної конкуренції, види конкуренції. Конкурентні відносини. Конкурентне середовище підприємства. Конкурент та його поняття, переваги. Конкурентоспроможність підприємства

Технологии вибровоздействия на нефть с целью восстановления ее транспортабельных свойств

Устройство для виброобработки нефти при откачке из нефтехранилищ. Устройство для откачки нефти из резервуара. Виброобработка нефти в земляном амбаре. Устройства для виброобработки нефти в трубопроводе. Устройство для вибрации участка трубопровода

Тест по дисциплине «История управленческой мысли»

Список литературы для чтения летом. 8 класс

Древнерусская литература. Литература VIII века, XIX века, XX века. Зарубежная литература

Сохранить?

Пропустить...

Введите код

Ok