ИНФОРМАТИКА · 10 КЛАСС
Введение · Интерактивный конспект

§ 1. Алгоритм и его свойства

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

Попробовать на модели ↓
Разбираемся в теме

Основные пункты параграфа

1

Понятие алгоритма

Алгоритм — точно определённая система понятных исполнителю предписаний.

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Алгоритм Евклида по шагам

Задайте два натуральных числа и выполняйте шаги: остаток r = a mod b, затем a := b и b := r. Каждый шаг — отдельное действие по точному правилу; когда b станет равным 0, в a — наибольший общий делитель. Для любых допустимых чисел способ один и тот же.

В информатику понятие алгоритма пришло из математики. Термин «алгоритм» произошёл от имени математика IX в. Мухаммеда ибн Мусы аль-Хорезми, который сформулировал правила четырёх основных арифметических действий. Сначала алгоритмами называли именно эти правила, позже — любой способ вычислений, единый для некоторого класса исходных данных.

Пример 1.1. Алгоритм «Решето Эратосфена» позволяет получить простые числа, не превосходящие N.

ШагДействие
1Выписать подряд все натуральные числа от 2 до N.
2Взять первое число 2 и зачеркнуть каждое второе число, начиная отсчёт со следующего за двойкой числа.
3Взять первое незачёркнутое число, большее 2 (число 3), и зачеркнуть каждое третье число, начиная отсчёт от числа, стоящего после 3 (учитывая и ранее зачёркнутые числа).
4Продолжать действия до тех пор, пока первое незачёркнутое число не окажется больше N.
5Незачёркнутыми окажутся все простые числа, не превосходящие N, и только они.

Приведённое определение не является определением в математическом смысле слова: в нём использованы другие неопределённые понятия — «система предписаний», «формальное выполнение» и др. Это описание понятия «алгоритм», раскрывающее его сущность. Уточнить его можно, указав общие свойства алгоритмов.

Главная мысль: Алгоритм — точно определённая система понятных исполнителю предписаний, формальное выполнение которых даёт решение задачи для любого допустимого набора исходных данных за конечное число шагов.
2

Свойства алгоритма

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

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Свойства алгоритма

Выберите свойство в списке и прочитайте подсказку. Придумайте команду, которая нарушает это свойство (например, «посолить по вкусу»), и исправьте её так, чтобы исполнитель выполнил её однозначно.

Дискретность

Алгоритм разбивается на отдельные действия (шаги). Очередное действие выполняется только после завершения предыдущего. Команда — указание исполнителю выполнить отдельное действие; команды из системы команд исполнителя называют простыми.

Детерминированность (определённость)

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

Понятность

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

Результативность

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

Конечность

Процесс, заданный алгоритмом, останавливается через конечное число шагов и выдаёт искомый результат. Это свойство тесно связано с результативностью.

Массовость

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

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

Пример 1.2. Рецепты блюд часто называют алгоритмами. Но результат зависит от того, кто готовит, на какой плите и из каких продуктов, — нарушается детерминированность. Фразы «посолить по вкусу», «добавить 2—3 ложки сахара» нарушают понятность.

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

Главная мысль: Если последовательность действий не обладает хотя бы одним из шести свойств алгоритма, она не может считаться алгоритмом.
3

Формы записи и базовые конструкции

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

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Следование, ветвление и цикл

Задайте число x и число повторений, выполняйте шаги. Команды идут одна за другой (следование), условие x ≥ 0 выбирает одну из ветвей (ветвление), сложение повторяется заданное число раз (цикл). При нуле повторений тело цикла не выполняется ни разу.

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

Следование

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

Ветвление

В зависимости от выполнения условия выполняется одна из последовательностей команд.

Цикл

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

Подпрограмма

Вспомогательный алгоритм для части задачи; его можно вызывать из основного алгоритма.

Пример цикла в записи на языке Pascal — алгоритм Евклида для наибольшего общего делителя натуральных чисел a и b:

var a, b, r: integer;
begin
  readln(a, b);
  while b <> 0 do
  begin
    r := a mod b;
    a := b;
    b := r;
  end;
  writeln(a);
end.

Для чисел 48 и 18 пары (a, b) меняются так: (48, 18) → (18, 12) → (12, 6) → (6, 0); программа выводит 6.

Главная мысль: Для одного алгоритма возможны разные формы записи, но любой алгоритм можно представить с помощью следования, ветвления и цикла.
4

Теория алгоритмов и проверка правильности

Формальные определения алгоритма эквивалентны; любой алгоритм проверяют на правильность.

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Решето Эратосфена

Задайте верхнюю границу N и выполняйте шаги: для очередного незачёркнутого p вычёркиваются кратные ему числа. Кратные, меньшие p², уже зачёркнуты на предыдущих шагах, поэтому модель начинает вычёркивание с p² и останавливается, когда p² > N. Проверьте результат на разных N.

Необходимость построить формальное определение алгоритма привела к появлению в 20—30-х гг. XX в. теории алгоритмов. Различные математики предложили для этого: машину Тьюринга, машину Поста, нормальный алгоритм Маркова. Существовали и другие определения алгоритма; впоследствии было доказано, что все они эквивалентны.

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

Любой алгоритм нужно проверять на правильность работы. Пример 1.4. Способы проверки алгоритма на правильность:

Математическое доказательство

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

Специально подобранные тесты

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

Главная мысль: Формальные определения алгоритма — машина Тьюринга, машина Поста, нормальный алгоритм Маркова — эквивалентны; правильность алгоритма проверяют доказательством или тестами.
Интерактивная практика

Исследуйте и примените

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

НАБЛЮДАЙТЕ И ПРОБУЙТЕ

Лаборатория: алгоритм Евклида и решето Эратосфена

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

Соберём главное

Шесть выводов

01

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

02

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

03

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

04

Формальные определения алгоритма — машина Тьюринга, машина Поста, нормальный алгоритм Маркова — эквивалентны; правильность алгоритма проверяют доказательством или тестами.

05

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

06

Термин «алгоритм» произошёл от имени математика IX в. аль-Хорезми, сформулировавшего правила арифметических действий.

Самопроверка

Тест: 10 вопросов

Один верный ответ. За ответ — 1 балл. Откройте и проверьте себя.

1. От чьего имени произошёл термин «алгоритм»?

2. Какое свойство алгоритма означает его разбиение на отдельные шаги?

3. Какое свойство алгоритма нарушает фраза рецепта «посолить по вкусу»?

4. Как называется свойство: при повторном применении к одним и тем же данным получается один и тот же результат?

5. Как называют множество исходных данных, для которых пригоден алгоритм?

6. Какое свойство алгоритма тесно связано с конечностью?

7. Что из перечисленного НЕ предлагалось как формальное определение алгоритма?

8. Какие базовые алгоритмические конструкции используют при составлении алгоритмов?

9. Какие способы проверки алгоритма на правильность названы в учебнике?

10. Какое свойство не выполняется для решения задачи «Волк, коза и капуста»?

ВыводыТестВ началоВсе параграфы
↑

Загрузка прогресса…

↑