Лабораторная работа № 20 (к § 48) Исследование алгоритмов и программ

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

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

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

План исследования алгоритма и программы

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

Разбор задач

Задача 1. Для алгоритма поиска максимального элемента выполнить трассировку на последовательности 7, 3, 9, 9, 2 и записать изменения переменной максимума. Предположим, что сначала максимумом объявляют первый элемент, затем сравнивают с ним остальные. Нужно проследить каждое сравнение и убедиться, что итоговое значение действительно наибольшее.

1. Начальное значение максимума — 7. Первый элемент уже учтён, поэтому цикл начинает проверку со второго.
2. Сравниваем 3 с 7: условие «элемент больше максимума» ложно, значение остаётся 7.
3. Сравниваем 9 с 7: условие истинно, максимум становится 9. Следующее число 9 не больше текущего максимума, поэтому он не меняется.
4. Последнее число 2 также не превышает 9. После завершения цикла максимум равен 9.

Ответ: значения переменной максимума после обработки элементов — 7, 7, 9, 9, 9. Равный текущему максимуму элемент не меняет значение переменной, а проверка всех элементов подтверждает итог.

Задача 2. Проверить программу, которая определяет, является ли число простым, на единице, нуле, отрицательном числе, простых и составных числах; найти возможный сбой. Число простое, если оно больше 1 и имеет ровно два натуральных делителя. Это определение сразу подсказывает, что проверять только делимость на несколько чисел недостаточно: нужно отдельно обработать значения меньше 2.

1. Составьте набор: −3, 0, 1, 2, 7, 9. Это отрицательное число, ноль, единица, простые числа и составное число.
2. Запустите программу на каждом входе и сопоставьте ответы с определением: 2 и 7 простые, остальные числа в наборе не простые.
3. Если программа проверяет делители циклом, но не отсекает числа меньше 2, изучите результат для 1. При цикле, начинающемся с 2 и не выполняющемся для 1, программа может ошибочно сообщить, что 1 простое.
4. Зафиксируйте этот вход и неверный ответ как контрпример, затем исправьте проверку и повторите весь набор тестов.

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

Задача 3. Сравнить два алгоритма сортировки на массивах разных размеров и с разным порядком элементов. Цель — не просто определить победителя на одном запуске, а выяснить, как меняется работа алгоритмов в разных условиях. Для честности подают одинаковые копии массива, а результат каждого измерения записывают.

1. Подготовьте массивы малого и большого размера: уже упорядоченный, обратный и случайный. Одинаковые исходные данные нужны, чтобы сравнение не зависело от сложности разных наборов.
2. Запустите обе сортировки на каждом массиве и проверьте правильность результата: элементы должны идти в нужном порядке, а их состав — сохраниться.
3. Измерьте число сравнений или время работы. Повторите измерения, особенно если сравнивается время, поскольку на него влияют случайные колебания и условия запуска.
4. Сопоставьте результаты по размеру и порядку данных; отдельно отметьте затраты памяти, если они важны для задачи.

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

Типичные ошибки

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

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

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

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

Связь с другими темами

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

Что запомнить

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