Простыми словами
Хочу подробнее остановиться на том примере, который привела в прошлой записи.
Задача формулируется очень просто: определить, является заданное число простым или составным.
читать дальшеЕсли у нас нет свидетеля, точнее, кандидата на роль делителя, на который нам достаточно поделить, чтобы убедиться, что это на самом деле делитель, — наша задача перебрать все простые числа, которые гипотетически могут претендовать на роль делителя. На самом деле, боюсь, легче проверять все числа подряд, а не только простые. Перебирать достаточно числа, не превосходящие квадратного корня из данного числа.
О! Вот тут вопрос для самопроверки))))
Вопрос. Определить класс сложности этого алгоритма (алгоритма "перебора делителей") в терминах О-нотации, или вообще в каких бы то ни было терминах.
Вообще на самом деле, поскольку большие простые числа очень активно используются в криптографии, то важно иметь быстрые алгоритмы, которые помогают определить, простое число перед нами, или составное. Такие алгоритмы называются тестами простоты.
Те, кто ответит на вопрос для самопроверки, убедятся, что сложность самого простого и естественного, с первого взгляда, алгоритма значительно превосходит полиномиальную. Однако, человеческая мысль не стоит на месте. Разработано достаточно много полиномиальных тестов простоты. Однако сами эти алгоритмы (простите за каламбур) не так уж просты!
Причем, то, что задача проверки на простоту полиномиально разрешима в общем виде, было доказано только в 2002 году! Однако предложенный детерминированный алгоритм оказался достаточно сложным, и это, конечно, сильно затрудняет его применение!
И вообще, здесь, конечно, палка о двух концах: чем больше мы пытаемся упростить алгоритм в терминах алгоритмической сложности, тем больше мы запутываем сам алгоритм, и, как следствие, код программы, пока он не станет совершенно нечитабельным!
***
Я читала где-то (очень давно, правда, в те времена, когда машины были не столь быстры, и время работы даже маленькой программы существенно зависело от ее структуры), что для ускорения хода работы программы желательно все циклы насколько это возможно писать линейно!
О чем я? Вот, представьте, у нас есть массив, состоящий из десяти элементов. Нам нужно каждому элементу присвоить его порядковый номер, умноженный на два.
Массив — это такая структура данных: как длинный ящик с перегородками, делящими его на ячейки. Название у него одно, но в каждой ячейке лежит своё значение.
Вот, например, пустой массив с именем А:
Название каждого его элемента состоит из двух частей: имени всего массива (А) и своего личного порядкового номера (нечто вроде адреса его проживания).
Все элементы массива должны иметь одинаковый тип данных. (На самом деле, тут всё чуть сложнее, но сейчас речь не об этом). В нашем случае "имеют одинаковый тип данных" означает, что все элементы могут быть либо числами (все сразу), либо строками (тоже все сразу). Если числами, то либо все они хором целые, либо вещественные, либо еще всякие и разные (а бывает их в машинном представлении много). Главное, что все десять значений могут быть только какого-то одного типа.
И вот теперь представьте, что нам нужно в каждую такую ячейку положить число.
Как я уже говорила, к примеру, число, вдвое большее номера каждого элемента. То есть в первую ячейку положить двойку, во вторую — четверку, в третью — шестерку, и т.д.
Обычно это делается в цикле, который на псевдоязыке выглядит следующим образом:
для i от 1 до 10 с шагом 1
Аi = i*2
конец цикла
i — это вспомогательная переменная, называемая счетчиком цикла. Она пробегает все значения от 1 до 10 с шагом 1 (то есть цикл обернется вокруг себя 10 раз), и в каждый элемент массива положится его значение.
Так вот, к чему я так долго веду.
Этот алгоритм, написанный проще всего, имеет самую большую сложность из всех алгоритмов, которые мы могли бы предложить для решения этой задачи.
Вот такой алгоритм считал бы (почти) вдвое быстрее:
для i от 1 до 9 с шагом 2
Аi = i*2
Аi+1 = (i+1)*2
конец цикла
Что мы здесь сделали?
Мы за каждый проход цикла стали вычислять не одно значение массива, а сразу два. Тем самым цикл укоротился вдвое (хотя тело его удлинилось, но это как раз менее существенно).
А вот такой алгоритм будет работать еще быстрее:
для i от 1 до 6 с шагом 5
Аi = i*2
Аi+1 = (i+1)*2
Аi+2 = (i+2)*2
Аi+3 = (i+3)*2
Аi+4 = (i+4)*2
конец цикла
Здесь у нас получится всего два прохода цикла вместо 10. (Нетрудно проверить, что результат у всех трех алгоритмов будет один и тот же!)
И наконец, самым быстрым будет вот такой вот линейный алгоритм:
А1 = 2
А2 = 4
А3 = 6
А4 = 8
А5 = 10
А6 = 12
А7 = 14
А8 = 16
А9 = 18
А10 = 20
Не шучу!
Это хорошо, когда известно заранее, сколько нам надо сделать шагов! Если же нет (мы не знаем длины массива до определенного времени), то без цикла всё же не обойтись, но предлагается делать его "большими шагами", как показано для случаев с шагом 2 и 5.
И вот, представьте, это задача не просто элементарная, а наипростейшая! Что же говорить о задачах сложных! Чтобы понизить алгоритмическую сложность, сами алгоритмы, и тексты соответствующих им программ усложняют до немыслимой степени! И разобраться в них зачастую очень и очень непросто.
Кроме того, возвращаясь к проверке больших чисел на простоту. Тут нас поджидает еще одна, на этот раз техническая проблема. В компьютере могут храниться разные типы данных. Каждый числовой тип, даже самый "вместительный" может хранить числа до какого-то максимального значения. А дальше — стоп! Переполнение! Numeric Overflow! И поэтому помимо всех вышеизложенных проблем, стоит еще проблема представления больших чисел и их обработки!
Можете себе представить? Мы вынуждены хранить число не целиком, а кусочками, и тем не менее нам нужно узнать, поделится оно на что-нибудь или нет! О-о-о! Здесь всё совсем непросто!
Однако, люди всё-таки имеют большой опыт каким-то образом выходить из трудных ситуаций.
Так, например, для некоторых классов чисел придумали специализированные эффективные тесты простоты.
Хотя, конечно, далеко не для всех...
Задача формулируется очень просто: определить, является заданное число простым или составным.
читать дальшеЕсли у нас нет свидетеля, точнее, кандидата на роль делителя, на который нам достаточно поделить, чтобы убедиться, что это на самом деле делитель, — наша задача перебрать все простые числа, которые гипотетически могут претендовать на роль делителя. На самом деле, боюсь, легче проверять все числа подряд, а не только простые. Перебирать достаточно числа, не превосходящие квадратного корня из данного числа.
О! Вот тут вопрос для самопроверки))))
Вопрос. Определить класс сложности этого алгоритма (алгоритма "перебора делителей") в терминах О-нотации, или вообще в каких бы то ни было терминах.
Вообще на самом деле, поскольку большие простые числа очень активно используются в криптографии, то важно иметь быстрые алгоритмы, которые помогают определить, простое число перед нами, или составное. Такие алгоритмы называются тестами простоты.
Те, кто ответит на вопрос для самопроверки, убедятся, что сложность самого простого и естественного, с первого взгляда, алгоритма значительно превосходит полиномиальную. Однако, человеческая мысль не стоит на месте. Разработано достаточно много полиномиальных тестов простоты. Однако сами эти алгоритмы (простите за каламбур) не так уж просты!
Причем, то, что задача проверки на простоту полиномиально разрешима в общем виде, было доказано только в 2002 году! Однако предложенный детерминированный алгоритм оказался достаточно сложным, и это, конечно, сильно затрудняет его применение!
И вообще, здесь, конечно, палка о двух концах: чем больше мы пытаемся упростить алгоритм в терминах алгоритмической сложности, тем больше мы запутываем сам алгоритм, и, как следствие, код программы, пока он не станет совершенно нечитабельным!
***
Я читала где-то (очень давно, правда, в те времена, когда машины были не столь быстры, и время работы даже маленькой программы существенно зависело от ее структуры), что для ускорения хода работы программы желательно все циклы насколько это возможно писать линейно!
О чем я? Вот, представьте, у нас есть массив, состоящий из десяти элементов. Нам нужно каждому элементу присвоить его порядковый номер, умноженный на два.
Массив — это такая структура данных: как длинный ящик с перегородками, делящими его на ячейки. Название у него одно, но в каждой ячейке лежит своё значение.
Вот, например, пустой массив с именем А:
Название каждого его элемента состоит из двух частей: имени всего массива (А) и своего личного порядкового номера (нечто вроде адреса его проживания).
Все элементы массива должны иметь одинаковый тип данных. (На самом деле, тут всё чуть сложнее, но сейчас речь не об этом). В нашем случае "имеют одинаковый тип данных" означает, что все элементы могут быть либо числами (все сразу), либо строками (тоже все сразу). Если числами, то либо все они хором целые, либо вещественные, либо еще всякие и разные (а бывает их в машинном представлении много). Главное, что все десять значений могут быть только какого-то одного типа.
И вот теперь представьте, что нам нужно в каждую такую ячейку положить число.
Как я уже говорила, к примеру, число, вдвое большее номера каждого элемента. То есть в первую ячейку положить двойку, во вторую — четверку, в третью — шестерку, и т.д.
Обычно это делается в цикле, который на псевдоязыке выглядит следующим образом:
для i от 1 до 10 с шагом 1
Аi = i*2
конец цикла
i — это вспомогательная переменная, называемая счетчиком цикла. Она пробегает все значения от 1 до 10 с шагом 1 (то есть цикл обернется вокруг себя 10 раз), и в каждый элемент массива положится его значение.
Так вот, к чему я так долго веду.
Этот алгоритм, написанный проще всего, имеет самую большую сложность из всех алгоритмов, которые мы могли бы предложить для решения этой задачи.
Вот такой алгоритм считал бы (почти) вдвое быстрее:
для i от 1 до 9 с шагом 2
Аi = i*2
Аi+1 = (i+1)*2
конец цикла
Что мы здесь сделали?
Мы за каждый проход цикла стали вычислять не одно значение массива, а сразу два. Тем самым цикл укоротился вдвое (хотя тело его удлинилось, но это как раз менее существенно).
А вот такой алгоритм будет работать еще быстрее:
для i от 1 до 6 с шагом 5
Аi = i*2
Аi+1 = (i+1)*2
Аi+2 = (i+2)*2
Аi+3 = (i+3)*2
Аi+4 = (i+4)*2
конец цикла
Здесь у нас получится всего два прохода цикла вместо 10. (Нетрудно проверить, что результат у всех трех алгоритмов будет один и тот же!)
И наконец, самым быстрым будет вот такой вот линейный алгоритм:
А1 = 2
А2 = 4
А3 = 6
А4 = 8
А5 = 10
А6 = 12
А7 = 14
А8 = 16
А9 = 18
А10 = 20
Не шучу!
Это хорошо, когда известно заранее, сколько нам надо сделать шагов! Если же нет (мы не знаем длины массива до определенного времени), то без цикла всё же не обойтись, но предлагается делать его "большими шагами", как показано для случаев с шагом 2 и 5.
И вот, представьте, это задача не просто элементарная, а наипростейшая! Что же говорить о задачах сложных! Чтобы понизить алгоритмическую сложность, сами алгоритмы, и тексты соответствующих им программ усложняют до немыслимой степени! И разобраться в них зачастую очень и очень непросто.
Кроме того, возвращаясь к проверке больших чисел на простоту. Тут нас поджидает еще одна, на этот раз техническая проблема. В компьютере могут храниться разные типы данных. Каждый числовой тип, даже самый "вместительный" может хранить числа до какого-то максимального значения. А дальше — стоп! Переполнение! Numeric Overflow! И поэтому помимо всех вышеизложенных проблем, стоит еще проблема представления больших чисел и их обработки!
Можете себе представить? Мы вынуждены хранить число не целиком, а кусочками, и тем не менее нам нужно узнать, поделится оно на что-нибудь или нет! О-о-о! Здесь всё совсем непросто!
Однако, люди всё-таки имеют большой опыт каким-то образом выходить из трудных ситуаций.
Так, например, для некоторых классов чисел придумали специализированные эффективные тесты простоты.
Хотя, конечно, далеко не для всех...
@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato
-
-
06.07.2008 в 22:12Поскольку речь идет о теории, а не о практике, не будем привязываться ни к какому конкретному языку (так и будем работать с псевдоязыком), и будем считать, что одна команда (любая) — это один шаг алгоритма.
Возьмем алгоритм 1:
для i от 1 до 10 с шагом 1
А(i) = i*2
конец цикла
Посмотрим, за сколько шагов он отработает.
В нем три строчки.
В первой строчке проверяется, правда ли i не меньше единицы и не больше десяти;
во второй строчке вычисляется величина i*2 и помещается в элемент Ai;
в третьей строчке счетчик увеличивается на единицу (да-да, за увеличение счетчика как раз отвечает оператор конце цикла).
Итого цикл прокрутился 10 раз, каждый раз выполнилось 3 действия. Общий результат: 10*3=30 шагов.
Алгоритм 2.
для i от 1 до 9 с шагом 2
А(i) = i*2
А(i+1) = (i+1)*2
конец цикла
Здесь у нас за каждый проход цикла выполняется не три, а четыре действия (каждое действие — строка программы; их четыре). Проходов цикла у нас уже не десять, а 5.
Общее число шагов: 5*4=20.
В полтора раза меньше, чем в первом алгоритме (значит, когда я говорила "в два раза", чуть-чуть приврала))) Хотя, операторы цикла и операторы присваивания неравнозначны (а здесь это не учитывается)
Алгоритм 3.
для i от 1 до 6 с шагом 5
А(i) = i*2
А(i+1) = (i+1)*2
А(i+2) = (i+2)*2
А(i+3) = (i+3)*2
А(i+4) = (i+4)*2
конец цикла
В этом алгоритме всего два прохода цикла; в каждом по 7 действий:
2*7=14
Вот это уже больше чем вдвое меньше первоначального.
И, наконец, наш линейный алгоритм.
А(1) = 2
А(2) = 4
А(3) = 6
А(4) = 8
А(5) = 10
А(6) = 12
А(7) = 14
А(8) = 16
А(9) = 18
А(10) = 20
Он состоит из десяти шагов. Это улучшило нашу первую версию втрое. И для такого смешного примера это на самом деле немало!
-
-
11.07.2008 в 16:25-
-
11.07.2008 в 20:20я, когда готовила эти материалы, смотрела на все эти алгоритмы.
Честно говоря, от вероятностных (вернее от краткого их изложения) просто мороз по коже пробирал... И даже, я бы сказала, охватывал мистический ужас
Особенно меня тронули сильно псевдопростые числа ))))))
-
-
11.07.2008 в 20:20-
-
11.07.2008 в 21:45На мой взгляд они гораздо проще, чем детерминированные...
-
-
11.07.2008 в 21:49я не о простоте, а о конечном результате!
доказать ведь простоту с помощью этих тестов нельзя!
-
-
11.07.2008 в 22:08Вероятность успешного прохождения n тестов МР для составного числа m равна P(n) = 1/4^n
-
-
11.07.2008 в 22:1650 проверок... Каждая из которых полиномиальна... Не так уж и быстро выходит.
Да и всё-таки, согласись, вероятность маленькая, но не равная нулю. Стоит сработать закону больших чисел, и кирдык. Что-то да навернется.
А если учесть темпы роста информации, то это выходит из области фантастики.
Нет, всё же наша
кондоваядетерминированная система круче! Надежнее! )))(теорема Демитко),
я правда, про это ничего не слышала...
надо почитать.
-
-
11.07.2008 в 22:28В инете теоремы на отдельной странице. Я смотрел. Но использовалась в нашем ГОСТе.
iu8.da.ru/cgi-bin/nph-stat.pl?path=iu8/5c/52cl/...
Стр. 13-14.
А еще на стр. 8 интересные формулы по простым числам.
-
-
11.07.2008 в 22:41Спасибо! )))
-
-
16.02.2009 в 17:53ссылка www.math.princeton.edu/~annals/issues/2004/Sept...
Docent
-
-
16.02.2009 в 21:38Спасибо за ссылку!
Надо попробовать разобраться.
-
-
08.06.2009 в 01:23Вот древняя, но полезная статья: cgm.computergraphics.ru/content/view/142
P.S. Извиняюсь за некропост
-
-
08.06.2009 в 14:33Насчет "раскрывать циклы" — по-моему это очень наглядная вещь для вот таких объяснений. Но на практике применять это прямо вот так — думаю, вряд ли кому-то придет в голову.
По крайней мере я к этому не призываю.
Однако существует большое количество быстрых алгоритмов, которые, конечно, гораздо эффективнее нежели просто линеаризация циклов.
Спасибо за замечание и ссылку.