Алгоритм: полный разбор

1. Что это такое

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

Слово происходит от имени математика аль-Хорезми (IX век). Строгое определение дал А. А. Марков: алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Важно: алгоритм — это не сам процесс, а его описание (план).

2. Свойства алгоритма (обязательные — спрашивают чаще всего)

Свойство	Что означает	Пример нарушения
Дискретность	Процесс разбит на отдельные законченные шаги	«Найди примерно середину» — не шаг
Понятность	Каждая команда входит в систему команд исполнителя (СКИ)	Роботу без шагомера команда «пройди 10 см»
Определённость (детерминированность)	Одна и та же команда при тех же данных даёт строго один результат; нет «двусмысленных» шагов	«Если число большое — уменьши» (большое — сколько?)
Результативность	После конечного числа шагов получается результат, либо вывод, что его нет	Бесконечный цикл без выхода
Конечность	Число шагов конечно	—
Массовость	Применим к целому классу задач, а не к одной	Алгоритм «сложи 2 и 3» — не алгоритм, а действие
Формальность (по некоторым учебникам)	Исполнитель выполняет команды, не вникая в смысл	—

3. Исполнитель

Исполнитель — объект, который может выполнять команды. Бывает формальный (выполняет всё буквально, не может ошибиться, но и «додумать» не может — компьютер, робот, Черепаха, Кузнечик) и неформальный (человек).

СКИ — система команд исполнителя — весь набор команд, которые он понимает. Среда — обстановка, в которой работает исполнитель. Отказ — команда, которую исполнитель выполнить не может.

4. Виды алгоритмов (по структуре)

• Линейный — все команды один раз, строго по порядку. Пример: «взять a, взять b, c = a + b, вывести c».
• Разветвляющийся — есть проверка условия и выбор пути.
• Циклический — некоторая группа команд повторяется.
• Вспомогательный — часть другого алгоритма, оформленная отдельно (подпрограмма, процедура, функция). Нужен, чтобы не писать одно и то же много раз.

5. Три базовые конструкции (структурное программирование)

Любой алгоритм можно собрать из трёх блоков:

Следование — команды друг за другом: \[ \text{команда}_1;\ \text{команда}_2;\ \dots;\ \text{команда}_n \]

Ветвление (если … то … иначе …): \[ \text{если } P \text{ то } S_1 \text{ иначе } S_2 \]

Цикл — пока условие истинно, повторяем тело: \[ \text{пока } P \text{ повторять } S \]

Кроме «пока», бывают цикл «для» (со счётчиком) и «повторять … до» (с постусловием).

6. Способы записи

1. Словесный — обычным текстом, по пунктам.
2. Блок-схема — стандартные фигуры:
   • овал — начало / конец;
   • прямоугольник — действие;
   • ромб — условие (вопрос, из него два выхода: «да» / «нет»);
   • параллелограмм — ввод / вывод;
   • стрелки — порядок шагов.
3. Псевдокод — учебный «полуязык» программирования (алг … нач … кон).
4. Программа — на реальном языке (Python, Паскаль и т. д.).
5. Таблица трассировки — таблица значений переменных по шагам (нужна для проверки).

7. Пример: алгоритм Евклида (НОД двух чисел)

Словесно: пока числа не равны, вычитать меньшее из большего.

Псевдокод:

пока a ≠ b
  если a > b
    то a := a − b
    иначе b := b − a
вывести a

Проверка для \(a = 48,\ b = 18\): 48 и 18 → 30, 18 → 12, 18 → 12, 6 → 6, 6. Ответ: 6. Свойства выполнены: шаги дискретны, команды понятны, процесс конечен, результат один и тот же, метод работает для любой пары чисел.

8. Алгоритм и программа — в чём разница

Программа — запись алгоритма на конкретном языке для конкретного компьютера. Один алгоритм → много программ. Программа — частный случай (реализация) алгоритма.

9. Что проверяют на ОГЭ / ЕГЭ

• назвать свойство по описанию («алгоритм применим к любым числам» → массовость);
• найти ошибку в блок-схеме или в псевдокоде (обычно: нет выхода из цикла, неверное условие, перепутаны ветви);
• исполнить алгоритм вручную и найти значение переменной;
• составить алгоритм для формального исполнителя (Кузнечик, Черепаха, Чертёжник);
• посчитать число шагов или команд.

10. Как решать задачи на исполнение алгоритма

1. Выпиши таблицу: столбцы — шаг и все переменные.
2. Выполняй строго по одной команде, не «пере

Алгоритм — текст для пересказа

Определение. Алгоритм — это точное описание последовательности действий исполнителя, которое за конечное число шагов приводит от исходных данных к результату. Важно: алгоритм — не сам процесс, а его план. Название идёт от имени математика аль-Хорезми.

Свойства. Их шесть, и они главное в теме. Дискретность — процесс разбит на отдельные шаги. Понятность — каждая команда входит в систему команд исполнителя, то есть исполнитель её умеет выполнять. Определённость — при одних и тех же данных команда всегда даёт один и тот же результат, двусмысленных шагов нет. Результативность — алгоритм обязательно заканчивается и даёт результат. Конечность — число шагов конечно. Массовость — алгоритм годится для целого класса похожих задач, а не для одной.

Исполнитель. Исполнитель — это объект, который выполняет команды. Он бывает формальный, как компьютер или робот: делает всё буквально и не может «додумать», и неформальный — человек. Набор всех команд, которые исполнитель понимает, называется системой команд исполнителя. Если команда ей не соответствует, возникает отказ.

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

Три базовые конструкции. Любой алгоритм собирается из трёх блоков: следование, ветвление («если… то… иначе…») и цикл («пока условие истинно, повторять…»). Это называется структурным программированием.

Способы записи. Словесный — обычным текстом по пунктам. Блок-схема — овал для начала и конца, прямоугольник для действия, ромб для условия, параллелограмм для ввода и вывода. Псевдокод — учебный полуязык. И программа — запись на настоящем языке программирования.

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

Алгоритм и программа. Программа — это запись алгоритма на конкретном языке для конкретного компьютера. Один алгоритм может дать много программ.

---

Скелет для ответа: определение → шесть свойств → исполнитель и его система команд → четыре вида → три конструкции → способы записи → пример → отличие от программы.

Если спросят про свойство по описанию: «применим к любым числам» — массовость; «каждый шаг отдельный» — дискретность; «всегда один результат» — определённость; «заканчивается» — результативность.

Алгоритм — короткий пересказ

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

Свойства — их шесть:

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

Исполнитель — тот, кто выполняет команды. Бывает формальный (компьютер, робот — делает буквально, «додумать» не может) и неформальный (человек). Набор всех его команд — система команд исполнителя.

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

Три конструкции, из которых строится любой алгоритм: следование, ветвление («если… то… иначе…»), цикл («пока… повторять…»).

Записывают словами, блок-схемой, псевдокодом или программой. Программа — это запись алгоритма на конкретном языке; один алгоритм может дать много программ.

Пример — алгоритм Евклида: пока числа не равны, вычитаем меньшее из большего. Для 48 и 18 ответ 6.

Опорный каркас: определение → шесть свойств → исполнитель → четыре вида → три конструкции → способы записи → пример.

Схемы по теме «Алгоритм»

Условные обозначения фигур

Фигура	Что означает
овал	начало / конец
параллелограмм	ввод / вывод
прямоугольник	действие (команда)
ромб	условие (вопрос), два выхода: «да» / «нет»
стрелка	порядок шагов

1. Линейный алгоритм (следование)

        ┌──────────────┐
        │   НАЧАЛО     │
        └──────┬───────┘
               ▼
        ╱──────────────╲
        │  ввод a, b   │
        ╲──────────────╱
               ▼
        ┌──────────────┐
        │   c = a + b  │
        └──────┬───────┘
               ▼
        ╱──────────────╲
        │    вывод c   │
        ╲──────────────╱
               ▼
        ┌──────────────┐
        │    КОНЕЦ     │
        └──────────────┘

2. Ветвление

        ┌──────────────┐
        │   a > b ?    │
        └──────┬───────┘
      да ◄─────┴─────► нет
        ▼               ▼
   ┌─────────┐    ┌─────────┐
   │ max = a │    │ max = b │
   └────┬────┘    └────┬────┘
        └───────┬──────┘
                ▼
          (дальше по схеме)

3. Цикл «пока»

              ▼
       ┌──────────────┐
  ┌───►│   i ≤ n ?    │──── нет ───►┌──────────┐
  │    └──────────────┘             │  КОНЕЦ   │
  │           │ да                  └──────────┘
  │           ▼
  │    ┌──────────────┐
  └────┤  i := i + 1  │
       └──────────────┘

4. Общая схема темы (для пересказа)

                        АЛГОРИТМ
                            │
   ┌───────────────┬────────┴────────┬────────────────┐
   ▼               ▼                 ▼                ▼
СВОЙСТВА      ИСПОЛНИТЕЛЬ          ВИДЫ            ЗАПИСЬ
   │               │                 │                │
дискретность   формальный       линейный         слова
понятность     неформальный     разветвляющийся  блок-схема
определённость      │           циклический      псевдокод
результативность    ▼           вспомогательный  программа
конечность      СКИ (система
массовость      команд)

5. Три конструкции — всё вместе

АЛГОРИТМ ─┬─ СЛЕДОВАНИЕ : команда₁ → команда₂ → … → команда_n
          ├─ ВЕТВЛЕНИЕ  : если P то S₁ иначе S₂
          └─ ЦИКЛ       : пока P повторять S

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

Исполнение алгоритма

Исполнение — это процесс пошагового выполнения команд алгоритма исполнителем. Алгоритм при этом «оживает»: из плана превращается в действия и результат.

Кто и как исполняет

• Автоматически — компьютер, робот, программа: быстро, без ошибок, но строго по СКИ.
• Вручную — человек: медленно, зато может заметить ошибку в самом алгоритме.

Главное правило: исполнитель выполняет команды формально — не вникая в смысл и ничего не додумывая. Что написано, то и делается.

Если команда не входит в СКИ или её нельзя выполнить в данной среде (например, «вправо» у самой стены), возникает отказ.

Схема одного шага исполнения

┌──────────────────────┐
│ взять следующую      │
│ команду              │
└──────────┬───────────┘
           ▼
┌──────────────────────┐    нет   ┌───────────────┐
│ команда есть в СКИ?  ├─────────►│    ОТКАЗ      │
└──────────┬───────────┘          └───────────────┘
           │ да
           ▼
┌──────────────────────┐
│ выполнить команду,   │
│ записать новые       │
│ значения переменных  │
└──────────┬───────────┘
           ▼
┌──────────────────────┐
│ команды кончились?   │── нет ──┐
└──────────┬───────────┘         │
           │ да                  └──► (на начало шага)
           ▼
      РЕЗУЛЬТАТ

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

Это таблица: столбец на каждый шаг, строка на каждую переменную. Заполняем строго по одной команде.

Пример 1. Линейный: \(c = a + b\), при \(a = 7,\ b = 5\)

Шаг	Команда	a	b	c
1	ввод a, b	7	5	—
2	c := a + b	7	5	12
3	вывод c	7	5	12

Пример 2. Цикл: \(s = 1+2+3+4\)

Шаг	Проверка \(i \le 4\)	s	i
1	да	0	1
2	да	1	2
3	да	3	3
4	да	6	4
5	да	10	5
6	нет → выход	10	5

Ответ: \(s = 10\). Тело цикла выполнилось 4 раза, а условие проверялось 5 раз — это частая деталь в заданиях.

Пример 3. С ветвлением: алгоритм Евклида для 48 и 18

Шаг	Сравнение	a	b
1	\(a > b\)	30	18
2	\(a > b\)	12	18
3	\(a < b\)	12	6
4	\(a > b\)	6	6
—	\(a = b\), стоп	6	6

Ответ: 6. Шагов 4 — значит, конечность и результативность соблюдены.

Что чаще всего ломается при исполнении

• Бесконечный цикл — условие никогда не станет ложным (нарушена результативность). Признак в трассировке: значения повторяются, выхода нет.
• Неверный порядок команд — переменная используется до того, как получила значение.
• Перепутаны ветви — «да» и «нет» поменяны местами.
• Ошибка на единицу — цикл начинают с 0 вместо 1 или используют \(\le\) вместо \(<\).
• Отказ исполнителя — команда вне СКИ или вне допустимой среды.

Как проверять себя

1. Достроил трассировку до конца — есть ли выход из цикла?
2. Все ли переменные получили значения до использования?
3. Совпадает ли результат с проверкой «в уме» на маленьком примере?
4. Конечное число шагов? Тогда алгоритм корректен по форме.

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

Какие действия и в каком порядке

Тут два разных набора действий — их легко перепутать, поэтому разделю.

А. Действия исполнителя (что он делает при исполнении)

1. Взять очередную команду из алгоритма.
2. Проверить: есть ли она в СКИ и выполнима ли в данной среде.
3. Если нет — отказ, исполнение прекращается.
4. Если да — выполнить её: изменить состояние (переместиться, поменять значение переменной, вывести данные).
5. Запомнить новое состояние.
6. Проверить, не кончились ли команды. Если нет — вернуться к пункту 1.
7. Если кончились — выдать результат.

Коротко: взять → проверить → выполнить → запомнить → проверить конец → результат.

Б. Действия ученика (что делать тебе, когда дали алгоритм на исполнение)

1. Выписать все переменные и их начальные значения.
2. Начертить таблицу: столбцы — номера шагов, строки — переменные и условие.
3. Идти строго по одной команде, а не «целиком».
4. На каждом шаге сначала проверить условие (если это ромб или «пока»), потом выполнять тело.
5. Записать в таблицу новые значения — не стирая старые.
6. Остановиться, когда вышел из цикла или дошли до «конец».
7. Взять значение из последней строки — это ответ. Отдельно посчитать, сколько раз выполнилось тело цикла.

В. Действия-ошибки, которые проверяют на контрольных

• выполнил команду, которой нет в СКИ (надо было сказать «отказ»);
• пропустил проверку условия на последнем шаге (лишний проход цикла);
• стёр старое значение вместо записи нового шага;
• посчитал шаги тела цикла вместо проверок условия.

Проверка на примере — \(s = 1+2+3+4\), таблица:

Проверка \(i \le 4\)	s	i
да	0	1
да	1	2
да	3	3
да	6	4
нет	10	5

Действия по порядку: 4 раза вошли в тело, условие проверялось 5 раз, ответ \(s = 10\).

Уточни, что именно нужно: действия исполнителя (пункт А) или порядок твоих действий при решении задачи (пункт Б)? Или речь о конкретном алгоритме — тогда пришли его условие.

Циклические алгоритмы

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

1. Из чего состоит цикл

• Тело цикла — команды, которые повторяются.
• Условие — проверка, продолжать или закончить.
• Счётчик (параметр) — переменная, которая меняется от прохода к проходу и приближает конец цикла.
• Начальные значения — то, что задаётся до цикла (часто \(s = 0\), \(i = 1\)).

Главное правило: внутри цикла что-то должно меняться, иначе условие никогда не станет ложным и получится бесконечный цикл.

2. Три вида циклов

А. Цикл с предусловием («пока»)

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

              ▼
       ┌──────────────┐
  ┌───►│  условие P?  │──── нет ───► выход из цикла
  │    └──────────────┘
  │           │ да
  │           ▼
  │    ┌──────────────┐
  └────┤  тело цикла  │
       └──────────────┘

Запись: пока P повторять S. В Паскале — while, в Python — while.

Б. Цикл с постусловием («повторять … до»)

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

       ┌──────────────┐
       │  тело цикла  │◄──┐
       └──────┬───────┘   │
              ▼           │
       ┌──────────────┐   │
       │  условие P?  │── нет ──┘
       └──────┬───────┘
              │ да
              ▼
           выход

Запись: повторять S до P (выход, когда P истинно).

В. Цикл со счётчиком («для»)

Число повторений известно заранее.

┌────────────────────────────┐
│ для i от 1 до n повторять  │
│        тело цикла          │
└────────────────────────────┘

Запись: для i от 1 до n. В Паскале — for, в Python — for i in range(1, n+1).

3. Примеры с трассировкой

Пример 1. Сумма \(1+2+\dots+n\) при \(n = 4\)

s := 0
для i от 1 до 4
    s := s + i
вывод s

Шаг	i	s
вход	1	0
1	1	1
2	2	3
3	3	6
4	4	10

Ответ: \(s = 10\). Тело выполнилось 4 раза.

Пример 2. Цикл «пока» — деление на 2, пока чётно

ввод n
пока n делится на 2 нацело
    n := n / 2
вывод n

Для \(n = 24\): 24 → 12 → 6 → 3. Ответ 3. Проверок условия было 4, тело выполнилось 3 раза.

Пример 3. Постусловие — когда нужно хотя бы одно действие

повторять
    ввод x
до x > 0

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

4. Что чаще всего спрашивают и где ошибаются

• Сколько раз выполнится тело? Считай проходы тела, а не проверки условия. Для «пока» при \(i\) от 1 до \(n\) — ровно \(n\) раз.
• Сколько проверок условия? У цикла «пока» на одну больше, чем проходов тела: последняя проверка даёт «нет».
• Бесконечный цикл — не меняется счётчик или условие неверное. Признак в таблице: значения повторяются, выхода нет.
• Ошибка на единицу — \(\le\) вместо \(<\) или старт с 0 вместо 1.
• Цикл не выполнился ни разу — так бывает только у «пока»; если по условию задачи действие должно быть хотя бы одно, нужен цикл с постусловием.
• Сумма не обнулена — до цикла обязательно \(s := 0\), иначе к сумме прибавится «мусор» из памяти.
• Сумма против произведения — для произведения начальное значение \(p := 1\), а не 0, иначе всё произведение обнулится.

5. Как решать задачу на цикл — порядок действий

1. Определи, что повторяется (тело) и что меняется (счётчик).
2. Реши, известно ли число повторений: да — «для», нет — «пока». Нужно хотя бы одно выполнение — постусловие.
3. Задай начальные значения: \(s := 0\), \(i := 1\), \(p := 1\).
4. Начерти таблицу «шаг / переменные» и пройди 3–4 шага вручную.
5. Проверь: есть ли выход, не зациклились ли, совпадает ли ответ с проверкой «в уме».

Для пересказа коротко: цикл — повторение тела, пока истинно условие; три вида — «пока» (проверка до тела, может не выполниться), «повторять…до» (проверка после тела, выполнится хотя бы раз) и «для» (число повторов известно заранее); внутри обязательно должно меняться значение, иначе цикл бесконечен.

Устный пересказ: «Алгоритмы и исполнители»

Говори медленно, по абзацам — каждый абзац это одна мысль. Весь текст рассчитан примерно на 2–3 минуты.

---

Определение. Алгоритм — это точная последовательность действий исполнителя, которая за конечное число шагов приводит от исходных данных к результату. Важно понимать: алгоритм — это не сам процесс, а его план, описание. Само слово происходит от имени математика аль-Хорезми.

Свойства. У алгоритма шесть основных свойств. Дискретность — процесс разбит на отдельные шаги. Понятность — каждая команда входит в систему команд исполнителя, то есть исполнитель умеет её выполнять. Определённость — при одних и тех же данных команда всегда даёт один и тот же результат, двусмысленных шагов нет. Результативность — алгоритм обязательно заканчивается и даёт результат. Конечность — число шагов конечно. И массовость — алгоритм подходит для целого класса похожих задач, а не для одной.

Исполнитель. Исполнитель — это объект, который выполняет команды. Он бывает формальный и неформальный. Формальный — это компьютер, робот, учебные исполнители вроде Черепахи или Кузнечика: он выполняет команды буквально, ничего не додумывает и ошибиться не может. Неформальный исполнитель — человек. Набор всех команд, которые исполнитель понимает, называется системой команд исполнителя. Если команда в неё не входит или её нельзя выполнить в данной обстановке, возникает отказ.

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

Три конструкции. Любой алгоритм можно собрать из трёх блоков. Это следование, ветвление — «если… то… иначе…» — и цикл — «пока условие истинно, повторять». Такой подход называется структурным программированием.

Исполнение. Исполнение — это пошаговое выполнение команд. Исполнитель действует формально. Чтобы не ошибиться, составляют трассировку — таблицу, где по шагам записывают значения переменных. Например, для суммы от одного до четырёх: \(s := 0\), затем в цикле \(s := s + i\), где \(i\) меняется от 1 до 4. Тело цикла выполнится четыре раза, условие проверится пять раз, ответ — 10.

Циклы. Цикл бывает трёх видов. С предусловием — «пока»: сначала проверка, потом тело, поэтому он может не выполниться ни разу. С постусловием — «повторять… до»: сначала тело, поэтому выполнится хотя бы один раз. И со счётчиком — «для», когда число повторений известно заранее. Внутри цикла обязательно должно меняться значение, иначе получится бесконечный цикл.

Запись. Алгоритм записывают словами, блок-схемой, псевдокодом или программой. В блок-схеме овал — начало и конец, прямоугольник — действие, ромб — условие с двумя выходами «да» и «нет», параллелограмм — ввод и вывод.

Алгоритм и программа. Программа — это запись алгоритма на конкретном языке для конкретного компьютера. Один алгоритм может дать много программ.

---

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

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

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

Свойства — это требования, которым должен удовлетворять настоящий алгоритм. Если хотя бы одно нарушено, это уже не алгоритм, а просто набор действий.

Семь свойств

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

2. Понятность. Каждая команда входит в систему команд исполнителя, то есть исполнитель знает, как её выполнять. Нарушение: команда «пройди 10 см» роботу, у которого нет линейки. Ключевые слова: «исполнитель умеет», «команда ему знакома».

3. Определённость (детерминированность). При одних и тех же исходных данных алгоритм всегда даёт один и тот же результат; ни один шаг нельзя понять двояко. Нарушение: «если число большое, уменьши его» — непонятно, какое число считать большим. Ключевые слова: «всегда один и тот же результат», «нет двусмысленности».

4. Результативность. Алгоритм обязательно заканчивается и даёт результат — либо вывод, что результата нет. Нарушение: бесконечный цикл, из которого нет выхода. Ключевые слова: «обязательно заканчивается», «получается результат».

5. Конечность. Число шагов конечно. Это уточнение результативности: процесс не может длиться бесконечно. Нарушение: «повторяй, пока не надоест». Ключевые слова: «конечное число шагов».

6. Массовость. Алгоритм применим не к одной конкретной задаче, а к целому классу однотипных задач с разными исходными данными. Нарушение: «сложи 2 и 3» — это отдельное действие, а не алгоритм. Ключевые слова: «подходит для любых чисел», «для целого класса задач».

7. Формальность. Исполнитель выполняет команды буквально, не вникая в их смысл и ничего не додумывая. Это свойство часто относят к самому исполнителю, а не к записи. Ключевые слова: «действует по инструкции, не рассуждая».

Таблица для быстрого повторения

Свойство	Суть одной фразой	Нарушение
Дискретность	разбит на отдельные шаги	«примерно», «как-нибудь»
Понятность	все команды из СКИ	команда незнакома исполнителю
Определённость	результат всегда один	двусмысленная команда
Результативность	заканчивается результатом	бесконечный цикл
Конечность	шагов конечное число	«повторяй бесконечно»
Массовость	годится для класса задач	алгоритм только для одной пары чисел
Формальность	исполнитель не рассуждает	требует «понимания» смысла

Как узнать свойство по описанию

Это самое частое задание. Работай по ключевым словам:

• «каждый шаг отдельный» → дискретность;
• «исполнитель понимает команду» → понятность;
• «при тех же данных всегда один результат» → определённость;
• «обязательно заканчивается» → результативность;
• «число шагов конечно» → конечность;
• «применим к любым числам / к разным задачам» → массовость.

Проверка на примере

Алгоритм Евклида — пока \(a \ne b\), вычитать меньшее из большего:

• шаги отдельные — дискретность;
• команды «сравнить», «вычесть», «вывести» понятны исполнителю — понятность;
• для пары 48 и 18 ответ всегда 6 — определённость;
• числа уменьшаются, цикл завершится — результативность и конечность;
• работает для любой пары натуральных чисел — массовость.

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

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

Алгоритмы и множества

Формулировка «алгоритм множества» может значить две разные вещи, поэтому дам главное — алгоритмы обработки множеств, а в конце уточню.

1. Множество — что это

Множество — набор элементов, где порядок не важен и повторов нет. \(\{3, 1, 2\}\) и \(\{1, 2, 3\}\) — одно и то же множество, а \(\{1, 1, 2\}\) — уже не множество (двойка повторов не допускает).

Обозначения: \(x \in A\) — элемент принадлежит множеству, \(x \notin A\) — не принадлежит, \(\varnothing\) — пустое множество.

2. Базовые операции

Операция	Запись	Что получается
Объединение	\(A \cup B\)	все элементы из обоих, без повторов
Пересечение	\(A \cap B\)	только общие элементы
Разность	\(A \setminus B\)	элементы \(A\), которых нет в \(B\)
Симметрическая разность	\(A \triangle B\)	элементы, входящие ровно в одно множество
Дополнение	\(\overline{A}\)	всё, чего нет в \(A\) (в пределах универсума)

Пример: \(A = \{1, 2, 3\},\ B = \{3, 4\}\). Тогда \(A \cup B = \{1, 2, 3, 4\}\), \(A \cap B = \{3\}\), \(A \setminus B = \{1, 2\}\), \(A \triangle B = \{1, 2, 4\}\).

3. Типовые алгоритмы

Проверка принадлежности (линейный поиск). Идём по всем элементам и сравниваем:

ввод x, A
флаг := ложь
для каждого a из A
    если a = x то флаг := истина
вывод флаг

Сложность — \(n\) сравнений, где \(n\) — размер множества.

Пересечение. Для каждого элемента первого множества проверяем, есть ли он во втором:

для каждого a из A
    если a ∈ B то вывести a

Получается \(A \cap B\), повторов не будет, потому что в \(A\) их нет.

Объединение через добавление. Кладём в результат сначала всё из \(A\), затем из \(B\), но с проверкой:

C := A
для каждого b из B
    если b ∉ C то добавить b в C

Именно проверка «\(\notin\)» убирает повторы — иначе множество превратится в мультимножество.

Разность. Оставляем элементы \(A\), которых нет в \(B\):

для каждого a из A
    если a ∉ B то вывести a

Удаление дубликатов из массива. Это и есть превращение массива в множество:

M := пусто
для каждого x из массива
    если x ∉ M то добавить x в M

Перебор всех подмножеств. У множества из \(n\) элементов ровно \(2^{n}\) подмножеств (включая пустое и само множество):

для mask от 0 до 2^n − 1
    взять элементы, у которых в номере mask стоит 1

Для \(\{a, b\}\): \(2^2 = 4\) подмножества — \(\varnothing, \{a\}, \{b\}, \{a, b\}\).

4. Трассировка маленького примера

\(A = \{1, 2, 3\},\ B = \{3, 4\}\), строим \(A \cup B\):

Шаг	Элемент	Есть в C?	C
старт	—	—	{1, 2, 3}
1	3	да	{1, 2, 3}
2	4	нет	{1, 2, 3, 4}

Три шага, результат \(\{1, 2, 3, 4\}\).

5. Где чаще всего ошибаются

• забыли проверку на повтор — получили мультимножество;
• перепутали разность: \(A \setminus B \ne B \setminus A\);
• посчитали, что подмножеств \(2^{n} - 1\) (забыли пустое);
• в пересечении вывели элемент дважды, если он встречается в обоих списках.

---

Уточни, что именно нужно: операции над множествами с примерами, алгоритм программы (Python/Паскаль) для объединения и пересечения, или речь о другом — что множество всех алгоритмов счётно (теория алгоритмов)?

Цикл — коротко и понятно

Цикл — это конструкция алгоритма, в которой группа команд (тело цикла) повторяется несколько раз, пока выполняется условие.

Из чего состоит

• Тело цикла — что повторяется.
• Условие — когда остановиться.
• Счётчик — переменная, которая меняется и приближает конец.
• Начальные значения — задаются до цикла: \(s := 0\), \(i := 1\).

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

Три вида

1. «Пока» (с предусловием) — сначала проверка, потом тело. Может не выполниться ни разу.

пока i ≤ n повторять
    s := s + i
    i := i + 1

2. «Повторять … до» (с постусловием) — сначала тело, потом проверка. Выполнится хотя бы один раз.

повторять
    s := s + i
    i := i + 1
до i > n

3. «Для» (со счётчиком) — число повторов известно заранее.

для i от 1 до 4
    s := s + i

Пример с трассировкой

Сумма \(1 + 2 + 3 + 4\):

Проверка \(i \le 4\)	s	i
да	1	1
да	3	2
да	6	3
да	10	4
нет	10	5

Ответ: \(s = 10\). Тело выполнилось 4 раза, условие проверялось 5 раз — последняя проверка дала «нет».

Частые ошибки

• Бесконечный цикл — счётчик не меняется или условие неверное.
• Ошибка на единицу — \(\le\) вместо \(<\) или старт с 0 вместо 1.
• Сумма не обнулена — до цикла обязательно \(s := 0\).
• Произведение начали с 0 — для произведения \(p := 1\), иначе всё обнулится.
• Путают число проходов тела и число проверок условия — у «пока» проверок на одну больше.

Для пересказа

Цикл — это повторение группы команд, пока истинно условие. Бывает трёх видов: «пока» — проверка до тела, поэтому может не выполниться ни разу; «повторять… до» — проверка после тела, поэтому выполнится хотя бы раз; «для» — когда число повторов известно заранее. В цикле обязательно должна меняться переменная-счётчик, иначе он будет бесконечным. Чтобы не ошибиться, строят таблицу-трассировку и считают отдельно проходы тела и проверки условия.

Блок-схемы циклов

1. Цикл «пока» (с предусловием)

        ┌──────────────────┐
        │  s := 0, i := 1  │
        └────────┬─────────┘
                 ▼
        ╱──────────────────╲
   ┌───►│     i ≤ n ?      │──── нет ───►┌─────────────┐
   │    ╲──────────────────╱              │  вывод s    │
   │             │ да                     └──────┬──────┘
   │             ▼                               ▼
   │    ┌──────────────────┐              ┌─────────────┐
   │    │   s := s + i     │              │   КОНЕЦ     │
   │    │   i := i + 1     │              └─────────────┘
   │    └────────┬─────────┘
   └─────────────┘

Особенность: ромб стоит до тела. Поэтому при \(i > n\) с самого начала тело не выполнится ни разу.

2. Цикл «повторять … до» (с постусловием)

        ┌──────────────────┐
        │  s := 0, i := 1  │
        └────────┬─────────┘
                 ▼
        ┌──────────────────┐
   ┌───►│   s := s + i     │
   │    │   i := i + 1     │
   │    └────────┬─────────┘
   │             ▼
   │    ╱──────────────────╲
   │    │     i > n ?      │──── да ───►┌─────────────┐
   │    ╲──────────────────╱             │  вывод s    │
   │             │ нет                   └──────┬──────┘
   └─────────────┘                              ▼
                                          ┌─────────────┐
                                          │   КОНЕЦ     │
                                          └─────────────┘

Особенность: проверка после тела, значит тело выполнится хотя бы один раз.

3. Цикл «для» (со счётчиком)

        ┌──────────────────────────┐
        │  s := 0                  │
        └────────────┬─────────────┘
                     ▼
        ┌──────────────────────────┐
        │  i от 1 до n             │◄──────┐
        │  (следующее значение i)  │       │
        └────────────┬─────────────┘       │
                     │ значения кончились  │
        ┌────────────┴───────────┐         │
        │ есть i                 │         │
        ▼                        ▼         │
┌──────────────────┐      ┌─────────────┐  │
│   s := s + i     │      │  вывод s    │  │
└────────┬─────────┘      └──────┬──────┘  │
         │                       ▼         │
         └──────────────────►┌─────────────┐│
                             │   КОНЕЦ     ││
                             └─────────────┘│
                                             │
   (шаг «взять следующее i» возвращается сюда)

Проще запомнить так: тело повторяется ровно \(n\) раз, а счётчик перебирает значения сам.

4. Из чего состоит цикл

                    ЦИКЛ
                      │
      ┌───────────────┼────────────────┬──────────────┐
      ▼               ▼                ▼              ▼
  НАЧАЛЬНЫЕ        УСЛОВИЕ           ТЕЛО         СЧЁТЧИК
  ЗНАЧЕНИЯ         (ромб)          (команды)     (меняется)
      │               │                │              │
  s := 0        i ≤ n  да/нет     s := s + i     i := i + 1
  i := 1                               │              │
      │               │                │              │
      └───────────────┴────────────────┴──────────────┘
                              │
                              ▼
                 Если менять нечего — цикл
                   никогда не закончится
                    (бесконечный цикл)

5. Сравнение трёх видов

   «ПОКА»            «ПОВТОРЯТЬ…ДО»        «ДЛЯ»
     ▼                      ▼                 ▼
 проверка               тело             счётчик i
     ▼                      ▼                 ▼
   тело                 проверка           тело
     ▼                      ▼                 ▼
 (цикл)                (цикл)              (цикл → i растёт)

 может не              выполнится        число повторов
 выполниться            минимум 1 раз     известно заранее
 ни разу

Что проверяют на контрольной: стрелку возврата рисуй обязательно — без неё схема не цикл, а просто ветвление. И у ромба должны быть подписаны оба выхода: «да» и «нет».