информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медSpanning Tree Protocol: недокументированное применениеПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Эта ф-ция не диффернцируема 13.08.04 18:16  Число просмотров: 3045
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 13.08.04 18:22  Количество правок: 3
<"чистая" ссылка>
Пусть функция f(x) определена в некоторой окрестности точки x0. Рассмотрим приращение функции в этой точке: df(x)=f(x0+dx)-f(x0). Функция f(x) называется дифференцируемой в точке, если ее приращение можно записать в виде df(x)=A*dx+a(dx)*dx, где dx - приращение независимой переменной, А - постоянная, не зависящая от dx, a(dx) - бесконечно малая функция при dx->0.

Это как раз не твой случай.

Как ты минимумы будешь искать?

Ее необходимо заменить чем-то непрерывным или кусочно-непрерывным. А чем?!
<theory>
Факторизация больших 13.08.04 14:59  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.08.04 15:00  Количество правок: 1
<"чистая" ссылка>
А можно ли попробовать пробежаться в поисках "0" по локальным минимумам F(x)=N%x, на интервале x от 2 до sqrt(N)?
А как Ты выявишь области локальных минимумов отсюда? 13.08.04 16:37  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Я то подумаю. А спросил - узнать, может кто ковырял, и наковырял доказательства, что точно невозможно. Тогда и думать на эту тему не буду. В и-нете про это ничего не нарыл. 13.08.04 17:16  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.08.04 17:19  Количество правок: 3
<"чистая" ссылка>
Эта ф-ция не диффернцируема 13.08.04 18:16  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 13.08.04 18:22  Количество правок: 3
<"чистая" ссылка>
Пусть функция f(x) определена в некоторой окрестности точки x0. Рассмотрим приращение функции в этой точке: df(x)=f(x0+dx)-f(x0). Функция f(x) называется дифференцируемой в точке, если ее приращение можно записать в виде df(x)=A*dx+a(dx)*dx, где dx - приращение независимой переменной, А - постоянная, не зависящая от dx, a(dx) - бесконечно малая функция при dx->0.

Это как раз не твой случай.

Как ты минимумы будешь искать?

Ее необходимо заменить чем-то непрерывным или кусочно-непрерывным. А чем?!
Это понятно, что функция дискретная. Берем значение в точке... 16.08.04 12:03  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> Как ты минимумы будешь искать?

Это понятно, что функция дискретная. Берем значение в точке х, если значение в точке х-1 и в точке х+1 бльше, чем в х, то пусть это и будет локальный минимум.

> Ее необходимо заменить чем-то непрерывным или
> кусочно-непрерывным. А чем?!

Можно попробовать параболой, а лучше кубической кривой интерполировать. Правда есть такие участки, что пока еще не понятно чем.
Это случай не когда есть непрерывная табулированная... 16.08.04 13:04  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 16.08.04 13:06  Количество правок: 1
<"чистая" ссылка>
> > Как ты минимумы будешь искать?
>
> Это понятно, что функция дискретная. Берем значение в точке
> х, если значение в точке х-1 и в точке х+1 бльше, чем в х,
> то пусть это и будет локальный минимум.

Это случай не когда есть непрерывная табулированная (дискретизированная) ф-ция, а именно дискретная. Нахождение минимумов получается только перебором. И как туда аналитику прикрутить - фиг знает.

> > Ее необходимо заменить чем-то непрерывным или
> > кусочно-непрерывным. А чем?!
>
> Можно попробовать параболой, а лучше кубической кривой
> интерполировать. Правда есть такие участки, что пока еще не
> понятно чем.

Вот в том-то и дело. Если бы можно было какими-то хотя бы кусками аппроксимировать... чем-то, охватывающем как можно больше точек.
А что если попробовать выразить эту функцию как... 16.08.04 16:25  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
А что если попробовать выразить эту функцию как рекуррентную? И уже её пробовать исследовать. Как выразить опять же непонятно, но всё таки может у кого какие идеи появятся.. И потом можно искать не области минимумов, а по определённым значениям в точках рекуррентной функции исключать конкретные диапазоны, чем сокращать область поиска корней. Это, на мой взгляд, было бы более продуктивно..
Тут товарищь volizar уже что-то на тему рекуррентности... 18.08.04 12:39  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 18.08.04 12:45  Количество правок: 3
<"чистая" ссылка>
> А что если попробовать выразить эту функцию как
> рекуррентную? И уже её пробовать исследовать. Как выразить

Тут товарищь volizar уже что-то на тему рекуррентности писал:
"http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=105916"

Берём следующее простое число b2, так что b2<b1.
Ищем следующее d. Оно будет равно d: = d + (c - b2)*( b1 - b2).
Само c станет равно c: = c + (b1 - b2).
Если d будет больше b2, d >b2 , то
находим новое c, c = c + d/b2 (без остатка)
новое d, d = d (mod b2)


> опять же непонятно, но всё таки может у кого какие идеи
> появятся.. И потом можно искать не области минимумов, а по
> определённым значениям в точках рекуррентной функции
> исключать конкретные диапазоны, чем сокращать область

Ну и как тут исключить большой интервал?

> поиска корней. Это, на мой взгляд, было бы более
> продуктивно..

У меня есть еще мысль: Разбить ряд простых чисел на группы, перемножить числа в группах, получим несколько очень больших чисел, перебирая эти очень большие числа находим НОД с заданным. Если НОД = 1, берем следующее. Если НОД равен заданному, значит все множители заданного принадлежат этой группе. Иначе НОД и есть один из множителей. Второй находится делением. НОД находится очень быстро. Чтобы избежать попадпния множителей в одну группу, группируем по разному: первая тысяча в первую, вторая во вторую и т.д., затем все числа, стоящие на четных местах, в очередную группу, все на нечетных в еще одну. Проблема в получении произведений этих групп - добраться до килобитных чисел займет много времени. Возможен такой вариант: просто генерим огромное случайное число, оно может оказаться и простым, но с бОльшей вероятностью оно будет произведением множества простых чисел. Если НОД с ним равен заданному или единицы, генерим следующее. Бред это все, конечно, но может кто-нибудь оценит такой метод разложения на простые. Т.е. с вероятностью 0.95 килобитное число раскладывается за N лет на гигагерцовом писюке.
Тут понятие дефференциируемости неуместно 14.08.04 00:19  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Функция определена на N и следовательно такие понятия как "бесконечно малая" и иже с ними тут не работают. Но всё равно даже дать приблизительную оценку невозможно. Конкретного доказательства я не смогу привести, но достаточно просто построить график этой функции и посмотреть как она себя ведёт.
Раз речь пошла про экстремумы... 14.08.04 00:37  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
> Функция определена на N и следовательно такие понятия как
> "бесконечно малая" и иже с ними тут не работают. Но всё
> равно даже дать приблизительную оценку невозможно.
> Конкретного доказательства я не смогу привести, но
> достаточно просто построить график этой функции и
> посмотреть как она себя ведёт.

Я поэтому и говорю про дифференцируемость, ибо другого способа нахождения минимумов не знаю.

Думаю, теперь DPP ясно, что задача некорректна.

Когда ф-ция дифференцируема, тогда предыдущая точка как бы жестко связана со следующей... поэтому для нее можно много че хорошего вычислить, а в этом случае каждая следующая точка ведет себя "непредсказуемо".
Пример в тему 14.08.04 01:04  
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
> Я поэтому и говорю про дифференцируемость, ибо другого
> способа нахождения минимумов не знаю.

Конкретного способа на самом деле и не существует, однако если взять, например, функцию "наборот" f(x)=x mod n на всём множестве N, то она так же недифференциируема, однако мы можем определить минимумы - это kn. Поэтому и без дифференциирования хотя бы примерно область минимумов указать можно. В случае DPP, если число ~2^1024, то мы можем достаточно точно предположить, что минимум будет ~2^512 :-) Однако такие предположения сводятся к обычному перебору, к сожалению.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach