«С.М.Дудаков МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ В ИНФОРМАТИКУ Рекомендовано учебно-методическим советом по прикладной математике и информатике УМО по классическому университетскому образованию в качестве учебного пособия для ...»

Федеральное агентство по образованию

Российской Федерации

Тверской государственный

университет

С.М.Дудаков

МАТЕМАТИЧЕСКОЕ

ВВЕДЕНИЕ

В ИНФОРМАТИКУ

Рекомендовано учебно-методическим советом по прикладной математике и

информатике УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений обучающихся по направлению 010500 Прикладная математика и информатика Тверь 2007 УДК 519.681 ББК З81я731-1 Д 81 Тверской государственный университет Факультет прикладной математики и кибернетики http://pmkinfo.tversu.ru Рецензенты:

профессор доктор физ.-мат. наук Чагров А.В.

профессор доктор техн. наук Сухомлин В.А.

Дудаков С.М. Математическое введение в информатику: Учеб. пособие.

Тверь: Твер. гос. ун-т, 2003. 221с.

ISBN 5-7609-0233- В пособии освещаются теоретические вопросы программирования: связь и эквивалентность различных языков программирования, доказательство корректности программ, вычислительная сложность алгоритмов.

Учебное пособие адресовано, прежде всего, студентам младших курсов, обучающихся по направлению 010500 Прикладная математика и информатика Выражаем глубокую благодарность доктору физико-математических наук профессору кафедры общей и прикладной алгебры и геометрии Александу Васильевичу Чагрову за внимательное ознакомление с рукописью и ценные замечания и доктору физико-математических наук декану факультета прикладной математики и кибернетики профессору Александу Васильевичу Язенину за помощь в издании книги.

УДК 519. ББК З81я731- c Тверской государственный университет, c ISBN 5-7609-0233-4 С.М.Дудаков, Оглавление Оглавление Предисловие Глава 1. Введение § 1.1. Основные понятия......................... § 1.2. Исторические сведения...................... § 1.3. Свойства алгоритмов и языков программирования...... § 1.4. Примеры алгоритмов....................... Глава 2. Некоторые математические сведения § 2.1. Алгебра и теория множеств................... § 2.2. Графы................................ § 2.3. Математическая логика..................... Глава 3. Структурированные программы § 3.1. Синтаксис............................. § 3.2. Семантика............................. § 3.3. Свойства структурных программ............... § 3.4. Простые программы....................... § 3.5. Подстановка............................ Глава 4. Программы с метками § 4.1. Синтаксис............................. § 4.2. Семантика............................. § 4.3. Построение программ с метками................ § 4.4. Построение структурированных программ........... § 4.5. Блок-схемы............................. 4 Оглавление Глава 5. Доказательство корректности структурированных программ § 5.4. Существование слабейших предусловий........... § 6.2. Графы зависимости, списки и деревья вызовов........ § 6.3. Аппликативное и функциональное программирование... § 6.5. Доказательство корректности подпрограмм......... § 6.6. Корректность правила ВП.................. Предисловие Книга написана, прежде всего, для студентов, обучающихся по направлению Прикладная математика и информатика и специальности Прикладная математика. Поводом к написанию стало то, что автор не смог найти другого издания, где весь необходимый материал был бы изложен на достаточно высоком уровне.

В ходе написания было принято решение включить в это пособие не только материал для студентов первого курса, но и некоторые темы, которые могут быть изучены на старших курсах, а также в ходе факультативных или самостоятельных занятий. Это продиктовано желанием дать полное изложение соответствующих тем. Для удобства читателя мы указываем уровень сложности каждого параграфа. Параграфы, не имеющие никаких пометок, являются обязательными для изучения в полном объме. Параграфы, помеченные одной звёздочкой, имеют более высокий уровень сложности, на младших курсах обязательным является изучение только основных понятий из изложенного в них материала. Параграфы, отмеченные двумя звёздочками, не содержат материала, который был бы необходимым для младших курсов, и рекомендуются для самостоятельного изучения, факультативных занятий или спецкурсов.

При написании автор ставил перед собой задачу не впасть в одну из двух крайностей. С одной стороны он не хотел бы, чтобы это было очередным пособием по теории алгоритмов. По этой дисциплине имеется уже много прекрасных изданий. Кроме того, курс Информатика предназначен, прежде всего, не для изучения теоретических основ, а для получения знаний, которые были бы полезны при практическом программировании.

С другой стороны было бы неправильно свести эту книгу к изучению какого-то конкретного языка программирования или к перечню некоторых алгоритмов. Такого рода издания тоже не редкость, а соперничать в этом вопросе с Д.Кнутом было бы просто бессмысленно.

В этой книге выбран промежуточный вариант. Мы предлагаем несколько вычислительных моделей, которые основаны на реальных языках программирования, и ограничиваемся изучением свойств этих моделей. Мы не вдаёмся в такие понятия как разрешимость или рекурсивная перечислимость, свойственные теории алгоритмов. С другой стороны мы предельно абстрактизировали и упростили выбранные модели, в связи с чем имеем возможность аксиоматически определять, что такое программа и её семантика, а также доказывать их свойства. Из-за близости вводимых моделей к реальным языкам программирования эти свойства легко переносятся на практически используемые языки.

При изложении материала мы придерживаемся следующего порядка.

В первой главе мы пытаемся дать краткие исторические сведения о том, как развивались представления об алгоритмах, а так же привести несколько примеров, которые проиллюстрировали бы понятие алгоритм на хорошо известных примерах.

Вторая глава является кратким справочным пособием по тем разделам математики, которые потребуются при изучении материала, но которые могут быть ещё не известны студентам первого курса. Поскольку изложение этих сведений не есть основная цель книги, то мы даём эти определения на полуформальном уровне, прибегая к некоторым интуитивным примерам.

Изложение основного материала начинается с третьей главы. Мы определяем некоторый простой язык, на котором в дальнейшем будем писать программы. В качестве базовых синтаксических конструкций мы берём стандартный набор для построения структурных программ: присваивание, следование, ветвление и цикл. Такой набор, с одной стороны, является достаточным для того, чтобы построенный язык был универсальным и чтобы доказанные результаты можно было распространить на все алголоподобные языки, с другой стороны, он достаточно прост, и можно легко доказывать утверждения о построенных программах.

Мы определяем семантику программы как некоторое преобразование конечных функций, определённых на натуральных числах. Это даёт возможность излагать материал на уровне доступном как для тех, кто имел опыт программирования, так и для тех, у кого его нет. Остаток этой главы посвящён изучению свойств построенного языка и его семантики. Мы получаем некоторые хорошо известные в программировании факты как теоремы, доказанные исходя из определений алгоритма и его семантики В четвёртой главе мы рассматриваем другую концепцию программирования, ориентированную на метки и операторы перехода. Мы приводим необходимые определения и формулируем простую теорему, которая используется в дальнейшем. Затем мы доказываем эквивалентность языка структурного программирования и языка программирования с метками, и в качестве следствия получаем все нужные свойства программ с метками, а также теорему о цикле для структурных программ.

Пятая глава посвящена доказательству корректности структурных программ методом Хоара. Вначале мы кратко описываем понятие исчисления и вывода, затем формулируем аксиомы и правила вывода Хоара и семантику этого исчисления. Для каждого правила мы доказываем его непротиворечивость. Также мы формулируем некоторые правила, которые допустимы в исчислении Хоара, с доказательством допустимости. В следующих параграфах мы рассматриваем слабейшие предусловия, формулируем и доказываем правила их нахождения. В качестве завершения этой главы мы доказываем существование слабейших предусловий и полноту обоих исчислений.

В шестой главе мы изучаем вопросы, связанные с подпрограммами.

Мы определяем их синтаксис, семантику, а также приводим некоторые определения, связанные с рекурсивными алгоритмами. Дальше мы изучаем метод построения программ без использования циклов и операторов перехода (функциональное программирования), доказывая, что любая программа эквивалентна функциональной. Затем мы доказываем обратное утверждение о том, что от рекурсии всегда можно избавиться, и, как следствие, от подпрограмм вообще. Завершается глава изучением методов доказательства корректности подпрограмм.

В седьмой главе мы изучаем некоторые вопросы, связанные с ресурсомкостью вычислительного процесса. Мы доказываем нижнюю границу памяти, необходимую для хранения натуральных чисел. Затем мы определяем, что такое время и память вычисления при работе алгоритма на конкретных входных значениях, а затем, что такое максимальные и средние время и память. Основная задача этой главы дать общие представления об эффективности того или иного алгоритма и некоторые приёмы нахождения времени и памяти.

При изложении всего материала мы приводим достаточно большое число примеров. Детальный разбор примеров должен помочь читателю понять формальные определения на интуитивном уровне и показать, что все они имеют простой практический смысл.

Часто после примеров даётся некоторое количество задач. Как правило, эти задачи того же типа, что и рассмотренный пример, и решение задач позволяет глубже вникнуть в суть рассматриваемых вопросов и получить практический опыт работы с изучаемыми объектами.

Излагая доказательства тех или иных утверждений, мы старались по мере возможности избегать оборотов типа ясно что, за которыми следует не вполне очевидный факт. Тем не менее, доказательства не всех утверждений приведены целиком. Отдельные части оставлены в качестве задач, которые сформулированы после соответствующих доказательств. Например, мы почти всегда, доказывая утверждение для неполного ветвления, доказательство для полного оставляем в качестве задачи. Для некоторых утверждений мы вообще не приводим доказательств, оставляя их на самостоятельное изучение.

Все задачи в данной книге разбиты на три уровня сложности. Задачи без пометок самые простые. Эти задачи составляют необходимый минимум для того, чтобы получить на экзамене положительную оценку.

Задачи, отмеченные одной звёздочкой, имеют более высокую сложность.

В эту категорию отнесены многие из задач на доказательство. Третий уровень трудности задачи с двумя звёздочками. Эти задачи адресованы тем, кто желает глубже разобраться в изучаемом предмете, а также для факультативных занятий. Для решения некоторых из этих задач математического материала, изложенного во второй главе, может оказаться недостаточно. В этом случае следует обратиться к другим пособиям, где более подробно изложена соответствующая тема. Прежде всего, это относится к пятой главе, где мы делаем некоторые ссылки на утверждения, которые доказываются в курсе математической логики.

В конце книги приводится предметный указатель, в который включены все понятия, определяемые в данной книге. В начале указателя приведён перечень условных символов и обозначений. Если точного соответствия какого-либо обозначения не найдено, следует искать аналогичные, возможно, с другими буквами.

После предметного указателя приводится список литературы, рекомендованной для более глубокого изучения вопросов, упоминаемых в этой книге.

Все замечания и предложения следует отправлять автору по адресу Глава Введение § 1.1. Основные понятия С некоторым допущением можно сказать, что и н ф о р м а т и к а наука о способах автоматической обработки данных. Это далеко не единственная дисциплина, изучающая подобного рода вопросы. Например, математическая логика, дискретная математика, теория вероятностей тоже тем или иным способом затрагивают эту тему. Можно сказать, что информатика, в отличие от вышеперечисленных дисциплин, изучает, прежде всего, вопрос практического использования этих методов. Разумеется, широкое практическое использование невозможно без теоретических основ, поэтому можно считать, что теоретические дисциплины образуют фундамент для информатики.

Основные понятия информатики алгоритм и исполнит е л ь. Алгоритм некоторый набор инструкций, который предназначен для решения какой-либо задачи. Исполнитель тот, для кого этот набор инструкций предназначен. Естественно, что исполнитель должен понимать, как выполнять инструкции алгоритма. Следовательно, между алгоритмом и исполнителем должна быть связь с е м а н т и к а.

Семантика это то, как исполнитель выполняет инструкции алгоритма.

Один и тот же алгоритм может быть записан разными способами. Например, алгоритм решения квадратного уравнения можно записать в виде формулы, а можно в виде последовательности действий вида: Возвести b в квадрат, Умножить a на c, и т.д. Поэтому удобно иметь некоторый способ единообразной записи алгоритмов.

Самый очевидный путь использовать для записи алгоритмов е с т е с т в е н н ы е я з ы к и (например, русский или английский).

Однако этот путь имеет множество недостатков, основные из которых следующие:

• Сложность изучения. Для изучения естественного языка необходимо потратить довольно существенное время.

• Сложность т р а н с л я ц и и. Как правило, алгоритмы пишутся для их выполнения каким-либо вычислительным устройством. Следовательно, это вычислительное устройство должно тем или иным способом понимать инструкции алгоритма. Однако, восприятие естественных языков вычислительными устройствами крайне сложная проблема, которая до сих пор не решена окончательно.

• Возможная неоднозначность. Многие конструкции естественных языков имеют больше одного толкования. Следовательно, исполнитель в ряде случаев не в состоянии решить, что же именно требуется Из-за этих недостатков, появились специальные языки языки п р о г р а м м и р о в а н и я (ЯП), которые их лишены. Как правило, ЯП строятся на основе небольшого количества слов естественного языка (обычно, английского) и их сокращений. Таким образом, ЯП просты в изучении и легко транслируются. Кроме того, имеется жёсткий перечень способов построения программ, каждый из которых снабжён однозначным способом толкования. Поэтому все ЯП однозначны и не допускают различных толкований1. Алгоритм, записанный на каком-либо ЯП, называют п р о г р а м м о й. Как правило, ЯП являются у н и в е р с а л ь н ы м и, то есть на ЯП можно написать программу для решения любой теоретически разрешимой задачи. Однако, существуют примеры ЯП, которые таковыми не являются. Обычно, это специализированные языки для решения узкого круга задач (например, язык запросов к базам данных SQL).

1 Это условие не всегда выполняется полностью, то есть существуют некоторые синтаксические конструкции, которые допускают двоякий смысл. Однако число таких конструкций невелико, и они специально оговорены в описании языка.

§ 1.2. Исторические сведения Слово алгоритм, пришло в русский язык из английского (algorithm), а в западных языках оно произошло от имени средневекового учёного Аль-Хорезми (лат. Algorismus, Algorithmi). Хотя слово алгоритм весьма недавнего происхождения, но алгоритмы используются людьми с самых давних времён. Например, ещё в древнем Вавилоне знали, что треугольник со сторонами 3, 4 и 5 является прямоугольным и использовали алгоритм построения прямого угла, основыванный на построении таких треугольников. Там же был известен алгоритм решения квадратного уравнения. Древним грекам был известен алгоритм нахождения простых чисел (решето Эратосфена) и многие алгоритмы, предназначенные для геометрических построений. Естественно, что с развитием математики количество задач накапливалось, и для многих из них были придуманы те или иные алгоритмы решения. Хотя не для всех задач алгоритмы были придуманы, но большинство математиков верило, что рано или поздно они будут найдены. Ещё Г.В.Лейбниц мечтал придумать алгоритм, который решал бы любую математическую задачу.

Первые удары по этой мечте были нанесены в 19 веке, когда было доказано, что многие из задач (например, классические задачи древности трисекция угла, удвоение куба, квадратура круга) не могут быть решены традиционными средствами (в случае приведённых выше задач, построение невозможно с помощью циркуля и линейки). Поэтому круг задач, для решения которых искались алгоритмы, заметно сузился. Постепенно всё свелось к задаче разрешения арифметики натуральных чисел, то есть по произвольному утверждению о натуральных чисел (записанному, естественно, некоторым специальным образом) определить, истинно оно или ложно.

В первой половине 20 века были предложены некоторые математические модели алгоритмов. Разные модели были предложены независимо многими людьми (А.М.Тьюринг, А.Чёрч, С.Клини, А.А.Марков, В.А.Успенский и т.д.). Однако возник вопрос: насколько универсальными являются эти модели? Тот факт, что задача неразрешима с их использованием, может быть истолкован так, что модели слишком упрощённые, то есть можно в определение алгоритма добавить какие-то средства, и с их использованием задача может быть решена. Оказалось, что все предложенные модели алгоритма эквивалентны, то есть то, что можно формализовать в рамках одной из этих моделей, можно формализовать и в любой другой. Это дало повод для того, чтобы выдвинуть гипотезу (тезис Чёрча), что эти модели в точности описывают всевозможные алгоритмы.

В частности, все современные ЯП, допускают трансляцию в любую из этих моделей, что является ещё одним подтверждением тезиса Чёрча.

Точная математическая формулировка понятий алгоритм и р а з р е ш и м о с т ь (то есть возможность решить задачу с помощью какоголибо алгоритма) дала возможность определять, разрешима та или иная задача или нет. В частности, было доказано, что арифметика натуральных чисел неразрешима.

В связи с появлением понятия алгоритм возникли многие задачи, которые непосредственно с ними связаны. Например, определить, останавливается ли алгоритм при некоторых входных данных, эквивалентны ли два алгоритма между собой и т.д. Большинство таких задач тоже оказались неразрешимыми.

Исторические представления об исполнителях тоже менялись. Исполнителем для первых алгоритмов был человек. Но уже в 17 веке Б.Паскаль построил первое механическое устройство2 для выполнения сложения и вычитания многозначных чисел. В 19 веке появились арифмометры, которые помогали в выполнении более сложных операций. Однако, эти устройства являлись всего лишь средствами, исполнителем оставался человек.

Ч.Бэббидж в 19 веке дал теоретическое описание аналитической машины. Эта машина должна имела запоминающее, операционное и управляющее устройства. В связи с наличием памяти и устройства управления, она уже могла работать по программе, то есть сама выступать исполнителем.

Первые электронные вычислительные машины появились в середине 20 века. Единственным способом написания программ была ручная запись чисел в ячейки памяти. Программы представляли собой последовательность чисел, которые обозначали те или иные машинные команды ( Я П В дальнейшем с увеличением скорости работы машин и объёма их памяти был изобретён более удобный способ записи программ каждая машинная команда записывалась с помощью того или иного, легко запоминаемого обозначения. Были написаны программы, которые автоматически переводили эти языки в ЯП первого уровня первые трансляторы.

Такие ЯП, каждая инструкция которых соответствует одной машинной 2 Существуют сведения, что аналогичные устройства были сконструированы ранее, но ни их самих, ни их точных описаний не сохранилось.

команде, называют ассемблерами ( Я П в т о р о г о у р о в н я ).

Позже были построены ещё более удобные ЯП ( т р е т ь е г о у р о в н я ), которые, в основном, используются и до сих пор с теми или иными дополнениями. В них уже имелись такие конструкции, которые реализовывались целым набором (иногда довольно большим) машинных команд (ЯП третьего уровня). Языки, которые изучаются в данной книге, являются математическими моделями ЯП третьего уровня.

В связи с распространением вычислительной техники появились новые разделы теории алгоритмов, например, сложность вычислений, которая изучает вопросы ресурсоёмкости решения задач с помощью вычислительных устройств.

§ 1.3. Свойства алгоритмов и языков программирования В математике рассматривают два вида алгоритмов детермин и р о в а н н ы е и н е д е т е р м и н и р о в а н н ы е. Алгоритм называют детерминированным, если каждая инструкция алгоритма однозначно определяет действие исполнителя. Алгоритм недетерминированный, если такой однозначности нет. Очевидно, что в реальных вычислительных устройствах недетерминированные алгоритмы неприменимы.

Алгоритм называется у н и в е р с а л ь н ы м, если он приводит к правильному решению задачи при любых начальных условиях. Алгоритм называют к о н е ч н ы м, если он приводит к решению задачи за конечное число шагов. Естественно, что самый хороший случай когда для решения задачи существует универсальный и конечный алгоритм. Однако, имеется ряд задач, для которых эти условия оказываются взаимоисключающими каждый конечный алгоритм не универсален, а каждый универсальный не конечен. Но большинство задач, которые приходится решать с помощью вычислительных устройств являются хорошими, то есть для них существуют универсальные конечные алгоритмы.

Если для решения задачи существует несколько алгоритмов, то естественно возникает вопрос, какой из них наиболее целесообразно использовать. Можно сравнивать алгоритмы по их размеру чем меньше алгоритм, тем более простым он является, тем меньше вероятность ошибки.

Кроме того, для хранения самого алгоритма тоже необходима память, которая при небольших размерах алгоритма может быть использована под другие нужды.

Другой способ сравнения алгоритмов по их вычислительной сложности, то есть по тому, сколько времени и памяти требуется для выполнения этого алгоритма. Чем меньше эти требования, тем более приемлемым является алгоритм. Если, например, алгоритм существует, но для завершения работы требуется не меньше 10100 шагов, то его следует считать неприемлемым, так как мы никогда не дождёмся результата. Можно доказать, что существуют задачи, для решения которых существуют алгоритмы, но каждый из них требует колоссальных ресурсов уже для небольших входных данных. Подобного рода задачи следует считать практически неразрешимыми.

В противоположность универсальным алгоритмам выделяют алгоритмы ч а с т н ы е, то есть, предназначенные для решения конкретной задачи, и не рассчитанные на решение иных аналогичных задач. Такие алгоритмы менее полезны, однако, часто прибегают именно к ним. Основная причина универсальный алгоритм или отсутствует, или является чрезмерно сложным, или требует много ресурсов (времени, памяти), которые предоставить невозможно. В частном же случае почти всегда можно прибегнуть к тем или иным упрощениям, которые делают алгоритм приемлемым.

Промежуточное положение между универсальными и частными алгоритмами занимают алгоритмы п о л у у н и в е р с а л ь н ы е, то есть рассчитанные на решение задачи не при любых начальных условиях, а при некоторых из них.

Языки программирования можно разделить на две большие группы д е к л а р а т и в н ы е и и м п е р а т и в н ы е. Программы на императивных языках программирования содержат точную последовательность инструкций, выполняя которую, исполнитель получает результат. К этой группе относится большинство языков.

Программы на декларативных языках (SQL, Prolog) содержать не точные последовательности инструкций, а цели, которые должны быть достигнуты, и описание средств, с помощью которых это следует делать.

Точную последовательность действий в этом случае определяет сам исполнитель, анализируя эти сведения.

Другой способ деления ЯП в зависимости от задач, на решение которых ориентированы ЯП. Выделяют у н и в е р с а л ь н ы е ЯП ЯП, дач, а годятся для решения их широкого круга3 (C, C++, Pascal, Basic).

Другая группа с п е ц и а л и з и р о в а н н ы е ЯП, то есть, ориентированные на решение задач из достаточно узкой области (Refal, Lisp, Prolog, SQL, языки разных интегрированных систем, систем управления базами данных).

Императивные языки делятся по способу записи инструкций. Выделяют с т р у к т у р н ы е ЯП (C, C++, Pascal), ЯП о р и е н т и р о в а н н ы е н а м е т к и (ранние версии Basic’а, Focal, ассемблеры), (C++, Smalltalk) и т.д.

§ 1.4. Примеры алгоритмов Рассмотрим несколько примеров математических задач и построим алгоритмы (пока на естественном языке, с привлечением математических формул) для их решения. Мы предполагаем, что исполнитель умеет выполнять арифметические действия с действительными числами.

Пример 1.1 (Решение квадратного уравнения). Пусть необходимо решить квадратное уравнение Естественно, что корни находятся по формулам:

Это пример частного алгоритма.

Пример 1.2. Усложним предыдущий пример и построим более универсальный алгоритм. Пусть дано произвольное уравнение вида Простейший способ обобщения это подставить в предыдущие формулы вместо конкретных чисел буквенные обозначения:

3 Термин универсальный по отношению к ЯП, следовательно, используется в двух различных смыслах. С одной стороны, универсальный ЯП ЯП, на котором можно решить любую разрешимую проблему, с другой ЯП, который предназначен для решения широкого круга задач.

Такой алгоритм уже будет полууниверсальным, так как рассчитан на решение некоторой группы исходных задач. Более точно, он применим в случае, когда a = 0 и b2 4ac 0.

Пример 1.3. Сформулируем алгоритм, который решает уравнение для любых коэффициентов a, b и c.

• Если три предыдущих пункта не выполнены, то a = 0.

4. Вычислить дискриминант:

Пример 1.4 (Нахождение НОД). Простейший алгоритм нахождения наибольшего общего делителя x и y следует из его определения: можно перебирать все натуральные числа от 1 до x и найти наибольшее из них, которое делит и x, и 4. Увеличить i на 1 и перейти к пункту 2.

В отличие от предыдущего алгоритма, данный алгоритм является и т е р а ц и о н н ы м, то есть при его выполнении будет многократно повторяться одна и та же последовательность действий (пункты 2–4).

Данный алгоритм является полууниверсальным, например, он даёт неправильный ответ в случае, когда x = 0.

Задача 1.1. Доработайте алгоритм из предыдущего примера так, чтобы он стал универсальным.

Приведённый алгоритм является достаточно медленным из-за того, что перебираются все натуральные числа некоторого диапазона, хотя заранее можно сказать, что большинство из них не могут равняться НОД (x, y). Более совершенным является алгоритм Евклида, который основан на следующем утверждении:

Утверждение 1.1. Если x, y натуральные числа и x > y, то НОД (x, y) = НОД (x y, y).

Пример 1.5 (Алгоритм Евклида).

1. Если x = y, то ответ x.

2. Если x < y, то ответ НОД (x, y x).

3. Если x > y, то ответ НОД (x y, y).

Этот алгоритм является р е к у р с и в н ы м, то есть для достижения результата используется тот же самый алгоритм, но с другими входными данными.

Например, для вычисления НОД (6, 4), нужно будет последовательно вычислить НОД (2, 4) и НОД (2, 2).

Задача 1.2. Определите, является ли этот алгоритм универсальным. Если нет, измените его так, чтобы он стал им.

Можно превратить этот алгоритм в нерекурсивный:

Пример 1.6.

1. Если x = y, то ответ x.

2. Если x < y, то вычесть x из y и перейти к п. 1.

3. Если x > y, то вычесть y из x и перейти к п. 1.

Рассмотрим ещё одну задачу.

Пример 1.7. Пусть даны длины сторон треугольника a, b, c, и требуется определить вид треугольника остро-, прямо- или тупоугольный. Для решения данной задачи можно воспользоваться теоремой косинусов: если угол лежит против стороны a, то Используя знак косинуса, а так же тот факт, что наибольший угол лежит против наибольшей стороны можно предложить такой алгоритм:

1. Если a < b, поменять a и b между собой.

2. Если a < c, поменять a и c между собой.

3. Если a b + c, то ответ такого треугольника не существует.

4. Вычислить Глава Некоторые математические сведения В этой книге мы будем предполагать, что исполнителем является некоторое устройство, которое может оперировать некоторыми конечными математическими объектами: натуральными числами, конечными отношениями, конечными множествами и т.д. Мы считаем, что читатель знаком с понятиями натуральное число и множество и умеет выполнять действия с ними. В этой главе мы постараемся кратко описать более сложные понятия для тех, кто с ними не знаком. Подготовленные читатели могут пропустить эту часть, и вернуться к ней, если встретят какой-либо незнакомый термин.

§ 2.1. Алгебра и теория множеств Прежде всего определим термин функция (отображение).

Определение 2.1 (Функция, отображение). Пусть даны множества A и B. Будем называть f n - м е с т н о й ф у н к ц и е й, действующей из A в B, если f это множество упорядоченных наборов из n + 1 элементов вида (a1, a2,..., an, b), где a1,..., an A, b B, которое удовлетворяет следующему условию: для всяких a1,..., an A существует точно один элемент b B такой, что (a1,..., an, b) f.

Рассмотрим пример.

Пример 2.1. Пусть A = {a1, a2 }, B = {b1, b2 }. Тогда • g = {(a1, b1 ), (a1, b2 ), (a2, b1 )} не функция, потому что для элемента a1 A существуют два элемента из B: b1 и b2 такие, что (a1, b1 ) g и • h = {(a1, b2 )} не функция, потому что для элемента a2 A не существует элемента b B такого, что (a2, b) h.

Задача 2.1. Выпишите всевозможные одно и двухместные функции из множества A = {a1, a2 } в множество B = {b1, b2 }.

Определение 2.2 (Значение функции). З н а ч е н и е ф у н к ц и и f на элементах a1,..., an элемент b B такой, что (a1,..., an, b) f.

Значение функции f на a1,..., an записывается в виде f (a1,..., an ). Для одноместных функций мы часто будем опускать скобки и писать f a1 вместо f (a1 ).

Пример 2.2. Рассмотрим функцию f из примера 2.1. Для нее f a1 = f (a1 ) = b Ещё один способ записи значений функции: f : a b, что означает f a = b.

Определение 2.3 (Ограничение). Если A1 A и f n-местная функция, действующая из A в B, то функция f1 ограничение f функция, действующая из A1 в B и для любых элементов a1,..., an A выполнено f (a1,..., an ) = f1 (a1,..., an ).

Пример 2.3. Рассмотрим множества A, B и функцию f из примера 2.1. Пусть A1 = {a1 }. Тогда A1 A. Функция f1 = {(a1, b1 )} будет ограничением функции f на A1. Если A2 = {a2 }, то f2 = {(a2, b1 )} будет ограничением f на A2.

Таким образом, ограничение это функция, которая получается из исходной сужением области определения.

Задача 2.2. Выпишите всевозможные ограничения функций из задачи 2.1.

Замечание 2.1. Для двухместных функций вместо рассмотренной выше записи значения (п р е ф и к с н а я ф о р м а так как символ функции стоит до её аргументов), используется и н ф и к с н а я ф о р м а записи, когда символ функции ставится между аргументами. Например, мы пишем a + b вместо + (a, b).

Кроме этого, для некоторых функций используются и другие формы записи, например, с использованием индексов: xy, logx y и т.д.

Задача 2.3. Запишите формулы для нахождения корней квадратного уравнения в префиксной форме.

Определение 2.4 (Частичная функция). Пусть даны множества A и B. Говорим, что f n-местная частичная функция если f это множество упорядоченных наборов из n + 1 элементов вида (a1, a2,..., an, b), где a1,..., an A, а b B. Кроме того, для всяких a1,..., an A существует не более одного элемента b B такого, что Если для a1,..., an не существует элемента b B такого, что (a1,..., an, b) f, то говорим, что на элементах a1,..., an частичная функция f н е о п р е д е л е н а. Если такой элемент b B существует, то он называется з н а ч е н и е м f на элементах a1,..., an и обозначается f (a1,..., an ).

Пример 2.4. Рассмотрим те же множества: A = {a1, a2 } и B = {b1, b2 }. Пусть f = {(a1, b2 )}. Тогда f частичная функция. f (a1 ) определено и f (a1 ) = b2.

f (a2 ) не определено. Иногда последний факт записывают в виде f (a2 ) =.

Задача 2.4. Напишите всевозможные одноместные частичные функции из A = {a1, a2 } в B = {b1, b2 }.

Замечание 2.2. Пусть f и g некоторые частичные функции из A в B. Нам часто будет требоваться оборот вида: для всякого a A либо f (a) и g (a) одновременно неопределены, либо одновременно определены и при этом f (a) = g (a). Мы часто будем заменять это более кратким: f (a) = g (a) для всякого a A. Таким образом, если ни f (a), ни g (a) неопределено, то мы считаем, что f (a) = g (a). Это можно рассматривать, как некоторое обозначение.

Нам понадобится ещё одно определение, связанное с функциями.

Определение 2.5 (Композиция отображений). Пусть даны два (частичных) одноместных отображения: f : A B и g : B C. П р о и з в е д е н и е о т о б р а ж е н и й (композиция отображений) f и g (именно в таком порядке) это (частичное) отображение h : A C определённое следующим образом:

h = {(a, c) : a A, c C и существует b B такой, Очевидно, что h (a) определено тогда и только тогда, когда определены f (a) и g (f (a)), и в этом случае h (a) = g (f (a)). Композиция отображений f и g обозначается так: h = gf. Точно так же как и для чисел можно определить степень отображения:

натуральное число. Считаем, что f Пример 2.5. Пусть A = {a1, a2 }, B = {b1, b2 }, C = {c1, c2 }. Пусть f = {(a1, b1 ), (a2, b1 )} и g = {(b1, c2 )}. Тогда, очевидно, Заметим, что хотя g и является частичной функцией в результате произведения получилась функция не частичная.

Замечание 2.3. Иногда, чтобы подчеркнуть, что функция всюду определена, её называют т о т а л ь н о й.

Задача 2.5. Напишите всевозможные одноместные частичные функции из множества A = {a1, a2 } в A и их композиции.

Определение 2.6. Пусть A множество, n натуральное число. С помощью An мы обозначаем м н о ж е с т в о в с е в о з м о ж н ы х у п о р я д о ч е н н ы х н а б о р о в д л и н ы n, элементами которых являются элементы A (д е к а р т о в а с т е п е н ь A):

В частности, A0 = {()} для любого A. Если отождествить набор из одного элемента (a) с самим элементом a, то A1 = A. Множество A y = succ (x) ;

Определение 3.8 (Множество переменных). Определим множество выражений:

3) Var (o (e1,..., en )) = Var (e1 ) · · · Var (en ), если o n-местная операция, e1,..., en выражения.

Для теста T = e1 e2 :

Для программы мы определим два множества Var () и LVar () 1. = x = e;. Var () = {x} Var (e), LVar () = {x}.

Таким образом, Var (a) это множество переменных, которые встречаются в a, LVar () множество переменных программы, которые встречаются в левой части операторов присваивания.

Пример 3.6. Для программ из примера 3.5:

1. Var () = {x, y}, LVar () = {x, y}.

2. Var () = {x, y}, LVar () = {x, y}.

3. Var () = {x, y, z}, LVar () = {y, z}.

Некоторые переменные программы используются для того, чтобы передать входные данные, другие чтобы программа могла сообщить результат. Чтобы выделить эти переменные, мы будем записывать наши алгоритмы в специальном виде.

Определение 3.9 (Алгоритм). Будем называть а л г о р и т м о м следующую запись:

После Alg указывается имя, которое мы даём алгоритму (и м я а л г о р и т м а), после arg список разделенных запятыми переменных, в которых задаются начальные условия (в х о д н ы е п е р е м е н н ы е).

Каждая переменная может появляться в этом списке не более одного раза. Т е л о а л г о р и т м а (программу) A, мы будем обозначать A.

Среди всех переменных мы будем выделять одну выходную пер е м е н н у ю. Выходная переменная будет иметь такое же имя, как сам алгоритм. Выходная переменная не может являться частью выражения.

Следовательно, она может использоваться только в левой части оператора присваивания. Выходная переменная не может быть входной переменной.

Пример 3.7. Рассмотрим алгоритм на рис. 3.1. В данном случае, имя алгоритма M ax, входные переменные x и y. Тело алгоритма:

Результат получается в выходной переменной M ax. Заметим, что в данной программе нельзя использовать операторы вида или потому что в этом случае M ax было бы выражением, а выходную переменную в выражениях использовать запрещено.

Лемма 3.1 (О сбалансированности). В любой программе сумма количества слов if и while равна количеству слов end. В любом префиксе программы сумма количества слов if и while не меньше количества слов end.

Доказательство. Доказательство индукция по построению программы. Обозначим сумму количеств if и while в программе с помощью I (), количество end E ().

Базис индукции.

Если оператор присваивания, то I () = E () = 0.

Шаг индукции.

E () = E (1 ) + E (2 ). По индукционному предположению, I (1 ) = E (1 ) и I (2 ) = E (2 ). Следовательно, I () = E ().

Пусть теперь 3 префикс. Тогда или 3 начальный фрагмент 1 и для него утверждение выполняется по индукционному предположению, или 3 = 1 4, где предположению I (1 ) = E (1 ) и I (4 ) E (4 ). Следовательно, 1 программа. Тогда Если 3 префикс, то или 3 не содержит ничего из 1, тогда 3. Для полного ветвления и цикла доказательство аналогично.

Задача 3.1. Обоснуйте индукционный шаг для полного ветвления и цикла.

Задача 3.2. Верно ли, что в любом суффиксе любой программы количество слов end не меньше, чем суммарное количество if и while?

Лемма 3.2 (О суффиксе программы). Если = 1 2, и Доказательство. Индукция по построению.

Базис индукции.

Пусть = x = e;

оператор присваивания. Любая программа оканчивается точкой с запятой. Внутри точка с запятой не встречается. тоже программа, следовательно, она тоже оканчивается точкой с запятой.

Но это означает, что 1 =. Противоречие. Следовательно, такой случай невозможен.

Шаг индукции.

Так как 1 оканчивается точкой с запятой, то граница между 1 и проходит или внутри 3, или внутри 4. Рассмотрим первый случай:

сумма количеств if и while не меньше количества end. Но тогда в сумма количеств if и while больше количества end, что противоречит предыдущей лемме. Следовательно, такая ситуация невозможна.

Пусть теперь количеств if и while не меньше количества end. Так как 3 программа, то в неё эти величины равны. Но тогда в 1 сумма количеств if и while снова больше количества end. Итак, мы доказали, что случай, когда полное ветвление, невозможен.

2. Для неполного ветвления и цикла доказательства аналогичны.

3. Осталось рассмотреть только следование:

Если 1 = 3, то, очевидно, 2 = 4. Иначе, граница между 1 и проходит внутри 3 или 4.

Первый случай:

предположению 5 программа. Но тогда 2 = Второй случай:

индукционному предположению 5 программа. 5 2 = 4, 5 = 4.

По индукционному предположению 2 программа.

Задача 3.3. Обоснуйте индукционный шаг для неполного ветвления и цикла.

Следствие 3.1 (О двойном представлении программы). Пусть существует программа 5 такая, что = 3 5 2 или = 1 5 4.

Задача 3.4. Докажите следствие.

§ 3.2. Семантика До сих пор мы рассматривали только то, каким образом записывать программы, но не говорили о том, что эта запись означает. Теперь рассмотрим этот вопрос.

Семантика программ будет определяться через понятие состояния.

Определение 3.10 (Состояние). С о с т о я н и е частичное отображение множества переменных в предметную область. З н а ч е н и е п е р е м е н н о й x на состоянии x.

Пример 3.8. Например, если множество переменных то следующие отображения будут состояниями:

Для обозначения состояний мы будем использовать буквы,,,, возможно, с индексами.

Определение 3.11 (Состояние программы). Состояние называется Иначе говоря, всем переменным, которые встречаются в программе, состояние приписывает некоторые значения.

В дальнейшем, говоря о каких-либо состоянии и программе мы всегда считаем, что состояние.

Задача 3.5. Определите, будут ли состояния из примера 3.8 состояниями программ из примера 3.5.

Сначала определим семантику выражений.

Определение 3.12 (Значение выражения). Пусть e выражение, (обозначается (e)) называется элемент предметной области, который определяется следующим образом.

1. Если e = x, где x 2. Если e = c, где c Таким образом В частности, (succ (e)) = (e) + 1.

Рассмотрим пример.

Пример 3.9. Будем рассматривать состояния 1 и 2 из примера 3.8.

Задача 3.6. Найдите значения выражений succ (z) и succ (succ (z)) на состояниях из примера 3.8.

Следующий наш шаг определение семантики для тестов.

Определение 3.13 (Истинность теста). Пусть e1 и e2 выражения.

что (e1 ) = (e2 ). Истинность теста e1 < e2 на состоянии означает, что (e1 ) < (e2 ). Истинность теста T на состоянии записывается как отсутствие истинности.

ИСТИНА, если |= T, и ЛОЖЬ, в противном случае.

Пример 3.10. Рассмотрим те же состояния из примера 3.8. Тогда Задача 3.7. Используя переменные x и y, напишите тесты, которые были бы истинны на состоянии тогда и только тогда, когда Теперь мы готовы к тому, чтобы определить семантику нашего ЯП.

Пусть множество всевозможных состояний программы.

Для каждой программы мы определим некоторую одноместную частичную функцию, которая действует из в. Эту функцию мы и будем называть семантикой программы. Мы будем обозначать эту функцию так же как и программу.

Определение 3.14 (Семантика программы). С е м а н т и к а п р о г р а м м ы определяется индукцией по построению программы.

1. Пусть () =, где состояние, которое определяется следующим образом:

То есть, для всех переменных y, отличных от x, y = y, и x = (e).

определим () = 2 (1 ()). В этом определении кроется возможная неоднозначность, о которой мы скажем чуть позже.

5. Для цикла семантика определяется несколько более сложным образом. Пусть () определено, если существует натуральное число n и последоваn тельность состояний i i=0 такие, что в) i |= T тогда и только тогда, когда i < n, то есть i |= T, если В этом случае () = n. Если же такого числа n не существует, то () не определено.

Определение 3.15 (Зацикливание программы). Если () не определено для программы и состояния, то говорим, что программа на состоянии з а ц и к л и в а е т с я. В противном случае говорим, что Следствие 3.2 (Условие зацикливания). Пусть Тогда () не определено тогда и только тогда, когда в последовательности i i, построенной по правилам а) и б), для каждого i выполняется Задача 3.8. Докажите следствие.

Рассмотрим несколько примеров.

Пример 3.11. Пусть = {(x, 1), (y, 2), (z, 3)}.

1. Рассмотрим программу 2. Для программы 3. Для следования программ из пп. 1 и 2:

4. Для неполного ветвления 2) нахождение целой части частного двух чисел;

3) нахождение остатка от деления двух чисел;

4) вычисление факториала числа;

5) проверку, является ли число простым, и докажите их правильность Естественно, что можно написать много разных алгоритмов, которые будут вычислять одну и ту же (частичную) функцию.

Определение 3.18 (Эквивалентность алгоритмов). Алгоритмы A и B называются э к в и в а л е н т н ы м и, если они вычисляют одну и ту же (частичную) функцию:

Следствие 3.5. Алгоритмы A и B эквивалентны тогда и только тогда, когда они имеют одинаковое число аргументов n и для любых v n или Res (A, v) и Res (B, v) одновременно неопределены, или одновременно определены и при этом Задача 3.18. Верно ли следующее утверждение:

Если A () = B () для любого состояния, то A и B эквивалентны?

Верно ли обратное к нему утверждение? Докажите.

Пример 3.16. Рассмотрим следующие алгоритмы.

Эти три алгоритма вычисляют двухместные функции:

Таким образом, первые два эквивалентны, а третий не эквивалентен первым двум.

§ 3.3. Свойства структурных программ Изучим некоторые свойства структурированных программ.

Сначала продемонстрируем, что значение переменных, которые не встречаются в левой части оператора присваивания в программе, не изменяется.

Лемма 3.4 (О сохранении значения). Если программа, x переменная x LVar (),, состояния и () =, то x = x.

Доказательство. Индукция по построению программы.

Базис индукции.

иначе x LVar (). По определению семантики для оператора присваивания () = и при этом y = (e) и z = z для всех переменных Шаг индукции.

1. Пусть = 1 2. По индукции для любого состояния если 1 () =, то x = x. По индукции для любого состояния если 2 () =, то x = x. По определению семантики для следования имеем = По индукции для любого состояния В противном случае Следовательно, () (x) = x.

3. Для неполного ветвления доказательство аналогично.

Так как () определено, то существуют число n и последовательn ность состояний i i=0 такие, что По индукционному предположению 1 () (x) = x для любого состояния. Следовательно, и т.д. В конце концов получим, что n x = x, то есть, что x = x.

Задача 3.19. Обоснуйте шаг для неполного ветвления.

Следующее утверждение показывает, что для работы программы существенно значение только тех переменных, которые в ней используются.

Лемма 3.5 (О неиспользуемых переменных). Для любой программы и любого состояния Доказательство. Индукция по построению программы.

Задача 3.20. Докажите лемму.

Задача 3.21. Докажите эту же лемму с заменой множества Var () на произвольное множество переменных V такое, что Var () V.

Следствие 3.6 (О двух состояниях). Если Следствие 3.7 (О результате). Если () определено, то Задача 3.22. Докажите оба следствия.

Определение 3.19 (Замена переменных). Если a это выражение, тест или программа, x1,..., xn переменные, e1,..., en выражения, то с помощью мы будем обозначать результат з а м е н ы в a всех переменных xi на выражения ei.

Пример 3.17. Пусть e = succ (x). Тогда (e)x = succ (y).

Замену можно определить и индукцией по построению выражений, тестов и программ.

Определение 3.20 (Замена переменных). Для выражений:

Для теста T = d1 d2, где d1, d Задача 3.23. Дайте определение замены для программы индукцией по построению программы.

Доказательство. Индукция по построению выражения d или теста T.

Задача 3.24. Докажите лемму.

Замечание 3.2. Очевидно, для того, чтобы результат замены ()e1...en, где программа снова был программой, необходимо, чтобы ei было переменной для каждого xi LVar ().

Задача 3.25. Приведите пример, доказывающий необходимость этого условия.

Покажем, что это условие является одновременно и достаточным.

Лемма 3.7 (О результате замены). Пусть программа, x переменные, e выражения, причём если xi LVar (), то ei переменная.

Тогда ()x программа.

Доказательство. Индукция по построению программы.

Задача 3.26. Докажите лемму.

Заметим, что замена осуществляется не последовательно, а одновременно, то есть нельзя сначала заменить x1 на e1, затем x2 на e2 и так далее.

Пример 3.18. Пусть T = x < y. Тогда (T )xy = y < z, то есть мы заменили x на y, а y на z. Если бы мы осуществляли замену не одновременно, а последовательно, то получили бы следующее Как видим, результат получился другой.

Введём понятие замены переменной для состояний.

x1,..., xn, y1,..., yn переменные, то с помощью ()x1...yn мы обозначаем следующее множество :

Рассмотрим пример.

Пример 3.19. Пусть = {(x, 1), (y, 2)}. Тогда Замечание 3.3. Результат замены переменных в состоянии может не быть состоянием, так как может не быть отображением. Например, для состояния из предыдущего примера:

не является отображением.

Сформулируем достаточное условие для того, чтобы результат замены был состоянием.

Лемма 3.8. Если все переменные yi не входят в dom и все они попарно различны, то будет состоянием.

Задача 3.27. Докажите, лемму.

Задача 3.28. Приведите пример, доказывающий, что условие из леммы не является необходимым.

Отметим одно из очевидных свойств замены.

Лемма 3.9 (Обратимость замены). Пусть a выражение, тест, программа или состояние. x1,..., xn переменные. Предположим, что переменные y1,..., yn не встречаются в a и попарно различны. Тогда совпадает с a.

Доказательство. В самом деле, при замене (a)y1...yn вместо xi всюду появятся yi, а при обратной замене xi вместо yi. Поскольку yi в a отсутствуют, то в никаких других местах xi не возникнут.

Задача 3.29. Докажите лемму индукцией по определению выражений, тестов и программ.

Следующие три леммы дают основные свойства замены переменных в выражениях, тестах и программах.

Лемма 3.10 (Замена переменных в выражениях). Пусть переменные y не входят в выражение e и состояние. Тогда для любых переменных x.

Доказательство. Индукция по построению выражения e.

Базис индукции.

1. e = c, где c константа. Так как x не зависит от состояния. Значит того, z = ()y (z). Следовательно, 3. e = xi. Тогда (e)y = yi. Но по определению ()y имеем xi = ()x (yi ). Следовательно, Шаг индукции.

Пусть e = o (e1,..., em ), o для всех i = 1,..., m. По определению значения выражения Далее, ()x ((e)x ) = o(()x ((e1 )x ),..., ()x ((em )x )) = Лемма 3.11 (Замена переменных в тестах). Пусть переменные y не входят в состояние и тест T. Тогда для любых переменных x.

Доказательство. По определению если T = e1 e2, e1, e Согласно лемме 3.10 имеем:

где i = 1, 2. Поэтому Значит Лемма 3.12 (Замена переменных в программах). Пусть переменные y не входят в состояние и программу. Тогда для любых переменных x.

Доказательство. Индукция по построению программы.

Базис индукции.

где z переменная, e выражение. Возможно два случая:

1. z = x1,..., z = xn. Тогда ()y = z = (e)y ; согласно лемме 3. Пусть () =. По определению семантики присваивания u = u, По определению семантики присваивания u = ()y u, если u = z, и Итак, z = z. Для любой другой переменной u имеем Поскольку z отличается от y1,..., yn по условию леммы, то z = (u)y.

Значит, Это и означает, что = ( )y.

2. z = xi. Тогда ()x = yi = (e)x. Согласно лемме 3. Пусть () =. По определению семантики присваивания u = u, По определению семантики присваивания u = ()x u, если u = yi, и Итак, yi = xi. Для любой другой переменной u имеем Следовательно, = ( )x.

Шаг индукции.

1. Пусть = 1 2. Тогда, очевидно, По определению семантики следования: () = 2 (1 ()) и Пусть 1 () =. По индукционному предположению По определению семантики для полного ветвления имеем:

Заменяя в первом равенстве x на y, получим По лемме 3.11, По индукционному предположению Поэтому получаем, что ( ())x = ()x ()x.

3. Для неполного ветвления доказывается аналогично.

По индукционному предположению для любого состояния имеет место:

Пусть i последовательность состояний для программы на, а Базис индукции: i = 0. Тогда Индукционный шаг: пусть для i доказано. Тогда Получаем, что Итак, мы доказали, что i y = i для всех i. Пусть () определено.

Тогда существует n такое, что i |= T тогда и только тогда, когда i < n и при этом () = n. Следовательно, по лемме 3. Согласно только что доказанному, это означает, что () определено Произведя ещё раз замену x на y, получим Задача 3.30. Обоснуйте индукционный шаг для неполного ветвления.

Следствие 3.8. Пусть дан алгоритм:

Попарно различные переменные y и B не встречаются в A и в x. Тогда алгоритм эквивалентен исходному.

Задача 3.31. Докажите следствие.

§ 3.4. Простые программы В этом параграфе мы докажем, что каждая программа эквивалентна программе специального вида.

Определение 3.22 (Простая программа). Программа называется п р о с т о й, если каждый оператор присваивания имеет один из трёх видов:

где x, y1,..., yn переменные, c константа, o операция. Операторы присваивания и тесты такого вида мы будем называть п р о с т ы м и.

Пример 3.20. Программы из примеров 3.13 и 3.14 являются простыми, а из примера 3.15 не является. Например, в программе Euclid есть тест u = succ (0), который в простой программе недопустим.

Лемма 3.13 (О разложении выражения). Пусть d выражение, y переменная,, состояния, = (y = d; ) (). Тогда для любого выражения Доказательство. Очевидно, что отличается от только тем, что y = (d). Индукция по построению выражения e.

Базис индукции.

Шаг индукции.

Пусть для выражений e1,..., en лемма доказана и e = o (e1,..., en ), где o операция.

Следствие 3.9 (О разложении теста). Пусть d выражение, y переменная,, состояния, = (y = d; ) (). Тогда для любого теста T Задача 3.32. Докажите следствие.

Напомним ещё раз, что с помощью V мы обозначаем множество всевозможных переменных, которые могут использоваться в программах.

Следствие 3.10 (Упрощение присваиваний). Пусть x, y переменные, d, e выражения, y V. Тогда для любого состояния Доказательство. Очевидно, что достаточно доказать, что () (x) = 1 () (x) так как остальные переменные из V не изменяются ни в ни в 1. Пусть = (y = d; ) (), тогда 1 () = (x = e; ) ( ).

Лемма 3.14 (Упрощение полного ветвления). Пусть T программы, y переменная, d выражение.

Тогда для любого состояния выполнено Доказательство. Пусть T = e1 e2. Пусть = (y = d; ) ().

Так как Если |= (T )d, то |= T, и мы получаем, что () = () и 1 ( ) = ( ). Если |= (T )d, то |= T, и, следовательно, () = () и 1 ( ) = ( ). И в том, и в другом случае Лемма 3.15 (Упрощение неполного ветвления). Пусть T программа, y переменная, d выражение.

Тогда для любого состояния выполнено Задача 3.33. Докажите лемму.

переменная, d выражение.

Тогда для любого состояния выполнено Доказательство. Пусть = (y = d; ) (). Рассмотрим последовательность состояний для на : 0 = и i+1 = i. Рассмотрим последовательность состояний для 2 на : 0 = и i+1 = (y = d; ) i.

Индукцией по i докажем, что (y = d; ) i = i. Из этого, в частности, следует, что Базис индукции.

Шаг индукции.

Пусть для i доказано. Тогда Далее, Кроме того, Так как d содержит только переменные из V, то То есть, Это и означает, что i+1 = (y = d; ) i+1. Из этого следует, что Пусть () определено. Тогда существует m такое, что Следовательно, Следовательно, 2 ( ) = m и Обратно, пусть 1 ( ) определено. Тогда существует m такое, что Получаем, что Это означает, () = m. Как и в предыдущем рассуждении Теорема 3.2 (О простой программе). Для всякой программы существует простая программа такая, что для любого состояния.

Доказательство. Для каждого a выражения, теста или программы определим некоторое число в е с этого объекта w (a).

Для выражений:

Для программ:

Здесь 1, 2 программы, T тест.

По индукции легко доказать, что x переменные;

Теперь индукцией по сложности программы мы докажем, что если w () > 0, то существует программа 1 такая, что w (1 ) < w () и для всех состояний.

Базис индукции.

= x = e; так как w () 1, то w (e) 2. Следовательно, e = o (e1,..., en ) и w (ei ) 1 для некоторого i. Возьмём новую переменную y, которая не встречается в, и построим Следовательно, Из следствия 3.10 следует, что Шаг индукции.

1. Если = 3 4, то w (3 ) > 0 или w (4 ) > 0. Рассмотрим первый случай. По индукционному предположению существует программа 31 :

Аналогично рассматривается и второй случай.

Тогда w (T ) > 0, w (3 ) > 0 или w (4 ) > 0. В последних двух случаях доказательство аналогично предыдущему. Если w (T ) > 0, T = e1 e2, то w (e1 ) > 0 или w (e2 ) > 0. Пусть, например, w (e1 ) > 0. Возьмём новую переменную y и построим 1 :

3. Для неполного ветвления аналогично.

Если w (3 ) > 0, то утверждение следует из индукционного предположения. Пусть w (3 ) = 0. Это означает, что 2w(T ) > 1 и w (T ) > 0.

T = e1 e2 и w (e1 ) > 0 или w (e2 ) > 0. Пусть, например, w (e1 ) > 0.

Возьмём новую переменную y и построим 1 :

По лемме 3. По определению веса Докажем, что Индукция по w (e1 ).

Базис: w (e1 ) = 1.

Шаг: пусть для w (e1 ) = u доказано. Рассмотрим w (e1 ) = u + 1:

По индукционному предположению получаем 2u + 2w(e2 ) < 2 + 2u+w(e2 ) < 2u+w(e2 ) + 2u+w(e2 ) = 2u+1+w(e2 ).

Следовательно, w (1 ) < w ().

Итак, мы доказали, что если w () > 0, то существует программа такая, что w (1 ) < w () и для всех состояний.

Пусть дана исходная программа. Построим последовательность программ (i )i : 0 =, i+1 получается из i с помощью описанной выше процедуры, если w (i ) > 0. Последовательность (w (i ))i будет убывающей цепью натуральных чисел, следовательно, она не может быть бесконечной. С другой стороны, для последнего элемента n не может быть w (n ) > 0. Следовательно, w (n ) = 0 и n простая программа. Так как для всех i, то Задача 3.34. Докажите все пропущенные места в доказательстве теоремы.

Следствие 3.11. Каждый алгоритм эквивалентен некоторому алгоритму, тело которого является простой программой.

Задача 3.35. Докажите следствие.

Задача 3.36. Преобразуйте тело алгоритма Euclid (пример 3.15) в простую программу.

§ 3.5. Подстановка Мы рассмотрели язык программирования с очень ограниченным набором конструкций. В реальных ЯП набор операций гораздо шире. В частности, имеется полный набор математических функций. Основная задача этого параграфа доказать, что подобное обогащение ЯП не приводит в увеличению его возможностей.

Теорема 3.3 (Теорема о подстановке). Пусть O алгоритм на языке программирования A, который вычисляет некоторую n-местную функцию o.

Пусть язык программирования B получен из языка программирования A добавлением новой операции o, означающей ту же самую функцию. Тогда для каждого алгоритма на B существует эквивалентный ему алгоритм на Доказательство. Пусть алгоритм, вычисляющий O имеет вид:

Рассмотрим произвольный алгоритм C на ЯП B:

Согласно теореме о простой программе, можно считать, что программа B является простой. В частности, это означает, что операция o встречается только в операторах присваивания вида Заменим каждую переменную v (кроме выходной переменной O) в программе O на новую переменную v. Согласно лемме о замене переменных, алгоритм будет вычислять ту же самую функцию.

Теперь построим программу следующим образом:

Здесь y1,..., yn это новые попарно различные переменные, z1,..., zm все переменные O, которые не являются аргументами. Тогда алгоритм эквивалентен алгоритму O. В самом деле, рассмотрим результаты вызовов = (O, a) и = (O, a). В результате выполнения первых n + m строк получим состояние такое, что xi = yi = xi. O ( ) опреO делено тогда и только тогда когда ( ) определено и в этом случае O ( ) (O) = O ( ) (O). Итак, O действительно эквивалентен O.

Теперь заменим в программе B каждый оператор присваивания вида Назовём полученную программу A. Очевидно, что операция o в A не встречается, то есть, A программа на языке программирования A.

Осталось только доказать, что для всякого начального состояния выполнено Индукцией по построению программы B докажем следующее утверждение: для всяких состояний и таких, что имеет место Базис индукции.

Рассмотрим произвольный оператор присваивания. Как мы уже сказали выше, возможна одна из четырех ситуаций:

так как переменная x изменяется одинаково и в A, и в B.

4. B = x = o (z1,..., zn ) ; x, z1,..., zn переменные. Тогда A = (O ) x z1...zn. Согласно лемме о замене переменных Для любых остальных переменных из B программа ( ) O y1...zn не изменяет значение, так как они не входят в неё в левой части оператора присваивания. Это и означает, что Шаг индукции.

Возможны четыре варианта.

1. B = B B. Тогда A = A A и по индукционному предположению Пусть B () = 1 и A ( ) = 1. По индукционному предположению Но по определению семантики следования Следовательно, и по индукционному предположению Заметим, что поскольку тест T состоит только из переменных из Var B, то |= T тогда и только тогда, когда |= T. По определению семантики ветвления имеем:

3. Для неполного ветвления аналогично.

и по индукционному предположению для любых состояний и таких, имеет место Рассмотрим последовательности состояний для B и для A :

Покажем, что для всех i. Для i = 0 это следует из условия. Пусть для i доказано.

Так как тест T содержит только переменные из Var B, то i |= T тогда и только тогда, когда i |= T. Следовательно, последовательность i i конечна тогда и только тогда, когда последовательность i i конечна, и m последний элемент тогда и только тогда, когда последний элемент. То есть, если A ( ) определено, то B () определено, и И, если B () определено, то A ( ) определено, и Построим алгоритм на ЯП A:

Поскольку выходная переменная C принадлежит множеству Var B, то для любого вызова = (C, v) Оба алгоритма вычисляют одну и ту же функцию, то есть эквивалентны.

Задача 3.37. Обоснуйте индукционный шаг для неполного ветвления.

Смысл доказанной теоремы состоит в том, что если мы расширяем ЯП операциями, которые могут быть вычислены программами на этом языке, то множество функций, которые вычисляются программами этого языка не изменяется. Например, мы уже видели, что на нашем ЯП можно написать сложение и вычитание. Следовательно, если мы добавим операции + и к нашему языку, то его выразительная сила не увеличится. Точно так же, если мы напишем программы, которые будут вычислять умножение, деление, логарифм и т.д., то мы можем утверждать, что расширение ЯП за счёт этих операций не позволяет написать ничего принципиально нового.

Задача 3.38. Напишите алгоритмы для сложения и вычитания натуральных чисел. Напишите алгоритмы для умножения и деления с использованием операций + и. Воспользуйтесь методом, предложенным в теореме, чтобы построить алгоритмы для умножения и деления без использования + и.

Задача 3.39. Напишите алгоритмы для возведения чисел в степень и вычисления факториала, используя операцию умножения. Воспользуйтесь методом, предложенным в теореме, чтобы построить алгоритмы для этих операций без использования. Используйте алгоритмы, полученные при решении предыдущей задачи.

Глава Программы с метками § 4.1. Синтаксис До сих пор мы рассматривали структурированные программы. Теперь мы рассмотрим иной подход к написанию программ. Исторически он является более ранним, однако, в настоящий момент его считают морально устаревшим, и он используется только в старых ЯП (таких как Фортран, Бейсик, Фокал) и в ЯП низкого уровня. Однако, основная конструкция этого подхода (переход к метке) остаётся практически во всех современных языках программирования.

Определение 4.1 (Метка). М е т к а это имя, служащее для обозначения операторов программы.

Синтаксис программ с метками следующий:

Определение 4.2 (Программа с метками). П р о г р а м м а с м е т ками последовательность операторов одного из двух следующих видов:

п е р е х о д а. В программе не допускаются два оператора с одинаковыми метками оператора. Кроме того, мы для удобства будем предполагать, что имена меток не совпадают ни с именами переменных, ни с константами, ни с другими, используемыми в программе словами (if, arg,... ).

Через Start (), где программа с метками, мы будем обозначать Если метка перехода не является меткой никакого оператора, то это Пример 4.1. Рассмотрим пример (рис. 4.1). В данном примере Start (M in ) = 1. 4 заключительная метка.

§ 4.2. Семантика Как и раньше, состояние частичное отображение множества переменных V в предметную область.

Определение 4.3 (Расширенное состояние). Р а с ш и р е н н о е с о с т о я н и е программы с метками пара (; ), где состояние Пример 4.2. Рассмотрим программу из примера 4.1. Следующие объекты будут расширенными состояниями:

Определение 4.4 (Семантика программы с метками). Сначала для всякой программы определим частичное отображение E E. (, ) определено и (, ) = (, ), если существует натуральное число n и последовательность расширенных состояний i, i i=0 такие, что 3) в программе есть операторы с метками 0,..., n1 ;

4) в программе нет оператора с меткой n (то есть n заключительная метка);

5) если для i < n в имеется оператор вида 6) если для i < n в имеется оператор вида () определено и () =, если для некоторой метки (необходимо заключительной).

Следствие 4.1. Для каждой программы с метками существует программа с метками, которая содержит не более одной заключительной метки, и () = () для всякого состояния.

Задача 4.1. Докажите следствие.

Как и в случае структурированных программ если () не определено, то говорим, что на зацикливается.

Следствие 4.2 (Условие зацикливания). Пусть программа с метками, (, ) расширенное состояние. Тогда (, ) определено тогда и только тогда, когда последовательность расширенных состояний, построенная с помощью пунктов 1, 5 и 6 определения семантики программ с метками, является конечной.

Следующее следствие доказывается аналогично доказанному ранее следствию о зацикливании структурированных программ.

Следствие 4.3 (Условие зацикливания). Если в последовательности расширенных состояний, построенной с помощью пунктов 1, 5 и 6, есть два одинаковых, то (, ) неопределено.

Задача 4.2. Докажите оба следствия.

{(x, 1), (y, 2), (z, 3)}. Тогда Последовательность: (1, 3), (3, 4).

Последовательность: (1, 2), (2, 4).

(1, 1) = (2, 4), потому что 1 |= x < y. Таким образом, (1 ) = 2.

Определение 4.5 (Числа Фибоначчи). Ч и с л а Ф и б о н а ч ч и Fi, i определяются по индукции:

при i 1. Первые числа Фибоначчи:

Задача 4.3. Найдите все числа Фибоначчи, которые меньше 1000.

Пример 4.4. На рис. 4.2 изображён алгоритм для вычисления числа Фибоначчи по его номеру.

Задача 4.4. Постройте последовательность расширенных состояний при вызове (F ib, 3).

Докажем, что алгоритм F ib и в самом деле вычисляет числа Фибоначчи. Пусть начальное состояние и i = i0.

Если i0 < 2, то последовательность расширенных состояний содержит 3 элемента: (, 1), (, 2), (, 100), где совпадает с, кроме того, что (F ib) = i = i0. Но Fn = n для n < 2, следовательно, F ib () (F ib) = Fi0.

Допустим, что i0 2. Первые пять элементов последовательности расширенных состояний таковы: (, 1), (, 3), (3, 4), (4, 5), (5, 6), где:

– 3 = кроме того, что 3 j = 1;

– 4 = 3 кроме того, что 4 f = 1;

– 5 = 4 кроме того, что 5 p = 0.

Утверждение 4.1. В последовательности расширенных состояний после любого элемента вида k, 6 имеется элемент вида l, 14. Если взять наименьшее из таких l, то Доказательство. После k, 6 должны идти k+1, 7 и k+2, 8 такие, что k+1 t = 0 и k+2 s = k f.

Затем должна идти последовательность из 0 или более троек вида таких, что Так как k+30+2 t = 0 и k+30+2 s = f, то, очевидно, Очевидно, что количество этих троек должно быть равно k p, так как то есть тест t < p не выполняется.

Возьмем l = k + 3 k p + 6. Тогда после этой последовательности троек будут идти Таким образом, мы действительно выбрали наименьшее из l больших k, для которых метка 14. Рассмотрим l :

Следствие 4.4. Для любого расширенного состояний вида k, 6 такого, что k f = Fk j и k p = Fk j1, существует расширенное состояние l, Доказательство. Выберем l из утверждения.

Утверждение 4.2. Алгоритм Fib вычисляет Fi0.

Доказательство. Покажем следующее: для всякого 2 n i0 в последовательности расширенных состояний существует элемент ln, такой, что Базис индукции.

n = 2. Мы уже видели, что Согласно следствию, существует номер l2 такой, что Шаг индукции.

Пусть для n доказано и n < i0. Тогда Значит, следом за ln, 14 идет ln, 6 и для него выполнены все условия следствия. Следовательно, существует ln+1 такой, что То есть утверждение выполняется и для n + 1.

Если n = i0, то после ln, 14 идут (, 15) и (, 100). Следовательно, Если сравнить это доказательство с доказательствами для структурированных программ, то нельзя не заметить, что оно является значительно более сложным. Это связано с тем, что программы с метками не имеют ясно выраженных логических частей. В случае структурированной программы мы доказывали её правильность двигаясь от отдельных операторов и постепенно рассматривая всё более широкие блоки. Каждый такой шаг делался согласно определению семантики для соответствующей конструкции. В случае же программы с метками такой метод не работает, мы должны рассматривать всю программу сразу, целиком. Это затрудняет понимание того, как работает программа и доказательство её правильности. Именно то обстоятельство, что программы с метками не имеют чётко выраженных логических блоков, и привело к тому, что они были вытеснены в значительной мере структурированными ЯП.

Задача 4.5. Напишите алгоритм, который подсчитывает сумму цифр заданного числа, и докажите его правильность. Используйте операции +,,, / целочисленное деление.

§ 4.3. Построение программ с метками Мы рассмотрели два ЯП структурированный и с метками. Мы докажем, что оба этих языка эквивалентны, то есть функции, которые можно вычислить с помощью структурированных программ, можно вычислить и с помощью программ с метками, и наоборот.

Мы ранее доказывали леммы о замене переменных, которые утверждали, что если одни переменные заменить другими, то получится эквивалентная программа. Докажем аналогичное утверждение и для меток.

Замена в программе метки на определяется точно так же как замена одной переменной на другую. Результат такой замены обозначается аналогично:

То есть () получается из заменой всюду метки на метку.

Замечание 4.1. Результат замены () может не быть программой с метками так как в результате замены в программе могут оказаться две одинаковых метки оператора. Однако, если метка не является меткой оператора программы, то () программа с метками.

Лемма 4.1 (О замене метки). Пусть метка не встречается в программе. Тогда для любого состояния и для любой метки имеет место () = () ().

Доказательство. Докажем следующее утверждение: если () () определено, то () определено и () () = ().

Рассмотрим последовательность расширенных состояний j, j j для () (). Так как () () определено, то последовательность расширенных состояний, j j является конечной. Пусть ( m, m ) (). Определим Докажем, что последовательность расширенных состояний j, µj j=0 является последовательностью расширенных состояний при работе на.

Используем индукцию по длине последовательности.

Базис индукции.

i = 0. Что 0 является начальным состоянием очевидно. С метками возможны две ситуации:

1. 0 = и µ0 = 0. Так как 0 = Start (), то µ0 = 0 должна быть и начальной меткой программы, потому что мы заменяем только 2. 0 =. Тогда µ0 =, потому что метки в программе отсутствуют, они могут появиться в () только в результате замены. Значит, Это доказывает базис утверждения.

Шаг индукции.

Пусть для i доказано, что последовательность расширенных состояний j, µj j=0 является правильной и i < m. Рассмотрим i + 1. Возможны следующие варианты:

1. В программе () есть оператор вида Тогда в программе есть оператор i+1 отличается от i только тем, что i+1 x = i (e). Это относится и к (), и к. Следующей меткой для должна быть µi+1. Значит, i+1, µi+1 очередной элемент.

2. В программе () есть оператор и i |= T. Тогда в программе есть оператор 3. В программе () есть оператор и i |= T. Тогда в программе есть оператор Следовательно, за элементом i, µi должен идти i+1, µi+1, где Рассмотрим µm. Если в существует метка оператора µm, то в программе () должна быть метка оператора m. Но последнее не выполняется, так как m заключительная метка. Значит, µm является заключительной меткой программы. Таким образом, последовательность расширенных состояний j, µj j заканчивается элементом ( m, µm ). То есть () определено и Это доказывает наше утверждение.

Доказать утверждение в обратную сторону легко, если заметить, что = () и при этом метка не встречается в программе (). Согласно только что доказанному, из этого следует: если () () определено, то () () определено и () () = () (). А так как = (), то это и означает следование в обратную сторону.

Определение 4.6 (Эффективное построение). Мы скажем, что по объекту A из некоторого класса можно э ф ф е к т и в н о построить объект B, если существует алгоритм, который выполняет такое построение для любого объекта A из этого класса.

Пример 4.5. Например, замена b = (a)x может быть эффективно построена, потому что существует алгоритм, выполняющий такую замену для любого слова a. В общих словах алгоритм замены следующий: идти по слову a и копировать все символы в слово b, кроме символа x, вместо которого копируется y.

Замечание 4.2. Не всякое построение эффективно. Например, для всякого алгоритма A существует алгоритм MA, который имеет минимальную длину среди всех эквивалентных A алгоритмов. Однако построение MA по A неэффективно.

Не существует алгоритма, который выполнял бы это построение для любого алгоритма A.

Теорема 4.1 (О построении программы с метками). По всякой структурной программе S можно эффективно построить программу с метками L такую, что S () = L () для любого состояния.

Доказательство. Докажем теорему индукцией по построению S.

Базис индукции.

Пусть где x переменная, e выражение. Возьмём Очевидно, что для всякого состояния имеет место S () = L ().

Шаг индукции.

Возможны четыре варианта.

1. S = S S. По индукции для S и для S существуют программы L и L. Выберем для каждой метки из программы L метку, которая не встречалась бы ни в L ни в L. Построим L, заменив в L все метки на. Согласно лемме о замене метки L ( ) = L ( ) начальная метка L. Пусть L = L. Согласно лемме о замене метки L () = L () для всякого состояния. Построим L = L L.

Докажем, что искомая программа.

Пусть S () определено. Тогда S () определено. Пусть S () =. Согласно индукционному предположению L () = L () =.

Пусть S ( ) =. Согласно индукционному предположению L ( ) = 2 ( ) =. Рассмотрим последовательность расширенных состояний для L (). Так как L () определено, то последовательность расширенных состояний i, i i для L () является конечной. Пусть заключительная метка программы L. Заметим, что ( m, m ) = (, ) является первым расширенным состоянием для L ( ). Так как L ( ) определено, то эта последовательность должна быть конечной:

i, i i=m. Очевидно, что n =. Рассмотрим последовательность i, i i=0. Эта последовательность является последовательностью расширенных состояний для L (). Так как заключительная метка программы L совпадает с заключительной меткой программы L, то Пусть теперь L () определено. Рассмотрим последовательность расn ширенных состояний i, i i=0. Тогда метка n должна быть заключительной меткой программы L. Но единственной заключительной меткой программы L является заключительная метка программы L.

му что сама заключительная метка программы L в программе L встречаться не может, потому что единственная метка из L, которая встречается в L, это. Но является начальной меткой L, то есть меткой оператора. А заключительная метка не может являться меткой оператора. Итак, метка 0 является меткой оператора программы L, а метка n1 меткой оператора L. Следовательно, в последовательности расширенных состояний должен быть элемент ( m, m ) метка оператора программы L. Но единственной меткой, которая удовлетворяет этим условиям является.

Итак, рассмотрим последовательность i, i i=0. Тогда она является последовательностью расширенных состояний для L () и m = заключительная метка 1. Значит, 1 () =. По индукционному предположению Теперь рассмотрим последовательность i, i i=m. Тогда, она является последовательностью расширенных состояний для L ( m ). Поэтому L ( m ) = n. По индукционному предположению Получаем, что таким образом, S () определено и S () = L ().

По индукционному предположению для S и для S существуют программы L и L. Построим L так же, как и в предыдущем случае.

встречается ни в L ни в L. Возьмём Возможны два случая: либо |= T, либо |= T. Рассмотрим первый Пусть S () определено. По индукционному предположению, L () определено и L () = S () =. Значит, существует последовательn ность расширенных состояний i, i i=0, для которой 0 =, 0 = Start L, n = и n =. Рассмотрим последовательность расширенных состояний, полученную из предыдущей добавлением в начало расширенного состояния (, ): (, ), i, i i=0. Легко показать, что последовательность расширенных состояний для L (). Кроме того, заключительная метка L, поэтому L () = n = = S ().

Пусть теперь L () определено. Следовательно, последовательность расширенных состояний i, i i для L () является конечной. Предположим, она содержит n + 1 элемент. Очевидно, что 1 = Start L. Последовательность i, i i=1 является последовательностью расширенных состояний для L (), так как метки операторов L в L не встречаются. Тогда последовательность является последовательностью расширенных состояний для L (). По индукционному предположению S () определено и S () = n. То Второй случай, когда |= T рассматривается аналогично, только вместо S, L, L рассматриваются S, L, L.

3. Для неполного ветвления построение аналогично.

и для S существует программа с метками L. Пусть начальная метка L, заключительная, а новая метка. Возьмём Пусть S () определено. Это означает, что существует последовательin ность состояний S i=0 такая, что Рассмотрим последовательность расширенных состояний L, j для L (). Пусть ji i-ый элемент, для которого ji =. В частности, j0 = 0, так как 0 =. Индукцией по i докажем, что Li = S.

Базис индукции.

Шаг индукции.

Пусть доказано, что Li = S и i < n. Это означает, что S |= T и Li |= T. Это означает, что вслед за расширенным состоянием Li, должно идти расширенное состояние Li,. Это является начальным расширенным состоянием для L Li. Из этого следует, что Это означает, что последовательность расширенных состояний для L Li является конечной, и ее последним элементом является S,. Заметим, что в этой последовательности метка встречается только один раз в конце.

Следовательно, в последовательности расширенных состояний для L () после Li, должно встретиться состояние S, и это первое место после ji, где меткой является. Очевидно, что ji+ номер этого расширенного состояния, и Li+1 = S.

Итак, мы доказали, что Li = S. Значит, То есть, Ln |= T. Значит, после расширенного состояния Ln, будет идти Ln,. Так как является заключительной меткой, то L () = ных состояний L, i i является конечной. Пусть (L, n ) последний элемент. Пусть ji i-ый элемент, в котором метка. Очевидно, что j0 = 0. Кроме того, n1 =, потому что метка встречается в L только в одном месте. Пусть n 1 = jm для некоторого m. Кроме того, Li |= T тогда и только тогда, когда i < m.

Рассмотрим последовательность состояний S для S (). Аналогично доказывается, что L = S. То есть, Это означает, что Задача 4.6. Завершите доказательство корректности построения для полного ветвления.

Задача 4.7. Покажите, как построить программу с метками для неполного ветвления, и докажите правильность построения.

Задача 4.8. Докажите, что если исходная структурная программа была простой, то с методом, предложенным в теореме, будет построена простая программа с метками.

Итак, мы научились по любой структурированной программе строить эквивалентную ей программу с метками.

Задача 4.9. Пользуясь методом, предложенным в теореме, постройте программы с метками по ранее построенным программам 1) для сложения чисел;

2) для вычитания чисел;

3) для умножения чисел;

4) для определения простоты числа.

§ 4.4. Построение структурированных В этом параграфе мы решаем обратную задачу по программе с метками построим эквивалентную структурированную программу.

Теорема 4.2 (Структуризация). По всякой программе с метками L можно эффективно построить структурную программу S такую, что Var L Var S и для любого состояния программы S. Программу S можно выбрать таким образом, чтобы она содержала только один оператор цикла.

Доказательство. Итак, пусть дана программа с метками L. Без ограничения общности можно предполагать, что все её метки являются натуральными числами большими 0. Это означает, что программа L имеет Каждый из операторов ok имеет один из видов:

2) ok = k if Tk then k else k Пусть w и y каждого оператора ok одного из этих видов определим структурную программу (ok ) следующим образом:

Здесь через n мы обозначаем следующее выражение:

Очевидно, что (n) = n для любого состояния. Построим программу S следующим образом:

Докажем, что S () определено тогда и только тогда, когда L () определено, для любого состояния и в этом случае По определению семантики программ с метками мы должны рассматi ривать последовательность расширенных состояний L, i i, для которой Теперь рассмотрим S. Через S обозначим состояние, которое получается из применением первых двух операторов присваивания программы S :

Очевидно, что поскольку никакие переменные из программы L эти операторы не изменяют. Для оператора цикла мы должны строить последовательность состояний S i такую, что S = S и S = S S.

Индукцией по i докажем следующее утверждение:

2) S w = 0, если метка i1 не является заключительной;

Базис индукции.

Для i = 0 утверждение, очевидно, выполнено, так как S = S, а свойства S мы описали выше.

Шаг индукции.

Пусть для i утверждение доказано. Тогда рассмотрим S S = S. По определению семантики следования имеем:

Пусть Тогда i отличается от S только тем, что i w = 1. Пусть i = ji.

Рассмотрим (ok ) S при k < ji. Очевидно, что потому что i w = 1, но, в то же время, потому что а в программе с метками нет двух одинаковых меток операторов. Из определения семантики для неполного ветвления получаем, что (ok ) i = Рассмотрим (ok ) i при k = ji. Тогда так как Пусть S = (ok ) i.

1. Если то по определению семантики присваивания и следования и по определению семантики программы с метками получим, что Для всех остальных переменных z будем иметь 2. Пусть теперь Теперь рассмотрим (ok ) S при k > ji. Очевидно, что поскольку S w = 0. Значит, (ok ) S = S.

Итак, мы доказали, что S = S S = S. Но при рассмотрении случая k = ji мы показали, что S удовлетворяет условиям утверждения.

Следовательно, утверждение доказано для i + 1 и, по индукции, для всех i, для которых метка i1 не заключительная.

стояний L, i i конечна. Предположим, что (L, n ) её последний элемент. Тогда n должна быть заключительной меткой. То есть, n = k для k = 1,..., m. Это означает, что (ok ) i = i для k = 1,..., m. Но так как n w = 1. Это означает, что S () = S. Но Пусть теперь S () определено. Тогда последовательность S нечна. Пусть S последний элемент. Это означает, что Так как S = S S k = S y для всякого k = 1,..., m. Согласно утверждению, S y = n1. Это означает, что метка n1 является заключительной и L () = L. Далее, очевидно, что Следовательно, Задача 4.10. Структуризируйте программы M in с рис. 4.1 и F ib с рис. 4. методом, предложенным в теореме.

Задача 4.11. Модифицируйте доказательство теоремы так, что если исходная программа с метками является простой, то построенная структурная программа тоже будет простой.

Итак, мы доказали, что структурированные программы и программы с метками вычисляют одни и те же функции. Выведем следствие.

Следствие 4.5 (Теорема о цикле). Для всякой структурной программы существует структурная программа 1, которая содержит только один оператор цикла и для любого состояния программы 1.

Доказательство. Для существует программа с метками 2 такая, что для любого состояния. По теореме о структуризации существует структурная программа 1, которая содержит один оператор цикла и для любого состояния программы 1. Следовательно, для любого состояния.

Задача 4.12. Сформулируйте теорему о подстановке для программ с метками и, используя теоремы о построении программ с метками и о структуризации, докажите её.

Задача 4.13. Сформулируйте и докажите теорему о простой программе для программ с метками.

§ 4.5. Блок-схемы Один из популярных ранее методов представления алгоритмов блоксхемы. Он и сейчас используется для иллюстрации несложных последовательностей инструкций. Как мы покажем, понятие блок-схемы полностью эквивалентно понятию программы с метками.

6. ОП : 5. Формула истинна. Следовательно, 7. НВ : 6. Формула истинна. Следовательно, 120 Глава 5. Доказательство корректности структурированных программ Задача 5.7. Докажите, что программа на рис. 5.1 находит среднее из трёх чисел.

Итак, мы научились доказывать корректность программ, не содержащих циклов. Прежде чем переходить к циклам дадим несколько определений.

Определение 5.9 (Инвариант программы). Условие (частичн ы й ) и н в а р и а н т п р о г р а м м ы, если тройка {} {} является полностью (частично) корректной.

Определение 5.10 (Инвариант цикла). Условие называется ( ч а стичным) инвариантом цикла если тройка { T } {} полностью (частично) корректна, Очевидно, что каждый инвариант программы (цикла) является и частичным инвариантом программы (цикла). Обратное, естественно, неверно.

Пример 5.7. = t = x; x = y; y = t;. Пусть = {x, y} = {u, v}. В этом случае является инвариантом программы. В самом деле, пусть x = u, y = v.

Тогда |=. () =, где x = v, y = u, то есть |=. Аналогично для случая, когда x = v, y = u.

Пример 5.8. Покажем, что u v = w инвариант следующего цикла:

Пусть |= u v = w, то есть u v = w. Очевидно, что и () (w) = w. Следовательно, Итак, () |= u v = w.

Замечание 5.7. Если инвариант программы, то инвариант цикла для любого T.

122 Глава 5. Доказательство корректности структурированных программ Обратное неверно. Рассмотрим пример.

Пример 5.9. Тот же цикл, но Пусть |=. Мы уже знаем из предыдущего примера, что () |= u v = w.

То есть () |= u x. Следовательно, инвариант цикла.

То, что не является инвариантом тела цикла, легко убедиться, рассмотрев состояние такое, что u = x = v + w. Тогда то есть () |=, хотя |=.

Определение 5.11 (Ограничитель цикла). Пусть дан цикл и предусловие. О г р а н и ч и т е л е м ц и к л а п р и п р е д у с л о в и и называется выражение L такое, что 1) (L ) для всякого состояния ;

2) () (L ) < (L ) для всякого состояния такого, что |= T.

Если предусловие истинно на предметной области, то такой ограничитель будет ограничителем и при любом другом предусловии. Мы будем Пример 5.10. Рассмотрим тот же цикл, что в примере 5.8. Пусть = ИСТИНА и L = xu. Очевидно, что (L) для любого. Пусть |= T, то есть |= u < x. Тогда Следовательно, Так как |= u < x, то Таким образом, Итак, L = x u ограничитель цикла при условии, следовательно, L универсальный ограничитель.

Лемма 5.1 (Полная корректность цикла). Пусть дан цикл инвариант цикла, L ограничитель. Тогда () определено и () |= ¬T для всякого состояния, для которого |=.

Доказательство. Пусть |=. Рассмотрим последовательность состояний цикла i i : 0 =, i+1 = 1 (). Индукцией по i докажем, что если i |= T, то 1 i определено и i+1 |=.

Базис индукции.

Если i = 0, то 0 |=.

Шаг индукции.

Пусть для i доказано и i |= T. Так как тройка { T } 1 {} полностью корректна, то 1 i определено и i+1 |=.

Рассмотрим последовательность i (L ) i. Если предположить, что (L ) i убывающая цепь натуральных чисел. Следовательно, она не может быть бесконечной, противоречие. Это означает, что должен существовать элемент n такой, что n |= T и i |= T для i < n. По определению семантики цикла () определено и () = n. Получаем, что Лемма 5.2 (Об ограничителе цикла). Если переменная z не входит в условия,, тест T, выражение L и программу 1 и тройка полностью корректна и (L) при любом состоянии, то L ограничитель цикла при условии.

Задача 5.8. Докажите лемму.

124 Глава 5. Доказательство корректности структурированных программ Задача 5.9. Приведите пример, доказывающий, что условие невхождения z в программу 1 существенно.

Теперь мы можем определить правила вывода для циклов. Пусть дан ЦЧ Для частичной корректности. Если частичный инвариант цикла, то {} { ¬T }. То есть, из частичной корректности { T } 1 {} следует частичная корректность {} { ¬T }.

ЦП Для полной корректности. Если инвариант цикла и L ограничитель, то {} { ¬T }. То есть, из полной корректности тройки где z не входит в, T, L и 1, следует полная корректность тройки {} { ¬T }. Предполагается, что выражение L должно принимать только натуральные значения.

Докажем, что с помощью этих правил из корректных троек получаются корректные. Для правила ЦП это следует из лемм 5.1 и 5.2.

Докажем это утверждение для правила ЦЧ. Пусть |= и () определено. Тогда существует последовательность i i=0 :

Так же как в лемме 5.1 доказывается, что i |=. Следовательно, n |= ¬T, то есть () |= ¬T и тройка {} { ¬T } частично корректна.

Рассмотрим пример.

Пример 5.11. Мы докажем полную корректность тройки для следующей программы:

3. ОП : 2. Формула истинна, поэтому {y = y u = 0} v = y; {}.

5. УПР : 4. Очевидно, что формула истинна. Поэтому • Прежде, чем продолжать, преобразуем вторую часть :

Рассмотрим v < x:

126 Глава 5. Доказательство корректности структурированных программ 8. ОП : 7. Формула истинна. Значит 10. УПР : 9. { v < x} 3 {}.

• Преобразуем последнюю формулу:

12. ОП : 11. {} 2 {u = x y}.

13. СЛ : 5, 12. {ИСТИНА} {u = x y}.

Мы формально доказали, что программа действительно выполняет вычитание чисел.

Мы часто в дальнейшем будем пользоваться следующей леммой.

Лемма 5.3 (О замене переменной). Если где y переменная, которая не встречается в доказательстве тройки {} {} (и, следовательно, в программе ).

Доказательство. Пусть D доказательство {} {}. Заменим всюду в D переменную x на y. Нужно теперь доказать, что полученная последовательность снова будет доказательством. Индукция по длине доказательства.

Базис индукции.

Аксиома: {()z } z = e; {}. Если z = x, то Получаем что является аксиомой.

Получаем что тоже является аксиомой.

Шаг индукции.

Индукционный шаг состоит в доказательстве того, что после замены переменных все применения правил останутся верными. Докажем два из них.

НВ Пусть тройка получена из тройки { T } 1 {} и истинности ¬T. По индукционному предположению Формула ()y ¬ (T )y ()y так же будет истинна. По правилу НВ получаем 128 Глава 5. Доказательство корректности структурированных программ ЦП Пусть из полной корректности тройки получена полная корректность По индукционному предположению получаем доказуемость Так как y отличается в том числе и от z, то с помощью правила ЦП можно вывести Задача 5.10. Докажите, что из истинности формулы ¬T следует истинность ()x ¬ (T )x ()x.

Задача 5.11. Докажите индукционный шаг для остальных правил.

Рассмотрим некоторые способы упростить формальные доказательства корректности.

Определение 5.12 (Допустимость). Аксиома или правило вывода называются д о п у с т и м ы м и в исчислении I, если их добавление к исчислению I не увеличивает множество доказуемых конструкций.

То есть аксиома или правило допустимы, если всё, что можно доказать с их использованием, можно доказать и без них. Введём некоторые новые аксиомы и правила, которые могут упростить доказательство, и докажем их допустимость.

ПРИСВ Аксиома:

при условии, что u не входит ни в, ни в e.

Доказательство. Аксиома АКС:

Так как u не входит ни в ни в e, то u (()x )e e = (e)x следует из. По правилу УПР получаем:

Задача 5.12. Докажите истинность формулы:

ПРИСВ* Аксиома:

при условии, что x не входит ни в, ни в e.

Доказательство. Предыдущая аксиома: