?

Log in

No account? Create an account

О больших числах

« previous entry | next entry »
дек. 17, 2008 | 08:35 pm
mood: crazycrazy

Только что прикинул, что для выполнения с виду "простой" операции (перебор всех возможных групп: 5 групп по 11 элементов, всего 55 элементов, и вычисление для каждой комбинации некой функции, речь идет всего лишь о методе AMOVA:) моему компу потребуется время, на 45 порядков превышающее время существования Вселенной O_O Или может я ошибаюсь...

И зачем я вчера ночью оставлял комп делать 10000000 пермутаций?
Метки:

Ссылка | Оставить комментарий |

Comments {8}

jalgard

(без темы)

from: jalgard
date: дек. 17, 2008 07:14 pm (UTC)
Ссылка

Я не понял, как ты оценил время выполнения алгоритма для 1 комбинации из 55 элементов... Или ты посчитал, сколько он успел за ночь и прикинул сколько таких бессонных ночей ему еще надо?)))
У нас где-то в мгу есть кластер)))

Ответить | Ветвь дискуссии

Старый Молекулярщик

(без темы)

from: molekularshik
date: дек. 17, 2008 07:37 pm (UTC)
Ссылка

Я посчитал, за сколько минут он делает миллион пермутаций (за 15) и вроде как вычислил необходимое число пермутаций: 55!/(5!*11^5) Ты не скажешь, верна ли сия формула?

А если она верна, все кластеры мира не помогут)

Ответить | Уровень выше | Ветвь дискуссии

jalgard

(без темы)

from: jalgard
date: дек. 17, 2008 08:43 pm (UTC)
Ссылка

Сначала надо понять, в какой ситуации находится задача: выбор с возвратом/без и порядок имеет/не имеет значения. Потом просто выбрать нужную формулу комбинаторики.

Подобные задачи чаще всего имеют формулу типа "размещения" A(из n по m) = n!/(n-m)!

Я так и не догнал, почему у тебя такая формула. 5 групп это что? 11 элементов - это как? то есть что тут число позиций и из чего можно выбирать. Например, ясно, что в десятичной системе мы выбираем цифру от 0 до 9, а позиций столько, сколько "значное" наше число. Если говорим о бросании монетки, то для позиции (результата каждого броска) берем 2 варианта (орел или решка), если для ДНК то 4 варианта (допустим, A/G/T/C). Тут я не понял, из чего допустимо набрать 55 элементов.

Ответить | Уровень выше | Ветвь дискуссии

(без темы)

from: anonymous
date: дек. 19, 2008 12:46 pm (UTC)
Ссылка

Учитывая нашу вчерашнюю беседу, я бы предложил следующее решение.
Используем C[n\k]=n!/(k!*(n-k)!);

Рассуждение:
пусть надо образовать из 55 элементов 5 групп по 11 элементов.
это делается последовательно:
1. 1 группа из 11 элементов: С1[n/k] = 55!/(11!(55-11)!)
2. 2 группа из 11 элементов: С2-//- = 44!/(11!(44-11)!)
3. -//- С3 = 33!/(11!(33-11)!)
4. -//- С4 = 22!/(11!(22-11)!)
5. И оставшиеся 11 элементов - 5 группа. Ее можно составить единственным способов (число способов=1).

Итог = С1*С2*С3*С4*1...
Думаю, примерно так...

Ответить | Уровень выше | Ветвь дискуссии

Старый Молекулярщик

(без темы)

from: molekularshik
date: дек. 19, 2008 01:48 pm (UTC)
Ссылка

Спасибо)

Ответить | Уровень выше | Ветвь дискуссии

Старый Молекулярщик

(без темы)

from: molekularshik
date: дек. 19, 2008 01:56 pm (UTC)
Ссылка

Все равно получается порядка 10^35 комбинаций, следовательно мой комп будет считать 10^14 возрастов Вселенной. Ну кластер посчитает, если верить твоим словам о его быстродействии, за один возраст)))

Ответить | Уровень выше | Ветвь дискуссии

Ирвин Непоседа

(без темы)

from: earwin
date: дек. 18, 2008 11:41 pm (UTC)
Ссылка

Увлёкся каббаллистикой?

Ответить | Ветвь дискуссии

Старый Молекулярщик

(без темы)

from: molekularshik
date: дек. 19, 2008 01:46 pm (UTC)
Ссылка

Ага)))

Ответить | Уровень выше | Ветвь дискуссии