Курсовая по программированию в МФТИ: корректность, тесты и производительность вместо количества строк

Курсовая по программированию в МФТИ чаще относится к конкретной дисциплине внутри ПМИ, ИВТ, программной инженерии, физической или инженерной программы, а не к отдельному направлению с названием «Программирование».

В актуальном наборе 2026 года МФТИ есть ПМИ, несколько программ ИВТ и программная инженерия. Поэтому оформление и глубину проекта нужно брать из реального курса.

Официальная страница:
https://pk.mipt.ru/bachelor/2026_rules/

Программа начинается с задачи

Плохо:

«Разработка программы на C++».

Сильнее:

«Реализация структуры данных для динамического множества с анализом времени операций».

Язык вторичен.

Главное:

• задача;
• ограничения;
• корректность;
• производительность.

Specification

Запишите:

• input;
• output;
• ограничения;
• invalid input;
• memory limit;
• time limit.

Не начинайте писать функцию, пока непонятно, что она должна делать на границе.

Контракты

Для функции полезно определить precondition и postcondition.

Например:

входной массив отсортирован.

После:

индекс первого элемента >= x.

Так тесты становятся яснее.

Структура данных

Выбирайте по операциям.

Если нужны быстрый поиск, вставка, минимум и порядок, разные структуры дают разный компромисс.

Не используйте дерево только ради сложности.

Complexity table

Сделайте таблицу:

| Операция | Array | Hash | Tree |
|---|---:|---:|---:|

После этого обоснуйте выбор.

Корректность

Ответьте на вопрос:

почему результат всегда правильный?

Инструменты:

• invariant;
• induction;
• contradiction;
• known theorem.

Тесты не заменяют доказательство для всех входов, если курс требует теорию.

Инвариант

Например, в binary search нужный элемент всегда остаётся внутри текущего интервала.

Покажите состояние до шага, после шага и termination.

Это лучше слов «алгоритм очевиден».

Граничные случаи

Проверьте:

• empty;
• one item;
• max size;
• duplicates;
• negative;
• sorted/reversed.

Ошибка часто живёт не в обычном случае.

Integer overflow

Если n до 10^9, произведение n*n может не поместиться в int.

Выберите тип осознанно.

Не исправляйте overflow после странного runtime.

Floating point

Не сравнивайте double через `==` без понимания задачи.

Для численных расчётов используйте tolerance.

Но tolerance должен быть связан с масштабом.

Memory

Оцените:

• asymptotic;
• peak;
• stack/heap.

Рекурсия на миллион уровней не подходит, даже если код красивый.

Iteration vs recursion

Сравните readability, depth и overhead.

Не делайте рекурсию самоцелью.

Parsing

Отделите чтение от алгоритма.

Так можно benchmark вычисление отдельно от I/O.

Error handling

Ошибка пользователя и внутренняя ошибка должны отличаться.

Например:

• invalid format -> понятное сообщение;
• invariant violation -> fail/test.

Не глотайте exception пустым catch.

Tests

Структура:

• unit;
• boundary;
• randomized;
• regression.

Каждый test должен иметь название по поведению.

Не test1.

Randomized testing

Для алгоритма можно сравнивать с медленным эталоном на тысячах случайных входов.

Например:

optimized vs brute force.

Это сильный способ проверки.

Differential testing

Если есть reference implementation, сравните outputs.

При первом mismatch сохраните seed и input.

Так bug воспроизводим.

Property based testing

Проверяйте свойства.

Для sort:

• nondecreasing;
• same multiset.

Не нужно заранее знать конкретный output для каждого случайного массива.

Fuzzing

Для parser, protocol или binary format fuzzing помогает найти crash.

Работайте локально.

Покажите corpus, найденный case, fix и regression test.

Code style

Стиль уменьшает стоимость чтения.

Используйте:

• naming;
• small functions;
• clear modules.

Не превращайте линтер в главный результат курсовой.

Static analysis

Компилятор warnings, sanitizer и analyzer помогают находить UB, memory bug и race.

Покажите конкретную найденную проблему.

Sanitizers

Для C/C++:

• address;
• undefined;
• thread.

Один пример before/after полезен на защите.

Version control

Git должен показывать этапы.

Небольшие commits помогают откату.

Не `project_final_v2_real.cpp`.

Build

Зафиксируйте compiler, version, flags и command.

Другой человек должен собрать проект.

Benchmark

Измеряйте на серии размеров:

10³
10⁴
10⁵
10⁶.

Покажите median нескольких повторов.

Warm cache

Если benchmark зависит от кеша, укажите условия.

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

Не смешивайте.

Profiler

Если программа медленная, найдите hotspot.

Не оптимизируйте функцию, которая занимает 2% времени.

Optimization

Цикл:

measure -> change -> measure.

Сохраните baseline.

После оптимизации код должен оставаться корректным по тем же тестам.

Parallel programming

Сначала проверьте, есть ли параллельная часть.

Измерьте speedup, efficiency и contention.

Не считайте четыре потока четырёхкратным ускорением.

Algorithmic vs micro optimization

Переход O(n²) -> O(n log n) обычно важнее ручного loop unrolling.

Сначала улучшайте алгоритм.

Сложность на реальных данных

Worst case и typical case могут отличаться.

Покажите оба, если это важно.

Не скрывайте плохой worst case за средним временем.

Reproducibility

Сохраните генератор данных и seed.

Benchmark должен запускаться одной командой.

Не вводите числа вручную из Excel.

Практическая глава

Схема:

1. specification;
2. algorithm;
3. correctness;
4. implementation;
5. tests;
6. random tests;
7. benchmark;
8. profiler;
9. optimization;
10. limits.

Контекст МФТИ

Программирование в МФТИ встроено в несколько сильных математических и инженерных направлений. Поэтому курсовая может требовать алгоритмической строгости, системной глубины или прикладного результата.

Проверяйте конкретный курс.

Защита

Будьте готовы объяснить invariant, оценить complexity, показать boundary test, воспроизвести bug, показать benchmark и назвать bottleneck.

Сильная курсовая по программированию в МФТИ оценивается не количеством кода, а тем, насколько решение корректно, измеримо и воспроизводимо.