(@_@)
Список вопросов
I. Множества
1) Понятие множества, принадлежность элемента множеству. Пустоу множество,универсальное множество.Способы задания множеств.2) Понятие подмножества и надмножества, строгого и нестрогого подмножеств. Равенство двух множест.
3) Понятие Булеана, мощьность булеана.
4) Мощьность множества. Конечные и бесконечные множества, счетные и континуальные множества.
5) Операции над множествами: объединение, пересечение, разность, симметрическая разность, дополнение.
6) Понятие вектора. Компонента вектора, размерность вектора, равенство векторов. Проекция вектора на ось, проекция множества векторов на ось.
7) Прямое произведение множеств. Степень множества.
8) Покрытия, дизъюнктные семейсва, развиение множеств.
9) Понятие отношения. Унарные, бинарные, многоместные отношения. Способы задания отношений.
10) Специальные виды отношений: обратное отношение, дополнение отношения, тождественное отношение, универсальное отношение.
11) Свойства отношений: рефлективность, антирефлективность, транзитивность.
12) Свойства отношений: симметричность, антисимметричность, асиметричность, полнота.
13) Композиция отношений. Свойства операции композиции. Степень отношения.
14) Отношение строгого и нестрогого порядка. Полный и частный порядок.
15) Отношение эквивалентности, классы эквивалентности, фактормножества, индекс разбиения.
16) Понятие соответствия. Область определения и область значений соответствия. Образ и прообраз элемента.
17) Свойства соответствия: всюду определённое, сюръективное, инъективное,функциональное, биективное соответствие.
18) Понятие функции. Аргумент и значение функции. Равенство функций. Обратная функция. Композиция функций. Способы заданий функции.
II. Графы.
1) Понятие графа. Инцидентность и смежность вершин и ребер. Изображение Графов.
2) Виды графов: орграф, основание графа;псевдограф; мультиграф; простой граф.
3) Виды графов: полный граф; подграф; двудольный граф; тривиалььный граф; пустой граф.
4) Понятие степени вершины графа. Регулярный граф. Полустепень исхода вершины, полустепень захода вершины. Виды вершин по валентности. Теорема Эйлера "о рукопожатии"
5) Задание графа матрицей смежности. Матрица смежности орграфа.
6) Задание графа матрицей инцидентности. Матрица инцедентности орграфа.
7) Изоморфизм графов.
8) Понфятие маршута в графе, завкнутого маршрута. Длина маршрута. Цепь, простая цепь, растояние между вершинами. Цикл, простой цикл. Путь, контур.
9) связность графа, компоненты связности. Точка сочленения, мост, блок.
10) Связность,однородная связность, сильная связность в орграфах. Конденсация.
11) Эйлеров цикл, условие существования эйлерова цикла в графе. Эйлерова цепь, условие сущуствования эйлеровой цепи в графе.
12) Гамильтов цикл в графе, гамильтова цепь.
13) Плоский граф, планарный граф. Соотношение числа вершин, ребер и граней в планарном графе. Условие планарности графа. Триангулированный граф.
14) Понятие раскраски графа. Хроматическое число.
15) Внутренне устойчивые множества вершин. Внешне устойчивые множества вершин. Вершинные покрытия. Ядро графа. Клика.
16) Понятие свободного дерева. Свойства дерева.
17) Коневое ориентированное дерево. Корень, лист, ветвь, высота, уровень, ярус. Потомок, передок.
18) m-арное дерево, m-арное полное дерево. Количество листьев и вершин в полном m-арном дереве высоты h.
III. Логические функции.
1) Общие сведенья о схемах дискретного действия. Комбинационные схемы и конечные автоматы. Схемы с несколькими выходами. Анализ сложных схем.
2) Понятие логической функции. равенство логической функции. Количество различных логических функций n аргументов.
3) Свойства логических функций: существованая зависемость от аргумента, сохранение нуля, сохранение единицы.
4) Логические функции одного аргумента. Техническая реализация функции одного аргумента.
5) Логическая функция двух аргументов. Техническая реализация функции двух аргументов.
6) Элементарные логические функции. Количество элементарных логических функций. Понятие базиса, минимального базиса. Теорема Поста-Яблонского о функциональной полноте. Ослабленая функцирнальная полнота.
7) Аксиомы и тождества булевой алгебры. Правила де Моргана. Порядок действий в булевой алгебре. Приведение к булевым не булевых операций.
8) Понятие дизъюнктивной совершенно нормальной формы записи логической функции. Получение ДСНФ из таблицы значений функций.
9) Понятие конъюнктивной совершенно нормальной формы записи логической функции. Получение КСНФ из таблицы значений функций.
10)
11)
12)
13)
14)
15)
16)
17)
18)
