авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 7 |

«министерство образования российской федерации московский государственный индустриальный университет кафедра информационные системы и технологии центр компьютерных ...»

-- [ Страница 2 ] --

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

§3. Высказывания и предикаты e e e e e e e ee F ( ( F vT ) = F F) ) (T = Рис. 2. Определение истинности предиката ((F T ) F ) Определение 3.12. Состояние s это отображение из множества идентификаторов в множество {T, F }. Пространство состояний перемен ных программы это прямое произведение множеств состояний всех пе ременных программы.

Теперь можно дать определение значения любого предиката в задан ном состоянии.

Определение 3.13. Значение предиката e в состоянии s (записыва ется как e(s) или s(e)) совпадает со значением константного предиката, который получается из предиката e заменой всех идентификаторов на их значения в состоянии s.

Предикат ((a T ) b), например, в состоянии s = {(a, T ), (b, F )} имеет значение F, ибо именно таково значение константного предиката ((T T ) F ).

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

Определение 3.14. Состояние s в расширенном смысле отображе ние из множества идентификаторов в множество {T, F, U }, где символ U означает неопределенное (undened) значение.

Большинство предикатов не имеют определенного значения в таком состоянии, в котором не определены некоторые из переменных, входящих 44 Глава I. Введение в информатику и программирование Таблица 3. Таблица истинности для условных операторов b T T F F T F U U U c T F T F U U T F U bc T T T F T U U U U b&&c T F F F U F U U U Таблица 4. Таблица истинности предиката ((a b) = (b a)) (a b) (b a) ((a b) = (b a)) a b F F F F T T F T T T F T T T T T T T T T в него. В частности, операции !,,, и = дают результат U, если хотя бы один из операндов имеет значение U. Совершенно другая ситуация с условными операторами. Для них справедлива таблица истинности 3.

Среди огромного множества всех предикатов особую роль играют те из них, которые всегда являются истинными, как, например ((!(!a)) = a).

Определение 3.15. Предикат называется тавтологией, если он ис тинен во всех состояниях, в которых он определен.

Один из простейших способов доказать, что предикат является тав тологией, это вычислить его значения во всех возможных состоя ниях. Таблица 4 является доказательством того факта, что предикат ((a b) = (b a)) тавтология.

Определение 3.16. Высказывания e1 и e2 эквивалентны, если пре дикат e1 = e2 является тавтологией.

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

Предложение 3.2. Законы коммутативности:

((e1 e2 ) = (e2 e1 ));

((e1 e2 ) = (e2 e1 ));

((e1 = e2 ) = (e2 = e1 )).

Предложение 3.3. Законы ассоциативности:

((e1 (e2 e3 )) = ((e1 e2 ) e3 ));

§3. Высказывания и предикаты ((e1 (e2 e3 )) = ((e1 e2 ) e3 ));

(e1 &&(e2 &&e3 )) = ((e1 &&e2 )&&e3 ));

((e1 (e2 e3 )) = ((e1 e2 ) e3 )).

Предложение 3.4. Законы дистрибутивности:

((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 )));

((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 )));

((e1 &&(e2 e3 )) = ((e1 &&e2 ) (e1 &&e3 )));

((e1 (e2 &&e3 )) = ((e1 e2 )&&(e1 e3 ))).

Предложение 3.5. Законы де Моргана:

((!(e1 e2 )) = ((!e1 ) (!e2 )));

((!(e1 e2 )) = ((!e1 ) (!e2 )));

((!(e1 &&e2 )) = ((!e1 ) (!e2 )));

((!(e1 e2 )) = ((!e1 )&&(!e2 ))).

Предложение 3.6. Закон отрицания:

((!(!e)) = e).

Предложение 3.7. Законы исключенного третьего:

(e (!e) = T );

(e (!e) = T ), если e определено.

Предложение 3.8. Законы противоречия:

(e (!e) = F );

(e&&(!e) = F ), если e определено.

Предложение 3.9. Закон импликации:

((e1 e2 ) = ((!e1 ) e2 )).

Предложение 3.10. Закон равенства:

((e1 = e2 ) = ((e1 e2 ) (e2 e1 ))).

Предложение 3.11. Законы упрощения дизъюнкции:

((e e) = e);

((e T ) = T );

((e F ) = e);

((e1 (e1 e2 )) = e1 ).

Предложение 3.12. Законы упрощения конъюнкции:

((e e) = e);

((e T ) = e);

((e F ) = F );

((e1 (e1 e2 )) = e1 ).

Предложение 3.13. Законы упрощения условного Или:

((e e) = e);

46 Глава I. Введение в информатику и программирование ((e T ) = T ), если e определено;

((e F ) = e);

((e1 (e1 &&e2 )) = e1 ).

Предложение 3.14. Законы упрощения условного И:

((e&&e) = e);

((e&&T ) = e);

((e&&F ) = F ), если e определено;

((e1 &&(e1 e2 )) = e1 ).

Предложение 3.15. Закон тождества:

(e = e).

4. Расширение понятия предиката. В реальных программах далеко не все переменные имеют логический тип, что означает невозможность их описания с помощью предикатов, введенных определением 3.9. Так, например, выражение i 3 для целочисленной переменной i предикатом в смысле упомянутого определения заведомо не является, что плохо. Эти и некоторые другие причины побуждают расширить множество предика тов, что и будет сейчас сделано в три этапа.

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

Начиная с этого момента выражение ((i 3)(j = 0)) предикат, так как для него можно указать следующую цепочку вывода: e (e e) (id1 e) (id1 id2 ) ((i 3) id2 ) ((i 3) (j = 0)). Множеством состояний этого предиката является пространство Z 2, так как каждая из двух входящих в него целых переменных может изменяться независимо программные переменные, то пространство Z от другой. Если i и j следует заменить на Z2. M Примером предиката, который определен в состоянии, в котором одна из входящих в него переменных не является определенной, может слу жить выражение P = ((a = 0)||(b/a 0)). В состоянии s = {(a, 0), (b, U )} он истинен: P (s) = T. Подобные предикаты возникают при описании фрагментов программ типа if (a==0 || b/a 0)...

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

§3. Высказывания и предикаты Если P (x) предикат в смысле определения 3.17, зависящий от пере менной x произвольного типа, а X некоторое множество, то будем счи тать предикатами выражения (x(x X P (x))) и (x(x X P (x))).

Первое из них означает, что существует хотя бы одно x X для кото рого выполнено P (x), а второе что для всех x X справедливо P (x).

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

((x X)P (x)) = (x(x X P (x))), ((x X)P (x)) = (x(x X P (x))).

Когда используемое множество X понятно из контекста, его опускают, что приводит к выражениям (x P (x)) и (x P (x)).

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

((!x)P (x)) = (x(P (x) y(P (y) (y = x)))).

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

В предикате R = (i(m i n xi 0)) идентификатор i является связанным (квантором ), а идентификаторы m, n и x свободными.

Выражение (i 0(i(m i n xi 0))) предикатом мы считать не можем, ибо i в нем является одновременно и свободным идентификатором и связанным, что недопустимо. Его легко слегка изменить так, чтобы оно стало предикатом: (i 0 (k(m k n x k 0))) уже предикат.

Третьим шагом в направлении расширения множества языка предика тов будет ослабление требования на наличие в предикате всех тех скобок, которые возникают в процессе его вывода. Напомним, что с точки зрения определения 3.9 выражение a b, например, предикатом не является, что не слишком удобно с практической точки зрения.

Разрешим удалять из предиката все те пары скобок, которые можно опустить без потери его однозначного толкования. При этом семантика 48 Глава I. Введение в информатику и программирование полученного предиката определяется приоритетом операций: сначала вы числяются выражения внутри скобок, затем логические выражения, заменившие логические идентификаторы id в смысле определения 3.17, после этого кванторы существования и всеобщности, а затем логиче ские операции !, && и, и, и, наконец, =.

Таким образом, мы принимаем следующее определение.

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

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

Рассмотрим, как решаются типичные задачи на вычисление значения предикатов в расширенном смысле в различных состояниях.

Задача 3.4. Вычислите значения предикатов P1 = (x = 0 x/(y2) = 0) и P2 = (x = 0 && x/(y 2) = 0) в состоянии s = {(x, 7), (y, 2)}.

Решение. Если восстановить в этих предикатах все недостающие скобки, то мы получим предикаты P3 = ((x = 0) ((x/(y 2)) = 0)) и P4 = ((x = 0)&&((x/(y 2)) = 0)) соответственно. В состоянии s вы ражение (x = 0) является ложным, ибо (7 = 0) = F, а x/(y 2) имеет значение U (не определено). В соответствии с таблицами истинности для операций и && можно сделать вывод, что P1 (s) = U, а P2 (s) = F.

9 (i Задача 3.5. Вычислите значения предиката P = (i 0 i 0)) (j j 2 k) в состоянии s = {(k, 0)}.

Решение. Предикат P представляет из себя конъюнкцию двух пре дикатов, первый из которых это i 0 i 9 i2 0, а второй в состоянии s совпадает с j j 2 0. Так как при i = 0 выполнено i2 0, то первый из них истинен, а истинность второго предиката не вызывает сомнений.

Таким образом, предикат P (s), являющийся конъюнкцией двух истинных выражений, сам является истинным, P (s) = T.

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

§3. Высказывания и предикаты x Определение 3.19. Подстановкой Ee называется выражение, полу чающееся одновременной подстановкой e вместо всех свободных вхожде ний x в E.

Вот несколько простых примеров: (x + y)x = (z + y);

для E = x z y y (i i n f (i) y) имеем Ex+y = x x + y (i i n f (i) x + y)), i но Ek = E, так как i не свободно в E.

Для предикатов с кванторами справедливы дополнительные законы эквивалентности, называемые также правилами построения отрицания.

Предложение 3.16. Законы построения отрицания:

!(xP (x)) = x(!P (x));

!(xP (x)) = x(!P (x)).

5. Приоритеты и ассоциативность операторов языка Java. При вычислении значения выражения в языке Java важны не только приори теты, но и ассоциативность операторов.

Определение 3.20. Оператор @ является левоассоциативным, если выражение a @ b @ c вычисляется, как (a @ b) @ c;

правоассоциатив ным, если оно эквивалентно a @ (b @ c);

неассоциативным если запись a @ b @ c не имеет смысла.

В этом определении символ @ означает любой из бинарных операторов языка.

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

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

Таблица 5. Приоритеты и ассоциативность операторов Пр-т Оператор Тип опер. Асс-ть Операция 1 числовой пре- и постинкремент ++ числовой пре- и постдекремент -- числовой унарныe плюс и минус +, - целый побитовое дополнение ~ логический логическое отрицание ! любой преобразование типа (type) Глава I. Введение в информатику и программирование Таблица 5. Приоритеты и ассоциативность операторов Пр-т Оператор Тип опер. Асс-ть Операция 2 *, /, % числовой умножение, деление и оста ток 3 +, - числовой сложение и вычитание + строковый конкатенация строк 4 целый сдвиг влево целый сдвиг вправо с размножени ем знакового бита целый сдвиг вправо с размножени ем нуля 5, = числовой меньше, меньше или равно, = числовой больше, больше или равно instanceof объект, сравнение типов тип 6 == простой равенство значений простых типов != простой неравенство значений про стых типов == объект равенство ссылок на объек ты != объект неравенство ссылок на объ екты 7 & целый побитовое И & логический логическое И 8 ^ целый побитовое исключающее Или ^ логический логическое исключающее Или 9 | целый побитовое Или | логический логическое Или 10 && логический условное И 11 || логический условное Или 12 ?: логический, оператор условия любой, любой 13 = любой присваивание, присваивание *=, /=, %=, с операцией +=, -=, §4. Особенности представления чисел в ЭВМ Таблица 5. Приоритеты и ассоциативность операторов Пр-т Оператор Тип опер. Асс-ть Операция =, =, =, &=, ^=, |= С логическими и условными операторами мы уже знакомы, семанти ка арифметических операторов объясняется в следующем параграфе, а с оператором instanceof мы разберемся в третьей главе книги.

6. Задачи для самостоятельного решения.

Задача 3.6. Докажите, что выражение ((e1 (e2 e3 )) = ((e1 e2 ) (e1 e3 ))) является предикатом.

Задача 3.7. Докажите, что выражение ((a a) не предикат.

Задача 3.8. Изобразите деревья вывода для каждого из законов эк вивалентности (см. страницу 42).

Задача 3.9. Покажите, что все законы эквивалентности (см. стр. 42) являются тавтологиями.

Задача 3.10. Решите задачу о банке с кофейными зернами (см.

стр. 34) § 4. Особенности представления чисел в ЭВМ Как уже отмечалось ранее, множествам целых Z и действительных R чисел в большинстве языков программирования соответствуют их ма шинные аналоги. В случае языка Java используемые в программах пере менные величины и константы типов int и double принимают значения из множеств ZM и RM соответственно. В этом параграфе мы разберемся с тем, как именно устроены эти множества, и каковы последствия того, что программы оперируют не с настоящими числами, а с элементами указан ных множеств. Однако сначала некоторые напоминания об информации вообще и ее представлении в ЭВМ.

1. Представление информации в компьютере. Любая информация (числовая, текстовая, звуковая, графическая и т.д.) в компьютере пред ставляется (кодируется) в так называемой двоичной форме. Как опера тивная, так и внешняя память, где и хранится вся информация, могут рассматриваться, как достаточно длинные последовательности из нулей и 52 Глава I. Введение в информатику и программирование единиц. Под внешней памятью подразумеваются такие носители инфор мации, как магнитные и оптические диски, ленты и т.п.

Единицей измерения информации является бит (BInary digiT) именно такое количество информации содержится в ответе на вопрос:

нуль или один? Более крупными единицами измерения информации яв ляются байт, килобайт (Kbyte), мегабайт (Mbyte), гигабайт (Gbyte) и те рабайт (Tbyte). Один байт (byte) состоит из восьми бит, а каждая после дующая величина больше предыдущей в 1024 раза.

Байта достаточно для хранения 256 различных значений, что позволя ет размещать в нем любой из алфавитно-цифровых символов, если только мы можем ограничиться языками с небольшими алфавитами типа русско го или английского. Первые 128 символов (занимающие семь младших бит) стандартизированы с помощью кодировки ASCII (American Standart Code for Information Interchange). Хуже обстоит дело с кодировками рус ского текста (символы русского алфавита расположены во второй поло вине таблицы из 256 символов) их несколько, а наиболее распростра ненные из них сейчас две Windows-1251 и KOI8-R.

Для кодирования всех возможных символов, используемых народами мира, одного байта мало необходимо использовать два последователь ных (стандарт Unicode). Именно так и поступают при хранении символь ных (char) значений в языке Java.

Полезно знать, что 210 = 1024 1000 = 103. Учитывая, что в кни ге среднего размера около 300000 букв, легко подсчитать, что, даже не используя никаких средств сжатия информации, на жестком диске совре менного персонального компьютера емкостью в 20 гигабайт можно раз местить большую библиотеку из почти 70000 книг.

2. Целые числа. К целочисленным типам в языке Java относятся byte, short, int и long. Для хранения значений этих типов на любом компью тере отводится один, два, четыре и восемь байт соответственно. При этом применяется представление чисел в так называемом двоичном дополни тельном коде.

Напомним, что используемая нами обычная система счисления явля ется позиционной с основанием 10. Это значит, что в ней все натуральные числа представляются с помощью десяти цифр (от нуля до девяти вклю чительно), а значение каждой из цифр числа зависит от позиции: самая правая цифра означает число единиц (100 ), вторая десятков (101 ), тре тья сотен (102 ) и так далее.

В p-ичной системе счисления все точно также, только число 10 в пре дыдущем абзаце нужно всюду заменить на p. Наряду с двоичной системой, в которой только две цифры (0 и 1), в информатике часто применяются §4. Особенности представления чисел в ЭВМ восьмеричная с цифрами от нуля до 7 и шестнадцатеричная. В послед нем случае в качестве цифр от десяти до пятнадцати используются буквы от A до F соответственно.

При записи положительных целых чисел в системе счисления с осно ванием p (на компьютере p = 2) все их множество оказывается состоящим из элементов вида d = n1 pn1 + n2 pn2 +... + 0, где величины i для всех i из диапазона от n 1 до нуля это цифры n-значного числа d в p-ичной системе счисления.

Перейдем теперь к вопросу представления отрицательных чисел. Для определенности рассмотрим тип byte, в котором любое число занима ет ровно восемь бит. Из записи в двоичной системе счисления равенства (1) + 1 = 0 легко найти, какой вид должно иметь неизвестное нам пока двоичное представление xxxxxxxx числа 1:

xxxxxxxx + 00000001 = Ясно, что на месте символов xxxxxxxx должно быть расположено чис ло 11111111. Правильным результатом при этом, конечно, следовало бы считать 100000000, а не 00000000, но ведь мы имеем дело с типом byte и, так как результат обязан разместиться в байте, единица исчезает.

Итак, число 1 должно кодироваться как 11111111. Дальнейшее уже совсем просто: для получения 2 нужно 1 уменьшить на единицу, что даст 11111110;

число 3 представляется как 11111101 и т.д.

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

Легко видеть, что при этом самым маленьким отрицательным чис лом, которое принадлежит типу byte, является число 128 (двоичное представление 10000000), а самым большим число 127 (представление 01111111). Все представимые числа (а их 256) в данном случае могут быть получены как пересечение двух множеств: множества Z всех целых чи сел и отрезка [128, 127]. Интересным является следующее наблюдение:

если число 01111111 увеличить на единицу, то получится 10000000, что означает следующее: 127 + 1 = 128 !

Итак, множество элементов типа byte можно представлять себе в виде свернутого в кольцо отрезка [128, 127]. Принципиально ничего не меня ется и для типов short, int и long увеличивается только длина отрез ка, который вырезается из действительной прямой перед сворачиванием его в кольцо. Минимальные и максимальные представимые значения для 54 Глава I. Введение в информатику и программирование каждого из этих типов в языке Java определены, как значения констант MIN_VALUE и MAX_VALUE в классах java.lang.Short, java.lang.Integer и java.lang.Long соответственно.

То, что для элементов множества ZM, являющегося машинным анало гом Z, нарушено фундаментальное свойство целых чисел x + 1 x, спо собно привести к различным невероятным на первый взгляд результатам, однако гораздо более странные вещи происходят при работе с веществен ными числами.

3. Вещественные числа. Обсуждаемые в данной секции вопросы зна чительно более полно рассмотрены в четвертой главе классической книги Кнута [7].

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

В отличие от множества целых чисел Z вещественные числа R обла дают свойством полноты: между любыми двумя различными числами всегда найдется отличное от них третье. Понятно, что любой из спосо бов представления бесконечного множества вещественных чисел с помо щью некоторого конечного множества RM не даст возможности сохранить свойство полноты. Наиболее распространенным способом реализации ве щественных чисел на ЭВМ является использование чисел с плавающей точкой. При этом множество RM оказывается состоящим из элементов вида 1 2 n + 2 +... + n )pe, f = ±( p p p где целые числа i для всех i из диапазона от 1 до n удовлетворяют соотношению 0 i p 1, а величина e лежит в диапазоне от L до U (L e U ). Число p является при этом основанием системы счисления (чаще всего это 2), константа n задает точность представления чисел (для типа double она больше, чем для float), а диапазон [L, U ] определяет область значений экспоненты (для типа double он также больше, чем для float).

Число ±( 1 + 2 +... + n ) принято называть мантиссой числа f с 2 n p p p плавающей точкой. Часто требуют, чтобы для всех чисел f = 0 величина 1 была ненулевой. Такие числа с плавающей точкой называют нормали зованными.

В языке Java для кодирования величин типов float и double также используют числа с плавающей точкой. При этом часть из имеющегося множества бит используют для размещения экспоненты e, а остальные биты для размещения мантиссы.

§4. Особенности представления чисел в ЭВМ Для того чтобы хорошо понять, что же представляет из себя множе ство RM нормализованных чисел с плавающей точкой, полезно изобразить его на числовой прямой для случая небольших n, L и U. Подобная задача приведена в конце параграфа. Сейчас же нам будет достаточно весьма качественного описания этого множества.

Так как RM симметрично относительно начала координат, то мож но разобраться только с неотрицательными числами. Нуль, конечно же, принадлежит искомому множеству. Ближайшая к нулю следующая точ ка получается при 1 = 1, 2 = 3 =... = n = 0 и e = L. Это число для чисел типов float и double определено, как MIN_VALUE в классах java.lang.Float и java.lang.Double соответственно.

Правее располагается множество точек, следующих друг за другом с шагом 2Ln. Затем шаг увеличивается. Потом еще. И еще. При e = U расстояние между двумя соседними точками множества R M достигает 2U n. Самая правая точка множества получается при 1 = 2 =... = n = 1 и e = U. Для типов float и double это число определено, как MAX_VALUE в классах java.lang.Float и java.lang.Double.

Кроме перечисленных (и симметричных им отрицательных) значений в результате выполнения некоторых операций могут получиться также следующие особые значения: плюс бесконечность (POSITIVE_INFINITY), минус бесконечность (NEGATIVE_INFINITY), минус ноль и не число (NaN).

Например, при делении единицы на минус ноль получается минус беско нечность.

Описанные особенности множества машинных вещественных чисел RM приводят к тому, что не для всех его элементов верны следующие соотношения, всегда справедливые для множества настоящих веществен ных чисел R:

• x + 1 x;

• x + x существует;

• (x · 2)/2 = x;

• (x/2) · 2 = x;

• a + (b + c) = (a + b) + c;

• a + b + c = c + b + a.

Приведем несколько примеров, иллюстрирующих эти особенности множества RM.

Задача 4.1. Предъявите действительное (типа double) число x та кое, что x + 1 = x, а (x · 2)/2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MAX_VALUE.

Текст программы.

56 Глава I. Введение в информатику и программирование public class DblMaxVal { public static void main(String[] args) { double x = Double.MAX_VALUE;

double y = x + 1.0;

if (x == y) { Xterm.print("Для числа ");

Xterm.print("x = " + x, Xterm.Blue);

Xterm.print(" величины x и (x+1) ");

Xterm.print("равны!\n", Xterm.Red);

} y = 2.0 * x;

double z = y / 2.0;

if (x != z) { Xterm.print("Для числа ");

Xterm.print("x = " + x, Xterm.Blue);

Xterm.print(" величины x и (2.0*x)/2.0 ");

Xterm.print("различны\n", Xterm.Red);

Xterm.print("и равны соответственно");

Xterm.print(" " + x, Xterm.Red);

Xterm.print(" и");

Xterm.print(" " + z + "\n", Xterm.Red);

} } } Задача 4.2. Предъявите такие действительные (типа double) числа a, b и c такие, что a + (b + c) = (a + b) + c.

Достаточно вспомнить, что точки множества RM расположены на чи словой прямой неравномерно.

Текст программы.

public class DblNoAssociative { public static void main(String[] args) { double x = 1.0e-16;

double y = 1. + (x + x);

double z = (1. + x) + x;

if (y != z) { Xterm.print("Для числа ");

Xterm.print("x = " + x, Xterm.Blue);

§4. Особенности представления чисел в ЭВМ Xterm.print(" величины 1.+(x+x) и (1.+x)+x ");

Xterm.print("различны\n", Xterm.Red);

Xterm.print("и равны соответственно");

Xterm.print(" " + y, Xterm.Red);

Xterm.print(" и");

Xterm.print(" " + z + "\n", Xterm.Red);

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

Задача. Напишите программу, вводящую действительные коэффи циенты a, b и c квадратного уравнения ax2 + bx + c = 0 с положительным дискриминантом, находящую оба корня этого уравнения.

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

Текст программы.

public class SquareEquation { public static void main(String[] args) throws Exception { double a = Xterm.inputDouble("Введите число a - ");

double b = Xterm.inputDouble("Введите число b - ");

double c = Xterm.inputDouble("Введите число c - ");

if (a == 0.) { Xterm.println("Уравнение не квадратное", Xterm.Red);

System.exit(0);

} if (b*b - 4.*a*c = 0.) { Xterm.println("Дискриминант неположителен", Xterm.Red);

return;

} double x1 = ( -b - Math.sqrt(b*b - 4.*a*c) ) / (2.*a);

double x2 = ( -b + Math.sqrt(b*b - 4.*a*c) ) / (2.*a);

Xterm.println("Корни уравнения:");

Xterm.println("x1 = " + x1, Xterm.Blue);

Xterm.println("x2 = " + x2, Xterm.Blue);

} 58 Глава I. Введение в информатику и программирование } Для извлечения квадратного корня здесь используется метод sqrt класса Math. Вызов метода System.exit и применение оператора return, которые в теле метода main почти эквивалентны и приводят к немедлен ному завершению выполнения программы, позволяет обойтись без ветви else оператора if-else. Остальная часть программы комментариев не требует.

Попробуйте, однако, выполнить эту программу при a=0.2E-16 и b=c=1.0 первый корень уравнения x1 окажется равным -5.0E16, а вто рой x2 нулю.

Если подставить эти значения в выражение ax2 + bx + c, то и для x и для x2 его значение окажется равным единице, а не нулю. Подобная ошибка для первого, весьма большого по величине корня, представляется вполне естественной, но вот соглашаться с тем, что нуль является корнем данного уравнения, совсем не хочется. Этой проблеме посвящена одна из приведенных ниже задач.

4. Арифметические и побитовые операторы языка Java. К ариф метическим операторам языка Java, которые определены для всех чи словых типов, относятся: + (сложение и унарный плюс), += (сложение с присваиванием), - (вычитание и унарный минус), -= (вычитание с присва иванием), * (умножение), *= (умножение с присваиванием), / (деление), /= (деление с присваиванием), % (остаток от деления или деление по мо дулю), %= (остаток от деления с присваиванием), ++ (инкремент) и - (декремент).

Любой оператор с присваиванием с точки зрения получаемого резуль тата эквивалентен выполнению соответствующей операции с последую щим присваиванием, но работает обычно быстрее: a @= b эквивалентно а = a @ b (здесь символ @ означает любую из бинарных арифметических операций).

Результат выполнения операций деления и деления по модулю (нахо ждения остатка) для целочисленных операндов является целым числом.

Так, например, 5/3 равняется 1.

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

int i = 2, j = 3;

// i = 2, j = int k = i + j++;

// k = 5, j = int m = --i;

// i = 1, m = §4. Особенности представления чисел в ЭВМ Таблица 6. Битовые операции a b ~a a|b a^b a&b 0 01 0 0 1 00 1 1 0 11 1 1 1 10 1 0 С величинами целых типов можно выполнять дополнительные дей ствия. К побитовым (или поразрядным) операторам языка Java относят ся следующие: ~ (дополнение), & (побитовое И), &= (побитовое И с при сваиванием), | (побитовое Или), |= (побитовое Или с присваиванием), ^ (исключающее Или), ^= (исключающее Или с присваиванием), (сдвиг влево), = (сдвиг влево с присваиванием), (сдвиг вправо), = (сдвиг вправо с присваиванием), (сдвиг вправо с размножением нуля) и = (сдвиг вправо с присваиванием с размножением нуля).

Результаты операций побитового дополнения, Или, исключающего Или и И получаются путем выполнения над каждым из битов операн да (операндов) действий в соответствии с таблицей 6.

Например, 4^5 равняется 1 (ибо двоичные представления этих чисел есть соответственно 100 и 101).

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

int i = 3, j = 100;

// i = 3, j = int k = i 4;

// k = int m = j 2;

// m = Легко понять, что сдвиг влево на n разрядов эквивалентен умножению на 2n, а сдвиг вправо делению на то же число.

5. Задачи для самостоятельного решения.

Задача 4.3. Предъявите целое число x такое, что x + 1 x.

Задача 4.4. Явно перечислите и изобразите на числовой прямой все точки множества RM, сделав следующие допущения: числа хранятся в нормализованной форме с плавающей точкой;

для хранения как мантис сы, так и порядка числа отводится по три бита (из которых в обоих слу чаях один является знаковым);

никаких особых значений нет.

Задача 4.5. Предъявите действительное (типа double) число x та кое, что (x/2) · 2 = x. Воспользуйтесь тем, что класс java.lang.Double определяет константу MIN_VALUE.

60 Глава I. Введение в информатику и программирование Задача 4.6. Определите (приближенно) M ACHEP S (машинное эп силон) для типов double и float. Машинным эпсилоном называется наи большее число x данного типа, удовлетворяющее соотношению 1 + x = 1.

Задача 4.7. Предъявите последовательность чисел (типа float), при суммировании которой в прямом и обратном порядке результаты будут отличаться не менее, чем вдвое.

Задача 4.8. Напишите программу, вводящую действительные коэф фициенты a, b и c квадратного уравнения ax2 + bx + c = 0 с положитель ным дискриминантом, находящую оба корня этого уравнения достаточно точно во всех случаях.

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

В случае языка Java пакет java.math дает возможность программи сту работать с целыми и вещественными числами произвольной длины и точности, не требуя при этом никакого дополнительного кодирования, однако обсуждение данного пакета в нашем курсе не предполагается.

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

§ 5. Рекурсия, итерация и оценки сложности алгоритмов Более подробное изложение материала, рассматриваемого в данном параграфе, может быть найдено в книгах [9] и [4]. Вопросы, связанные с асимптотическими оценками сложности алгоритмов, подробно изложены в классической книге Кнута [6] и, охватывающем тематику двух первых курсов цикла программистских дисциплин, прекрасном издании [8].

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

§5. Рекурсия, итерация и оценки сложности алгоритмов Определение 5.1. Рекурсия это такой способ организации обработ ки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ.

Определение 5.2. Итерация способ организации обработки дан ных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.

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

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

Факториал n! целого неотрицательного числа n задается следующими соотношениями:

0! = 1, n! = n · (n 1)! для n 0.

Числами Фибоначчи fn называют последовательность величин 0, 1, 1, 2, 3, 5, 8,..., определяемую равенствами:

f0 = 0, f1 = 1, для n 1.

fn = fn1 + fn Математическая модель итерации сводится к повторению некоторо го преобразования (отображения) T : X X на множестве переменных программы X (прямом произведении множеств значений отдельных пе ременных). Программной реализацией итерации является обычно некото рый цикл, тело которого осуществляет преобразование T.

В качестве примера можно рассмотреть схему вычисления факториала натурального числа в соответствии с его другим определением: n! = 1 · 2 ·... · n. При написании программы в соответствии с ним нужно работать с двумя величинами целого типа ZM : числом i, которое будет играть роль счетчика и изменяться от 1 до n включительно, и величиной k, в которой будет накапливаться произведение чисел от 1 до i.

Пространством X в данном случае будет Z2, в качестве начальной M точки в этом пространстве возьмем точку (1, 1) (что соответствует i = k = 1), а преобразование T : X X будет иметь вид T (i, k) = (i + 1, k i). В случае, например, трехкратного применения преобразования T получим T (T (T (1, 1))) = T (T (2, 1)) = T (3, 2) = (4, 6), что обеспечит вычисление факториала числа 3.

62 Глава I. Введение в информатику и программирование Рекурсия и итерация взаимозаменяемы. Более точно, справедливо сле дующее утверждение.

Теорема 5.1. Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде, и наоборот.

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

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

Задача 5.1. Напишите рекурсивную программу, вычисляющую фак ториал введенного натурального числа.

Текст программы.

public class FactR { static int f(int x) { return (x == 0) ? 1 : x * f(x-1);

} public static void main(String[] args) throws Exception { Xterm.println("n!=" + f(Xterm.inputInt("n=")));

} } Организация рекурсивных вычислений на языке Java не требует ис пользования никаких специальных конструкций достаточно известного нам вызова метода. В приведенной программе метод f получает на вход целое число x и рекурсивно вычисляет его факториал. Рассмотрим про цесс выполнения данной программы для n = 3 более подробно.

Вызов метода f с аргументом 3 представим в виде листа бумаги, на котором указано входное значение (число 3). Универсальный исполнитель должен выполнить предписанные действия на этом листе бумаги и полу чить итоговый результат. Так как число 3 отлично от нуля, универсаль ный исполнитель попытается умножить число 3 на f(2), но последняя величина для ее вычисления требует вызова метода f с аргументом 2.

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

Вычисление f(2) потребует нахождения f(1), что вызовет появление еще одного листа бумаги третьего экземпляра метода f. Он, в свою §5. Рекурсия, итерация и оценки сложности алгоритмов очередь, вызовет f(0). В этот момент накопится уже пачка листов (ее на зывают стеком вызовов) целых четыре штуки. При этом вычисления на всех нижних листах приостановлены до завершения работы с верхними.

Далее события будут развиваться следующим образом. Метод f, вы званный с нулевым аргументом, самостоятельно вычисляет и возвращает с помощью оператора return результат число 1. Верхний элемент из стека вызовов методов после этого удаляется и возобновляются вычис ления величины f(1). Этот процесс продолжается до тех пор, пока стек вызовов не станет пустым, что произойдет по завершению вычисления значения f(3). Итоговое значение 6 будет возвращено в метод main, ко торый его и напечатает.

При написании рекурсивных программ обычно необходимо исследо вать два основных вопроса:

а) всегда ли и почему программа заканчивает работу?

б) почему после окончания работы программы будет получен требуемый результат?

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

Рассмотрим следующее утверждение P, зависящее от числа n: про грамма завершает свою работу для входного значения n за конечное время. Для того чтобы доказать истинность утверждения P (n) для всех целых неотрицательных чисел с помощью метода математической индук ции достаточно проверить его истинность при нулевом значении n (база индукции) и убедиться в справедливости индуктивного перехода, что тре бует проверки истинности предиката P (n) P (n + 1).

При нулевом значении аргумента программа завершает свою работу немедленно, поэтому утверждение P (0) истинно и база индукции прове рена.

Пусть утверждение P (n) истинно при некотором значении n. Пока жем, что и P (n + 1) тогда истинно. Для вычисления f(n+1) в соответ ствии с текстом программы нужно перемножить n+1 и f(n). Истинность P (n) гарантирует нам вычисление второго множителя за конечное время, а так как перемножение двух чисел тоже требует конечного времени, то и P (n + 1) истинно, что и завершает доказательство завершения работы программы при всех целых неотрицательных значениях аргумента.

Заметим, что для отрицательных значений n Z данная програм ма должна была бы работать бесконечно долго (как принято говорить, должна зациклиться). Однако из-за того, что в реальности мы имеем дело с машинным заменителем множества целых чисел множеством 64 Глава I. Введение в информатику и программирование ZM, выполнение всегда завершится за конечное время, хотя полученный результат и не будет иметь никакого смысла.

Доказательство правильности вычисляемого приведенной программой значения проводится совершенно аналогично. Рассмотрим утверждение P (n) = (для входного значения n результатом является n!) и докажем его истинность по индукции.

Истинность P (0) (база индукции) проверяется непосредственно, а для проверки корректности индуктивного перехода напишем следующую це почку равенств: P (n + 1) = (n + 1) · P (n) = (n + 1) · n! = (n + 1)!, первое из которых следует из текста программы, второе из предположения индукции, а третье из определения факториала. Это завершает дока зательство теоретической правильности написанной программы.

В реальности, однако, быстрый рост функции n! и ограниченность множества ZM приводят к тому, что эта программа позволяет получить правильные результаты только при очень небольших значениях n. Уже при n = 13 печатаемое ей значение 1932053504 отличается от правиль ного 6227020800, а при n = 17 программа выдает даже отрицательный результат!

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

Задача 5.2. Напишите рекурсивную программу, печатающую n-ое число Фибоначчи.

Текст программы.

public class FibR { static int fib(int x) { return (x 1) ? fib(x-2) + fib(x-1) : (x == 1) ? 1 : 0;

} public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n - ");

Xterm.println("fib(" + n + ") = " + fib(n));

} } Обратите внимание, что при вычислении f5 в соответствии с этой про граммой понадобится найти f4 и f3. Определение f4, в свою очередь, по требует вычисления f3 и f2, и так далее. Внимательно изучение содер жимого стека вызовов для этой задачи показывает, что для нахождения каждого следующего числа Фибоначчи требуется примерно вдвое большее время, чем для определения предыдущего. Для того, чтобы убедиться в этом, нарисуйте дерево, изображающее процесс вычисления f 7 с помощью данной программы.

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

Язык Java предусматривает три различных оператора цикла: while, do-while и for. Первый из них обычно используют в ситуации, когда тело цикла нужно выполнить нуль или более раз, а второй применяется, если его выполнение хотя бы раз обязательно. Третий из операторов является наиболее универсальным и используется в различных ситуациях.

Дополнительными средствами, используемыми при организации цик лов, являются операторы break и continue. Первый из них прерывает выполнение цикла, а второй позволяет досрочно перейти к выполнению следующей итерации, проигнорировав часть операторов тела цикла, еще не выполненных в текущей итерации. Заметим, что в языке Java отсут ствует оператор goto, в тех редких ситуациях, где он мог бы оказаться полезным, можно использовать операторы break или continue с метками.

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

Задача 5.3. Напишите итерационную программу, вычисляющую факториал введенного натурального числа.

Текст программы.

public class FactIv1 { public static void main(String[] args) throws Exception { int n, i, k;

n = Xterm.inputInt("Введите n - ");

i = k = 1;

while (i = n) { k *= i;

i += 1;

} Xterm.println("" + n + "! = " + k);

} } Конструкцию while в ней можно заменить на do-while:

66 Глава I. Введение в информатику и программирование Фрагмент программы (FactIv2.java).

А еще лучше воспользоваться циклом for:

Фрагмент программы (FactIv3.java).

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

Нахождение точной зависимости T (n) для конкретной программы задача достаточно сложная. По этой причине обычно ограничиваются асимптотическими оценками этой функции, то есть описанием ее при мерного поведения при больших значениях параметра n. Иногда для асимптотических оценок используют традиционное отношение O (чита ется О большое ) между двумя функциями f (n) = O(g(n)), определе ние которого можно найти в любом учебнике по математическому анали зу, хотя чаще применяют отношение эквивалентности (читается тэта большое ). Его формальное определение есть, например, в книге [8], хотя нам пока достаточно будет понимания данного вопроса в общих чертах.

В качестве первого примера вернемся к только что рассмотренным программам нахождения факториала числа. Легко видеть, что количе ство операций, которые должны быть выполнены для нахождения фак ториала n! числа n в первом приближении прямо пропорционально этому числу, ибо количество повторений цикла (итераций) в данной програм ме равно n. В подобной ситуации принято говорить, что программа (или алгоритм) имеет линейную сложность (сложность O(n) или (n)).

Можно ли вычислить факториал быстрее? Оказывается, да. Можно написать такую программу, которая будет давать правильный результат для тех же значений n, для которых это делают все приведенные выше программы, не используя при этом ни итерации, ни рекурсии. Ее слож ность будет (1), что фактически означает организацию вычислений по некоторой формуле без применения циклов и рекурсивных вызовов!

Не менее интересен и пример вычисления n-го числа Фибоначчи. В процессе ее исследования фактически уже было выяснено, что ее слож ность является экспоненциальной и равна (2n ). Подобные программы практически не применимы на практике. В этом очень легко убедиться, попробовав вычислить с ее помощью 40-е число Фибоначчи. По этой при чине вполне актуальна следующая задача.

Задача 5.4. Напишите программу, печатающую n-ое число Фибонач чи, которая имела бы линейную сложность.

§5. Рекурсия, итерация и оценки сложности алгоритмов Вот решение этой задачи, в котором переменные j и k содержат зна чения двух последовательных чисел Фибоначчи.

Текст программы.

public class FibIv1 { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n - ");

Xterm.print("f(" + n + ")");

if (n 0) { Xterm.print(" не определено\n");

} else if (n 2) { Xterm.println(" = " + n);

} else { long i = 0;

long j = 1;

long k;

int m = n;

while (--m 0) { k = j;

j += i;

i = k;

} Xterm.println(" = " + j);

} } } Следующий вопрос вполне естественен а можно ли находить числа Фибоначчи еще быстрее?

После изучения определенных разделов математики совсем просто вы вести следующую формулу для n-ого числа Фибоначчи fn, которую легко проверить для небольших значений n:

n n 1 1+ 5 1 fn =.

2 Может показаться, что основываясь на ней, легко написать программу со сложностью (1), не использующую итерации или рекурсии.

Текст программы.

public class FibIv2 { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n - ");

double f = ( 1.0 + Math.sqrt(5.) ) / 2.0;


int j = (int)( Math.pow(f,n) / Math.sqrt(5.) + 0.5 );

68 Глава I. Введение в информатику и программирование Xterm.println("f(" + n + ") = " + j);

} } На самом деле эта программа использует вызов функции возведения в степень Math.pow(f,n), которая не может быть реализована быстрее, чем за логарифмическое время (log2 n). Про алгоритмы, в которых коли чество операций примерно пропорционально log n (в информатике приня то не указывать основание двоичного логарифма) говорят, что они имеет логарифмическую сложность ((log n)).

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

Задача 5.5. Напишите программу, печатающую n-ое число Фибонач чи, которая имела бы логарифмическую сложность.

Текст программы.

public class FibIv3 { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n - ");

Xterm.print("f(" + n + ")");

if (n 0) { Xterm.println(" не определено");

} else if (n 2) { Xterm.println(" = " + n);

} else { Matrix b = new Matrix(1, 0, 0, 1);

Matrix c = new Matrix(1, 1, 1, 0);

while (n0) { if ((n&1) == 0) { n = 1;

c.square();

} else { n -= 1;

b.mul(c);

} } Xterm.println(" = " + b.fib());

} } } §5. Рекурсия, итерация и оценки сложности алгоритмов class Matrix { private long a, b, c, d;

public Matrix(long a, long b, long c, long d) { this.a = a;

this.b = b;

this.c = c;

this.d = d;

} public void mul(Matrix m) { long a1 = a*m.a+b*m.c;

long b1 = a*m.b+b*m.d;

long c1 = c*m.a+d*m.c;

long d1 = c*m.b+d*m.d;

a = a1;

b = b1;

c = c1;

d = d1;

} public void square() { mul(this);

} public long fib() { return b;

} } Если попробовать посчитать десятимиллионное число Фибоначчи с по мощью этой и предыдущей программ, то разница во времени счета будет вполне очевидной. К сожалению, результат будет неверным (в обоих слу чаях) в силу ограниченности диапазона чисел типа long.

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

Рассмотрим четыре алгоритма решения одной и той же задачи, имею щие сложности log n, n, n2 и 2n соответственно. Предположим, что второй из этих алгоритмов требует для своего выполнения на некотором компью тере при значении параметра n = 103 ровно одну минуту времени. Тогда времена выполнения всех этих четырех алгоритмов на том же компью тере при различных значениях параметра будут примерно такими, как в таблице 7.

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

70 Глава I. Введение в информатику и программирование Таблица 7. Сравнительная таблица времен выполнения алгоритмов Сложность алгоритма n = 10 n = 103 n = 0.2 сек. 0.6 сек. 1.2 сек.

log n 0.6 сек. 1 мин. 16.6 час.

n 6 сек. 16.6 час. 1902 года n 1 мин. 10295 лет 10300000 лет 2 n С увеличением быстродействия компьютеров возрастают и значения параметров, для которых работа того или иного алгоритма завершает ся за приемлемое время. Таким образом, увеличивается среднее значение величины n, и, следовательно, возрастает величина отношения времен выполнения быстрого и медленного алгоритмов. Чем быстрее компью тер, тем больше относительный проигрыш при использовании плохого алгоритма!

5. Массивы в языке Java. Язык Java, так же как и многие другие языки, позволяет работать с массивами элементов различных типов. Мас сив (array) используют, когда возникает необходимость хранить несколь ко однотипных значений, например, 50 целых чисел или 100 наименований книг, так как было бы неудобно использовать в таких случаях различные имена для всех этих переменных. В ближайшее время мы будем работать только с одномерными массивами и не будем пользоваться тем, что мас сивы динамические структуры данных. Об этом речь пойдет в третьей главе книги.

Рассмотрим следующую простейшую задачу на работу с массивом це лых чисел.

Задача 5.6. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, печатает его, затем инвертирует (то есть меняет местами первый элемент с последним, второй с предпоследним и т.д.), и вновь печатает.

Текст программы.

public class InvArr { public static void main(String[] args) throws Exception { int n, i, a[];

n = Xterm.inputInt("Введите длину массива n - ");

a = new int[n];

for (i=0;

in;

i++) a[i] = Xterm.inputInt("Введите a[" + i + "] - ");

§5. Рекурсия, итерация и оценки сложности алгоритмов Xterm.print("Введенный массив a =");

for (i=0;

in;

i++) Xterm.print(" " + a[i]);

Xterm.print("\nИнвертированный массив a =");

for (i=0;

in/2;

i++) { int j = a[i];

a[i] = a[n-1-i];

a[n-1-i] = j;

} for (i=0;

in;

i++) Xterm.print(" " + a[i]);

Xterm.print("\n");

} } Как видно из текста этой программы, для того чтобы завести мас сив, необходимо объявить его и зарезервировать затем память для его элементов с помощью оператора new. В этом случае все они будут авто матически проинициализированы нулевыми значениями. Массив из трех целых чисел, содержащий величины 3, 7 и 11, можно задать так:

int a[] = {3, 7, 11};

Элементы любого массива нумеруются с нуля, а для доступа к i-му его элементу используется выражение a[i]. Язык Java отслеживает все попытки обратиться к несуществующему элементу массива при попыт ке работать, скажем с a[n], возникает исключительная ситуация (выход индекса за границу массива), так как последний элемент имеет индекс n 1, а не n.

В качестве более содержательного комментария к программе инверти рования массива заметим, что выполнение цикла, переставляющего эле менты, завершается, как только будет достигнута середина массива. Если условие продолжения цикла in/2 заменить на in, то процесс обмена не завершится после того, как массив уже будет инвертирован, и обмен эле ментов продолжится, что приведет к двукратному инвертированию мас сива, что эквивалентно тождественному преобразованию.

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

Задача 5.7. Напишите программу, печатающую максимальный эле мент непустого массива.

Текст программы.

public class MaxArr { public static void main(String[] args) throws Exception { int n, i, a[];

n = Xterm.inputInt("Введите длину массива n - ");

Глава I. Введение в информатику и программирование a = new int[n];

for (i=0;

in;

i++) a[i] = Xterm.inputInt("Введите a[" + i + "] - ");

int max = a[0];

for (i=1;

in;

i++) if (a[i] max) max = a[i];

Xterm.println("Максимальный элемент массива = " + max);

} } В заключение рассмотрим задачу, включающую дополнительное тре бование на структуру программы.

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

Текст программы.

public class NumMaxArr { public static void main(String[] args) throws Exception { int n, i, a[];

n = Xterm.inputInt("Введите длину массива n - ");

a = new int[n];

int max = Integer.MIN_VALUE;

int nMax = 0;

for (i=0;

in;

i++) { a[i] = Xterm.inputInt("Введите a[" + i + "] - ");

if (a[i] max) { max = a[i];

nMax = 1;

} else if (a[i] == max) nMax += 1;

} Xterm.println("Количество макс. элементов = " + nMax);

} } Использование константы Integer.MIN_VALUE позволяет избежать необходимости присваивания переменной max значения нулевого элемента массива до начала циклического просмотра остальных элементов.

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

§5. Рекурсия, итерация и оценки сложности алгоритмов Задача сортировки является классической задачей на массивы.

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

Приведенный ниже алгоритм, который последовательно обменивает все соседние пары элементов, расположенных в неправильном порядке, является одним из самых медленных алгоритмов сортировки среди всех широко известных его асимптотическая сложность является квадра тичной ((n )).

Текст программы.

public class Sort { private static void sort(int[] a, int n) { int i, j, t;

for (i=0;

in-1;

i+=1) for (j=n-1;

ji;

j-=1) if (a[j] a[j-1]) { t=a[j];

a[j]=a[j-1];

a[j-1]=t;

} } public static void main(String[] args) throws Exception { int n, i, a[];

n = Xterm.inputInt("Введите длину массива n - ");

a = new int[n];

for (i=0;

in;

i++) a[i] = Xterm.inputInt("Введите a[" + i + "] - ");

Xterm.print("Исходный массив\n");

for (i=0;

in;

i++) Xterm.print(" " + a[i]);


Xterm.print("\n");

sort(a, n);

Xterm.print("Отсортированный массив\n");

for (i=0;

in;

i++) Xterm.print(" " + a[i]);

Xterm.print("\n");

} } 74 Глава I. Введение в информатику и программирование 6. Исключительные ситуации и работа с последовательностями.

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

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

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

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

Текст программы.

public class NumMaxSeqv1 { public static void main(String[] args) { int max = Integer.MIN_VALUE;

int nMax = 0;

try { while (true) { int x = Xterm.inputInt("Очередной элемент x - ");

if (x max) { max = x;

nMax = 1;

} else if (x == max) nMax += 1;

Xterm.println("Количество макс. элементов = " + nMax);

} } catch(Exception e) { ;

} } } Эта программа использует конструкцию try-catch, предназначенную для обработки исключительных ситуаций (называемых и просто исклю чениями). Интерпретатор байт-кода пытается выполнить все действия, §5. Рекурсия, итерация и оценки сложности алгоритмов указанные в блоке try (try переводится именно так пытаться). Ес ли это удается, то содержимое блока catch не оказывает никакого влия ния на ход выполнения программы. Однако, если в процессе выполнения блока try возникает исключительная ситуация нечто препятствую щее продолжению нормального выполнения программы, то управление немедленно передается блоку catch (catch означает поймать).

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

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

Фрагмент программы (NumMaxSeqv2.java).

Заметьте, что для программ, предусматривающих обработку исклю чительных ситуаций, теряет свою актуальность совет о необходимости до писывания фразы throws Exception в строку, начинающую определение метода main.

7. Задачи для самостоятельного решения.

Задача 5.11. Напишите программу, вычисляющую факториал вве денного натурального числа, не использующую ни итерации, ни рекурсии (имеющую сложность (1)).

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

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

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

Указание. Можете попробовать разобраться в программе, решаю щей задачу 5.5. В ней выполняется более сложное действие квадратная матрица возводится в степень n за логарифмическое время.

Задача 5.14. Напишите программу, вводящую целое число a и нату ральное n, вычисляющую и печатающую степень an без использования вызова функции возведения в степень.

76 Глава I. Введение в информатику и программирование Задача 5.15. Напишите программу (быстрое возведение в степень), возводящую целое число a в целую неотрицательную степень b без вызова функции возведения в степень с временнй сложностью (log b).

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

Задача 5.17. Напишите программу, вводящую натуральное число, и печатающую Yes, если оно является простым и No иначе.

Задача 5.18. Напишите программу, печатающую n-ое простое число.

Задача 5.19. Напишите рекурсивную программу, печатающую бино k минальный коэффициент Cn для целых n и k, где 0 k n. Для неотри n цательных n и k имеют место следующие соотношения: Cn = Cn = 1, k+1 k+1 k Cn+1 = Cn + Cn.

Задача 5.20. Напишите программу, вводящую имя пользователя (с применением метода inputChars), которая затем приветствует его.

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

Задача 5.22. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, и печатает Yes, если массив симметричен, и No иначе.

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

Задача 5.24. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел, циклически сдвигает элементы массива вправо на k позиций, и печатает результат. Число k вводится с клави атуры, а сложность программы должна быть (n).

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

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

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

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

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

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

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

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

Задача 5.33. Напишите программу, вводящую фразу русского языка (с использованием метода inputChars), которая определяет, является ли введенная фраза палиндромом.

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

§ 6. Спецификация программ и преобразователь предикатов Важнейший для дальнейшего изучения материал этого параграфа в более подробном изложении можно найти в книге [4]. Полезным будет также и знакомство с подходом учебного пособия [9].

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

Задача 6.1. Запишите предикат, утверждающий, что если i j, а m n, то u = v.

78 Глава I. Введение в информатику и программирование Решение. В данном случае все очевидно: i j m n (u = v).

Задача 6.2. Запишите предикат, утверждающий, что ни одно из сле дующих утверждений не является истинным: a b, b c и x = y.

Решение. Это задание тоже не является сложным. Вот несколько эквивалентных между собой решений: P1 = ((a b) = F ) ((b c) = F ) ((x = y) = F ), P2 =!(a b)!(b c)!(x = y) и P3 = a b b c x = y.

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

В ряде последующих задач нам придется иметь дело с массивами, по этому договоримся о следующих обозначениях: будем обозначать вырезку из массива b[0..m 1], в которой содержатся все элементы данного масси ва с индексами от j до k включительно, символом b[j..k]. В случаях, когда j k, k 0 или j m, вырезка представляет из себя пустое множество.

Задача 6.3. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 все элементы вырезки b[j..k] являются нулевы ми.

Решение. Используем квантор всеобщности: i j i k + 1 b[i] = 0.

Задача 6.4. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 ни один из элементов вырезки b[j..k] не нулевой.

Решение. Переформулировав данное высказывание (все элементы вырезки не нулевые), запишем ответ в следующем виде: i j i k + 1 b[i] = 0.

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

Задача 6.5. Запишите предикат, утверждающий, что для массива b[0..n 1] длины n 0 некоторые из элементов вырезки b[j..k] нулевые.

Решение. Данное высказывание можно понимать двояко: оно может означать, что в вырезке существует хотя бы один нулевой элемент, а мо жет значить и то, что в ней как минимум два нулевых элемента. Вот ответы для каждого из этих вариантов трактовки задачи: P 1 = i j i k + 1 b[i] = 0 и P2 = i j i k + 1 m (j m k + 1 m = i)(b[i] = 0) (b[m] = 0).

Вот аналогичные задачи из области математики.

Задача 6.6. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} является сюръективной и отрицание этого факта. Упростите получившиеся предикаты, если это возможно.

§6. Спецификация программ и преобразователь предикатов Решение. В соответствии с определением сюръективности имеем P = (y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} y = f (x)). Построим отрицание и упростим его в соответствии с законами эквивалентности. !P = (!(y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} y = f (x))) = (y {1, 2, 3, 4, 5} !(x {1, 2, 3, 4, 5} y = f (x))) = (y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} !(y = f (x))) = (y {1, 2, 3, 4, 5} x {1, 2, 3, 4, 5} y = f (x)).

Задача 6.7. Запишите предикат, который утверждает, что функция f : {1, 2, 3, 4, 5} {1, 2, 3, 4, 5} все элементы, не превосходящие трех, не увеличивает, и отрицание этого факта. Упростите получившиеся преди каты, если это возможно.

Решение. P = (x {1, 2, 3} f (x) x). Его отрицание можно упро стить: !P =!(x {1, 2, 3} f (x) x) = (x {1, 2, 3} f (x) x).

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

Часто, однако, полезно поручить проверку истинности предикатов в процессе выполнения программы непосредственно компьютеру. В раз личных языках программирования эта возможность реализована по разному. Например, в программах на языке C можно использовать ма крос assert(P), который в случае ложности его аргумента (предиката P) немедленно прекращает выполнение программы, сообщая о причине этого.

Механизм работы с исключениями и оператор if позволяют легко ре ализовать аналогичную конструкцию в языке Java. Вот простейший при мер.

Задача 6.8. Напишите программу, содержащую проверку истинности утверждения о положительности введенного с клавиатуры целого числа.

Текст программы.

public class Assert { public static void main(String[] args) throws Exception { int n = Xterm.inputInt("Введите n - ");

if (n = 0) throw new Exception("n = 0");

Xterm.println("n = " + n);

} } При вводе неположительного числа программа прекращает свое вы полнение и печатает следующий текст:

80 Глава I. Введение в информатику и программирование java.lang.Exception: n= at Assert.main(Assert.java:4) Богатые возможности работы с исключениями, имеющиеся в языке, позволяют реализовать гораздо более изощренные способы проверки ис тинности предикатов, нежели использованный в программе простейший вариант возбуждения исключения типа Exception без попыток его после дующей обработки. Эти возможности, однако, не будут рассматриваться в нашем курсе.

2. Спецификация программы и преобразователь предикатов wp.

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

Определение 6.1. Спецификацией {Q} S {R} программы S, где Q и R предикаты, называется предикат, означающий, что если выполнение S началось в состоянии, удовлетворяющем Q, то имеется гарантия, что оно завершится через конечное время в состоянии, удовлетворяю щем R.

Под программой S в данном определении может пониматься один или несколько отдельных операторов или же действительно целая большая программа.

Определение 6.2. Предикат Q называется предусловием или вход ным утверждением S;

R постусловием или выходным утверждением программы S.

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

Спецификация {i = 0} "i++;

" {i = 1} является тавтологией, специфи кация {i = 0} "i++;

" {i = 0} ложна во всех состояниях, а спецификация {i = 0} "i++;

" {i = j} истинна при j = 1 и ложна в остальных состояни ях.

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

Определение 6.3. Программа S является правильной при заданных Q и R, если спецификация {Q} S {R} является тавтологией.

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

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

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

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

Проиллюстрируем введенное понятие на нескольких примерах.

wp("i = i + 1;

", i 1) = (i 0), так как если переменная i удовле творяла условию i 0, то после выполнения программы "i = i + 1;

" она действительно будет удовлетворять неравенству i 1.

wp("if (x = y) z=x;

else z=y;

", z = max(x, y)) = T, ибо выпол нение программы "if (x = y) z=x;

else z=y;

" при любых начальных условиях приведет к тому, что переменная z станет равной максимально му значению из величин x и y.

x), потому что y wp("if (x = y) z=x;

else z=y;

", z = y) = (y будет равно максимуму из чисел x и y (а именно таково будет z после выполнения программы "if (x = y) z=x;

else z=y;

") тогда и только тогда, если именно переменная y имеет бльшее значение.

о wp("if (x = y) z=x;

else z=y;

", z = y 1) = F. Это (пустое мно жество состояний) означает, что ни при каких начальных условиях про грамма "if (x = y) z=x;

else z=y;

" не сможет сделать величину z меньше, чем y.

wp("if (x = y) z=x;

else z=y;

", z = y+1) = (x = y+1), ибо только при таком начальном условии после выполнения приведенной программы переменная z станет равной y + 1.

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

Предложение 6.1. {Q} S {R} = (Q wp(S, R)).

82 Глава I. Введение в информатику и программирование Определение 6.5. Преобразователем предикатов (обозначаемый че рез wpS (R)) называют wp(S, R) когда фиксируют программу S и рассмат ривают wp(S, R) как функцию одной переменной R.

Предложение 6.2. Преобразователь предикатов wp(S, R) обладает следующими свойствами:

1) wp(S, F ) = F (закон исключенного чуда);

2) wp(S, Q) wp(S, R) = wp(S, Q R) (дистрибутивность конъюнкции);

3) (Q R) (wp(S, Q) wp(S, R)) (закон монотонности);

4) wp(S, Q) wp(S, R) = wp(S, Q R) (дистрибутивность дизъюнкции).

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

Докажем аккуратно дистрибутивность конъюнкции. Для доказа тельства эквивалентности достаточно показать, что из условия wp(S, Q) wp(S, R), стоящего в левой части, вытекает условие wp(S, Q R), разме щенное в правой, и наоборот. Для доказательства импликации wp(S, Q) wp(S, R) wp(S, Q R) рассмотрим произвольное состояние s, удовле творяющее условию wp(S, Q) wp(S, R). Так как выполнение программы S, начавшееся в s, завершится при истинных Q и R, то истинным будет и предикат Q R.

Для доказательства обратной импликации wp(S, Q R) wp(S, Q) wp(S, R) рассмотрим состояние s, удовлетворяющее условию wp(S, QR).

Тогда выполнение S, начавшееся в s, обязательно завершится в некотором состоянии s, удовлетворяющем Q R. Но любое такое s обязательно удовлетворяет и Q и R, так что s удовлетворяет и wp(S, Q) и wp(S, R), что и завершает доказательство.

Закон монотонности докажите самостоятельно, а вот по поводу по следнего свойства преобразователя предикатов дистрибутивности дизъюнкции надо сделать некоторые замечания. Дело в том, что ес ли в качестве S рассмотреть операцию бросания монеты, которая может завершиться либо выпадением герба (G), либо решки (R), то wp(S, G) = wp(S, R) = F, ибо нельзя гарантированно предсказать результат бросания ни при каких начальных условиях. С другой стороны, wp(S, G R) = T, так как всегда выпадет либо герб, либо решка.

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



Pages:     | 1 || 3 | 4 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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