Tài liệu Skkn định hướng giảng dạy thuật toán sắp xếp và tìm kiếm trong trường thpt

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN Kính gửi: Hội đồng sáng kiến cấp ngành Chúng tôi ghi tên dưới đây: STT Họ tên Ngày sinh 1 Đặng Minh Hiến 20/3/1975 2 Nguyễn Ngọc Thành 10/6/1982 3 Nguyễn Mạnh Cường 17/7/1984 4 Nguyễn Trung Quyết 22/08/1987 5 Vũ Thị Phương 12/02/1989 Nơi công tác THPT Gia Viễn B THPT Gia Viễn B THPT Gia Viễn B THPT Gia Viễn B THPT Gia Viễn B Chức vụ Trình độ chuyên môn Tỷ lệ (%) đóng góp vào việc tạo ra sáng kiến P. Hiệu trưởng Đại học 20% TPCM Đại học 20% Giáo viên Thạc sĩ 20% Giáo viên Đại học 20% Giáo viên Đại học 20% I. Tên sáng kiến, lĩnh vực áp dụng: - Tên sáng kiến: “Định hướng giảng dạy thuật toán sắp xếp và tìm kiếm trong trường THPT” - Lĩnh vực áp dụng: Giảng dạy bộ môn tin học THPT, ôn luyện đội tuyển học sinh giỏi. II. Nội dung sáng kiến: 1. Giải pháp cũ thường làm: Việc tìm kiếm và sắp xếp thường là một vấn đề khó, trừu tượng đối với mỗi học sinh khi mới bắt đầu tiếp cận tin học và lập trình. Trước đây giáo viên mỗi khi dạy đến phần tìm kiếm và sắp xếp theo cấu trúc thường cũng không hiểu sâu vấn đề, dạy không rõ ràng, chiếu lệ, ví dụ áp dụng nghèo nàn không phong phú. Chủ yếu đưa ra ý tưởng ở dạng tổng quát để học sinh biết được tìm kiếm, sắp xếp là như thế nào. Dẫn đến học sinh mơ hồ, khó hiểu đối với nội dung phần đang học, nội dung môn học. Mặt khác học sinh không chủ động tìm hiểu nội dung theo yêu cầu của giáo viên, nên hoàn toàn bị động đối với môn học. Bằng thực nghiệm với nhiều năm giảng dạy trên lớp và ôn thi học sinh giỏi chúng tôi nhận thấy khi giảng dạy phần sắp xếp và tìm kiếm thường gặp các vấn đề như: Thứ nhất, việc đưa thuật tìm kiếm và sắp xếp chưa phù hợp. Khi học thuật toán là vào học kỳ I lớp 10 (Bài 4. Bài toán và thuật toán) thì đến HKII lớp 11 (bài 11. Kiểu mảng) học sinh mới có bài tập để vận dụng, để tiếp cận thì học 1 sinh lại phải lật lại kiến thức về thuật toán đã học lớp 10 - những kiến thức học sinh đã học khá lâu mà không phải học sinh nào cũng nhớ được, chính việc này làm vấn đề có thể phức tạp lên và học sinh sẽ trở nên thụ động tiếp thu thông qua những gì giáo viên truyền đạt, không phát huy được tính chủ động, tích cực của mình. Trong các đợt ôn thi cho đội tuyển học sinh giỏi thì gần như giáo viên phải truyền đạt lại từ đầu, dẫn đến mất thời gian và hiệu quả đạt được thì không cao. Thứ hai, chưa xây dựng cụ thể hệ thống các ví dụ minh họa vận dụng và bài tập phù hợp với tiến trình phát triển tư duy cho học sinh để học sinh có thể hiểu rõ về tìm kiếm và sắp xếp. Ngoài ví dụ mẫu trong sách giáo khoa ra thì không có thêm các ví dụ áp dụng cụ thể và nếu có thì học sinh cũng rất khó thực hiện và ghi nhớ vì chỉ dừng lại ở các bài toán biểu diễn dưới dạng liệt kê hoặc sơ đồ khối chứ chưa thực hiện việc viết chương trình. Điều này dẫn đến học sinh học thụ động, không hiểu sâu kiến thức, kém linh hoạt khi vận dụng và bài tập cụ thể. Tiến trình lên lớp cũ khi dạy về thuật toán: - Học sinh xác định bài toán - Giáo viên nêu ý tưởng - Giáo viên đưa ra thuật toán bằng liệt kê hoặc sơ đồi khối - Giáo viên mô phỏng ví dụ Thứ ba, phần mô phỏng thuật toán để học sinh tiếp cận thuật toán một cách nhanh nhất thường ít được quan tâm và sử dụng. Trong tin học lớp 10 có đưa ra việc mô phòng, tuy nhiên phần diễn đạt chưa sâu và đơn giản dẫn đến học sinh khó thể hiểu hết được quá trình thực hiện thuật toán. Việc đi sâu vào biểu diễn thuật toán bằng sơ đồ khối hoặc liệt kê làm học sinh khó hiểu và nhàm chán. Thứ tư, không có nội dung để học sinh tham gia trong quá trình tìm hiểu thuật toán, làm mất đi tính chủ động của học sinh khi học thuật toán. Thường thì giáo viên trình bày thuyết trình học sinh nghe giảng tiếp thu. 2. Giải pháp mới cải tiến: Hiểu rõ các tồn tại của cách thức giảng dạy nói trên, nhóm chúng tôi đưa ra việc xây dựng tài liệu tìm hiểu về sắp xếp và tìm kiếm với cách thức tiếp cận hoàn toàn mới nhằm khắc phục những tồn tại này, đó là: - Xây dựng kế hoạch dạy học nhà trường cho phù hợp với nội dung giảng dạy. Đưa nội dung của các thuật toán trong đó có thuật toán sắp xếp, tìm kiếm trong bài 4 tin học 10 vào nội dung giảng dạy trong tin học 11. - Đưa ra nhiều thuật toán sắp xếp, tìm kiếm khác nhau khi ôn học sinh giỏi. Mục đích ngoài để giải quyết các bài toán thì học sinh cũng được rèn luyện cách thức xử lý các công việc không khác nhau ngoài sắp xếp, rèn luyện được tư duy thuật toán tốt hơn. - Cung cấp cho học sinh đầy đủ kiến thức về các thuật toán tìm kiếm, sắp xếp và bổ sung một số kiến thức nâng cao. Sau mỗi thuật toán có đưa ra đánh giá nhận xét đầy đủ để học sinh có cách nhìn tổng quan về thuật toán đang sử dụng. - Các ví dụ minh họa và bài tập được trình bày chi tiết, được sắp xếp một 2 cách hợp lý, từ dễ đến khó, bài toán sau có liên hệ với bài toán trước. Đặc biệt đưa các dạng câu hỏi trắc nghiệm vào giảng dạy để luyện tập cũng như nâng cao khả năng tư duy nhanh khi tiếp cận thuật toán. - Sử dụng những kiến thức cũ để tiếp cận kiến thức mới thông qua hệ thống các bài tập, có thể sử dụng kết quả của bài toán này cho bài toán kia. - Tài liệu đề cập đến nhiều dạng kiến thức khác nhau đặc biệt là các bài toán thực tiễn. Việc làm này một mặt củng cố kiến thức cho học sinh. Mặt khác giúp học sinh có cái nhìn chung nhất, thấy được mối liên hệ giữa tin học và thực tiễn cuộc sống. - Tài liệu cung cấp hệ thống bài tập phong phú. Điều này giúp cho học sinh đứng trước mỗi bài toán phải biết phân tích, đánh giá, so sánh và nhận dạng để lựa chọn phương pháp giải phù hợp nhất cho bài toán đó. Rèn luyện cho học sinh tính chủ động, tích cực và kỹ năng vận dụng linh hoạt, sáng tạo kiến thức đã học. Với những cải tiến trên và các kỹ thuật dạy học mới ngày nay thì việc học sinh nghiên cứu tiếp nhận kiến thức thông qua các hệ thống câu hỏi trắc nghiệm hoặc các biểu diễn môn phỏng sẽ trở nên dễ dàng hơn rất nhiều. III. Hiệu quả kinh tế và xã hội 1. Hiệu quả kinh tế Thứ nhất, xét về mặt thời gian. Để biên soạn một chủ đề hoặc một chuyên đề dạy học thì giáo viên sẽ phải mất rất nhiều thời gian tìm kiếm, biên tập lại từ các tài liệu trên internet và các sách tham khảo. Học sinh có nhu cầu tìm kiếm bài tập để luyện thì cũng phải tìm kiếm trong nhiều tài liệu rồi hệ thống lại. Điều này cũng sẽ mất rất nhiều thời gian. Trong khi đó, giáo viên và học sinh có thể sử dụng ngay tài liệu này để học cũng như sử dụng trong việc ôn thi học sinh giỏi. Nếu cần thì giáo viên chỉ cần bổ sung hàng năm để có được tài liệu phong phú về bài tập cho riêng mình. Thứ hai, xét về tài chính. Để viết nên tài liệu này, không kể tài liệu sách giáo khoa (học sinh và giáo viên nào cũng có), giáo viên sẽ mất rất nhiều giờ truy cập internet, và nhiều giờ để nghĩ ra các bài toán. Trong khi với tài liệu này, giáo viên chỉ cần phô tô hoặc in tài liệu này với giá rẻ. Nếu tính về hiệu quả kinh tế sẽ tiết kiệm rất nhiều, vì với tài liệu này ta sẽ còn duy trì trong nhiều năm tiếp theo nữa. 2. Hiệu quả xã hội: Sáng kiến là tài liệu dùng trong việc giảng dạy theo chương trình chuẩn THPT và là tài liệu tham khảo tốt cho học sinh yêu thích với môn học lập trình, sử dụng cho quá trình ôn thi học sinh giỏi. Sáng kiến không chỉ giúp giải quyết cho vấn đề đổi mới phương pháp dạy học theo hướng tích cực chủ động khi giảng dạy cho học sinh về tìm kiếm và sắp xếp nói riêng mà nó còn mở ra hướng đổi mới cho việc nghiên cứu các chuyên đề khác để xử lý các nội dung khó của tin học 11. IV. Điều kiện và khả năng áp dụng Để áp dụng được sáng kiến này thì mỗi nhà trường cần xây dựng một kế hoạch dạy học hợp lý, phù hợp với đối tượng học sinh mà mình giảng dạy. 3 Qua thực nghiệm và tiến hành áp dụng trong các năm học đã qua, tài liệu rất hữu ích trong công tác giảng dạy của giáo viên, đặc biệt là việc ôn luyện thi học sinh giỏi. Đồng thời, nâng cao chất lượng giảng dạy và học tập bộ môn tin học 11, tạo được hứng thú học tập và góp phần bồi dưỡng năng lực tự học cho học sinh. Vì vậy, sáng kiến có thể áp dụng rộng rãi trong nhà trường nói riêng và toàn tỉnh nói chung. Tài liệu này được các đồng nghiệp trong nhà trường đánh giá cao về chất lượng nội dung và phương pháp dạy học. Chúng tôi xin cam đoan mọi thông tin nêu trong đơn là trung thực, đúng sự thật và hoàn toàn chịu trách nhiệm trước pháp luật. Gia Viễn, ngày 19 tháng 05 năm 2019 XÁC NHẬN CỦA LÃNH ĐẠO Người nộp đơn ĐƠN VỊ CƠ SỞ (Ký và ghi rõ họ tên) 4 PHỤ LỤC PHẦN I – ĐẶT VẤN ĐỀ 1. Lí do chọn sáng kiến Trong những năm gần đây vấn đề đổi mới căn bản và toàn diện nền giáo dục đã trở thành một vấn đề không chỉ riêng ngành giáo dục mà toàn xã hội quan tâm, đổi mới để đáp ứng với nhu cầu thực tiễn xã hội ngày nay. Một trong những sự thay đổi đó là thay đổi phương pháp dạy học từ phương pháp dạy học truyền thống sang phương pháp dạy học tích cực, từ người giáo viên là trung tâm của mọi hoạt động thì giờ đây với phương pháp dạy học tích cực học sinh trở thành trung tâm của các hoạt động, từ tiếp thu thụ động sang chủ động, tư duy, sáng tạo; giáo viên chỉ là người định hướng và hỗ trợ. Đây là một phương pháp đã được áp dụng rất thành công ở rất nhiều nước tiên tiến trên thế giới. Để làm được điều này người thầy cần phải thiết kế những bài giảng, những chuyên đề cho phù hợp với nội dung kiến thức; phương pháp, phương tiện dạy học phù hợp với từng đối tượng học sinh là một điều hết sức cấp thiết. Để qua mỗi phần học, tiết học học sinh thích thú với kiến thức mới, qua đó hiểu được kiến thức đã học trên lớp, đồng thời học sinh thấy được tầm quan trọng của vấn đề và việc ứng dụng của kiến thức trước hết để đáp ứng những yêu cầu của môn học, sau đó là việc ứng dụng của nó vào các công việc thực tiễn trong đời sống xã hội. Môn Tin học là một môn học mới mẻ của học sinh THPT, đặc biệt với nội dung tin học 11, với nhiều kiến thức trừu tượng chưa sát thực tế mà đối với học sinh mới được tiếp xúc với môn lập trình sẽ cảm thấy khó tiếp thu, khó hiểu và không làm được các bài tập áp dụng dẫn đến sự chán nản khi học bộ môn. Xuất phát từ thực tiễn giảng dạy tôi thấy rằng, để thay đổi điều này thì cần phải xây dựng lại một số nội dung khó của tin học 11 sao cho phù hợp với đối tượng học sinh và tìm lại sự hứng thú với môn học cho các em học sinh. Xuất phát từ cơ sở trên, tôi đã chọn đề tài “Định hướng giảng dạy thuật toán sắp xếp và tìm kiếm trong trường THPT”, nhằm giúp các em dễ tiếp cận các thuật toán tìm kiếm và sắp xếp hơn, từ đó hiểu rõ được ngữ nghĩa cũng như cách sử dụng các thuật toán này phù hợp với nhiều bài toán khác nhau từ đó tiếp thu tốt nội dung bài học và làm tốt các bài tập áp dụng, cảm thấy yêu thích hơn môn tin học nói chung và nội dung về ngôn ngữ lập trình nói riêng. 2. Mục đích của sáng kiến Ngoài việc giúp cho học sinh tiếp cận dễ dàng với các thuật toán sắp xếp và tìm kiếm thì sáng kiến còn xây dựng hệ thống các dạng bài tập thường gặp để ôn luyện cho học sinh dự thi các kỳ thi học sinh giỏi môn tin học. 3. Phạm vi nghiên cứu Sáng kiến tập trung việc đổi mới trong xây dựng kế hoạch giáo dục phù hợp cũng như nghiên cứu nội dung các thuật toán tìm kiếm và sắp xếp theo 5 chương trình Chuẩn ở trường THPT. Bên cạnh đó cũng đề cập đến một số phần mở rộng cũng như nâng cao của các thuật toán tìm kiếm và sắp xếp dùng trong ôn thi học sinh giỏi. Cùng với đó là hệ thống ví dụ minh họa cũng như bài tập áp dụng với từng thuật toán cụ thể. 4. Phương pháp nghiên cứu a) Nghiên cứu lý luận: Tìm hiểu về các tài liệu đề cập đến các thuật toán tìm kiếm và sắp xếp, b) Nghiên cứu thực tiễn: Tìm hiểu về cách giảng dạy tìm kiếm và sắp xếp mà giáo viên thường làm. Phân tích và làm rõ ưu điểm, nhược điểm của từng cách dạy để từ đó xây dựng nội dung một cách hợp lý nhằm bồi dưỡng năng lực tự học cho học sinh. c) Thực nghiệm sư phạm: Tiến hành thực nghiệm nhằm đánh giá tính khả thi, tính hiệu quả và tính phổ dụng của sáng kiến. Đồng thời, cũng nhằm hoàn thiện về mặt nội dung và lý luận trong sáng kiến. 6 PHẦN II - GIẢI QUYẾT VẤN ĐỀ I. Cơ sở lý luận: Thuật toán sắp xếp và tìm kiếm là hai khái niệm căn bản trong bộ môn tin học nói chung và trong chuyên ngành lập trình nói riêng. Ngay cả trong cuộc sống hàng ngày ta vẫn thường gặp những công việc liên quan đến sắp xếp, tìm kiếm như xếp hàng tập trung cho học sinh theo thứ tự từ thấp đến cao, xếp điểm trung bình các môn học cuối năm của một lớp theo thứ tự từ cao đến thấp; tìm những học sinh có học lực loại yếu, những học sinh phải thi lại… Nói một cách tổng quát, cho một dãy đối tượng, cần sắp xếp lại vị trí các đối tượng hoặc tìm kiếm các đối tượng theo một tiêu chí nào đó. Dưới đây ta xét bài toán sắp xếp, tìm kiếm dạng đơn giản và hướng giải quyết thông thường như sau: Bài toán 1: Cho dãy A gồm N số nguyên a1, a2,… aN. Sắp xếp các số hạng để dãy A trở 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). - Xác định bài toán + Input: Dãy A gồm N số nguyên a1, a2,… aN. + Output: Dãy A được sắp xếp lại thành dãy không giảm. - Ý tưởng: Với mỗi cặp số hạng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi vị trí của chúng cho nhau. Việc này được lặp lại cho đến khi không còn sự đổi chỗ nào xảy ra nữa. Bài toán 2: Cho dãy A gồm N số nguyên khác nhau: a1, a2,…, aN và một số nguyên K. Tìm xem có hay không chỉ số i (1  i  N ) mà ai = K. Nếu có hãy cho biết chỉ số só đó. - Xác định bài toán: + Input: Dãy A gồm N số nguyên a1, a2,…, aN và số nguyên K. + Output: Đưa ra chỉ số i sao cho ai=K (nếu có). - Ý tưởng: Lần lượt từ số hạng thứ nhất so sánh giá trị số hạng với K cho đến khi tìm được hoặc tìm hết mà không tìm được số hạng nào có giá trị bằng K. Đây là hai bài toán cơ bản mà học sinh có thể sử dụng những kiến thức đã học trong sách giáo khoa để thực hiện. II. Cơ sở thực tiễn Ưu điểm của việc sử dụng các thuật toán trong sách giáo khoa đó là dễ nhớ, dễ sử dụng. Tuy nhiên nhược điểm của các thuật toán này là không áp dụng cho nhiều bài toán khác nhau, thời gian thực hiện không tối ưu với các loại dữ liệu lớn, bên cạnh đó thì không kích thích được tư duy học sinh, dễ làm học sinh tiếp thu một các thụ động, gây ra sự nhàm chán khi học, khó phát triển tư duy thuật toán của học sinh mà đây là một trong nội dung hết sức quan trọng với việc học lập trình. Bên cạnh đó thì có quá ít bài tập về sắp xếp, tìm kiếm để học 7 sinh vận dụng dẫn đến học sinh hiểu về toán tìm kiếm và sắp xếp một cách rất mơ hồ, không biết sử dụng một cách linh hoạt cho các bài toán khác nhau. Mặt khác tôi nhận thấy giữa thuật toán được học ở lớp 10 và ngôn ngữ lập trình lớp 11 chưa có sự gắn kết chặt chẽ. Các em được học về thuật toán nhưng sau gần một năm các em mới có thể vận dụng thuật toán đó sang một ngôn ngữ lập trình cụ thể. Điều đó dẫn tới việc các em quên, không nắm chắc được thuật toán, làm cho thuật toán vốn dĩ đã khó càng trở nên khó hơn nữa. Hậu quả là việc học môn tin ở trường THPT đối với các em là đối phó không mang lại sự hấp dẫn mới mẻ đối với một môn học mà nó là nền tảng của các công việc ngày nay. III. Các biện pháp để giải quyết vấn đề 1. Xây dựng kế hoạch giảng dạy: Để học sinh có thể vận dụng các thuật toán trực tiếp vào thực tiễn thì mỗi nhà trường cần thay đổi nội dung chương trình phù hợp quá trình học tập của học sinh. Cụ thể với bộ môn tin học của trường THPT Gia Viễn B chúng tôi đã thống nhất xây dựng nội dung chương trình tin học đó là đưa nội dung của phần thuật toán, trong đó có thuật toán sắp xếp và tìm kiếm vào nội dung của chương trình tin học lớp 11 như sau: Tuần Tiết Nội dung Chương I. Một số khái niệm lập trình và ngôn ngữ lập trình 1 §1 Khái niệm lập trình và ngôn ngữ lập trình 1 2 §2 Các thành phần của ngôn ngữ lập trình 3 §4 Bài toán và thuật toán (tiết 1) 2 4 §4 Bài toán và thuật toán (tiết 2) 5 §4 Bài toán và thuật toán (tiết 3) 3 6 §4 Bài toán và thuật toán (tiết 4) Chương II. Chương trình đơn giản §3 Cấu trúc chương trình §4 Một số kiểu dữ liệu chuẩn 7 4 §5 Khai báo biến 8 §6 Phép toán, biểu thức, câu lệnh gán (mục 1, 2, 3) 9 §6 Phép toán, biểu thức, câu lệnh gán ( mục 4, 5, 6) §7 Các thủ tục chuẩn vào/ra đơn giản 5 10 §8 Soạn thảo, dịch, thực hiện và hiệu chỉnh chương trình. 11 Bài tập và thực hành 1 ( mục a, b, c) 6 12 Bài tập và thực hành 1 ( mục d, e, f, g, h, i) Chương III. Cấu trúc rẽ nhánh và lặp 13 §9 Cấu trúc rẽ nhánh (mục 1, 2, 3) 7 14 §9 Cấu trúc rẽ nhánh (mục 4) 15 Bài tập 8 16 §10 Cấu trúc lặp (mục 1) 17 §10 Cấu trúc lặp (mục 2) 9 18 §10 Cấu trúc lặp (mục 3) 8 Ghi chú Sách GK 10 Phòng máy Phòng máy 10 11 12 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 Bài tập Bài tập và thực hành 2 ( mục a, b, c, d) Bài tập và thực hành 2 ( mục e, f, g, h) Ôn tập Kiểm tra 1 tiết Chương IV. Kiểu dữ liệu có cấu trúc §11 Kiểu mảng (mục 1: a) §11 Kiểu mảng (mục 1: b ví dụ 1) §11 Kiểu mảng (mục 1: b ví dụ 2) Bài tập Bài tập và thực hành 3 ( bài 1) Bài tập và thực hành 3 ( bài 2) Bài tập và thực hành 4 ( bài 1) Bài tập và thực hành 4 ( bài 2) Ôn tập Ôn tập Kiểm tra học kỳ I §12 Kiểu xâu (mục 1, 2) §12 Kiểu xâu (mục 3) Phòng máy Phòng máy Phòng máy Phòng máy Phòng máy Phòng máy Nội dung phần thuật toán không dạy của tin học lớp 10 chuyển sang chuyên đề tháo lắp máy tính. 2. Xây dựng nội dung giảng dạy các thuật toán: Bên cạnh việc thay đổi cấu trúc chương trình thì việc thay đổi nội dung, phương pháp giảng dạy cho phù hợp thực tiễn là một điều hết sức quan trọng. Dưới đây là nội dung mà chúng tôi thực hiện giảng dạy trong chuyên đề thuật toán sắp xếp và tìm kiếm. Bên cạnh những thực toán trong sách giáo khoa cho đối tượng học sinh lớp cơ bản là những thuật toán nâng cao để ôn luyện cho học sinh giỏi. 2.1. Bài toán đặt vấn đề Theo phương pháp dạy học tích cực để tiếp cận khái niệm sắp xếp và một số thuật toán sắp xếp thì nên đưa ví dụ mang tính thực tiễn hoặc đơn giản để phát huy khả năng của hiện có của học sinh. Ví dụ như ta có thể đưa ra bài toán sau cho học sinh thảo luận và đưa ra phương án giải quyết: Bài toán 1: Cho dãy số A gồm 5 số: 5 3 1 2 4. Với những kiến thức đã được học, chắc chắn học sinh sẽ có đưa ra cách thức như: So sánh lần lượt các số sau đó tìm số nhỏ nhất đặt ở đầu, sau đó với cách làm tương tự tìm số nhỏ thứ 2,... Rồi cuối cùng là tìm được cả 5 vị trí. Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp được biểu diễn như sau: Lượt duyệt 1: So sánh các giá trị liền kề để đưa giá trị 1 về phía đầu dãy 5 3 1 2 9 4 53124 53124 53124 51324 15324 Lượt duyệt 2: Tiếp tục đưa giá trị 2 về phía đầu dãy 5 3 2 4 15324 15324 15234 12534 Lượt duyệt 3: Đưa giá trị 3 về phía đầu dãy: 5 3 4 12534 12534 12354 Lần duyệt 4: Đưa giá trị 4 về phía đầu dãy: 5 4 12354 12345 Sau đó giáo viên có thể đưa ra vấn đề mở rộng hơn: Bài toán 2: Cho dãy số A gồm 5000 số: a1, a2,...,a5000. Như vậy đến đây học sinh sẽ xuất hiện mâu thuẫn khó giải quyết nếu dữ liệu nhỏ thì việc sắp xếp sẽ thực hiện rất đơn giản nhưng nếu dữ liệu lớn hơn thì thời gian để thực hiện sẽ rất khó kể cả sử dụng máy tính máy tính đi chăng nữa. Đến đây ta có thể đưa ra phương hướng giải quyết mâu thuẫn, đó là: lựa chọn và sử dụng một thuật toán phù hợp để giải quyết một bài toán nào đó. Từ đó học sinh cũng sẽ hiểu được kết luận: “Một bài toán thì có nhiều thuật toán để giải”. Dẫn dắt đến những thuật toán mới với những cách xử lý mới. 2.2. Một số thuật toán sắp xếp cơ bản: Là hệ thống các dạng bài toán được trình bày theo mức độ phát triển tư duy của học sinh. Trong mỗi thuật toán thì đều có mô phỏng ví dụ và đưa ra đánh giá nhận xết cho từng thuật toán. 2.2.1 Thuật toán sắp xếp nổi bọt (Bubble Sort) - Ý tưởng của thuật toán: 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 đó được lặp đi lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa. - Ý tưởng được mô tả cụ thể như sau: + Lượt 1: Ta xét từ cuối dãy, nếu gặp hai phần tử kề nhau mà số đứng trước lớn hơn số đứng sau thì ta đổi chỗ chúng cho nhau. Sau lượt 1, phần tử nhỏ nhất được đưa về vị trí 1. 10 + Lượt 2: Ta xét từ cuối dãy (chỉ đến phần tử thứ 2), nếu gặp hai phần tử kề nhau mà số đứng trước lớn hơn số đứng sau thì ta đổi chỗ chúng cho nhau. Sau lượt 2, phần tử nhỏ thứ hai được đưa về vị trí 2. + Lượt i: Ta xét từ cuối dãy (chỉ đến phần tử thứ i), nếu gặp hai phần tử kề nhau mà số đứng trước lớn hơn số đứng sau thì ta đổi chỗ chúng cho nhau. Sau lượt i, phần tử nhỏ thứ i được đưa về vị trí i. + Xong lượt thứ n-1 thì dãy được sắp xếp xong. - Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4. Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt được biểu diễn như sau: Lượt duyệt 1: So sánh các giá trị liền kề để đưa giá trị 1 về phía đầu dãy 5 3 1 2 4 53124 53124 53124 51324 15324 Lượt duyệt 2: Tiếp tục đưa giá trị 2 về phía đầu dãy 5 3 2 4 15324 15324 15234 12534 Lượt duyệt 3: Đưa giá trị 3 về phía đầu dãy: 5 3 4 12534 12534 12354 Lần duyệt 4: Đưa giá trị 4 về phía đầu dãy: 5 4 12354 12345 - Chương trình cài đặt Procedure BubbleSort; Var i, j: integer; tg: integer; Begin For i:= 1 to n – 1 do For j:= n downto i+1 do If a[j – 1] > a[j] then Begin Tg:= a[j]; a[j]:= a[j-1]; 11 a[j-1]:= tg; End; End; * Ngoài ra, còn cách cài đặt khác của thuật toán trên đó là xét từ đầu dãy về cuối dãy hay đưa các giá trị lớn nhất về phía cuối dãy, chương trình cài đặt như sau: Procedure Bubble Sort; Var i, j: integer; tg: integer; Begin For i:= 1 to n – 1 do For j:= i+1 to n do If a[j – 1] > a[j] then Begin Tg:= a[j]; a[j]:= a[j-1]; a[j-1]:= tg; End; End; Nhận xét: Tại lượt thứ i có n – i phép so sánh. Vậy số phép so sánh là: (n-1) + (n-2) + …+ 1 = n( n − 1) . 2 Độ phức tạp của thuật toán là O(n2) 2.2.2. Thuật toán sắp xếp kiểu chọn (Selection Sort) - Ý tưởng thuật toán: + Ở lượt thứ nhất, chọn trong dãy khóa a1, a2,…, aN ra khóa nhỏ nhất (khóa  mọi khóa khác) và đổi giá trị của nó với a1, khi đó giá trị khóa a1 trở thành giá trị khóa nhỏ nhất. + Ở lượt thứ hai, chọn trong dãy khóa a2,…, aN ra khóa nhỏ nhất và đổi giá trị của nó với a2. … + Ở lượt thứ i, chọn trong dãy khóa ai, ai+1,…, aN ra khóa nhỏ nhất và đổi giá trị của nó với ai. … + Ở lượt thứ n-1, chọn trong 2 khóa an-1, aN ra khóa nhỏ nhất và đổi giá trị của nó với aN-1. - Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4. Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp kiểu chọn như sau: Lần duyệt 1: Đổi khóa 1 cho 5 12 53124 13524 Lần duyệt 2: Đổi khóa 2 cho 3 13524 12534 Lần duyệt 3: Đổi khóa 3 cho 5 12534 12354 Lần duyệt 4: Đổi khóa 4 cho 5 12354 12345 - Chương trình cài đặt: Procedure SelectionSort; Var i, j, jmin, tg: integer; Begin For i:= 1 to n-1 do Begin jmin := i; For j := i + 1 to n If a[j] < a[jmin] then jmin:= j; If jmin <> i then Begin tg := a[j]; a[j]:= a[jmin]; a[jmin] := tg; end; end; End; Nhận xét: Tại lượt thứ i có n – i phép so sánh để tìm ra phần tử nhỏ nhất hiện hành. Vậy số phép so sánh vẫn là: (n-1) + (n-2) + …+ 1 = n( n − 1) . 2 Độ phức tạp của thuật toán là O(N 2 ) 2.2.3. Thuật toán sắp xếp kiểu chèn (Insertion Sort) - Ý tưởng thuật toán: Xét dãy khóa a1, a2,…, aN. Ta thấy dãy con chỉ gồm mỗi một khóa a1 có thể coi là đã sắp xếp rồi. Xét thêm a2, so sánh a2 với a1, nếu thấy a2 < a1 thì chèn nó vào trước a1. Đối với a3, xét dãy gồm 2 khóa a1, a2 đã sắp xếp và tìm cách chèn a3 vào dãy khóa đó để được một thứ tự sắp xếp. 13 Tổng quát, sắp xếp dãy a1, a2,…, ai trong điều kiện dãy ai-1 đã được sắp xếp rồi bằng cách chèn ai vào đúng vị trí dãy đó khi sắp xếp. - Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4. Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán chèn được biểu diễn như sau: Lượt 1: Chèn 3 vào trước 5 53124 Lượt 2: Chèn 1 vào dãy 3, 5 35124 Lượt 3: Chèn 2 vào dãy 1, 3, 5 13524 Lượt 4: Chèn 4 vào dãy 1, 2, 3, 5 12354 Kết quả cuối cùng nhận được 12345 - Chương trình cài đặt: Var i, j: integer; tg: integer; Begin For i:= 2 to n do Begin tg := a[i]; j := i – 1; while (j>0 ) and ( tg < a[j] ) do begin a[j+1] := a[j]; j := j – 1; end; a[j+1] := tg; end; end; Nhận xét: Trường hợp tốt nhất : Dãy ban đầu đã có thứ tự không cần phải vào vòng lặp while. Với i chạy từ 2 đến n thì số phép so sánh tổng cộng sẽ là n-1 Độ phức tạp : O(n) Trường hợp xấu nhất : Dãy ban đầu có thứ tự ngược Vòng lặp while : i-1 lần Vòng lặp for: (n-1)+(n-2)+……+1= n( n − 1) 2 Độ phức tạp: O(n2) 14 2.2.4. Thuật toán sắp xếp nhanh (Quick Sort). - Ý tưởng thuật toán: Sắp xếp dãy khóa a1, a2,…, aN. Có thể coi là sắp xếp đoạn chỉ số từ chỉ số 1 tới chỉ số n trong dãy khóa đó. Để sắp xếp một đoạn trong dãy khóa, nếu đoạn đó  1 phần tử thì không cần phải làm gì. Nếu đoạn đó có 2 phần tử trở lên thì ta chọn một khóa ngẫu nhiên làm chốt, mọi khóa nhỏ hơn chốt thì được xếp vào vị trí trước chốt, còn mọi khóa lớn hơn chốt thì được xếp vào vị trí sau chốt. Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm hai đoạn khác rỗng mà mọi khóa trong đoạn đầu  chốt, và mọi khóa trong đoạn sau đều  chốt. Vấn đề trở thành sắp xếp hai đoạn mới tạo ra (có độ dài ngắn hơn đoạn ban đầu) bằng phương pháp tương tự. - Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4. Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp nhanh được biểu diễn như sau: (5 3 1 2 4) 1 (3 5 2 4) 1 (3 4 2) 5 1 (2) 3 (4) 5 12345 - Chương trình cài đặt: Procedure QuickSort (L, H: longint); Var i, j: longint; x, tg: longint; Begin i := L; j:= H; x := a[ (L+H) div 2 ]; repeat while a[i] < x do inc (i); while a[j] > x do dec (j); if i <= j then begin tg := a[i]; a[i] := a[j]; a[j] := tg; inc (i); Dec (j); end; 15 until i>j; if L < j then QuickSort (L, j); if i < H then QuickSort (i, H); end; Nhận xét: Trường hợp chương trình ít gọi tới thủ tục sắp xếp và chỉ sắp xếp trên tập dữ liệu nhỏ thì có thể sử dụng thuật toán đơn giản có độ phức tạp O(N 2) dễ cài đặt. Trường hợp sắp xếp trên tập dữ liệu lớn nên sử dụng thuật toán sắp xếp nhanh vì độ phức tạp của thuật toán là O(nlogn). 2.2.5. Sắp xếp bằng đếm phân phối (Distribution Counting) - Ý tưởng thuật toán Thuật toán dành cho trường hợp đặc biệt, khóa của các phần tử A 1, A2,…, AN là các số nguyên nằm trong khoảng từ 0 tới K (Tkey = 0..M). Xây dựng dãy C0, C1,…CM các biến đếm, trong đó CV là số lần xuất hiện giá trị V trong dãy khóa. Dựa vào dãy biến đếm, ta sẽ biết được sau khi sắp xếp thì giá trị V nằm từ vị trí nào tới vị trí nào. Tức là sau khi sắp xếp: + Giá trị 0 đứng trong đoạn từ vị trí 1 tới vị trí C0 + Giá trị 1 đứng trong đoạn từ vị trí C0+1 tới vị trí C0+C1 + Giá trị 2 đứng trong đoạn từ vị trí C0+C1+1 tới vị trí C0+C1+C2 … + Giá trị v đứng trong đoạn từ vị trí C0+C1+…+Cv-1 +1 tới vị trí C0+C1+C2+…+Cv … Nếu ta tính lại dãy C như sau: For V:=1 to M do Cv := Cv-1+Cv Thì Cv là vị trí cuối của đoạn chứa giá trị V trong dãy khóa đã được sắp xếp. Dựng lại dãy khóa dắp xếp bằng cách thêm dãy khóa phụ X 1, X2,.., Xn, sau đó duyệt lại dãy khóa A, mỗi khi gặp khóa mang giá trị V ta đưa giá trị đó vào khóa Xcv và giảm Cv đi 1. Và cuối cùng là gán giá trị dãy khóa X cho dãy khóa A. - Ví dụ: Cho dãy số A gồm 5 số: 6 3 6 2 4. Mô tả cách sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp phân phối được biểu diễn như sau: V 1 2 3 4 5 6 I 1 2 3 4 5 Ai 6 3 6 2 4 Số lần xuất hiện của V trong mảng C[a[i]] 0 1 1 1 0 2 16 Vị trí của V 0 1 2 3 3 5 Thứ tự sắp xếp trong mảng của Ai 5 2 4 1 3 - Chương trình cài đặt: Procedure Sxphanphoi; Var C:array [0..M] of integer; X: Tarray; i: integer; v:Tkey; Begin For V:=0 to M do C[v]:=0; For i:=1 to n do C[A[i]]:= C[A[i] ]+ 1; For V:=1 to M do C[v]:=C[v-1] +C[v]; For i:=n downto 1 do Begin V:=A[i]; X[C[v]]:=A[i]; C[v]:=C[v]-1; End; A:=X; End; Nhận xét: Độ phức tạp của thuật toán là O(max(N, M)). Giá trị M càng nhỏ thì thuật toán sắp xếp càng nhanh. Nhưng cần lưu ý là Distribution Counting Sort chỉ nên áp dụng khi ta biết rõ M, nếu M quá lớn mà N nhỏ thì nên lựa chọn các thuật toán khác để xử lý. 2.2.6. Thuật toán sắp xếp trộn (Merge Sort). - Ý tưởng: - Nếu chỉ có một phần tử trong dãy thì coi như dãy đã được sắp xếp. Ngược lại thì chia dãy thành hai nửa cho tới khi không thể chia được nữa; sau đó kết hợp các dãy nhỏ lại thành dãy mới đã được sắp xếp. - Ví dụ: Sắp xếp mảng A gồm các phần tử: 14 33 27 10 35 19 42 44 Đầu tiên, giải thuật sắp xếp trộn chia toàn bộ mảng thành hai nửa. 14 33 27 10 35 19 42 44 Tiến trình chia này không làm thay đổi thứ tự các phần tử trong mảng ban đầu. Bây giờ chúng ta tiếp tục chia các mảng này thành 2 nửa. 14 33 27 10 35 19 42 44 Tiến hành chia tiếp cho tới khi không còn chia được nữa. 14 33 27 10 35 19 42 44 17 Tiếp theo sẽ tổ hợp chúng theo như đúng cách thức mà chúng được chia ra với cách thức là so sánh hai phần tử trong mỗi dãy và sau đó tổ hợp chúng vào trong một dãy khác theo cách thức đã được sắp xếp. 14 33 10 27 19 35 42 44 Tiếp tục kết hợp từng cặp dãy một ở trên. 10 14 27 33 19 35 42 44 Sau bước kết hợp cuối cùng ta sẽ được kết quả: 10 14 19 27 33 35 42 44 - Chương trình: procedure mergesort(1,r: integer); var i, j, k, m : integer; begin if r-1>0 then begin m:=(r+1) div 2; mergesort(1,m); mergesort(m+1,r); for i := m downto 1 do b[i] := a[j]; for j :=m+1 to r do b[r+m+1-j] := a[j]; for k :=1 to r do if b[i] < b[j] then begin a[k] := b[i] ; i := i+1 end else begin a[k] := b[j]; j:= j-1 end; end; end; Nhận xét: Ta thấy ngay số lần lặp của bước 2 (phân phối) và bước 3 (trộn) bằng log2n. Ta cũng thấy rằng chi phí thực hiện bước 2 và bước 3 tỉ lệ thuận với n. Như vậy, ta có thể ước tính độ phức tạp của thuật toán Merge Sort thuộc O(nlog2n) 2.3. Một số thuật toán tìm kiếm cơ bản. Trong ngành khoa học máy tính, một giải thuật tìm kiếm là một thuật toán lấy đầu vào là một bài toán và trả về kết quả là một lời giải cho bài toán đó, thường là sau khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuật toán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là các thuật toán tìm kiếm. Dưới đây là bài toán dạng đơn giản để chúng ta có thể hiểu rõ hơn về các thuật toán tìm kiếm. - Bài toán: Cho dãy A gồm N số nguyên khác nhau: a1, a2,…, aN và một số nguyên K. Cần biết có hay không chỉ số i (1  i  N ) mà ai = k. Nếu có hãy cho biết chỉ số só đó. - Xác định bài toán: - Input: Dãy A gồm N số nguyên a1, a2,…, aN và số nguyên K. - Output: Đưa ra chỉ số i sao cho ai=k (nếu có). 18 2.3.1. Thuật toán tìm kiếm tuần tự (Sequential Search) - Ý tưởng thuật toán: Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá. - Ví dụ: Cho dãy số A gồm các phần tử: 4 5 6 9 2 1 và số k=9, thuật toán tìm kiếm tuần tự mô tả bằng bảng sau: I 1 2 3 4 5 6 A[i] 4 5 6 9 2 1 A[i]=k? Sai Sai Sai Sai Đúng Thuật toán tìm kiếm tuần tự sẽ duyệt tuần tự từ phần đầu đến khi tìm thấy phần tử có giá trị bằng k thì dừng lại, như ví dụ trên ta sẽ tìm được i=5. - Chương trình cài đặt: Procedure Tktuantu; Var i: integer; Begin i:=1; While(i<=n)do Begin If a[i] = k then break else i:=i+1; End; If(i<=n) then Write(i) else Write(‘khong co so nguyen ’,k ,’ trong day’); End; Nhận xét: Số phép toán so sánh trong thuật toán: n Độ phức tạp thuật toán: O(n) 2.3.2. Thuật toán tìm kiếm nhị phân (Binary Search) - Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở “giữa dãy” để so sánh với k, trong đó Giua = (Chỉ số đầu+chỉ số cuối)/2 (Dãy đang xét) . Khi đó, chỉ xảy ra một trong ba trường hợp sau: – Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc. – Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,…, aGiua–1 (phạm vi tìm kiếm mới bằng khoảng 19 một nửa phạm vi tìm kiếm trước đó). – Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,…, aN. Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng. - Ví dụ: Cho dãy A gồm các phần tử 2 3 6 7 8 9 và một số nguyên x=7, thuật toán tìm kiếm nhị phân được thể hiện qua bảng mô tả như sau: I 1 2 3 4 5 6 A[i] 2 3 6 7 8 9 Dau 1 4 4 Cuoi 6 6 4 giua 3 5 4 A[giua]=x? Sai Sai Đúng Như vậy với chỉ sau ba lần duyệt thì thuật toán đã tìm ra chỉ số phần tử có giá trị bằng x là i=4; - Chương trình: Procedure binary(dau,cuoi:integer); Var giua:integer; begin dau:= 1; cuoi:= n; while dau <= cuoi do begin giua:= (dau+cuoi) div 2; if x = a[giua] then begin writeln(giua); break; end else if x < a[giua] then cuoi:= giua -1 else dau:= giua+1; end; if dau > cuoi then writeln(x, ’khong có trong day’); End; Nhận xét: Số phép so sánh: 2*log(n) Số phép gán chỉ số: 2*log(n) Độ phức tạp thuật toán: O(log(n)) Thuật toán này thực hiện dựa trên giả thiết là dữ liệu đã được sắp xếp. Nếu cần sắp xếp trước khi tìm kiếm thì độ phức tạp sẽ tăng lên vì vậy nên áp dụng thuật toán trong tình huống dãy đã sắp xếp sẵn. 20