Vấn đề logic máy tính

Question

Hãy xem xét một máy tính đa cấp trong đó tất cả các cấp đều khác nhau. Mỗi cấp độ có các chỉ dẫn mạnh gấp m lần so với cấp dưới nó; có nghĩa là, một lệnh r mức có thể thực hiện công việc của các chỉ lệnh r - 1 ở mức m, Nếu chương trình mức 1 yêu cầu k giây để chạy, các chương trình tương đương sẽ mất bao nhiêu ở mức 2, 3 và 4, giả sử hướng dẫn mức n được yêu cầu để giải thích một lệnh r + 1 đơn?

Đây là giải pháp mà tôi đã đưa ra. Bất cứ ai có thể xác nhận hoặc bình luận?

Đây là giải pháp mà tôi sẽ đề cập đến. Bất cứ ai có thể xác minh hoặc bình luận?

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ính toán t runtime (q) cho một chương trình nào đó có chứa q level-1 hướng dẫn, chúng ta phải đưa vào tài khoản cả số theo cấp số nhân tăng của các hướng dẫn cấp 1 mỗi hướng dẫn mức r đại diện (hiển thị như m^(r-1)) và số lượng bổ sung của các hướng dẫn mức 1 cần thiết để diễn giải cho mỗi lớp mà chương trình được thực hiện (được hiển thị dưới dạng nm^(r-1)). Các hướng dẫn cấp 1 bổ sung được sử dụng để giải thích bởi các cấp thấp hơn cũng phải được thêm vào các phương trình cuối cùng cho r> 2. Cuối cùng, đối với mỗi phương trình, chúng ta có thể xác định số giây mà chương trình cần để chạy bằng cách nhân tổng số lệnh cấp 1 được sử dụng bởi thời gian thực hiện của một chu kỳ cấp 1, như được tính bằng (k/q).

Tuyên bố từ chối trách nhiệm: Bài tập về nhà IS này, bài tập đã được giao. Tôi không thể hiểu ngữ nghĩa của vấn đề này và tôi thực sự muốn hiểu nó.

Answer 1

Vấn đề chỉ đơn giản nói rằng nếu phải mất k đơn vị thời gian ở mức 1 thì đơn vị k/m nó sẽ mất ở cấp độ thứ hai như vậy ...

Answer 2

Nó chỉ là một hàm đệ quy:

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

Bây giờ giải thích:

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) 

Answer 3

Tôi không chắc định nghĩa nhiệm vụ được hoàn tất bởi vì nếu nó là tôi không thấy bất kỳ cách lành mạnh khác để giải quyết nó hơn là đơn giản hóa nó.

Vì vậy, dưới đây là một vài điều tôi muốn giả:

1. t (q, 1) = k (chúng tôi được giao nhiệm vụ để tìm t (q, r)) => t (1,1) = q/k, tại sao? Bởi vì nếu chúng ta không cho rằng thời gian chỉ phụ thuộc vào số lượng hướng dẫn chứ không phải trên kiểu lệnh, chúng ta đang ở trong thực tế, nơi nhiệm vụ này không thể giải được. Trong trường hợp này q sẽ không được xem xét như một số và chúng ta không thể giả định một tập hợp các lệnh khác sẽ mất ít hoặc nhiều thời gian hơn dựa trên số lượng lệnh. Trong kết luận, theo như đọc của tôi đi trong nhiệm vụ này họ liên quan đến thời gian chỉ để số hướng dẫn.
2. nếu chương trình có nguồn gốc ở một cấp 'r' thì sẽ mất n hướng dẫn của một cấp độ khác để diễn giải chúng (làm cho chúng nguyên gốc). Không có gì trong định nghĩa nhiệm vụ (như được trình bày ở đây) mà buộc bạn phải giải thích chỉ các cấp r + 1 hướng dẫn. Trên thực tế bởi vì chúng ta bắt đầu từ cấp một, "hướng dẫn n cấp r được yêu cầu để giải thích một lệnh r + 1 duy nhất" sẽ là khá vô dụng nếu chúng ta không thể giả định những gì tôi đang nói ở trên.
3. cũng hướng dẫn mức q X sau khi được giải thích nên thường xuyên chuyển đổi để hướng dẫn Y mức q, vise khác mà chúng tôi không bao giờ có thể biết được thời gian thực hiện một tầm cao mới vì số hướng dẫn rất có thể khác nhau (như trong thế giới thực)

vì vậy, đây là câu trả lời với những điều kiện tiên quyết:

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) 

Nếu bất kỳ của 3 giả định là sai, bạn cần phải giới thiệu chức năng mới chưa biết nên trả lời sẽ trở thành chỉ là một phương trình của chức năng chưa biết đó sẽ là vô dụng nhưng nhiều hơn nữa vô dụng hơn cái này. Điều này chỉ đẹp hơn :)

Btw bạn cần xem xét bài tập của mình ở trường đại học để xem các nhiệm vụ tương tự đã được giải quyết như thế nào để đảm bảo tiếp cận vấn đề là chính xác.

Answer 4

Tôi nghĩ rằng tất cả các bạn đang làm quá phức tạp. Báo cáo vấn đề nói, nói cách khác, mỗi lớp chạy nhanh gấp m lần so với lớp trên. Do đó lớp 2 hoàn thành chương trình trong 1/m thời gian, lớp 3 trong 1/m * 1/m và như vậy. Vì vậy, phương trình cuối cùng chỉ là:

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