The word «semantic» is ambiguous, and you’ve encountered two slightly different meanings in these different contexts.
The first meaning (your code) is related to how a compiler interprets the code you type. But there are varying degrees of interpretation for this — syntax is one level, where interpretation is simply deciding that n1*n2 means you want to perform multiplication. But there is also a higher level of interpretation here — if n1 is an integer, and n2 is floating point, what is the result? What if I cast it, should it be rounded, truncated, etc? These are «semantic» questions rather than syntactic ones, but someone, somewhere, decided that yes, the compiler can answer these for most people.
They also decided that the compiler has limits to what it can (and should!) interpret. For example, it can decide that casting to an int is a truncation, not rounding, but it can’t decide what you really want when you try to multiply an array by a number.
(Sometimes people decide that they CAN, though. In Python, [1] * 3 == [1,1,1].)
The second meaning refers to a much wider scope. If the result of that operation is supposed to be sent to a peripheral device that can take values of 0x000 to 0xFFF, and you multiply 0x7FF by 0x010, clearly you’ve made a semantic error. The designers of the peripheral device must decide whether, or how, to cope with that. You, as a programmer, could also decide to put in some sanity checks. But the compiler has no idea about these external semantic constraints, or how to enforce them (filter user input? return an error? truncate? wrap?), which is what the second quote is saying.
Отладка программы призвана выискивать «вредителей» кода и устранять их. За это отвечают отладчик и журналирование для вывода сведений о программе.
В предыдущей части мы рассмотрели исходный код и его составляющие.
После того, как вы начнете проверять фрагменты кода или попытаетесь решить связанные с ним проблемы, вы очень скоро поймете, что существуют моменты, когда программа крашится, прерывается и прекращает работу.
Это часто вызвано ошибками, известными как дефекты или исключительные ситуации во время выполнения. Акт обнаружения и удаления ошибок из нашего кода – это отладка программы. Вы лучше разберетесь в отладке на практике, используя ее как можно чаще. Мы не только отлаживаем собственный код, но и порой дебажим написанное другими программистами.
Для начала необходимо рассортировать общие ошибки, которые могут возникнуть в исходном коде.
Синтаксические ошибки
Эти эрроры не позволяют скомпилировать исходный код на компилируемых языках программирования. Они обнаруживаются во время компиляции или интерпретации исходного кода. Они также могут быть легко обнаружены статическими анализаторами (линтами). Подробнее о линтах мы узнаем немного позже.
Синтаксические ошибки в основном вызваны нарушением ожидаемой формы или структуры языка, на котором пишется программа. Как пример, это может быть отсутствующая закрывающая скобка в уравнении.
Семантические ошибки
Отладка программы может потребоваться и по причине семантических ошибок, также известных как логические. Они являются наиболее сложными из всех, потому что не могут быть легко обнаружены. Признак того, что существует семантическая ошибка, – это когда программа запускается, отрабатывает, но не дает желаемого результата.
Рассмотрим данный пример:
3 + 5 * 6
По порядку приоритета, называемому старшинством операции, с учетом математических правил мы ожидаем, что сначала будет оценена часть умножения, и окончательный результат будет равен 33. Если программист хотел, чтобы сначала происходило добавление двух чисел, следовало поступить иначе. Для этого используются круглые скобки, которые отвечают за смещение приоритетов в математической формуле. Исправленный пример должен выглядеть так:
(3 + 5) * 6
3 + 5, заключенные в скобки, дадут желаемый результат, а именно 48.
Ошибки в процессе выполнения
Как и семантические, ошибки во время выполнения никогда не обнаруживаются при компиляции. В отличие от семантических ошибок, эти прерывают программу и препятствуют ее дальнейшему выполнению. Они обычно вызваны неожиданным результатом некоторых вычислений в исходном коде.
Вот хороший пример:
input = 25 x = 0.8/(Math.sqrt(input) - 5)
Фрагмент кода выше будет скомпилирован успешно, но input 25 приведет к ZeroDivisionError. Это ошибка во время выполнения. Другим популярным примером является StackOverflowError или IndexOutofBoundError. Важно то, что вы идентифицируете эти ошибки и узнаете, как с ними бороться.
Существуют ошибки, связанные с тем, как ваш исходный код использует память и пространство на платформе или в среде, в которой он запущен. Они также являются ошибками во время выполнения. Такие ошибки, как OutOfMemoryErrorand и HeapError обычно вызваны тем, что ваш исходный код использует слишком много ресурсов. Хорошее знание алгоритмов поможет написать код, который лучше использует ресурсы. В этом и заключается отладка программы.
Процесс перезаписи кода для повышения производительности называется оптимизацией. Менее популярное наименование процесса – рефакторинг. Поскольку вы тратите больше времени на кодинг, то должны иметь это в виду.
Отладка программы
Вот несколько советов о том, как правильно выполнять отладку:
- Использовать Linters. Linters – это инструменты, которые помогают считывать исходный код, чтобы проверить, соответствует ли он ожидаемому стандарту на выбранном языке программирования. Существуют линты для многих языков.
- Превалирование IDE над простыми редакторами. Вы можете выбрать IDE, разработанную для языка, который изучаете. IDE – это интегрированные среды разработки. Они созданы для написания, отладки, компиляции и запуска кода. Jetbrains создают отличные IDE, такие как Webstorm и IntelliJ. Также есть NetBeans, Komodo, Qt, Android Studio, XCode (поставляется с Mac), etc.
- Чтение кода вслух. Это полезно, когда вы ищете семантическую ошибку. Читая свой код вслух, есть большая вероятность, что вы зачитаете и ошибку.
- Чтение логов. Когда компилятор отмечает Error, обязательно посмотрите, где он находится.
Двигаемся дальше
Поздравляем! Слово «ошибка» уже привычно для вас, равно как и «отладка программы». В качестве новичка вы можете изучать кодинг по книгам, онлайн-урокам или видео. И даже чужой код вам теперь не страшен 
В процессе кодинга измените что-нибудь, чтобы понять, как он работает. Но будьте уверены в том, что сами написали.
Викторина
- Какая ошибка допущена в фрагменте кода Python ниже?
items = [0,1,2,3,4,5] print items[8] //комментарий: элементы здесь представляют собой массив с шестью элементами. Например, чтобы получить 4-й элемент, вы будете использовать [3]. Мы начинаем отсчет с 0.
- Какая ошибка допущена в фрагменте кода Python ниже?
input = Hippo' if input == 'Hippo': print 'Hello, Hippo'
Ответы на вопросы
- Ошибка выполнения: ошибка индекса вне диапазона.
2. Синтаксическая ошибка: Отсутствует стартовая кавычка в первой строке.
Добавлено 30 мая 2021 в 17:27
В уроке «3.1 – Синтаксические и семантические ошибки» мы рассмотрели синтаксические ошибки, которые возникают, когда вы пишете код, который не соответствует грамматике языка C++. Компилятор уведомит вас об ошибках этого типа, поэтому их легко обнаружить и обычно легко исправить.
Мы также рассмотрели семантические ошибки, которые возникают, когда вы пишете код, который выполняет не то, что вы планировали. Как правило, компилятор не обнаруживает семантических ошибок (хотя в некоторых случаях умные компиляторы могут генерировать предупреждения).
Семантические ошибки могут вызывать большинство из симптомов неопределенного поведения, например, приводить к тому, что программа выдает неправильные результаты, быть причиной неустойчивого поведения, искажать данные программы, вызывать сбой программы – или они могут вообще никак не влиять.
При написании программ семантические ошибки практически неизбежны. Некоторые из них вы, вероятно, заметите, просто используя программу: например, если вы писали игру лабиринт, а ваш персонаж может проходить сквозь стены. Тестирование вашей программы (7.12 – Введение в тестирование кода) также может помочь выявить семантические ошибки.
Но есть еще одна вещь, которая может помочь – это знание того, какой тип семантических ошибок наиболее распространен, чтобы вы могли потратить немного больше времени на то, чтобы убедиться, что в этих случаях всё правильно.
В этом уроке мы рассмотрим ряд наиболее распространенных типов семантических ошибок, возникающих в C++ (большинство из которых так или иначе связаны с управлением порядком выполнения программы).
Условные логические ошибки
Один из наиболее распространенных типов семантических ошибок – это условная логическая ошибка. Условная логическая ошибка возникает, когда программист неправильно пишет логику условного оператора или условия цикла. Вот простой пример:
#include <iostream>
int main()
{
std::cout << "Enter an integer: ";
int x{};
std::cin >> x;
if (x >= 5) // упс, мы использовали operator>= вместо operator>
std::cout << x << " is greater than 5";
return 0;
}А вот результат запуска программы, при котором была обнаружена эта условная логическая ошибка:
Enter an integer: 5
5 is greater than 5Когда пользователь вводит 5, условное выражение x >= 5 принимает значение true, поэтому выполняется соответствующая инструкция.
Вот еще один пример для цикла for:
#include <iostream>
int main()
{
std::cout << "Enter an integer: ";
int x{};
std::cin >> x;
// упс, мы использовали operator> вместо operator<
for (unsigned int count{ 1 }; count > x; ++count)
{
std::cout << count << ' ';
}
return 0;
}Эта программа должна напечатать все числа от 1 до числа, введенного пользователем. Но вот что она на самом деле делает:
Enter an integer: 5Она ничего не напечатала. Это происходит потому, что при входе в цикл for условие count > x равно false, поэтому цикл вообще не повторяется.
Бесконечные циклы
В уроке «7.7 – Введение в циклы и инструкции while» мы рассмотрели бесконечные циклы и показали этот пример:
#include <iostream>
int main()
{
int count{ 1 };
while (count <= 10) // это условие никогда не будет ложным
{
std::cout << count << ' '; // поэтому эта строка выполняется многократно
}
return 0; // эта строка никогда не будет выполнена
}В этом случае мы забыли увеличить count, поэтому условие цикла никогда не будет ложным, и цикл продолжит печатать:
1 1 1 1 1 1 1 1 1 1пока пользователь не закроет программу.
Вот еще один пример, который преподаватели любят задавать в тестах. Что не так со следующим кодом?
#include <iostream>
int main()
{
for (unsigned int count{ 5 }; count >= 0; --count)
{
if (count == 0)
std::cout << "blastoff! ";
else
std::cout << count << ' ';
}
return 0;
}Эта программа должна напечатать «5 4 3 2 1 blastoff!«, что она и делает, но не останавливается на достигнутом. На самом деле она печатает:
5 4 3 2 1 blastoff! 4294967295 4294967294 4294967293 4294967292 4294967291а затем просто продолжает печатать уменьшающиеся числа. Программа никогда не завершится, потому что условие count >= 0 никогда не может быть ложным, если count является целым числом без знака.
Ошибки на единицу
Ошибки «на единицу» возникают, когда цикл повторяется на один раз больше или на один раз меньше, чем это необходимо. Вот пример, который мы рассмотрели в уроке «7.9 – Инструкции for»:
#include <iostream>
int main()
{
for (unsigned int count{ 1 }; count < 5; ++count)
{
std::cout << count << ' ';
}
return 0;
}Этот код должен печатать «1 2 3 4 5«, но он печатает только «1 2 3 4«, потому что был использован неправильный оператор отношения.
Неправильный приоритет операторов
Следующая программа из урока «5.7 – Логические операторы» допускает ошибку приоритета операторов:
#include <iostream>
int main()
{
int x{ 5 };
int y{ 7 };
if (!x > y)
std::cout << x << " is not greater than " << y << 'n';
else
std::cout << x << " is greater than " << y << 'n';
return 0;
}Поскольку логическое НЕ имеет более высокий приоритет, чем operator>, условное выражение вычисляется так, как если бы оно было написано (!x) > y, что не соответствует замыслу программиста.
В результате эта программа печатает:
5 is greater than 7Это также может произойти при смешивании в одном выражении логического ИЛИ и логического И (логическое И имеет больший приоритет, чем логическое ИЛИ). Используйте явные скобки, чтобы избежать подобных ошибок.
Проблемы точности с типами с плавающей запятой
Следующая переменная с плавающей запятой не имеет достаточной точности для хранения всего числа:
#include <iostream>
int main()
{
float f{ 0.123456789f };
std::cout << f;
}Как следствие, эта программа напечатает:
0.123457В уроке «5.6 – Операторы отношения и сравнение чисел с плавающей запятой» мы говорили о том, что использование operator== и operator!= может вызывать проблемы с числами с плавающей запятой из-за небольших ошибок округления (а также о том, что с этим делать). Вот пример:
#include <iostream>
int main()
{
// сумма должна быть равна 1.0
double d{ 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 };
if (d == 1.0)
std::cout << "equal";
else
std::cout << "not equal";
}Эта программа напечатает:
not equalЧем больше вы выполняете арифметических действий с числом с плавающей запятой, тем больше в нем накапливаются небольшие ошибки округления.
Целочисленное деление
В следующем примере мы хотим выполнить деление с плавающей запятой, но поскольку оба операнда принадлежат целочисленному типу, вместо этого мы выполняем целочисленное деление:
#include <iostream>
int main()
{
int x{ 5 };
int y{ 3 };
std::cout << x << " divided by " << y << " is: " << x / y; // целочисленное деление
return 0;
}Этот код напечатает:
5 divided by 3 is: 1В уроке «5.2 – Арифметические операторы» мы показали, что мы можем использовать static_cast для преобразования одного из целочисленных операндов в значение с плавающей запятой, чтобы выполнять деление с плавающей запятой.
Случайные пустые инструкции
В уроке «7.3 – Распространенные проблемы при работе с операторами if» мы рассмотрели пустые инструкции, которые ничего не делают.
В приведенной ниже программе мы хотим взорвать мир, только если у нас есть разрешение пользователя:
#include <iostream>
void blowUpWorld()
{
std::cout << "Kaboom!n";
}
int main()
{
std::cout << "Should we blow up the world again? (y/n): ";
char c{};
std::cin >> c;
if (c=='y'); // здесь случайная пустая инструкция
blowUpWorld(); // поэтому это всегда будет выполняться, так как это не часть оператора if
return 0;
}Однако из-за случайной пустой инструкции вызов функции blowUpWorld() выполняется всегда, поэтому мы взрываем независимо от ввода:
Should we blow up the world again? (y/n): n
Kaboom!Неиспользование составной инструкции, когда она требуется
Еще один вариант приведенной выше программы, которая всегда взрывает мир:
#include <iostream>
void blowUpWorld()
{
std::cout << "Kaboom!n";
}
int main()
{
std::cout << "Should we blow up the world again? (y/n): ";
char c{};
std::cin >> c;
if (c=='y')
std::cout << "Okay, here we go...n";
blowUpWorld(); // упс, всегда будет выполняться. Должно быть внутри составной инструкции.
return 0;
}Эта программа печатает:
Should we blow up the world again? (y/n): n
Kaboom!Висячий else (рассмотренный в уроке «7.3 – Распространенные проблемы при работе с операторами if») также попадает в эту категорию.
Что еще?
Приведенные выше примеры представляют собой хороший образец наиболее распространенных типов семантических ошибок, которые склонны совершать на C++ начинающие программисты, но их гораздо больше. Читатели, если у вас есть дополнительные примеры, которые, по вашему мнению, являются распространенными ошибками, напишите об этом в комментариях.
Теги
C++ / CppLearnCppДля начинающихОбучениеПрограммирование
Семантические ошибки в программировании
Ранее я рассказывал о видах ошибок в программировании. И там я упомянул об ошибках, которые я назвал логическими. Но вообще такие ошибки часто называют семантическими. И это самые труднонаходимые ошибки, которые доставляют программистам больше всего неприятностей. Поэтому я решил рассказать о них отдельно.
Семантика — это раздел лингвистики (науки о языках), который изучает смысловое значение частей языка (слов, предложений и т.п.).
Поскольку языки программирования — это тоже языки, то и правила и термины лингвистики точно также применимы и к языкам программирования. А семантика в языке программирования означает то же самое, что и в человеческом языке, например, в русском.
Семантика определяет смысл программы, а семантические ошибки связаны с нарушением смысла программы. То есть семантические ошибки нарушают логику программы (поэтому я и назвал их ранее логическими).
С точки зрения синтаксиса программа может быть безупречной. И даже во время выполнения в ней может не быть никаких ошибок. Но при этом она может быть бессмысленна с точки зрения решаемой задачи.
Например, вам надо было написать программу, которая вычисляет площадь круга. А вы “немного” ошиблись, и ваша программа вычисляет площадь прямоугольника.
При этом:
- Программа компилируется без ошибок
- Программа запускается, работает и завершается без ошибок
- Программа получает данные, обрабатывает их и выдаёт результат
Но, что самое страшное — пользователь думает, что результат правильный!!!
То есть программа безупречна во всём. Кроме одного — она решает не ту задачу, которую нужно решить пользователю. Поэтому с точки зрения пользователя она бессмысленна.
А с точки зрения программиста она содержит семантическую ошибку.
Такая программа делает не то, что вы от неё хотели, а то, что вы ей сказали. Вы ей сказали вычислять площадь прямоугольника, и она делает это. И это не её вина, а ваша. Вы дали неправильное указание.
Кстати, плохие руководители в жизни ведут себя точно также — дают сотрудникам неправильные или неоднозначные распоряжения, а потом удивляются, что работа выполнена неправильно. И обвиняют в этом, конечно, сотрудников.
Находить семантические ошибки бывает очень трудно. Особенно в чужих программах. Я это знаю не понаслышке. Иногда на это уходит несколько дней или даже недель. Иногда вообще хочется плюнуть на это и написать новую программу.
Так что старайтесь ещё до того, как начнёте писать код, тщательно продумать алгоритмы и прочие способы решения задачи, чтобы потом не было мучительно больно при поиске таких ошибок, которые не видит компилятор, и мучительно стыдно перед заказчиком.
А на сегодня всё. Подключайтесь к каналу в Телеграм или к другим моим группам, чтобы ничего не пропустить.
|
|
Основы программирования Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать. Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь. Подробнее… |
21
программы на этом тесте проявилась аналогичная ошибка, и только затем проводить бумажное тестирование.
Пример 1.6. Пусть проводится бумажное тестирование для алгоритма (1.7) на те сте № 1 из табл. 1.1. Для отслеживания изменений переменных построим табл. 1.5.
Таблица 1.5
|
Номер шага |
A |
b |
c |
p |
S |
||
|
1 |
–3 |
1 |
1 |
–0.5 |
|||
|
2 |
–3 |
1 |
1 |
–0.5 |
|||
|
− 0.8125 |
|||||||
Отрицательное число под квадратным корнем фиксирует ошибку.
Конец примера.
Многие трансляторы позволяют выполнять программу в режиме так называемой пошаговой отладки, при этом на каждом шаге вычислений можно увидеть значения переменных. И тогда можно постоянно сравнивать значения переменных, получен ные в ходе бумажного тестирования, со значениями, полученными на компьютере. Такой процесс фактически является пошаговым тестированием по методу белого ящика.
Если ошибка зафиксирована при выполнении теста большой размерности, то по шаговая отладка практически невозможна – она потребовала бы гигантских усилий. В этом случае перед локализацией ошибки следует подобрать такой тест минималь ной размерности, при выполнении которого проявляется в точности такая же ошибка.
Все эти средства позволяют локализовать ошибку, но не могут ответить на во прос, в чем ее причина. А вот поиск истинной причины ошибки бывает непростым делом, нередко для этого требуется полностью переосмыслить алгоритм. Как раз здесь больше всего сказывается квалификация и опыт программиста: бывает, то, на что у начинающего программиста уходит несколько дней, у профессионала занимает несколько минут. При устранении ошибки также сказывается квалификация програм миста, так как иногда для этого приходится полностью переписывать весь алгоритм. И это еще не все: после внесения любых исправлений в программу нет никакой га рантии, что в ней не появились другие (новые!) ошибки. Поэтому необходимо прове сти повторное тестирование программы даже на тех тестах, которые ранее давали правильные результаты.
Итак, полностью отлаженной можно считать такую программу, которая де монстрирует правильное выполнение всех ранее разработанных тестов. При этом для большей уверенности в правильности программы, прошедшей тестовые испытания, для разработки тестов должны применяться методы как черного, так и белого ящика.
Тем не менее, полной гарантии, что в отлаженной программе отсутствуют ошиб ки, нет: закон Э.Дейкстры верен!
22
Вопросы и задания
1.Какими свойствами должен обладать алгоритм? В чем смысл этих свойств?
2.Для чего необходим специальный язык программирования?
3.Что такое синтаксическая и что такое семантическая ошибка в алгоритме? Как и когда они обнаруживаются?
4.Почему невозможно, как правило, исчерпывающее тестирование?
5.В чем состоит цель тестирования?
6.Почему тестированием нельзя доказать отсутствие ошибок в программе?
7.Что такое множество входов, множество выходов, область входов и область выходов в ал горитме?
8.Как область входов и область выходов делятся на подобласти эквивалентности?
9.Как тестировать алгоритм по методу черного ящика для данных большой размерности?
10.Как выбирать тесты по методу белого ящика для последовательного, ветвящегося и цик лического алгоритма?
11.Как выбрать тесты по методу белого ящика для алгоритма, состоящего из последователь ности k ветвящихся алгоритмов (if-then-else)?
12.Как выбрать тесты по методу белого ящика для алгоритма, состоящего из последователь ности k циклических алгоритмов (while-do)?
13.В чем состоит задача отладки?
14.Как выполнять пошаговое тестирование?
15.Что делать, если ошибка в выходных данных обнаружена при работе алгоритма на тесте очень большой размерности?
16.Алгоритм вычисляет максимальное значение среди массива целых чисел. Разработать те сты по методу черного ящика.
17.Написать алгоритм, вычисляющий максимальное значение среди массива целых чисел. Разработать тесты по методу белого ящика.
18.Алгоритм возводит целое число n в целую степень m и выдает результат, присваивае мый переменной типа integer. Разработать тесты по методу черного ящика. Каков бу дет результат при n = 8 и m = 5?
19. Написать алгоритм, возводящий целое число n в целую степень m. Разработать тесты по методу белого ящика.
20.Написать алгоритм, который вводит три вещественных числа, проверяет, может ли суще ствовать треугольник со сторонами, равными этим числам. Если не может, то выдает со общение об этом и просит ввести данные повторно. Если может, то вычисляет и выводит площадь треугольника. Оформить алгоритм в виде программы на Паскале. Разработать те сты по методу черного ящика и по методу белого ящика, протестировать программу на объединенных тестах.
21.Написать программу, которая вводит размер n массива X, (n≤10000) генерирует слу чайные целочисленные значения в массиве X, после чего выполняет алгоритм (1.8) (упо
23
рядочения) и проверяет правильность результата. Разработать тесты по методам черного и белого ящика, протестировать программу на объединенных тестах.
Глава 2 Доказательство правильности алгоритмов
2.1 Принципы аналитического доказательства
Казалось бы, выхода нет, и мы должны смириться с тем, что в любой программе всегда есть необнаруженные ошибки. Но Э.Дейкстрой и рядом других великих про граммистов был разработан аналитический метод доказательства правильности алго ритмов, который позволяет проверить правильность алгоритма не для одного кон кретного набора входных значений, как при тестировании, а для любого количества наборов входных значений. Поэтому такой метод в принципе может решить пробле му правильности алгоритмов.
Идея доказательства правильности заключается в следующем. Любой алгоритм в процессе своего исполнения использует и изменяет значения переменных. Для таких переменных составляют два логических условия, называемых предусловием и посту словием. Предполагается, что предусловие должно быть истинным перед исполнени ем алгоритма, а постусловие – после исполнения.
Доказательство правильности содержит два этапа:
1)доказательство завершимости алгоритма, т.е. доказательство того, что при любых значениях переменных на входе алгоритма он когда-нибудь обязательно за кончит свое выполнение;
2)доказательство истинности постусловия после завершения алгоритма при предположении истинности предусловия перед исполнением алгоритма.
Для проведения доказательства следует знать свойства отдельных операторов ал горитма, которые определяются языком программирования.
Доказательство завершимости нередко бывает очевидным, если, например, алго ритм состоит из последовательности присваиваний или из цикла for. Если же пере
менные, входящие в условие цикла while, изменяются сложным образом, то дока зательство завершимости будет не простым. В любом случае необходимо опреде лить, при каком условии алгоритм завершится: это условие будет частью постусло вия.
Доказательство истинности постусловия после завершения алгоритма, как прави ло, далеко не очевидно. Для проведения такого доказательства используют следую щие специальные методы:
25
1)последовательное перечисление выполняемых действий, применяется для по следовательных алгоритмов, когда по ходу исполнения операторов отслеживают из менение логических соотношений;
2)перечисление вариантов, применяется для ветвящихся алгоритмов, когда вся область значений переменных, входящих в предусловие, разбивается на подобласти,
идля каждой подобласти доказательство проводится отдельно;
3)метод математической индукции, применяется для циклической структуры алгоритма, этот метод является стандартным для математических доказательств;
4)инвариант, также применяется для циклической структуры алгоритма, когда из предусловия и постусловия выделяется общая, неизменяемая часть;
5)метод эквивалентов используют, когда есть два разных алгоритма с одина ковыми пред- и постусловиями, и для доказательства правильности второго алгорит ма доказывают правильность первого алгоритма и эквивалентность первого и второ го алгоритмов;
6)абстракция, применяется при доказательстве сложных алгоритмов, когда не возможно провести доказательство сразу для всего алгоритма.
Применение различных методов доказательства рассмотрим на нескольких про стых примерах.
Пример 2.1.
Пусть для числовых переменных x,y выполнено предусловие x=a, y=b, где a, b – некоторые числовые значения. В записи условия запятая подразумевает логи ческую связку «и». Требуется доказать, что после выполнения алгоритма (2.1):
будет справедливым постусловие x=b, y=a.
Доказательство. Завершимость алгоритма очевидна. Доказательство истинности постусловия проведем последовательным перечислением выполняемых действий. После первого присваивания текущее условие: x=a, y=b, z=b, после второго: x=a, y=a, z=b, после третьего: x=b, y=a, z=b, что и требовалось доказать.
Конец примера.
Пример 2.2. Пусть для числовых переменных x,y выполнено предусловие x=a, y=b, где a, b – некоторые числовые значения. Требуется доказать, что после выполнения алгоритма (2.2)
|
if x<y then |
||
|
begin |
(2.2) |
|
|
z:=y; y:=x; x:=z |
||
|
end |
26
будет справедливым постусловие x≥y.
Доказательство. Завершимость алгоритма очевидна. Доказательство проведем перечислением двух вариантов:
1)x≥y; условие оператора if будет ложным, поэтому больше никаких дей ствий в алгоритме выполняться не будет; из этого условия и предусловия следует справедливость постусловия;
2)x<y; условие оператора if будет истинным, поэтому в алгоритме будут вы
полнены присваивания, в результате которых, как доказано в примере 2.1, перемен ные x и y обменяются своими значениями, что приведет к смене условия x<y на противоположное, т.е. на x≥y.
Конец примера.
Доказательство правильности – мощное средство для обнаружения ошибок в ал горитме. Предположим, что алгоритм (2.1) записан в виде двух присваиваний: x:=y; y:=x. Тогда после первого присваивания: x=b, y=b, после второго ниче го не изменилось: x=b, y=b. Последнее условие не совпадает с требуемым посту словием, т.е. в алгоритме ошибка!
А теперь рассмотрим метод математической индукции. Метод позволяет доказы вать утверждение, зависящее от параметра индукции – некоторой целочисленной переменной. Утверждение доказывается для всех значений параметра, бóльших или равных некоторому начальному значению.
Доказательство методом математической индукции содержит три этапа: 1) базис, 2) предположение, 3) индуктивный вывод.
На этапе базиса проверяют, что доказываемое утверждение P(n) относительно параметра индукции n справедливо при n = n0.
На втором этапе делается предположение, что утверждение P(n) справедливо для всех значений n, не бóльших, чем некоторое k, k ≥ n ≥ n0.
Наконец, на этапе индуктивного вывода доказывается, что P(n) будет спра ведливо при n = k + 1 > n0. Из этого следует, что утверждение P(n) справедливо для
любого n ≥ n0.
Покажем это для n = M, таком, что M > n0. Вначале положим k = n0. Согласно третьему этапу доказательства утверждение будет справедливо при n = n0 + 1. При менив еще раз третий этап доказательства при n = n0 + 1, получим справедливость утверждения P(n) при n = n0 + 2 и т.д., пока не дойдем до n = M.
Метод математической индукции широко используется в математике для доказа тельства самых разных логических утверждений. Рассмотрим несколько различных примеров его применения.
Пример 2.3. Докажем, что для вычисления суммы квадратов чисел от 1 до n: S = 12 + 22 + … + n2
27
справедлива формула
|
Sn |
= |
2n3 |
+ 3n2 |
+ n |
(2.1) |
|
6 |
|||||
Доказательство.
Базис. При n = 0 сумма Sn = 0, с другой стороны, при n = 0 формула (2.1) вер
на.
Предположение. Пусть при n ≥ 0 формула (2.1) верна. Вывод. При n + 1 по формуле (2.1) получаем:
|
S |
n+1 |
= |
2n3 + 3n2 + n |
+ (n + 1)2 |
= |
2(n + 1)3 + 3(n + 1)2 + (n + 1) |
. |
|
6 |
6 |
||||||
Конец примера.
Проиллюстрируем применение метода математической индукции на примере ал горитма вычисления факториала.
Пример 2.4. Пусть выполнено предусловие n=M, M≥1. Требуется доказать, что после выполнения алгоритма (2.3) будет справедливо постусловие:
f=1*2*…*M.
|
f:=1; i:=2; |
|||
|
while i<=n do |
(2.3) |
||
|
begin f:=f*i; |
|||
|
i:=i+1 |
|||
|
end |
|||
|
Доказательство. Завершимость алгоритма очевидна, |
так как переменной i |
перед выполнением цикла присваивается 2, а при каждом исполнении цикла она уве личивается на 1. Поэтому через n-1 исполнение цикла переменная i будет равна n+1, и условие в заголовке цикла станет ложным. Справедливость постусловия до
кажем методом математической индукции.
Базис. Если M=1, то переменная f будет равна 1, так как цикл ни разу не будет
выполняться. Таким образом, базис справедлив.
Предположение. Предполагаем, что при M=k, k≥1 справедливо постусловие
f=1*2*…*k.
Индуктивный вывод. Все отличие выполнения алгоритма при M=k+1 от выпол нения при M=k состоит в том, что вначале алгоритм выполнится в точности так же, как при M=k, а затем цикл будет исполнен еще один раз для i=k+1. Так как по предположению, перед последним выполнением цикла f=1*2*…*k, то после по следнего выполнения цикла (после исполнения оператора f:=f*i) переменная f будет равна f=1*2*…*k*(k+1)=1*2*…*M, что и требовалось доказать.
Конец примера.
28
Метод доказательства с помощью инварианта состоит в следующем. Пусть предусловие записано как (P and Q), а постусловие – как (S and Q), т.е. в них имеется общая часть Q, называемая инвариантом. Доказательство состоит в про верке истинности инварианта после выполнения алгоритма. Обычно инвариант при меняют при доказательстве правильности оператора цикла. При этом требуется дока зать, что однократное исполнение цикла сохраняет истинность инварианта. Тогда, с учетом завершимости цикла, будет следовать истинность инварианта после завер шения цикла. Вообще говоря, строгое доказательство корректности самого метода инварианта можно провести методом математической индукции, но так как это дока зательство тривиально, мы его оставим в качестве упражнения.
Рассмотрим применение инварианта на предыдущем примере.
Пример 2.5. Пусть выполнено предусловие n=M, M≥1. Требуется доказать, что после выполнения алгоритма (2.3) будет справедливым постусловие:
f=1*2*…*M.
Доказательство. Завершимость алгоритма доказана в примере 2.4, отметим лишь, что после окончания выполнения цикла i=n+1.
После выполнения присваиваний в первой строчке алгоритма предусловие для оператора цикла станет таким: n=M, M≥1, i=2, f=1. Последнее равенство запи шем в виде: f=1*…*(i-1). Постусловие запишем в виде: n=M, M≥1, i=n+1, f=1*…*(i-1). Первые два равенства в постусловии очевидны (n и M не изменяются), справедливость равенства i=n+1 была доказана. Осталось доказать справедливость последнего равенства f=1*…*(i-1), которое здесь и является
инвариантом. Действительно, непосредственной проверкой операторов в алгоритме убеждаемся, что выполнение двух действий в теле цикла изменяет переменные f и i, но оставляет инвариант справедливым.
Конец примера.
Самое главное в доказательстве методом инварианта – умение формулировать условие в виде инварианта, что требует некоторого навыка. В то же время использо вание инварианта обычно упрощает доказательство алгоритма.
Применение метода эквивалентов будет рассмотрено в разделе 2.2, а метода аб стракции для доказательства правильности сложных алгоритмов – в разделе 2.3.
На практике аналитическое доказательство не заменяет, а дополняет компьютер ное тестирование. Имеется ряд причин, по которым нельзя ограничиться только ана литическим доказательством.
Во-первых, очень трудно учесть все ограничения, связанные с конкретным пред ставлением данных (особенно целых и вещественных чисел) в компьютере, что уже было отмечено в разделе 1.3.
29
Во-вторых, при выполнении реального алгоритма на компьютере трудно заранее учесть все нюансы взаимодействия алгоритма со стандартными программами и опе рационной системой.
В-третьих, в доказательстве могут быть ошибки!
Поэтому только при сочетании тестирования и аналитического доказательства правильности можно добиться того, чтобы алгоритм был практически безошибоч ным. На самом деле наибольшая практическая польза от доказательства состоит в том, что оно заставляет программиста писать ясные и понятные алгоритмы, в кото рых в принципе будет меньше ошибок, чем при написании алгоритмов методом «как получится».
2.2 Доказательство правильности простых алгоритмов
Рассмотрим правила построения пред- и постусловий для основных типов струк тур алгоритмов и операторов языка программирования. Обозначим через S некото рый алгоритм, через P – предусловие, а через R – постусловие для него. Сокращен но мы это будем записывать так:
Присваивание. Если имеется некоторое условие P(x), в запись которого входит переменная x, то
|
{P(w)} x:=w {P(x)}, |
(2.3) |
где P(w) есть то же самое условие, что и P(x), в котором каждое вхождение пере менной x заменено правой частью присваивания w.
Последовательный алгоритм. Если S1 и S2 – операторы, для которых выпол няются условия
|
{P} S1 {Q} |
и {Q} S2 {R}, |
(2.4) |
||
|
то |
||||
|
{P} S2; |
S2 {R}. |
(2.5) |
||
|
Ветвящийся алгоритм. Если |
S1 |
и |
S2 – операторы, для которых выполняются |
|
|
условия |
{P, not B} S1 {Q}, |
|||
|
{P, B} S1 {Q} |
и |
(2.6) |
||
|
то |
||||
|
{P} if B then S1 else S2 {Q}. |
(2.7) |
|||
|
Если к тому же S2 – пустой оператор, то |
||||
|
{P} if B then S1 {Q}. |
(2.8) |
Циклический алгоритм. Если S – оператор, для которого выполняется условие
|
30 |
|
|
{P, B} S { P }, |
(2.9) |
|
то |
|
|
{P} while B do S { P, not B }. |
(2.10) |
Условие P здесь является инвариантом цикла.
Правильность рассмотренных соотношений следует из смысла операторов языка Паскаль. Применение правил (2.2) – (2.10) полезно при выводе пред- и постусловий для рассмотренных операторов.
А теперь рассмотрим применение метода эквивалентов. Для алгоритмов эквива лентность можно доказывать относительно некоторых, общих для обоих алгоритмов переменных.
Пример 2.6. Докажем эквивалентность алгоритмов (2.3) и (2.4) относительно
|
переменной f. А именно, докажем, что для обоих алгоритмов при любом |
n≥0 зна |
||
|
чения переменной f будут одинаковы после завершения алгоритмов. |
|||
|
f:=1; |
|||
|
for i:=2 to n do |
(2.4) |
||
|
f:=f*i |
Доказательство. Вначале докажем, что циклы в обоих алгоритмах выполнятся одинаковое число раз. Для алгоритма (2.4) цикл for при границах изменения пара метра цикла от 2 до n≥0 исполнится ровно n-1 раз. Для алгоритма (2.3) до выпол нения цикла i=2, а при каждом выполнении после всех других действий в конце цикла i увеличивается на единицу. Поэтому цикл закончится после того, как i=n+1, т.е. цикл проработает также n-1 раз.
А теперь докажем, что после завершения алгоритмов переменные f в обоих ал горитмах будут равны. Действительно, в обоих алгоритмах переменные f перевы числяются одинаковыми операторами, в которых переменные i равны между собой.
Легко доказать методом математической индукции, что тогда при любом (одинако вом для обоих алгоритмов) значении n переменные f также будут иметь одина
ковые значения.
Конец примера.
Рассмотренный пример является частным случаем эквивалентности операторов цикла while и for. Рассмотрим общие случаи эквивалентности.
Эквивалентность последовательной структуры алгоритма. Если S1 и S2 – алгоритмы, в которых используются различные переменные, то эквивалентны по следовательности
Эквивалентность операторов цикла. Если S – оператор, не изменяющий пере менную i, то эквивалентны циклы
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #