Sáng kiến kinh nghiệm Tin học lớp 10: Thuật toán quay lui và ứng dụng giải bài toán tối ưu

Phần 1: ĐĂT VÂN ĐÊ<br /> ̣ ́ ̀<br /> Kinh th<br /> ́ ưa quy ́thây cô giao!<br /> ̀ ́<br /> Tiến sĩ triều Lê, Thân Nhân Trung đã nói “Hiền tài là nguyên khí <br /> của quốc gia, nguyên khí thịnh thì thế nước mạnh mà hưng thịnh, nguyên <br /> khí suy thì thế  nước yếu mà thấp hèn”. Vì thế  các bậc đế  vương thánh <br /> minh luôn coi việc giáo dục nhân tài, kén chọn kẻ  sĩ, vun trồng nguyên <br /> khí quốc gia làm công việc hàng đầu..., câu nói bất hủ  của Thân Nhân  <br /> Trung đã cho thấy từ thời xa xưa các thế hệ ông cha đã rất coi trọng nhân <br /> tài và coi những nhân tài là tương lai của đất nước. Với cương vị là một  <br /> giáo viên chuyên ngành Tin học trực tiếp giảng dạy, tôi thấy được những <br /> nhiệm vụ  quan trọng phải làm đầu tiên đó là làm thế  nào để  học sinh  <br /> thích học và học giỏi môn Tin. Trong thời đại ngày nay, Tin học có vai  <br /> trò và vị trí đặc biệt quan trọng trong khoa học kĩ thuật và đời sống, giúp  <br /> con người tiếp thu một cách dễ  dàng các môn khoa học khác có hiệu <br /> quả.<br /> Có thể  nói phát hiện và bồi dưỡng HSG là một trong những hoạt <br /> động chuyên môn chính trong năm học của trường. Bản thân qua tham  <br /> khảo các đề thi HSG của tỉnh và quốc gia đã thấy hầu hết các đề thi đều <br /> có các bài toán tối  ưu. Để  giải các bài toán tôi  ưu thì có nhiều phương <br /> pháp giải, trong đó ứng dụng thuật toán quay lui để  giải bài toán tối ưu  <br /> cũng là một phương pháp được nhiều người sử  dụng. Đo cung chinh la<br /> ́ ̃ ́ ̀ <br /> ̉ ́ ̀ ̀ “Thuật toán quay lui và  ứng dụng giải bài toán  <br /> ly do đê tôi viêt đê tai <br /> ́<br /> tối ưu”.<br /> <br /> <br /> Tôi rât mong đ<br /> ́ ược sự  gop y cua quy thây cô đê đê tai ngay cang<br /> ́ ́ ̉ ́ ̀ ̉ ̀ ̀ ̀ ̀  <br /> được hoan thiên h<br /> ̀ ̣ ơn.<br /> Xin chân thanh cam <br /> ̀ ̉ ơn!<br /> <br /> <br /> Trang 1<br /> Phân 2: NH<br /> ̀ ỮNG BIÊN PHAP GIAI QUYÊT VÂN ĐÊ<br /> ̣ ́ ̉ ́ ́ ̀<br /> I. CƠ SỞ LÝ LUẬN CỦA VẤN ĐỀ:<br /> Cũng như  trình bày  ở  trên bài toán tối  ưu là một trong những bài  <br /> toán thường gặp trong các kỳ thi học sinh giỏi.<br /> Công việc khó khăn  ở  đây là làm thế  nào để  các em có thể  hiểu  <br /> được thuật toán và có thể ứng dụng vào giải các bài toán liên quan.<br /> Xuất phát từ thực tiễn như vậy, tôi đã đưa ra một số bước giúp cho <br /> các em có thể  hiểu được thuật toán và  ứng dụng để  giải các bài toán <br /> cùng loại:<br /> ­ Ý tưởng của thuật toán.<br /> ­ Thuật toán.<br /> ­ Ứng dụng thuật toán giải các bài toán đơn giản.<br /> ­ Ứng dụng thuật toán quay lui có đánh giá cận giải một số  bài <br /> toán phức tạp.<br /> ­ Ứng dụng thuật toán giải bài toán trong các đề thi học sinh giỏi.<br /> II. THỰC TRẠNG CỦA VẤN ĐỀ:<br /> 1) Thực trạng về cấp quản lý<br /> *) Ưu điểm:<br /> ­ Đã quan tâm vào công tác phát triển mũi nhọn.<br /> ­ Có sự  phân công nhiệm vụ  cho từng giáo viên trực tiếp <br /> giảng dạy, giám sát và kiểm tra quá trình thực hiện của giáo viên.<br /> ­ Động viên tinh thần cũng như tạo mọi điều kiện thuận lợi  <br /> nhất để giáo viên thực hiện nhiệm vụ.<br /> *) Hạn chế:<br /> Khi phân công nhiệm vụ  thì chưa xác định một chiến lược <br /> lâu dài, đó là chỉ tập trung phát hiện và bỗi dưỡng học sinh lớp 11  <br /> <br /> <br /> <br /> <br /> Trang 2<br />  mà không phát hiện và bồi dưỡng ngay từ khi các em đang học lớp <br /> 10.<br /> 2) Thực trạng về giáo viên<br /> *) Ưu điểm:<br /> ­ Được đào tạo về chuyên môn cơ bản, có sức khỏe, sức trẻ,  <br /> có lòng nhiệt tình trong công việc. Luôn luôn học tập trau dồi tri  <br /> thức, nhằm phục vụ tốt nhất cho sự nghiệp giáo dục.<br /> ­ Trong quá trình giảng dạy, tuy gặp nhiều khó khăn nhưng <br /> phần lớn các thầy cô giáo đều đặt chữ “tâm” lên hàng đầu, đây là  <br /> một trong những thuận lợi góp phần vào sự  thành công của ngành <br /> giáo dục.<br /> ­ Có sự đầu tư vào nghiên cứu khi được giao nhiệm vụ.<br /> *) Hạn chế:<br /> Một số  giáo viên không có tâm huyết, chưa tập trung vào <br /> công tác chuyên môn nên kiến thức về ôn luyện học sinh giỏi còn  <br /> hạn chế. Việc bồi dưỡng HSG chỉ  tập trung cho số   ít giáo viên <br /> trong tổ.<br /> 3) Thực trạng về học sinh <br /> *) Ưu điểm:<br /> ­ Các em HS ngoan, cần cù chịu khó, có ý thức vươn lên <br /> trong học tập.<br /> ­ Có trách nhiệm với việc học tập, trong quá trình học tập <br /> hăng say phát biểu, đóng góp nên sự thành công của bài giảng.<br /> *) Hạn chế:<br /> ­ Kiến thức cơ bản về lập trình còn rất nhiều hạn chế, chỉ <br /> có số  ít em học sinh trên địa bàn thị  trấn, mới được tiếp cận với  <br /> lập trình ở chương trình lớp 8 – THCS.<br /> <br /> <br /> <br /> Trang 3<br />  ­ Đa số các em học tốt môn Tin học thì lại học tốt các môn <br /> khoa học tự nhiên (Toán, Lí, Hóa), nên đã theo tham gia bồi dưỡng <br /> ở các bộ môn đó.<br /> ­ Tin học là môn mà không có trong các kỳ  thi tốt nghiệp  <br /> cũng như  đại học hàng năm, nên các em cũng không mặn mà với <br /> việc tham gia học và bồi dưỡng HSG.<br /> <br /> <br /> 4) Thực trạng về cơ sở vật chất<br /> *) Ưu điểm:<br /> ­ Có đủ cơ sở vật chất để phục vụ cho lớp học.<br /> ­ Có các phương tiện phục vụ cho mục đích giảng dạy , VD: <br /> Bảng từ, máy chiếu, máy tính...<br /> *) Hạn chế:<br /> ­ Thiếu tài liệu và sách tham khảo.<br /> ­ Một số học sinh không có đủ kinh phí mua máy tính cá <br /> nhân phục vụ cho mục đích ôn tập tại nhà.<br /> <br /> <br /> III. CÁC BIỆN PHÁP ĐàTIẾN HÀNH ĐỂ GIẢI QUYẾT VẤN ĐỀ:<br /> 1. Thuật toán quay lui: Giả thiết một cấu hình cần tìm được mô tả bởi <br /> một bộ  phận gồm n thành phần a1, a2,...an. Giả  sử  tìm được i ­ 1 thành <br /> phần a1, a2, ai­1, ta tìm thành phần thứ  i bằng cách duyệt tất cả  các khả <br /> năng có thể  của ai. Với mỗi khả  năng j kiểm tra xem nó có chấp nhận  <br /> được không. Xảy ra hai trường hợp:<br /> ­ Chấp nhận được thì xác định ai theo j và kiểm tra xem i = n chưa, nếu i <br /> = n thì ta ghi nhận một cấu hình, còn nếu i