учитель математики и информатики

На олимпиадах по информатике популярными являются задачи, включающие нахождение остовного дерева графа. При этом, существует 2 основных алгоритма: Прима и Крускала. Существует общая рекомендация, что, если в графе много вершин и мало ребер (разреженный граф), то применяется алгоритм Крускала. Если же мало вершин и много ребер – алгоритм Прима. Однако, встречаются ситуации, когда определиться с выбором алгоритма на основании понятий «мало» и «много» затруднительно. На уроках информатики и проектной мастерской мы с учеником 10А класса Болуц Романом(победитель муниципальной, региональной олимпиад, а также призер Всероссийской и Всесибирской олимпиад) поставили задачу: получить более точные критерии для выбора алгоритма. Статья порешению олимпиадных задач.docx