- •31. Замыкание множества булевых функций.
- •38. Определение и свойства групп.
- •39. Группа подстановок.
- •40. Подгруппы. Пересечение подгрупп. Циклические подгруппы.
- •41.Теорема о подгруппе циклической группы.
- •42. Порядок элемента группы. Теорема о циклической подгруппе.
- •43. Разложение группы по подгруппе. Теорема Лагранжа.
- •44. Гомоморфизмы и изоморфизмы групп. Ядро гомоморфизма. Изоморфизм циклических групп.
- •45. Нормальные подгруппы. Фактор-группы.
- •46. Теорема о гомоморфизме групп.
- •47. Определение и свойства колец.
- •48. Гомоморфизмы колец.
- •49. Идеалы, классы вычетов, фактор-кольца.
- •50. Теорема о гомоморфизме колец.
- •53) Простое поле. Теорема о изоморфизме простого поля.
- •54) Основные понятия теории графов.
- •55) Маршруты в графавах.
- •56) Матрица смежности и матрица инцидентности.
- •57) Алгоритмы обхода графа в ширину и глубину.
- •58) Алгоритмы Дейкстры.
58) Алгоритмы Дейкстры.
Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны ((u, v) ≥ 0 для всех (u, v)E).
Формальное объяснение
В процессе работы алгоритма Дейкстры поддерживается множество S V, состоящее из вершин v, для которых δ(s, v) уже найдено. Алгоритм выбирает вершину u V\S с наименьшим d[u], добавляет u к множеству S и производит релаксацию всех рёбер, выходящих из u, после чего цикл повторяется. Вершины, не лежащие в S , хранятся в очереди Q с приоритетами, определяемыми значениями функции d. Предполагается, что граф задан с помощью списков смежных вершин.
Не формальное объяснение
Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.