Типы ошибок в программах

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

• дефект (fault) – причина на уровне кода/данных/дизайна;
• сбой (error) – попадание исполнения в некорректное состояние;
• отказ (failure) – наблюдаемое неверное поведение/результат.

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

Таксономия ошибок

1. По фазе обнаружения
   

   1. Лексические и синтаксические (compile-time): неверные ключевые слова, скобки, пунктуация операторов. Компилятор/интерпретатор прекращает сборку/запуск.

   2. Семантические и типовые: несовместимость типов, обращение к необъявленной переменной, неверные параметры вызова.

   3. Линковочные/конфигурационные: отсутствующие объявления/модули, конфликты версий библиотек.

   4. Ошибки времени выполнения (run-time): деление на ноль, выход за границы массива, разыменование нулевого указателя, переполнение стека/кучи, нарушения доступа к файлам/сети.

   5. Логические (алгоритмические): программа завершается без исключений, но вычисляет неверный результат (например, off-by-one, неверное условие цикла).

2. По природе
   

   • Численные: переполнение/потеря точности/катастрофическая отмена.

   • Структурные: выход за границы, работа с «висячими» ссылками, утечки ресурсов.

   • Состояния/потоков управления: зацикливание, пропущенные ветви, нарушение инвариантов цикла/структуры данных.

   • Конкурентные: гонки данных, взаимная блокировка (deadlock), живое зависание (livelock).

   • Ввод-вывод/средовые: неверные пути, кодировки, права доступа, EOF-ловушки.

   • Проектные/спецификационные: неверные требования, двусмысленные формулировки, несогласованные единицы измерения.

Формальные основы корректности

1. Контракты (Хоаровская тройка)
   

   Для фрагмента кода S корректность формулируется как:

   {P} S {Q}

   где P – предусловие (что истинно до), Q – постусловие (что гарантируется после).
   Частичная корректность: если P истинно и S завершилась, то Q истинно.
   Полная корректность: частичная корректность + гарантированная завершимость.

2. Инвариант цикла
   

   Инвариант I должен быть истинным:

   1. после инициализации перед первой итерацией;

   2. сохраняться каждой итерацией;

   3. вместе с условием выхода давать постусловие задачи.

   Инварианты – главный инструмент обнаружения логических ошибок в циклах (типичные задачи ЕГЭ).

Численные ошибки и строгие границы

1. Переполнение целых (двухкомплементарный код)
   

   Для n-битового целого:

   min_signed = -2^(n-1)

   max_signed =  2^(n-1) - 1

   max_unsigned = 2^n - 1

   Проверка умножения на переполнение (без длинной арифметики):

   если a ≠ 0 и |b| > ⌊max_signed / |a|⌋ ⇒ переполнение при a*b

   Аналогично для сложения:

   если (a > 0 и b > 0 и a > max_signed - b) ⇒ переполнение

   если (a < 0 и b < 0 и a < min_signed - b) ⇒ переполнение

2. Вещественная арифметика
   

   • Сравнение с допуском:

   |x - y| ≤ ε

   • Накопление погрешности суммирования n чисел при фиксированной абсолютной погрешности операции δ:

   |Δ_sum| ≤ (n - 1) * δ

   • Катастрофическая отмена: при вычитании близких чисел относительная ошибка резко возрастает – избегать вычислительных схем с близкими разностями, использовать эквивалентные устойчивые формулы.

Структурные и логические ошибки (паттерны)

1. Off-by-one: неверные границы диапазонов (for i=1..n vs 1..n-1).
2. Выход за границы/индексация: неверный порядок индексов в матрице, смешение баз индексации.
3. Неинициализированные переменные: чтение до присваивания.
4. Неправильная область видимости: теневание имён, использование локальной переменной после выхода (в небезопасных языках – «висячие» указатели).
5. Деление на ноль/остаток по нулю: отсутствие проверки.
6. Смешение = и == (в языках, где присваивание – выражение).
7. Нарушение инвариантов структур данных: забыли обновить размер, «головы/хвосты» списка.
8. Модификация коллекции во время итерации без корректной схемы.

Конкурентные ошибки (кратко, но строго)

• Гонки данных: два потока одновременно читают/пишут одну переменную без синхронизации ⇒ недетерминированность.

• Deadlock (условия Кофмана – необходимые): 
  

  1. взаимное исключение,

  2. удержание и ожидание,

  3. отсутствие принудительного изъятия,

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

• Livelock: потоки «вежливо уступают» друг другу бесконечно, прогресса нет.

• ABA-проблема: при lock-free структурах; лечится тегами/версионностью.

Диагностика и предупреждение

1. Предупреждение (правила дисциплины)
   

   Правило 1. Инициализация по умолчанию:

   sum := 0; count := 0; flag := false

   Правило 2. Явные границы и инварианты: записывать в комментарии до кода цикла.
   Правило 3. Проверка входа: предусловия на диапазоны/значения.
   Правило 4. Использование «безопасных» операций сравнения вещественных: |x-y| ≤ ε.
   Правило 5. Контроль переполнений перед операцией (см. формулы).
   Правило 6. Минимальная область видимости переменных; избегать теневания.
   Правило 7. Исключения: ловить ожидаемые, не глушить все подряд; разделять «восстановимые» и «фатальные».
   Правило 8. Ресурсы – через RAII/with-контексты/try/finally: утечки недопустимы.
   Правило 9. Юнит-тесты: краевые случаи, пустые/минимальные входы, большие входы.
   Правило 10. Статический анализ: стиль, возможные нулевые ссылки/выход за границы, неиспользуемые переменные.
   Правило 11. Логирование с контекстом, но без утечки секретов.
   Правило 12. Детерминированность: фиксировать порядок итерации/сортировок, не полагаться на случайный порядок структур.

2. Отладка (методика)
   

   • Репродукция и минимизируемый пример.

   • Бинарный поиск по изменениям (bisect по коммитам).

   • Инварианты как runtime-asserts:

   assert(предусловие);  ...; assert(инвариант); ...; assert(постусловие);

   • Разделяй и властвуй: изолировать модуль, подменять внешние зависимости заглушками.

Связь с ЕГЭ по информатике (типовые ловушки)

• Неверные границы циклов (off-by-one) в подсчёте количества/суммы.

• Смешение целочисленного и вещественного деления:

• 7 div 2 = 3,   7 / 2 = 3.5

• Переполнение при больших произведениях/степенях для 32-битного типа.

• Неправильная работа с флагом «найдено»: не обнулил/не прервал цикл.

• Логические выражения: приоритеты операций, отрицание сложных условий (де Морган).

• Неправильная обработка EOF/«сторожевых» значений.

• Нарушение инварианта при рекурсии: отсутствует/неверное условие остановки.

Мини-шпаргалка ЕГЭ:

• До цикла инициализируй всё, что считаешь.
• Проверь делитель на ноль до операции.
• Для сравнения вещественных применяй |x-y| ≤ ε.
• Для больших n оцени переполнение.
• Сформулируй инвариант – он «поймает» половину логических ошибок.

Иллюстративные мини-примеры

1. Off-by-one
   

   # неверно: пропустим последний элемент

   s = 0

   for i in range(0, n-1):

       s += a[i]

   # верно для 0..n-1:

   for i in range(0, n):

       s += a[i]

2. Вещественные сравнения
   

   def eq(x, y, eps=1e-9):

       return abs(x - y) <= eps

3. Проверка переполнения сложения (32-бит)
   

   if (a > 0 and b > max32 - a) → overflow

   if (a < 0 and b < min32 - a) → overflow

4. Инвариант подсчёта
   

   I(t): после t итераций цикла s = sum(a[1..t])

Пять упражнений (академический формат)

Упражнение 1. Границы и инвариант
Дан псевдокод:
s := 0
for i := 1 to n-1 do
    s := s + a[i]

a) Объясните, почему пропущен элемент a[n]. Предложите исправление двумя способами.
b) Запишите инвариант цикла и докажите коррекцию исправленного варианта.
c) Оцените сложность по времени и памяти.

Упражнение 2. Целочисленное vs вещественное деление
Требуется вычислить среднее значение целых a[1..n]. Рассмотрены варианты:
avg1 := sum / n
avg2 := sum div n

a) Для каких sum, n значения совпадают?
b) Какой тип нужно выбирать для avg1 и avg2?
c) Приведите вход, на котором неверный выбор операции даёт неправильный ответ, и укажите корректную форму вывода.

Упражнение 3. Переполнение и безопасная мультипликация
Дано 32-битное знаковое целое.
a) Запишите проверку на переполнение при вычислении p := a * b (см. формулы §3).
b) Покажите, как изменить алгоритм вычисления факториала, чтобы избежать переполнения: (1) переход на 64-бит, (2) логарифмическая оценка, (3) длинная арифметика.
c) Докажите корректность выбранной проверки для крайних значений a, b.

Упражнение 4. Логическое выражение и закон де Моргана
Дан фрагмент:
if not (x >= 0 and y <> 0) then ...

a) Преобразуйте условие к эквивалентной форме без внешнего not (используйте де Моргана).
b) Составьте таблицу истинности обеих форм и докажите эквивалентность.
c) Объясните, какая из форм менее подвержена ошибкам чтения/написания в контексте ЕГЭ.

Упражнение 5. Флаг и досрочный выход
Задача: проверить наличие элемента x в массиве a[1..n].
Даны два варианта:
(found, i) := (false, 1)
while i ≤ n do
    if a[i] = x then found := true
    i := i + 1
и
(found, i) := (false, 1)
while i ≤ n and not found do
    if a[i] = x then found := true else i := i + 1

a) Покажите логическую ошибку первого варианта (лишняя итерация после нахождения).
b) Сформулируйте инвариант второго варианта и докажите, что он завершится не более чем за n шагов.
c) Оцените среднее число итераций при равновероятном расположении x и при отсутствии x.

Заключение

Грамотная классификация ошибок и владение строгими приёмами – контракты, инварианты, проверка границ и переполнений, численная устойчивость, аккуратная работа с типами и ресурсами – позволяют системно предупреждать дефекты и быстро локализовывать сбои. Для ЕГЭ это напрямую конвертируется в успех: правильно выбранные операции, верные границы циклов, корректная арифметика и формальная аргументация («почему это правильно») обеспечивают устойчивые высокие результаты.