2001-gre-vs-practice.pdf/Q39 — различия между версиями

Версия 19:07, 23 декабря 2024 (просмотреть исходный код) StasFomin (обсуждение | вклад) ← Предыдущая правка		Текущая версия на 21:11, 23 декабря 2024 (просмотреть исходный код) Илья52 (обсуждение | вклад)
Строка 1:		Строка 1:
	== Вопрос: Q39-e5724f ==		== Вопрос: Q39-e5724f ==
		+
	{{reserve-task|[[Участник:Илья52|илья52]] 11:04, 21 декабря 2024 (UTC)}}		{{reserve-task|[[Участник:Илья52|илья52]] 11:04, 21 декабря 2024 (UTC)}}
	<blockquote>		<blockquote>
Строка 10:		Строка 11:
	=== Ответы ===		=== Ответы ===
−	# Нет такого условия, время всегда будет одним и тем же.	+	* Нет такого условия, время всегда будет одним и тем же.
−	# <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m>	+	* Правильный ответ: <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m>
−	# <m>x > y</m>	+	* <m>x > y</m>
−	# <m>\frac{1}{x} + \frac{1}{w} < \frac{1}{y} + \frac{1}{z}</m>	+	* <m>\frac{1}{x} + \frac{1}{w} < \frac{1}{y} + \frac{1}{z}</m>
−	# <m>x + w > y + z</m>	+	* <m>x + w > y + z</m>
	=== Объяснение ===		=== Объяснение ===
Строка 34:		Строка 35:
	Получим неравенство <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m>.		Получим неравенство <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m>.
−
−	Правильный ответ: 2.
	</i>		</i>

---

Текущая версия на 21:11, 23 декабря 2024

Вопрос: Q39-e5724f

Для вычисления матричного произведения и , где содержит строк и столбцов, а - строк и столбцов, требуется время, пропорциональное , и в результате получается матрица из строк и столбцов. Рассмотрим произведение трех матриц , , , которые содержат, соответственно, строк и столбцов, строк и столбцов, а также строк и столбцов. При каком условии потребуется меньше времени, чтобы вычислить произведение как () , (т.е. сначала умножить первые две матрицы), или быстрее вычислить его как ()?

Ответы

• Нет такого условия, время всегда будет одним и тем же.
• Правильный ответ:

Объяснение

Исходники — вопрос 39 на 33 странице книги «2001-gre-vs-practice.pdf»

Оценим сколько времени нужно на умножение () .

Умножение () пропорцианально , получается матрица размера на . Далее результат умножается на . Время умножения пропорцианально .

Таким образом, первое умножение пропорцианально .

Аналогичными рассуждениями получаем, что умножение вторым способом пропорцианально .

По условию, первый способ должен занимать меньше времени, составим неравенство:

Разделим обе части на .

Получим неравенство .

StasFomin 19:04, 23 декабря 2024 (UTC): Илья, если вы невнимательно посмотрели постановку квеста, просмотрите сначала все замечания по оформлению в канале, уже нет сил переделывать за всеми.