Алгоритмы. Рекурсивные функции. Часть I
пределение. Алгоритм — некоторая конечная последовательность предписаний (правил, инструкций и т.п.), однозначно определяющая процесс преобразования исходных P и промежуточных данных в результат Q решения задачи.
Теория алгоритмов — это наука, изучающая общие свойства и закономерности алгоритмов, разнообразные формальные модели их представления. На основе формализации понятия алгоритма возможно сравнение алгоритмов по их эффективности и другим показателям, проверка их эквивалентности, определение областей применимости.
Абстракция потенциальной осуществимости. Как уже отмечалось, алгоритмический процесс при выработке результата Q из исходных данных P совершает несколько отдельных шагов. Число таких шагов может быть настолько велико, что достижение результата Q является практически неосуществимым. Однако в теории алгоритмов мы не учитываем практическую неосуществимость и считаем возможным выполнить любое конечное число шагов. Это положение называется абстракцией потенциальной осуществимости. Это же положение предполагает, что мы можем оперировать со сколь угодно большими объектами, например, сколь угодно длинными словами и т.п.
Описание алгоритмов и формулирование используемых правил могут осуществляться различными математическими средствами. Каждый способ задания алгоритма характеризуется абстрактным алфавитом и математическим формализмом. При этом вводится понятие алгоритмической системы, как общего способа задания алгоритмов
Введение. Алгоритмические системы
Алгоритмической системой называется математический формализм, предназначенный для строгого описания всего множества неформально определенных алгоритмов.
Алгоритмическая система должна обеспечивать возможность описания алгоритма для любой алгоритмически разрешимой задачи или доказательство невозможности такого описания, если данная задача неразрешима.
В теории алгоритмов используются разные подходы к построению алгоритмических систем:
1. Функциональный подход, основанный на традиционных математических понятиях числовой функции и вычислений. Исторически это первый подход к построению алгоритмических систем, в рамках которого была впервые решена проблема алгоритмической разрешимости и построена алгоритмическая система на основе рекурсивных функций Гёделя-Клини.
Эта алгоритмическая система является хорошо изученной, а полученные с ее помощью результаты используются во многих разделах математики и вне рамок теории алгоритмов. При использовании алгоритмических моделей этого класса основной акцент делается на результат выполнения алгоритма, т.е. алгоритм рассматривается с точки зрения его результата.
2. Автоматный подход, основанный на построении и описании работы некоторой интерпретирующей системы (абстрактного автомата). В качестве интерпретирующих систем выступают машины — дискретные устройства, которые выполняют некоторые элементарные операции на каждом шаге вычислений. По своей концепции эти абстрактные машины близки к современным ЭВМ. В рамках этого подхода разработаны алгоритмические системы Поста, Тьюринга, Шепердсона-Стерджиса, Ван Хао, основанные на описании машин, преобразующих слова в определенном алфавите.
3. Языковый подход, основанный на описании преобразований слов в абстрактных алфавитах. В качестве элементарных операций используются подстановки — замены другими словами подслов входного слова и слов, получающихся на промежуточных шагах алгоритма. В рамках подхода характерно использование специальных методов преобразования слов и языков описания правил вывода. Используются продукции Поста, формальные грамматики Хомского, нормальные алгорифмы Маркова.
Частично-рекурсивные функции
Частичной n-арной функцией f, заданной на множестве натуральных чисел, называется правило, которое некоторым наборам (x1, x2, …, xn) натуральных чисел ставит в соответствие однозначно определенное число f (x1, x2, …, xn) Î N. Множество Х, состоящее из всех наборов (x1, x2, …, xn), для которых существует значение функции f, называется областью определения функции f, а множество всех значений функции f называется областью значения функции f. Функция f называется всюду определенной, если ее значение определено при любом наборе аргументов (Пример — любая нуль-арная функция). Функция f (x1, x2, …, xn) называется вычислимой, если существует алгоритм a, вычисляющий функцию f.
Определение. Общерекурсивными (англ. general recursive) называют всюду определенные частично рекурсивные функции. Любая примитивно рекурсивная функция является общерекурсивной. Поэтому и для частично рекурсивных функций можно считать, что у них в качестве аргумента и результата могут быть списки из натуральных чисел.
Определение. Функция f: N→N∪{⊥} называется вычислимой (англ. computable function), –– если существует программа, вычисляющая функцию f, такая, что:
— если f (n) определено для натурального числа n, то программа завершает свою работу на входе n и выводит f (n); если f (n) не определено, то программа зависает на входе n.
Определение. Числовые функции являются частичными, если они определены не на всем множестве натуральных чисел. Частным случаем частичной числовой функции является всюду определенная числовая функция, т.е. на всем множестве натуральных чисел.
Определение. Частично рекурсивными (англ. partial recursive) называют функции, которые можно получить с помощью правил минимизации, подстановки и рекурсии из константной функции 0, функции I (x) = x+1, и набора функций Pn, k (x1, …, xn) = xk,
Pn, k (x1, …, xn) = xk, где k⩽ n. Заметим, что частично рекурсивная функция может быть не определена для некоторых значений аргументов.
Будем далее рассматривать совокупность функций от аргументов с целыми неотрицательными значениями. В этой совокупности выделим класс частично-рекурсивных функций, которые можно получить из трех исходных функций совокупности при помощи трех операций.
Такими тремя исходными функциями являются:
1. О (х) = 0 — функция нуля, которая всюду определена и ставит любому значению аргумента х значение 0.
2. s (x) = x +1 — функция следования (или сдвига), которая всюду определена и ставит любому значению аргумента х следующее значение в расширенном натуральном ряде.
3. Imn (x1, …, xn) = xm — функция выбора (или проектирующая функция, или функция введения фиктивных переменных), которая всюду определена для n (n>0) своих аргументов и ставит любому набору значений этих аргументов значению аргумента с номером m (m< n}).
Все эти функции, очевидно, вычислимы.
Операции, при помощи которых из исходных функций нуля, следования и выбора получаются любые другие частично-рекурсивные функции, имеют названия суперпозиции С, примитивной рекурсии Pr и минимизации μ
Операция суперпозиции С
Будем говорить, что n-местная функция ф получена из m-местной функции f и
n-местных функций g1, g2, …, gm с помощью оператора суперпозиции, если для всех x1,…, xn, справедливо равенство:
ф (x1,…, xn) = f (g1(x1,…, xn), …, gm (x1,…, xn)).
Если функции g (x1, …, xn), f1(x1, …, xn), …, fm (x1, …, xn) частично-рекурсивны, то суперпозиция этих функций также является частичной функцией целочисленных неотрицательных аргументов и, по данному определению, частично-рекурсивна. Получение функции f из функций g, f1, …, fmобозначается схемой f = С (g, f1, …, fm)
Понятие суперпозиции функций и сложной функции хорошо известно, но нас сейчас этот оператор интересует с точки зрения его взаимоотношений с процессом вычислимости функций с помощью машин Тьюринга.
Заметим, что если функции g, f1, …, fm являются полными (всюду определены), то функция f также является полной. Но если одна из функций g, f1, …, fm является частичной, то частичной может быть и функция f их суперпозиции.
Отметим также, что функции f1, …, fm могут иметь разные аргументы и их число, так как при помощи функции выбора мы можем ввести фиктивные аргументы. Например, пусть даны функции g (u, v), f1 (x, y), f2 (x, z), и мы хотим определить функцию h (x, y, z) как их суперпозицию. Так как x = I13 (x, y, z), y = I23(x, y, z), z = I33(x, y, z), то можно определить
h (x, y, z) = g (f1 (I13(x, y, z)), I23(x, y, z)), f2 (I13(x, y, z), I33(x, y, z)).
Пример 1. Применение оператора суперпозиции к функциям: h (x, y) = х + y;
g1(v, u, z) = u2vz; g2(v, u, z) = 2uvz. После подстановки получаем
f (v, u, z) = F21(h, g1, g2) = u2vz +2uvz.
Операция примитивной рекурсии Pr
Возьмем пару частично-рекурсивных функций g(x1, …, xn), h(x1, …, xn, y, z). Тогда примитивной рекурсией этих функций называется функция f = Pr (g, h), определяемая следующим соотношением
При этом при вычислении значения функции для некоторого значения аргумента y = p производятся последовательные вычисления значений функции для y = 0, 1,2, …, р. Но если какое-либо значение в этой последовательности окажется неопределенным (в силу частичности функций g и h), то значение функции f также становится неопределенным для этого значения аргумента y. Использование операции примитивной рекурсии обеспечивает накопление результатов, что соответствует циклическому алгоритму вычислений.
Пример 2. Функцию сложения х + y можно определить следующим образом:
х + 0 = х = I12(х, у),
х + (у + 1) = (х + у) + 1 =s(х + у).
Поэтому можно взять g (x, у) =I12(х, у), h (x, у, z) = s(х + у), где такие функции уже определены как рекурсивные. И тогда схема функции суммирования
х + у =Рr (I12(х, у), s(х + у)).
Операция минимизации μ
Эта операция позволяет получать обратные функции. Определяется она следующим образом. Пусть имеется частично-рекурсивная функция g (x1, …, xn-1, y). Фиксируем набор (x1, …, xn-1) всех аргументов, кроме последнего, и рассмотрим уравнение относительно y:
g (x1, …, xn-1, y) = xn, с помощью которого мы определим новую функцию f (x1, …, xn). Для этого будем искать минимальный корень уравнения, вычисляя последовательно
g1(x1, …, xn-1, 0), g2(x1, …, xn-1,1), … и т.д. до тех пор, пока
— либо не найдем решения,
— либо не обнаружится, что очередное значение функции g не вычисляется для указанных аргументов (в силу частичности этой функции),
— либо мы не убедимся, что решения нет.
Решение, если оно есть, обозначим через μy (g (x1, …, xn-1, y) = xn) и определим как значение функции f (x1, …, xn). Если же решение не найдено (его нет, или для некоторого значения y из последовательности 0, 1, 2, … не определена функция g), то значение функции f при этих значениях аргументов является неопределенным (частичность функции f).
Операция минимизации μ (g) определяет для частично-рекурсивной функции
g (x1, …, xn-1, y) другую частично-рекурсивную функцию
f (x1, …, xn) = μy (g (x1, …, xn-1, y) = xn).
Пример 3. Функция √х является обратной для функции х2. Определим эту функцию через операцию минимизации для функции х2: √х = μy (y 2 = х). Эта функция определена для значений х = 0, 1, 4, 9, … и не определена, например, для значения х = 2, так как вычисляемые значения y 2 = 0, 1, 4, 9 растут монотонно и, следовательно, никогда не примут значения 2.
Пример 4. Функция х — y является обратной для функции х + y. Ее определим через операцию минимизации для функции х + y: х — y = μz (y + z = х). Эта функция определена для любых значений х ≥ y.
ХЕШИРОВАНИЕ
Хеши́рование (хэширование) (от англ. hash — мешанина, фарш), преобразование цифрового информационного объекта в кодовую последовательность фиксированной длины. Такое преобразование осуществляется путем использования хеш-функции. Примерами известных хещ-функций являются SHA-1, SHA-2 (Secure Hashing Algorithm), MD5, CRC-32, ГОСТ Р 34.11–2012(неофициальное название — Стрибог).
Цифровым информационным объектом может быть, например, отдельная запись в базе данных, пароль пользователя в информационной системе, сообщение электронной почты и др. Сущность этого понятия заключается в создании достаточно небольшого, не подлежащего расшифровке цифрового «отпечатка» фиксированной длины для произвольного информационного объекта. Как правило, этот отпечаток должен однозначно идентифицировать исходный объект, а восстановление исходной информации по этому отпечатку должно быть затруднено или невозможно.
В процессе хеширования выполняются три функции:
— Преобразование ключей переменной длины в значения фиксированной длины (обычно длиной в машинное слово или меньше), складывая их по словам или другим единицам с использованием оператора сохранения четности, такого как ADD или XOR,
— Перемешивание битов ключа так, чтобы полученные значения были равномерно распределены по пространству ключей , и
— Сопоставление ключевых значений со значениями, меньшими или равными размеру таблицы.
Свойства Хеш-функции
Уникальность — два разных сообщения не могут выдать одинаковый хеш (на самом деле бывают исключения (коллизии) — об этом позже).
«Лавинный эффект» — если в исходных данных поменять хотя бы одну букву, получится совершенно другой хеш.
Предсказуемость — для одного и того же сообщения всегда получается одинаковый хеш.
Необратимость — нельзя просто так взять и прочитать то, что захешировано. Нельзя просто так взять и развернуть алгоритм вспять и прочитать исходное сообщение.
Скорость — чтобы данные быстро обрабатывались в высоконагруженных системах.
Хорошая хеш-функция удовлетворяет двум свойствам: она должна быть очень быстрой для вычисления и должна минимизировать дублирование выходных значений ( коллизии ).
При тестировании хэш-функции равномерность распределения хэш-значений можно оценить с помощью теста хи-квадрат. Этот тест является мерой соответствия: это фактическое распределение элементов в корзинах по сравнению с ожидаемым (или равномерным) распределением элементов. Формула имеет вид
где n — количество ключей, m — количество сегментов, а b j — количество элементов в сегменте j.
Соотношение в пределах одного доверительного интервала (например, от 0,95 до 1,05) указывает на то, что оцененная хэш-функция имеет ожидаемое равномерное распределение.
Криптографическая хеш-функция — это алгоритм, который принимает на вход произвольный массив данных (сообщение, например, текст, картинку и др.) и превращает его в уникальный битовый массив фиксированного размера (из букв и цифр). Такой массив называется хешем, или хеш-суммой, а сам процесс — хешированием.
Иллюстрация: Оля Ежак для Skillbox M
КАК РАБОТАЕТ ХЕШ_ФУНКЦИ
Пусть задана фраза «Hello, world!», алгоритмом SHA-1она преобразуется в двоичный код:
01110111 01101111 01110010 01101100 01100100 00100001, который образован из10410 бит или 11010002. Но алгоритм SHA-1на вход принимает блоки размером только в 512 бит (у нас меньше), что требует дополнения
01001000 01100101 01101100 01101100 01101111 00101100 00100000
01110111 01101111 01110010 01101100 01100100 00100001 10000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 01011000
Дополнение начинается единицей, за которой следуют нули, а последний байт описывает размер сообщения в битах. Алгоритм SHA-1 использует также пять констант вида:
h0 = 0×67452301; h1 = 0xEFCDAB89; h2 = 0×98BADCFE; h3 = 0×10325476; h4 = 0xC3D2E1F0. Далее исходное сообщение разбивается на 80 частей (кусочков) и перемешивает с каждой из констант. Каждая итерация цикла обновляет значения h0–h4 до тех пор, пока не будет исчерпано исходное сообщение. На выходе готовый хеш получаем как конкатенацию финальных значений:
готовый хеш: 943a702d06f34599aee1f8da8ef9f7296031d699
Хеш-функция, сопоставляющая имена целым числам от 9 до 15. Обнаружена коллизия между ключами «Джон Смит» и «Сандра Ди»
Заключение
Подытожим основные положения статьи:
Рассмотрена одна из моделей формализации алгоритма.
Частично-рекурсивные функции, которая исторически появилась первой. Эта модель задается тремя очень простыми рекурсивными функциями из которых строятся более сложные функции с использованием трех операций: суперпозиции, примитивной рекурсии и минимизации.
К этим моделям тесно примыкает процедура хеширования, используемая во многих прикладных областях.
Криптографическая хеш-функция — это алгоритм, который принимает на вход сообщение и превращает его в хеш, то есть битовый массив фиксированного размера. Например, для SHA-1 это 160 бит (40 символов), а для SHA-256 — 256 бит (выдается 2^256 вариантов хешей)
Для каждого сообщения создаётся свой уникальный хеш. Если поменять во входных данных хотя бы один символ, хеш изменится до неузнаваемости Хеш можно присвоить любому файлу: тексту, песне или компьютерной игре. Ключевой смысл — убедиться, что данные нельзя изменить или подделать.
Результат работы хеш-функции необратимый — алгоритм нельзя запустить в обратную сторону и получить исходное сообщение. Этим хеширование отличается от шифрования, где, как правило, есть ключ дешифровки.
Хеширование используется для разных задач: для безопасного хранения паролей на сайте, создания цифровых подписей, защиты игровых данных, подтверждения транзакций в блокчейне и многого другого.
Литература
1. Д. Кнут. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: «Вильямс», 2006 —720 с.
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т1. М: Мир, 1978 — 612 с.
3. Мендельсон Э. Введение в математическую логику М: Наука, 1976 — 320 c.
4. Википедия. http://ru.wikipedia.org/wiki/
5. Хопрокфт Дж., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. 2-е издание. — М.: Издательский дом «Вильямс», 2002 — 528 с.
6. Миллер Р. Теория переключательных схем / Р. Миллер. — М.: Наука, 1971. — Том 2: Последовательностные схемы и машины. — 304 с.
7. Стаблибайн Т. Регулярные выражения. Карманный справочник. — СПб.: Питер, 2004 —160 с.
8. Оллонгрен А. Определение языков программирования интерпретирующими автоматами. М.: Мир, 1977 — 288 с.
9. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. СПб.: Наука, 2000 — 780 с.
10. Проектирование цифровых вычислительных машин / С.А. Майоров, Г.И. Новиков, О.Ф. Немолочнов и др. Под ред. С.А. Майорова. М.: Высш.шк., 1972. 344 с.
11. Гринченков Д.В., Потоцкий С.И. Математическая логика и теория алгоритмов для программистов. Учебное пособие. М: Кнорус, 2010 — 208 с.
12. Трахтенброт В.А. Алгоритмы и вычислительные автоматы. М.: Сов.радио, 1974 — 200 с.
13. Гавриков М.М., Иванченко А.Н., Гринченков Д.В. Теоретические основы разработки и реализации языков программирования, Учебное пособие. М: Кнорус, 2010 — 184 c.
14. Ахо А., Хопкровт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов, М: Мир , 1979 — 536 с.
15. Ананий В. Левитин. Алгоритмы: введение в разработку и анализ. — М.: «Вильямс», 2006 — 576 с.
16. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ. — 4-е изд. М.: Вильямс, 2011 — 1296 с.
17. Норенков И.П. Основы автоматизированного проектирования: учеб. для вузов. — 4-е изд., перераб. и доп. — М.: Изд-во МГТУ им. Н.Э. Баумана, 2009. — 430 с.
18. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. — 2-е изд. — М.: Вильямс, 2008. — 528 с.
19. Tourlakis G. Theory of Computation. — Wiley, 2012.
20. Arora S., Barak B. Computational Complexity: A Modern Approach. — Cambridge: Cambridge University Press, 2009.
