Báo cáo Giải pháp Chuyển giao nhiệm vụ cho học sinh khi phân tích độ tối ưu của thuật toán nhằm nâng cao chất lượng bồi dưỡng HSG

Nội dung tài liệu: Báo cáo Giải pháp Chuyển giao nhiệm vụ cho học sinh khi phân tích độ tối ưu của thuật toán nhằm nâng cao chất lượng bồi dưỡng HSG

1. 2. Những đóng góp mới của đề tài (hiệu quả): - Tuy có rất nhiều tài liệu hay viết về phân tích độ tối ưu của thuật toán nhưng một lần nữa tôi nhấn mạnh việc giao nhiệm vụ cho học sinh tìm hiểu, trình bày, thảo luận cùng giáo viên và các bạn đã tạo động lực, hứng thú và nhất là khắc sâu kiến thức một cách tự nhiên đối với học sinh. - Thay đổi được cách dạy học truyền thống từ dạy học trang bị kiến thức sang dạy học hình thành phát triển phẩm chất và năng lực theo hướng tiếp cận chương trình GDPT mới - Tất cả các bài toán đều được xây dựng trên các Sub từ dễ đến khó để làm nổi bật được độ tối ưu của từng thuật toán. - Đề tài đã tổng hợp được một số bài tập đáp ứng hiệu quả cho việc giảng dạy lập trình có hiệu quả. - Đề tài đã được đồng nghiệp trong tổ chuyên môn sử dụng làm tài liệu bồi dưỡng HSG, góp phần vào nhiều kỳ thi HSG Tỉnh lớp10, 11, 12 các năm và mang lại kết quả tương đối trong các kỳ thi HSG. 3. Nội dung đề tài 3.1. Nêu khái niệm “độ phức tạp của thuật toán” GV đặt ra yêu cầu nhóm 1 tìm hiểu và trình bày khái niệm độ phức tạp của thuật toán (Big O) và một số ví dụ minh họa Nhóm 1: “Độ phức tạp của thuật toán” là thuật ngữ thường dùng để chỉ khoảng thời gian tiêu hao để chạy một thuật toán. Các lập trình viên thường sử dụng Big O như một phương tiện để so sánh mức độ hiệu quả của nhiều cách xử lý khác nhau cho cùng một vấn đề. Khái niệm Big O có thể đúc kết thành một câu ngắn gọn như sau: Thời gian chạy nhanh như thế nào, còn tùy thuộc vào giá trị đầu vào -input, vì giá trị input sẽ lớn dần lên khi chương trình chạy. Nghe có vẻ lý thuyết quá phải không? Nhưng thực sự đây là một khái niệm rất thú vị, và bạn không cần quan tâm đến những cách tiếp cận quá chuyên sâu như với các khái niệm phương trình toán học ở bậc phổ thông. Chỉ hiểu khái niệm Big O một cách đơn giản như sau: - 2 -
2. • Thời gian chạy nhanh như thế nào – Sẽ rất khó để xác định chính xác được thời gian chạy của một thuật toán. Vì mỗi máy tính với cấu hình khác nhau sẽ cho ra một kết quả khác nhau tùy thuộc vào CPU, bộ nhớ của máy. Nên, thay vì đặt câu hỏi “thời gian tiêu hao chính xác là bao nhiêu?”, ta nên sử dụng Big O để tiếp cận vấn đề theo hướng “Thời gian chạy nhanh như thế nào?”. • Còn tùy thuộc vào giá trị input. Nếu đo một thuật toán chạy chính xác mất bao nhiêu thời gian, bạn có thể đo bằng các đơn vị thời gian cụ thể như giây hoạc mili giây, nhưng với Big O, ta sẽ sử dụng đơn vị đo input - ở đây gọi là “n”. Vì vậy các lập trình viên thường lấy đơn vị dựa trên độ phức tạp của thuật toán với input là “n” để tính thời gian chạy chương trình. • Vì giá trị input sẽ lớn dần lên khi chương trình chạy. Khi bắt đầu chạy chương trình mọi người thường nghĩ sẽ thật tốn công sức nếu người viết một thuật toán phức tạp để xử lý giá trị đầu vào nhỏ, nhưng qua từng bước của thuật toán đó, giá trị ban đầu vốn nhỏ lại dần trở nên lớn hơn thì mọi chuyện lại hoàn toàn khác, chẳng ai còn quan tâm đến độ phức tạp của thuật toán đó nữa. Với phép phân tích Big O, lập trình viên chỉ quan tâm đến yếu tố khác bị tiêu hao (thời gian, dung lượng lưu trữ) khi giá trị đầu vào lớn dần. Đấy chính là lý do mà “phép phân tích Big O” đôi khi còn được gọi là “phép tính tiệm cận” • O(f(n)), hàm f(n) càng nhỏ thì càng tốt, với n là input đầu vào Vậy: ✓ O(1) – Độ phức tạp nhỏ nhất là các phép toán +, -, *, /, %, div, mod ✓ int a=5; //O(1) ✓ int b=a+4; //O(1) ✓ int c= a*b +2022; //O((1) ✓ int n; cin >> n; //O(1) ✓ Trường hợp 1: Nếu thao tác trong vòng for nó có độ phức tạp là O(1) Ví dụ: cout << i ≤ endl thì khi đó vòng for với int với đầu vào là n thì nó lặp n lần thì dẫn đến độ phức tạp là O(n) nhưng phải đảm bảo được rằng các thao tác trong vòng for cont << - 3 -
3. i ≪ endl nó có độ phức tạp O(1) và khi đó nó nhận với độ phức tạp với vòng for ngoài O(n). Tức O(n) * O(1) = O(n) Nhận thấy trong hàm duyệt từ 1 đến n mà trong đó hàm nằm trong vòng for nên độ phức tạp không phải là O(n) nữa vì khi đó số thao tác trong hàm for checkNT này có độ phức tạp là O (log(n)) ( 푛). Với n là Iput đầu vào mà vòng for duyệt từ 2  푛 thì nó là O( 푛) có nghĩa là nó có 푛 vòng lặp. Mà ( 푛) → O(log(n))  n vòng lặp * ( logn)  O ( n * logn) Vậy độ phức tạp trên sẽ là O( n * logn) ✓ Xét 2 vòng For lồng nhau: For (int i = 1; i ≤ n; i ++) For ( int j= 1; j ≤ m; j ++) { // } } Một vòng For duyệt từ 1 n, một vòng for trong duyệt từ 1 m vậy độ phức tạp là của số lần lặp vòng For ngoài * với số lần lặp vòng For trong ( n*m)  O(n*m)  O(n^2) Ví dụ: // O (5*10) với n=5, m=10 int main() { for (int i=1; i<=5;i++) for (int j=1;j<=10; j++) cout << "Hello world!" << endl; return 0; } Sẽ đưa ra màn hình 50 lần Hello world! - 4 -
4. ✓ Xét 3 vòng lặp lồng nhau thì độ phức tạp O (n*m*k) Ví dụ: int main() { for (int i=1; i<=5;i++) for (int j=1;j<=10; j++) for (int k=1;k<=20; k++) cout << "Hello world!" << endl; return 0; }  O ( n^3 ) độ phức tạp này thì rất tệ rồi và ta nên tránh. Xin chân thành cảm ơn cô và cả lớp đã lắng nghe! 3.2. Một số ví dụ làm nổi bật ”. Độ Phức Tạp Của Thuật Toán Và Lựa Chọn Cách Giải Thuật GV đặt câu hỏi tạo tình huống: Tại sao thời gian lại quan trọng? Nhóm 2 chuẩn bị và trình bày sản phẩm của nhóm: Trong một số chương trình, sản phẩm phần mềm nếu xử lí quá chậm sẽ gây khó chịu cho người dùng ứng dụng. Ví dụ 1: Bạn mua hàng mà bấm nút tìm kiếm mất 1 phút thì bạn có khó chịu không? Nếu thời gian tìm kiếm của google cho mỗi từ khoá tốn 5 giây thì liệu google có trở thành công cụ tìm kiếm số 1 thế giới hay không? Ví dụ 2: Một mảng có n phần tử. Hãy tìm phần tử lớn nhất trong mảng Bài này tất nhiên chẳng có cách nào khác, bạn sẽ duyệt toàn bộ phần tử trong mảng (duyêt - 5 -
5. qua mảng n lần) để tìm ra phần tử lớn nhất. Độ phức tạp thuật toán ở đây có thể hiểu là O(n) (chạy qua n phần tử để tìm kiếm) Một mảng có n phần tử. Hãy sắp xếp mảng theo thứ tự tăng dần Với bài toán này bạn thường dùng 2 vòng lặp từ i->n và từ j->n để đổi chỗ. Lúc này độ phức tạp thuật toán là O(n^2) Tuy nhiên với 1 số giải thuật sắp xếp như quicksort, độ phức tạp chỉ là O(n*log(n)). Bạn thử thay n=10, thì giải thuật bên trên có thể hiểu sẽ chạy xấp xỉ là 10*10=100 phép tính, nhưng giải thuật Quicksort thì chỉ dùng khoảng 10 phép tính. Với n rất nhỏ, 100 hay 1000 thì chương trình đều chạy có thời gian xấp xỉ bằng nhau. Thật ra kết quả là có chênh, nhưng quá nhỏ nên các bạn không thấy. Nhưng với n cực lớn, ví dụ 100000 phần tử, thì thuật toán có độ phức tạp O(n^2) với O(nlogn) là cực kì khác biệt. Ví dụ 3: Cho một mảng có n phần tử đã sắp xếp. Hãy tìm xem có phần tử x hay không? Bài này nếu các bạn duyệt từ 1 tới n để tìm xem có x hay không, độ phức tạp vẫn là O(n). Tuy nhiên nếu để ý, do mảng này là mảng đã sắp xếp, nên bạn có thể áp dụng thuật toán tìm kiếm nhị phân. Tức là bạn chặt dãy ra làm 2, xem X lớn hay nhỏ hơn phần tử ở giữa, nếu nhỏ hơn thì tìm kiếm ở đoạn dưới, nếu lớn hơn thì tìm kiếm ở đoạn trên. Cứ như vậy bạn chặt dãy ra làm 2 liên tục, thì số phép tìm kiếm sẽ là log2 của n, sẽ nhanh hơn nhiều lần so với giải thuật tìm kiếm tuần tự bên trên. Chọn giải thuật phù hợp Nhóm 2 có tìm hiểu từ nhiều nguồn tài liệu khác nhau ví như: Nhóm 2 trình bày đã kết thúc, xin chân thành cảm ơn cô và cả lớp đã lắng nghe! 4. Giáo viên nhận xét và tổng kết lại toàn bộ nội dung 4.1 . Nhận xét: - Nhóm 1: Hoàn thành phần được giao một cách nghiêm túc. Đã trình bày được tổng quan khái niệm về độ tối ưu của thuật toán và lấy được một số ví dụ minh họa độ phức tạp của thuật toán. Trình bày mạch lạc, rõ rang. - Nhóm 2: Các em đã biết cách tìm kiếm, thu thâp từ nhiều nguồn tài liệu để phân tích thời - 6 -
6. gian chạy của thuật toán, tuy đã đưa ra một số ví dụ nhưng cần đưa ra các thuật toán đó để trình bày chi tiết hơn khi phân tích độ tối ưu của thuật toán. 4.2 . Tổng kết lại toàn bộ nội dung Sau đây là một số bài toán đã được phân tích độ tối ưu của thuật toán được đúc rút trong quá trình ôn luyện: 1. Các công thức toán có các phép +, -, *, /, %, Div, Mod thì nó đều có độ phức tạp: O (1) ✓ int c= a*b +2022; //O((1) ✓ int n; cin >> n; //O(1) 2. Thuật toán tìm kiếm nhị phân nó có độ phức tạp là O(logn) < O(n) int BinarySearch_Recursive(int a[],int x,int left,int right){ if(left>right){ return -1; } int mid=(left+right)/2; if(x==a[mid]){ return mid; } if(x<a[mid]){ return BinarySearch_Recursive(a,x,left,mid-1); } return BinarySearch_Recursive(a,x,mid+1,right); } – Thuật toán binary search tiết kiệm thời gian hơn rất nhiều so với tìm kiếm tuyến tính. – Thuật toán binary search chỉ được áp dụng cho những mảng đã được sắp xếp thứ tự. Thuật toán tìm kiếm tuyến tính áp dụng cho bất kỳ mảng nào cũng được. 3. Các thuật toán set/ map hay hàng đợi rất mạnh ưu tiên có độ phức tạp là O(logn)/ trên mỗi thao tác của nó. Vì vậy các thao tác tìm kiếm, Insert, Delete, ta hay dùng set nó chỉ mất O (logn). - 7 -
7. 4. Phân tích thừa số nguyên tố thì độ phức tạp là O ( 푛 ) hay là O (logn) void phantich(int a, int &x) { int i = 2; while (i*i <= a) { while (a % i == 0) { a /= i; p[i]++; } i++; } 5. Đọc n phần tử từ Iput  O(n) Ví dụ: - Đọc vào input của mảng A gồm n phần tử - Duyệt từ 0 n - Hay in một mảng có n phần tử - Duyệt các phần tử trong mảng Thì tất cả đều có độ phức tạp là O(n) int main(){ //O(n) int n; cin >> n; int a[n]; //O(n) for (int i=0; i<=5;i++){ cin >> a[i]; } //O(n) for (int i=0; i<=5;i++){ cout << a[i] << " "; } } - 8 -
8. ❖ Chú ý: Muốn độ phức tạp chỉ là O (n) thì thao tác trong vòng For phải có độ phức tạp là O(1) 6. Với độ phức tạp là O(nlogn) ví dụ hàm kiểm tra số nguyên tố //O(longn) bool nt(int n){ for (int i=2; i<=sqrt(n);i++){ if (n%i==0) return false; } return n>1; } //O(n*longn) int main(){ for (int i=1; i<=n;i++){ if (nt(i)) cout << i << endl; } } 7. Duyệt tất cả các tập hợp k của mảng gồm n phần tử nó tương đương với k vòng for lồng nhau thì độ phức tạp là  O (nk) 8. Duyệt tất cả các tập con của tập gồm n phần tử: O(2n) 9. Duyệt tất cả các hoán vị của tập n phần tử: O(n!) 10. Độ phức tạp của chương trình sẽ là độ phức tạp của đoạn có độ phức tạp lớn nhất. Ví dụ: Đoạn 1 có độ phức tạp là O(n) Đoạn 2 có độ phức tạp là O (n*n)  O (n12) Đoạn 3 có độ phức tạp là O ( log n) - 9 -
9. Thì độ phức tạp của chương trình sẽ là O (n^2) Hoặc O(n2+2+1+n3 + n2log n)  O(n3) Trường hợp : O (n2+n2 )= O (2n2) = O (n2) - Có những bài toán độ phức tạp lớn lên đến 2n hoặc n! sinh ra tất cả các hoán vị, sinh ra các tập con của tập n phần tử. Thì tùy vào Input ntrong một chương trình ta có thể lựa chọn các thuật toán khác nhau, n lớn thì ta chọn thuật toán có độ phức tạp bé, n bé thì ta chọn độ phức tạp lớn cũng được. - Thông thường số thao tác của thuật toán rơi vào 106 thì thời gian chạy hết 1s. Vậy vòng For mà chạy quá lâu lên đến 109, 1016, 1012 thì sẽ bị time out. - Nên phải biết một số thao tác mà độ phức tạp như thế nào. Biết cách lựa chọn thuật toán nào để độ phức tạp nhỏ nhất có thể. Sau đây là bảng liệt kê các độ phức tạp của thuật toán có thể chấp nhận được với n là Input đầu vào: Với n là Input Các độ phức tạp của thuật toán có thể chấp nhận được n ≤ 10 O(n!), O(n7), O(n6) n ≤ 20 O(2n.n), 0 (n5) n ≤ 80 O(n4) n ≤ 400 O(n3) n ≤ 7500 O(n2) n ≤ 5.104 O (n 푛) n ≤ 5.105 O(nlogn) n ≤ 5.106 O(n) n ≤ 1018 O(log2n), O(logn), O(1) ❖ Vậy: - Với n càng nhỏ thì ta có thể sử dụng độ phức tạp lớn; - Với n càng lớn thì ta phải tối ưu thuật toán càng nhỏ càng tốt. - 10 -
10. Xét một số bài toán cụ thể: Bài toán 1: Tính tổng các số nguyên từ 1 n Với các bạn dùng vòng lặp từ 1 n để tính tổng, độ phức tạp sẽ là O(n). Với n bằng 1 tỷ, tương đương bạn phải thực hiện 1 tỷ lần phép toán cộng. Trong khi đó nếu dùng công thức thì chỉ cần một dòng là ra: n*(n+1)/2. Giải thuật này có độ phức tạp là O(1) chỉ 1 phép toán duy nhất. Bài toán 2: Tính tổng tất cả các số 0 999 chia hết cho 3 hoặc 5 Học sinh nào cũng nghĩ ngay tới đoạn code: int s, i = 0; while (i<1000){ if (i % 3 == 0 || i % 5 == 0){ s += i; } i++; } } Cách này không tối ưu vì độ phức tạp là O(n) Với đoạn code này máy tính sẽ phải thực hiện 1000 vòng lặp và hàng trăm phép tính (tương ứng với mỗi vòng lặp đúng điều kiện) Đoạn code tối ưu là: int sum(int n){ int target = 999; int p = target/n; return n*(p*(p+1))/2; } Độ phức tạp ở đây là O(1). Với đoạn code hai này thì máy chỉ cần tính vài biểu thức đơn giản. Vậy ta biết cái nào tối ưu hơn rồi. Bài toán 3: Tìm ước chung lớn nhất của 2 số a, b UCLN(a,b)? - 11 -
11. a Nếu a = b Sub 1: UCLN(a,b) = UCLN(a ― b,b)Nếu a > b UCLN(b ― a,b)Nếu b > a Đoạn code : #include #include int ucln(int a, int b){ // Nếu a = 0 => ucln(a,b) = b // Nếu b = 0 => ucln(a,b) = a if (a == 0 || b == 0){ return a + b; } while (a != b){ if (a > b){ a -= b; // a = a - b }else{ b -= a; } } return a; } a nếu b = 0; Sub 2 : Theo Euclid: UCLN(a,b) = UCLN(b, a%b) nếu b > 0; Đoạn code: int ucln(int a, int b) { int tmp; while(b != 0) { tmp = a % b; a = b; b = tmp; } return a; - 12 -