Каковы ресурсы мозга (к Руссо)

 
1 2 3 4 5 6
US russo #08.02.2011 03:25  @Сергей-4030#08.02.2011 03:23
+
-
edit
 
Сергей-4030> Да, просто по возрастанию

Понятно.

N может быть бесконечно большой величиной? Элементы выбираются случайно?
 3.6.33.6.3
US Сергей-4030 #08.02.2011 03:29  @russo#08.02.2011 03:25
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Сергей-4030>> Да, просто по возрастанию
russo> Понятно.
russo> N может быть бесконечно большой величиной? Элементы выбираются случайно?

N может быть "любой конечной величиной". В множестве натуральных чисел нет элемента "бесконечное число". :) Но это неважно, можно для простоты зафиксировать N=10, как долго будет выполнятся на твоем рабочем компьютере, как думаешь?
 8.0.552.2378.0.552.237
US russo #08.02.2011 03:34  @Сергей-4030#08.02.2011 03:29
+
-
edit
 
Сергей-4030> N может быть "любой конечной величиной".

Впрочем понятно что на деле мы ограничены размером ячейки памяти.

Сергей-4030> как долго будет выполнятся на твоем рабочем компьютере, как думаешь?

По идее практически мгновенно. Я бы сделал что-то на основании сравнения "левого конца" бинарного регистра памяти.

1) Смотрим у кого единичка левее всегов регистре.
1.5) Если таких чисел (т.е. с самой левой единичкой в одном и том же месте) больше одного сравниваем следующий "правый" бит и т.д.
2) Записываем самое большое число куда надо
3) Убираем его из чисел которые нужно сортировать
4) Проверяем есть ли еще несортированные числа. если есть goto п.1, если нету п.5
5) Так как с задача надо сортировать по возрастанию то полученный список инвертируем. end

Сильно чушь?
 3.6.33.6.3
Это сообщение редактировалось 08.02.2011 в 03:41
US Сергей-4030 #08.02.2011 03:40  @russo#08.02.2011 03:34
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Сергей-4030>> N может быть "любой конечной величиной".
russo> Впрочем понятно что на деле мы ограничены размером ячейки памяти.
Сергей-4030>> как долго будет выполнятся на твоем рабочем компьютере, как думаешь?
russo> По идее практически мгновенно. Я бы сделал что-то на основании сравнения "левого конца" бинарного регистра памяти. Впрочем я не программист, может и чушь :)

Ты не понял. Я не про то, как отсортировать массив. Твой компьютер тебе засортирует не то что десять элементов, а что хошь. Я про то, как сортировать. Ты меняешь случайным порядком пару цифр ( не сравниваешь, просто меняешь). Если теперь массив отсортирован - конец. Если нет - снова меняешь. Ну вот если бы ты сам так делал, представляешь. У тебя шесть цифр. Ты метаешь кубик, выпала двойка. Метаешь снова, выпала шестерка. Меняешь местами второй и шестой элемент в ряду. Смотришь - уже все по порядку? Если нет, метаешь кубики снова и снова и снова.
 
US russo #08.02.2011 03:43  @Сергей-4030#08.02.2011 03:40
+
-
edit
 
Сергей-4030> Ты меняешь случайным порядком пару цифр ( не сравниваешь, просто меняешь)

Гм.

В смысле у нас есть случайный массив. В нем случайным образом каждый шаг меняются местами две цифры. Задача оценить наиболее вероятное число шагов до нужной нам сортировки массива. Так что ли? :-/
 3.6.33.6.3
US Сергей-4030 #08.02.2011 03:44  @russo#08.02.2011 03:43
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
russo> В смысле у нас есть случайный массив. В нем случайным образом каждый шаг меняются местами две цифры. Задача оценить наиболее вероятное число шагов до нужной нам сортировки массива. Так что ли? :-/

Да. Собственно, даже не число шагов, а за сколько твой компьютер справится. Хочется оценить впечатления не по отдельным числам, а по произведению. Только в Вики не глядеть, испортишь весь эксперимент! ;)
 8.0.552.2378.0.552.237
US Сергей-4030 #08.02.2011 03:48  @Сергей-4030#08.02.2011 03:44
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Для примера, исходный массив:

23 5 99 12 8 32
меняем 2 и 6
23 32 99 12 8 5
меняем 2 и 6
23 5 99 12 8 32
меняем 1 и 1
23 5 99 12 8 32
меняем 1 и 4
12 5 99 23 8 34
меняем 2 и 5
12 8 99 23 5 34

и т.д. и т.п.
 8.0.552.2378.0.552.237
+
-1
-
edit
 

Mishka

модератор
★★☆
russo> Во-первых заряд иона это само по себе бесконечное значение (представь измерение с прибором с бесконечной точностью)

Ы-ы-ы! Ну ты то куда? :) Во-первых, слово бесконечное плохое. Значение конечное. Во-вторых, точность (а ты имел количество знаков после запятых) точно. Как корень из двух. В-третьих, оно в природе не непрерывно в силу дискретности зарядов. По современным понятиям.

russo> Во-вторых важен не заряд, а потенциал. Т.е. важно электрическое поле. Оно же зависит от положения иона, а пространство, повторюсь, бесконечно делимая величина.
Нет, и оно не будет бесконечно делимой. :)
 3.6.133.6.13
US russo #08.02.2011 04:02  @Сергей-4030#08.02.2011 03:44
+
-
edit
 
Сергей-4030> в Вики не глядеть, испортишь весь эксперимент! ;)

Тэкс. nPr(10,10) == 3,628,800.

Ну пусть несколько секунд если N == 10 :rolleyes:
 3.6.33.6.3
Mishka> Значение конечное

Почему оно конечно :-/ Т.е. скажем заряд электрона будет 10-19 * 1.60...50000000 — т.е. после очередной цифры сплошные нули до бесконечности?

Mishka> точность точно

Я ж не спорю что точность измерения бесконечной быть не может. Но это не отменяет того что истинное значение заряда — бесконечная цифра.

Mishka> оно в природе не непрерывно в силу дискретности зарядов

Кол-во заряженных единиц дискретно. Но я же не о них.

russo>> пространство, повторюсь, бесконечно делимая величина.
Mishka> Нет, и оно не будет бесконечно делимой. :)

Кто сказал :D Есть конечно loop quantum theory и иже с ними, но все же мне кажется как минимум значительная часть физиков полагает пространство бесконечно делимым.
 3.6.33.6.3

Mishka

модератор
★★☆
russo> Ну пусть несколько секунд если N == 10 :rolleyes:

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

Для двух легко. Либо 0 шагов, либо 1.
 3.6.133.6.13
US Сергей-4030 #08.02.2011 04:10  @russo#08.02.2011 04:02
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Сергей-4030>> в Вики не глядеть, испортишь весь эксперимент! ;)
russo> Тэкс. nPr(10,10) == 3,628,800.
russo> Ну пусть несколько секунд если N == 10 :rolleyes:

Ну вот, посчитал. Так нечестно. Но таки правильно, да. Многие люди после того, как немного попытаются посортировать таким образом, думают, что это будет очень долго. Весь аргумент мне испортил. :)
 8.0.552.2378.0.552.237
US Mishka #08.02.2011 04:14  @Сергей-4030#08.02.2011 04:10
+
-
edit
 

Mishka

модератор
★★☆
Сергей-4030> Ну вот, посчитал. Так нечестно. Но таки правильно, да. Многие люди после того, как немного попытаются посортировать таким образом, думают, что это будет очень долго. Весь аргумент мне испортил. :)

Серёг, будь аккуратен. Это средняя производительность. :) Да и то на 10 надо умножить, т.к. двумя в среднем надо от 5 до 10 перестановок сделать, чтобы из произвольной комбинации попасть. А худший случай — никогда.
 3.6.133.6.13
Mishka> Для двух легко. Либо 0 шагов, либо 1.

Да это-то понятно понятно. Однако выше двух уже меньше понятно. Я решил что каждый шаг для массива из десяти разных элементов вероятность правильной сборки будет 1/3.5кк, но все же тут не совсем — каждый раз у нас не пересортируется весь массив, а только два случайных числа.

В общем не знаю :( Хоть в вики лезь, или за книгами :)
 3.6.33.6.3
US russo #08.02.2011 04:16  @Сергей-4030#08.02.2011 04:10
+
-
edit
 
Сергей-4030> Ну вот, посчитал.

В свою защиту — формулу nPr() я помню с универа ишшо :) Числа умножал делил на калькуляторе правда, не труЪ столбиком
 3.6.33.6.3
MD Wyvern-2 #08.02.2011 04:19  @Сергей-4030#08.02.2011 00:45
+
-
edit
 

Wyvern-2

координатор
★★★☆
Сергей-4030>>> Все "аналоговости" - хорошо замаскированные двоичности. ;)
ahs>> На уровне отдельных молекул - незамутненная квантовая механика без признаков двоичности :)
ahs>> Потенциал действия двоичен, потенциал покоя - нет :Р
Сергей-4030> Пачиму ж тогда у вас пары нуклеотидов в качестве битиков, а не какая-нибудь аналоговость замудреная?

Каких таких нахрен "битиков"? Пары нуклеотидов твердо установлены раз и навсегда - а значит не несут никакой информации, бессмысленны. Единица информации в живом - триплет И никакой примитивной "двоичности"
Жизнь коротка, путь искусства долог, удобный случай мимолетен, опыт обманчив.... Ἱπποκράτης  3.6.133.6.13
US Сергей-4030 #08.02.2011 04:19  @Mishka#08.02.2011 04:14
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Mishka> Серёг, будь аккуратен. Это средняя производительность. :)

Миша, Руссо прав, это именно единицы секунд в среднем. Я проверял в т.ч. на практике. :)

Mishka>Да и то на 10 надо умножить, т.к. двумя в среднем надо от 5 до 10 перестановок сделать, чтобы из произвольной комбинации попасть.

Нет, почему? Произвольная комбинация может быть уже отсортированной, к примеру.

Mishka>А худший случай — никогда.

Конечно, но даже время в десять раз выше среднего (порядка минуты на нынешних компьютерах) практически невероятно, сотые доли процента, насколько я помню.
 8.0.552.2378.0.552.237
US Сергей-4030 #08.02.2011 04:20  @russo#08.02.2011 04:16
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Сергей-4030>> Ну вот, посчитал.
russo> В свою защиту — формулу nPr() я помню с универа ишшо :) Числа умножал делил на калькуляторе правда, не труЪ столбиком

Ну, в данном-то случае просто факториал. :)
 8.0.552.2378.0.552.237
+
-
edit
 
Wyvern-2> Каких таких нахрен "битиков"?

Ну, там конечно не (0,1), а (0,1,2,3).

Но не притворяйся что ты не понял что имелось в виду :-P

Wyvern-2> Единица информации в живом - триплет

Ага, а единица информации в компе — байт. Который состоит из "битиков" ;)
 3.6.33.6.3
US russo #08.02.2011 04:22  @Сергей-4030#08.02.2011 04:20
+
-
edit
 
Сергей-4030> Ну, в данном-то случае просто факториал. :)

Дык, а факториал не умножение чтоли? ;) На кулькуляторе я конечно вбил 10!, а не 1*2*3.. — я ж не мазохист. И деление там есть!!! на один :F
 3.6.33.6.3
+
-
edit
 

Wyvern-2

координатор
★★★☆
Wyvern-2>> Единица информации в живом - триплет
russo> Ага, а единица информации в компе — байт. Который состоит из "битиков" ;)

Почему же "байт"? Может быть "слово"? Помнится были процессоры с 27 битным словом и еще черте каким.
Но речь тут шла, как бы Миша не отмазывал :D , именно о двоичности - "сигнал есть"/"сигнала нет" Чего в функционировании нейронов не наблюдается.
Жизнь коротка, путь искусства долог, удобный случай мимолетен, опыт обманчив.... Ἱπποκράτης  3.6.133.6.13
+
-1
-
edit
 

Wyvern-2

координатор
★★★☆
Сергей-4030>> Все "аналоговости" - хорошо замаскированные двоичности. ;)
ahs> На уровне отдельных молекул - незамутненная квантовая механика без признаков двоичности :)
Может быть квантовость есть и на более высоком уровне, кстати:
Могут ли жизнь и сознание быть связанными с фундаментальной квантовой природой Вселенной? | Windows 7even - это наводка ;) Пенроуза вообще "затирают" , его не понимают ни физики, ни биологи :D Явный признак того, что идея стоящая - как и то, что тубулины были открыты после создания Пенроузом своей теории, причем хаяли ее поначалу именно по поводу, мол, отсутствия в нейронах какого либо субстрата ;)
Жизнь коротка, путь искусства долог, удобный случай мимолетен, опыт обманчив.... Ἱπποκράτης  3.6.133.6.13
US Сергей-4030 #08.02.2011 04:30  @Wyvern-2#08.02.2011 04:26
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
Wyvern-2> Но речь тут шла, как бы Миша не отмазывал :D , именно о двоичности - "сигнал есть"/"сигнала нет" Чего в функционировании нейронов не наблюдается.

Речь шла о дискретности.
 8.0.552.2378.0.552.237
US Mishka #08.02.2011 05:29  @Сергей-4030#08.02.2011 04:19
+
-
edit
 

Mishka

модератор
★★☆
Сергей-4030> Миша, Руссо прав, это именно единицы секунд в среднем. Я проверял в т.ч. на практике. :)

Это вероятностная оценка. Может быть и хуже. :) Даже вики даёт O(n*n!) average.

Сергей-4030> Нет, почему? Произвольная комбинация может быть уже отсортированной, к примеру.

Может, но может потребовать и 5. Для 10. Для N — N/2 или N/5 — не важно, поэтому O(N*N!). А Руссо дал просто O(N!)

Сергей-4030> Конечно, но даже время в десять раз выше среднего (порядка минуты на нынешних компьютерах) практически невероятно, сотые доли процента, насколько я помню.

Там надо повышать размерность до 10,000 хотя бы. Правда, с факториалом уже будет попа. А вот даже пузырьком будет всего 100,000,000*const где-то.
 3.6.133.6.13
+
-
edit
 

Mishka

модератор
★★☆
Wyvern-2> Почему же "байт"? Может быть "слово"? Помнится были процессоры с 27 битным словом и еще черте каким.

Потому что байт. :) Никто нигде не говорит, что байт это 8 бит. Это одно из допущений в современной архитектуре. А так у HP 16 бит долгое время было.

Wyvern-2> Но речь тут шла, как бы Миша не отмазывал :D , именно о двоичности - "сигнал есть"/"сигнала нет" Чего в функционировании нейронов не наблюдается.

Ник, тебе не хватает воображения. Двоичная система эквивалентна троичной, а та четверичной... и т.д. Доказыается у математиков на первом курсе в теории чисел. :P Система счисления у математиков равно удобству представления. Как и системы координат. Напомню, что системы координат (система ортов) может быть очень странной. Например, в пространстве простых полиномов ортами будут x^n, где n бегает от 0 и до бесконечности. :P

Поэтому речь о дискретности.
 3.6.133.6.13
1 2 3 4 5 6

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru