Основы информатики

Компьютеры хранят все данные числами. Узнайте, как алгоритмы работают с переменными через инструкцию set и условие if.

Предсказывайте поведение алгоритмов с условиями и входными данными.

Массив — это пронумерованная последовательность ячеек. Научитесь обращаться к значениям по индексу и понять, как команды читают и изменяют массив.

Научитесь перебирать все элементы массива с помощью циклов while и for, искать максимум, вычислять сумму и считать элементы по условию.

Научитесь искать значение в массиве: линейный перебор, досрочный выход (done) и ускорение поиска в отсортированном массиве.

Эффективный алгоритм поиска в отсортированном массиве: проверяем середину и отбрасываем половину.

Изучите два базовых инструмента алгоритмов сортировки: сравнение элементов массива и их обмен местами через временную ячейку.

Постройте первый алгоритм сортировки — сортировку выбором — шаг за шагом.

Разберитесь с алгоритмом сортировки вставками: как расширять отсортированный сегмент каскадом обменов и защититься от краевого случая A[-1].

Узнайте, как экспериментально измерять скорость алгоритмов и предсказывать форму зависимости «размер входа — время».

Научитесь подсчитывать обращения к массиву, сравнения и обмены, чтобы оценить стоимость алгоритма.

Узнайте, почему число сравнений сортировки вставками зависит от содержимого массива, и освойте понятия лучшего и худшего случая.

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

Научитесь сравнивать алгоритмы по показателю степени и освоите нотацию О-большое.

Изучите, что $O(n^2)$ — это множество функций, как множества вложены и почему принято указывать наименьший показатель.

Формальное определение O-большого через константу $c$ и отношение функций; доказательство принадлежности множеству $O(\cdot)$.

Узнайте, что такое устойчивое паросочетание и почему алгоритм NRMP защищён от цепочек расколов.

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

Алгоритм Гейла–Шепли использует индивидуальные жадные решения больниц и кандидатов для построения централизованного устойчивого паросочетания.

Докажите, что алгоритм Гейла — Шепли всегда строит устойчивое паросочетание, в котором сопоставлены все участники.

Почему хороший алгоритм обязан не просто давать правильный результат, но и гарантированно завершаться. Метод доказательства завершимости через убывающую целочисленную величину на примере алгоритма Гейла–Шепли.

Анализ времени работы алгоритма Гейла — Шепли: три реализации с O(n³), O(n² log n) и O(n²).

Как алгоритм Гейла–Шепли адаптируется к реальным задачам: несколько мест, неравные стороны, неполные списки.

Узнайте, как деревья решений разбивают сложную задачу на последовательность простых вопросов «да или нет».

Оптимизируйте дерево решений, уменьшая число вопросов через разбиение пополам.

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

Узнайте, как параллелизм ускоряет только параллелизуемые части задачи — и почему добавление работников даёт убывающую отдачу.

Узнайте, как конвейерная обработка повышает эффективность, используя простаивающие ресурсы, и в чём разница между задержкой и пропускной способностью.

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

Научитесь размещать ресурсы там, где они нужнее всего, не увеличивая их объём.

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

Интерфейс — это стандартизированный способ взаимодействия с системой, скрывающий её внутреннее устройство. За одним интерфейсом могут стоять разные реализации с разными компромиссами.

Сформулируйте задачу о мостах Кёнигсберга и познакомьтесь с идеей полного перебора.

Полный перебор — метод проверки всех возможных вариантов. На задаче о мостах Кёнигсберга узнаем, почему перебор работает для малых задач и почему становится непрактичным при росте числа вариантов.

Узнайте, как задачу о мостах Кёнигсберга можно превратить в задачу о графе — и почему это открывает более быстрое решение.

Освойте критерий существования эйлерова пути: подсчёт вершин с нечётной степенью.

Узнайте, как описать головоломку в виде графа, чтобы компьютер мог найти решение автоматически.

Научитесь превращать головоломку о переправе через реку в граф: вершины, рёбра и правила допустимых расстановок.

Узнайте, как алгоритм поиска в глубину (DFS) находит путь в графе состояний головоломки.