Дискретная математика

Дискретная математика Часть 1. Теория множеств.

1.  Дайте определение множества, его элементов, конечных, бесконечных, счётных и
дискретных множеств.

2.  Дайте определение подмножества, пустого и универсального множества,
собственных и несобственных подмножеств. Что такое равносильные множества?
Приведите примеры множеств и подмножеств.

3.  Назовите три основных операции, определённые на множествах. Назовите порядок
выполнения операций.

4.  Сформулируйте свойства идемпотентности, коммутативности, ассоциативности и
дистрибутивности для операций на множествах.

5.  Сформулируйте формулы для объединения и пересечения пустого и
универсального множеств с произвольным множеством, произвольного множества
и его дополнения, для дополнения дополнения произвольного множества, законы
де Моргана. Запишите формулы для дополнений пустого и универсального
множеств. Чему равносильно утверждение, что одно множество является
подмножеством другого?

6.  Что такое Булева алгебра? Что такое диаграммы Эйлера-Венна?

7.  Назовите три дополнительные операции над множествами.

8.  Дайте определение отображения / множества X во множество Y. Дайте
определение образа и прообраза элементов. Дайте определение отображения
множества X на множество Г.

9.  Когда отображение называется инъективным, сюръективным и биективным?

10.  Дать определение эквивалентных множеств и определение счётного множества.
Перечислите основные свойства эквивалентных множеств.

11.  Что такое мощность множества? Какова мощность конечных множеств? Мощность
каких множеств называется алеф-нуль? Мощность каких множеств называется
континуумом?

12.  Какой мощностью может обладать подмножество счётного множества? Какова
мощность суммы конечного или счётного числа счётных множеств? Подмножества
какой мощности содержит бесконечное множество? Что можно сказать о
мощностях множеств М и А, если М - несчётное множество, aАCM -
конечное или счётное множество?

13. Что можно сказать о мощностях множеств М и M U A , если М -
бесконечноемножество, а А - конечное или счётное множество? Какой мощностью
обладает множество всех пар натуральных чисел? Какой мощностью обладает
множество рациональных чисел?

14.  Какой мощностью обладает множество всех конечных последовательностей,
составленных из элементов данного счётного множества?

15.  Дайте определение отношения на множествах и приведите примеры. Как можно
задать отношение на множестве.

16.  Дайте определение свойствам рефлексивности, антирефлексивности,
симметричности и антисимметричности для отношений.

17.  Какое свойство отношений следует из антисимметричности отношения? Дайте
определение транзитивности отношения.

18.  Дайте определение отношения эквивалентности

19.  Дайте определение отношения толерантности

20.  Дайте определение отношения порядка.

21.  Какое множество называют упорядочным? Что такое соответствие порядка или
подобное соответствие?

22.  Что такое подобные множества и что вы можете сказать о их мощности?

Часть 2. Математическая логика.

1.  Что такое высказывание? Что называется алгеброй высказываний? Что такое
тождественная истина и тождественная ложь? Дайте определение отрицания и
приведите её таблицу истинности.

2.  Дайте определение конъюнкции, дизъюнкции и приведите их таблицы
истинности.

3.  Дайте определение импликации, двойной импликации и приведите их таблицы
истинности.

4.  Дайте определение формулы алгебры высказываний и равносильности двух
формул.

5.  Сформулируйте равносильности для формул алгебры высказываний, называемые
законами: идемпотентности, коммутативности, ассоциативности и
дистрибутивности.

6.  Сформулируйте равносильности для формул алгебры высказываний: для
дизъюнкции произвольного высказывания и тождественной истины и
тождественной лжи, для конъюнкции произвольного высказывания и
тождественной истины и тождественной лжи, законы исключённого третьего,
законов отрицания отрицания, законов де Моргана, законов отрицаний
тождественной истины и тождественной лжи.

7.  Приведите формулы, эквивалентные импликации и двойной импликации,
записанные через конъюнкцию, дизъюнкцию и отрицание. Приведите варианты
импликации.

8.  Что такое логическая функция? Каково число различных логических функций,
зависящих от п аргументов? Какая переменная логической функции называется
фиктивной, а какая существенной?

9.  Что такое штрих Шеффера, знак Лукашевича, разделительная дизъюнкция?
Дайте определение полной системы связок.

10.  Отношение следствия и эквивалентности для двух высказываний.

11.  Что такое несовместимые высказывания. Как проверить правильность
высказываний? Что такое элементарное произведение, элементарная сумма?
Когда элементарное произведение является тождественно ложным и когда
элементарная сумма является тождественной истиной?

12.  Что такое ДНФ и КНФ. Приведите алгоритмы их получения.

13.  Сформулируйте необходимые и достаточные условия того, что формула алгебры
высказываний является тождественной истиной или тождественной ложью.

14.  Что такое СДНФ и СКНФ. Приведите алгоритмы их получения.

15.  Приведите алгоритм построения формул алгебры высказываний(СДНФ и СКНФ)
по заданной логической функции.

16.  Расскажите о принципах моделирования алгебры высказываний с помощью
релейно-контактных схем.

17.  Что такое исчисление высказываний? Что входит в алфавит исчисления
высказываний? Что является формулой высказываний?

18.  Приведите аксиомы исчисления высказываний.

19.  Что такое правила вывода, приведите основные правила вывода. Какая формула
называется выводимой в исчислении высказываний?

20.  Сформулируйте теорему дедукции и её основные следствия.

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

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

Часть 3. Теория графов.

1.  Дайте определения графов, орграфов, вершин, дуг и рёбер. Какие вершины, дуги и
рёбра называются смежными?

2.  Что такое цепь, путь, цикл и контур? Какие пути(цепи) называются простыми?
Какие цепи(циклы), пути(контуры) называются гамильтоновыми? Какие
цепи(циклы), пути(контуры) называются эйлеровыми?

3.  Дайте определение вершины, инцидентной дуге(ребру) графа. Что такое степень
вершины? Что такое полустепень захода вершины и полустепень исхода вершины?
Что такое вход и выход графа? Что такое однородный граф? Что такое полный
граф? Как связано число рёбер графа со степенями его вершин?

4.  Когда граф называется связным, а когда не связным? Что такое число компонент
связности для несвязного графа? Что такое перешеек(мост, связующая линия)?
Какой граф называется деревом?

5.  Сформулируйте теорему о необходимости и достаточности того, чтобы
неориентированный граф обладал эйлеровым циклом. Сформулируйте теорему о
существовании эйлерового контура на ориентированном графе.

6.  Сформулируйте теорему о необходимости и достаточности того, чтобы
неориентированный граф обладал эйлеровой цепью. Приведите алгоритм
построения эйлерового цикла.

7.  Когда два графа называют изоморфными? Что означает утверждение, что граф
укладывается на поверхности? Дайте определение планарного и плоского графов.

8.  Дайте определение операции подразделения ребра графа. Когда два графа
называют гомеоморфными? Сформулируйте теорему Понтрягина-Куратовского.

9.  Дайте определение цикломатического числа графа. Дайте определение вектора-
цикла и независимых циклов. Сформулируйте теорему о величине
цикломатического числа графа, и её следствия. Каким ещё способом можно
определить цикломатическое число графа?

10.  Дайте определение числа внутренней устойчивости графа. Дайте определение
числа внешней устойчивости графа.

11.  Дайте определение ядра графа. Дайте определение хроматического числа графа.
Сформулируйте теорему о связи мощности множества вершин графа и числами
внутренней устойчивости и хроматическим.

12.  Дайте определение объединения, пересечения и прямого произведения графов.

13.  Дайте определение матрицы смежности для графа. Как определяются матрицы
смежности для объединения и пересечения графов.

14.  Дайте определение матрицы инциденций для графа.

15.  Дайте определения матрицы достижимостей и контрадостижимостей для графа.

16.  Сформулируйте эквивалентные определения понятия дерева.

17.  Что такое прадерево? Что такое частичный граф? Сформулируйте теорему о
необходимом и достаточном признаке того, что граф содержит частичный граф?

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

19.  Приведите постановку задачи о кратчайшем пути между двумя вершинами
ориентированного графа и её экономическую интерпретацию.

20.  Приведите алгоритм решения задачи о кратчайшем пути между двумя вершинами
ориентированного графа.

21.  Дайте определение сети. Что такое отношение порядка между вершинами графа?
Приведите аксиомы порядка.

22. Приведите постановку задачи о пути, максимальной длины между двумя

вершинами ориентированного графа в сетевом планировании. Дайте представление о сетевом планировании.

Часть 4. Элементы теории кодирования.

1.  В чем состоит процесс кодирования?

2.  Что такое кодирование и декодирование?

3.  Чем занимается криптология? Что такое криптография?

4.  Что такое алфавитное кодирование?

5.  Дайте объяснение математического понятия алфавитного кодирования.

6.  Как определяется схема алфавитного кодирования и как определяются кодовые
слова?

7.  В чем состоит проблема взаимной однозначности алфавитного кодирования?

8.  Что называется префиксом слова и когда схема алфавитного кодирования обладает
свойствами префикса?

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

10.  Какая схема кодирования называется обратной к схеме алфавитного кодирования и
как она обозначается?

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

12.  Что называется нетривиальным разложением элементарного кода?

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

14.  Сформулируйте теорему о необходимом и достаточном условии взаино
однозначного кодирования.

15.  Как по ориентированному циклу написать слово схемы алфавитного кодирования?

16.  Как строится двоичное алфавитное кодирование?

17.  Каковы свойства самокорректирующихся кодов?

18.  Какие коды называются кодами Хемминга? Что называется длиной кода
Хемминга? Что называется числом информационных и контрольных символов?

Каким соотношением эти символы связаны?

19.  Опишите процесс кодирования Хемминга.

20.  Опишите процесс декодирования Хемминга, исправляющего не более
чем одну ошибку.