МФТИ: Алгоритмы и программирование

Материалы раздела

• Как формализовать алгоритмическую задачу и оценить ресурсы решения? — До написания программы задачу переводят с естественного языка в точную модель: определяют входные данные, допустимые значения, требуемый результат и связь результата со входом.
• Как выбирать между следованием, ветвлением и циклом? — Структурная программа собирается из последовательности действий, выбора ветви и повторения. Эти конструкции выражают разные свойства задачи: следование фиксирует зависимость…
• Как доказывать правильность цикла с помощью инварианта? — Инвариант — утверждение о состоянии программы, истинное перед каждой проверкой условия цикла. Он связывает уже выполненную часть работы с остатком и позволяет перейти от…
• Как надёжно исследовать квадратное уравнение в программе? — Задача о квадратном уравнении проверяет не формулу корней, а полноту классификации входа. Коэффициент при квадрате может оказаться нулём, дискриминант — положительным, нулевым…
• Как анализировать и преобразовывать запись числа алгоритмом? — Число и его запись — разные объекты. Арифметический алгоритм получает цифры остатками от деления, строковый — читает символы и переводит их в значения.
• Почему алгоритм Евклида находит НОД и как его реализовать? — Наибольший общий делитель двух целых чисел сохраняется, если большее число заменить остатком от деления на меньшее.
• Как обрабатывать последовательность за один проход и постоянную память? — Линейная потоковая обработка читает каждый элемент один раз и хранит только агрегированное состояние. Такой метод нужен, когда последовательность велика или поступает по сети и…
• Как организовать обработку одномерного и двумерного массива? — Массив хранит элементы одного типа и предоставляет доступ по индексу. Его сила — быстрый переход к известной позиции, а ограничение — необходимость аккуратно управлять границами…
• Как выполнять вставку и удаление элемента в массиве? — Массив размещает элементы последовательно, поэтому вставка в середину требует освободить позицию сдвигом хвоста, а удаление — закрыть образовавшийся разрыв.
• Как сравнивать пузырьковую сортировку, выбор и вставки? — Квадратичные сортировки выполняют порядка n² сравнений или перемещений в неблагоприятном случае, но устроены по-разному.
• Как работает слияние и почему MergeSort имеет сложность O(n log n)? — Слияние объединяет два уже отсортированных массива в один, каждый раз выбирая меньший из текущих первых элементов.
• Как вычислять значение многочлена по схеме Горнера? — Прямое вычисление aₙxⁿ + … + a₁x + a₀ может многократно возводить x в степень и выполнять лишние умножения. Схема Горнера переписывает многочлен во вложенной форме и обрабатывает…
• Какие алгоритмы нужны для анализа символьных строк? — Строка — последовательность символов, но способ индексирования зависит от языка и кодировки. Учебные задачи обычно работают с логическими символами выбранного алфавита: считают…
• Как проектировать рекурсивный алгоритм и анализировать дерево вызовов? — Рекурсия решает задачу через экземпляры меньшего размера. Корректная функция имеет базовый случай, переход к нему и правило объединения результатов.
• Как представлять граф и выполнять обход в глубину или ширину? — Граф состоит из вершин и рёбер, которые могут быть ориентированными, неориентированными и взвешенными. Представление выбирают по плотности и операциям.
• Как считать пути и находить оптимальный маршрут в ациклическом графе? — Ориентированный ациклический граф не содержит направленного цикла, поэтому его вершины можно упорядочить так, чтобы каждое ребро шло слева направо.
• Как обходить дерево и разбирать арифметическое выражение? — Дерево — связный ациклический граф с выделенным корнем, если рассматривается иерархия. Каждый узел, кроме корня, имеет единственного родителя; листья не имеют детей.
• Как приближённо решать уравнения и оценивать погрешность? — Численный метод ищет не символическую формулу, а значение с заданной точностью. Ответ должен сопровождаться условием существования, критерием остановки и оценкой ошибки.
• Когда применять вероятностный алгоритм и метод Монте-Карло? — Вероятностный алгоритм использует случайный выбор как часть вычисления. Один запуск может дать приближение или небольшой риск ошибки, поэтому результат описывают не только…
• Как распознать задачу динамического программирования? — Динамическое программирование применяют, когда задача распадается на повторяющиеся подзадачи, а оптимальный ответ строится из их решений.
• Когда использовать список, стек, очередь и дек? — Линейные структуры различаются не содержимым, а набором дешёвых операций. Массив быстро обращается по индексу, связный список меняет связи рядом с известным узлом, стек выдаёт…
• Как устроены словарь и хеш-таблица? — Словарь хранит пары ключ–значение и поддерживает поиск по ключу. Хеш-таблица реализует этот интерфейс, преобразуя ключ в индекс корзины.
• Как функции, типы и парадигмы помогают описывать программу? — Язык программирования задаёт средства записи алгоритма и модель выполнения, а функция выделяет именованное преобразование с контрактом входа и результата.
• Как проектировать, тестировать и доказывать работоспособность программы? — Разработка начинается с постановки задачи и модели данных, продолжается декомпозицией, реализацией и проверкой, а не сводится к набору операторов.
• Как провести пробный письменный и устный экзамен МФТИ по информатике? — Репетиция должна воспроизводить не только сложность задач, но и переключение форматов. Официальная программа задаёт двухчасовую письменную часть, затем собеседование до тридцати…