💡 Определение

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

⚠️ Когда что-то НЕ является алгоритмом?

Пример из учебника: Построение перпендикуляра к прямой с помощью циркуля.

Инструкция:

1. Отложить от точки A на прямой MN циркулем отрезки равной длины.
2. Увеличить раствор циркуля до радиуса, в полтора-два раза больше.
3. Провести дуги окружностей...

Проблема: Шаг 2 неоднозначен. «Полтора-два раза» — это сколько? 1,5? 1,7? 2? Для компьютера это катастрофа. Нарушено свойство понятности.

Как исправить? Указать точное значение: «Увеличить раствор циркуля в 1,5 раза относительно длины AB».

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

Исполнитель — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.

Исполнители бывают двух типов:

• Формальные («неразмышляющие») — строго следуют инструкциям без творчества (компьютеры, роботы)
• Неформальные — могут принимать решения и интерпретировать команды (люди)

💬 Псевдокод

Гибрид естественного языка и программирования. Используется для быстрой записи идеи алгоритма.

Пример: Поиск простых чисел (Решето Эратосфена).

Алгоритм: Найти все простые числа от 2 до n

1. Создать список чисел от 2 до n
2. p := 2
3. Зачеркнуть все числа, кратные p (2p, 3p, 4p, ...)
4. Найти следующее незачёркнутое число > p
5. Присвоить p это число
6. Повторять шаги 3-5, пока p² ≤ n
7. Оставшиеся незачёркнутые числа — простые

Оптимизация: Можно начинать зачёркивать с p², а не с 2p, потому что все меньшие составные числа уже будут зачёркнуты.

📚 Решето Эратосфена: поиск простых чисел

Простые числа — это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число (например: 2, 3, 5, 7, 11, 13...).

Метод нахождения простых чисел в интервале [2; n] предложил греческий математик Эратосфен (275–194 гг. до н. э.). По одной из версий, он выписал все числа от 2 до 10 000 на папирусе, натянутом на рамку, и прокалывал составные числа. Папирус стал подобен решету, которое «просеивало» составные числа, а простые оставляло.

Интересный факт: В 2013 г. открыто простое число, запись которого в десятичной системе счисления состоит из 17 425 170 знаков. На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, США.

🎮 Как работает алгоритм

Пусть задумано число X ∈ [A, B].

1. C := (A + B) div 2  // Находим середину
2. Если X = C, то число угадано
3. Если X < C, то B := C - 1  // Сдвигаем правую границу
4. Если X > C, то A := C + 1  // Сдвигаем левую границу
5. Повторяем с шага 1

Почему это эффективно? За каждый шаг диапазон сокращается вдвое. Для чисел от 0 до 100 понадобится максимум 7 попыток (log₂(100) ≈ 6.64).

💡 Определения

Вычислительный процесс, порождённый алгоритмом — это последовательность шагов алгоритма, пройденных при его исполнении.

Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма.

Важно: Речь идёт именно о вычислительном процессе, а не о самом алгоритме. В циклических алгоритмах за счёт повторного выполнения одних и тех же команд число шагов может быть значительно больше числа команд.

📊 Типы сложности

Сложность обычно выражают как функцию от размера входных данных n.

🎯 Практический пример

Вы хотите найти песню в плейлисте из 1000 треков.

• Линейный поиск (перебор всех треков): до 1000 операций
• Бинарный поиск (если список отсортирован): ≈ 10 операций

Разница в 100 раз! Вот почему Spotify или YouTube Music мгновенно подбирают рекомендации.

🏛️ Метод из Древней Индии

Рассмотрим метод быстрого вычисления натуральной степени n вещественного числа x, описанный в Древней Индии ещё до нашей эры.

1. Запишем n в двоичной системе счисления.
2. Заменим в этой записи каждую единицу парой букв КХ,
   а каждый ноль — буквой К.
3. Вычеркнем крайнюю левую пару КХ.
4. Полученная строка, читаемая слева направо, даёт правило
   быстрого вычисления x^n, если:
   - букву К рассматривать как операцию возведения 
     результата в квадрат
   - букву X — как операцию умножения результата на х
   Вначале результат равен х.

🔢 Пример: вычислим x¹⁰⁰

1. 100 = 1100100₂
2. Строим последовательность: KXKXKKKXKK
3. Вычёркиваем крайнюю левую пару КХ: KXKKKXKK
4. Вычисляем искомое значение:

   K: возвести x в квадрат → x²
   X: умножить результат на x → x³
   K: возвести результат в квадрат → x⁶
   K: возвести результат в квадрат → x¹²
   K: возвести результат в квадрат → x²⁴
   X: умножить результат на x → x²⁵
   K: возвести результат в квадрат → x⁵⁰
   K: возвести результат в квадрат → x¹⁰⁰

Результат: Мы вычислили сотую степень числа x за 8 умножений. Это значительно эффективнее «прямолинейного» алгоритма возведения в степень, требующего 99 операций умножения.

💡 Почему это работает?

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