[Назад]
Ответ в нить
Animapcha image [@] [?]
Тема   ( ответ в 152038)
Сообщение flower
Файл 
Пароль  (для удаления файлов и сообщений)
Параметры   
  • Прежде чем постить, ознакомьтесь с правилами.
  • Поддерживаются файлы типов GIF, JPG, MP4, OGV, PNG, WEBM размером до 5000 кБ.
  • Ныне 3137 unique user posts. Посмотреть каталог
  • Максимальное количество бампов нити: 375
158343002960.png-(3.11KB, 271×237, 33cf6535.png)
152038
No. 152038    
Пассажиры, а давайте обсуждать математику. Элементарную и неэлементарую, школьную и вузовскую; прикладную и чистую. Словом, всю-всю-всю.
Развернуть все изображения
No. 152039    
Существует ли эффективный алгоритм параллельной вставки в сбалансированное каким-нибудь способом сортированное (слева все элементы больше, справа меньше) бинарное дерево?

Теоретически, если два элемента вставляются в далеко отстоящие друг от друга ветки, мы можем одновременно вставлять и в одну, и в другую в большом количестве случаев, в которых перебалансировка не затрагивает общие вершины на пути. С одной стороны, когда мы ищем место для вставки нового элемента мы можем помечать посещаемые ноды как используемые, и если мы встретили используемую ноду, то вставлять элемент уже после того, как используемые ноды на соответствующем пути к месту вставки освободятся. А если на пути используемых кем-то ещё нод нет, то делаем вставку. Но я пока слабо представляю реализацию этого.
No. 152040    
>>152039
Что за глупый вопрос, это же банально, просто берё...
>сбалансированное каким-нибудь способом
Ааа, вот в чём весь цимес.
No. 152041    
>>152039
По поводу сбалансированного бинарного дерева. Ставится ли задача записать его элементы в массив и составить функцию декодирующую индексы элементов из массива обратно в бинарное дерево.
No. 152043    
>>152041
> Ставится ли задача записать его элементы в массив
Такой задачи не стоит: хранить в массиве дерево не обязательно. Ведь проитерировать элементы и записать их в массив можно всегда.
> составить функцию декодирующую индексы элементов из массива обратно в бинарное дерево
Такой задачи не стоит. Пока стоит задача хоть как-то сбалансированное сортированное бинарное дерево каких-то элементов, которые можно сравнивать, реализовать, но с параллельной вставкой. А ещё в нём должно быть можно удалять элементы, пока не обязательно параллельно.
No. 152069    
>>152043
> Такой задачи не стоит. Пока стоит задача хоть как-то сбалансированное сортированное бинарное дерево каких-то элементов, которые можно сравнивать, реализовать, но с параллельной вставкой.
Что-то очень похожее на СУБД-шные индексы.
No. 152072    
Достали уже ваши математические проповеди.
No. 152121    
>>152072
Где ты проповеди видишь, умнице?
No. 152122    
>>152069
Да. Соответственно оно скорее всего есть. (Не факт, что эти БД именно бинарные деревья используют.)
No. 152144    
>>152121
Везде. Треды, посвящённые скучнейшей из наук, есть чуть ли не на каждой борде.
No. 152145    
>>152144
Математика самая крутая наука. В ней можешь делать вообще что хочешь. Выдумывать свои миры. Вот где на100ящая свобода.
No. 152146    
>>152145
Но это особые миры. Таких, как на картинках, рассуждая не получишь же. Да и то это будут иллюзии, пока не найдётся некий метод «овеществления» этого всего, навроде ЭВМ.

>>152144
Тред про математику тут есть. А проповедей, по крайней мере до >>152145, не видно. Вам правда настолько противно, как если бы тут гуро или тому подобное запостили?
No. 152163    
>>152144
>треды есть чуть ли не на каждой борде
Кто бы мог подумать, что в окружении бородатых админов с физматподготовкой рассуждают о математике.
No. 152283    
158444209777.jpg-(71.97KB, 600×800, 15666428787970.jpg)
152283
Предлагаю задачку.
Какое наименьшее число гирь необходимо для того, чтобы иметь возможность взвесить любое число граммов от 1 до 100 на чашечных весах, если гири можно класть на обе чашки весов?
No. 152284    
>>152283
Пять, по степеням тройки от 0 до 4.
No. 152315    
158460975020.jpg-(103.44KB, 624×832, 1539990896568.jpg)
152315
>>152284
Теперь ты предлагай задачку.
No. 152316    
158461251620.png-(32.69KB, 190×200)
152316
>>152315
No. 152321    
158461751233.png-(142.75KB, 400×470, Konqi.png)
152321
>>152316
Верно ли, что сопротивление между этими точками такое же, если бы мы прошли по диагонали и направо?
Сопротивление между точками квадрата стремится к нулю, так как напряжение одинаковое, а токи разветвляются.
Сопротивление между точками на одном проводе равно одному ому.
1.
No. 152322    
>>152321
Правильный ответ: 4/pi−½
No. 152323    
158461885659.jpg-(213.02KB, 883×680, Cinnabar_(Houseki_no_Kuni)_full_1837770.jpg)
152323
>>152316
Даже думать нечего: 1/Inf => |Inf := 1/dr | => 1/1/dr => dr
No. 152324    
>>152323
Что такое dr?
No. 152328    
>>152315
Положим существует три множества A, B, C, которые могут содержать одинаковые элементы (их пересечения непустые). Из каждого множества необходимо случайным образом выбирать подмножества A', B', C' соответственно, каждое из n элементов, так, чтобы они не пересекались (их пересечения пустые).
Так для A = {a, b, c, d, e, f}, B = {a, c, d, q}, C = {e, f} и n = 2, подмножества A' = {a, c}, B' = {d, q} и C' = {e, f} будет верным выбором, а A' = {a, e}, B' = {d, q} и C' = {e, f} — нет.
Придумать эффективный алгоритм.

>>152316
То чувство, когда помнишь физику только на уровне 7-ого класса (простая кинематика и динамика). Стыдно.
No. 152331    
158462667345.jpg-(10.34KB, 180×146)
152331
>>152323
Мог бы просто написать, что ответ - ⑨, раз не знаешь как решается.
No. 152333    
>>152328
За сколько находится мощность множества, за О(1)?
No. 152334    
>>152333
Допустим.
No. 152335    
>>152333 >>152334 >>152328
В принципе, задачу можно перефразировать примерно так.
Даны три числа a, b, c.
Найти частное решение (x, y, z) системы x & ~a == 0 && y & ~b == 0 && z & ~c == 0 && x & y == 0 && y & z == 0 && x & z == 0.

Если представлять множества таким образом, то можно считать побитовые сдвиги и прочие логические операции, а также инкремент и декремент O(1). Тогда считать количество элементов во множестве можно за O(n), где n — его мощность; пересечения, объеденения, исключения и прочее можно делать за O(1).
No. 152339    
>>152335
Пропущено условие про количество положительных бит. Оно должно быть равно n.

В принципе x & y == 0 && y & z == 0 && x & z == 0 равносильно xy | yz | xz = 0 (здесь и далее xy = x & y). Что в свою очередь равносильно xy ^ xz ^ yz = 0.
x & ~a == 0 && y & ~b == 0 && z & ~c == 0 равносильно (полагая, что приоритет ~ наивысший) ~ax | ~by | ~cz = 0. ~ax | ~by | ~cz = ~ax ^ ~by ^ ~a~bxy ^ ~cz ^ ~a~cxz ^ ~b~cyz ^ ~a~b~cxyz.
x & ~a == 0 && y & ~b == 0 && z & ~c == 0 равносильно ~a~b~cxyz ^ ~a~bxy ^ ~a~cxz ^ ~b~cyz ^ ~ax ^ ~by ^ ~cz = 0.
Тогда система сворачивается в уравнение (~a~b~cxyz ^ ~a~bxy ^ ~a~cxz ^ ~b~cyz ^ ~ax ^ ~by ^ ~cz) | (xy ^ xz ^ yz) = 0.
Продолжаем сводить всё в одно уравнение в кольце <Z, ^, &>:
~a~b~cxyz ^ ~a~bxy ^ ~a~cxz ^ ~b~cyz ^ ~ax ^ ~by ^ ~cz ^ xy ^ xz ^ yz ^
(~a~b~cxyz ^ ~a~bxy ^ ~a~cxz ^ ~b~cyz ^ ~ax ^ ~by ^ ~cz) & xy ^
(~a~b~cxyz ^ ~a~bxy ^ ~a~cxz ^ ~b~cyz ^ ~ax ^ ~by ^ ~cz) & xz ^
(~a~b~cxyz ^ ~a~bxy ^ ~a~cxz ^ ~b~cyz ^ ~ax ^ ~by ^ ~cz) & yz = 0.
Если эту штуку раскрыть, то мы получаем в левой части жуткий полином третей степени от трёх переменных в кольце <Z, ^, &>. В принципе, это можно представить в виде системы нелинейных уравнений в Z₂, а это уже поле. Даёт ли нам это что-нибудь?
No. 152340    
158464230253.png-(91.04KB, 720×1242, Без названия4_20200319212156.png)
152340
>>152316
Очень интересный момент. Добавление перемычечного резистора уменьшает общее сопротивление.

А вообще, как решать эту задачу? Искать потенциалы в узлах сетки?
No. 152341    
>>152146
Это всё выглядит как понты. "Смотрите, мы обсуждаем сложные вещи, которые нам не нужны, зато мы типа умные!"
No. 152344    
>>152341
Не расстраивай меня. Что плохого в обсуждении красоты, магии, духов и мистического?
Сколько понтов в обсуждении музыки?
Удалить сообщение []
Пароль  
[Mod]