Hãy trình bày thuật toán sắp xếp nổi bọt theo phương pháp làm mịn dần.

Hãy trình bày thuật toán sắp xếp chọn theo phương pháp làm mịn dần.

Hãy trình bày thuật toán tìm kiếm tuần tự theo phương pháp làm mịn dần.

Với một bài toán, chỉ có một phương pháp thiết kế làm mịn dần duy nhất. Đúng hay sai?

Phát biểu sau về phương pháp làm mịn dần là đúng hay sai?

Phương pháp thiết kế làm mịn dần sẽ chia bài toán gốc thành các bài toán con, mỗi bài toán con sẽ lại được phân tích và chia thành các bài toán/vấn đề con nhỏ hơn nữa. Quá trình phân rã thành các bài toán con đó sẽ còn tiếp tục cho đến khi nhận được bài toán đủ đơn giản để có thể giải ngay bằng các câu lệnh lập trình. Quá trình thiết kế đó sẽ kết thúc khi tất cả các bài toán con được giải quyết hoàn toàn.

Phương pháp thiết kế làm mịn dần chính là tên gọi khác của phương pháp thiết kế từ trên xuống.

Mệnh đề nào sau đây mô tả đúng về phương pháp thiết kế làm mịn dần?

A. Thiết kế được chia làm nhiều bước, các bước đều độc lập hoàn toàn với nhau. B. Thiết kế được chia làm nhiều bước, bước sau thường là chi tiết hơn, làm mịn hơn một bước ở trước đó.

C. Thiết kế được chia làm nhiều bước, bước sau thường là tổ hợp, kết hợp các kết quả của các bước trước đó.

D. Thiết kế được chia làm nhiều bước, mỗi bước sẽ tương ứng với một hàm hoặc chương trình con nào đó của bước trước.

Giả sử f(n) = an* + a,.n*?

Nếu f(n) = O(g(n)) thì có suy ra được g(n) = O(f(n)) hay không?

Xác định độ phức tạp thời gian của hàm sau:

Em hãy xác định thời gian chạy T(n) của thuật toán sắp xếp chèn sau, với n là độ dài của dãy A.

Cho biết hàm sau thực hiện công việc gì và hãy xác định độ phức tạp thời gian của chương trình.

Cho biết thuật toán sau thực hiện công việc gì và hãy xác định độ phức tạp

thời gian của thuật toán.

1 def findMax(A):

2 maxVal = A[0]

Tính độ phức tạp của các hàm thời gian sau:

a) T(n) = n + 2log n.

c) T(n) = 2100

b) T(n) = n2 + 3nlogn + 2n.

d) T(n) = 2n+1.

Chứng minh rằng nếu f(n) = O(g(n)) và g(n) = O(h(n)) thì ta có: f(n) = O(h(n)).

 a) Chứng minh n = O(n2).

b) Chứng minh n2 = O(n).

Tính độ phức tạp của các hàm sau theo kí hiệu O-lớn.

a) n + 2n.log(n) + 10.

b) 2n2 + 3n3log(n) + n3/2.

c) 2" + 3" + 5".

Đánh giá thời gian chạy của thuật toán sắp xếp nổi bọt đã học trong sách giáo khoa.

Đánh giá thời gian chạy của thuật toán sắp xếp chèn đã học trong sách giáo khoa.

Đánh giá thời gian chạy của chương trình sau tính theo đơn vị thời gian, A là một dãy số cho trước có n phần tử.

Đánh giá thời gian chạy của chương trình sau, trong đó A là ma trận vuông bậc n.

Đánh giá thời gian chạy của chương trình sau:

Đánh giá thời gian chạy của chương trình sau:

Giả sử một chương trình P mô tả một thuật toán nào đó. Người ta đo được các thông tin thời gian sau:

T1 = thời gian chương trình nhập dữ liệu input và đưa vào bộ nhớ.

T2 = thời gian chạy chương trình từ khi nhập xong dữ liệu input và tính xong dữ liệu output.

T3 = thời gian đưa dữ liệu output ra thiết bị ngoài chuẩn.

Khi đó thời gian chạy chương trình T(n) dùng để tính độ phức tạp thời gian của thuật toán là phương án nào trong các phương án sau?

A. T1 + T2.

B. T2.

C. T2+T3.

Viết chương trình tạo dãy A có n phần tử với giá trị ngẫu nhiên. Sau đó tính thời gian chạy của lệnh sắp xếp A.sort() của Python và so sánh thời gian này với các thời gian chạy của các thuật toán em đã biết (xem Câu 23.8). Em có nhận xét gì về kết quả thu được?

Hàm sau tạo một dãy số nguyên có n phần tử và các giá trị nằm ngẫu nhiên trong phạm vi [a, b].

1 def sinh_day(n,a,b):

2 from random import randint

3 A = [randint(a, b) for i in range(n)] 

4 return A

Em hãy viết chương trình tạo dãy A như trên với độ dài n và thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A. Sau đó tính thời gian chạy của các thuật toán này. Ghi lại bảng kết quả với các giá trị của n = 100, 1000, 10 000, 100 000.

Viết chương trình thực hiện các việc sau:

– Nhập dãy số A từ bàn phím.

– Thực hiện các thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt trên dãy A.

– Tính thời gian chạy của từng thuật toán trên đối với dãy

A, kết quả đưa ra màn hình.

Trong các bài toán sau, kích thước đầu vào của bài toán là gì, được tính như thế nào?

a) Bài toán sắp xếp dãy số A theo thứ tự tăng dần.

b) Bài toán tính tổng 1+ 2 + ... + n với n là số tự nhiên cho trước.

c) Bài toán tính gcd(a,b) – ước chung lớn nhất của hai số tự nhiên cho trước a, b.

Với thuật toán sắp xếp chèn (trong sách giáo khoa), cùng kích thước n, thì bộ dữ liệu kiểm thử nào cho thời gian chạy:

a) Nhanh nhất?

b) Chậm nhất?

Cùng một chương trình, với hai bộ dữ liệu đầu vào khác nhau (cùng kích thước) thì thời gian chạy chương trình với hai bộ dữ liệu này sẽ giống nhau hay khác nhau?

Để chứng minh một thuật toán là đúng cần phải làm gì? Chọn phương án đúng nhất trong các phương án sau:

A. Cần tiến hành kiểm thử chương trình cài đặt thuật toán, kiểm thử càng nhiều càng tốt.

B. Cần cài đặt thuật toán trên càng nhiều ngôn ngữ lập trình càng tốt.

C. Cần chạy thử chương trình cài đặt thuật toán xem thời gian chạy có nhanh hay không.

D. Cần chứng minh bằng toán học chặt chẽ tính đúng của thuật toán.

Mệnh đề sau có đúng không?

Muốn chứng minh một chương trình chạy đúng chỉ cần thực hiện thật nhiều việc kiểm thử (test). Nếu kiểm tra trên tất cả các bộ dữ liệu kiểm thử đều đúng thì chương trình đúng.

Viết chương trình cho phép người dùng nhập các số nguyên từ bàn phím, sắp xếp các số đã được nhập theo thứ tự tăng dần và in ra màn hình dãy số đã được sắp xếp, nhập vào từ khoá 'end' để kết thúc chương trình. Yêu cầu ngay khi nhập xong dữ liệu thì dãy số cũng sắp xếp xong (chúng ta có thể thực hiện bằng cách mỗi khi nhập một phần tử mới, sắp xếp vào đúng vị trí của nó trong dãy số).

Chúng ta thường thấy danh sách lớp thường được sắp xếp theo thứ tự bảng chữ cái. Cho trước một danh sách lớp chưa được sắp xếp như sau: Nam, An Cường, Sơn, Trung, Bình.

Hãy cho biết kết quả sau mỗi bước lặp với mỗi thuật toán sắp xếp nổi bọt, sắp xếp chèn và sắp xếp chọn cho đến khi danh sách được sắp xếp xong.

Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của thuật toán sắp xếp được mô tả như sau:

5, 7, 4, 6, 9, 20, 8

4, 5, 7, 6, 9, 20, 8

4, 5, 6, 7, 9, 20, 8

Thuật toán sắp xếp được sử dụng là:

A. Thuật toán sắp xếp chọn.

C. Thuật toán sắp xếp nổi bọt.

B. Thuật toán sắp xếp chèn.

Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của thuật toán sắp xếp được mô tả như sau:

5, 8, 1, 4, 7, 10

5, 1, 8, 4, 7, 10

5, 1, 4, 8, 7, 10

Thuật toán sắp xếp được sử dụng là:

A. Thuật toán sắp xếp chọn.

C. Thuật toán sắp xếp nổi bọt.

B. Thuật toán sắp xếp chèn.

Thứ tự các phần tử trong dãy số sau ba vòng lặp liên tiếp của một thuật toán sắp xếp được mô tả như sau:

1, 4, 10, 9, 3, 7, 12, 20

1, 3, 10, 9, 4, 7, 12, 20

1, 3, 4, 9, 10, 7, 12, 20

Thuật toán sắp xếp được sử dụng là:

A. Thuật toán sắp xếp chọn.

B. Thuật toán sắp xếp chèn.

C. Thuật toán sắp xếp nổi bọt.

Mô tả “Ở mỗi bước lặp, thuật toán tìm kiếm phần tử lớn nhất/ nhỏ nhất trong dãy để đưa về đúng vị trí của nó” là đúng nhất với thuật toán sắp xếp nào sau đây?

A. Thuật toán sắp xếp chèn.

B. Thuật toán sắp xếp chọn.

C. Thuật toán sắp xếp nổi bọt.

D. Các thuật toán ở phương án A, B, C đều không phù hợp.