Luận văn Thạc sĩ Sư phạm Toán: Phát triển tư duy thuật toán cho học sinh thông qua dạy học giải toán tổ hợp chương trình lớp 11, ban nâng cao

Chia sẻ: Ganuongmuoixa | Ngày: | Loại File: PDF | Số trang:84

Thêm vào BST

Báo xấu

35
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu của luận văn là đề ra một số biện pháp phát triển tư duy thuật giải trong quá trình dạy học nội dung đại số tổ hợp lớp 11 nhằm góp phần nâng cao hiệu quả dạy học Toán ở trường phổ thông. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Sư phạm Toán: Phát triển tư duy thuật toán cho học sinh thông qua dạy học giải toán tổ hợp chương trình lớp 11, ban nâng cao

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC GIÁO DỤC KIỀU VĂN VƯỢNG PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THÔNG QUA DẠY HỌC GIẢI TOÁN TỔ HỢP CHƯƠNG TRÌNH LỚP 11, BAN NÂNG CAO LUẬN VĂN THẠC SĨ SƯ PHẠM TOÁN HÀ NỘI – 2013 i
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC GIÁO DỤC KIỀU VĂN VƯỢNG PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THÔNG QUA DẠY HỌC GIẢI TOÁN TỔ HỢP CHƯƠNG TRÌNH LỚP 11, BAN NÂNG CAO LUẬN VĂN THẠC SĨ SƯ PHẠM TOÁN Chuyên ngành: LÝ LUẬN VÀ PHƯƠNG PHÁP DẠY HỌC (BỘ MÔN TOÁN) Mã số: 60 14 10 Người hướng dẫn khoa học: GS.TS. BÙI VĂN NGHỊ HÀ NỘI – 2013 i
LỜI CẢM ƠN Để hoàn thành luận văn, tác giả xin được bày tỏ lòng biết ơn chân thành đến quý thầy cô Trường Đại học Giáo dục, Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi và giúp đỡ tác giả trong thời gian học tập và làm luận văn. Đặc biệt, tác giả xin được bày tỏ lòng kính trọng và biết ơn sâu sắc đến người thầy hướng dẫn của mình là GS.TS. BÙI VĂN NGHỊ, người thầy đã tận tình hướng dẫn, chỉ bảo và giúp đỡ tác giả trong suốt quá trình nghiên cứu và thực hiện luận văn này. Tác giả xin chân thành cảm ơn các thầy cô giáo trong Ban Giám hiệu và tổ Toán trường THPT Hàm Long, thành phố Bắc Ninh, tỉnh Bắc Ninh đã tạo điều kiện, cộng tác và giúp đỡ tác giả làm thực nghiệm sư phạm tại trường. Xin cảm ơn các anh chị, các bạn học viên cùng học tại lớp LL&PP dạy học Bộ môn Toán K6, trường Đại học Giáo dục, Đại học Quốc gia Hà Nội đã dành sự quan tâm và tham gia đóng góp ý kiến cho tác giả trong quá trình học tập và nghiên cứu. Cuối cùng, tác giả xin được cảm ơn gia đình, người thân đã động viên và tạo điều kiện tốt nhất để tác giả có thể hoàn thành luận văn này. Mặc dù bản thân tác giả đã cố gắng nghiên cứu và thực hiện luận văn này song vẫn không thể tránh khỏi những hạn chế và thiếu sót. Tác giả rất mong nhận được sự đóng góp các ý kiến quý báu của các thầy cô giáo, các bạn đồng nghiệp và những người quan tâm đến các vấn đề được trình bày trong luận văn để luận văn được hoàn thiện hơn. Hà Nội, ngày 21 tháng 11 năm 2013 Người thực hiện Kiều Văn Vượng i
DANH MỤC CÁC CHỮ VIẾT TẮT Chữ viết tắt Ý nghĩa CB : Chủ biên CNTT : Công nghệ thông tin CT : Chương trình ĐK : Điều kiện GV : Giáo viên HS : Học sinh NC : Nâng cao NXB : Nhà xuất bản PPDH : Phương pháp dạy học SGK : Sách giáo khoa SGV : Sách giáo viên TCB : Tổng chủ biên THPT : Trung học phổ thông TNSP : Thực nghiệm sư phạm TXĐ : Tập xác định VD : Ví dụ ii
MỤC LỤC Trang Lời cảm ơn ..................................................................................................... i Danh mục chữ viết tắt .................................................................................... ii Mục lục ............................................................................................................ iii MỞ ĐẦU ........................................................................................................ 1 Chương 1: TƯ DUY THUẬT TOÁN VÀ VẤN ĐỀ PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THÔNG QUA MÔN 5 1.1. Cơ sở lý luận 5 1.1.1. Quan điểm hoạt động trong phương pháp dạy học 5 1.1.2. Một số quan điểm khác 6 1.2. Dạy học giải bài tập toán học 6 1.2.1. Vai trò của bài tập trong quá trình dạy học 6 1.2.2. Giải bài tập 7 1.3. Tư duy thuật toán 8 1.3.1. Khái niệm thuật toán và quy trình tựa thuật toán( thuật giải) 8 1.3.2. Các đặc trưng của thuật toán 12 1.3.3. Các phương pháp biểu diễn thuật toán 12 1.3.4. Độ phức tạp của thuật toán 16 1.3.5. Tư duy thuật toán và vấn đề phát tiển tư duy thuật toán trong dạy học 17 1.3.6. Dạy học thuật toán và quy trình tựa thuật toán 18 1.4. Một số thực tiễn về dạy học Đại số tổ hợp ở trường THPT 19 1.4.1. Đặc điểm của chương trình và sách giáo khoa đại số và giải tích 11 nâng cao trong chương trình Trung học phổ thông hiện nay 19 1.4.2. Đặc điểm phần đại số tổ hợp trong chương trình và sách giáo khoa Đại số và giải tích 11 nâng cao. 20 1.4.3.Một số nhận định chủ quan của tác giả về thực tiễn dạy và học Đại số tổ hợp ở trường THPT Hàm Long, Bắc Ninh. 22 iii
1.5. Tiểu kết chương 1 22 Chương 2: BIỆN PHÁP RÈN LUYỆN VÀ PHÁT TRIỂN TƯ DUY THUẬT TOÁN TRONG DẠY HỌC GIẢI TOÁN ĐẠI SỐ TỔ HỢP LỚP 11(NÂNG CAO) 23 2.1. Nội dung Đại số tổ hợp trong sách giáo khoa lớp 11 (nâng cao) 23 2.1.1. Hai quy tắc đếm cơ bản 23 2.1.2. Hoán vị 23 2.1.3. Chỉnh hợp 24 2.1.4. Tổ hợp 24 2.1.5. Nhị thức Newton 24 2.2. Định hướng phát triển tư duy thuật toán cho học sinh thông 25 qua dạy học giải toán đại số tổ hợp 2.2.1. Dạy học theo hướng phát triển tư duy thuật toán phải trên cơ sở đáp ứng được mục đích của việc dạy, học môn toán ở nhà trường phổ thông. 25 2.2.2. Dạy học theo hướng phát triển tư duy thuật toán phải trên cơ sở tôn trọng chương trình sách giáo khoa hiện hành. 25 2.2.3. Dạy học theo hướng phát triển tư duy thuật toán góp phần đổi mới phương pháp dạy học hiện nay. 26 2.2.4. Dạy học theo hướng phát triển tư duy thuật toánphải góp phần đắc lực hình thành nhân cách con người ở thời đại mới. 26 2.2.5. Dạy học theo hướng phát triển tư duy thuật toán phải phát huy tính tính cực nhận thức của học sinh phù hợp với thực tiễn hoàn cảnh, môi trường giáo dục và thực tiễn học sinh. 26 2.2.6. Dạy học theo hướng phát triển tư duy thuật toán phải kết hợp chặt chẽ rèn luyện cho học sinh tính tổ chức, tính linh hoạt và sáng tạo. 27 2.3. Biện pháp phát triển tư duy thuật toán cho học sinh trong dạy học giải toán đại số tổ hợp. 27 iv
2.3.1. Biện pháp 1 : Rèn luyện cho học sinh sử dụng thành thạo các thuật toán đã được trang bị trong chương trình. 27 2.3.2. Biện pháp 2: Tổ chức cho học sinh phát hiện những thuật toán mới để giải cùng một những dạng toán 38 2.3.3. Biện pháp 3: Trang bị và rèn luyện cho học sinh những kĩ thuật cần thiết quy một dạng toán lạ về dạng toán quen, về thuật toán quen thuộc. 46 2.3.4. Biện pháp 4: Tạo điều kiện cho học sinh đề xuất một hay nhiều thuật toán để giải cùng một dạng toán; qua đó chọn được thuật toán tốt nhất. 49 2.3.5. Biện pháp 5: Khắc phục những khó khăn, sai lầm cho học sinh 52 2.4. Tiểu kết chương 2 57 Chương 3: THỰC NGHIỆM SƯ PHẠM 59 3.1. Mục đích, nhiệm vụ, kế hoạch thực nghiệm sư phạm 59 3.1.1. Mục đích 59 3.1.2. Nhiệm vụ 59 3.1.3. Kế hoạch thực nghiệm sư phạm 59 3.2. Nội dung thực nghiệm sư phạm 60 3.2.1. Giáo án thực nghiệm thứ nhất 60 3.2.2. Giáo án thực nghiệm thứ hai 64 3.3. Đánh giá kết quảthực nghiệm sư phạm 68 3.3.1. Đề bài kiểm tra, đánh giá sau giờ dạy thực nghiệm sư phạm: 68 3.3.2. Kết quả thực nghiệm sư phạm 70 3.4. Kết luận chung về thực nghiệm 72 KẾT LUẬN VÀ KHUYẾN NGHỊ 73 v
MỞ DẦU 1. Lý do chọn đề tài 1.1. Để phục vụ cho sự nghiệp công nghiệp hóa - hiện đại hóa đất nước và bắt kịp sự phát triển của xã hội trong điều kiện bùng nổ thông tin, ngành giáo dục và đào tạo phải đổi mới phương pháp dạy học một cách mạnh mẽ nhằm đào tạo những con người có đầy đủ phẩm chất của người lao động trong nền sản xuất tự động hóa như: năng động, sáng tạo, tự chủ, kỷ luật nghiêm, có tính tổ chức, tính trật tự của các hành động và có ý thức suy nghĩ tìm giải pháp tối ưu khi giải quyết công việc. Điều 24, luật giáo dục (2005) quy định:" Phương pháp giáo dục phổ thông phải phát huy tính tích cực, tự giác chủ động, tư duy sáng tạo của học sinh,..., bồi dưỡng phương pháp tự học, rèn luyện kỹ năng vận dụng kiến thức vào thực tiễn, tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh". Muốn đạt được điều đó, một trong những việc cần thiết phải thực hiện trong quá trình dạy học là phát triển tư duy thuật giải cho học sinh. 1.2. Hiện nay ở trường phổ thông đã tiến hành giáo dục tin học. Tin học được dạy tường minh như một nội dung và sử dụng máy tính điện tử như công cụ dạy học. Do đó vấn đề phát triển phát triển tư duy thuật toán trong môn toán giữ một vị trí quan trọng trong giáo dục tin học. Khẳng định này được thể hiện rõ trong mục đích giáo dục tin học: "Làm cho tất cả mọi học sinh tốt nghiệp trung học đều nắm được những yếu tố cơ bản của tin học với tư cách là thành tố của văn hóa phổ thông". "Góp phần hình thành ở học sinh những loại hình tư duy liên hệ mật thiết với việc sử dụng công nghệ thông tin như tư duy thuật giải, tư duy điều khiển,..", "Góp phần hình thành ở học sinh những phẩm chất của người lao động trong nền sản xuất tự động hóa như: tính kỷ luật, tính kế hoạh hóa, tính phê phán và thói quen tự kiểm tra,..". 1
1.3. Phát triển tư duy thuật toán là một mục đích của việc dạy học toán ở trường phổ thông vì: Tư duy thuật toán tạo điều kiện tốt để học sinh tiếp thu kiến thức, rèn luyện các kỹ năng Toán học. Tư duy thuật toán phát triển sẽ thúc đẩy sự phát triển các thao tác trí tuệ (như: phân tích, tổng hợp, so sánh, trừu tượng hóa, khái quát hóa,...) cũng như những phẩm chất trí tuệ (như : tính linh hoạt, tính độc lập, tính sáng tạo). Tư duy thuật toán giúp học sinh hình dung được quá trình tự động hóa diễn ra trong những lĩnh vực khác nhau của con người, trong đó có lĩnh vực xử lý thông tin. Điều này làm cho học sinh thích nghi với xã hội tự động hóa, góp phần làm giảm ngăn cách giữa nhà trường và xã hội. 1.4. Phát triển tư duy thuật toán trong môn toán có ý nghĩa về nhiều mặt và môn toán chứa đựng khả năng to lớn về phát triển tư duy thuật giải, thế nhưng, tư duy thuật giải chưa được chú ý phát triển đúng mức ở nhà trường phổ thông. Đã có một số công trình nghiên cứu về vấn đề này, trong số các công trình đó có thể kể tới luận án của tiến sỹ Dương Vương Minh: "Phát triển tư duy thuật giải của học sinh trong khi dạy học các hệ thống số ở trường phổ thông" (1998). Luận án này đã xem xét việc phát triển tư duy thuật giải cho học sinh trong khi dạy các hệ thống số chứ chưa đi sâu vào việc phát triển tư duy thuật giải cho học sinh trong khi dạy học nội dung phương trình. Luận văn của thạc sỹ Nguyễn Thị Thanh Bình: "Góp phần phát triển tư duy thuật giải của học sinh Trung học phổ thông thông qua dạy học nội dung lượng giác 11" (2000) đã đề cập đến việc phát triển tư duy thuật giải cho học sinh trong khi dạy nội dung lượng giác 11. 1.5. Nội dung chương đại số tổ hợp – ban nâng cao là nội dung khá hay và khó ở chương trình toán trung học phổ thông vì có tính trừu tượng, nhiều dạng toán, nhiều quy trình vận dụng kỹ năng tính toán nhiều bài toán có tiềm 2
năng có thể chuyển về một thuật toán hay một quy trình tựa thuật toán. Đó là điều kiện thuận lợi nhằm phát triển tư duy thuật toán cho học sinh. Với những lý do nêu trên, tôi chọn đề tài "Phát triển tư duy thuật toán cho học sinh thông qua dạy học giải toán tổ hợp chương trình lớp 11, ban nâng cao " làm đề tài nghiên cứu khoa học của mình. 2. Mục đích nghiên cứu Mục đích nghiên cứu của luận văn là đề ra một số biện pháp phát triển tư duy thuật giải trong quá trình dạy học nội dung đại số tổ hợp lớp 11 nhằm góp phần nâng cao hiệu quả dạy học Toán ở trường phổ thông. 3. Giả thuyết khoa học Trong quá trình dạy học Toán trung học phổ thông nói chung, dạy học nội dung đại số tổ hợp nói riêng, giáo viên thực hiện theo một quy trình dạy học theo hướng phát triển tư duy thuật toán sẽ góp phần nâng cao chất lượng dạy học toán ở trường phổ thông. 4. Nhiệm vụ nghiên cứu Để đạt được mục đích nêu trên, luận văn có nhiệm vụ trả lời các câu hỏi khoa học sau: 4.1. Tư duy thuật toán là gì? Vì sao nó cần được phát triển ở học sinh trong dạy học môn Toán? 4.2. Có thể đưa ra thuật toán hay quy trình tựa thuật toán để giải một số dạng bài toán tổ hợp nhằm tập luyện hoạt động tư duy thuật toán cho học sinh được không? 4.3. Làm thế nào để đánh giá tính khả thi và hiệu quả của đề tài? 5. Phương pháp nghiên cứu 5.1. Nghiên cứu lý luận 3
- Nghiên cứu các công trình Tâm lí học, Giáo dục học, Lí luận và Phương pháp dạy học bộ môn Toán liên quan đến đề tài. - Các công trình nghiên cứu các vấn đề có liên quan trực tiếp đến đề tài (các luận văn, luận án, chuyên đề...) 5.2. Nghiên cứu thực tiễn Dự giờ, quan sát giờ dạy của giáo viên và hoạt động học tập của học sinh trong quá trình dạy học nói chung, dạy học nội dung đại số tổ hợp nói riêng. 5.3. Thực nghiệm sư phạm Tổ chức thực nghiệm sư phạm một số nội dung của luận văn tại trường THPT Hàm Long – tỉnh Bắc Ninh, kiểm chứng tính khả thi của đề tài thông qua các lớp học thực nghiệm và đối chứng trên cùng một lớp đối tượng. 6. Đóng góp của luận văn 6.1. Luận văn góp phần làm sáng tỏ nội dung khái niệm tư duy thuật toán và vai trò vị trí của việc phát triển tư duy thuật toán trong dạy học toán. 6.2. Xây dựng được các quy trình dạy học theo hướng phát triển tư duy thuật toán cho học sinh. 6.3. Khai thác được một số dạng bài toán tổ hợp có thể giúp học sinh xây dựng được thuật toán hay quy trình tựa thuật toán. 7. Cấu trúc luận văn Ngoài phần mở đầu, kết luận và khuyến nghị, tài liệu tham khảo, nội dung chính của luận văn được trình bày trong gồm có 3 chương. Chương 1: Tư duy thuật toán và vấn đề phát triển tư duy thuật toán cho học sinh phổ thông. Chương 2: Biện pháp rèn luyện và phát triển tư duy thuật toán trong dạy học giải toán đại sô tổ hợp lớp 11, ban nâng cao. Chương 3: Thực nghiệm sư phạm. 4
CHƯƠNG 1 TƯ DUY THUẬT TOÁN VÀ VẤN ĐỀ PHÁT TRIỂN TƯ DUY THUẬT TOÁN CHO HỌC SINH THÔNG QUA MÔN TOÁN 1.1. Cơ sở lý luận 1.1.1. Quan điểm hoạt động trong phương pháp dạy học Chúng ta biết rằng quá trình dạy học là một quá trình điều khiển hoạt động giao lưu của học sinh nhằm thực hiện những mục đích dạy học. Còn học tập là một quá trình xử lý thông tin. Quá trình này có các chức năng: đưa thông tin vào, ghi nhớ thông tin, biến đổi thông tin, đưa thông tin ra và điều phối. Học sinh thực hiện các chức năng này bằng những hoạt động của mình. Thông qua hoạt động thúc đẩy sự phát triển về trí tuệ ở học sinh làm cho học sinh học tập một cách tự giác, tích cực. Xuất phát từ một nội dung dạy học ta cần phát hiện những hoạt động liên hệ với nó rồi căn cứ vào mục đích dạy học mà lựa chọn để tập luyện cho học sinh một số trong những hoạt động đã phát hiện. Việc phân tích một hoạt động thành những hoạt động thành phần giúp ta tổ chức cho học sinh tiến hành những hoạt động với độ phức hợp vừa sức họ. Việc tiến hành hoạt động nhiều khi đòi hỏi những tri thức nhất định, đặc biệt là tri thức phương pháp. Những tri thức này lại là kết quả của một quá trình hoạt động khác. Trong hoạt động, kết quả rèn luyện được ở một mức độ nào đó có thể lại là tiền đề để tập luyện và đạt kết quả cao hơn. Do đó cần phân bậc những hoạt động theo những mức độ khác nhau làm cơ sở cho việc chỉ đạo quá trình dạy học. Trên cơ sở việc phân tích trên về phương pháp dạy học theo quan điểm hoạt động. Luận văn được nghiên cứu trong khuôn khổ của lý luận dạy học, lấy quan điểm hoạt động làm nền tảng tâm lý học. Nội dung của quan điểm này được thể hiện một cách tóm tắt qua những tư tưởng chủ đạo sau: 5
* Cho học sinh thực hiện và tập luyện những hoạt động và hoạt động tương thích với nội dung và mục đích dạy học. * Hướng đích và gợi động cơ cho các hoạt động. * Truyền thụ tri thức, đặc biệt là những tri thức phương pháp, như phương tiện và kết quả của hoạt động. * Phân bậc hoạt động làm căn cứ cho việc điều khiển quá trình dạy học. 1.1.2. Một số quan điểm khác Luận văn lấy quan điểm hoạt động làm nền tảng tâm lý học để nghiên cứu nhưng cũng dựa vào quan điểm của lý thuyết tình huống và lý thuyết kiến tạo bởi vì các quan điểm dạy học của các lý thuyết này có sự giao thoa với quan điểm của lý thuyết hoạt động. Theo lý thuyết tình huống thì học là sự thích ứng (bao gồm đồng hóa và điều tiết) đối với một môi trường sản sinh ra những mâu thuẫn, những khó khăn, những sự mất cân bằng. Một tình huống thường liên hệ với những quy trình hành động. Một yếu tố của tình huống mà sự thay đổi giá trị của nó có thể gây ra sự thay đổi quy trình giải quyết vấn đề của học sinh. Do đó trong quá trình dạy học ta cần soạn thảo ra tình huống tương ứng với tri thức cần dạy (tình huống cho tri thức đó một nghĩa đúng). Sau đó ủy thác tình huống này cho học sinh. Học sinh tiến hành hoạt động học tập diễn ra nhờ sự tương tác với môi trường. Theo lý thuyết kiến tạo, học tập là hoạt động thích ứng của người học. Do đó dạy học phải là dạy hoạt động, tổ chức các tình huống học tập đòi hỏi sự thích ứng của học sinh, qua đó học sinh kiến tạo được kiến thức, đồng thời phát triển được trí tuệ và nhân cách của mình. Như vậy, nếu phân tích rõ quan điểm dạy học theo lý thuyết tình huống và lý thuyết kiến tạo sẽ góp phần phát triển phương pháp dạy học phát triển tư duy thuật giải cho học sinh. 6
1.2. Dạy học giải bài tập toán học 1.2.1. Vai trò của bài tập trong quá trình dạy học Bài tập toán có vai trò quan trọng trong môn Toán. Điều quan trọng là bài tập có vai trò giá trị mang hoạt động của học sinh. Thông qua giả bài tập, học sinh phải thực hiện những hoạt động nhất định bao gồm cả nhận dạng và thể hiện định nghĩa, định lý, quy tắc hay phương pháp ( thuật toán), những hoạt động Toán học phức hợp, những hoạt động trí tuệ phổ biến trong Toán học, những hoạt động trí tuệ chung và những hoạt động ngôn ngữ. Từ đó ta càng thấy rõ hoạt động của học sinh liên hệ mật thiết với mục tiêu, nội dung và phương pháp dạy học. 1.2.2. Giải bài tập Vấn đề giải bài tập được tiến hành theo hai hướng cơ bản sau: Một là thông qua nghiên cứu việc giải bài tập để xác định cấu trúc quy luật hoạt động tư duy của con người. Hai là nghiên cứu việc giải bài tập như một dạng hoạt động học của học sinh. Phải kể đến công trình nghiên cứu của G.Poolya trong nhiều tác phẩm của mình: Giải bài toán như thế nào? Toán học và những suy luận có lý, Sáng tạo toán học…tuy ông không đưa ra một định nghĩa chính xác về giải bài tập, nhưng theo ông giải bài toán là sự “tìm kiếm một cách ý thức phương tiện thích hợp để đạt tới một mục đích trông thấy rõ ràng nhưng không thể đạt được ngay”. Dựa trên ngững tư tưởng tổng quát cùng với những gợi ý chi tiết của Polya (1975) về cách thức giải bài toán đã được kiểm nghiệm trong thực tiễn dạy học, Nguyễn Bá Kim [6] đã nêu phương pháp chung để giải bài toán như sau: + Bước 1: Tìm hiểu nội dung đề bài - Phát biểu đề bài dưới dạng thức khác nhau để tìm hiểu rõ nội dung bài toán. - Phân biệt cái đã cho và cái phải tìm, phải chứng minh. - Có thể dùng công thức, ký hiệu, hình vẽ để hỗ trợ cho việc diễn tả đề bài. 7
+ Bước 2: Tìm cách giải - Tìm tòi phát hiện cách giải nhờ những suy nghĩ có tính chất tìm đoán, biến đổi cái đã cho, biến đổi cái phải tìm hay phải chứng minh, liên hệ cái đã cho hoặc cái phải tìm với tri thức đã biết. liên hệ bài toán cần giải với một bài toán cũ tương tự, một trường hợp riêng, một bài toán tổng quát hơn hay một bài toán nào đó có liên quan, sử dụng phương pháp đặc thù với từng dạng toán chứng minhphanr chứng, quy nạp toán học, toán dựng hình, toán quỹ tích… - Kiểm tra lời giải bằng cách xem lại kĩ từng bước thực hiện hoặc đặc biệt hóa kết quả tìm được hoặc đối chiếu kết quả với một số tri thức liên quan… - Tìm tòi những cách giải khác, so sánh chúng để có thể chọn được cách giải hợp lý nhất. + Bước 3: Trình bày lời giải Từ cách giải đã phát hiện, sắp xếp các việc phải làm thành một chương trình gồm các bước theo một trình tự thích hợp và thực hiện các bước đó. + Nghiên cứu sâu lời giải - Nghiên cứu khả năng ứng dụng kết quả của lời giải. - Nghiên cứu giải các bài toán tương tự, mở rộng hay lật ngược vấn đề. 1.3. Tư duy thuật toán 1.3.1. Khái niệm thuật toán và quy tắc tựa thuật toán Hằng ngày con người tiếp xúc với rất nhiều bài toán từ đơn giản đến phức tạp. Đối với một số bài toán, tồn tại những quy tắc xác định mô tả quá trình giải. Từ đó con người đã đi đến khái niệm trực giác về thật toán và khái niệm này đã được dùng từ lâu, kéo dài suốt mấy nghìn năm trong Toán học. Thuật toán theo nghĩa trực giác được hiểu như một dãy hữu hạn các chỉ dẫn thực hiện được một cách đơn trị, kết thúc sau một số hữu hạn bước và đem lại kết quả là biến đổi thông tin vào một lớp của bài toán đó. Tuy nhiên trong quá trình dạy học, chúng ta thường chỉ gặp những quy tắc chưa mang đủ các đặc điểm đó nhưng cũng tỏ ra có hiệu lực trong việc chỉ 8
dẫn hành động và giải toán. Đó là “quy tắc tựa thuật toán” hay còn gọi là “Thuật giải” được hiểu như một dãy hữu hạn những chỉ dẫn thực hiện theo một trình tự xác định nhằm biến đổi thông tin vào của một lớp bài toán thành thông tin ra mô tả lời giải của lớp bài toán đó. Quy tắc tựa thuật toán phân biệt với thuật toán như sau: + Mỗi chỉ dẫn trong quy tắc có thể chưa mô tả hành động một cách xác định. + Kết quả thực hiện mỗ chỉ dẫn có thể không đơn trị. + Quy tắc không bảo đảm chắc chắn rằng sau một số hữu hạn bước thì đem lại kết quả là lời giải của bài toán. Mặc dù còn có những hạn chế so với thuật toán nhưng quy tắc tựa thuật toán cũng vẫn là tri thức phương pháp có ích cho quá trình hoạt động và giải toán. Trong tin học, người ta quan niệm bài toán là một việc nào đó ta muốn máy tính thực hiện. Những việc như đưa một dòng chữ ra màn hình, giải phương trình bậc hai, quản lý cán bộ của một cơ quan... là những ví dụ về bài toán. Khi dùng máy tính giải toán, ta cần quan tâm đến hai yếu tố: Đưa vào máy thông tin gì (Input) và lấy ra thông tin gì (Output). Do đó để phát biểu một bài toán, ta cần phải trình bày rõ Input và Output của bài toán và mối quan hệ giữa Input và Output. Ví dụ 1: Bài toán tìm ước chung lớn nhất của hai số nguyên dương. Input: Hai số nguyên dương M và N. Output: ước chung lớn nhất của M và N. Ví dụ 2: Bài toán tìm nghiệm của phương trình bậc 2: ax2 + bx + c = 0 (a  0). Input: Các số thực a, b, c. (a  0) Output: Tất cả các số thực x thỏa mãn: ax2 + bx + c = 0 Ở đây Output có thể là một hoặc hai số thực hoặc câu trả lời không có số thực nào như vậy. 9
Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần cơ bản: Input: Các thông tin đã có. Output: Các thông tin cần tìm từ Input. Việc cho một bài toán là mô tả rõ Input cho trước và Output cần tìm. Vấn đề là làm thế nào để tìm ra Output. Việc chỉ ra tường minh một cách tìm Output của bài toán được gọi là một thuật toán 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 (algorithm) giải bài toán đó. Có nhiều định nghĩa khác nhau về thuật toán. Dựa vào sự phân tích trên ta có thể định nghĩa thuật toán như sau: 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 toán, ta nhận được Output cần tìm. Ví dụ 2: Tìm giá trị lớn nhất của một dãy số nguyên. + Xác định bài toán. + Input: Số nguyên dương N và dãy N số nguyên a1, a2, ...an. + Output: Giá trị lớn nhất Max của dãy số. * Ý tưởng: - Khởi tạo giá trị Max = a1. - Lần lượt với i từ 2 đến N, so sánh giá trị số hạng a i với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai. * Thuật toán: Thuật toán giải bài toán này có thể được mô tả theo cách liệt kê như sau: Bước 1: Nhập N và dãy a1, a2, ...,an. Bước 2: Max = ai ; i: = 2 Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc. Bước 4: + Bước 4.1. Nếu ai > Max thì Max: = ai + Bước 4.2. Nếu i: = i + 1 rồi quay lại bước 3. Từ đó ta thấy thuật toán có các tính chất sau: 10
* 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. Ví dụ: Với thuật toán tìm Max đã xét: * Tính dừng: Vì giá trị của i mỗi lần tăng lên một đơn vị nên sau N lần thì i > N, khi đó kết quả của phép so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc. * Tính xác định: Thứ tự thực hiện các bước của thuật toán được mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các bước so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện. * Tính đúng đắn: Vì thuật toán so sánh Max với từng số hạng của dãy số và thực hiện Max: = ai nếu ai > Max nên sau khi so sánh hết N số hạng của dãy thì Max là giá trị lớn nhất. 1.3.2. Các đặc trưng của thuật toán - Tính đơn trị Tính đơn trị của thuật toán đòi hỏi rằng các thao tác sơ cấp phải đơn trị, nghĩa là hai phần tử thuộc cùng một cơ cấu, thực hiện cùng một thao tác trên cùng một đối tượng thì phải cho cùng kết quả. Ví dụ: Quy trình 4 bước để giải một bài toán. Bước 1. Tìm hiểu nội dung bài toán. Bước 2. Tìm đường lối giải toán. Bước 3. Thực hiện chương trình giải toán. Bước 4. Kiểm tra kết quả và nghiên cứu lời giải. 11
Quy trình này không phải là một thuật toán vì tính đơn trị bị vi phạm. Chẳng hạn bước 1, bước 2, bước 3, bước 4 không được xác định vì người ta có thể hiểu và làm theo nhiều cách khác nhau. Từ tính đơn trị, ta cũng thấy được tính hình thức hóa của thuật toán. Bất kể cơ cấu nào, chỉ cần biết thực hiện đúng trình tự quy định là sẽ đi đến kết quả chứ không cần phải hiểu ý nghĩa của những thao tác này. Tính chất này hết sức quan trọng vì nhờ đó ta có thể giao cho những thiết bị tự động thực hiện thuật giải, làm một số công việc thay thế cho con người. - Tính hiệu quả Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như: khối lượng tính toán, không gian và thời gian khi thuật toán được thực hiện. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề - bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Độ phức tạp của thuật toán là một tiêu chuẩn được dùng rộng rãi. - Tính tổng quát Thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. 1.3.3. Các phương pháp biểu diễn thuật toán Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn ngữ toán học như: "ta có", "điều phải chứng minh","giả thiết",... và sử dụng các phép suy luận toán học như phép kéo theo, phép tương đương,... Thuật toán là một phương pháp thể hiện lời giải một bài toán nên cũng phải tuân theo một số quy tắc nhất định. Để có thể truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thuật toán. Có 4 phương pháp biểu diễn thuật toán. 12
+ Ngôn ngữ tự nhiên và ngôn ngữ toán học. + Dùng lưu đồ - sơ đồ khối. + Dùng ngôn ngữ phỏng trình. + Dùng ngôn ngữ lập trình. - Ngôn ngữ tự nhiên và ngôn ngữ toán học. Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên và ngôn ngữ toán học, người ta sử dụng ngôn ngữ thường ngày và ngôn ngữ toán học để liệt kê các bước của thuật toán. Các thuật toán ở mục 1 đều được viết dưới dạng ngôn ngữ tự nhiên và ngôn ngữ toán học. Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc thuật toán, đôi lúc gây hiểu nhầm hoặc khó hiểu cho người đọc. - Lưu đồ - Sơ đồ khối. Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý. Để biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác: thao tác lựa chọn và thao tác hành động. * Thao tác lựa chọn. Thao tác lựa chọn được biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện: a=b =0 * Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý. 13