2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Бинарный поиск наверх
Сообщение05.01.2011, 09:26 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Вот есть у нас вычислимое отношение $R(n,x)$. И доказано (безо всякого намёка на поиск, чисто от противного), что $\forall x \exists n R(n,x)$. Как его лучше искать? Допустим, есть дополнительный вычислимый предикат $S(n,x)$, истинный тогда и только тогда, когда существует $m \leqslant n$, такой что $R(m,x)$. Всё равно мало помогает...

 Профиль  
                  
 
 Re: Бинарный поиск наверх
Сообщение05.01.2011, 13:47 


04/11/10

141
Профессор Снэйп

Тоже решили Зиммерманом "побаловаться"?.

 Профиль  
                  
 
 Re: Бинарный поиск наверх
Сообщение05.01.2011, 16:55 
Заслуженный участник


26/07/09
1559
Алматы
2Профессор Снэйп
Наверное, можно так. Фиксируем $x$. В цикле выбираем $n$ случайно и проверяем $S(n,\ x)$. Как только условие выполнилось, присваиваем $x\gets n$ и повторяем все сначала, прямо с цикла. Если $R$ транзитивно, то мы (вроде-бы) будем приближаться к искомому $n$. Последовательность значений, которые присваивались к $x$ должна сходиться (или нет :) ).

Бред, не иначе... :)

 Профиль  
                  
 
 Re: Бинарный поиск наверх
Сообщение05.01.2011, 17:17 
Заслуженный участник


04/05/09
4584
Профессор Снэйп в сообщении #395483 писал(а):
Вот есть у нас вычислимое отношение $R(n,x)$. И доказано (безо всякого намёка на поиск, чисто от противного), что $\forall x \exists n R(n,x)$. Как его лучше искать? Допустим, есть дополнительный вычислимый предикат $S(n,x)$, истинный тогда и только тогда, когда существует $m \leqslant n$, такой что $R(m,x)$. Всё равно мало помогает...
Сначала умножаем $n$ на два, пока не получим $S(n,x)$, а потом бинарным поиском вниз.

 Профиль  
                  
 
 Re: Бинарный поиск наверх
Сообщение06.01.2011, 00:55 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
venco в сообщении #395694 писал(а):
Сначала умножаем $n$ на два, пока не получим $S(n,x)$, а потом бинарным поиском вниз.

А почему именно на два?

 Профиль  
                  
 
 Re: Бинарный поиск наверх
Сообщение06.01.2011, 02:27 
Заслуженный участник


04/05/09
4584
Оптимум где-то около $2^{\sqrt{2\log_2 n}}$, но разница небольшая. Наверно лучше умножать на большее число, например 10.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group