31.05.2018 20:55 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов Уважаемые участники форума , прошу сделать оценку вычислительной сложности алгебраического выражения. Привожу пошаговую процедуру его вычисления. Буду признателен за любое внимание к моей просьбе. Задаётся последовательность простых делителей р_1≤р_i≤р_m, i = 1, 2,.., m, р_1= 3. Рассматривается множество нечётных чисел х≤х_m, где〖 х〗_m=р_1 р_m. Применяется формула р_k(р_(i_1 ) р_(i_2 )) ≤√( x_m/(р_(i_1 ) р_(i_2 ) ) ) , с последующим отбором р_k из интервала р_1≤р_i≤р_m по его оценке . Числа р_m и х_m как угодно велики. Вычислительная сложность произведения〖 р〗_(i_1 ) р_(i_2 ) в худшем случае, то есть полагая, что все р_i имеют порядок р_m,равна∶T(n)=O(log^2 n) . Деление тоже имеет сложность T(n)=O(log^2 n). Корень может быть вычислен за время T(n)=O(log^3 n). Отбор (поиск) р_k на пронумерованном интервале р_i≤р_mтребует T(n)=O(log n). Символом n обозначена длина числа〖 х〗_m в бинарном представлении. Чему равна вычислительная сложность всей операции, включая поиск р_k? Как здесь работают правило произведения и правило суммы для T(n) ? Как найти примеры оценок вычислительной сложности алгебраических выражений. Редактировалось 1 раз(а). Последний 25.06.2018 20:02.
|
01.06.2018 11:31 Дата регистрации:
6 лет назад Посты: 17 | Уважаемые участники форума, выношу на обсуждение статью Бредихин Б.А. "Оценка вычислительной сложности комбинаторного метода факторизации чисел", размещенную в электронном журнале Куб ГАУ. http://ej.kubagro.ru/2017/10/pdf/06.pdf Уважаемые участники форума, выношу на обсуждение статью Бредихин Б.А. "Оценка вычислительной сложности комбинаторного метода факторизации чисел", размещенную в электронном журнале Куб ГАУ. http://ej.kubagro.ru/2017/10/pdf/06.pdf.Заранее благодарен за внимание и конструктивные замечания. Затрудняюсь в поиске требований к объёму и оформлению статьи на нашем форуме, поэтому вынужден применить ссылку на электронный журнал Куб ГАУ. Буду признателен администрации форума за соответствующее сообщение на мой E-mail.Обязуюсь выполнить все требования и разместить статью на форуме, а пока прошу извинить и сделать исключение для моей темы. Бредихин.
|
02.06.2018 14:57 Дата регистрации:
8 лет назад Посты: 130 | Непонятно. В статье "Комбинаторный метод факторизации" есть примеры но их для меня мало. Если строить графы как написано то никакой памяти и времени не хватит. Например в самом начале делителей может быть за миллиард и что делать тогда? И вообще номера делителей неизвестны алгоритму. Нельзя писать что 83 это 22 делитель а 47 это 14 - алгоритм эти номера не находил, и они ему неизвестны. Редактировалось 1 раз(а). Последний 02.06.2018 14:58.
|
14.06.2018 23:39 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов Отвечаю на вопрос xxyyzz и благодарю за внимание к моей статье"Комбинаторный метод факторизации".Прошу ознакомиться со статьёи"Оценка вычислительной сложности комбинаторного метода факторизации чисел".Буду признателен за все замечания и реко-мендации. Алгоритму комбинаторного метода задана пронумерованная последовательность простых чисел р_1≤р_i≤р_(m ) от минимального р_1 до максимального возможного р_(m ) в канонических разложениях чисел исследуемого интервала. Задача алгоритма – отобрать из заданной последовательности делители〖 р〗_(k_n ), ограничивающие кроны графа, по их оценкам вида р_(k_n )≤ β . Здесь β − максимально допустимое значение р_(k_n ) , определяемое формулой алгоритма. Далее не имеет значения в каком виде представлять делители на графе и в таблице. Однако их представление порядковыми номерами (индексами) существенно снижает объём печати. Древовидная структура (граф) применёна только для наглядности изложения и обоснования алгоритма таблицы факторизаций. Таблица содержит минимальную информацию о факторизации чисел, а её протяжённость обусловлена только длиной исследуемого интервала, как угодно малого в том числе. Таким образом таблица комбинаторного метода имеет объём печати, минимально возможный в задаче о факторизации. Потолок составления таблицы (как и потолок применимости метода) ограничен только обстоятельством непреодолимой силы − неограничен-ностью факторизуемых чисел и их разложений.
|
15.06.2018 12:05 Дата регистрации:
8 лет назад Посты: 130 | сложность Цитата
Алгоритму комбинаторного метода задана пронумерованная последовательность простых чисел р_1≤р_i≤р_(m ) от минимального р_1 до максимального возможного р_(m )
Ну если пронумерованная, тогда да. На практике такой трюк не имеет смысла, так как вся сложность будет именно в построении этой пронумерованной последовательности. Вроде как если есть такой "чёрный ящик" который по номеру выдаёт простое число или на оборот, по простому числу выдаёт его номер, то факторизация с таким ящиком делается быстро и без заморочек. Только я не помню где это доказывается. Там уже способ не важен.
|
16.06.2018 13:31 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов Отвечаю xxyyzz и благодарю за оперативную реакцию. Я не матёрый хакер ,но уверен , что моему компьютеру не сложно упорядочить заданную ему последовательность простых чисел по модулю, то есть по длине бинарного представления числа, и далее присвоить порядковый номер каждому числу. В этом нет никакого трюка. Однако нумерация чисел не обязательна. Алгоритм перемножением минимального простого числа ( 3 для ряда нечётных ) и максимального из заданных определяет правую границу интервала нечётных чисел, которые содержат только заданные факторы . Далее по формуле, в которую входят только уже заданные параметры, определяется оценка очередного делителя для графа. Сравнением по модулю оценки с заданными простыми выбирается делитель, наиболее близкий к оценке слева. После отыскания всех ограничивающих делителей − граф построен, то есть задача решена. Однако есть смысл всё-таки пронумеровать заданную последовательность простых чисел по модулю и выводить на печать не модуль делителя, а его порядковый номер (индекс). При этом все вычислительные операции алгоритма выполняются над модулями до выхода на печать. Это существенно сокращает объём печати и повышает потолок составления таблицы факторизаций. Построение графов при факторизации больших чисел не имеет смысла и не влияет на потолок применимости метода.
|
17.06.2018 01:03 Дата регистрации:
8 лет назад Посты: 130 | сложность Упорядочить заданную последовательность - элементарно, но только если она задана. Обычно неизвестно сколько простых чисел входит в заданный интервал. И само это узнавание - задача сложная. Хорошо, можете привести ещё несколько примеров? Не таких простых как в статье? например факторизуйте 337 (13*29), лучше первым способом. У вас там много всего не указано но подразумевается. Я могу сделать программу если пойму как это работает.
|
18.06.2018 21:10 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов Отвечаю xxyyzz и благодарю за оперативную реакцию. Сколько простых чисел входит в заданный интервал? Интервал начинается минимальным простым числом( 3 для ряда нечётных) и заканчивается заданным (максимальным). Произве-дение границ этого интервала есть правая граница интервала факторизуемых чисел.Числа, не превышающие эту границу,имеют в своих разложениях только заданные факторы. Можно задать границу интервала факторизации и определить затем максимально воз-можный фактор. Как видите,в этом нет никакой проблемы. Факторизуйте, например,337…….. Комбинаторный метод факторизует интервал чисел. Левой границей интервала в статье принято начало ряда нечёт-ных чисел.Однако это преследует чисто методические цели. Левую границу, как и правую, можно ( и нужно ) назначать по своему умыслу и рассматри-вать любой интервал натурального ряда в том числе как угодно малый. Всё об этом - только в моей монографии ( см. литература ) Можете привести несколько примеров…….. В статье « Оценка сложности……..» изложена пошаговая процедура построения графа. Этого изложения достаточнодля составления программы алгоритма. При желании рассмотреть другие примеры можно ознакомиться с главой «Факторизация больших чисел» в моей монографии. Я могу сделать программу…… Замечательная мысль!! Я уверен, что комбинаторный метод займет своё достойное место в Теории чисел и у вас есть шанс быть в числе первопроходцев в его освоении.Следует особо заметить, что на печать программа должна выдавать канонические разложения чисел в табличной форме. Древовидная структура для этой цели непригодна.Ясно также, что прикладной смысл имеет только програм-ма, составленная для произвольно заданного интервала натурального ряда. Если пойму…….. Поймёте – не святые горшки лепят. Месите глину! Я к Вашим услугам.
|
19.06.2018 11:23 Дата регистрации:
8 лет назад Посты: 130 | пример у вас в примере где 249 там дальше (p1) = 83 , (p2) = 47. Мне не понятно откуда появилось это 47 ?
|
20.06.2018 12:04 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов Уточняю: р_(k_2 )(р2) = 47 = p14. Это делитель, ограничивающий крону справа в графе s = 2. Смотрите крону графа со стволом 2 на рис. 2. Он рассчитан по формуле, выведенной в пункте 3 статьи. Определяется для всех стволов вида〖 р〗_(i_1 ) . Для графа s = 3 крону второго уровня придётся строить для стволов вида р_(i_1 ) р_(i_2 ), то есть для всех сочетаний делителей первого и второго уровней. Формулы для расчёта ограничивающих делителей приведены в каждом расчёте, выведены в пункте 3 статьи. Бог в помощь.
|
20.06.2018 15:11 Дата регистрации:
8 лет назад Посты: 130 | пример У вас совершенно не понятно что куда подставлять! Если бы я мог это понять читая вашу статью то не спрашивал бы, но вы пишите своим языком используя нестандартные обозначения. Понять это для меня не представляется возможным, поэтому я ещё раз вас прошу подставить значения в вашу формулу и вывести наконец число 47. 83 вы получили разделив 249 на 3(p1), а 47??? Или я ничего не понял?
|
20.06.2018 23:35 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов Что куда подставлять? Даю фрагмент статьи. Уровень n = 2: р_(k_2 ) р_(i_1 )≤ xm , р_(k_2 )(р_(i_1 )) ≤ x_m/р_(i_1 ) . р_(k_2 )(р1) ≤ (р_1 р_m)/р_1 = 249/3 = 83 , р_(k_2 )(р1) = 83 = p22. р_(k_2 )(р2) ≤ (р_1 р_m)/р_2 = 249/5 = 49,8 , р_(k_2 )(р2) = 47 = p14. Вот формула – это куда подставлять! В ней x_m/р_(i_1 ) − число 249 делится на каждый р_(i_1 )- делитель первой кроны и получается максимальный делитель второй кроны р_(k_2 )(р_(i_1 )) . Для делителя первой кроны〖 р〗_(i_1 )= р2=5 получается р_(k_2 )(5) ≤ 49,8 , то есть р_(k_2 )(5) = 47 = p14 − как ближайшее простое к числу 49,8 , которое является верхней оценкой для р_(k_2 )(5). В формуле стоит ≤ . Для делителя первой кроны р_(i_1 )= р1=3 получается р_(k_2 )(3) ≤ 83= p22 . Здесь число 83 простое и подбирать его не требуется, как в предыдущем случае, то есть искомое простое число совпадает с его оценкой . Смотрите рисунок 2. Считаю , что не имеет смысла обсуждать подобные элементарные вопросы. Если мы действительно хотим создать программу метода , то нам следует перейти к обсуждению более серьёзных вопросов, которые могут появиться только при достаточно глубоком изучении метода по двум моим статьям . Я применяю нормативную терминологию и символику в том числе в древовидной структуре, стараюсь быть понятым, остальное за вами.
|
21.06.2018 11:43 Дата регистрации:
8 лет назад Посты: 130 | сложность Вот теперь понятно. У вас вся сложность построения упирается в алгоритм поиска ближайшего простого и в количество частичных графов. Количество частичных графов экспоненциально возрастает от длины записи числа X макс. На действительно большом числе алгоритм встанет на поиске ближайшего простого к корню из Xм. Но даже если это пропустить, далее идёт построение частичных графов(не важно в таблице или ещё как нибудь) и количество этих построений - это номер простого Pk1. Уже после 12 значного этого номера, количество памяти превышает пределы современных компьютеров. А современные сложные задачи факторизации начинаются от чисел с 200 и выше количеством знаков. (до 100 знаков элементарно факторизуется решетом за несколько минут - десятков минут) Что вы хотите обсудить?
|
25.06.2018 19:40 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов «Количество частичных графов экспоненциально возра-стает от длины записи числа X макс…………» Число частичных графов первого уровня определяется из соотношения р_1≤р_(i_1 )≤р_(k_1 ) (s), где р_(k_1 ) (s) ≤√(s&x_m ). (Не смешите Бога, считая эту зависимость экспонентой).Отсюда, число стволов р_(i_1 )в графе порядка s равно k_1 (s) , то есть индексу максимально допустимого делителя. При достаточно больших значениях 〖 х〗_m можно принимать k_1=р_(k_1 )/ln〖р_(k_1 ) 〗 = (s√(s&x_m ))/ln〖x_m 〗 . При выборе границы интервала в виде x_m= р_1^(s_m ) получается: р_(k_1 ) (s)≤ р_1^(s_m/s). Из графика р_(k_1 ) (s) следует, что его значение с ростом порядка графа в пределах 2 ≤ s ≤ s_m/2 резко снижается от своего наибольшего значения р_(k_1 ) (2)≤ р_1^(s_m/2) до р_(k_1 ) (s_m/2)≤р_(1 )^2, то есть до значения р_(k_1 )=р_3.Таким образом, 〖 р〗_(k_1 )может быть проблемным только в графах младших порядков (s =2;3) Ясно, что〖 р〗_(k_1 )может быть как угодно большим при соответствующем выборе x_m. Однако при больших x_m рассматривать интервал x ≤x_m не только невозможно, но и не имеет смысла – факторизации будут повторяться. Практически следует рассматривать последовательность смежных интервалов вида x_1≤x ≤x_2, в том числе как угодно малых.(Пункт 5 статьи «Комб. метод…. » и пункт 3 статьи «Оценка сложности……») При факторизации каждого такого интервала из множества возможных частичных графов будут отбираться только немногие частичные графы , факторизующие числа этого интервала. И в память и на печать будет выдаваться ограниченная информация. Как видите, не так страшен чёрт …………. Отбор факторизующих графов может оказаться успешным уже в начале процесса , а может потребовать анализа любого числа графов из числа возможных. В этом у комбинаторного метода есть проблема. Но есть и возможности её решения: параллельные вычисления, исключение частичных графов по данным о составе факторов и другие пути, подлежащие исследованию. «Уже после 12 значного этого номера, количество памяти превышает пределы…………» Вы затрудняетесь извлечь корень из числа, которое собираетесь факторизовать. Но в его каноническом разложении может оказаться любой делитель 〖 р〗_i≤р_m=x_m /3.Модуль р_m и число этих делителей растут неограниченно вместе с x_m. Никакими ухищре-ниями вам не удастся снизить эти параметры. Именно по этой причине для любого метода факторизации существует потолок примене-ния по числу x , который обусловлен прежде всего возможностями вычислительной техники, а не природой алгоритма. Есть смысл повышать потолок метода для решения реальных практических задач, имеющих свой разумный потолок. Кроме того, повышение потолка таких задач происходит и по мере снижения вычислительной беспомощности. Однако в экзотических задачах типа взлома ключей такого потолка нет. Проблема решения таких задач обусловлена обстоятель-ством непреодолимой силы − неограниченностью числа х и числа его факторов. Эта проблема имеет сомнительное отношение к теории чисел. Теория алгоритмов занимается разрешимостью задач, а не преодолением их вычислительной сложности. Таким образом определяющим фактором при оценке научной значимости любого метода факторизации является не вычислительная сложность, а его новизна, позволяющая объяснить (если не открыть) какие-либо свойства натурального ряда. Преимущества комбинаторного метода , определяющие его новизну, изложены в заключении статьи. «….современные сложные задачи факторизации….» Какие задачи вы считаете современными? В победном тоне вы приводите пример эффективного применения метода решета. Но в нём во первых факторизуется число, а не интервал чисел, во вторых факторизация выполняется при заданном числе факторов. Комбинаторный метод решает такую задачу построением одного полного графа для как угодно малой окрестности заданного числа, в котором обособленность частичных графов допускает параллельные вычисления. В третьих , что даёт теории чисел этот трюк? Кому и что он даёт в прикладном плане? Для какой разумной и полезной цели нужны факторизации таких чисел? Метод решета имеет свою исторически сложившуюся научную и методическую ценность и достоин применения лучшего, нежели изготовление шулерских отмычек. «Что вы хотите обсудить?» Намерен обсуждать проблемы программирования алгоритма построения графа и составления таблицы. Только процесс програм-мирования позволит дать достоверную оценку вычислительной сложности комбинаторного метода и установить потолок его приме-нения в разумно поставленных задачах. Пошаговые процедуры построения графа и составления таблицы даны в статье «Оценка сложности….» Считаю, что дополняющую информацию лучше пересылать по электронной почте, дабы можно было передавать графику и не уродовать формулы.До начала составления программы нет смысла ломать копья. Месите глину. Горшки будем лепить вместе.
|
26.06.2018 10:57 Дата регистрации:
8 лет назад Посты: 130 | сложности Цитата
Именно по этой причине для любого метода факторизации существует потолок примене-ния по числу x , который обусловлен прежде всего возможностями вычислительной техники, а не природой алгоритма.
Это не так. Цитата
Проблема решения таких задач обусловлена обстоятель-ством непреодолимой силы − неограниченностью числа х и числа его факторов. Эта проблема имеет сомнительное отношение к теории чисел. Теория алгоритмов занимается разрешимостью задач, а не преодолением их вычислительной сложности.
В математике обстоятельство непреодолимой силы - доказательство. До сих пор не доказана невозможность постройки "быстрых" алгоритмов, но также не доказана возможность, и не представлен ни один алгоритм. Это имеет прямое отношение к теории чисел. Теория чисел также занимается "преодолением их вычислительной сложности" это тоже самое что и "разрешимость". Цитата
Таким образом определяющим фактором при оценке научной значимости любого метода факторизации является не вычислительная сложность, ....
Определяющим фактором "научной значимости" является полезность алгоритма. Пример- умножение Карацубы.((""Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций. Следует заметить, что при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение. ""отсюда https://habr.com/post/124258/)) Цитата
...а его новизна, позволяющая объяснить (если не открыть) какие-либо свойства натурального ряда. Преимущества комбинаторного метода , определяющие его новизну, изложены в заключении статьи
Новые свойства это хорошо. решето - неэффективно, но лучше пока не придумали. Параллельные вычисления - линейное ускорение, нам нужно экспоненциальное. Цитата
В третьих , что даёт теории чисел этот трюк? Кому и что он даёт в прикладном плане? Для какой разумной и полезной цели нужны факторизации таких чисел? Метод решета имеет свою исторически сложившуюся научную и методическую ценность и достоин применения лучшего, нежели изготовление шулерских отмычек.
Сейчас числа на "замках" стали такими длинными что метод решета уже не справляется на разумном количестве компьютеров. Вообще проблема глубже. Факторизация - "частный случай" проблемы P =? NP. Научимся быстро факторизовывать большие числа, возможно научимся также быстро решать задачи из "NP" Что такое проблема P против NP? P = класс задач с известным полиномиальным алгоритмом решения. NP = класс задач,для которых неизвестны/не существуют полиномиальные методы решения (в худшем случае) Проблема: возможен ли полиномиальный алгоритм для хотя бы одной задачи из "NP" До сих пор никому не удалось доказать возможность\невозможность полиномиального алгоритма для любой задачи из NP. Задачи "NP" это задачи оптимизации при заданых ограничениях и не только. Также в задачи "NP" легко кодируется много прикладных моделирующих задач. Если найти полиномиальный алгоритм хотя бы к одной из NP задач то это толкнёт науку (все сферы) очень хорошо так))) Эта та задача которую следует решать, всё остальное - "детский сад штаны на лямках" и топтание на месте.
|
26.06.2018 11:30 Дата регистрации:
8 лет назад Посты: 130 | теерь по делу Нет никаких проблем в программировании, весь ваш алгоритм простой. Проблема в понимании - мне вас трудно понимать, особенно все ваши эти обозначения. Давайте по порядку для графа второго порядка (для числа с двумя множителями): находим максимальный простой делитель P_макс <= корень из X, где X это факторизуемое число. Корень из X в программе делается элементарно. Ближайшее простое к корню из X придётся искать отдельным алгоритмом. Сделал (собрал из интернета) алгоритм нахождения ближайшего простого слева от заданного числа. К 15 значному числу находится ближайшее простое за время около 7 секунд. Но он не выдаёт порядковый номер этого простого. Можно ли обойтись без порядкового номера?
|
28.06.2018 09:08 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов. Можно ли обойтись без порядкового номера? Можно! Однако есть смысл всё-таки пронумеровать заданную последовательность простых чисел по модулю и выводить на печать не модуль делителя, а его порядковый номер (индекс). При этом все вычислительные операции алгоритма выполняются над модулями до выхода на печать. Это существенно сокращает объём печати и повышает потолок составления таблицы факторизаций.Факторы - числа длинные, а их индексы всё-таки короче (см. сообщение от 16 06 18). . Об алгоритме построения графа второго порядка. Извлечением корня из 〖 х〗_m вы нашли наибольший делитель первого уровня р_(k_1 ) , Все простые делители р_1 ≤ р_i≤ р_(k_1 ) будут стволами для крон второго уровня. Для каждого ствола крона начинается делителем, равным стволу, и заканчивается делителем , ближайшим к числу 〖 х〗_m, делённому на ствол. Число операций равно числу стволов (см.сообщение от 20 06 18) Но надо факторизовать интервал〖 x〗_1 < x ≤ x_2. Тогда придётся искать и левую границу кроны второго уровня, поделив x_1 на ствол. В кронах, у которых границы совпадают, искомых факторизаций нет. Эти стволы отбрасываю-тся. Стволов останется не больше числа искомых факторизаций. Как видите, вычислительная проблема состоит в вычислении и отборе границ крон, сравнении границ между собой с последующим отбором ограниченного числа стволов, имеющих ненулевые кроны. Всё просто ! Сделайте оценку сложности и сравните с моей в статье «Оценка…….» В графе третьего порядка при построении кроны второго уровня изменятся только формулы для вычисления оценок границ. Кроны третьего уровня строятся по такому же алгоритму, но для стволов вида р_(i_1 ) р_(i_2 ).Это совокупность сочетаний каждого отобранного стола первого уровня с каждым делителем его кроны. Пошаговая процедура построения графов изложена в статье «Оценка…..». Это не так! Это так! По своей природе алгоритм − это адекватное отображение реальных соотношений в задаче. Среди возможных алгоритмов решения данной задачи желаемого вами может не оказаться. Тогда уповайте на вычислительную технику. Преодоление выч. сложности это то же самое, что и разрешение……… Разрешимость задачи это наличие хотя бы одного алгоритма её решения. Невозможность его реализовать называется вычислительной беспомощностью. Она довольно быстро снижается. Уже существуют компьютеры с производительностью, измеряемой в петафлопсах (〖10〗^15 операций с плавающей запятой в секунду). Определяющим фактором "научной значимости" является полезность алгоритма. Правильно, добавим только: и в теории и на практике.Комбинаторный метод с помощью простого алгоритма приводит к цели непосредственно, а не путём последовательных испытаний, как ныне существующие. Он даёт возможность записать таблицу генетических кодов чисел как угодно малого интервала, заданного в любой точке натурального ряда. Таблица состоит из отдельных частей, отражающих классификацию составных чисел интервала (см. Заключение к статье Комб. метод). Научимся быстро факторизовать большие числа, возможно научимся также быстро решать задачи из "NP" Вы не определяете понятие «большое число», следовательно, полагаете его сколь угодно большим. Я определяю «большое число» как порог по x практической задачи, поставленной разумно. Пытаться вычислить объём или протяжённость вселенной неразумно. Что касается поиска «полиномиального метода», то бог вам в помощь. Однакосреди возможных алгоритмов решения данной задачи желаемого вами может не оказаться и тогда придётся надеть «штаны на лямках». Пожалуйста! Руководствуйтесь пошаговой процедурой, изложенной в статье " Оценка.....". Мне лучше отвечать вам по электронной почте.С уважением, borisaba.
|
28.06.2018 12:44 Дата регистрации:
8 лет назад Посты: 130 | сложность Индексы короче но их получение требует больших затрат вычислительных ресурсов. Фактически придётся реализовывать решето эратосфена которое прономерует все простые числа числа до X_макс. А это экспоненциальное время и экспоненциальная память. Можно использовать заранее сгенерированные пронумерованные последовательности простых чисел, но это будет жесткое ограничение на X_макс. Вы всю сложность убрали из "своего поля зрения" но она никуда не делась. Нет смысла использовать ваш алгоритм когда и так мы реализуем решето, уж тогда проще сразу через решето и искать делители. На готовой последовательности сложность вашего алгоритма будет пропорциональна длине этой последовательности, то-есть он будет линеен от длины последовательности. Обьём печати - по другому память компьютера (компьютеру всё равно в памяти у него число или в печати). Сложность любого алгоритма складывается из сложности по времени и сложности по памяти. Есть алгоритмы с полиномиальным временем работы, но с экспоненциальным количеством требуемой памяти. Если не нумеровать простые, и не использовать готовые последовательности, то похоже при постройке графов придётся перебирать все числа, ну или делать что-же самое - считать последовательности простых, а это экспоненциальное время и экспоненциальная память. Для чисел которые влезают в регистр процессора (это числа до 4 294 967 296 для 32 бит) полный перебор длиться секунды, нет никакого смысла городить огороды с последовательностями и графами. А с большими числами ваш алгоритм не будет быстрее. Это я всё про сложность. Цитата
Это так!...
Так да не так))) А может и оказаться))) Цитата
Правильно, добавим только: и в теории и на практике.Комбинаторный метод с помощью простого алгоритма приводит к цели непосредственно, а не путём последовательных испытаний, как ныне существующие.
Вы просто "последовательные испытания" вывели из под "своего поля зрения" но они никуда не делись))) Вашему алгоритму всё равно нужны последовательности и на сегодняшний момент единственный способ вычислить их - это использовать "последовательные испытания". Большое число это число от 200 до 1000 и более десятичных знаков. Полиномиальный алгоритм справиться с любым числом лишь бы оно влезло в память и ещё осталось для записи ответа. На одну цифру в компьютере тратиться 1 байт (грубо, это не всегда,и не суть) в 4 гигабайта влезет 4294967296 значное десятичное число. Современные ПК могут иметь 32 гигабайт оперативной и 4 терабайт на жёстком диске не говоря уже о серверах. Вот и думайте))) Зачем такие числа считать? Да незачем. А маленькие и стандартными способами обрабатываются неплохо. Вон даже онлайн калькуляторы неплохо числа раскладывают до 9 знаков. Вот как раз таки объём и протяженность - полиномиальные алгоритмы. Найти полиномиальный алгоритм для задачи факторизации - разумно. У меня есть косвенные подтверждения возможности существования такого алгоритма. Но я оставил эти поиски, и переключился на поиск полиномиального алгоритма для одной из NP задач, так как увидел возможность его найти, там кстати тоже графы))) поэтому меня и привлекла ваша статься, но я понял что у вас нет полиномиального алгоритма, а не экспоненциальные для меня представляют "чисто академический интерес". В теме изначально был вопрос о сложности - сложность вашего - экспоненциальная от длины числа, и линейная от длины последовательности. Но длина последовательности всё равно экспоненциально зависит от длины факторизуемого числа как и в решете (это тоже последовательность). Градации сложности в общем непринципиальны. На сложности можно поставить точку.
|
03.07.2018 20:12 Дата регистрации:
6 лет назад Посты: 17 | Вычислительная сложность алгоритмов. Признателен за обстоятельную и профессионально изложенную информацию. Она в какой-то мере послужила мне ликбезом. Согласен поставить точку после того как узнаю ваше мнение о выполненной мною оценке сложности двух задач, которые вам будут понятны .Вы можете ответить мне в любом кратком формате. Мне нужна уверенность в своих понятиях о сложности вычисления алгебраических выражений и алгоритма в целом. Надеюсь и заранее благодарю . Оценка сложности алгоритма построения графов первой версии Задано: р_1≤р_i≤р_m , i = 1, 2,.., m, р_1= 3. Установлено: х_m=р_1 р_m , 〖 s〗_(m )= | ln〖x_m 〗/ln〖р_1 〗 |. Кроны графов построены по условию р_(i_n )≥ 〖 р〗_(i_1 ). Граф s =2. Интервал 3 <х≤х_m. Уровень n =1. Применяется формула р_(k_1 )≤√(х_m ), с последующим от-бором р_(k_1 ) из последовательности р_1≤р_i≤р_m по его оценке. Эта операция выполняется однократно. Уровень n =2. Применяется формула р_(k_2 ) (〖 р〗_(i_1 )) ≤ x_m/р_(i_1 ) для каждого р_1≤р_(i_1 )≤р_(k_1 ) с последующим отбором 〖 р〗_(k_2 ) из последовательности 〖 р〗_1≤р_i≤р_m по его оценке 〖 р〗_(k_2 ) (〖 р〗_(i_1 )). Число таких операций равно индексу k_1. При достаточно больших значениях 〖 х〗_m можно принимать k_1=р_(k_1 )/ln〖р_(k_1 ) 〗 = (2√(x_m ))/ln〖x_m 〗 . Операция по отысканию оценки р_(k_2 )(〖 р〗_(i_1 )) имеет вычислительную сложность T(n) = O(log^2 n). Отбор (поиск) р_(k_2 ) на интервале〖 р〗_i≤р_m требует T(n)=O(log n). В итоге сложность построения кроны графа s =2 в стандартных обозначениях равна: T(n) =O(n^(1⁄2) log n). Здесь под n понимается длина входного параметра х_m в бинарном представлении. Такую же оценку имеет метод пробных делений однако он факторизует одно число, а комбинаторный метод – интервал чисел, мень-ших заданного. Кроме того, факторизация интервала вида〖 х〗_1<х≤х_2 открывает возможность снижения сложности алгоритма. В этом случае на уровне n = 2 в графах со стволами р_1≤ р_(i_1 )≤ р_(k_1 )(x_1) вычисляются делители р_(k_2 ) (x_2 )≤x_2/р_(i_1 ) , р_(k_2 ) (x_1 )≤x_1/р_(i_1 ) с последующим их отбором из интервала р_1≤р_i≤р_(m.) Кроны второго уровня в этих графах имеют вид р_(k_2 ) (x_1 )<р_(i_2 )≤р_(k_2 ) (х_2 ). . Кроны, в которых р_(k_2 ) (x_2 )> р_(k_2 ) (x_1 ) содержат только числа интервала 〖 х〗_1<х≤х_2 . Их следует вычислить по факторизациям. Кроны, в которых р_(k_2 ) (x_2 )= р_(k_2 ) (x_1 ) не содержат чисел интервала〖 х〗_1<х≤х_2 (пустые кроны) и должны быть отброшены. Процесс отбора непустых крон прекращается после факторизации всех чисел интервала. Успех может прийти быстро и может потребовать анализа всех крон. Вероятность быстрого успеха определяется числом факторизаций. В связи с этим можно пытаться оптимизировать процесс отбора крон и получить существенное снижение сложности. В связи с этим, для графа s = 2 оценку T(n) =O(n^(1⁄2) log n) следует считать оценкой наихудшего случая. Граф s = 3. Уровень n =2. Применяется формула р_(k_2 )(〖 р〗_(i_1 )) ≤√( x_m/р_(i_1 ) ) , для каждого 〖 р〗_1≤р_(i_1 )≤р_(k_1 ) с последующим отбором 〖 р〗_(k_2 ) из последовательности 〖 р〗_1≤р_i≤р_m . Число операций равно индексу k_1. При достаточно больших значениях 〖х〗_m можно принимать k_1=р_(k_1 )/ln〖р_(k_1 ) 〗 = (3∛(x_m ))/ln〖x_m 〗 . Операция по отысканию р_(k_2 )(〖 р〗_(i_1 )) имеет вычислительную сложность T(n) = O(log^2 n) . Отбор (поиск) р_(k_2 ) на интервале〖 р〗_i≤р_mтребует T(n)=O(log n).Сложность постро-ения кроны второго уровня в стандартных обозначениях будет равна: T(n) =O(n^(1⁄3) log n). Уровень n =3. Применяется формула р_(k_3 )(〖 р〗_(i_1 ),р_(i_2 )) ≤ x_m/(р_(i_1 ) р_(i_2 ) ) с после-дующим отбором р_(k_3 ) из последовательности 〖 р〗_i по его оценке . Вычислительная сложность произведения р_(i_1 ) р_(i_2 ) в худшем случае равна∶ T(n)=O(log^2 n) . Деление имеет сложность T(n)=O(log^2 n). В итоге операция по отысканию оценки р_(k_3 )(〖 р〗_(i_1 ),р_(i_2 )) имеет вычислительную сложность T(n) = O(log^2 n) . Отбор (поиск) р_(k_2 ) на интервале〖 р〗_i≤р_mтребует T(n)=O(log n). Число операций по отысканию р_(k_3 )(〖 р〗_(i_1 ),р_(i_2 )) то есть число сочетаний вида р_(i_1 ) р_(i_2 ), равно λ_3 =(〖x_m〗^(5⁄6) )/ln^2〖x_m 〗 .(Принять на веру.) В итоге вычислительная сложность построения кроны третьего уровня и графа s =3 равна: T(n) = O(n^(5⁄6)) . Если в этой задаче добавить корень ,то оценка получится такой. Применяется формула р_(k_3 )(〖 р〗_(i_1 ),р_(i_2 )) ≤√( x_m/(р_(i_1 ) р_(i_2 ) ) ) , с последующим отбором р_(k_3 ) из интервала р_1≤р_i≤р_m по его оценке. Дробь требует T(n)=O(log^2 n).Корень может быть вычислен за T(n)=O(log^3 n). Отбор р_(k_3 ) требует T(n)=O(log n). Сложность операции по отысканию〖 р〗_(k_3 ) , включая его отбор, будет равна: T(n)=O(log^3 n) согласно правилу суммы. Без корня она была равна: T(n)=O(log^2 n). Комбинаторный метод согласно изложенной выше оценке его сложности является экспоненциальным. Его можно отнести к группе алгоритмов , работающих за квазилинейное время T(n) =O(n〖 log〗^k n). Одним из близких к нему по сложности можно считать алгоритм сортировки слиянием, работающий за время T(n) =O(n〖 log〗^2 n). Затрудняюсь найти алгоритм с более близкой сложностью.
|
06.07.2018 11:48 Дата регистрации:
8 лет назад Посты: 130 | сложность Не не не, я не профессионал. Я тут просто мимо проходил)))) Вы пишите : Цитата
Операция по отысканию оценки р_(k_2 )(〖 р〗_(i_1 )) имеет вычислительную сложность T(n) = O(log^2 n)
Я так и не понял что это за операция, вы используете какие-то странные обозначения только вам понятные. Совершенно не нужно использовать такие запутанные обозначения. Но это не важно. На арифметические операции можно не смотреть - все они полиномиальны и линейны, можно даже сказать что "щёлкаются за 1 такт." Основа вашего алгоритма - поиск по заранее заданной (уже имеющийся) последовательности с отбором ближайшего с низу к некоторому числу. Эта операция (операция поиска) выполняется за время порядка О(log n), где n - число элементов этой последовательности (для структур данных типа хеш-таблицы - за время O(1) в среднем) Операция построения этой последовательности - экспоненциальная и точную её сложность я затрудняюсь определить. Далее у вас на каждом уровне исходная последовательность просто делиться на отрезки, и поиск дальше уже выполняется по ним, элементов больше не становиться, делить можно не больше количества раз чем n/2. Вот и получается что в худшем случае сложность О(n/2 log n), где n - количество элементов (простых чисел) в последовательности. Вообще я не математик и может быть я немного неправильно посчитал сложность но сути это не меняет.
|
