Hướng dẫn giải nhanh Tin học 11 định hướng Khoa học máy tính Cánh diều bài 5: Đánh giá thuật toán

KHỞI ĐỘNG

Câu hỏi: Theo em, một thuật toán như thế nào thì được xem là chạy nhanh/chạy chậm?

Hướng dẫn trả lời:

Một thuật toán được xem là có hiệu suất tốt hơn khi nó đòi hỏi ít thời gian để thực hiện và sử dụng ít bộ nhớ hơn.

LUYỆN TẬP

Câu 1: Em hãy cho ví dụ một lời gọi hàm được tính là phép toán sơ cấp và một lời gọi hàm không được tính là phép toán sơ cấp.

Hướng dẫn trả lời:

Ví dụ lời gọi hàm được tính là phép toán sơ cấp:

int number = 1990;

if ((number % 2) == 0)

    Console.WriteLine($"{number} là số chẵn");

// In ra: 1990 là số chẵn

int a = 5;

int b = 10;

if (a >= b)

{

    Console.WriteLine("Số a lớn hơn hoặc bằng số b");

}

else

{

    Console.WriteLine("Số a nhỏ hơn số b");

}

//In ra: Số a nhỏ hơn số b

Sau lệnh "else," bạn có thể tiếp tục với một lệnh "if" khác để tạo một cấu trúc "if-else" để kiểm tra nhiều tình huống.

int a = 10;

int b = 10;

if (a > b)

{

    Console.WriteLine("Số a lớn hơn hoặc bằng số b");

}

else if (a < b)

{

    Console.WriteLine("Số a nhỏ hơn số b");

}

else

{

    Console.WriteLine("Hai số a, b bằng nhau");

}

VẬN DỤNG

Câu 1: Xét bài toán sắp xếp dãy số. Hãy cho biết khi nào ta có trường hợp thuận lợi nhất, số phép toán cần làm là ít nhất?

Hướng dẫn trả lời:

Trong vấn đề của việc sắp xếp dãy số, mục tiêu là sắp xếp các số trong dãy theo thứ tự tăng hoặc giảm dần. Để tối ưu hóa quá trình sắp xếp và giảm số lần so sánh cũng như hoán vị giữa các phần tử, việc lựa chọn phương pháp sắp xếp là quan trọng. Tình huống tốt nhất trong bài toán sắp xếp dãy số xảy ra khi dãy đã có sẵn thứ tự tăng hoặc giảm dần. Trong tình huống này, việc không cần phải hoán vị các phần tử trong quá trình sắp xếp dẫn đến số lượng phép toán ít nhất.

Ngược lại, khi dãy số ban đầu là không có thứ tự, ta cần phải thực hiện một loạt hoán vị để đạt được thứ tự mong muốn. Trong trường hợp này, số lượng phép toán sẽ tăng lên so với trường hợp dãy đã có thứ tự. Vì vậy, để tối ưu hóa quá trình và giảm số lượng phép toán, việc sắp xếp dãy số theo thứ tự tăng hoặc giảm dần trước khi tiến hành các phép toán sắp xếp khác là lựa chọn hợp lý nhất.

Câu 2: Ước lượng số phép toán sơ cấp cần thực hiện để tìm số lớn nhất trong dãy số:

a) Đầu vào là dãy ngẫu nhiên.

b) Đầu vào là dãy giảm dần.

Hướng dẫn trả lời:

a) Đầu vào là dãy ngẫu nhiên: Để tìm số lớn nhất trong dãy số ngẫu nhiên, chúng ta cần so sánh từng cặp số với nhau và lựa chọn số lớn hơn. Với dãy có n phần tử, chúng ta sẽ cần thực hiện khoảng n - 1 phép so sánh để tìm được số lớn nhất. Do đó, ước lượng số phép toán sơ cấp là khoảng (n - 1).

b) Đầu vào là dãy giảm dần: Trong trường hợp dãy đã được sắp xếp giảm dần, số lớn nhất sẽ là phần tử đầu tiên của dãy. Chúng ta chỉ cần thực hiện một phép so sánh để tìm số lớn nhất. Do đó, ước lượng số phép toán sơ cấp là 1.

CÂU HỎI TỰ KIỂM TRA

Câu 1: Tại sao không thể đánh giá thuật toán qua chương trình cài đặt thuật toán?

Hướng dẫn trả lời:

Việc đánh giá một thuật toán không thể hoàn chỉnh chỉ bằng cách xem xét chương trình cài đặt của nó, vì việc đánh giá thuật toán yêu cầu xem xét nhiều khía cạnh khác nhau. Chương trình cài đặt thuật toán chỉ là một phần của quá trình triển khai thuật toán, nhưng để đánh giá thuật toán, chúng ta cần xem xét các khía cạnh khác như hiệu suất, tốc độ, độ chính xác, sử dụng bộ nhớ, độ phức tạp tính toán, và sự ổn định của thuật toán trong các tình huống khác nhau.

Vì vậy, để đánh giá hiệu suất của một thuật toán, chúng ta cần tiến hành các thí nghiệm và kiểm tra kết quả của thuật toán trên các tập dữ liệu khác nhau, thay vì chỉ dựa vào chương trình cài đặt. Các thử nghiệm này thường được thiết kế để đánh giá khả năng của thuật toán xử lý các tình huống đa dạng và đo đạc hiệu suất theo các chỉ số khác nhau.

Câu 2: Khi nào thì áp dụng quy tắc lấy max?

Hướng dẫn trả lời:

Trong Python, quy tắc tìm giá trị lớn nhất áp dụng để xác định phần tử có giá trị cao nhất trong một danh sách (list) hoặc tập hợp (set). Nó được sử dụng khi bạn cần tìm giá trị lớn nhất trong một tập dữ liệu cụ thể, ví dụ như tìm giá trị lớn nhất trong danh sách các số hoặc xác định phần tử có giá trị lớn nhất trong một tập hợp.

Quy tắc tìm giá trị lớn nhất rất hữu ích khi bạn đối mặt với việc xử lý các tập dữ liệu lớn và muốn xác định giá trị cao nhất trong tập dữ liệu đó.

Câu 3: Quy tắc nhân áp dụng cho cấu trúc vòng lặp là gì?

Hướng dẫn trả lời:

Quy tắc nhân hóa là một phương pháp tối ưu hóa thường được sử dụng trong lập trình để cải thiện hiệu suất của các vòng lặp. Quy tắc này áp dụng cho cả cấu trúc vòng lặp for và while trong Python. Các quy tắc nhân hóa giảm số lần lặp của vòng lặp bằng cách thay thế vòng lặp bằng một chuỗi các lệnh tương ứng.

Kỹ thuật nhân hóa có khả năng tăng tốc độ thực thi của chương trình bằng cách giảm số lần lặp của vòng lặp, giảm thời gian thực hiện và tối ưu hóa việc sử dụng bộ nhớ. Tuy nhiên, việc áp dụng quy tắc nhân hóa cần phải được thực hiện cẩn thận, vì nó có thể làm cho mã chương trình trở nên khó đọc và khó bảo trì nếu không được thực hiện đúng cách.