Троичный поиск - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:26Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:33, 1 сентября 2022

2022-09-01T06:33:50Z

Rybak: imply explicitly

2016-06-11T01:21:09Z

imply explicitly

Savelin: /* Алгоритм */

2014-06-14T20:14:53Z

‎Алгоритм

Savelin: /* Псевдокод */

2014-06-14T19:50:13Z

‎Псевдокод

Savelin: /* Алгоритм */

2014-06-14T19:38:30Z

‎Алгоритм

Savelin: /* Псевдокод */

2014-06-14T19:04:11Z

‎Псевдокод

Savelin в 09:08, 23 мая 2014

2014-05-23T09:08:18Z

Savelin: /* См. также */

2014-05-22T16:53:24Z

‎См. также

Savelin: /* Источники информации */

2014-05-22T16:52:21Z

‎Источники информации

← Предыдущая		Версия 16:05, 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 Майкл Наки].
−	\|}
−
	'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.		'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.
	== Алгоритм ==		== Алгоритм ==

← Предыдущая		Версия 06:33, 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 Майкл Наки].
		+	\|}
		+
	'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.		'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.
	== Алгоритм ==		== Алгоритм ==

@@ Строка 2: / Строка 2: @@
 == Алгоритм ==
-[[File:Ternar2.png|thumb|280px|Пример. <tex>f(a) < f(b) \Rightarrow x_{min} \in [l, b]</tex>]]
+[[File:Ternar2.png|thumb|280px|Пример. <tex>f(a) < f(b) \implies x_{min} \in [l, b]</tex>]]
 Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
@@ Строка 13: / Строка 13: @@
 <tex> \forall x', x'' \in [l, r]: \\
-l       < x' < x'' < x_{min} \Rightarrow f(l)       > f(x') > f(x'') > f(x_{min}) \\
+l       < x' < x'' < x_{min} \implies f(l)       > f(x') > f(x'') > f(x_{min}) \\
-x_{min} < x' < x'' < r       \Rightarrow f(x_{min}) < f(x') < f(x'') < f(r)       </tex>.
+x_{min} < x' < x'' < r       \implies f(x_{min}) < f(x') < f(x'') < f(r)       </tex>.
 Значит если <tex>f(a) < f(b)</tex>, то <tex>x_{min} \in [l, b]</tex>,

@@ Строка 22: / Строка 22: @@
 пока не будет достигнута необходимая точность, то есть <tex> r-l < \varepsilon </tex>.
-Отрезок <tex>[l, a]</tex> брать нельзя, потому что мы не умеем различать случаи, когда <tex>f(a) < f(b)</tex> и <tex>a</tex> слева или справа от минимума.
+Из рассуждений и рисунка может возникнуть идея взять, например, отрезок <tex>[l, a]</tex> вместо отрезка <tex>[l, b]</tex>. Но этого делать нельзя, потому что мы не умеем различать случаи, когда <tex>f(a) < f(b)</tex> и <tex>a</tex> слева или справа от минимума.
-Можно заметить, что если мы всегда будем брать отрезок <tex>[l, b]</tex> при <tex>f(a) < f(b)</tex> или <tex>[a, r]</tex> при <tex>f(a) > f(b)</tex> , то минимум функции всегда будет в нашем отрезке. Если <tex>f(a) == f(b)</tex>, то можно взять любой отрезок.
+Можно заметить, что если мы всегда будем брать отрезок <tex>[l, b]</tex> при <tex>f(a) < f(b)</tex> или <tex>[a, r]</tex> при <tex>f(a) > f(b)</tex> , то минимум функции всегда будет в нашем отрезке. Если <tex>f(a) = f(b)</tex>, то можно взять любой отрезок.
 === Псевдокод ===

@@ Строка 30: / Строка 30: @@
 Рекурсивный вариант:
-  '''function''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
+  '''double''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
       '''if''' right - left < eps
           '''return''' (left + right) / 2
@@ Строка 42: / Строка 42: @@
 Итеративный вариант:
-  '''function''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
+  '''double''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
       '''while''' right - left > eps
           a = (left * 2 + right) / 3

← Предыдущая		Версия 09:08, 23 мая 2014
Строка 1:		Строка 1:
−	'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке.	+	'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.
−
	== Алгоритм ==		== Алгоритм ==

@@ Строка 57: / Строка 57: @@
 == См. также ==
-* [[Поиск с помощью золотого сечения]] {{---}} оптимизация троичного поиска.
+* [[Поиск с помощью золотого сечения]]
 == Источники информации ==

@@ Строка 62: / Строка 62: @@
 * Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.
 [[Категория: Дискретная математика и алгоритмы]]
 [[Категория: Алгоритмы поиска]]