Брачная не статья. Теория алгоритмов. Часть 1.

Добрый утро, день, вечер. Мы вот с вами опять тут. Так как желающих продолжения криптографии пока нет(Мынка сам не хочет) мне предложили рассказать о Теории Алгоритмов. Мой коллега рассказывал это на одной из встреч(Каких встреч? Я опять что то пропустил?), но там почти никого не было, а Мынке тема понравилась и поэтому мы тут с вами. Ну что же, начнём.

Теория алгоритмов: основные понятия

Ну для начала дадим определение алгоритма:

Определение: Алгоритм — это точное предписание о выполнении в определённом порядке простых операций для решения всех задач некоторого класса.

Звучит классно и возможно даже прикольно, НО если бы всё так было просто не было так интересно. Возникла необходимость формализации понятия алгоритма(начало XX в.(Скобочки мои, кыш)):

— Внутренние причины — потребности развития теории алгоритмов;
— внешние — появление алгоритмически неразрешимых проблем.

Лейбниц, XVII в.: цель — разработать единый алгоритм решения любой математической задачи(Ну удачи).

Не для всякого класса задач существует алгоритм решения; такие задачи названы алгоритмически неразрешимыми. Доказать алгоритмическую неразрешимость задачи невозможно без строгого определения понятия «алгоритм».

Это определение должно соответствовать существующему понятию. Решение было получено созданием различных алгоритмических систем(Нет, только не определение снова):

Определение: Способ задания алгоритмов, характеризующийся свойством универсальности, называется алгоритмической системой.

Звучит классно, да? Но что мы понимаем под универсальностью? Мы подразумеваем следующее:

Универсальность: любой алгоритм можно записать данным способом.

При изучении алгоритмических систем было выявлено:
— всякий алгоритм, сформулированный в любой алгоритмической системе, является алгоритмом в интуитивном смысле;
— все существующие алгоритмы могут быть записаны в любой алгоритмической системе;
— существуют алгоритмически неразрешимые проблемы.

Алгоритмы мы можем разделить по способу взаимодействия с окружающей средой:

И по способу организации вычислений:

Мы будем рассматривать последовательные вычислительные алгоритмы(Не понятно, но очень интересно)

Основные свойства вычислительных последовательных алгоритмов:
1. Конструктивность — алгоритм работает только с конструктивными объектами, т. е. объектами конечной длины.
2. Конечность — алгоритм должен быть задан конечным предписанием.
3. Дискретность и элементарность — алгоритм представляет собой последовательность элементарных шагов.
4. Результативность — для каждого шага и алгоритма в целом должно быть известно, что считать за результат. Результат должен получаться за конечное число шагов.
5. Детерминированность (определённость) — любое применение алгоритма к одним и тем же исходным данным должно приводить к одному и тому же результату и одной и той же последовательности шагов.
6. Массовость — алгоритм должен быть применим к большому множеству исходных данных

Звучит весело и интересно. Но с чем люди работают обычно? Правильно с алфавитом.

Определение: Абстрактный алфавит — это непустое конечное множество символов (знаков), называемых буквами алфавита.

Примеры:

A = {a, b, c}, B = {0, 1, . . . , 9}, C = {|}, D = {дикий, Мынка, убежал, _ }.

Слово в алфавите — конечная последовательность букв этого алфавита.

Множество всех слов в алфавите A обозначается

Примеры:

Длина слова α — количество букв в нём.

Пустое слово λ — слово нулевой длины (не пробел!).

Конкатенация слов α и β — слово γ, полученное приписыванием к слову α слова β: γ = α·β или γ = αβ.

Примеры:
кило · метр = километр;
α = λα = αλ;
abc = aλbc = abλc = . . .

Слово β является подсловом слова α, если α = γβδ, где γ, δ —любые слова, возможно, пустые.

Если мы рассмотрим слова baba (слово выбирал Мынка), и выпишем все его подслова то получим: λ, a, b, ab, ba, bab, aba, baba.

А теперь ваше любимое,
Определение: Алфавитным оператором называется всякое соответствие, сопоставляющее словам в некотором алфавите слова в том же самом или другом алфавите.

Будем обозначать алфавитные операторы Γ.
Пусть A — входной и B — выходной алфавит оператора Γ.
Тогда

Область определения алфавитного оператора Γ:

Если

то алфавитный оператор называется полностью определённым, иначе частично определённым.

Если

то оператор называется однозначным, иначе многозначным.

Выполним следующее задание:
A = {A, B, . . . , Z}, B = {0, 1, . . . , 9}, Γ каждой букве сопоставляет её ASCII-код.

Какой это оператор?

Ну логично(Нет), что это однозначный, так как элементу из A соответствует ровно один элемент из B. Но частично определённый так как соответствие задано для букв, а не для слов.