Страница Михаила Медведева
Задача 3-выполнимости (3-SAT) является NP-полной. Однако задача 2-SAT является полиномиальной
Изложены базовые теоретические сведения о сильно связных компонентах в теории графов.
В статье приведены базовые алгоритмы для решения задач на геометрическую тематику. Показано их применение на конкретных примерах.
Описывается алгоритм решения задачи поиска кратчайшего пути из одного источника до остальных вершин графа, именуемый алгоритмом Дейкстры. Рассматривается реализация алгоритма с помощью массивов, STL контейн
Описывается два основных способа организации обработки данных: итеративный и рекурсивный. Рассматривается набор олимпиадных задач, которые решаются при помощи итеративного и рекурсивного подхода.
Описываются числа Фибоначчи, их свойства и методы вычисления. Рассматривается набор олимпиадных задач, которые решаются при помощи чисел Фибоначчи.
Описывается расширенный алгоритм Евклида и рассматриваются его приложения к решению олимпиадных задач. Приводятся алгоритмы решения линейных сравнений и диофантовых уравнений.
Описывается один из классических методов поиска в графе – поиск в глубину. Представлена реализация поиска в глубину на несвязном (ориентированном) графе. Описана техника раскраски вершин и расстановки
В статье даны определения и свойства наибольшего общего делителя и наименьшего общего кратного, приведены алгоритмы их вычислений. Предложен разбор олимпиадных задач на эту тему.
В статье рассматривается структура данных, которая позволяет находить сумму соседних элементов массива, а также модифицировать их за логарифмическое время. Такую структуру называют сумматором, в статье она