Сортировка/Задачи/sorting-convex-hull - История изменений

StasFomin: Массовая правка: добавление Категория:Теоретические задачи

2023-05-04T06:50:55Z

Массовая правка: добавление Категория:Теоретические задачи

StasFomin: Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]]

2020-05-20T15:49:54Z

Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]]

StasFomin: Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]]

2020-02-20T09:08:10Z

Массовая правка: замена :Решенные задачи]] на :Нерешенные задачи]]

StasFomin в 01:08, 16 мая 2019

2019-05-16T01:08:45Z

StasFomin: StasFomin переименовал страницу Участник:Олеся Кузнецова/sorting-convex-hull в Сортировка/Задачи/sorting-convex-hull без оставления перенаправления

2019-05-16T01:08:31Z

StasFomin переименовал страницу Участник:Олеся Кузнецова/sorting-convex-hull в Сортировка/Задачи/sorting-convex-hull без оставления перенаправления

Олеся Кузнецова: Олеся Кузнецова переименовал страницу Участник:Олеся Кузнецова/Задача sorting-convex-hull в Участник:Олеся Кузнецова/sorting-convex-hull

2019-05-15T18:40:56Z

Олеся Кузнецова переименовал страницу Участник:Олеся Кузнецова/Задача sorting-convex-hull в Участник:Олеся Кузнецова/sorting-convex-hull

Олеся Кузнецова: Новая страница: « Рассмотрим следующие функциональные задачи: \begin{itemize} \item Задача сортировки. Даны ра…»

2019-05-15T18:40:33Z

Новая страница: «<latex> Рассмотрим следующие функциональные задачи: \begin{itemize} \item Задача сортировки. Даны ра…»

Новая страница

<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>

[[Категория:Предложенные студентами задачи]]

← Предыдущая		Версия 06:50, 4 мая 2023
Строка 16:		Строка 16:

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

← Предыдущая		Версия 15:49, 20 мая 2020
Строка 15:		Строка 15:
	</latex>		</latex>

−	[[Категория:~~Нерешенные~~ задачи]]	+	[[Категория:Решенные задачи]]

← Предыдущая		Версия 09:08, 20 февраля 2020
Строка 15:		Строка 15:
	</latex>		</latex>

−	[[Категория:~~Решенные~~ задачи]]	+	[[Категория:Нерешенные задачи]]

← Предыдущая		Версия 01:08, 16 мая 2019
Строка 15:		Строка 15:
	</latex>		</latex>

−	[[Категория:~~Предложенные студентами~~ задачи]]	+	[[Категория:Решенные задачи]]

← Предыдущая	Версия 01:08, 16 мая 2019
(нет различий)

← Предыдущая	Версия 18:40, 15 мая 2019
(нет различий)