О сложности самокорректирующихся алгоритмов для двух задач поиска

Для задачи поиска $m$-го по величине элемента и задачи одновременного поиска минимального и максимального элементов во множестве мощности $n$ рассмотрены алгоритмы, основанные на попарном сравнении его элементов. При этом считалось, что некоторые сравнения могут быть выполнены неправильно, причем общее число ошибочных сравнений не превышает заданной величины $k$, зависящей, быть может, от $n$. Показано, что для первой задачи при $m=o(n/\log n)$ асимптотически оптимальный алгоритм, корректирующий $k$ ошибочных сравнений, получается из асимптотически наилучшего (без самокоррекции) алгоритма многократным дублированием каждого сравнения. Для второй задачи в предположении, что $k\to\infty$ при $n\to\infty$, построен самокорректирующийся алгоритм, который, с одной стороны, существенно проще алгоритма многократного дублирования, но, с другой стороны, значительно сложнее наилучшего алгоритма без требования самокоррекции. Доказана асимптотическая оптимальность этого алгоритма.