Просмотр исходного текста страницы Сортировка/Задачи/sorting-convex-hull

<latex>
Рассмотрим следующие функциональные задачи:
\begin{itemize}
\item Задача сортировки. Даны различные целые числа $a_1, \dots , a_n$. Нужно найти перестановку $p_1, \dots , p_n$ такую
что $a_{p_1} < a_{p_2} ~\iff~ p_1 < p_2$. То есть, перестановка задаёт порядок чисел от наименьшего к наибольшему.
\item Задача о выпуклой оболочке. На плоскости дан набор из n целых точек $(x_1, y_1), \dots ,(x_n, y_n)$. Нужно найти
их выпуклую оболочку, то есть, наименьшее по включению выпуклое множество, содержащее все эти точки. Выходом к задаче должен быть набор чисел $p_1, \dots , p_m$ такой, что выпуклую оболочку образуют точки именно с такими номерами и при этом рёбра многоугольника проходят по соседним в этом наборе точкам, а также между точками $p_1$ и $p_m$. Приэтом точка $p_1$ является лексикографически минимальной
в этом наборе, то есть, она обладает наименьшей x-координатой, а среди точек с такой x-координатой – наименьшей y-координатой.
\end{itemize}

Необходимо построить сведение первой задачи ко второй, используя следующую модель сведения:
Пусть есть две функции над словами из алфавита $\Sigma, \mathcal{A} : \Sigma^{*} \rightarrow \Sigma^{*}$ и $\mathcal{B} : \Sigma^{*} \rightarrow \Sigma^{*}$.
Сведением функции $\mathcal{A}$ к функции $\mathcal{B}$ мы будем называть такую вычислимую за линейное время функцию $f : \Sigma^{*}$, что $\mathcal{A}(x)=\mathcal{B}(f(x))$.
Считайте, что предикат $a \le b$ и функции $a + b$ и $a^2$ от целых чисел вычисляются за $O(1)$.
</latex>

[[Категория:Решенные задачи]]
[[Категория:Теоретические задачи]]