Giáo án dạy học theo chuyên đềCHUYÊN ĐỀ : GIẢI BÀI TOÁN TRÊN MÁY TÍNH [TIẾT 1][ Gồm các tiết từ tiết 9-15,17,18 trong ppct tin học 10]I. Mục tiêu bài học1. Kiến thức:- Hiểu được khái niệm về bài toán, thuật toán.- Hiểu được một số thuật toán trong tin học- Biết được các loại ngôn ngữ lập trình- Biết các bước cơ bản khi tiến hành giải toán trên máy tính.2. Kĩ năng: Xác định bài toán và lựa chọn thuật toán để giải bài toán trên máy tính.3. Thái độ: Học sinh hứng thú và tìm hiểu các giải bài toán trên máy tính [có thể hứng thú ápdụng trên một phần mềm cụ thể]4. Năng lực hướng tới:- Năng lực sử dụng công nghệ thông tin và truyền thông: Xem xét và nhìn nhận về Tin họckhông đơn thuần là sử dụng máy tính, sử dụng hiệu quả các kiến thức về toán học để xácđịnh bài toán và thuật toán áp dụng để giải bài toán trên máy tính.- Năng lực giao tiếp: Chủ động trong giao tiếp, tôn trọng lắng nghe có phản ứng tích cựctrong giao tiếp- Năng lực tự học: Xác định nhiệm vụ khi học Tin học để phục vụ cho công việc.II. Chuẩn bị của giáo viên và học sinh.1. Giáo viên: SGK, giáo án, SGV, máy chiếu [nếu có].2. Học sinh: SGK, vở ghi bài, vở bài tập.III. Phương pháp Thuyết trình, vấn đáp.IV. Tiến trình lên lớp1. Ổn định lớp.- Ổn định lớp, yêu cầu lớp trưởng báo cáo sĩ số.2.Bài giảngHoạt động1Nội dungGiáo án dạy học theo chuyên đề1. Khởi động [Tình huống xuất phát]2. Hình thành kiến thức3. Luyện tập4. Tìm tòi và mở rộngV. Hướng dẫn cụ thể tiến trình dạy họcGV: Trong toán học ta nhắc nhiều đến kháiniệm “bài toán” và hiểu đó là những việc màcon người cần phải thực hiện sao cho từ nhữngdữ kiện ban đầu phải tìm hay chứng minh mộtkết quả nào đó.Vậy khái niệm “Bài toán” trong tin học cókhác gì không? Lấy ví dụ về các bài toán trongtin học.GV: Lấy một số ví dụ cho hs hiểu về bài toántrong toán học và bài toán trong tin học.- Hiểu được khái niệm bài toán, thuật toán- Xây dựng thuật toán để giải một số bài toánthường gặp- Biết được các loại ngôn ngữ lập trình- Biết các bước để giải các bài toán trên máytính- Câu hỏi dạng trắc nghiệm- Áp dụng vào ví dụ giải phương trình bậc 2 códạng: ax2 + bx +c =0- a1x + b1y = c1a2x + b2y = c2- ……………Cho một số ví dụ cụ thể.1. Hoạt động 1: Tình huống xuất phát [Tiết 1][1] Mục tiêu: Tạo động cơ để học sinh quan tâm đến cách giải một bài toán trên máy tính[2] Phương pháp/ kỹ thuật dạy học: Cá nhân, thảo luận nhóm[3] Phương tiện: SGK, máy tính, máy chiếu[4] Sản phẩm: Học sinh có nhu cầu muốn biết cách giải bài toán trên máy tính điện tửHoạt động của giáo viênHoạt động của học sinhGv: Cho học sinh xác định một số ví dụ bài oántrong toán học và bài toán trong môn Tin họcGiáo viên chia làm 3 nhóm yêu cầu từng nhómthực hiện công việc sau: Cho phương trình bậc2 có dạng:ax2 + bx +c =0 [a0] em hãy:- Xác định điều kiện để giải được bài toán, mụcđích của việc giải phương trình[Nhóm 1]Câu trả lời mong đợi:- Nêu cách giải bài toán [Nhóm 2]- Nhóm 1:- Đưa ra kết quả của bài: [Nhóm 3]+ Các giá trị a,b,c [a0]2Giáo án dạy học theo chuyên đề+ a=1;b=2,c=1+ a=1;b=2;c=-3+ a=1;b=2; c=8[Việc chia 3 nhóm sẽ vẫn dùng cho các tiết còn lại]Gv: Vậy để giải quyết một bài toán, công việctrước tiên là gì và sau đó thực hiện giải quyết rasao chúng ta nghiên cứu bài học hôm nayGV: Trình chiếu chương trinh TP, kết quả nhằmgợi cho HS hứng thú đi tìm hiểu cách làmMàn hình chương trìnhMàn hình kết quả:Một số slide trong bài3+ Nghiệm của phương trình- Nhóm 2:+ Tính : ∆ = B2 + 4ac+ Nếu ∆ =0 thì phương trình có nghiệmkép+ Nếu ∆ >0 thì phương trình có 2 nghiệm+ Nếu ∆ =0 thì phương trình vô nghiệm- Nhóm 3:+ Phương trình có 1 nghiệm kép+ Phương trình có 2 nghiệm phân biệt+ Phương trình vô nghiệmHs: Trả lời: Xác định dữ kiện của bài toán,và yêu cầu của bài toánGiáo án dạy học theo chuyên đềSlide 34Giáo án dạy học theo chuyên đềSlide 42. Hoạt động 2: Hình thành kiến thứcNội dung 1: Xác định bài toán [Tiết 1][1] Mục tiêu: - Hiểu được khái niệm bài toán- Xác định được Input, Output của bài[2] Phương pháp / Kỹ thuật : Đàm thoại, phát hiện vấn đề. Khai thác mối quan hệ giữa thựctiễn với tin học[3] Hình thành tổ chức hoạt động: Làm việc cá nhân, Thảo luận nhóm[4] Phương tiện: SGK, máy chiếu, máy tính[5] Kết quả: Học sinh nhớ được và xác định được Input ,Out put của bàiHoạt động của giáo viênHoạt động của học sinhGV: Trong toán học ta nhắc nhiều đến kháiniệm “bài toán” và hiểu đó là những việc 1. Xác định bài toánmà con người cần phải thực hiện sao cho a. Khái niệm bài toántừ những dữ kiện ban đầu phải tìm hayBài toán là những việc mà con người muốnchứng minh một kết quả nào đómáy tính thực hiện.Ví dụ: Giải phương trình, quản lý thông tin vềGV: Lấy một số ví dụ cho HS xác định đâu HS,... là bài toán.là bài toán trong tin học, trong toán học.b. Xác định bài toánGv: Đối với bài toán tin học cũng tương tự * Khi máy tính giải bài toán cần quan tâm đến 2như trong toán học. Công việc xác định dữ yếu tố:5Giáo án dạy học theo chuyên đềkiện của bài toán là input, và cái cần tìm[yêu cầu của bài toán] là output.Gv: Ghi lần lượt ví dụ lên bảng và gọi hsxác định input và output.Gv: Nhận xét.Hs: Chú ý lắng nghe, ghi bài.- Input [thông tin đưa vào máy]- Output [thông tin muốn lấy từ máy]Ví dụ 1: Tìm Input, Output của phương trình códạng ax+b=0Input: Các hệ số a,b.Output: Nghiệm thỏa mãn phương trình.Ví dụ 2: Tìm Input, Output để kiểm tra tổng của2 số nguyên A, B có phải là số chẵn hay không?Ví dụ 3: Bài toán giải phương trình bặc haiax2+bx+c=0Input: a, b, c là các số thực.Output: nghiệm x của phương trình.Một số slide có sử dụng trong bàiSlide 66Giáo án dạy học theo chuyên đềSlide 8Slide 117Giáo án dạy học theo chuyên đềSlide 12Slide 148Giáo án dạy học theo chuyên đềSlide 16Nội dung 2: Lựa chọn hoặc thiết kế thuật toán [Tiết 1-6][1] Mục tiêu: - Khái niệm về thuật toán- Một số ví dụ về thuật toán- Xác định lý do lựa chọn thuật toán tối ưu- Thiết kế được thuật toán theo phương pháp liệt kê hoặc sử dụng sơ đồ khối[2] Phương pháp / Kỹ thuật : Đàm thoại, phát hiện vấn đề. Khai thác mối quan hệ giữa thựctiễn với tin học[3] Hình thành tổ chức hoạt động: Làm việc cá nhân, Thảo luận nhóm[4] Phương tiện: SGK, máy chiếu, máy tính[5] Kết quả: Học sinh biết lựa chọn và thiết kế được thuật toánHoạt động của giáo viên9Hoạt động của học sinhGiáo án dạy học theo chuyên đềGv: [Đặt vấn đề] Máy tính là một thiếtbị giúp con người xử lí thông tin. Do đókhi dùng máy tính làm một việc nào đó,ta chỉ cần quan tâm đến hai yếu tố: đưavào máy thông tin gì [Input] và cần lấyra thông tin gì [Output]. Muốn máy tínhlàm được công việc này, ta cần hướngdẫn cho máy các thao tác mà máy có thể2. Lựa chọn hoặc thiết kế thuật toánA. Khái niệm thuật toán: Là một dãy hữu hạncác thao tác được xắ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 đó, từinput của bài toán này ta nhận được output cântìm.- Tác dụng của thuật toán: Dùng để giải một bàitoán.thực hiện được. Để làm việc này ta cầnphải có thuật toán. Vậy thuật toán là?GV:Trình chiếu PP một số ví dụ.Ví dụ: [Trình chiếu PP]Xác định input, Output.* Cách viết thuật toán theo từng bước như trêngọi là cách liệt kê:[ Trình chiếu ở PP]* Ngoài ra thuật toán còn được diễn tả bằng sơđồ khối với các quy định.Elip: Các thao tác nhập xuất dữ liệu.Hình thoi: Thao tác so sánh.Hình chữ nhật: Các phép toánMũi tên: quy đình trình tự các thao tác.Lưu ý: 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ácthì thuật toán kết thúc hoặc có đúng một thao tácxác định để được thực hiện tiếp theo- Tính đúng đắn: Sau khi thuật toán kết thúc taphải nhận được output cần tìmMỘT SỐ VÍ DỤ MINH HỌAVí dụ 1: Kiểm tra tính nguyên tố của một sốnguyên dương* Xác định bài toán- Input: N là một số nguyên dương;- Output: “ N là số nguyên tố” hoặc“ N không là số nguyên tố”;* Ý tưởng:- Nếu N=1 thì N không là số nguyên tố;10Giáo án dạy học theo chuyên đềGV: Cho HS ví dụ để HS hiểu về thuậttoán và tính chất của thuật toán.- Nếu 1 < N < 4 thì N là nguyên tố;- Nếu N ≥ 4 và không có ước số trong phạm vitừ 2 đến phần nguyên căn bậc hai của N thì N làsố nguyên tố.* Thuật toána] Cách liệt kêB1: Nhập số nguyên dương N;B2: Nếu N = 1 thì thông báo N không nguyêntố rồi kết thúc;B3: Nếu N < 4 thì thông báo N là nguyên tố rồikết thúc;Gv: Hãy xác định I/O của bài toán?Gv:Nhận xét. Yêu cầu học sinh nghiêncứu và trình bày ý tưởng, thuật toán.B4: i←2;NB5: Nếu i > [] thì thông báo N là sốnguyên tố rồi kết thúc;B6: Nếu N chia hết cho i thì thông báo Nkhông nguyên tố rồi kết thúc;←B7: ii + 1 rồi quay lại bước 5.b] Sơ đồ khối:Hs: Có 5 phút nghiên cứu SGK, sau đólên bảng trình bày thuật toán bằngphương pháp liệt kê.Gv: Nhận xét, hướng dẫn HS hoàn thànhthuật toán.Mô phỏng việc thực hiện thuật toán11Giáo án dạy học theo chuyên đềHS: Một HS khác lên bảng dựa vào thuậttoán bằng phương pháp liệt kê vẽ sơ đồkhối và trình bày trước lớp.GV: Nhận xét, hướng dẫn HS hoàn thành Ví dụ 2: Bài toán sắp xếpTa chỉ xét bài toán dạng đơn giản:sơ đồ thuật toánCho dãy A gồm N số nguyên a1, a2,...,aN. Cần sắpxếp các số hạng để dãy A trở thành dãy khônggiảm.Thuật toán sắp xếp bằng tráo đổi [ExchangeSort]* 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 thành một dãykhông giảm.* Ý tưởng: 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. Lặp lại quá trình này cho đếnkhi không có sự đổi chỗ nào xảy ra nữa.* Thuật toána] Liệt kêB1. Nhập N, các số hạng a1, a2,...,aN;←B2. MN;B3. Nếu M < 2 thì đưa ra dãy A được sắp xếprồi kết thúc;- Đặt vấn đề: Sắp xếp thứ tự hs chào cờtheo thứ tự thấp trướccao sau.- Đưa ra ý tưởng, diễn tả thuật toán bằngliệt kê các bước.12B4. M←←M – 1, i←0;B5. i i + 1;B6. Nếu i > M thì quay lại bước 3;B7. Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;B8. Quay lại bước 5.b] Sơ đồ khốiGiáo án dạy học theo chuyên đềGv: Hãy xác định I/O của bài toán?- Gv và hs cùng giải quyết để đưa ra sơđồ khối.- Mô phỏng thuật toán sắp xếp bằng tráođổi với dãy A gồm 6 số:359817Gv:Nhận xét. Yêu cầu học sinh nghiêncứu và trình bày ý tưởng, thuật toán.Hs: Có 5 phút nghiên cứu SGK, sau đólên bảng trình bày thuật toán bằng Ví dụ 3: Bài toán tìm kiếmTa chỉ xét bài toán tìm kiếm dạng đơn giản:phương pháp liệt kê.Cho dãy A gồm N số nguyên khác nhau: a 1,Gv: Nhận xét, hướng dẫn HS hoàn thành a2,...,aN và một số nguyên k. Cần biết có haykhông chỉ số ithuật toán.[1 ≤ i ≤ N] mà ai = k. Nếu có hãy cho biết chỉ sốđó.Thuật toán tìm kiếm tuần tự [Sequential Search]* Xác định bài toán- Input: Dãy A gồm N số nguyên khác nhau a 1,a2,...,aN và số nguyên k;- Output: Chỉ số i mà ai = k hoặc thông báokhông có số hạng nào của dãy A có giá trị bằngk.HS: Một HS khác lên bảng dựa vào thuật * Ý tưởng: Ta so sánh giá trị k với lần lượt các sốtoán bằng phương pháp liệt kê vẽ sơ đồ hạng của dãy bắt đầu từ a 1. Nếu có giá trị nàobằng k thì dừng, ngược lại thì dãy A không có sốkhối và trình bày trước lớp.hạng nào bằng k.GV: Nhận xét, hướng dẫn HS hoàn thành * Thuật toána] Liệt kêsơ đồ thuật toánB1. Nhập N, các số hạng a1, a2,...,aN và khoá k;←B2. i1;B3. Nếu ai = k thì thông báo chỉ số i rồi kếtthúc;←B4. ii + 1;B5. Nếu i > N thì thông báo dãy A không có sốhạng nào có giá trị bằng k rồi kết thúc;13Giáo án dạy học theo chuyên đềB6. Quay lại bước 3.b] Sơ đồ khốiGv: Hãy xác định I/O của bài toán?Gv:Nhật xét. Yêu cầu học sinh nghiêncứu và trình bày ý tưởng, thuật toán.Hs: Có 5 phút nghiên cứu SGK, sau đólên bảng trình bày thuật toán bằngphương pháp liệt kê.Mô phỏng thuật toánGv: Nhận xét, hướng dẫn HS hoàn thànhthuật toán.HS: Một HS khác lên bảng dựa vào thuậttoán bằng phương pháp liệt kê vẽ sơ đồkhối và trình bày trước lớp.GV: Nhận xét, hướng dẫn HS hoàn thànhsơ đồ thuật toánB.Lựa chọn thuật toán:- Mỗi thuật toán chỉ giải 1 bài toán song 1 bàitoán thì có nhiều thuật toán để giải. Vậy ta phảichọn thuật toán tối ưu nhất trong các thuật toánđưa ra.* Thuật toán tối ưu: Là thuật toán có các tiêu chísau:- Dể hiểu:14Giáo án dạy học theo chuyên đề- Trình bài dể nhình.- Thời gian chạy nhanh.- Tốn ít bộ nhớ.Gv: Hãy xác định I/O của bài toán?* Biểu diễn thuật toán:- Theo phương pháp liệt kê hoặc sử dụng sơ đồGv:Nhật xét. Yêu cầu học sinh nghiênkhối.cứu và trình bày ý tưởng, thuật toán.GV: Đưa thêm cho học sinh thuật toántìm kiếm nhị phân:Thuật toán tìm kiếm nhị phânCách 1: Liệt kê các bướcB1: Nhập N, các số hạng a1, a2,..., aN vàkhóa k;B2: Đầu ß 1, Cuối ß N;B3: Giữa ß [[Đầu+Cuối]/2];B4: Nếu agiữa=k thì thông báo chỉ sốgiữa rồi kết thúc;B5: Nếu agiữa>k thì đặt Cuối = Giữa-1rồi chuyển sang B7;B6: Đầu ß Giữa + 1;B7: Nếu Đầu > Cuối thì thông báo dãyA không có số hạng có giá trị bằng k,rồi kết thúc;B8: Quay lại B3.GV: Yêu cầu HS đưa ra những khó khănvà thuận lợi khi lựa chọn một trong haithuật toán này. Dẫn dắt vào phần lựachọn thuật toán.15Giáo án dạy học theo chuyên đềMột số slide sử dụng trong bài16Giáo án dạy học theo chuyên đềSlide 18Slide 2017Giáo án dạy học theo chuyên đềSlide 23Slide 2418Giáo án dạy học theo chuyên đềSlide 25Slide 26Slide 2819Giáo án dạy học theo chuyên đềSlide 29Slide 3020Giáo án dạy học theo chuyên đềSlide 31Slide 3221Giáo án dạy học theo chuyên đềSlide 33Nội dung 3: Viết chương trình[1] Mục tiêu- Học sinh biết được các loại ngôn ngữ lập trình- Học sinh biết được việc lựa chọn ngôn ngữ lập trình để viết chương trình cho máy.[2] Phương pháp / Kỹ thuật : Đàm thoại, phát hiện vấn đề. Khai thác mối quan hệ giữa thựctiễn với tin học[3] Hình thành tổ chức hoạt động: Làm việc cá nhân, Thảo luận nhóm[4] Phương tiện: SGK, máy chiếu, máy tính[5] Kết quả: Học sinh nhớ được và xác định các loại ngôn ngữ lập trình thích hợp thông quahướng dẫn của giáo viên.Hoạt động của giáo viênGv: Để giải một bài toán máy tính khôngHoạt động của học sinhthể chạy trực tiếp thuật toán mà phải thựchiện theo chương trình. Vì vậy ta cầnchuyển đổi thuật toán sang chương trình.Một chương trình có thể viết từ nhiều 3. Viết chương trình22Giáo án dạy học theo chuyên đềngôn ngữ khác nhau gọi là ngôn ngữ lậptrình.a. Ngôn ngữ lập trình* Ngôn ngữ máy- Là ngôn ngữ duy nhất mà máy tính có thểGv: Một trong những ngôn ngữ đó là hiểu và thực hiện được.Hợp ngữ. Ngôn ngữ này thường sử dụng - Các loại ngôn ngữ khác muốn máy hiểu đượccác từ [thường là các từ viết tắt trong và thực hiện phải được dịch ra ngôn ngữ máytiếng Anh] làm thành các lệnh.thông qua chương trình dịch.ADD là phép cộng các số, giá trị củacác số này được ghi trên thanh ghi.Theo nhận định ở trên, ngôn ngữ nàyphải được chuyển sang ngôn ngữ máy thì * Hợp ngữmáy mới có thể hiểu và thực hiện- Sử dụng một số từ để thực hiện lệnh trên cácthanh ghi.Vd: ADD AX, BXGv: Hợp ngữ là ngôn ngữ mạnh nhưng [trong đó: ADD- phép cộng; AX, BX- cácnó không thích hợp với nhiều người sử thanh ghi]dụng → Xây dựng ngôn ngữ lập trình - Muốn máy hiểu được ngôn ngữ này cần phảibậc cao, vậy ngôn ngữ thế nào được coi chuyển nó sang ngôn ngữ máy.là ngôn ngữ bậc cao?Hs: Trả lời.Gv: Không nằm ngoài quy định, ngônngữ này muốn máy hiểu và thực hiện thìcũng phải chuyển sang ngôn ngữ máy.Muốn chuyển đổi từ các ngôn ngữ * Ngôn ngữ bậc caokhác sang ngôn ngữ máy thì phải dùng Là ngôn ngữ gần với ngôn ngữ tự nhiên, có tínhchương trình dịch.Gv: Khi viết chương trình cần lựa chọnngôn ngữ thích hợp.Hs: Chú ý, ghi bài23độc lập cao, ít phụ thuộc vào loại máy.Vd: Fortran, Cobol, Basic, Pascal, C, C++....Giáo án dạy học theo chuyên đềGv: Hướng dẫn HS thực hành trên máy b. Viết chương trìnhtính bằng chương trình TP- Là việc lựa chọn cấu trúc ngôn ngữ lập trìnhGiải phương trình bậc 2 có dạng: ax2 + để diễn đạt thuật toán trên máy.bx +c =0 [a0]- Khi viết chương trình cần lựa chọn ngôn ngữMàn hình soạn thảo để viết chương trình:thích hợp, tuân theo ngữ pháp của ngôn ngữ đó.Màn hình kết quả:Nội dung 4: Hiệu chỉnh[1] Mục tiêu: Hiểu được và lựa chọn được các test để chương trình hoàn thiện.[2] Phương pháp / Kỹ thuật : Đàm thoại, phát hiện vấn đề. Khai thác mối quan hệ giữa thựctiễn với tin học[3] Hình thành tổ chức hoạt động: Làm việc cá nhân, Thảo luận nhóm[4] Phương tiện: SGK, máy chiếu, máy tính[5] Kết quả: Học sinh biết lựa chọn bộ test phù hợp với nội dung từng bàiHoạt động của giáo viênGv:. Sau khi viết xong chương trình cầu phảiHoạt động của học sinhchạy thử chương trình bằng các dữ liệu đặctrưng. Để phát hiện sai sót để hiệu chỉnh. Gọi là Sau khi viết xong chương trình cầu phải24Giáo án dạy học theo chuyên đềhiệu chỉnh chương trình.chạy thử chương trình bằng các dữ liệuGv : Cho HS quan sát màn hình Tpđặc trưng. Để phát hiện sai sót để hiệuchỉnh. Gọi là hiệu chỉnh chương trình.Màn hình đưa ra các 3 bộ Test và ý nghĩa của nóGV: Yêu cầu HS lấy đủ các bộ test tiêu biểu đểđảm bảo chương trình đúng với tất cả cáctrường hợp.Nội dung 5: Viết tài liệu[1] Mục tiêu- Xác định được nội dung khi viết tài liệu cho chương trình cụ thể[2] Phương pháp/Kỹ thuật : Đàm thoại, phát hiện vấn đề. Khai thác mối quan hệ giữa thựctiễn với tin học[3] Hình thành tổ chức hoạt động: Làm việc cá nhân, Thảo luận nhóm[4] Phương tiện: SGK, máy chiếu, máy tính[5] Kết quả: Học sinh biết được lý do khi thực hiện bước viết tài liệu cho chương trình.Hoạt động của giáo viênGv: Viết mô tả chi tiết bài toán, thuậtHoạt động của học sinhViết mô tả chi tiết bài toán, thuật toán, chươngtoán, chương trình và hướng dẫn sử trình và hướng dẫn sử dụng.dụng.Hs: Chú ý, ghi bài..25