Алоха, науканы.
А поясните по хардкору отличие метода Монте-Карло от детерминированного М-К (deterministic Monte Carlo). А то гугл меня не спасает совсем.

GD Star Rating
a WordPress rating system

23 Responses to Алоха, науканы.

  1. Odaekb:

    Насколько я понял, вот тут хорошо описано:
    http://xkcd.com/221/

  2. Abaein:

    Тогда чем он отличается от QMC, там ведь тоже псевдо случайный числа используют?

  3. Odaekb:

    в моих скромных познаниях, QМС требует неких особых свойств последовательности.
    А детерминированный -это если сделать randomize(0) — просто всегда одна и та же последовательность, без требований сверх того.

    Могу быть неправ, самым краем в свое время касался.

  4. Ip2green:

    Первый раз слышу про deterministic Monte Carlo. Поделись ссылкой?

  5. Abaein:

    Вот сам удивился, инфы по MC/QMC в сети море, а про это нет.
    Тут в самом начале.

  6. Ip2green:

    ОК, я вроде разобрался.

    Смотри, обычный МС дает тебе приближённое значение интеграла. При это каждый раз разное. Т.е. ты можешь посчитать с помощью МС один и тот же интеграл десять раз, и у тебя будет десять похожих, но разных ответов.

    Есть такие приложения, где нужно посчитать один и тот же интеграл 10 раз и получить один и тот же ответ. Видимо, зд-графика — одни из них. Для таких случаев придумали DМС. Это тот же самый МС, только вместо случайных (или превдослучаных, если быть точнее) числе мы берем наперед-заданную последовательность. В результате, если мы возьмем один и тот же интеграл 10 раз, мы получим один и тот же ответ, с одним и тем же отклонением от правильного ответа.

    Это объясняет информационный вакуум. Во первых, приложение достаточно редкое. Если у нас есть возможность запустить МС 10 раз, мы просто запускаем его 10 раз и усредняем ответ. Так и ошибка меньше будет. Во вторых, для такого алгоритма становится сложнее доказать всякие красивые математические теоремы о сходимости.

  7. Abaein:

    Вот мне бы про формирование последовательности узнать нужно.

  8. Ip2green:

    C какой целью интересуетеcь?

    Я об это штуке до сегодняшнего утра не знал, но предположу что последовательности формируются точно так же как и для обычного МС. Ну или как для обычного QMC. Единственная разница — ты эти последовательности генерируешь заранее и сохраняешь в памяти. Принцип генерации последовательностей не меняется.

  9. Abaein:

    Есть подозрение что можно сделать ускоритель рендеров, перенеся их численные методы в железо. Вот пытаюсь разобраться в матане, чтобы оценить возможности.

  10. Odaekb:

    В старом добром паскале была функция инициализации ГСЧ randomize(0)
    после randomize(0) всегда шла одна и та же последовательность, удобно для отладки..

  11. Ip2green:

    В принципе, можно привязать зерно рандомизации к параметрам интеграла (т.е. чтобы для разных интегралов получалась разная последовательность, но для одного интеграла — одна и та же)

  12. Ip2green:

    : Хотя если мы хотим железного ускорения, нам все-же лучше сгенерировать последовательность заранее и зашить ее в микросхему.

  13. Ip2green:

    Думаю, нужно почитать про генерацию последовательностей в QMC. А потом сделать функцию как в комиксе сверху.

  14. Abaein:

    Ну если так, то я вообще в шоколаде.

  15. CopRU:

    неправ. QMC — обычный Монте-Карло, лишь в применении к особым алгоритмам расчета квантовых задач. Никаких особых условий к гсч (типа, чтобы было истинное случайное число и т.п.) нет. Говорю как человек написавший диссер в QMC.

  16. Peein:

    Абстрактное замечание по теме — посмотри на proposition 3.2 здесь например.

  17. Peein:

    proposition 3.5 в главе 3.2 я хотел сказать.

  18. Abaein:

    блджад, тогда чем они различаются?

  19. Abaein:

    товарищь, для меня это сложновато. Можешь пояснить хоть чуть-чуть?

  20. Peein:

    Там написано, что если твой монте-карло метод удовлетворяет некоторым условиям, то найдется последовательность, используя которую вместо случайной можно сделать метод детерминированным, не ухудшив качество его работы.

    В целом есть целая область под названием Derandomization, вопрос которой — какие классы задач из тех, что требуют для эффективного решения использование случайности, можно решить и без оной.

  21. Abaein:

    Там описывают как получать такие последовательности?

  22. Abaein:

    В смысле в той статье.

  23. Peein:

    Нет, это неконструктивная теорема, как почти все в этой области. Я ж сказал, абстрактное замечание.

Добавить комментарий