https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&feed=atom&action=history
Сортировка/Задачи/sorting-convex-hull - История изменений
2024-03-28T11:20:13Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=25848&oldid=prev
StasFomin: Массовая правка: добавление Категория:Теоретические задачи
2023-05-04T06:50:55Z
<p>Массовая правка: добавление <a href="/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8" title="Категория:Теоретические задачи">Категория:Теоретические задачи</a></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 06:50, 4 мая 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16" >Строка 16:</td>
<td colspan="2" class="diff-lineno">Строка 16:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:Решенные задачи]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:Решенные задачи]]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Категория:Теоретические задачи]]</ins></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=11118&oldid=prev
StasFomin: Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]]
2020-05-20T15:49:54Z
<p>Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]]</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 15:49, 20 мая 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l15" >Строка 15:</td>
<td colspan="2" class="diff-lineno">Строка 15:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></latex></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></latex></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<del class="diffchange diffchange-inline">Нерешенные </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<ins class="diffchange diffchange-inline">Решенные </ins>задачи]]</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=10550&oldid=prev
StasFomin: Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]]
2020-02-20T09:08:10Z
<p>Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]]</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 09:08, 20 февраля 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l15" >Строка 15:</td>
<td colspan="2" class="diff-lineno">Строка 15:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></latex></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></latex></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<del class="diffchange diffchange-inline">Решенные </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<ins class="diffchange diffchange-inline">Нерешенные </ins>задачи]]</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=9613&oldid=prev
StasFomin в 01:08, 16 мая 2019
2019-05-16T01:08:45Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 01:08, 16 мая 2019</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l15" >Строка 15:</td>
<td colspan="2" class="diff-lineno">Строка 15:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></latex></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div></latex></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<del class="diffchange diffchange-inline">Предложенные студентами </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<ins class="diffchange diffchange-inline">Решенные </ins>задачи]]</div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=9612&oldid=prev
StasFomin: StasFomin переименовал страницу Участник:Олеся Кузнецова/sorting-convex-hull в Сортировка/Задачи/sorting-convex-hull без оставления перенаправления
2019-05-16T01:08:31Z
<p>StasFomin переименовал страницу <a href="/Permission_denied" title="Permission denied">Участник:Олеся Кузнецова/sorting-convex-hull</a> в <a href="/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull" title="Сортировка/Задачи/sorting-convex-hull">Сортировка/Задачи/sorting-convex-hull</a> без оставления перенаправления</p>
<table class='diff diff-contentalign-left'>
<tr style='vertical-align: top;' lang='ru'>
<td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 01:08, 16 мая 2019</td>
</tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div>
</td></tr></table>
StasFomin
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=9397&oldid=prev
Олеся Кузнецова: Олеся Кузнецова переименовал страницу Участник:Олеся Кузнецова/Задача sorting-convex-hull в Участник:Олеся Кузнецова/sorting-convex-hull
2019-05-15T18:40:56Z
<p>Олеся Кузнецова переименовал страницу <a href="/Permission_denied" title="Permission denied">Участник:Олеся Кузнецова/Задача sorting-convex-hull</a> в <a href="/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%9E%D0%BB%D0%B5%D1%81%D1%8F_%D0%9A%D1%83%D0%B7%D0%BD%D0%B5%D1%86%D0%BE%D0%B2%D0%B0/sorting-convex-hull&action=edit&redlink=1" class="new" title="Участник:Олеся Кузнецова/sorting-convex-hull (страница не существует)">Участник:Олеся Кузнецова/sorting-convex-hull</a></p>
<table class='diff diff-contentalign-left'>
<tr style='vertical-align: top;' lang='ru'>
<td colspan='1' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='1' style="background-color: white; color:black; text-align: center;">Версия 18:40, 15 мая 2019</td>
</tr><tr><td colspan='2' style='text-align: center;' lang='ru'><div class="mw-diff-empty">(нет различий)</div>
</td></tr></table>
Олеся Кузнецова
https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/sorting-convex-hull&diff=9395&oldid=prev
Олеся Кузнецова: Новая страница: «<latex> Рассмотрим следующие функциональные задачи: \begin{itemize} \item Задача сортировки. Даны ра…»
2019-05-15T18:40:33Z
<p>Новая страница: «<latex> Рассмотрим следующие функциональные задачи: \begin{itemize} \item Задача сортировки. Даны ра…»</p>
<p><b>Новая страница</b></p><div><latex><br />
Рассмотрим следующие функциональные задачи:<br />
\begin{itemize}<br />
\item Задача сортировки. Даны различные целые числа $a_1, \dots , a_n$. Нужно найти перестановку $p_1, \dots , p_n$ такую<br />
что $a_{p_1} < a_{p_2} ~\iff~ p_1 < p_2$. То есть, перестановка задаёт порядок чисел от наименьшего к наибольшему.<br />
\item Задача о выпуклой оболочке. На плоскости дан набор из n целых точек $(x_1, y_1), \dots ,(x_n, y_n)$. Нужно найти<br />
их выпуклую оболочку, то есть, наименьшее по включению выпуклое множество, содержащее все эти точки. Выходом к задаче должен быть набор чисел $p_1, \dots , p_m$ такой, что выпуклую оболочку образуют точки именно с такими номерами и при этом рёбра многоугольника проходят по соседним в этом наборе точкам, а также между точками $p_1$ и $p_m$. Приэтом точка $p_1$ является лексикографически минимальной<br />
в этом наборе, то есть, она обладает наименьшей x-координатой, а среди точек с такой x-координатой – наименьшей y-координатой.<br />
\end{itemize}<br />
<br />
Необходимо построить сведение первой задачи ко второй, используя следующую модель сведения:<br />
Пусть есть две функции над словами из алфавита $\Sigma, \mathcal{A} : \Sigma^{*} \rightarrow \Sigma^{*}$ и $\mathcal{B} : \Sigma^{*} \rightarrow \Sigma^{*}$.<br />
Сведением функции $\mathcal{A}$ к функции $\mathcal{B}$ мы будем называть такую вычислимую за линейное время функцию $f : \Sigma^{*}$, что $\mathcal{A}(x)=\mathcal{B}(f(x))$.<br />
Считайте, что предикат $a \le b$ и функции $a + b$ и $a^2$ от целых чисел вычисляются за $O(1)$.<br />
</latex><br />
<br />
[[Категория:Предложенные студентами задачи]]</div>
Олеся Кузнецова