Анализ алгоритмов. Определение возможных результатов работы алгоритма при заданном множестве входных данных

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

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

• Алгоритм — это конечная последовательность действий, приводящая от входных данных к результату.
• Результат работы алгоритма зависит от входных данных: разные входные данные могут давать разные результаты.
• Множество возможных результатов — это все результаты, которые алгоритм может выдать для всех допустимых входных данных.
• Анализ алгоритма позволяет определить, какие результаты возможны, а какие — нет, без фактического выполнения алгоритма.
• Для детерминированного алгоритма при одинаковых входных данных результат всегда одинаков.
• Алгоритм может быть недетерминированным, если результат зависит от случайных факторов, но в школьном курсе обычно рассматриваются детерминированные алгоритмы.
• Чтобы определить возможные результаты, нужно рассмотреть все допустимые входные данные и проследить, как алгоритм преобразует их в результат.

Алгоритм

Точное и понятное предписание исполнителю выполнить конечную последовательность действий для достижения поставленной цели.

Входные данные

Информация, которую алгоритм получает для обработки.

Выходные данные (результат)

Информация, которую алгоритм выдаёт после обработки входных данных.

Множество возможных результатов

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

Детерминированный алгоритм

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

Анализ алгоритма

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

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

1. Пример 1расчёт

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

   Решение

   • если входное число x >= 0, то результат равен x, иначе результат равен -x
   • Для входных данных {-3, 0, 5} возможные результаты: {3, 0, 5}
2. Пример 2случай

   Алгоритм определения чётности числа

   Пояснение

   • если число делится на 2, то результат 'чётное', иначе 'нечётное'
   • Для входных данных {1, 2, 3, 4} возможные результаты: {'нечётное', 'чётное'}
3. Пример 3случай

   Алгоритм нахождения максимального из двух чисел

   Пояснение

   • если a > b, то результат a, иначе b
   • Для входных данных (1, 2), (5, 5), (7, 3) возможные результаты: {2, 5, 7}

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

• Алгоритмы и исполнители (7 класс)
• Основные алгоритмические конструкции (8 класс)
• Программирование на языке Паскаль (8 класс)