Важность рандомизированных алгоритмов

Введение:

• Рандомизация является важной концепцией, поэтому алгоритмы рандомизации используются в различных областях, таких как теория чисел, вычислительная геометрия, теория графов и распределенные вычисления.
• Входные данные для рандомизированного алгоритма аналогичны входным данным для детерминированных алгоритмов, наряду с последовательностью случайных битов, которые могут использоваться алгоритмом для осуществления случайного выбора.
• Другими словами, рандомизированный алгоритм — это алгоритм, поведение которого зависит от входных данных, подобно детерминированному алгоритму, и случайный выбор осуществляется как часть его логики.
• В результате алгоритм дает разные результаты даже для одного и того же входа.
• Другими словами, алгоритм демонстрирует случайность; следовательно, его время выполнения часто объясняется случайной величиной.

Преимущества:

• Рандомизированные алгоритмы известны своей простотой.
• Любой детерминированный алгоритм может быть легко преобразован в рандомизированный алгоритм. Эти алгоритмы очень просты для понимания и реализации.
• Рандомизированные алгоритмы очень эффективны.
• Они используют мало времени и места для выполнения по сравнению с любыми детерминированными алгоритмами.
• Рандомизированные алгоритмы демонстрируют лучшие асимптотические оценки по сравнению с детерминированными алгоритмами.
• Другими словами, сложность алгоритма рандомизированных алгоритмов лучше, чем у большинства детерминированных алгоритмов.
• Надежность является важным вопросом во многих критических приложениях, поскольку не все рандомизированные алгоритмы всегда дают правильные ответы.
• Кроме того, многие рандомизированные алгоритмы могут не завершаться.
• Следовательно, надежность является важной проблемой, с которой необходимо иметь дело.
• Качество рандомизированных алгоритмов зависит от качества генератора случайных чисел, используемого как часть алгоритма.
• В отличие от других парадигм проектирования, рандомизированный алгоритм не использует единый принцип проектирования.
• Вместо этого следует рассматривать рандомизированные алгоритмы как алгоритмы, разработанные с использованием набора принципов.
• Вместо этого следует рассматривать рандомизированные алгоритмы как алгоритмы, разработанные с использованием набора принципов.

Некоторые принципы проектирования перечислены в следующих подразделах:

Концепция свидетеля :

• Этот принцип включает в себя вопрос проверки того, обладает ли данный вход свойством X или нет.
• Он устанавливается путем нахождения определенного объекта, называемого свидетелем или сертификатом.
• Свидетель идентифицируется, чтобы доказать тот факт, что входные данные действительно обладают желаемым свойством X.
• Проведя меньше испытаний, можно выяснить, действительно ли присутствовало имущество.
• Присутствие свидетеля является убедительным доказательством собственности X, основанным на отсутствии свидетелей. Этот принцип иллюстрируется на примере проверки простоты.

Отпечатки пальцев :

• По определению отпечаток пальца — это более короткое сообщение, представляющее более крупный объект.
• Отпечатки пальцев — это метод, при котором сравнивают два больших объекта, А и В, только путем сравнения их соответствующих коротких отпечатков пальцев.
• Если два отпечатка пальцев не совпадают, то объекты A и B различны.
• Однако если отпечатки пальцев совпадают, то есть веские косвенные доказательства того, что оба объекта одинаковы.

Проверка личности :

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

Случайная выборка и заказ :

• Производительность алгоритма иногда улучшается за счет рандомизации входного распределения или порядка.
• Можно заметить, что при определенном порядке ввода производительность алгоритма может быть выше или просто приемлемой.
• Здесь рандомизация приводит к рандомизированному упорядочению, разбиению и выборке.
• Кроме того, рандомизированные алгоритмы собирают информацию о входных распределениях, используя случайные выборки. Это иллюстрируется проблемой найма.

Обездвиживание противника :

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