Обсуждение:Декартово дерево - История изменений

Kirelagin: /* Приоритет */ Новая тема

2014-01-28T17:05:28Z

‎Приоритет: Новая тема

Dgerasimov в 06:34, 16 мая 2012

2012-05-16T06:34:19Z

Dgerasimov в 12:19, 15 мая 2012

2012-05-15T12:19:40Z

Dgerasimov в 19:06, 3 мая 2012

2012-05-03T19:06:29Z

Орынбаев Хусаин в 13:02, 1 мая 2012

2012-05-01T13:02:54Z

Орынбаев Хусаин в 13:01, 1 мая 2012

2012-05-01T13:01:27Z

Орынбаев Хусаин в 12:58, 1 мая 2012

2012-05-01T12:58:15Z

Орынбаев Хусаин в 12:01, 1 мая 2012

2012-05-01T12:01:42Z

Dgerasimov в 09:48, 1 мая 2012

2012-05-01T09:48:43Z

Орынбаев Хусаин в 18:08, 28 апреля 2012

2012-04-28T18:08:38Z

← Предыдущая		Версия 17:05, 28 января 2014
Строка 51:		Строка 51:
	:: все еще не исправлено...--[[Участник:Dgerasimov\|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)		:: все еще не исправлено...--[[Участник:Dgerasimov\|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
	::: аргх. правильно говорить «декартова дерева». --[[Участник:Dgerasimov\|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)		::: аргх. правильно говорить «декартова дерева». --[[Участник:Dgerasimov\|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)
		+
		+	== Приоритет ==
		+
		+	Ребятушки, у вас полстатьи в корне максимальный проритет, полстатьи — минимальный. Давайте уж сойдемся на том, что приоритет, он на то и приоритет, чтобы первым шел тот, у кого он больше. [[Участник:Kirelagin\|Кирилл Елагин]] 21:05, 28 января 2014 (GST)

@@ Строка 28: / Строка 28: @@
 : {{tick | ticked=1}} нет источников --[[Участник:Rybak|Андрей Рыбак]] 12:36, 25 марта 2012 (GST)
-: {{tick}} доказательство:
+: {{tick | ticked=1}} доказательство:
-:: {{tick}}«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
+:: {{tick | ticked=1}}«являются незавимыми непрерывными случайными величинами с одинаковым вероятностным распределением» — непрерывные случайные величины? Гм, вроде этого не было в курсе дискретки, ну это еще интуитивно более-менее ясно. А вот что такое «одинаковое распределение»?
 ::: «с одного и того же распределения» — бред. возьмем для приортиетов нечестную монету (или что-то подобное), она может давать независимые случайные величины, но для приоритетов не подходит.
 :::: Все еще не исправлено --[[Участник:Dgerasimov|Дмитрий Герасимов]] 11:44, 26 апреля 2012 (GST)<nowiki>Вставьте сюда текст, который не нужно форматировать</nowiki>

@@ Строка 36: / Строка 36: @@
 ::::::: Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке доказательства -- [[Участник:Орынбаев Хусаин|Орынбаев Хусаин]] 15:58, 1 мая 2012 (GST)
 :::::::: Должны быть разными, в том числе. В общем, то, что тебе нужно называется равномерным распределением. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 23:06, 3 мая 2012 (GST)
 :: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
 :: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
@@ Строка 43: / Строка 44: @@
 :: как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется.
 ::: {{tick | ticked=1}} Только пояснение о том, какое неравенство использвуется, лучше в скобках после написать, а не с новой строки.
-:::: {{tick}} И обозначай в тех логарифм не как ln, а как \ln.
+:::: {{tick | ticked=1}} И обозначай в тех логарифм не как ln, а как \ln.
 ::::: Ааа, хрень полная написана. Во-первых, log n и ln n при маленьких n отличаются так же, как при больших — а именно в константу раз. Во-вторых, значок ~ означает, что функции эквивалентны, то есть их частное при больших n стремится к 1.
-: {{tick}} Кстати, там где ты говоришь про высоту декартового дерева, говори не O(\ln n), а O(\log n) (просто один раз упомяни, что они в константу раз различаются и все).
+: {{tick | ticked=1}} Кстати, там где ты говоришь про высоту декартового дерева, говори не O(\ln n), а O(\log n) (просто один раз упомяни, что они в константу раз различаются и все).
 : {{tick | ticked=1}} У тебя merge в техе в разных местах по-разному написан, то <tex> Merge </tex>, то <tex>\operatorname{Merge}</tex>.
 : {{tick | ticked=1}} «Построение декартово дерева»
 :: все еще не исправлено...--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
 ::: аргх. правильно говорить «декартова дерева». --[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)

@@ Строка 35: / Строка 35: @@
 :::::: ох. Суть формулировки ты не изменил, а только сделал более мутной. «приоритеты  которого выбраны случайно и независимо». Возьмем _нечестную_ игральную кость с 1000000000 граней, к примеру, будем выбирать ею приоритеты. Случайно? Случайно. Независимо? Независимо. Подходит для выбора приоритетов? Нет. В чем же проблема?--[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)
 ::::::: Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке доказательства -- [[Участник:Орынбаев Хусаин|Орынбаев Хусаин]] 15:58, 1 мая 2012 (GST)
 :: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
 :: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?
@@ Строка 42: / Строка 43: @@
 :: как-то ты сразу суммы свернул, надо чуть поподробнее расписать замены диапазонов суммирования, ну или что там используется.
 ::: {{tick | ticked=1}} Только пояснение о том, какое неравенство использвуется, лучше в скобках после написать, а не с новой строки.
-:::: И обозначай в тех логарифм не как ln, а как \ln.
+:::: {{tick}} И обозначай в тех логарифм не как ln, а как \ln.
 : {{tick}} Кстати, там где ты говоришь про высоту декартового дерева, говори не O(\ln n), а O(\log n) (просто один раз упомяни, что они в константу раз различаются и все).
 : {{tick | ticked=1}} У тебя merge в техе в разных местах по-разному написан, то <tex> Merge </tex>, то <tex>\operatorname{Merge}</tex>.
-: {{tick}} «Построение декартово дерева»
+: {{tick | ticked=1}} «Построение декартово дерева»
 :: все еще не исправлено...--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
 ::: аргх. правильно говорить «декартова дерева». --[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)

@@ Строка 34: / Строка 34: @@
 ::::: '''НЕ ИСПРАВЛЕНО!!!!!1111''' --[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
 :::::: ох. Суть формулировки ты не изменил, а только сделал более мутной. «приоритеты  которого выбраны случайно и независимо». Возьмем _нечестную_ игральную кость с 1000000000 граней, к примеру, будем выбирать ею приоритеты. Случайно? Случайно. Независимо? Независимо. Подходит для выбора приоритетов? Нет. В чем же проблема?--[[Участник:Dgerasimov|Дмитрий Герасимов]] 13:48, 1 мая 2012 (GST)
-::::::: Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке раздела -- [[Участник:Орынбаев Хусаин|Орынбаев Хусаин]] 15:58, 1 мая 2012 (GST)
+::::::: Мне кажется, что все предыдущие формулировки были мутными, ведь нам нужно чтобы высота была логарифм, поэтому выбираем приоритеты случайно, единственное что надо выделить это независимость, она используется в утверждении что среди X_{i,k} любая вершина может оказаться с минимальным приоритетом. Иначе говоря я не вижу мест, где моей формулировки недостаточно. Насчет проблемы, если она заключается в том что приоритеты должны быть разными, то да формулировка не до конца корректна. Но если к примеру написать как написано где то глубоко в кормене "Декартово дерево из n ключей, приоритеты 'y' у которого выбраны так, что n! перестановок входных ключей равновероятны, имеет высоту O(log n)" станет несколько ... в общем я написал в шапке доказательства -- [[Участник:Орынбаев Хусаин|Орынбаев Хусаин]] 15:58, 1 мая 2012 (GST)
 :: вот эта запись x_i — ancestor x_j — не очень. Во-первых, ancestor of, а во-вторых, «—» как-то неуместно. Лучше x_i is ancestor of x_j, в общем.
 :: «использовали линейность математического ожидания E» — эм, просто линейность математического ожидания, зачем значок E тут?

@@ Строка 21: / Строка 21: @@
 : {{tick}} Написать, чем отличаются реализации 1 и 2 друг от друга.
 :: '''Наверное, они отличаются не тем, что не используется merge или split, а в том, что просто их меньше во второй реализации?'''--[[Участник:Dgerasimov|Дмитрий Герасимов]] 16:40, 28 апреля 2012 (GST)
-::: Если написать что в реализации 2 используется меньше split или merge, будет выглядеть не очень, когда их там в принципе нет, если я правильно понял(Редактор)
+::: Если написать что в реализации 2 используется меньше split или merge, будет выглядеть не очень, когда их там в принципе нет(Редактор)
 :: И писать «этот вариант отличается» надо либо после объявления реализации № 2, либо вообще после неет.
 : {{tick | ticked=1}} А вообще почему-то реализация 1 расписана по пунктом, а во второй все сплошным текстом.