Математическая логика и теория алгоритмов. Часть II. Теория алгоритмов
Покупка
Новинка
Многотомное издание:
Том 1 (2025), Том 2 (2025)
Издательство:
Директ-Медиа
Год издания: 2025
Кол-во страниц: 89
Возрастное ограничение: 16+
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-4499-5081-9
Артикул: 891195.01.99
В учебно-методическом пособии изложены основные сведения по математической логике. Учебно-методическое пособие содержит расширенный материал лекций (часть 2 - теория алгоритмов) по дисциплине «Математическая логика и теория алгоритмов», предусмотренных учебным планом и рабочей программой дисциплины.
Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления».
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Математическая логика и теория алгоритмов Часть II Теория алгоритмов Учебно-методическое пособие Москва 2025
УДК 510.5(075) ББК 22.127я73 М34 Составители: Шабанова Н. Ю., Ефремова О. А. Рецензенты: Гринюк А. В., канд. техн. наук, кафедра информатики и информационной безопасности АНО «Международная полицейская академия»; Михед А. Д., канд. техн. наук, доц. каф. информационной безопасности и вычислительной техники ТулГУ Математическая логика и теория алгоритмов. В 2 ч. М34 Ч. 2 : теория алгоритмов : учебно-методическое пособие / сост. Н. Ю. Шабанова, О. А. Ефремова. — Москва : Директ-Медиа, 2025. — 88 с. ISBN 978-5-4499-5081-9 (ч. 2) ISBN 978-5-4499-5082-6 В учебно-методическом пособии изложены основные сведения по математической логике. Учебно-методическое пособие содержит расширенный материал лекций (часть 2 — теория алгоритмов) по дисциплине «Математическая логика и теория алгоритмов», предусмотренных учебным планом и рабочей программой дисциплины. Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления». УДК 510.5(075) ББК 22.127я73 ISBN 978-5-4499-5081-9 (ч. 2) ISBN 978-5-4499-5082-6 © Шабанова Н. Ю., составление, 2025 © Ефремова О. А., составление, 2025 © Издательство «Директ-Медиа», оформление, 2025
Введение Дисциплина «Математическая логика и теория алгоритмов» закладывает прочный фундамент для изучения практически всех специализированных курсов, преподаваемых в технических вузах и университетах для направлений подготовки, связанных с изучением компьютеров, информационных технологий и коммуникационных сетей. Непосредственная цель дисциплины «Математическая логика и теория алгоритмов» — дать основы теории математического обеспечения для современных компьютерных и информационных технологий. Практически половину курса «Математическая логика и теория алгоритмов» занимает теория алгоритмов: подходы к понятию алгоритма, свойства, типы алгоритмических моделей, вопросы оптимизации программ, математические основы программирования. В настоящее время многие вопросы теории алгоритмов, особенно их эффективность и сложность, рассматриваются и являются важными при решении многих практических задач. В связи с развитием сферы применимости теории алгоритмов возрастает значение и актуальность этого раздела в изучаемой дисциплине. Теория алгоритмов является мощным инструментом для исследований во множестве новых областей. Основные положения теории алгоритмов приведены в части 2 данного учебно-методического пособия. В рамках данного раздела дисциплины предполагается изучить элементы теории алгоритмов и их сложности.
1. Определение сложности алгоритмов Понятие «алгоритм» давно является привычным не только для математиков. Оно является концептуальной основой разнообразных процессов обработки информации. Возможность автоматизации таких процессов обеспечивается наличием соответствующих алгоритмов. С алгоритмами первое знакомство происходит в начальной школе при изучении арифметических действий с натуральными числами. В упрощенном понимании «алгоритм» — это то, что можно запрограммировать на компьютере. Слово «алгоритм» содержит в своем составе преобразованное географическое название Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока — Муххамад ибн Муса ал-Хорезми (Магомет, сын Моисея, из Хорезма). Он жил приблизительно с 783 по 850 гг., и в 1983 г. отмечалось 1200-летие со дня его рождения в городе Ургенче — областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как cugorismi. Откуда и пошло слово «алгоритм» — сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям. Зародившись еще в средневековье, интуитивное понятие алгоритма c середины XX в. получило широкое распространение. Однако формирование строгого научного понятия алгоритма не закончено и в настоящее время. Прежде, чем затронуть эту сложную и важную проблему, перейдем к примерам. Рассмотрим алгоритм Евклида, который допускает «арифметическую» интерпретацию — нахождение наибольшего общего делителя (НОД) двух натуральных чисел. Если дана пара натуральных чисел a > b, то результат деления а на b c остатком r эквивалентен равенству а = q · b + r. В этом случае НОД(а,b) = НОД(b,r), (1) например, 21 = 2 · 9 + 3 и НОД(21,9) = = НОД(9,3) = 3. Пусть а0 и а1 — натуральные числа, а0 > а1.
Поиск НОД(а0, а1) по алгоритму Евклида требует выполнения
серии однотипных шагов, каждый из которых — деление с
остатком:
0
1 1
2
1
2
2
3
2
1
1
1
,
,
.
n
n
n
n
n
n
n
a
q a
a
a
q a
a ,
a
q
a
a
a
q a
−
−
−
−
=
+
↓
↓
=
+
=
+
↓
↓
=
3333333333333
(1)
В этом случае
0
1
(
,
),
na
НОД a a
=
так как
0
1
1
2
1
(
,
)
( ,
)
(
,
)
n
n
n
НОД а а
НОД а а
НОД а
а
a
−
=
=
=
=
2
.
Формула (1) позволяет оформить алгоритм Евклида в виде
рекурсивной процедуры, то есть процедуры, вызывающей самое
себя (пример простейшей рекурсии — факториал: n! = (n – 1)! n).
Запишем процедуру NOD на псевдокоде, близком языку Паскаль (заменив для краткости блочные скобки begin, end на фигурные: {, } ):
NOD(a,b)
{ if b=0 then NOD:= a
else { r:= a mod b; NOD:= NOD(b,r) }}
Здесь использована операция mod вычисления остатка от
деления а на b (например, 30 mod 21 = 9). При вычислении
NOD(30,21) = NOD(21,9) = NOD(9,3) = 3 процедура вызывает
себя трижды.
В численном анализе близкими к рекурсиям являются
рекуррентные соотношения, оформленные в виде итерационных схем:
1
0
(
),
задано,
n
n
x
x
x
Φ
+ =
−
решающих уравнения типа
( )
x
x
Φ
=
, где x — вещественное
число (x может быть и вектором с вещественными координатами). xn — последовательность рациональных приближений,
при определенных условиях сходящаяся к точному решению.
Итерации проводятся до тех пор, пока расстояние между соседними приближениями не станет меньше заданной погрешности:
(
)
n
n
| x
x
|
Φ
ε
−
<
. Здесь возникает проблема зацикливания алгоритма, если последовательность хn расходится. Рассмотрим
алгоритм A(x0), решающий уравнение х = х2 методом итераций:
A(x0)
{ x:= x0;
while abs(x−x*x) > 1e−6 do x:= x*x;
A:= x }
Вызвав процедуру А(0,99), получим результат, приближенно равный нулю — меньшему корню уравнения, так как
0 99m
nx
,
=
стремится к нулю с ростом степени
2n
m =
. Но незначительное увеличение исходного данного х0 нашего алгоритма
всего лишь на 0,02 приведет к расходящемуся процессу, так как
1,01m →∞ при
2n
m =
→∞.
Численные методы также можно «арифметизировать» —
свести к алгоритмам, работающим с натуральными числами: из-за
ограниченности разрядной сетки компьютера вещественные
числа — бесконечные десятичные дроби — заменяются рациональными приближениями с конечной мантиссой, а любое рациональное число можно задать парой натуральных чисел, например:
1,5 = 3 : 2 ∼ (3, 2); −2 = 3 − 5 ∼ (3, 5).
С кибернетической точки зрения алгоритм можно рассматривать, как «техническое» устройство, преобразующее набор
входных данных х1, х2, … хm в выходные параметры у1, у2, … уn,
например, как процедуру умножения матрицы на вектор (рис. 1):
1
1
2
3
1
2
1
2
3
2
3
x
a a a
y
x
b b b
y
x
=
Рис. 1. Алгоритм как «техническое» устройство
Чтобы ограничиться функциями, принимающими только
числовые, а не векторные значения, мы можем данный пример
представить в виде двух алгоритмов:
1 1
2
2
3
3
1 1
2
2
3
3
( )
;
( )
.
A x
a x
a x
a x
B x
b x
b x
b x
=
+
+
=
+
+
Алгоритм
x1
x2
x3
y1
y2
Приведенные соображения позволяют свести теоретические проблемы существования и сходимости алгоритмов к изучению натуральных функций натуральных аргументов: A: N × N × … × N → N, где N — множество натуральных чисел. Вплоть до 30-х гг. нашего столетия понятие алгоритма оставалось интуитивно понятным, имевшим скорее методологическое, а не математическое значение. Так, к началу XX в. много ярких примеров дала алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако в начале XX в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование разрешающего алгоритма — это можно сделать, используя интуитивное понятие алгоритма. Другое дело — доказать несуществование алгоритма — для этого нужно знать точно — что такое алгоритм. Задача точного определения понятия алгоритма была решена в 30-х гг. в работах Гильберта, Черча, Клини, Поста, Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Рекурсивная функция это функция, для которой существует алгоритм вычисления ее значений по произвольному значению аргумента. Класс рекурсивных функций был определен строго как конкретный класс функций в некоторой формальной системе. Был сформулирован тезис (называемый «тезис Черча»), утверждающий, что данный класс функций совпадает с множеством функций, для которых имеется алгоритм вычисления значений по значению аргументов.
Другой подход заключался в том, что алгоритмический процесс определяется как процесс, осуществимый на конкретно устроенной машине (называемой «машиной Тьюринга»). Был сформулирован тезис (называемый «тезис Тьюринга»), утверждающий, что любой алгоритм может быть реализован на подходящей машине Тьюринга (МТ). Оба данных подхода, а также другие подходы (Марков, Пост) привели к одному и тому же классу алгоритмически вычислимых функций и подтвердили целесообразность использования тезиса Черча или тезиса Тьюринга для решения алгоритмических проблем. Поскольку понятие рекурсивной функции строгое, то с помощью обычной математической техники можно доказать, что решающая некоторую задачу функция не является рекурсивной, что эквивалентно отсутствию для данной задачи разрешающего алгоритма. Аналогично, несуществование разрешающей МТ для некоторой задачи равносильно отсутствию для нее разрешающего алгоритма. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, т. е. получение высказываний типа «Задача P алгоритмически разрешима» или «Задача P алгоритмически неразрешима». В данном направлении получен ряд фундаментальных результатов. Среди них отрицательное решение Новиковым П. С. в 1952 г. классической проблемы тождества для конечно определенных групп, сформулированной Деном в 1912 г. Знаменитая десятая проблема Гильберта, сформулированная им в 1900 г. (среди других 23 проблем) формулируется так: «10. Задача о разрешимости диофантова уравнения. Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах». Алгоритмическая неразрешимость 10-й проблемы Гильберта была доказана в 1970 г. Мятиясевичем Ю. В. В настоящее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение теории алгоритмов осуществляется как в использовании самих результатов (особенно это касается использования разработанных
алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помощью проясняются такие понятия как доказуемость, эффективность, разрешимость, перечислимость и другие. В технику термин «алгоритм» пришел вместе с кибернетикой. Понятие алгоритма помогло, например, точно определить, что значит эффективно задать последовательность управляющих сигналов. Применение компьютеров послужило стимулом развитию теории алгоритмов и изучению алгоритмических моделей, к самостоятельному изучению алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а также их оптимизации. Возникло важное направление в теории алгоритмов — сложность алгоритмов и вычислений. Начала складываться так называемая метрическая теория алгоритмов, основным содержанием которой является классификация задач по классам сложности. Сами алгоритмы стали объектом точного исследования, как и те объекты, для работы с которыми они предназначены. В этой области естественно выделяются задачи получения верхних и задачи получения нижних оценок сложности алгоритмов, и методы решения этих задач совершенно различны. Для получения верхних оценок достаточно интуитивного понятия алгоритма. Для этого строится неформальный алгоритм решения конкретной задачи, и затем он формализуется для реализации на подходящей алгоритмической модели. Если показывается, что сложность (время или память) вычисления для этого алгоритма не превосходит значения подходящей функции при всех значениях аргумента, то эта функция объявляется верхней оценкой сложности решения рассматриваемой задачи. В области получения верхних оценок получено много ярких результатов для конкретных задач. Среди них разработаны быстрые алгоритмы умножения целых чисел, многочленов, матриц, решения линейных систем уравнений, которые требуют значительно меньше ресурсов, чем традиционные алгоритмы. Установить нижнюю оценку — значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алгоритмической модели, и такие результаты получены только в очень жестких вычислительных моделях. В связи с этим получила развитие