Здесь больше нет рекламы. Но могла бы быть, могла.


Ответ

Имя:
E-mail:
Тема:
Иконка сообщения:

подсказка: нажмите alt+s для отправки или alt+p для предварительного просмотра сообщения


Сообщения в этой теме

Автор: Mrrl›
« : 27/12/2005, 22:13:17 »

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

               


               

      
Автор: Арвинд›
« : 27/12/2005, 21:30:12 »


Цитата из: Mrrl on 27-12-2005, 20:05:14
А sum(i*log(i)) - это больше, чем n2. Не играет
Логично, блин. Что-то я сильно тормознул.

Однако, оценка n*sqrt(2*log2n)*2^sqrt(2*log2n) приводилась вроде бы до того, как алгоритм был дополнен линейным поиском с.т. по значению (CheckVal)? Значит, теперь, если аккуратно считать, должно получиться больше.
Извиняюсь, что задаю вопрос, не разобравшись  ;)

               

               
Автор: Mrrl›
« : 27/12/2005, 20:05:14 »

Оценка такая:

n*sqrt(2*log2n)*2^sqrt(2*log2n)

Это лучше, чем n(1+eps), но хуже, чем n*log(n)M
(при любых eps>0, M<infinity)

А sum(i*log(i)) - это больше, чем n2. Не играет :(

               

               
Автор: Арвинд›
« : 27/12/2005, 18:44:44 »

Да, больше вроде некому.


Вопрос по предложенному алгоритму (я так и не разглядел его в деталях): оценка-то какая в итоге?
Она лучше или хуже, чем сумма (по i от 1 до n)  i*log i ?
Потому что мне (очень смутно) кажется, что с оценкой в виде такой суммы алгоритм можно придумать.
Плюс еще линейная добавка, конечно.

               

               
Автор: Mrrl›
« : 24/12/2005, 23:14:07 »

Может быть, и там. Но по-моему, в численных методах дальше быстрого преобразования Фурье не идут. По той же причине - непрактично. Быстрое умножение матриц и полиномов, быстрая и сверхбыстрая длинная арифметика - компьютерная алгебра этим занимается наверняка, а кто еще?

               

               
Автор: Арвинд›
« : 24/12/2005, 22:58:56 »

Нет, думаю, что не рассматриваются. По крайней мере нам Васильев в "методах оптимизации" этого не рассказывал точно, а экономисты наверняка меньше материала проходят. Думаю, если решение нашей задачи где-то и есть, то не в популярных учебниках, а в статьях - и скорее по тематике "численные методы".

               

               
Автор: Bindaree›
« : 24/12/2005, 22:55:36 »

*нервно*

ничего не знаю про программу :)

               

               
Автор: Mrrl›
« : 24/12/2005, 22:44:37 »

Злостный оффтопик
Посмотрел я программу этого курса (МОР). Очень интересно. Но неужели там действительно рассматриваются эффективные (быстрее, чем за N^2) алгоритмы работы с матрицами? Задача ведь совершенно не практическая - какой смысл обрабатывать матрицу быстрее, чем ее можно построить?

               

               
Автор: Bindaree›
« : 22/12/2005, 23:16:05 »

Господа,

я вот это все не читала подробно, но у меня тот же вопрос, что и у Арвинда - есть МОР. Есть Кун с Такером. Есть определители и все прочие прелести.

Я собираюсь эту тему шлепнуть. Не вижу я в ней формата ИР. Можно? Конечно, не сейчас. Но потом,когда она вам всем надоест :)


С уважением,

Шаси

1. Вопрос решен. Можно писать дальше. Тема стерта в любом случае не будет, в худшем (маловероятном) случае - перенесена.
2. А что такое МОР?
Арвинд.

Эй, я не останавливала тему :) Я просто плотоядно на нее косилась  ;D Уже больше не кошусь.Вообще в ее сторону не смотрю.  ;)

МОР - метод оптимальных решений  ;) раздел математики, посвященный как раз этой проблеме :) в частности, поиску эффективных решений для матриц и оптимизиционных задач :)

С уважением,

Шаси.

               

               
Автор: Mrrl›
« : 19/12/2005, 22:46:23 »

Так я же написал: если существует хотя бы одна седловая точка со значением a, то точка (iv,jv), выданная функцией CheckVal, гарантированно является одной из них. Но если мы не уверены в существовании, нам надо потратить еще m+n операций на проверку. Если окажется, что (iv,jv) - не седловая точка, значит, их вообще нет.

               

               
Автор: Меанор›
« : 19/12/2005, 22:25:10 »

Ну хорошо, а что нам даст поиск предполагаемого значения в седловой точке, если мы даже не будем уверены в том, что такая точка на матрице существует? Допустим, мы поличили: если на матрице есть седловая точка, то значение в ней A. Как нам её найти? Ведь, не любая точка со значением A является седловой.

               

               
Автор: Mrrl›
« : 19/12/2005, 21:51:15 »

1. "То есть, допустим, две оказались в текущем квадрате седловыми?"
  Как мы знаем, если две точки оказались седловыми, то значения в них одинаковы. Поэтому я предлагаю на каждом этапе искать не саму седловую точку, а только ее значение. На каждом шаге алгоритма у нас будут три кандидата на значения седловых точек (те, что вернулись из трех под-подматриц), и нам нужно проверить, какое из них может оказаться значением седловой точки для нашей подматрицы. Для этого можно воспользоваться следующим алгоритмом (сравнивающим значение седловой точки, если она есть, с поданным значением a):


int CheckVal(double [,]M,int m,int n,double a,out int iv,out int jv){
  iv=jv=0;
  int i1=0,j1=0;
  while(i1<m && j1<n){
    if(M[i1,j1]>a) j1++; else i1++;
  }
  if(i1==m) return 1;   // a>val
  int i2=0,j2=0;
  while(i2<m && j2<n){
    if(M[i2,j2]>=a) j2++; else i2++;
  }
  if(j2==n) return -1;   // a<val
  iv=i1; jv=j2;  // some saddle point
  return 0;
}


Алгоритм выдает -1,0 или 1, если a меньше, равно или больше значения седловой точки соответственно. Если выдано 0, то в параметрах iv, jv выдаются координаты потенциальной седловой точки (если хотя бы одна седловая точка со значением a есть, то гарантируется, что (iv,jv) - одна из них).

2. Действительно, можно ничего не проверять. Если в подматрице все диагональные элементы одинаковы, то их значение - единственный кандидат на значение седловой точки. Его и вернем.

3. "Обычный метод" - деление пополам или что-то еще?
Пусть f(n) - число операций, необходимое для поиска седловой точки. Пусть мы умеем искать медиану (и более широко - k-е по порядку значение из массива) + сортировать массив на "большие - меньшие" за C*n операций.
В случае деления пополам получаем:
f(n)=3*f(n/2)+n*(C+4)
(здесь 4*n - наихудшее время работы функции CheckVal).
Очевидно, что f(n)=D*n^(ln(3)/ln(2)), где D - некоторая константа.

Пусть рекурсия неравномерна. Для нее
f(n)=f(n-n1)+2*f(n1)+n*(2*C+4)
2*C понадобилось, поскольку диагональные элементы делятся на части дважды. Можно проверить, что если
n1=n/2^(sqrt(2*log(n)-1/2), то f(n)<D*n*sqrt(2*log(n))*2^sqrt(2*log(n))
(но это примерно страница выкладок). А это функция растет медленнее любой степенной (c показателем, большим 1).

В общем, дело в формуле f(n)=f(n-n1)+2*f(n1)+n*(2*C+4), точнее, в коэффициенте 2 перед f(n1). Поскольку f(n) выпукла вниз, для минимизации этого выражения требуется, чтобы выполнялось условие n1<n-n1. Точнее, f'(n-n1)=2*f'(n), а из-за медленного роста f(n)/n получаем, что n1 гораздо меньше n-n1.






               

               
Автор: Меанор›
« : 19/12/2005, 21:23:02 »

И в-третьих, объясните, что ваша неравноразмерная рекурсия с n1 даёт по сравнению с обычным, равноразмерным методом? Почему она будет работать быстрее? Пояните, пожалуйста, расчёты.

               

               
Автор: Меанор›
« : 19/12/2005, 21:17:04 »


Цитата из: Mrrl on 19-12-2005, 20:11:54
Достаточно проверить, есть ли в этой подматрице такая седловая точка.


Я пока не видел описания алгоритма для этого, работающего быстрее, чем за M*N.

               

               
Автор: Меанор›
« : 19/12/2005, 21:15:12 »

Не понял. Причем здесь равенство значений? Одна точка - седловая в некоторой подматрице. Вторая - тоже седловая. Пусть они в одном ряду находятся. (Иначе, будет уже четыре седовых.) Но одна из них может быть седловой во всей матрице, а вторая может не быть. Естественно могут быть и обе или ни одна из них. Как, простите, мы можем из рекурсии вернуть только одну (не более чем одну) подозрительную на "седловость" точку?