Элементы теории алгоритмов — тест

Есть задачи, для которых программу не напишет никто и никогда — не из-за нехватки мощности, а потому что такого алгоритма не существует. Это доказано.

Что проверяется

Уточнение понятия алгоритма: интуитивное определение и его недостаточность, машина Тьюринга и её устройство, лента, головка и таблица переходов, нормальные алгорифмы Маркова, тезис Чёрча — Тьюринга об универсальности этих моделей. Алгоритмически неразрешимые задачи: проблема остановки и суть её доказательства, распознавание эквивалентности программ, примеры неразрешимых задач за пределами информатики. Сложность вычислений: число операций как функция размера входных данных, порядок роста, линейная, логарифмическая, квадратичная и экспоненциальная сложность, сравнение алгоритмов на больших данных, переборные задачи. Доказательство правильности программ: предусловие и постусловие, инвариант цикла, доказательство завершения, отличие доказательства от тестирования.

Проблема остановки

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

Тестирование не заменяет доказательства

Тесты показывают наличие ошибок, но не их отсутствие: проверить все входные данные невозможно. Инвариант цикла позволяет обосновать правильность сразу для всех случаев.

Как устроена работа

Одиннадцать заданий: выбор варианта, соответствие между алгоритмом и порядком роста числа операций, восстановление пропусков, упорядочивание видов сложности и подсчёт числа операций. Разбор к каждому заданию показывает ход рассуждения. Работа рассчитана примерно на двадцать пять минут, отметка выставляется по шкале пятьдесят, семьдесят и восемьдесят пять процентов. Отдельные вопросы посвящены машине Тьюринга, переборным задачам и инварианту цикла.

Организация тестирования

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