19. Группа симметрий фигуры.
Сопряженные элементы группы. Два элемента a и b группы G называются сопряженными, если существует такой элемент g , что a g = g b, т.е. если g-1 a g = b. Говорят также, что a получается трансформацией элемента b элементом g . Если g-1 a g = a, то элемент a называется инвариантным относительно трансформации элементом g.
Сопряженная подгруппа. Если для подгрупп A и B группы G найдется такой элемент g G, что A g = g B, т.е. g-1 A g = B, то подгруппа B называется сопряженной подгруппе A в G. Говорят также, что подгруппа B получается трансформацией подгруппы A элементом g. Если g-1 A g = A, то подгруппа A называется инвариантной относительно трансформации элементом g. Поскольку нормальный делитель группы инвариантен относительно трансформации любым ее элементом, то его называют также инвариантной подгруппой группы.
Покажем сейчас на примере, как понятия теории групп позволяют сжато выражать некоторые геометрические факты. Чертеж слева (где P — фиксированная точка, t — фиксированная прямая, X — переменная точка, пробегающая множество всех точек плоскости) приводит нас к следующей теореме. Результат последовательного отражения точки X относительно прямой t, полученного образа относительно точки P и этого нового образа опять относительно прямой t совпадает с результатом отражения точки X относительно точки P, симметричной точке P относительно прямой t. Сформулируем этот факт в терминах группы движений плоскости. Отражение относительно точки P обозначим через . Очевидно, 2 = 1, т.е. = -1. Аналогично, обозначив отражение относительно прямой t через , получаем, что 2 = 1, откуда -1 = . Теперь наше геометрическое утверждение о трех последовательных отражениях может быть выражено следующей формулой: = -1 . Чертеж справа показывает, что три последовательных отражения — относительно точки P, затем прямой t и, наконец, снова точки P — равносильны отражению относительно прямой t , симметричной прямой t относительно точки P. Это можно выразить формулой: = -1.
t t t
X
P P
X
Кроме того, легко проверить, что условие принадлежности точки P прямой t равносильно условию = . Чтобы убедиться в этом, достаточно заметить, что в первом случае условие -1 = означает совпадение точек P и P, тогда как во втором случае условие -1 = означает совпадение прямых t и t.
Преимущества языка теории групп становятся особенно убедительными, если выраженные на этом языке геометрические понятия и отношения попытаться выразить также средствами аналитической геометрии. Например:
.
- 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. Исчисление высказываний.