Сложные темы ЕГЭ и олимпиад по информатике: Алгоритмы на графах

Некоторые задачи ЕГЭ относятся или легко сводятся к алгоритмическим задачам на графах. Трудности при их решении для новичков связаны со специфичностью этой темы. Графы и деревья уже обсуждались в курсе «Рекурсия». Там же приведены способы машинного представления графов и рекурсивные варианты поисков в глубину и в ширину. Здесь предполагается углубиться в тему, подробнее обсудить вопросы, связанные с представлением графов, расширить список итеративных графовых алгоритмов и обсудить их применение для решения задач ЕГЭ. Этот курс входит в серию курсов по темам, освоение которых при подготовке к ЕГЭ и олимпиадам по информатике, как правило, вызывают затруднения. Планируемые курсы серии (в скобках указаны номера задач ЕГЭ, решение которых обсуждается в курсе): Рекурсия (16, 17); Динамическое программирование (26, 27) Префиксные суммы (27); Поиск подмножества (27); Сортировки (26); Делимость (25); Метод посимвольной обработки строк (24); Регулярные выражения (24); Методы обработки строк (24). Они могут использоваться и как дополнение к регулярным курсам или изучению соответствующей литературы , и как средство самостоятельной (при достаточном уровне знаний) подготовки к ЕГЭ. Главная цель – глубокое понимание алгоритмов и структур данных. Общеизвестны проблемы, возникающие при освоении школьниками основ программирования. Эти проблемы не решаются в полной мере ни демонстрацией хорошо структурированного кода, ни его подробным комментированием, ни пространным словесным описанием его пошагового выполнения. Динамический характер работы алгоритма и поведения данных вступают в противоречие с попыткой их статического описания. Плюс трудности восприятия новичком инструкций, предназначенных не ему, а компьютеру. Вот почему визуализация механизма работы алгоритма и изменения данных играет не меньшую (а, возможно, и большую) роль, чем текст. В простых случаях используются статические иллюстрации, но по большей части требуются анимация и видео-демонстрация. Все программы написаны на Python и почти все снабжены соответствующими ссылками на онлайн визуальный Python-отладчик. При прочих равных предпочтение отдавалось задачам, предлагавшимся на ЕГЭ, что может помочь и в подготовке к олимпиадам в той степени, в которой тематика задач ЕГЭ пересекается с тематикой олимпиадных заданий. В данном курсе разбираются решения задач № 13, 22, 23 из ЕГЭ. Вместе ними обсуждаются классические задачи теории графов. Подробное решение этих задач способствует освоению приемов представления и обработки графов.