книги / Математическая логика и теория алгоритмов. Анализ алгоритмов
.pdfМинистерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования «Пермский национальный исследовательский политехнический университет»
А.Ю. Городилов, С.Ф. Тюрин
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ. АНАЛИЗ АЛГОРИТМОВ
ПодредакциейС.Ф. Тюрина
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
Издательство Пермского национального исследовательского
политехнического университета
2019
УДК 510 (075.8)
ББК 22.176я73+22.12я73 Г60
Рецензенты:
кандидат физико-математических наук, доцент А.С. Епифанов (Институт точной механики и проблем
управления РАН, г. Саратов); доктор технических наук, доцент В.И. Фрейман (Пермский национальный исследовательский
политехнический университет)
Городилов, А.Ю.
Г60 Математическая логика и теория алгоритмов. Анализ алгоритмов : учеб. пособие / А.Ю. Городилов, C.Ф. Тюрин; под ред. С.Ф. Тюрина. – Пермь: Изд-во Перм. нац. исслед. политехн.ун-та,2019.–176с.
ISBN 978-5-398-02230-8
Изложен материал лекций и практических занятий по основным задачам анализа сложности алгоритмов.
Предназначено для студентов бакалавриата и специалитета, изучающих дисциплину «Математическая логика и теория алгоритмов», а также может быть полезно для магистров, изучающих дисциплины «Исследование операций», «Теория игр и исследование операций», и аспирантов.
УДК 510 (075.8)
ББК 22.176я73+22.12я73
ISBN 978-5-398-02230-8 |
©ПНИПУ,2019 |
ОГЛАВЛЕНИЕ |
|
ВВЕДЕНИЕ................................................................................................. |
5 |
1. АНАЛИЗ СЛОЖНОСТИ НЕРЕКУРСИВНОГО |
|
АЛГОРИТМА ПО ПРОГРАММЕ ИЛИ СХЕМЕ............................. |
23 |
1.1. Пример анализа алгоритма вычисления |
|
факториала числа х (x > 0, x – целое число)............................................ |
24 |
2.АНАЛИЗСЛОЖНОСТИРЕКУРСИВНЫХ АЛГОРИТМОВ........ |
27 |
2.1. Решение рекуррентных соотношений .............................................. |
28 |
2.2. Рекурсивный алгоритм решения задачи о Ханойской башне............ |
32 |
2.3. Анализ рекурсивного алгоритма решения задачи |
|
о Ханойской башне.................................................................................... |
37 |
2.3.1. Анализ подстановок переменных в рекурсивном |
|
алгоритме решения задачи о Ханойской башне при n = 1............... |
42 |
2.3.2. Анализ подстановок переменных в рекурсивном |
|
алгоритме решения задачи о Ханойской башне при n = 2............... |
46 |
2.3.3. Анализ подстановок переменных в рекурсивном |
|
алгоритме решения задачи о Ханойской башне при n = 3............... |
49 |
2.4. Оценка сложности рекурсивного алгоритма решения |
|
задачи о Ханойской башне....................................................................... |
54 |
3. ПОНЯТИЕ ОБ ОЦЕНКЕ СЛОЖНОСТИ ПРОГРАММ |
|
ВСТРОЕННЫХ СИСТЕМ .................................................................... |
55 |
3.1. Примеры команд языка Ассемблер: АSM51 ................................... |
56 |
3.2. Пример программной реализации временной задержки |
|
на языке ASM51......................................................................................... |
66 |
3.3. Дизассемблирование.......................................................................... |
68 |
3.4. Декомпиляция и обратная разработка программного |
|
обеспечения................................................................................................ |
69 |
3.5. Программная реализация конечного автомата................................. |
70 |
3.6. Анализ универсальной программы распознавания |
|
последовательности срабатывания двоичных датчиков |
|
для микроконтроллера 80С51 в системе Proteus 7.2 SP6 |
|
на языке СИ................................................................................................ |
73 |
3
3.7. Программа распознавания последовательности |
|
вводимых с клавиатуры символов .......................................................... |
80 |
3.8. Программа контроллера NUCLEO-F401RE платформы |
|
Mbed для распознавания последовательности срабатывания |
|
переключателей ........................................................................................ |
83 |
4. ПОНЯТИЕ О ТЕСТИРОВАНИИ АЛГОРИТМОВ |
|
(ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ) ............................................. |
90 |
Отладка программ на языке ASM51........................................................ |
90 |
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 1. |
|
Анализ сложности нерекурсивных алгоритмов...................................... |
93 |
Ответы и советы. Практическое занятие № 1....................................... |
105 |
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 2. |
|
Анализ сложности рекурсивных алгоритмов........................................ |
108 |
Ответы и советы. Практическое занятие № 2....................................... |
118 |
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 3. |
|
Анализ сложности задач......................................................................... |
123 |
Ответы и советы. Практическое занятие № 3....................................... |
134 |
ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4. |
|
Практическая работа по исследованию и сравнению |
|
сложности алгоритмов............................................................................ |
139 |
Ответы и советы. Практическое занятие № 4....................................... |
146 |
ПРИЛОЖЕНИЕ А. Пример отчета по практической работе |
|
«Исследование и сравнение сложности алгоритмов» ......................... |
151 |
ПРИЛОЖЕНИЕ Б. Пример оформления исходного |
|
кода программы....................................................................................... |
159 |
ПРИЛОЖЕНИЕ В. Профилирование программ................................. |
170 |
СПИСОК ЛИТЕРАТУРЫ.................................................................... |
174 |
4
ВВЕДЕНИЕ
Со времен античности известен алгоритм (способ, метод) нахождения наибольшего общего делителя, описанный Эвклидом в своем труде «Начала».
Известен также алгоритм определения произвольного количества последовательных простых чисел, так называемое решето Эратосфена.
Прообраз алгоритма решения системы линейных алгебраических уравнений (метод исключения переменных) Гаусса описан в китайском источнике «Девять книг по арифметике»
(202 г. до н.э. – 9 г.н.э.).
ЕвклидилиЭвклид(древнегреч. |
ЭратосфенКиренский(древнегреч. |
||
́ |
́ |
́ |
́ |
Εὐκλείδης,от«добраяслава»,время |
ἘρατοσθένηςὁΚυρηναῖος; |
||
расцвета–около300г.дон.э.)– |
276г.дон.э.–194г.дон.э.)– |
||
древнегреческийматематик,автор |
греческийматематик,астроном, |
||
первогоиздошедшихдонастеоре- |
географ,филологипоэт,с235г. |
||
тическихтрактатовпоматематике |
дон.э.–главаАлександрийской |
||
|
|
библиотеки.Первыйизвестный |
|
|
|
учёный,вычислившийразмерыЗемли |
|
5
Но, конечно, в те времена всё это не называлось словом «алгоритм», этомы таксегодняназываем.
Считается, что понятием и словом «алгоритм» мы обязаны АльХорезми (полное имя – Абу Абдулла
(или Абу Джафар) Мухаммед ибн Муса (это типа отчество) альХорезми, т.е. из Хорезма) ок. 783 –
ок. 850 г.
Родина аль-Хорезми – историческая область Хорезм, включавшая в себя территорию современного Узбекистанаи часть Туркмении. Аль Хорезми написал первое руководство по арифметике, основанное на
позиционном принципе. Ему принадлежит процедура (алгоритм) вычислений в десятичной арифметике (так мы и вычисляем – «столбиком»). Написал знаменитую книгу «Китаб аль-джебр вальмукабала» – «Книга о восстановлении и противопоставлении» (посвящена решению линейных и квадратных уравнений), от названия которой произошло слово «алгебра» (аль джебра). Имя автора в латинизированной форме Algoris-
mus и Algorithmus стало, как считает-
ся, обозначать в средневековой Европе всю систему десятичной арифметики.
Но только через три века эта арифметика дошла до Европы благодаря Леонардо Пизанскому – первому крупному математику средневековой Европы.
Его отец былкупцом,часто был в северной Африке, где и познако-
6
мился с арабскими (индийскими) цифрами, в том числе с нулём. А до этого использовалась не очень удобная для купеческих вычислений (и вычисления процентов ростовщиками) римская система счисления. Леонардо более известен под прозвищем Фибона́ччи (Fibonacci), что в переводе с итальянского означает аббревиатуру «хороший сын родился» (Figlio Buono Nato Ci).
С Леонардо Пизанским связаны числа Фибоначчи (есть информация, что этот ряд Леонардо сам почерпнул в книгах с восто- ка)–рекурсия, введение арабских(индийских)цифр,нуля.
Но пока сложность вычислительных задач была в принципе не высокой, потребности в теории алгоритмов как таковой не было, и это продолжалось долгие века. Эта потребность возникла только к 30-м гг. ХХ в. на фоне создания первых ЭВМ и формирования информатики как науки.
А началось все с чисто логических проблем, со знаменитых теорем Гёделя.
Невозможность полной формализации для достаточно богатых формальных теорий потребовала уточнения и своего рода стандартизации понятия алгоритма как некой формальной и даже «механической» процедуры. Имеется информация, что Гёдель
следовал в США из фашистской |
|
Германии в 30-е гг. ХХ в. через тер- |
|
риторию СССР и проезжал на поез- |
|
де через Пермь. В США ему нужно |
|
было сдавать экзамен на гражданство, |
|
так вот он обнаружил, что конститу- |
|
ция США противоречива, и это якобы |
|
может создать условия законным пу- |
|
тем установить тиранию. По одним |
|
данным Эйнштейн на правах друга |
|
удержал Гёделя от заявления об этом |
|
на экзамене, по другим – Гёдель зая- |
Курт Гёдель (1906–1978) – |
вил об этом, но все обошлось, граж- |
австрийский и американский |
данство он получил. |
математик, логик |
7
АланМатисонТьюринг
(1912–1954)
ЭмильПост(1897–1954)–
американскийматематик
АлонзоЧёрч(1903–1995)–
американскийматематик илогик
Одним из ярчайших личностейоснователей теории алгоритмов может по праву считаться британский математик АланМатисон Тьюринг.
Машина Тьюринга – это абстрактная модель вычислительного устройства. В теории алгоритмов также известнаимашинаПоста.
Большой вклад в теорию алгоритмов внёсАлонзоЧёрч.
Известен так называемый тезис Чёрча. В терминах вычислимости по Тьюрингу, тезис гласит, что для любой интуитивно вычислимой функции существует вычисляющая её значения машина Тьюринга. Так называемый физический тезис Чёрча – Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.
Другой сильный тезис Чёрча – Тьюринга (тезис Чёрча – Тьюринга – Дойча): любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть реализован физическимустройством.
Сэр Чарльз Энтони Ричард Хоар известен как создатель алгоритмической логики, он автор известного алгоритма сортировки (и один из основателей структурного программирования).
8
Хоар обучался в МГУ компьютерному переводу в 1959 г. Он автор логики Хоара для конструирования корректных программ. Получил рыцарский титул в 2000 г. за заслуги в областиобразованияиIT.
Большой вклад в теорию алгоритмов внес Стивен Кук.
Стивен Артур Кук знаменит своей работой над теорией сложности вычислений, он лауреат премии
Тьюринга. В своей работе «The Complexity of Theorem Proving Procedures» Кук доказал, что задача выполнимости булевых формул в конъюнктивной нормальной форме КНФ (SAT) является NP-полной. Тем самым он поднял вопрос о равенстве классов сложности P и NP, один из сложнейших вопросов теории вычислительных систем, на который до сих пор нет ответа. Теорема Кука – Левина утверждает, что задача о выполнимости булевой формулы является NP-полной. Теорема называется теоремой Кука–Левина, поскольку независимо от Кука и в то же время эта теорема была доказанасоветским математиком Леонидом Левиным.
Стивен Кук(род.1939)– |
ЛеонидАнатольевичЛевин |
американскийучёныйвобласти |
(род.1948г.,Днепропетровск)– |
теориивычислительныхсистем |
советскийиамериканскийматематик, |
|
специалиствобластитеории |
|
вычислительнойсложности |
9
С 50-х гг. XX в. – с момента создания вычислительной техники – начала активно развиваться теория сложности вычислений. Сложности временной (число шагов алгоритма) и/или пространственной (оцениваемой ёмкостью требуемой памяти), возможно, включая и память для записи самого алгоритма.
Постепенно сформировалось понятие «эффективного» алгоритма, под которым стали понимать любой полиномиальный алгоритм, т.е. алгоритм, время выполнения которого ограничено
|
некоторым полиномом от длины |
|
|
записи входных данных. Задачи, |
|
|
разрешимые такими алгоритмами, |
|
|
образуют класс, который стали |
|
|
обозначать через P. |
|
|
Любой алгоритм может быть |
|
|
описан с помощью трёх базовых |
|
|
управляющих структур: последо- |
|
Коррадо Бём (род. 1923) – |
вательность (х THEN у), ветвле- |
|
ние (IF х THEN у ELSE z), цикл |
||
итальянский математик |
(WHILE х DO у). Соответствую- |
|
|
щее математическое обоснование |
|
|
этому ранее в конце 40-х гг. ХХ в. |
|
|
интуитивно установленному факту |
|
|
как основе структурного програм- |
|
|
мирования выполнили в 1965 г. |
|
|
итальянские математики Коррадо |
|
|
Бёмом (Corrado Böhm) и Джузеппе |
|
|
Якопини(Giuseppe Jacopini). |
|
|
Об этом же неустанно говорил |
|
́ |
и писал один из «отцов» структурно- |
|
гопрограммированияДейкстра. |
||
Эдсгер Вибе Дейкстра (Edsger |
|
|
Wybe Dijkstra, 1930–2002) – |
Собственно, истоки програм- |
|
нидерландский учёный, труды |
мирования связаны с именем Джо- |
|
которого оказали влияние на |
||
на Бэкуса – американского учёного |
||
развитие информатики |
||
и информационных технологий |
в области информатики. |
10