Сортирующая сеть глубины O(log N) - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:40:08Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:35, 1 сентября 2022

2022-09-01T03:35:01Z

Dominica: /* Доказательство */

2015-05-17T09:13:58Z

‎Доказательство

Dominica: /* Анализ сепараторов */

2015-05-17T00:55:25Z

‎Анализ сепараторов

Dominica: /* Анализ сепараторов */

2015-05-17T00:18:59Z

‎Анализ сепараторов

Dominica: /* Анализ сепараторов */

2015-05-16T23:59:58Z

‎Анализ сепараторов

Dominica: /* Анализ сепараторов */

2015-05-16T23:26:32Z

‎Анализ сепараторов

Dominica: /* Анализ сепараторов */

2015-05-16T23:14:45Z

‎Анализ сепараторов

Dominica: /* Анализ сепараторов */

2015-05-16T18:23:05Z

‎Анализ сепараторов

Dominica: /* Конструкция разделителей */

2015-05-16T16:26:59Z

‎Конструкция разделителей

← Предыдущая		Версия 16:40, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Ажтаи (Ajtai), Комлос (Komlos) и Шимереди (Szemeredi) сконструировали сортирующую сеть на <tex>N</tex> входов глубины <tex> O(\log N) </tex>, при они не углублялись в исследование значения константы, получавшейся при правильном соблюдении необходимой ассимптотики. Впоследствии Патерсон выяснил, что <tex> O(\log N) </tex> можно заменить на <tex> c\log_2 N </tex> с константой приблизительно равной <tex> 6100 </tex>. Здесь будет описана более поздняя реализация, которая включает в себя меньшую константу <tex>c</tex>, а именно, будет доказано, что для любого целого числа <tex>N</tex> такого,что <tex>N \ge 2^{78}</tex> существует сортирующая сеть на <tex>N</tex> входов, такая, что глубина в худшем случае будет <tex>1830 \log_2 N - 58657 </tex>.		Ажтаи (Ajtai), Комлос (Komlos) и Шимереди (Szemeredi) сконструировали сортирующую сеть на <tex>N</tex> входов глубины <tex> O(\log N) </tex>, при они не углублялись в исследование значения константы, получавшейся при правильном соблюдении необходимой ассимптотики. Впоследствии Патерсон выяснил, что <tex> O(\log N) </tex> можно заменить на <tex> c\log_2 N </tex> с константой приблизительно равной <tex> 6100 </tex>. Здесь будет описана более поздняя реализация, которая включает в себя меньшую константу <tex>c</tex>, а именно, будет доказано, что для любого целого числа <tex>N</tex> такого,что <tex>N \ge 2^{78}</tex> существует сортирующая сеть на <tex>N</tex> входов, такая, что глубина в худшем случае будет <tex>1830 \log_2 N - 58657 </tex>.

← Предыдущая		Версия 03:35, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Ажтаи (Ajtai), Комлос (Komlos) и Шимереди (Szemeredi) сконструировали сортирующую сеть на <tex>N</tex> входов глубины <tex> O(\log N) </tex>, при они не углублялись в исследование значения константы, получавшейся при правильном соблюдении необходимой ассимптотики. Впоследствии Патерсон выяснил, что <tex> O(\log N) </tex> можно заменить на <tex> c\log_2 N </tex> с константой приблизительно равной <tex> 6100 </tex>. Здесь будет описана более поздняя реализация, которая включает в себя меньшую константу <tex>c</tex>, а именно, будет доказано, что для любого целого числа <tex>N</tex> такого,что <tex>N \ge 2^{78}</tex> существует сортирующая сеть на <tex>N</tex> входов, такая, что глубина в худшем случае будет <tex>1830 \log_2 N - 58657 </tex>.		Ажтаи (Ajtai), Комлос (Komlos) и Шимереди (Szemeredi) сконструировали сортирующую сеть на <tex>N</tex> входов глубины <tex> O(\log N) </tex>, при они не углублялись в исследование значения константы, получавшейся при правильном соблюдении необходимой ассимптотики. Впоследствии Патерсон выяснил, что <tex> O(\log N) </tex> можно заменить на <tex> c\log_2 N </tex> с константой приблизительно равной <tex> 6100 </tex>. Здесь будет описана более поздняя реализация, которая включает в себя меньшую константу <tex>c</tex>, а именно, будет доказано, что для любого целого числа <tex>N</tex> такого,что <tex>N \ge 2^{78}</tex> существует сортирующая сеть на <tex>N</tex> входов, такая, что глубина в худшем случае будет <tex>1830 \log_2 N - 58657 </tex>.

← Предыдущая		Версия 09:13, 17 мая 2015
Строка 362:		Строка 362:

	== Доказательство ==		== Доказательство ==
		+
		+	Будем считать, что
		+	<tex>A=k^2</tex> и <tex>\nu = 1/k </tex>.
		+	<tex>\mu = k ^{-5},\; \delta = \dfrac{1}{3}k^{-5}, \; \delta_F = \dfrac{2k}{k^2 - 1} </tex>
		+
		+	Тогда получим, что
		+	<tex> t_f = 3d - 20 </tex> и <tex>\alpha(t_f) = \omega(t_f) = d - 6 </tex>, где <tex>d = \log N/\log k </tex>.
		+
		+
		+	<tex> \varepsilon_B \le \dfrac{1}{4}k^{-4} \cdot \dfrac{4k-1}{4k} </tex>
		+
		+	<tex> \varepsilon_F \le \dfrac{1}{4}k^{-4} \cdot\dfrac{4k-1}{4k} </tex>
		+
		+
		+	<tex> \varepsilon^* = 2^{-39}\sqrt{1 + 79\ln 2} < 2 ^{-36} </tex>
		+
		+	<tex> f > 2^{34} \cdot \dfrac{1-2^{-12}}{1 - 2^{-36}} > 1.7 \times 10^{10} </tex>
		+
		+
		+	<tex> \varepsilon_B = 2 ^{-29}\sqrt{1 + 59\ln 2} < 1.25 \times 10 ^{-8} </tex>
		+
		+	<tex> \delta_F = 128/4095 </tex>
		+
		+	<tex> \varepsilon_F = 1/(8\times 10^7) = 1.25 \times 10^{-8} </tex>
		+
		+	<tex> \sqrt{\dfrac{2(1+\ln m)}{m}} \le k ^{-6} </tex>
		+
		+	<tex> M/32 < m \le M/16 </tex>
		+
		+	<tex> \log k = (\dfrac{1}{12} + o(1))\log M </tex> <tex> M \to \infty </tex>
		+
		+	<tex> f \ge (1 + o(1))\dfrac{m}{2k^4} \ge (1+o(1))k^8\ln k </tex>
		+
		+	<tex>M \to \infty </tex>
		+
		+	<tex> \varepsilon_B = k^{-6}, \; \delta_F = \dfrac{2k}{k^2 - 1}, \; \varepsilon_F = k^{-8} </tex>
		+
		+	<tex> \sqrt{\dfrac{2(1+\ln m)}{m}} \le \dfrac{1}{5}k^{-4} </tex>
		+
		+	<tex> \log k = (\dfrac{1}{8} + o(1))\log M </tex>
		+
		+	<tex> \sqrt{\dfrac{2(1 + \ln \lfloor M^{3/2}\rfloor)}{\lfloor M^{3/2}\rfloor}} \le k^{-6} </tex>
		+
		+	<tex> \varepsilon_B = \dfrac{1}{5}k^{-4}, \; \delta_F = \dfrac{2k}{k^2 - 1}, \; \varepsilon_F = \dfrac{1}{5}k^{-4} </tex>

@@ Строка 257: / Строка 257: @@
 <tex>|F_j|=fn,|B_j|=bn</tex>
-== Анализ сепараторов ==
+== Анализ разделителей ==
 лемма 6.3
 <tex> p = \dfrac{1}{kn}\sum\limits _{i=1}^k r_i </tex>

@@ Строка 348: / Строка 348: @@
 <tex>x \le \bigg(\dfrac{e^4(f+2)^2n}{4j}\bigg)^{2//\varepsilon_Ff}\bigg(\dfrac{2ej}{fn}\bigg)^{(f-2)/f} </tex>
-<tex>t = /\varepsilon_F(f-2)/2 </tex>
+<tex>t = \varepsilon_F(f-2)/2 </tex>
 == Доказательство ==

← Предыдущая		Версия 23:59, 16 мая 2015
Строка 328:		Строка 328:

	<tex>\dbinom{n}{k}\dbinom{j - fk/2}{k} \le \dbinom{n}{k}\dbinom{j}{k} < \bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k </tex>		<tex>\dbinom{n}{k}\dbinom{j - fk/2}{k} \le \dbinom{n}{k}\dbinom{j}{k} < \bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k </tex>
		+
		+	<tex> 1 + \sum\bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k < \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} </tex>
		+
		+	<tex>e^2nj \ge e^2j > 90 </tex>
		+
		+	<tex>x \le 2j/(f+2) </tex>
		+
		+	<tex>\dfrac{d}{dx}\ln\bigg(\bigg(\dfrac{e^2nj}{x^2}\bigg)^x\bigg) = \ln\dfrac{nj}{x^2} \ge \ln\dfrac{n(f + 2)^2}{4j} \ge \ln\dfrac{25(f+2)^2}{4f} \ge \ln 90</tex>
		+
		+
		+	<tex> \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} \cdot \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj} </tex>
		+
		+
		+	<tex>x = \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2/\varepsilon_Ff} \cdot \bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f} \cdot \dfrac{2ej}{fn}; </tex>
		+
		+
		+	<tex>(e^2/\varepsilon_F)^{2/f} = ((e^2/\varepsilon_F)^{\varepsilon_F})^{2/\varepsilon_Ff} \le (e^2))^{2/\varepsilon_Ff} </tex>
		+
		+	<tex>x \le \bigg(\dfrac{e^4(f+2)^2n}{4j}\bigg)^{2//\varepsilon_Ff}\bigg(\dfrac{2ej}{fn}\bigg)^{(f-2)/f} </tex>
		+
		+	<tex>t = /\varepsilon_F(f-2)/2 </tex>

	== Доказательство ==		== Доказательство ==

← Предыдущая		Версия 23:26, 16 мая 2015
Строка 313:		Строка 313:

	<tex> \sum\limits_{s=1}^n g(s) = \sum\limits_{s=1}^a g(s) + \sum\limits_{s=c}^n g(s) \\ < \dfrac{1}{1-\delta}(g(a) + g(c)) \\ \le \dfrac{\delta^{b-a} + \delta^{c-b}}{1-\delta}g(b) \\ \le \dfrac{1 + \delta}{1-\delta}g(b) </tex>		<tex> \sum\limits_{s=1}^n g(s) = \sum\limits_{s=1}^a g(s) + \sum\limits_{s=c}^n g(s) \\ < \dfrac{1}{1-\delta}(g(a) + g(c)) \\ \le \dfrac{\delta^{b-a} + \delta^{c-b}}{1-\delta}g(b) \\ \le \dfrac{1 + \delta}{1-\delta}g(b) </tex>
		+
		+
		+	<tex> \dfrac{90}{89} \bigg(\dfrac{e^2(f + 2)^2n}{4j}\bigg) ^{2j/(f+2)} </tex>
		+
		+
		+	<tex>s_1,\; s_1,+s_2, \; s_1+s_2+s_3, \; \dots ,\; s_1+s_2+s_3+\dots +s_k </tex>
		+
		+
		+	<tex> \sum\limits_{i = 1}^{k}(s_i+dfrac{1}{2}f) \le j, </tex>
		+
		+
		+	<tex> \sum\limits_{k=0}^n\dbinom{n}{k}\dbinom{j - fk/2}{k} </tex>
		+
		+
		+	<tex>\dbinom{n}{k}\dbinom{j - fk/2}{k} \le \dbinom{n}{k}\dbinom{j}{k} < \bigg(\dfrac{e^2(f+2)^2n}{k^2}\bigg)^k </tex>

	== Доказательство ==		== Доказательство ==

@@ Строка 277: / Строка 277: @@
 <tex> \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj}</tex>
 <tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{ejs}{(\tfrac{1}{2}fs + \varepsilon_Fj)n}\bigg)^{\tfrac{1}{2}fs+\varepsilon_Fj} </tex>
 == Доказательство ==

← Предыдущая		Версия 18:23, 16 мая 2015
Строка 258:		Строка 258:

	== Анализ сепараторов ==		== Анализ сепараторов ==
		+	лемма 6.3
		+	<tex> p = \dfrac{1}{kn}\sum\limits _{i=1}^k r_i </tex>
		+
		+	<tex>\sum\limits_{i=1}^k\|R_i\cap S\| \ge (p+t)ks </tex>
		+
		+
		+	<tex> \Bigg( \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t}\Bigg)^{ks} </tex>
		+
		+
		+	<tex> \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t} < \exp(-2t^2) </tex>
		+
		+
		+	<tex> \bigg( \dfrac{p}{p+t} \bigg) ^{p+t} \bigg(\dfrac{1-p}{1-p-t}\bigg)^{1-p-t} < \bigg(\dfrac{ep}{p+t}\bigg) ^{p+t} </tex>
		+
		+
		+	<tex> \exp(-2t^2ms) \le (em)^{-n^2/s} \le (em)^{-n} </tex>
		+
		+
		+	<tex> \dfrac{1 + e^{-5}}{1 - e^{-5}} \Bigg(\bigg(\dfrac{efn}{2\varepsilon_Fj}\bigg)^{2/f}\dfrac{2ej}{fn}\Bigg)^{\varepsilon_Fj}</tex>
		+
		+	<tex> p(s) \le \dbinom{n}{s} \bigg(\dfrac{ejs}{(\tfrac{1}{2}fs + \varepsilon_Fj)n}\bigg)^{\tfrac{1}{2}fs+\varepsilon_Fj} </tex>

	== Доказательство ==		== Доказательство ==

@@ Строка 246: / Строка 246: @@
 <tex> \delta_F \le 1/25 </tex>
 <tex> \varepsilon_F \ge \dfrac{2}{f - 2}\left (1 + \dfrac{\ln(3e^5f)}{\ln(0.12/e\delta_F)}\right )</tex>
 == Анализ сепараторов ==
 == Доказательство ==