Модульное программирование

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

Формальная модель модуля

1. Абстракция модуля
   

   Модуль можно задать тройкой:

   M = <I, E, B>

   где

   • I – интерфейс (экспортируемые объявления: типы, константы, подпрограммы),

   • E – контракт (предусловия/постусловия, инварианты, гарантии и исключения),

   • B – тело (скрытая реализация, локальные структуры данных и вспомогательные функции).

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

2. Контракты (Хоаровская запись)
   

   Для функции/процедуры f:

   {P(x)}  r := f(x)  {Q(x, r)}

   • P – предусловие (что обязан выполнить клиент перед вызовом),

   • Q – постусловие (что гарантирует модуль после завершения).

3. Граф зависимостей модулей
   

   Пусть задан ориентированный граф G = (V, E), где вершины – модули, ребро A → B означает «A использует B». Требования:

   • ацикличность G (для упрощения сборки): допустима топологическая сортировка,

   • сложность построения порядка сборки – O(|V| + |E|).

Связность и зацепление (cohesion & coupling)

1. Связность (внутренняя цельность модуля) 
   Высокая связность – признак качественного дизайна: модуль решает одну предметную задачу. Примеры: prime_utils, matrix_ops, string_scan.
   

2. Зацепление (степень зависимости между модулями)
   

   Снижаем зацепление:

   • передаём данные через параметры, а не через глобальные переменные;

   • экспортируем минимально необходимый интерфейс;

   • не «протаскиваем» детали реализации наружу.

Правила модульного проектирования (строгие)

Правило 1. Единственная ответственность. Один модуль – одна чёткая задача.

Правило 2. Интерфейс минимален. Экспортируйте только то, что необходимо клиенту.

Правило 3. Скрытие данных. Структуры и буферы – максимально private, работа с ними только через функции интерфейса.

Правило 4. Контракты на границах. В интерфейсе фиксируйте P и Q (словами или псевдокодом), включая ошибки/исключения.

Правило 5. Ацикличность зависимостей. Не допускайте кольцевых ссылок; выносите общие типы в отдельный низкоуровневый модуль.

Правило 6. Отдельная сборка и тесты. Каждый модуль компилируется и тестируется независимо (юнит-тесты).

Правило 7. Стабильность имен и типов. Изменения реализации не должны ломать интерфейс без необходимости.

Правило 8. Документирование сложностей. В интерфейсе отмечайте временную/пространственную сложность.

Параметры, область видимости и время жизни

1. Передача параметров
   

   • По значению – копия аргумента (безопасно, но может быть дороже).

   • По ссылке/указателю – позволяет обновлять данные на месте; требует осторожности.

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

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

2. Область видимости
   

   • Локальная (внутри функции/модуля) – рекомендуема по умолчанию.

   • Экспортируемая – только для элементов, необходимых клиенту.

3. Время жизни
   

   • автоматическое (на стеке, живёт до конца блока),

   • статическое/глобальное (живёт всё время работы),

   • динамическое (в куче, освобождение – обязанность владельца).

Шаблоны модулей для типичных задач ЕГЭ

1. Модуль ввода-вывода (IO)
   

   • функции чтения массива/строки по условиям задачи,

   • строгая валидация данных и сообщений об ошибках.

2. Модуль числовых функций (Math/NumberTheory)
   

   • gcd(a,b), lcm(a,b), is_prime(n), factor(n),

   • контракт: диапазоны входов, сложность алгоритмов.

3. Модуль обработки массивов (ArrayOps)
   

   • count_if(A, P), max_pos(A), pairs_by_pred(A, B, Pred),

   • инварианты циклов документируются в комментариях.

4. Модуль строк (StringOps)
   

   • подсчёт подстрок, фильтрация символов по классу, нормализация регистра.

5. Модуль матриц (MatrixOps)
   

   • транслирует операции transpose, row_sum, col_max,

   • чёткие предикаты корректности индексов.

Контракты и инварианты (примерно и копируемо)

1. Пример контракта
   

   function count_divisible_pairs(A: array of int, k: int) -> int

   Предусловие: k > 0; длина(A) = n ≥ 0

   Постусловие: результат = |{ (i, j) | 0 ≤ i < j < n, (A[i] + A[j]) mod k = 0 }|

   Сложность: O(n) по времени и O(k) по памяти (через счётчики остатков)

2. Инвариант цикла (эталон)
   

   I(t): после обработки префикса A[0..t-1]

   - freq[r] содержит количество элементов с остатком r среди A[0..t-1]

   - pairs = число пар внутри префикса, удовлетворяющих условию

Организация кода и сборки

1. Разделение на интерфейс и реализацию
   

   • *.h / *.hpp (заголовки) – объявления, контракты, описания типов;

   • *.c / *.cpp / *.pas / модуль Python – реализация.

2. Порядок сборки
   

   Топологическая сортировка графа зависимостей модулей (O(V+E)). Ошибка цикла обнаруживается, если отсортировано меньше |V| модулей.

3. Версионирование интерфейса (кратко)
   

   Используйте семантическое версионирование:

   MAJOR.MINOR.PATCH

   • несовместимые изменения → MAJOR+1,

   • совместимые расширения → MINOR+1,

   • исправления → PATCH+1.

Тестирование модулей: методика «чёрного ящика»

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

Связь с ЕГЭ по информатике

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

Мини-шаблоны (копируемые фрагменты)

Предикат и фильтрация:

function is_good(x): return (x % 7 = 0) and (x % 5 ≠ 0)

function count_good(A):

    cnt := 0

    for x in A:

        if is_good(x): cnt := cnt + 1

    return cnt

Разделение ввода/решения/вывода:

A := read_array()

ans := solve(A)    // только вычисление, без I/O

print(ans)

Инвариант суммы:

sum := 0

for i := 0..n-1:

    // I: sum == Σ_{t=0..i-1} A[t]

    sum := sum + A[i]

// Q: sum == Σ_{t=0..n-1} A[t]

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

Упражнение 1. Декомпозиция задачи «пары по делимости»

Дано: массив целых A[0..n-1], целое k > 0. Требуется посчитать число пар (i, j), i < j, таких, что (A[i] + A[j]) mod k = 0.
a) Спроектируйте модули io, arith, pairs. Опишите интерфейсы и контракты (пред-/постусловия).
b) Для pairs.count_divisible_pairs сформулируйте инвариант однопроходного алгоритма на остатках.
c) Докажите сложность O(n + k) и корректность результата. 

Упражнение 2. Модуль prime_utils для задач ЕГЭ

Специфицируйте интерфейс:
is_prime(n) -> bool
next_prime(n) -> int
factor(n) -> list of (p, α)

a) Запишите контракты и оценки сложности (решето/проверка делителями до ⌊√n⌋).
b) Предложите минимальный набор тестов (граничные значения: 0,1,2, большие простые, квадраты простых).
c) Покажите, как модуль используется в задаче «найти сумму простых делителей каждого числа массива».

Упражнение 3. Граф модулей и топологическая сортировка

Модули: main использует io и solver; solver использует array_ops и math_ext; array_ops использует io (для загрузки), math_ext автономен.
a) Постройте граф зависимостей и выполните топологическую сортировку (один корректный порядок).
b) Добавьте ошибочную зависимость io → solver. Объясните, почему возникает цикл, и предложите способ его устранения (вынос общих типов).
c) Оцените сложность вычисления порядка сборки.

Упражнение 4. Контракты и инварианты для обработки матрицы

Функция: row_argmax(A: m×n, i) -> (j, val)

возвращает позицию и значение максимума в строке i.
a) Запишите P: требования к m,n,i и корректности индексов. Запишите Q: спецификацию результата и поведение при нескольких максимумах (выберите, например, минимальный j).
b) Сформулируйте инвариант внутреннего цикла по столбцам и докажите корректность.
c) Укажите сложность и типичные краевые случаи.

Упражнение 5. Тест-план как модуль

Создайте модуль tests для проверки ArrayOps.partition(A, P) – разбиение массива по предикату P с сохранением относительного порядка (стабильная версия).
a) Определите набор классов эквивалентности: пустой массив, все элементы «истинные», все «ложные», перемежающиеся значения, дубликаты.
b) Сформулируйте оракул: после вызова все элементы, для которых P(x)=true, идут раньше остальных, и относительный порядок внутри групп не меняется.
c) Опишите автоматизированные тесты (табличный подход): список входов и ожидаемые выходы.

Заключение

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