Sáng kiến kinh nghiệm Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính

THÔNG TIN CHUNG VỀ SÁNG KIẾN
1. Tên sáng kiến: 
 Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính.
2. Lĩnh vực áp dụng sáng kiến: 
 Áp dụng trong giảng dạy lập trình môn tin học 11.
3. Thời gian áp dụng sáng kiến: 
 Từ ngày 20, tháng 09, năm 2014 đến ngày 20, tháng 4, năm 2016.
4. Tác giả: 
 Họ và tên: Nguyễn Thị Phương Ngân.
 Năm sinh: 1986.
 Nơi thường trú: Khu Tập thể giáo viên trường THPT Mỹ Tho.
 Trình độ chuyên môn: cử nhân sư phạm tin học.
 Chức vụ công tác: Giáo viên dạy môn Tin học.
 Nơi làm việc: Trường THPT Mỹ Tho.
 Điện thoại: 0975061791.
5. Đơn vị áp dụng sáng kiến:
 Tên đơn vị: Trường THPT Mỹ Tho.
 Địa chỉ: xã Yên Chính – Ý Yên – Nam Định.
MỤC LỤC
	 Trang
Đề tài: Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính.
I. Điều kiện, hoàn cảnh tạo ra sáng kiến
 Hiện nay trên thế giới, tin học ngày càng phát triển mạnh mẽ, có ứng dụng rộng rãi trong hầu hết các lĩnh vực của xã hội, sự phát triển của tin học được tính bằng giờ, cứ mỗi giờ lại có thêm phiên bản phần mềm tin học được nâng cấp hay có những phần mềm mới được tạo ra. Ở Việt Nam cũng vậy, tin học có mặt trợ giúp trong mọi ngành nghề, ở khắp mọi nơi, từ thành thị đến nông thôn và phổ biến với tất cả mọi người từ người già đến trẻ, từ những công - nhân viên đến những người nông dân đều rất cần đến sự trợ giúp của tin học. Ngày nay, tin học đã trở thành một phần không thể thiếu trong cuộc sống của mỗi chúng ta.
 Lịch sử phát triển xã hội loài người đang ở nền văn minh thứ ba. Sự hình thành và phát triển của mỗi nền văn minh gắn liền với một công cụ lao động mới, chẳng hạn như máy hơi nước – đối với nền văn minh công nghiệp, máy tính điện tử - đối với nền văn minh thông tin. Máy tính chính là công cụ trợ giúp cho sự phát triển Tin học, có thể đáp ứng nhu cầu tính toán, lưu trữ, tìm kiếm,.., và xử lý thông tin một cách có hiệu quả.
 Máy tính có tốc độ xử lý nhanh (hàng tỉ lệnh trên 1 giây) nhưng nó cũng có giới hạn. Tất cả các máy tìm kiếm (ví dụ như google, yahoo hay gmail) đều được lập trình bằng các đoạn lệnh của một Ngôn ngữ lập trình nào đó nhưng máy nào sử dụng thuật toán tối ưu (tốt nhất ) thì tìm kiếm được nhanh, chính xác và sẽ được đông đảo người dùng lựa chọn sử dụng.
 Với một bài toán cũng vậy, một bài toán có thể có nhiều thuật toán để giải nhưng ta nên lựa chọn thuật toán tối ưu (có số phép tính ít nhất). Vậy việc lựa chọn một thuật toán đưa tới kết quả nhanh là một đòi hỏi thực tế cần được quan tâm đặc biệt. Do đó, trong khi viết chương trình ta nên tìm cách viết sao cho chương trình thực hiện càng ít phép toán càng tốt. Xuất phát từ thực tế đó tôi đưa ra đề tài: “Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính” nhằm định hướng cho các em học sinh biết phân tích, lựa chọn thuật toán tối ưu trước khi lập trình giải bài toán trên máy tính.
II. Mô tả giải pháp
1. Thực trạng
 Nhận thấy tầm quan trọng của Tin học đối với thực tế cuộc sống, mọi lĩnh vực, ngành nghề, từ năm học 2007- 2008 Bộ giáo dục và đào tạo đã đưa môn Tin học thành môn học chính thức ở tất cả các trường Trung học cơ sở, Trung học phổ thông. Mỗi khối lớp được biên soạn chương trình từ cơ bản đến cụ thể từng vấn đề nhằm giúp học sinh có sự hiểu biết về Tin học, có sự tư duy, logic giữa Tin học với các môn học khác, từ đó giúp các em vận dụng vào thực tế. 
 Trong chương trình Tin học 11 đi sâu vào dạy học lập trình, các em học sinh đã hiểu được những khái niệm cơ sở, kiến thức về lập trình, đã có thể vận dụng kiến thức để lập trình giải các bài toán trên máy tính. Tuy nhiên các em lập trình còn mang tính chất cảm tính, lập trình sao cho chương trình chạy được chứ chưa biết phân tích, lựa chọn thuật toán tối ưu để giải quyết bài toán. Trước thực tế đó tôi đưa ra đề tài: “Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính” nhằm định hướng cho các em biết thuật toán tối ưu là gì, vì sao phải lựa chọn thuật toán tối ưu, để từ đó các em biết phân tích, lựa chọn thuật toán trước khi lập trình giải bài toán trên máy tính.
2. Các giải pháp trọng tâm
2.1. Mục đích, yêu cầu
- Đề tài này đi sâu vào mục đích trao đổi cùng đồng nghiệp, các thầy cô giáo vai trò của việc lựa chọn được thuật toán tối ưu.
- Giúp các em học sinh nhớ lại quy trình khi lập trình giải một bài toán trên máy tính, đặc biệt là bước lựa chọn thuật toán giải bài toán rất quan trọng.
- Giúp các em học sinh hiểu được thuật toán ở đây là cái gì và vì sao nên lựa chọn thuật toán tối ưu để giải bài toán, từ đó đứng trước một bài toán học sinh biết nhận xét, phân tích các trường hợp để đề xuất, lựa chọn thuật toán tối ưu giải bài toán sao cho chương trình chạy nhanh hơn.
- Thông qua một số thuật toán cơ bản (như sắp xếp, tìm kiếm,) học sinh biết vận dụng để có thể giải quyết những bài toán phức tạp hơn.
2.2. Nội dung
2.2.1. Nhắc lại các bước lập trình giải bài toán trên máy tính 
 Thông thường khi lập trình giải bài toán trên máy tính học sinh hay bị mắc sai lầm là viết chương trình luôn mà bỏ qua các bước giải bài toán trên máy tính, vì vậy có khi chương trình đã chạy nhưng sai kết quả vì hiểu sai đề, hoặc thuật toán chưa khả thi
 Vì vậy khi dạy lập trình giáo viên nhắc học sinh không nên ngay lập tức viết chương trình mà nên nhớ lại các bước giải bài toán trên máy tính. Việc giải bài toán trên máy tính thường được tiến hành qua 5 bước sau:
+ Bước 1: Xác định bài toán;
+ Bước 2: Lựa chọn hoặc thiết kế thuật toán;
+ Bước 3: Viết chương trình;
+ Bước 4: Hiệu chỉnh;
+ Bước 5: Viết tài liệu.
 Trong 5 bước giải bài toán trên máy tính thì bước lựa chọn hoặc thiết kế thuật toán đặc biệt rất quan trọng để các em có thể phân tích đề bài, tìm ra hướng giải, thuật toán phù hợp.
2.2.2. Một số khái niệm
2.2.2.1. Khái niệm thuật toán
2.2.2.1.1. Thuật toán là gì
 Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy từ Input của bài toán, ta nhận được Output cần tìm.
2.2.2.1.2. Các tính chất của thuật toán
 - Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.
 - Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo.
 - Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.
2.2.2.1.3. Vì sao phải lựa chọn thuật toán tối ưu
a. Vì sao phải lựa chọn thuật toán tối ưu
 Sau khi đã xây dựng được một thuật toán và một chương trình tương ứng, mặc dù đã được cài đặt theo một thuật toán đúng và đáp ứng được các tính chất của thuật toán nhưng có thể không cho kết quả mong muốn đối với một bộ dữ liệu nào đó vì hoặc là nó đòi hỏi quá nhiều thời gian, hoặc là không có đủ bộ nhớ để lưu giữ dữ liệu và các biến của chương trình. Vì vậy ta cần phân tích thuật toán để đưa ra thuật toán tối ưu.
b. Căn cứ vào đâu để xác định thuật toán là tối ưu
 Với một bài toán, không chỉ có một thuật toán, vậy căn cứ vào đâu để có thể nói được thuật toán này nhanh hơn thuật toán kia? Ta có thể căn cứ vào thời gian và bộ nhớ cần thiết để thực hiện thuật toán. Trong đề tài này ta sẽ quan tâm đến thời gian thực hiện thuật toán. Việc đánh giá thời gian thực hiện của thuật toán dẫn tới một khái niệm “độ phức tạp về thời gian của thuật toán” đã được chứng minh và thường được gọi tắt là độ phức tạp của thuật toán, kí hiệu là O(..). Độ phức tạp của thuật toán càng nhỏ thì thuật toán càng chạy nhanh và khả thi.
 Thời gian thực hiện một thuật toán phụ thuộc vào rất nhiều yếu tố như: kích thước của dữ liệu đưa vào, lựa chọn, bố trí kiểu dữ liệu có hợp lý không 
 Vậy để tính toán thời gian thực hiện thuật toán ta sẽ đếm số câu lệnh mà nó thực hiện, hoặc trong một số trường hợp có thể đếm cụ thể phép tính số học, so sánh, gánmà thuật toán đòi hỏi thực hiện hoặc có thể chạy trực tiếp chương trình bằng một ngôn ngữ lập trình cụ thể và thử nghiệm nó nhờ một số bộ dữ liệu nào đấy rồi so sánh kết quả thử nghiệm với kết quả mà ta đã biết. 
c. Ngôn ngữ thuật toán
 - Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán.
 - Thuật toán thường được mô tả bằng một dãy các lệnh. Bộ xử lý sẽ thực hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì kết thúc.
 - Ngôn ngữ thuật toán bao gồm:
 + Ngôn ngữ liệt kê từng bước;
 + Sơ đồ khối;
 + Ngôn ngữ lập trình 
 - Trong đề tài này tôi ưu tiên sử dụng ngôn ngữ liệt kê từng bước và ngôn ngữ lập trình Pascal.
2.2.3. Một số thuật toán cơ bản thường dùng
2.2.3.1. Thuật toán sắp xếp
2.2.3.1.1. Bài toán
 * Bài toán: Cho số nguyên dương N và dãy A gồm N số nguyên: a1, a2,, aN. Sắp xếp dãy A thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau).
 * Ví dụ: Cho N=6, dãy A: 3 2 1 4 6 3
 => Dãy sau khi sắp xếp: 1 2 3 3 4 6
2.2.3.1.2. Thuật toán
 Trong quá trình học tập và giảng dạy tôi đã được học và biết có rất nhiều phương pháp sắp xếp (chẳng hạn như sắp xếp kiểu lựa chọn, sắp xếp kiểu thêm dần, sắp xếp kiểu phân đoạn, sắp xếp kiểu vun đống, sắp xếp kiểu hòa nhập hai đường trực tiếp, sắp xếp tuần tự, tráo đổi, sắp xếp nhanh Quick sort). Tuy nhiên trong chương trình tin học phổ thông tôi ưu tiên sử dụng phương pháp sắp xếp bằng tráo đổi và sắp xếp nhanh Quick-sort. Tôi nhận thấy: phương pháp sắp xếp bằng tráo đổi đơn giản dễ hiểu với học sinh, số lượng phép tính toán, chi phí thời gian thực hiện cũng không quá cao, tuy nhiên nếu tập dữ liệu đưa vào lớn thì phương pháp này bộc lộ hạn chế; còn phương pháp sắp xếp nhanh Quick sort thì quả là một thuật toán sắp xếp tuyệt vời, có chi phí thời gian thấp.
 Trong đề tài này tôi đưa ra hai thuật toán sắp xếp đó là: sắp xếp bằng tráo đổi và sắp xếp nhanh Quick sort để độc giả có sự so sánh và sử dụng linh hoạt trong trường hợp cụ thể.
2.2.3.1.2.1. Thuật toán sắp xếp bằng tráo đổi 
 * Ý tưởng phương pháp: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó đư