Введение в вероятностные алгоритмы

давайте представим что на марсоходе будет установлен генератор случайных чисел и мы должны будем создать алгоритм который должен обработать в реальном мире в реальном мире всегда существует вероятность ошибки главное чтобы эта вероятность была настолько несущественной что на нее можно было бы закрыть глаза если для вас это удивительно вспомните что в окружающей нас реальности не бывает стопроцентные определенности вероятность ошибки есть всегда например если мы рассмотрим чип то на нем всегда есть микроскопическое количество радиоактивных веществ в процессе распада они излучают альфа-частицы которые способны переключить бит в компьютерной памяти и хранящиеся там число внезапная изменится более того космические лучи также могут вызвать программные ошибки поэтому полностью исключать вероятность ошибки нельзя я уточнил какая вероятность ошибки будет приемлемой для марсохода и мне ответили нас устроит чтобы для каждой проверке вероятность ошибки была равна двум джек-потом подряд в лотерее 6 из 49 вероятность два раза подряд выиграть в лотерее 6 из 49 приблизительно равна 6 на 10 в минус 14 степени можно перестраховаться и округлить это число к меньшему значению пусть допустимая для нас вероятность ошибки 10 в минус 15 степени это достаточно надежно ошибка вряд ли появится даже за сотни или тысячи итерации алгоритма у вас может возникнуть вопрос может ли генератор случайных чисел ускорить алгоритм принятия решения например проверки числа на простоту это очень хороший вопрос давайте сделаем шаг назад и снова рассмотрим исходную задачу пусть у нас есть набор целых чисел от 1 до некоего предела это будет наше универсальное множество целых чисел его можно разделить на два подмножество и алгоритма проверки как раз относится к вопросу разделения на 2 подмножество например вопрос является ли число n меньше ста алгоритма проверки даст ответ да для всех целых чисел которые и меньше ста это будет один набор и нет для всех остальных чисел это будет второе подмножество а теперь давайте вернёмся к поиску простых чисел мы хотим найти такой элементарный признак который был бы свойственен всем простым и только простым числам тогда для любого числа n достаточно было бы проверить наличие такого признака проблема в том что такого простого и легко вычисляемого признака по которому можно однозначно отличить простое число от составного до сих пор найти не удалось но мы знаем быстро вычисляемые признаки для большинства составных чисел например самый быстрый такой критерий это проверка на четность все четные числа делятся на 2 алгоритм проверки будет очень быстром достаточно взглянуть на последнюю цифру и с увеличением числа n сложность решения задачи несколько не растет нам по-прежнему достаточно взглянуть лишь на последней двоичный разряд так называемый младший бит теперь представьте что мы используем проверку на четность в качестве очень ненадежные проверки на простоту наш алгоритм будет принимать некое число n и проверять является ли она четным если число чётное и больше двух то мы на сто процентов уверены что оно составное у нас есть доказательства делитель двойка это и есть такой признак но если алгоритм выдал нет то мы не уверенны является ли число простым нечетное число может быть простым потому что все простые числа больше двойки нечетные но нечетное число может быть и составным например 9 или 15 и огромное количество составных нечетных чисел делает такой критерий неприемлемым давайте поясню на схеме нам дано число n она или простое или составное если оно простое алгоритм со стопроцентной вероятностью ответят верно простых четных чисел больше двойки не бывает но тогда алгоритм не сможет точно отличить составное от простого если число n составное наш алгоритм в половине случаев назовет его составным в половине случаев простым то есть если алгоритм отвечает число составное значит он нашел 100 процентное доказательство делитель 2 а если наш алгоритм отвечает число простое то мы знаем что он с неприемлемой для нас вероятностью ошибается мы с вами научились обходить эту неприемлемую вероятность ошибки при помощи нескольких итераций нарисуем схему работы нашего алгоритма на вход поступает некое число n и алгоритм проводят серию проверок на делимость начиная со равно двум он проверяет делится ли n на а и если не делятся то всю закрашенную половину можно исключить тогда мы задаёмся новым вопросом делится ли n на 3 если нет мы исключаем вот эту область дальше проверяем делимость на 57 и так далее и эта последовательность непересекающихся участков постепенно закрашивает всю область составных чисел если на какой-то итерации алгоритм отвечает да значит мы нашли доказательства что n составное и значение а в этот момент и есть это самое доказательства цикл проверок прерывается и алгоритм отвечает число составное в противном случае мы продолжаем проверять пока не исключен все возможные составные числа пока не дойдем до корня квадратного из n как вы помните у любого составного числа n обязательно должен быть делитель меньший или равный корню из n и тогда алгоритм тоже заканчивает работу если под ящик делителей не найдено а число а стало больше корня из n это и будет доказательство его простоты и алгоритм отвечает число простое таким образом алгоритм может закончиться двумя способами оба варианта на сто процентов доказывают простое или составное число на входе если число простое то мы перебираем все возможные делители исключаем их и это будет доказательством его простоты проблема этого алгоритма в том что в худшем случае нам придется перебирать все простые числа от 2 до корня из n и с увеличением числа n растет и количество возможных простых делителей а значит растет и количество итераций для худшего варианта когда алгоритм получил на входе простое число с другой стороны такой алгоритм абсолютно точно доказывает простоту числа n но сейчас от нас не требуется стопроцентной уверенности нас не просят доказать простоту от нас просят уверенности с вероятностью 99 целых и пятнадцать девяток после запятой и процентов возможно имеет смысл пересмотреть принцип проверки на делимость если вы помните самый быстрый наш алгоритм поиска простых чисел пользовался шаблоном например тем что все простые числа имеют вид 6k плюс минус 1 так к нам попадали только простые числа и мы не тратили время на составные и такой алгоритм можно модифицировать превратить его в алгоритм проверки простоты если входное число n имеет вид 6k плюс минус 1 мы можем сказать что она возможно простое однако такой же вид имеет многие составные числа этот критерий не отсекает только простые числа он отсекает все простые больше тройки плюс и еще какое-то количество составных и это количество лишних составных можно рассматривать как некую погрешность нашего алгоритма а если число больше 3 и не имея это вид 6k плюс минус 1 то мы с полной уверенностью можем заявить что оно составное так что ошибаемся мы только с определением простых чисел но погрешность такого критерия тоже слишком велика вероятность ошибки превышает допустимые границы нужно придумать какой-то другой критерий который уменьшит вот этот участок и снизят ошибку до допустимого уровня а значит надо подумать как снижать границу ошибки с каждой итерацией попробуйте предложить в комментариях к этому видео свои критерии и подумать как а в этом может помочь генератор случайных чисел спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них