Теория алгоритмов

УДК 510.5
ББК  22.12
     К90


                                      Рецензенты:
         доктор технических наук, профессор В.И. Римшин, член-корреспондент РААСН;
                        кандидат технических наук, доцент Н.А. Гаряев,
 доцент кафедры информационных систем, технологий и автоматизации в строительстве НИУ МГСУ





     Куликов, Владимир Георгиевич.
К90      Теория алгоритмов [Электронный ресурс] : учебно-методическое пособие / В.Г. Куликов,
      В.С. Евстратов  ; Министерство науки и высшего образования Российской Федерации,
     Национальный исследовательский Московский государственный строительный университет,
     кафедра информационных  систем, технологий и автоматизации в  строительстве. —
     Электрон. дан. и прогр. (1,2 Мб). — Москва  : Издательство МИСИ – МГСУ, 2022. —
    Режим доступа: http://lib.mgsu.ru — Загл. с титул. экрана.
        ISBN 978-5-7264-2963-2 (сетевое)
        ISBN 978-5-7264-2964-9 (локальное)

       В учебно-методическом пособии по дисциплине «Теория алгоритмов» представлены разделы,
      традиционно изучаемые в курсе теории алгоритмов: машины Тьюринга, нормальные алгоритмы
      Маркова, рекурсивные функции и т.д. Рассмотрены вопросы интуитивного и формального опреде      ления алгоритмов, сложности и нумерации алгоритмов, алгоритмически неразрешимых проблем,
      конструирования машин Поста.
         Для обучающихся по направлению подготовки 09.03.02 Информационные системы и технологии.


                                   Учебное электронное издание


                                            © ФГБОУ ВО «НИУ МГСУ», 2022

                Редактор Л.В. Себова
              Корректор В.К. Чупрова
     Компьютерная правка и верстка О.В. Суховой
   Дизайн первого титульного экрана Д.Л. Разумного

     Для создания электронного издания использовано:
         Microsoft Word 2010, ПО Adobe Acrobat Pro.


Подписано к использованию 16.01.2022. Объем данных 1,2 Мб.


         Федеральное государственное бюджетное
      образовательное учреждение высшего образования
           «Национальный исследовательский
  Московский государственный строительный университет»
            129337, Москва, Ярославское ш., 26.

                  Издательство МИСИ – МГСУ.
   Тел. (495) 287-49-14, вн. 14-23, (499) 183-91-90, (499) 183-97-95.
                   E-mail: ric@mgsu.ru, rio@mgsu.ru

                           Оглавление


ВВЕДЕНИЕ ................................................................................................................................................. 5

1. ОСНОВНЫЕ ПОНЯТИЯ И МОДЕЛИ АЛГОРИТМОВ ..................................................................... 6

2. МАШИНА ТЬЮРИНГА ...................................................................................................................... 21

3. МАШИНА ПОСТА ............................................................................................................................... 22

4. РЕКУРСИВНЫЕ ФУНКЦИИ .............................................................................................................. 23

5. АССОЦИАТИВНЫЕ ИСЧИСЛЕНИЯ ................................................................................................ 25

6. КЛАССЫ СЛОЖНОСТИ ..................................................................................................................... 26

7. ЛОГИЧЕСКИЙ СИНТЕЗ ВЫЧИСЛИТЕЛЬНЫХ СХЕМ ................................................................. 29

Библиографический список ..................................................................................................................... 37

ПРИЛОЖЕНИЕ ......................................................................................................................................... 38

                          ВВЕДЕНИЕ
    Современное формальное определение алгоритма было дано в 1930–1950-х годах в произведениях А. Тьюринга, Э. Поста, А. Черча, Н. Винера, А.А. Маркова.
   Алгоритм (процедура) — решение задач в виде точных последовательно выполняемых
предписаний. Это интуитивное определение сопровождается описанием интуитивных свойств
(признаков) алгоритмов: эффективность, определенность, конечность [1].
   Эффективность — возможность исполнения предписаний за конечное время.
    Например, алгоритм — процедура, состоящая из «конечного числа команд, каждая из которых
выполняется механически за фиксированное время и с фиксированными затратами»1.
   Функция может быть эффективно вычислена с помощью алгоритмов, если существует механическая процедура, из которой для конкретных значений ее аргументов может быть найдено
значение этой функции.
   Определенность — возможность точного математического определения или формального
описания содержания команд и последовательности их применения в этой процедуре.
   Конечность — выполнение алгоритма для конкретных исходных данных за конечное количество шагов.
   Для доказательства алгоритмов в теории используются алгоритмические преобразования слов
и фраз формального языка.
   В формальных описаниях алгоритм конструктивно связан с концепцией машины, предназначенной для автоматизированных преобразований символьной информации.
   Для автоматических расчетов разрабатываются модели алгоритмов распознавания языков и
машина, которая работает с этими моделями. Таким образом, они сочетают математическое и формальное определение алгоритма с конструктивным, что позволяет создавать модели на компьютере.
    Алгоритмические вычисления используются во всех областях науки и техники. Например, в
монографии Д. Кнута [1] рассматривается множество проблемно ориентированных алгоритмических
решений.
    Интуитивно понятный графический метод построения алгоритмов в виде диаграмм и схем
по-прежнему актуален и поддерживается стандартами языкового редактирования.
   Объектно ориентированное обобщение алгоритмических языков позволяет включить алгоритмическое мышление и организовать крупномасштабное программирование с огромной производительностью и ресурсами компьютерной памяти, что постоянно увеличивает стандартные библиотеки.
    Теория алгоритмических языков и компиляторов действительно связана с алгоритмами, но
это независимая область знания и применения алгоритмов.
   Общая теория алгоритмов обращается к проблеме эффективной вычислимости. Было разработано несколько формальных определений алгоритма, в которых эффективность и окончательность вычислений можно количественно оценить с помощью количества элементарных шагов
и требуемого объема памяти.
   Аналогичными моделями алгоритмических преобразований символьной информации являются:
    – конечные автоматы;
    – машина Тьюринга;
    – машина Поста;
    – ассоциативное исчисление или нормальные алгоритмы Маркова;
    – рекурсивные функции.
    Некоторые из этих моделей составляют основу методов программирования и используются в
алгоритмических языках.
   В современной программной инженерии алгоритмы как методы решения задач занимают
видное место по сравнению с традиционной математикой. И неважно, есть ли в абстрактных алгоритмических моделях чистое алгоритмическое решение. Если необходимо решение проблемы,
широко используются эвристики, и «доказательством» работоспособности алгоритма является
его успешное тестирование [2].

       1 Ахо А. Теория синтаксического анализа, перевода и компиляции : в 2 т. Т. 1 / А. Ахо, Дж. Ульман ; пер. с англ.
В.Н. Агафонова ; под ред. В.М. Курочкина. — Москва : Мир, 1978. — 612 с.
                                           5

                1. ОСНОВНЫЕ ПОНЯТИЯ И МОДЕЛИ АЛГОРИТМОВ

   Для формального описания алгоритма необходимо формальное описание решаемой проблемы. В большинстве случаев описание проблемы носит неформальный (вербальный) характер,
следовательно, переход к алгоритму неформальный и требует проверки и тестирования, а также
нескольких итераций для приближенного решения.
   Верификация (от лат. verus — истинный и facere — делать) — способ подтверждения
любых теоретических положений, алгоритмов, программ и процедур путем сравнения их с
экспериментальными данными (справочными или эмпирическими), алгоритмами и программами.
   Тестирование используется для определения соответствия объекта испытаний указанным
спецификациям.
   Теория алгоритмов не может предоставить универсального и формального способа описания проблемы и ее алгоритмического решения. Однако ценность теории состоит в том, что
она дает примеры таких описаний и определения алгоритмически неразрешимых задач.
   Один из примеров — на обычном языке, и задача формулируется как разработка алгоритма
распознавания принадлежности любого предложения к определенному регулярному языку.
Доказано, что регулярный язык можно формально преобразовать в модель алгоритма для
решения этой проблемы за конечное число шагов. Эта модель представляет собой конечный
автомат.
    Регулярные языковые расширения используются: при описании словаря формальных алгоритмических языков и алгоритмов, при исследовании шаблонов редактирования, в современном программировании (Java, Phyton, C#, PHP, JS), в компиляторах и системах управления
обработкой данных, в качестве интерактивных языков в операционных системах. Следовательно, конечный автомат может использоваться для алгоритмического решения проблем в
этих областях.
   Алфавит языка обозначается как конечное множество символов. Например:                                       ∑= {𝑎, 𝑏, 𝑐, 𝑑},   Символ и цепочка символов образуют слово — a, b, 0, abbcd, 0111000. Пустое слово (е)∑= {0, 1}.не содержит символов.
   Множество слов S = {a, ab, aaa, bc} в алфавите  называют языком
   Язык S = L(Σ) может содержать неограниченное количество слов.                                         Σ                    L(Σ).   Для их определения используются различные формальные правила. В простейшем случае
это алгебраическая формула, которая содержит операции по формированию слов из символов
алфавита и ранее полученных слов.
    Рассмотрите следующие шаги, чтобы сформировать новые наборы из существующих
наборов слов.
     1. Символы алфавита могут быть связаны путем конкатенации (присоединения) к строкам
словесных символов, связанных с новыми словами.
    Конкатенация двух слов x|y обозначает, что к слову x справа приписано слово y или x|y = xy,
причем xy ≠ yx.
    Произведение S1|S2 = S1S2 множеств слов S1 и S2 — это множество всех различимых слов,
построенных конкатенацией соответствующих слов из S1 и S2.
   Если S1 = {a, aa, ba}, S2 = {e, bb, ab}, то S1S2 = {a, aa, ba, abb, aabb, baab, ...}. Для конкатенации выполняется ассоциативность, но коммутативность и идемпотентность не выполняются:
S1S2 ≠ S2S1; SS ≠ S.
     2. Объединение (S1   S2) или (S1 + S2) множеств:
    S1 = {a, aa, ba}, S2 = {e, bb, ab}, S1   S2 = {a, aa, ba, e, bb, ab}. Для операции объединения               ∪выполняются следующие законы:                         ∪
                                           6