Шифр Scytale

В криптографии шифр «Сцитала», известный также как шифр Древней Спарты, представляет собой прибор, используемый для осуществления перестановочного шифрования.

Прибор состоит из граненого цилиндра (жезла) и узкой полоски пергамента, которая обматывается вокруг цилиндра по спирали. На гранях цилиндра записывалось сообщение.

Шифр Цезаря

Шифр Цезаря – один из древнейших шифров. Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки.

Шифрование основано на использовании таблицы замен: в одну строку таблицы записываются буквы алфавита, а в другую – тот же алфавит, но сдвинутый влево на выбранное значение смещения. Символ, находящийся под символом исходного алфавита, – это заменяющий символ в шифротексте.

Шифр моноалфавитной подстановки

Метод шифрования, при котором каждая буква исходного текста заменяется на другую букву или символ из определенного набора подстановки.

Шифрование основано на использовании таблицы замен: в одну строку таблицы записываются буквы алфавита языка исходного сообщения, а в другую строку – символы, на которые заменяются буквы исходного сообщения.

Key – это кодовое слово, на основе которого формируется алфавит шифротекста. Первым шагом создания нового алфавита служит удаление всех повторяющихся букв, которые присутствуют в кодовом слове. Затем из алфавита удаляются все буквы кодового слова. На заключительном шаге кодовое слово внедряется в алфавит со смещением первого элемента кодового слова на величину параметра Offset.

Шифр двойной перестановки

Метод шифрования, основанный на перестановке символов или букв входного текста. Он представляет собой комбинацию двух этапов перестановки: по строкам и по столбцам матрицы.

Процесс шифрования начинается с разбивки открытого текста на строки, которые затем заполняются в матрицу. Затем происходит перестановка символов по строкам и столбцам в матрице в соответствии с заданным ключом или алгоритмом. Полученная матрица становится шифротекстом.

Шифр Виженера

Шифр Виженера можно рассматривать, как шифр, состоящий из последовательности нескольких шифров Цезаря с различными значениями сдвига алфавитов.

Для зашифровывания используется таблица замен, в которой каждой букве алфавита языка исходного сообщения ставится в соответствие несколько вариантов букв для представления в шифротексте. Для этого выбирается кодовое слово длиной n, которое делит открытый текст на отрезки та- кой же длины.

Далее составляется так называемая таблица Виженера: горизонтально записывается алфавит языка исходного сообщения, а вертикально под первым символом алфавита записывается кодовое слово. Заполнение таблицы осуществляется символами алфавита, начинающегося с очередной буквы кодового слова и циклически замыкающегося.

Элемент шифротекста выбирается на пересечении столбца, соответствующего букве открытого текста, и строки, соответствующей букве кодового слова.

Шифр Хилла

Шифр, основанный на матричном преобразовании текста.

Перед шифрованием необходимо каждому символу алфавита следует сопоставить код равный порядковому номеру символа в алфавите.

Затем коды символов открытого текста записываются в матрицу размером n × m и создается шифрующая матрица n × n.

Для шифрования матрица открытого текста умножается на шифрующую матрицу и вычисляется остаток от деления значения элементов матрицы-произведения на число символов выбранного алфавита.

Комбинированный шифр ADFGVX

Шифр ADFGVX – один из самых известных шифров времен Первой мировой войны, который использовался немецкой армией. Особенность шифра заключается в том, что он основан на комбинации базовых операций замены и перестановки.

Шифрование осуществляется в два этапа:
1. На первом этапе сначала задается матрица-ключ 6 × 6, заполненная произвольно символами алфавита и цифрами от 0 до 9. Индексами строк и столбцов этой матрицы служат буквы A, D, F, G, V, X. Далее каждый символ открытого текста кодируется парой буквенных индексов, на пересечении которых в матрице-ключе он находится.

2. На втором этапе задается кодовое слово для перестановки столбцов, а затем ранее закодированный открытый текст переписывается построчно в матрицу с числом столбцов, равным длине ключевого слова. В завершение столбцы этой матрицы переставляются в соответствии с лексикографическим порядком букв ключевого слова и итоговый шифротекст образуется конкатенацией строк этой матрицы.

Шифр Плейфера

Шифр подстановки, который использует матрицу, называемую таблицей Плейфера, для шифрования и расшифровки сообщений.

Чтобы зашифровать текст, его необходимо разбить на пары символов (блоки).

Процесс шифрования подчиняется следующим правилам:
⁃ Если два символа совпадают или остался один символ, то к первому символу добавляется X и шифруется уже эта пара.
⁃ Если символы находятся в одной строке, то они замещаются на сим- волы, расположенные в ближайших от них ячейках справа.
⁃ Если символы находятся в одном столбце, то они замещаются на рас- положенные ниже в ближайших от них клетках
⁃ Если символы находятся в разных углах образуемого ими прямо- угольника, то они заменяются на символы, стоящие в противоположных углах этого прямоугольника в тех же строках.

Алгоритм А*

Используется для поиска кратчайшего пути. A* сочетает в себе элементы алгоритма Дейкстры и жадного поиска по принципу «наилучшее первое» для поиска оптимального пути с учетом предполагаемой стоимости.

Ключевые идеи:
⁃ Эвристическая функция h(n):
Оценивает стоимость от текущего узла до цели. Эвристика помогает эффективно направлять поиск к цели.
⁃ Функция стоимости g(n):
Представляет фактическую стоимость от начального узла до текущего узла.
⁃ Общая стоимость f(n):
представляет собой сумму функции стоимости и эвристики: f(n) = g(n) + h(n).

Временная сложность алгоритма A* зависит от эвристики. В худшем случае, число вершин, исследуемых алгоритмом, растёт экспоненциально по сравнению с длиной оптимального пути, но сложность становится полиномиальной, когда эвристика удовлетворяет следующему условию:
| h(n) - h*(n) | <= O (log h*(x))
где h* — оптимальная эвристика, то есть точная оценка расстояния из вершины x к цели.

Алгоритм Беллмана-Форда

Широко используемый алгоритм в теории графов и сетевом анализе. Он используется для поиска кратчайшего пути от одной исходной вершины ко всем остальным вершинам взвешенного графа, даже если граф содержит ребра с отрицательным весом.

Ключевые идеи:

⁃ Кратчайший путь из одного источника.
Беллман-Форд фокусируется на поиске кратчайшего пути от исходной вершины ко всем остальным вершинам графа.
⁃ Ребра с отрицательным весом.
В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда может обрабатывать графы с ребрами с отрицательным весом. Однако он не может обрабатывать графы с отрицательными весовыми циклами.
⁃ Релаксация
Основная операция Беллмана-Форда – это релаксация. Алгоритм итеративно улучшает расчетное расстояние до вершин, учитывая все ребра.

Сложность: O(V*E)

Алгоритм Прима

Алгоритм в теории графов для поиска минимального остовного дерева (MST) связного неориентированного графа с взвешенными ребрами.

Минимальное остовное дерево — это подграф, который включает все вершины исходного графа, образует дерево (без циклов) и имеет минимально возможную сумму весов ребер.

Алгоритм:
1. Начните с пустого набора, представляющего минимальное связующее дерево (MST). Выберите произвольную начальную вершину (обычно первую) и добавьте ее в MST.
2. Пока MST содержит менее V вершин: Определите ребро минимального веса, которое соединяет вершину в MST с вершиной вне MST и добавьте в MST вершину, соединенную выбранным ребром, вместе с самим ребром.
3. Продолжайте процесс выбора ребер, пока MST не будет содержать все вершины V.
4. Алгоритм завершен, когда MST содержит все вершины исходного графа.

Сложность: O(E + V log V)

Алгоритм Краскала

Алгоритм в теории графов для поиска минимального остовного дерева (MST) связного неориентированного графа с взвешенными ребрами. Он начинает с пустого дерева и неоднократно добавляет к нему ребра, гарантируя при этом отсутствие циклов.

Алгоритм:
1. Начните с пустого набора, представляющего минимальное связующее дерево (MST).
2. Отсортируйте все ребра графа в порядке возрастания веса.
3. Для каждого ребра проверьте, не приведет ли его добавление к MST к созданию цикла. Обычно это делается с использованием структуры данных с непересекающимися наборами. Если добавление ребра не образует цикл, добавьте его в MST.
4. Продолжайте процесс выбора ребер до тех пор, пока MST не будет содержать все вершины или пока не будут рассмотрены все ребра.
5. Алгоритм считается завершенным, когда MST содержит все вершины или когда все ребра учтены.

Сложность: O(E log E)

Алгоритм Борувки

Алгоритм для поиска минимального остовного дерева в неориентированном взвешенном графе. Он был разработан Йозефом Борувкой в 1926 году и является одним из первых оптимальных алгоритмов для этой задачи.

Алгоритм:
1. Начинаем с произвольного узла графа и инициализируем каждую компоненту связности как отдельное дерево.
2. На каждой итерации алгоритма просматриваем все ребра графа:
- Для каждой компоненты связности выбираем ребро минимального веса, которое соединяет ее с другой компонентой связности.
- Объединяем две компоненты связности в одну, используя выбранное минимальное ребро.
3. Повторяем шаг 2 до тех пор, пока не останется только одна компонента связности.

Сложность: O(E log V)

Алгоритм Миллера-Рабина

Алгоритм для проверки чисел на простоту. Он основан на принципе ферматовских свидетелей и позволяет с высокой вероятностью определить, является ли число простым или составным.

Алгоритм:
1. Представьте число n в виде n-1 = 2^s * d, где d нечетное.
2. Выберите случайное целое число a в интервале [2, n-2].
3. Вычислите a^d mod n.
4. Если (a^d) mod n = 1 или (a^d) mod n = n-1, перейдите к следующему шагу.
5. Для i от 1 до s-1:
- Вычислите (a^(2^i * d)) mod n.
- Если (a^(2^i * d)) mod n = n-1, перейдите к следующему шагу.
- Если (a^(2^i * d)) mod n = 1, то число n является составным.
6. Если ни в одном из шагов выше не было обнаружено свидетелей простоты, то число n с высокой вероятностью является простым. В противном случае, число n является составным.

Сложность: O(k * log^3(n))

Алгоритм обратного удаления

Тесно связан с алгоритмом Краскала.

В этом алгоритме мы сортируем все ребра в порядке убывания их весов. После сортировки поочередно выбираем ребра в порядке убывания. Мы включаем текущее выбранное ребро, если исключение текущего ребра приводит к отключению в текущем графе. Основная идея — удалить ребро, если его удаление не приводит к отключению графа.

Алгоритм:
1. Отсортируйте все ребра графа в порядке невозрастания весов ребер.
2. Инициализируйте MST как исходный граф и удалите лишние ребра, используя шаг 3.
3. Выберите ребро с наибольшим весом из оставшихся ребер и проверьте, разъединяет ли удаление ребра граф или нет. Если отключается, то ребро не удаляем. В противном случае мы удаляем край и продолжаем.

Сложность: O((E*(V+E)) + E log E)

Алгоритм Флойда — Уоршелла

алгоритм динамического программирования, используемый для поиска кратчайших путей между всеми парами вершин во взвешенном ориентированном графе.

Алгоритм:
1. Создайте матрицу для хранения кратчайших расстояний между всеми парами вершин и инициализируйте ее.
2. Каждую вершину графа рассматривайте как промежуточную вершину пути.
3. Обновите матрицу, учитывая, приводит ли использование промежуточной вершины к более короткому пути между любой парой вершин.
- Для каждой пары вершин (i, j) рассмотрим все вершины (k) как потенциальные промежуточные звенья:
- Если путь от вершины i до j через вершину k короче текущего расстояния от i до j, обновите расстояние в матрице.
4. Продолжайте, пока не будут рассмотрены все пары вершин.

Сложность: O(V^3)

Топологическая сортировка

Алгоритм, используемый для линейного упорядочения вершин ориентированного ациклического графа таким образом, что для каждого направленного ребра (u, v) вершина u предшествует вершине v в линейном порядке.

1. Инициализировать место, где вы будете хранить отсортированные вершины.
2. Выберите любую вершину без входящих ребер в качестве отправной точки.
3. Пока в графе есть необработанные вершины: Выберите вершину (v), у которой нет входящих ребер (степень 0), и удалите ее из графа. Добавьте вершину v в конец линейного порядка. Обновить степени соседних вершин (уменьшить на 1), поскольку вершина v была удалена.
4. Продолжайте шаг итерации, пока все вершины не будут обработаны.

Сложность: O(V + E)

Алгоритм LZW

Метод без потерь для сжатия данных, который основан на построении и использовании словаря. Он был разработан Терри Велчем в 1984 году.

Алгоритм:
1. Создаем словарь, содержащий начальный набор символов (обычно это все возможные символы, например, ASCII).
2. Читаем символы исходной строки один за другим.
3. Проверяем, есть ли текущая последовательность символов в словаре:
а. Если да, добавляем текущий символ к последовательности.
б. Если нет, записываем индекс текущей последовательности в выходной поток и добавляем новую запись в словарь с текущей последовательностью символов.
4. Повторяем шаги 2-3 до тех пор, пока не прочитаем все символы исходной строки.
5. Записываем последний индекс в выходной поток.
6. Завершаем сжатие.

Сложность алгоритма LZW зависит от размера исходной строки и размера словаря. В худшем случае: O(n^2), где n - размер строки.

Алгоритм Кнута-Морриса-Пратта

Алгоритм для поиска всех вхождений шаблона в тексте.

1. Создайте массив префиксов (также известный как LPS — самый длинный суффикс префикса), который поможет избежать ненужных сравнений на этапе поиска.
2. Начните сопоставлять шаблон с текстом с самого начала. Используйте два указателя: «i» и «j», чтобы отслеживать позиции.
3. Продолжайте поиск шаблона в тексте, обновляя i и j по мере необходимости.

Алгоритм выводит позиции всех вхождений шаблона в текст.

Сложность: O(N + M)

Алгоритм Рабина-Карпа

Алгоритм поиска строки в тексте, использующий хэш-функции для эффективного сравнения подстроки с искомой строкой.

Алгоритм:
1. Вычисляем хэш-функцию для искомой строки.
2. Вычисляем хэш-функцию для первой подстроки текста, длиной равной длине искомой строки.
3. Если хэш-значения совпадают, сравниваем каждый символ искомой строки с соответствующим символом подстроки текста. Если все символы совпадают, значит, мы нашли вхождение искомой строки.
4. Если хэш-значения не совпадают, перемещаем окно подстроки текста на один символ вправо и повторяем шаг 3 до конца текста.
5. Если мы достигли конца текста и не нашли вхождений искомой строки, значит, она отсутствует в тексте.

Сложность: O(n + m), где n - длина текста, а m - длина искомой строки. Однако, в худшем случае: O(n * m).