 |
|
|
|
ТИС (теория информационных систем)
|
1
|
Множества, основные понятия.
|
|
2
|
Операции над множествами. Основные тождества алгебры множеств. Диаграммы Эйлера-Венна.
|
|
3
|
Прямое произведение множеств. Отношения на множествах. Бинарные отношения, область определения и область значений, обратное отношение.
|
|
4
|
Свойства отношений. Отношение эквивалентности и отношение частичного порядка.
|
|
5
|
Функции, отображения. Определения сюръективной, инъективной и биективной функций.
|
|
6
|
Операции. Определения коммутативности, ассоциативности, дистрибутивности, единицы и обратного элемента.
|
|
7
|
Единственность единицы и обратного элемента.
|
|
8
|
Алгебраические структуры. Гомоморфизм алгебраических структур. Изоморфизм.
|
|
9
|
Простейшие алгебраические структуры: полугруппа, моноид, группа.
|
|
10
|
Кольца и поля. Свойства, единственность единицы и обратного элемента в поле. Решение уравнения a x + b=0 в поле.
|
|
11
|
Элементы комбинаторики. Правило сумм и произведения. Размещения, сочетания, перестановки.
|
|
12
|
Высказывания. Операции над высказываниями.
|
|
13
|
Формулы алгебры логики. Основные равносильности.
|
|
14
|
Булева алгебра, определение, примеры интерпретаций.
|
|
15
|
Булевы функции. Таблицы истинности Булевых функций двух переменных, сравнение с логическими операциями.
|
|
16
|
Совершенная дизъюнктивная нормальная форма (СДНФ). Преставление булевой функции в ДНФ по её таблице истинности. Приведение формулы алгебры логики к СДНФ.
|
|
17
|
Совершенная конъюнктивная нормальная форма (СКНФ).
|
|
18
|
Логика предикатов. n-местный предикат. Логические операции над предикатами. Кванторные операции. Формулы логики предикатов. Тождественная истинность и тождественная ложность формулы. Выполнимость формулы.
|
|
19
|
Графы, основные понятия. Способы задания графов. Подграфы.
|
|
20
|
Маршруты (пути), циклы (контуры) в графах.
|
|
21
|
Связность в графах. Компонента связности, матрица достижимости, матрица связности (сильной связности). Булевы матрицы. Операции над булевыми матрицами. Выделение компонент связности.
|
|
22
|
Поиск маршрута в графе: алгоритм Тери. Поиск минимального маршрута: алгоритм «фронт волны».
|
|
23
|
Центр, радиус, диаметр связного графа.
|
|
24
|
Нагруженный граф (орграф). Поиск минимального пути в нагруженном графе. Алгоритм Форда-Беллмана.
|
|
25
|
Эйлеровы цикл и цепь. Условие существования эйлерова цикла.
|
|
26
|
Гамильтоновы цикл и цепь. Условия существования гамильтонова цикла.
|
|
27
|
Деревья и их свойства.
|
|
28
|
Цикломатическое число. Вектор-циклы. Цикловой базис. Цикломатическая матрица. Уравнения Кирхгоффа.
|
|
29
|
Транспортная сеть. Поток транспортной сети, максимальный поток полный поток, величина потока.
|
|
30
|
Построение полного потока.
|
|
31
|
Орграф приращений. Теорема Форда-Фалкерсона. Построение максимального потока.
|
|
23.12.2013; 18:17
хиты: 1818
рейтинг:0
|
|
|
|
|
|
Copyright © 2013-2025. All Rights Reserved. |
помощь
|
|
