2001-gre-vs-practice.pdf/Q39 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q39-e5724f == <blockquote> Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D…») |
Илья52 (обсуждение | вклад) |
||
| (не показано 12 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| + | {{checkme|[[Участник:Илья52|илья52]] 18:19, 21 декабря 2024 (UTC)}}== Вопрос: Q39-e5724f == | ||
| + | {{reserve-task|[[Участник:Илья52|илья52]] 11:04, 21 декабря 2024 (UTC)}} | ||
| + | <blockquote> | ||
| + | Для вычисления матричного произведения <m>M_1</m> и <m>M_2</m>, где <m>M_1</m> содержит <m>p</m> строк и <m>q</m> столбцов, а <m>M_2</m> - <m>q</m> строк | ||
| + | и <m>r</m> столбцов, требуется время, пропорциональное <m>pqr</m> , и в результате получается матрица из <m>p</m> строк и <m>r</m> столбцов. | ||
| + | Рассмотрим произведение трех матриц <m>N_1</m>, <m>N_2</m>, <m>N_3</m>, которые содержат, соответственно, <m>w</m> строк и <m>x</m> столбцов, <m>x</m> строк и <m>y</m> столбцов, а также <m>y</m> строк и <m>z</m> столбцов. При каком условии потребуется меньше времени, чтобы вычислить произведение | ||
| + | как (<m>N_1</m><m>N_2</m>) <m>N_3</m>, (т.е. сначала умножить первые две матрицы), или быстрее вычислить его как <m>N_1</m> (<m>N_2</m><m>N_3</m>)? | ||
| + | </blockquote> | ||
| − | == | + | === Ответы === |
| − | < | + | # Нет такого условия, время всегда будет одним и тем же. |
| − | + | # <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m> | |
| − | + | # <m>x > y</m> | |
| − | + | # <m>\frac{1}{x} + \frac{1}{w} < \frac{1}{y} + \frac{1}{z}</m> | |
| − | + | # <m>x + w > y + z</m> | |
| − | + | === Объяснение === | |
| − | + | <i> {{cstest-source|2001-gre-vs-practice.pdf|33|39}} | |
| − | + | Оценим сколько времени нужно на умножение (<m>N_1</m><m>N_2</m>) <m>N_3</m>. | |
| − | + | ||
| − | + | Умножение (<m>N_1</m><m>N_2</m>) пропорцианально <m>wxy</m>, получается матрица размера <m>w</m> на <m>y</m>. Далее результат умножается на <m>N_3</m>. Время умножения пропорцианально <m>wyz</m>. | |
| − | </ | + | |
| − | + | Таким образом, первое умножение пропорцианально <m>wxy + wyz</m>. | |
| − | < | + | |
| − | + | ||
| − | + | Аналогичными рассуждениями получаем, что умножение вторым способом пропорцианально <m>xyz + wxz</m>. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | По условию, первый способ должен занимать меньше времени, составим неравенство: | |
| − | + | ||
| − | + | ||
| + | <m>wxy + wyz < xyz + wxz</m> | ||
| − | + | Разделим обе части на <m>wxyz</m>. | |
| − | < | + | |
| − | + | ||
| − | + | Получим неравенство <m>\frac{1}{x} + \frac{1}{z} < \frac{1}{w} + \frac{1}{y}</m>. | |
| − | + | Правильный ответ: 2. | |
| − | + | ||
| − | + | ||
</i> | </i> | ||
| Строка 46: | Строка 41: | ||
{{question-ok|}} | {{question-ok|}} | ||
| − | [[ | + | [[Категория:Надо не забыть выбрать тему]] |
Текущая версия на 18:20, 21 декабря 2024
Решено: илья52 18:19, 21 декабря 2024 (UTC)== Вопрос: Q39-e5724f ==
Задача зарезервирована: илья52 11:04, 21 декабря 2024 (UTC)
Для вычисления матричного произведения и , где содержит строк и столбцов, а - строк и столбцов, требуется время, пропорциональное , и в результате получается матрица из строк и столбцов. Рассмотрим произведение трех матриц , , , которые содержат, соответственно, строк и столбцов, строк и столбцов, а также строк и столбцов. При каком условии потребуется меньше времени, чтобы вычислить произведение как () , (т.е. сначала умножить первые две матрицы), или быстрее вычислить его как ()?
Ответы
- Нет такого условия, время всегда будет одним и тем же.
Объяснение
Исходники — вопрос 39 на 33 странице книги «2001-gre-vs-practice.pdf»
Оценим сколько времени нужно на умножение () .
Умножение () пропорцианально , получается матрица размера на . Далее результат умножается на . Время умножения пропорцианально .
Таким образом, первое умножение пропорцианально .
Аналогичными рассуждениями получаем, что умножение вторым способом пропорцианально .
По условию, первый способ должен занимать меньше времени, составим неравенство:
Разделим обе части на .
Получим неравенство .
Правильный ответ: 2.