Đề thi cuối kỳ học phần Nhập môn phân tích độ phức tạp thuật toán năm 2024 - 2025 | Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Đề thi
NHẬP MÔN PHÂN TÍCH THUẬT TOÁN
(120 phút, được phép dùng tài liệu) Câu 1
Với n nguyên dương, ta đặt: 1 1 1 H = 1+ + + ...+ S = H + H + ... + H n và . 2 3 n n 1 2 n
a) Chứng minh: H = n +1 H − nH −1 n ( ) n+1 n
b) Tìm công thức tính Sn theo Hn.
c) Ước lượng độ lớn của Sn (so với n) theo kí hiệu Θ. Câu 2
Giả sử n là một số nguyên dương. Xem thuật toán mã giả trong bảng sau đây. I=1, result=0, h=1
While I<=n do J=1, t =1
a) Phân đoạn thuật toán thành các thành
While J<=h do
phần để có thể ước lượng số lượng các t = x * I * J
phép toán được thực hiện. J = J + 1
b) Hãy tính theo n số phép gán và số Endw
phép so sánh được thực hiện trong I = I + 1 thuật toán.
h = h + 1/I {phép chia số thực} result = result + x
c) Xác định độ phức tạp của thuật toán. Endw Câu 3
Giả sử n là một số nguyên dương. Xem hàm được viết trong bảng sau đây.
float Si(float x, long n) {
long i=1; float z=0; while(i<=n){
a) Phân đoạn hàm này thành các thành phần để có
long j=1; float t=1;
thể ước lượng số lượng các phép toán được thực
while(j-i<=i*i*i){ hiện. if(j>=i*i)
b) Ước lượng theo n số phép gán được thực hiện. t = t/2; t = t*x; j = j + 1; } z = z + i*t; i = 2*i; } return z; } (Đề thi gồm 1 trang)
Document Outline

• Câu 1
• Câu 2
• a) Phân đoạn thuật toán thành các thành phần để có thể ước lượng số lượng các phép toán được thực hiện.
• b) Hãy tính theo n số phép gán và số phép so sánh được thực hiện trong thuật toán.
• c) Xác định độ phức tạp của thuật toán.
  • Câu 3