Основы алгоритмизации и программирования

1. Алгоритм и корректность

1.1. Что считается алгоритмом

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

1.2. Спецификация задачи

Перед кодом фиксируют: вход, выход, ограничения, особые случаи, критерии корректности.

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

Инвариант — утверждение, которое истинно перед каждой итерацией. Это основной способ строгого доказательства корректности алгоритма.

2. Типы данных и базовые конструкции

2.1. Базовые типы

2.2. Ввод/вывод и валидация

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

3. Условные операторы и циклы

3.1. Ветвления

if/else выбирает одну из ветвей. Для сложной логики полезно заранее выписать таблицу условий.

3.2. Циклы

• for: известное число шагов.
• while: пока условие истинно.
• do-while: минимум одна итерация.

3.3. Контроль цикла

• break — аварийный выход.
• continue — переход к следующей итерации.

4. Функции, рекурсия, декомпозиция

4.1. Функции

• Одна функция — одна ответственность.
• Явные входы/выходы, минимум скрытого состояния.
• Имена должны объяснять поведение.

4.2. Рекурсия

Обязательно:

• база рекурсии;
• шаг, приближающий к базе;
• оценка глубины (во избежание переполнения стека).

4.3. Разбиение задачи

Сложную задачу делят на этапы: чтение входа, вычислительное ядро, формат вывода. Это снижает сложность отладки.

5. Массивы, строки, базовые структуры

5.1. Массивы

• Индексация и границы.
• Линейный проход, подсчет, поиск min/max.
• Двумерные массивы: обход по строкам/столбцам.

5.2. Строки

• Частоты символов.
• Проверка палиндрома.
• Разбор токенов.

5.3. Начальные структуры данных

• Стек (LIFO).
• Очередь (FIFO).
• Множество (проверка принадлежности).
• Словарь/хеш-таблица (ключ → значение).

6. Оценка сложности

6.1. Модель Big-O

O(f(n)) оценивает рост времени/памяти при росте размера входа n.

6.2. Оценка в практике

• Учитывать худший случай.
• Сравнивать и время, и память.
• Учитывать ограничение задачи (например, n ≤ 10^5).

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

7.1. Линейный и бинарный поиск

def binary_search(a, x):
    left, right = 0, len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            return mid
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

7.2. Базовые сортировки

• Пузырьковая, вставками, выбором — каждая O(n^2).
• Нужны не ради практики, а для понимания обменов и инвариантов.

7.3. Шаблоны задач

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

8. Практика разработки и экзаменационный минимум

8.1. Инженерные принципы

• Писать тесты на крайние случаи.
• Разделять вычисления и ввод/вывод.
• Не дублировать код (DRY).
• Рефакторить после получения рабочего решения.

8.2. Чек-лист перед сдачей

1. Все ветви условий покрыты тестами.
2. Границы массивов проверены.
3. Сложность соответствует ограничениям.
4. Имена переменных осмысленные.
5. Нет неиспользуемого кода и «магических» констант.

8.3. Минимум к экзамену

• Корректно писать циклы и функции.
• Уметь оценивать сложность фрагмента кода.
• Решать типовые задачи на массивы/строки/поиск/сортировку.
• Понимать рекурсию и уметь заменить ее итерацией при необходимости.