21. Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.
Кольцом называется непустое множество R, для элементов которого определены две бинарные операции — сложение и умножение (обозначаемые + и × соответственно; знак × обычно опускается), причем предполагаются выполненными следующие аксиомы колец (a, b, c Î R):
Коммутативность сложения: a + b = b + a.
Ассоциативость сложения:
a + (b + c) = (a + b) + c.
Обратимость сложения (возможность вычитания): уравнение a + x = b имеет решение x = b - a Î R.
Дистрибутивность умножения относительно сложения:
a (b + c) = a b + a c и (b + c) a = b a + c a.
Если , то кольцо называют ассоциативным;
если , альтернативным;
если ab = ba и , йордановым;
если a2 = a, a(bc) + b(ca) +c(ab) = 0, то оно называется кольцом Ли;
если ab = ba , то кольцо называется коммутативным.
Примеры колец:
множество всех целых чисел;
множество всех четных чисел и вообще целых чисел, кратных данному числу m;
множество всех рациональных чисел;
множество всех многочленов от одного или нескольких переменных с рациональными, действительными или комплексными коэффициентами;
множество всех функций, непрерывных на данном отрезке числовой прямой
Тело есть такая система (A, + , ×), что система (A, +) является абелевой группой, а система (A¢, ×), где A¢ получается из A удалением нулевого элемента (т.е. нейтрального элемента абелевой группы), является группой и операция × дистрибутивна относительно операции + .
Теорема. Кольцо является телом тогда и только тогда, когда оно содержит не менее двух элементов и оба уравнения ax = b и xa = b, разрешимы для любых элементов a, bÎ A, где a ¹ 0.
Тело служит обобщением системы (Q, + , ×) рациональных чисел, однако требование коммутативности умножения опускается.
Теорема Веддербёрна Всякое конечное тело коммутативно.
Поле может быть определено как множество, содержащее не менее двух элементов, на котором заданы две бинарные алгебраические операции — сложение и умножение, обе ассоциативные и коммутативные, связанные между собой законом дистрибутивности, т.е. для любых a, b, c из поля справедливо:
a + b = b + a , ab = ba ,
(a + b) + c = a + (b + c), (ab) c = a (bc),
(a + b) c = ac + bc .
Кроме того, в поле требуется существование нулевого элемента 0 (нуля), для которого 0 + a = a , и для каждого элемента a противоположного элемента –a, то есть такого элемента, что a + (–a ) = 0, а также существование единичного элемента e (единицы), для которого ae = a, и для каждого ненулевого элемента a существование обратного элемента a–1, т.е. такого элемента, что aa–1 = e. Отсюда следует, что в поле выполнимы операция вычитания, а также операция деления на ненулевой элемент. Таким образом, все элементы поля образуют абелеву группу по сложению (аддитивная группа поля), а все ненулевые элементы — абелеву группу по умножению (мультипликативная группа поля).
- 2. Операции над множествами. Круги Эйлера. Покрытия и разбиения. Классы разбиения.
- 3. Законы алгебры множеств. Формула включений и исключений.
- 5. Соответствия. Способы задания соответствий.
- 6. Инволюция (обращение) соответствий. Объединение, пересечение, дополнение, произведение соответствий.
- 7. Функциональные соответствия, их связь с графиками функций.
- 8. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество.
- 9. Отношение. Бинарное отношение. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное отношения.
- Унарные:
- Бинарные:
- Соответствия a, b, r
- 10. Отношение эквивалентности. Фактор-множество множества по отношению.
- 11. Отношение предпорядка, упорядоченности, строгой упорядоченности. Отношение частичного порядка.
- 12. Замыкание отношений. Рефлексивное, симметричное, транзитивное замыкание отношений.
- 13. Понятие нечеткого множества. Функция принадлежности. Способы формализации нечетких множеств. Наиболее распространенные параметрические функции принадлежности.
- 14. Основные логические операции над нечеткими множествами и их свойства.
- 15. Диаграмма Хассе как способ задания отношения частичного порядка на множестве.
- 16. Отображения. Изоморфизм. Автоморфизм. Гомоморфизм. Эпиморфизм. Эндоморфизм. Мономорфизм. Биморфизм.
- 17. Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли.
- 18. Группоид. Квазигруппа. Латинский квадрат. Лупа. Полугруппа. Моноид. Группа. Абелева группа.
- 19. Группа симметрий фигуры.
- 20. Группа подстановок.
- 21. Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.
- 22. Решетка (структура). Решетка как частично упорядоченное множество.
- 23. Решетка как универсальная алгебра.
- Графы и ориентированные графы
- 27. Виды графов: двудольные графы, регулярные графы, полные графы, деревья, планарные графы
- 28. Изоморфизм графов.
- 29. Способы задания графов.
- 32. Эйлеров путь в графе. Задача о кенигсбергских мостах. Эйлеров цикл. Теорема о существовании эйлерова цикла.
- 33. Алгоритм нахождения эйлерова цикла и его вычислительная сложность.
- 34. Гамильтонов цикл в графе. Алгоритм с возвратом для поиска гамильтонова пути. Оценки вычислительной сложности алгоритма.
- 35. Задача коммивояжера. Алгоритм поиска субоптимального решения.
- 36. Задача построения минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима. Оценка вычислительной сложности этих алгоритмов.
- 37. Перенумерация вершин графа. Алгоритм топологической сортировки.
- 39. Принцип оптимальности Беллмана. Алгоритм нахождения кратчайшего пути в ориентированном графе и его вычислительная сложность.
- 1 Begin
- 40. Алгоритм вычисления расстояний между всеми парами вершин графа. Общий случай.
- 41. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры. Оценка вычислительной сложности.
- 1 Begin
- 5 Begin
- 42. Алгоритм топологической сортировки. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе в случае бесконтурного графа. Оценка вычислительной сложности
- 43. Знаковые графы и их практическое применение. Задачи из области социологии малых групп, экономики и политики.
- 44. Теорема о структуре (теорема Харари о балансе).
- 45. Знаковые орграфы как модель когнитивных карт. Контуры положительной и отрицательной обратной связи и устойчивость/изменчивость моделей на орграфах.
- 46. Двудольные графы. Необходимое и достаточное условие двудольности графа.
- 47. Сети Петри. Функционирование сети Петри. Конечные разметки сети.
- Иллюстрация к правилу срабатывания перехода
- 48. Сети Петри. Ограниченность, безопасность, сохраняемость, достижимость, живость. Моделирование на сетях Петри.
- 50. Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система. Способы описания конечных автоматов: перечислительный; диаграмма состояний; таблица состояний.
- 51. Алгебра логики. Функции алгебры логики. Существенные и несущественные переменные. Бинарные логические операции. Формула. Суперпозиция функций. Таблицы истинности и таблицы Кэли.
- 52. Формы записи операций (функций) — инфиксная, префиксная, постфиксная. Эквивалентные формулы.
- 53. Основные схемы логически правильных рассуждений.
- 54. Функционально полные системы (базисы). Булева алгебра логики. Функциональная полнота системы булевых функций. Примеры других алгебр логики.
- 55. Основные эквивалентные соотношения в булевой алгебре. Выражение через дизъюнкцию, конъюнкцию и отрицание других логических бинарных операций. Двойственность.
- 56. Булева алгебра логики. Сднф и днф. Карта Карно. Функциональные схемы как приложение булевых функций.
- 57. Функции k-значной логики и их задание с помощью таблицы истинности и с помощью таблицы Кэли. Примеры k-значных логик.
- 59. Квантор всеобщности и квантор существования.
- 61. Истинные формулы и эквивалентные соотношения логики предикатов.
- 62. Префиксная нормальная форма. Процедура получения пнф.
- 63. Формальные теории. Принципы построения формальной теории.
- 64. Исчисление высказываний.