Приднестровский государственный университет  им.Т.Г. Шевченко

«Утверждаю»      Зав. кафедрой ВКСС  профессор __________Ю.А.Долгов

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__15__

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Алгебра Жегалкина и линейные функции.
2. Примеры логических функций одной и двух переменных. Представление логических функций булевой формулой.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__17__

2. Понятие   множества.  Примеры  множеств.  Операции  над множествами  (пересечение,  объединение, разность, симметрическая разность, дополнение до универсального). Диаграммы Эйлера-Венна.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__18__

1. Эйлеровы и Гамельтоновы циклы. Условия существования Эйлеровых циклов в графе.
2. Двойственность, Принцип двойственности. Свойство самодвойственных функций
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__19__

1. Планарные графы.  Карта  графа.  Теорема  Куратовского. Раскраска графа и карты. Хроматическое число графа. Толщина графа.
2. Минимизация в классе дизъюнктивных нормальных форм ( понятия и основные методы.)
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__20__

1. Маршруты, цепи,  циклы
2. Произведение   множеств.  Примеры.  N-арное  отношение, бинарное   отношение.   Способы   задания   отношений.   Примеры. Тождественное,    универсальное,    пустое   отношение.   Область определения  и  область  значений  бинарного  отношения. Обратное бинарное отношение.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__1___

1. Понятие алгебраической системы. Определение нижней и верхней грани, решетки, полной решетки. Иллюстрация решеток с помощью диаграмм Хассе. Примеры.
2. Образ и прообраз вершины и множества вершин. Поиск путей (маршрутов) с минимальным числом дуг (ребер). Алгоритм фронта волны.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__2___

1. Группоид. Мультипликативный  и  аддитивный  группоид.  Мономорфизм, эпиморфизм, изоморфизм. Пример изоморфного отображения.
2. Приведение формул к нормальным формам. (Определение элементарной конъюнкции, элементарной дизъюнкции, КНФ, ДНФ, алгоритмы приведения, примеры.) Запись СДНФ, СКНФ логической функции, заданной таблицей. Переход от ДНФ к КНФ. Примеры.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__3__

1. Понятия   суперпозиции,   формулы,   глубины   формулы, подформулы,  внешней  (главной) операции. Определение формулы над S, равносильных (эквивалентных) формул.
2. Полугруппа,  моноид,  абелева  полугруппа.  Разрешимость уравнений.  Квазигруппа.  Примеры. Подстановка. Пример полугруппы подстановок.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__4___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Определение функциональной полноты системы логических функций S, замкнутость системы логических функций. Понятие базиса. Примеры замкнутых классов.
2. Покрытие и разбиение множества. Отношение эквивалентности. Класс эквивалентности.  Теорема  о  разбиении  и отношении эквивалентности. Примеры. Вид матрицы отношения эквивалентности.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__5___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Отношение порядка. Строгое, нестрогое отношение порядка. Сравнимость   элементов.   Полностью   и  частично  упорядоченные множества. Примеры. Определение покрытия элемента x элементом y.  Диаграммы Хассе. Примеры.
2. Операции над графами и их частями (операции с частями графа – объединение, пересечение, дополнение; операции с графами – объединение, сумма, симметрическая разность, произведение, операции удаления ребра, вершины, операция подразбиения и стягивания).
3. Практическое задание.

Протокол №3 заседания кафедры  ВКСС                                    Экзаменатор____________

от 1 декабря 2005 г.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__6___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1 Расстояния. Диаметр, радиус и центр графа.

2. Разложение   Шеннона.  Предельное  разложение  Шеннона. (Дизъюнктивное  и  конъюнктивное)
3. Практическое задание.

Протокол №3 заседания кафедры  ВКСС                                    Экзаменатор____________

от 1 декабря 2005 г.

Приднестровский государственный университет  им.Т.Г. Шевченко

«Утверждаю»

Зав. кафедрой ВКСС

профессор __________Ю.А.Долгов

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__7___

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Взвешенные графы. Алгоритм нахождения экономичного дерева в графе.
2. Приведение формул к  нормальным  формам.  (Определение элементарной   конъюнкции,  элементарной  дизъюнкции,  КНФ,  ДНФ, алгоритмы приведения, примеры). Запись СДНФ, СКНФ логической функции, заданной таблицей. Переход  от ДНФ к КНФ. Примеры.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__8___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Синтез логических схем в заданном базисе. Примеры базисов.
2. Способы   представления  графов  (матрицы  смежности и инцидентности, список ребер.)
3. Практическое задание.

Протокол №3 заседания кафедры  ВКСС                                    Экзаменатор____________

от 1 декабря 2005 г.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__9___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Понятие   алгебры   логики,   функции   алгебры  логики (логической   функции).   Задание   логических  функций  таблицей. Определение несущественной (фиктивной) переменной.
2. Группа.  Конечная,  бесконечная,  абелева,  циклическая. Свойства групп. Второе определение группы. Примеры.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__10___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Производная первого порядка от булевой функции, Смешанная производная, производная  к-го  порядка. Вес производной.  Условия,  определяемые производными.
2. Расстояния. Диаметр, радиус и центр графа.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__11___

1. Поле. Свойства и примеры полей.
2. Взвешенные графы. Алгоритм нахождения экономичного дерева в графе.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__30___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Кольцо. Свойства и примеры колец. Коммутативное кольцо, кольцо  с единицей, кольцо с делителями нуля. Построение кольца с делителями нуля.
2. Функции, сохраняющие ноль и единицу. Теорема о необходимом и достаточном условии функциональной полноты системы функций (в слабом и сильном смысле). Леммы о немонотонных и нелинейных функциях.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__29___

1.   Понятие N-арной операции. Алгебра. Замкнутость множества относительно       N-арной  операции.  Подалгебра. Операнды, операции. Примеры. Тождественная операция.
2. Взаимно-однозначное соответствие.  Мощность множества. Теоремы. Равномощные множества. Счетность множеств. Мощность континуум. Континуальные множества.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__28___

1. Определение функциональной полноты системы логических функций S, замкнутость системы логических функций. Понятие базиса. Примеры замкнутых классов.
2. Деревья и лес.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__27___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

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

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__26___

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

Факультет Инженерно-технический                                                                    Курс 2

Специальность ЭС, ЭМ

1. Понятие слабо определенной логической функции. Минимизация логических функций. Понятие единичного и нулевого интервалов, максимального интервалов, способы их записи. Сокращенная и минимальная ДНФ. Метод таблицы различий.
2. Степени и полустепени вершин графа. Части, суграфы и подграфы.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__25___

1. Изоморфизм булевой алгебры логических функций и булевой алгебры множеств.
2. Расстояния. Диаметр, радиус и центр графа.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__24___

1. Релейно-контактные схемы как применение булевой алгебры.
2. Эйлеровы и гамильтоновы циклы.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__23___

1. Устойчивость, покрытия и паросочетания (число внутренней устойчивости графа, реберное число независимости, вершинное покрытие, реберное покрытие, окрестность, неокрестность).
2. Булева алгебра и эквивалентные преобразование в ней. Определение булевой алгебры, булевых формул. Свойства булевых операций. Замена и подстановка, их особенности и различия.
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__22___

1. Минимальный путь (маршрут) во взвешенном орграфе (графе). Алгоритм Форда-Беллмана
2. Иллюстрация решеток с помощью диаграмм Хассе. Дистрибутивная решетка, решетка с дополнением. Второе определение решетки
3. Практическое задание.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__21___

1. Понятие множества. Примеры множеств. Операции над множествами (пересечение, объединение, разность, симметрическая разность, дополнение до универсального). Диаграммы Эйлера-Венна.
2. Запись СДНФ, СКНФ логической функции, заданной таблицей. Переход  от ДНФ к КНФ. Примеры.
3. Практическое задание.