Теория алгоритмов
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
МИСИ-Московский государственный строительный университет
Год издания: 2022
Кол-во страниц: 43
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7264-2963-2
Артикул: 854436.01.99
В учебно-методическом пособии по дисциплине «Теория алгоритмов» представлены разделы, традиционно изучаемые в курсе теории алгоритмов: машины Тьюринга, нормальные алгоритмы Маркова, рекурсивные функции и т.д. Рассмотрены вопросы интуитивного и формального определения алгоритмов, сложности и нумерации алгоритмов, алгоритмически неразрешимых проблем, конструирования машин Поста.
Для обучающихся по направлению подготовки 09.03.02 Информационные системы и технологии.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
УДК 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 с.
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}. Для операции объединения ∪выполняются следующие законы: ∪