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

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

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

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

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

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

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

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

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

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

1 семестр

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Файл

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

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

.

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

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

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

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

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

Аутизм: история, причины, признаки, симптомы, лечение

Реферат по генетике. Ранний аутизм. Аутизм у детей. Аутизм. Прогноз. Причины возникновения аутизма. Признаки и симптомы раннего аутизма.

Методы определения параметров вращения Земли

Для решения многих фундаментальных и прикладных задач в навигации, геодезии, геофизике, астрометрии и других науках необходимо с высокой степенью точности знать параметры вращения Земли

Схема процесу проектування

Лекція. Операції проектування, основні етапи та стадії. Процес проектування можна розділити на етапи, які, в свою чергу, розділяються на процедури та операції.

Гинекология: тесты, вопросы и ответы

Задания. Гинекология. Ответы на вопросы тесты по предмету гинекологии. Неправильные положения и пороки развития половых органов. Острый живот в гинекологии. Новообразования женских половых органов Бесплодный брак Воспалительные заболевания женских половых органов

Ґрунти та підґрунтя. Тест з відповідями

Які мінерали є джерелом калію в грунті? Що є джерелом азоту в грунті? Який хімічний меліорант є відходом хімічного виробництва, збагаченим на фтор?

Сохранить?

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

Введите код

Ok