Проблема компьютерной логики

Рассмотрим многоуровневый компьютер, в котором все уровни различны. На каждом уровне есть инструкции, которые в разы столь же мощны, как и уровни ниже этого уровня; то есть одна команда уровня r может выполнять работу инструкций r-1 m уровня. Если программе уровня 1 требуется k секунд для запуска, сколько времени будут выполняться эквивалентными программами на уровнях 2, 3 и 4, предполагая n инструкций r уровня требуется интерпретировать одну команду r + 1?

Это решение, с которым я столкнулся. Кто-нибудь может подтвердить или прокомментировать?

Level (r)        Level-1 Instructions (m)          Time
4                m^3                               t(q) ==(m^3q+n+nm+nm^2) (k/q)
3                m^2                       t(q) =(m^2q+n+nm)(k/q)
2                m                             t(q) = (mq+n)(k/q)
1                1                             t(q) = k

Для вычисления времени выполнения t (q) для данной программы, содержащей q инструкций уровня 1, мы должны учитывать как экспоненциально возрастающее число инструкций уровня 1, представляемых каждой командой уровня r (показано как m ^ ( r-1)) и дополнительное количество команд уровня 1, необходимых для интерпретации для каждого слоя, на котором выполняется программа (отображается как nm ^ (r-1)). Дополнительные команды уровня 1, используемые для интерпретации нижними уровнями, также должны быть добавлены в окончательные уравнения для r > 2. Наконец, для каждого уравнения мы можем определить количество секунд, которое программа выполняет для запуска, умножая общее количество инструкций уровня 1, используемых временем выполнения одного цикла уровня 1, как рассчитывается (k/q).

Отказ от ответственности: это домашняя работа, задание уже передано. Я просто не могу получить семантику этой проблемы, и я действительно хотел бы ее понять.

Ответ 1

Проблема заключается в том, что если на уровне 1 требуется k единиц времени, то k/m единиц он будет принимать на втором уровне, так как...

Ответ 2

Я думаю, вы все делаете это слишком сложно. Другими словами, в заявлении проблемы говорится, что каждый уровень выполняется в m раз быстрее, чем слой выше. Следовательно, слой 2 завершает программы в 1/м время, слой 3 в 1/м * 1/м и так далее. Итак, окончательное уравнение справедливо:

t (q) = k/(m ** q)

Ответ 3

Это просто рекурсивная функция:

t(q, r) = q*k if r == 1
t(q, r) = q*t(m, r-1) + t(n, r-1)

Теперь объясняется:

This is obvious since it was stated in the question (I parameterized k as the elementary unit, k is the time for one level 1 instruction):
t(q, r) = q*k if r == 1

The amount of time it takes to execute a function with q r-1 instructions
t(q, r) = 
          q times the amount of the time it takes for m level r-1 instruction
          q*t(m, r-1)
                        plus the time it takes for n level r-1 instructions
                        + t(n, r-1)

Ответ 4

Я не уверен, что определение задачи завершено, потому что, если это я, я не вижу другого разумного способа его решения, чем его упрощения.

Итак, вот несколько вещей, которые я бы предположил:

t (q, 1) = k (нам нужно найти t (q, r)) = > t (1,1) = q/k, почему? Потому что, если мы не предполагаем, что время зависит только от количества инструкций, а не от типа инструкций, мы на самом деле находимся там, где эта задача не разрешима. В таком случае q не будет рассматриваться как число, и мы не можем предположить, что другой набор инструкций потребует меньше или больше времени, основанного на числе инструкций. В заключение, что касается моего чтения в этой задаче, они связывают время только с количеством инструкций.
Если программа является родной на одном уровне "r", тогда для их интерпретации потребуется n инструкций другого уровня (сделать их родными). В определении задачи (представленном здесь) нет ничего, что заставляет вас интерпретировать только инструкции уровня r + 1. Фактически, потому что мы начинаем с первого уровня, "n инструкций уровня r требуется для интерпретации одной команды r + 1" было бы бесполезно, если мы не можем предположить, что я говорю выше.
также q инструкций уровня X после интерпретации всегда должны преобразовываться в q-уровни Y-инструкций, другие тиски мы никогда не сможем узнать время выполнения другого уровня, потому что количество инструкций может сильно различаться (например, в реальном мире).

Итак, вот ответ с этими предпосылками:

q=number of level one program instructions
t(q, r)=time necessary to execute q **level 1** instructions on level r comp
t(1, r)=time necessaty to execute one instruction on level r comp
t(1, 1)=time necessary to execute one instruction on level 1 comp
t(q, 1)/m^(r-1)=time to execute q **native** instructions on level r comp

t(q, 1)=k
t(1, 1)=k/q
t(q,r)=(time to interpret q non-native instructions/convert them to native) + (time to actually execute the code)
t(q,r)=t(qn, 1)/m^(r-1) + t(q, 1)/m^(r-1)
t(q,r)=(time to execute qn native instructions) + (time to execute q native instructions)
t(q,r)=nt(q, 1)/m^(r-1) + t(q, 1)/m^(r-1)
t(q,r)=(n+1)t(q, 1)/m^(r-1)
t(q,r)=(n+1)k/m^(r-1)

Если какое-либо из трех предположений неверно, вам нужно ввести новые неизвестные функции, поэтому ответ станет просто уравнением неизвестных функций, которое было бы бесполезным, но гораздо более бесполезным, чем этот. Это просто красивее:)

Btw вам нужно посмотреть ваши упражнения в университете, чтобы увидеть, как схожие задачи были решены, чтобы быть уверенным, что подход к проблеме правильный.