MÔN TIN HỌC LỚP 10
CHƯƠNG I:
Bài 4. BÀI TOÁN VÀ THUẬT TOÁN

I. MỤC ĐÍCH – YÊU CẦU
1. Kiến thức :
Hiểu đúng khái niệm “Bài toán” trong Tin học và 2 thành phần cơ bản : Input, Output.
Hiểu rõ khái niệm “Thuật toán” – Cách biểu diễn thuật toán (liệt kê, sơ đồ khối). Nắm chắc các biểu tượng thể hiện thao tác trên sơ đồ khối, “đọc” được sơ đồ khối đơn giản.
Hiểu được quan hệ giữa các khái niệm : “Bài toán” – “Thuật toán” – “Ngôn ngữ lập trình”
Học sinh hình dung rõ hơn một bước về cách thức hoạt động của máy tính.
2. Kỹ năng :
Biết cho ví dụ một số bài toán trong Tin học, từ đó xác định được Input, Output.
Mô tả được các thao tác trong thuật toán của một số bài toán đơn giản bằng 2 cách : liệt kê, vẽ sơ đồ khối.
Có khái niệm ban đầu về biến, cách dùng biến.

II. ĐỒ DÙNG DẠY HỌC
Giáo viên chuẩn bị máy vi tính, projector, CD tài liệu liên quan.
Học sinh chuẩn bị bảng phấn, phiếu học tập, tham khảo (photo trước).

III. CÁC PHƯƠNG PHÁP DẠY HỌC
Phương pháp vấn đáp gợi mở là chủ yếu, kết hợp việc tạo tình huống có vấn đề, hướng dẫn trực quan bằng các slide mô phỏng thuật toán giúp học sinh tham gia tích cực vào giờ học.

IV. HOẠT ĐỘNG DẠY HỌC :
Hoạt động của GV
Hoạt động của HS
Nội dung

Hoạt động 1 : Kiểm tra bài cũ
Mục tiêu : Giúp HS ôn lại kiến thức trong bài “Giới thiệu về máy tính”. Nhấn mạnh lại qui trình xử lí : Nhập ( Tính toán, xử lí ( Xuất để liên hệ qua bài mới
Gọi 1 học sinh trả bài, 1 học sinh vẽ lại sơ đồ xử lí thông tin trên máy tính


Chú ý theo dõi
Câu hỏi kiểm tra :
Khái niệm hệ thống tin học?
Các thành phần của 1 hệ thống tin học?
Kể tên một số thiết bị nhập, xuất dữ liệu (Input/Output Device) ?
Vai trò của CPU?
Qui trình, sơ đồ xử lí thông tin trên hệ thống tin học ?

Nhấn mạnh : Nhập ( Tính toán ( Xuất dữ liệu Xử lí thông tin (sơ đồ 1)

Hoạt động 2 : Khái niệm Bài toán trong Tin học
Dẫn nhập
Bổ sung sơ đồ 1 ( 2
1. Mục tiêu : Giúp HS hiểu khái niệm Bài toán tin học.

2. Cách tiến hành
* Giới thiệu khái niệm Bài toán trong Tin học
* Sự khác biệt giữa bài toán trong Tin học và các bài toán thông thường : HS chia nhóm thảo luận và đánh dấu chọn đúng các bài toán tin học
* GV tổng kết ( Kết luận








Làm việc theo nhóm
Các nhóm báo cáo kết quả.
Lắng nghe, ghi chép

 Nhập ( Tính toán ( Xuất dữ liệu Xử lí thông tin
Bài toán INPUT ==========( OUTPUT
(sơ đồ 2)
§4. BÀI TOÁN – THUẬT TOÁN
I. BÀI TOÁN
1. Khái niệm
Chọn đúng các bài toán trong Tin học:
( Giải phương trình bậc 2
( Quản lí sách trong thư viện
( Tìm USCLN của 2 số nguyên dương
( Xếp loại học tập của HS
Kết luận : Trong phạm vi Tin học các yêu cầu trên đều được xem là bài toán. “Bài toán là một việc mà ta muốn máy tính thực hiện”

Hoạt động 3 : Input, Output của bài toán
1. Mục tiêu : Giúp HS nắm rõ 2 thành phần cơ bản này.
2. Cách tiến hành :
Yêu cầu các nhóm thảo luận xác định dữ liệu vào, ra của các ví dụ trên.
* GV nhận xét, hướng dẫn HS tìm Input, Output ( Kết luận 2 các thành phần cơ bản Input, Output
* Yêu cầu mỗi HS suy nghĩ, đặt một bài toán với Input, Output của nó. Ghi kết quả vào phiếu học tập của mình.
Làm việc theo nhóm
Các nhóm báo cáo kết quả.




Lắng nghe, ghi chép

Suy nghĩ nhanh, ghi Phiếu học tập


2. Các thành phần của 1 bài toán tin học
- Vào a, b, c ( x1, x2
- Vào tên đầu sách, loại, số lượt mượn ( tổng đầu sách mỗi loại, top 10 đầu sách hay nhất…
- Vào 2 số nguyên dương a, b ( USCLN m
- Vào điểm số các môn ( G, Kh, TB, Y, K
Kết luận :
Các bài toán cấu tạo bởi 2 thành phần : INPUT : Các thông tin đã có (giả thiết) OUTPUT : Các thông tin cần tìm (kết luận, yêu cầu)

Hoạt động 4 : Khái niệm Thuật toán
1. Mục tiêu :
Giúp HS hiểu khái niệm thuật toán
2. Cách tiến hành :
Bổ sung sơ đồ 2, trình bày khái niệm thuật toán thông qua sơ đồ này
Lắng nghe, quan sát, ghi chép
II. THUẬT TOÁN
Khái niệm
…
Bài toán
INPUT ==========( OUTPUT
Bằng cách nào?

Giải bài toán Hướng dẫn các thao tác Thuật toán cho máy thực hiện
Kết luận :
Bài toán (sơ đồ 3)
Thuật toán
INPUT ==========( OUTPUT
(thao tác 1; … ; thao tácn)

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 (tính dừng) - Các thao tác được tiến hành theo một trình tự xác định (tính xác định) - Sau khi thực hiện xong dãy các thao tác đó ta nhận được Output của bài toán (tính đúng đắn)

Hoạt động 5 : Mô tả các thao tác trong thuật toán
1. Mục tiêu : Giúp HS biết, hiểu 2 cách mô tả thuật toán: Liệt kê, dùng sơ đồ
2. Cách tiến hành :
* Yêu cầu HS thảo luận theo nhóm và nêu các bước tiến hành tìm nghiệm PTB2 ax2 + bx + c = 0.
* Gợi ý, giúp HS sắp xếp ‎ tưởng hợp ly
* Chú ý : Giải thích sơ lược về ý nghĩa của biến, phép gán (()
* Diễn đạt bằng cách liệt kê đôi khi dài dòng và do có sự khác biệt ngôn ngữ và cách diễn đạt ( diễn đạt bằng sơ đồ khối thống nhất, rõ ràng. GV chuyển từ các bước đã liệt kê sang sơ đồ khối
* Nêu ‎ý nghĩa các biểu tượng trong sơ đồ













* 2 cách trên diễn đạt trên được sử dụng cho con người, còn máy phải thông qua ngôn ngữ lập trình.






Thực hiện yêu cầu của GV theo nhóm

Mỗi nhóm liệt kê các bước tiến hành

Lắng nghe, ghi chép





















- Có được khái niệm về Ngôn ngữ lập trình và Chương trình máy tính.
Mô tả các thao tác trong thuật toán
Bước 1 : Nhập a, b, c;
Bước 2 : Tính ( ( b2 – 4ac;
Bước 3 : Nếu ( < 0 thì thông báo vô nghiệm, rồi kết thúc;
Bước 4 : Nếu ( = 0 thì thông báo nghiệm kép x = -b/2a, rồi kết thúc;
Bước 5 : Thông báo có 2 nghiệm x1, x2 = (-b(√()/2a, rồi kết thúc;

Biến : Một ô nhớ lưu giữ giá trị của 1 đại lượng có thể thay đổi trong quá trình thực hiện thuật toán.
Phép gán ((): - Tính giá trị biểu thức bên phải dấu ( - Lưu giá trị tính được vào tên biến bên trái

Cách liệt kê :
Nêu tuần tự các bước cần tiến hành.
Cách vẽ sơ đồ khối


Ý nghĩa các biểu tượng


Ngôn ngữ lập trình được dùng để diễn tả các thuật toán cho máy tính hiểu và thực hiện được. Kết quả diễn tả thuật toán như vậy gọi là một chương trình máy tính.

Hoạt động 6 : Khảo sát ví dụ tìm giá trị lớn nhất của một dãy số nguyên
1. Mục tiêu : Củng cố kiến thức đã tiếp thu, vận dụng vào bài toán cụ thể
2. Cách tiến hành
* Yêu cầu HS xác định bài toán : Input, Output
* Dùng slide mô phỏng cho ý tưởng bài toán. Hướng dẫn HS từng bước liệt kê các thao tác.
* GV tổng kết ( xây dựng thuật toán từ các bước đã liệt kê
* Chuyển thuật toán sang cách biểu diễn bằng sơ đồ tương ứng. GV gợi ý và thực hiện các bước lặp, nhảy, so sánh
* Yêu cầu HS tự vẽ lại sơ đồ khối cho bài toán tìm giá trị nhỏ nhất của dãy số này
* Nhấn mạnh các bước xây dựng một thuật toán : - Xác định bài toán - Hình thành ý tưởng - Xây dựng thuật toán





- Chú ý quan sát, trả lời theo hướng dẫn từng bước của GV







* HS tham gia xây dựng sơ đồ khối những bước đơn giản

* HS thực hiện trên Phiếu học tập.
Xác định bài toán:
Input: Số nguyên dương N và dãy N số nguyên a1, a2, …, aN. (ai với i: 1(N)
Output: Số lớn nhất (Max) của dãy số.
Ý tưởng:
- Đặt giá trị Max = a1.
- Lần lượt cho i đi từ 2 đến N, so sánh giá trị ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
Xây dựng thuật toán:
a) Cách liệt kê: Bước 1: Nhập N và dãy a1,a2…, aN; Bước 2: Max ( a1; i ( 2; Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc; Bước 4: Nếu ai > Max thì Max ( ai; Bước 5: i ( i+1 rồi quay lại B3.
a) Sơ đồ:



Hoạt động 7 : Thuật toán kiểm tra tính nguyên tố của một số nguyên dương
1. Mục tiêu : Giúp HS nắm bắt ý tưởng thuật toán. Đi từ đơn giản ( phức tạp. Vấn đề cải tiến thuật toán ( tính hiệu quả của thuật toán
2. Cách tiến hành :
* Nhắc lại các bước tiến hành xây dựng 1 thuật toán
* Yêu cầu các nhóm xác định bài toán đặt ra, nhắc lại định nghĩa số nguyên tố
* GV bổ sung thêm các tính chất cần thiết để hình thành ‎ý tưởng thuật toán 1 (đơn giản)
* Gợi ý tìm ước số i > 1 đầu tiên của N và quan hệ i với N trong 2 trường hợp N nguyên tố và không nguyên tố. Xác định điểm dừng và tính đúng đắn của thuật toán


* Gọi từng nhóm tham gia xây dựng thuật toán (với sự hướng dẫn của GV)

* So sánh thuật toán do HS xây dựng với thuật toán đúng thể hiện trên slide








* Mô phỏng thuật toán với các trường hợp N=9, N=7











* Nêu vấn đề khi áp dụng thuật toán này cho những số N lớn ( Yêu cầu cải tiến ( thuật toán 2 (hiệu quả hơn)

* GV trình bày các bước hình thành thuật toán.


























* Kết luận về tính hiệu quả của một thuật toán
* Dặn dò HS xem lại, đối chiếu những điểm khác nhau giữa sơ đồ thuật toán trên slide và trong SGK – Làm thêm các bài toán tương tự theo gợi ý trên Phiếu học tập










* Thảo luận theo nhóm, xác định Input, Output
* Phát biểu lại định nghĩa số nguyên tố




* Nhận xét, tham gia hình thành ‎ý tưởng thuật toán



* Các nhóm tham gia xây dựng thuật toán












* Quan sát, theo dõi

















* Góp ý hình thành ‎ý tưởng thuật toán mới



* Quan sát, theo dõi, so sánh, phát hiện những điểm khác nhau giữa sơ đồ trên slide và SGK










III. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN
A. KIỂM TRA TÍNH NGUYÊN TỐ
1. 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ố
ĐN : “Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N”
TC : - Nếu N = 1 ( N không là số nguyên tố - Nếu 1 < N < 4 ( N là số nguyên tố
2. Ý tưởng
N<4 : Xem như bài toán đã được giải quyết
N>=4 : Tìm ước i đầu tiên > 1 của N * Nếu i < N ( N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N) * Nếu i = N ( N là số nguyên tố
3. Xây dựng thuật toán
a) Cách liệt kê :
Bước 1 : Nhập số nguyên dương N;
Bước 2 : Nếu N=1 thì thông báo “N không là số nguyên tố”, kết thúc;
Bước 3 : Nếu N<4 thì thông báo “N là số nguyên tố”, kết thúc;
Bước 4 : i ( 2 ;
Bước 5 : Nếu i là ước của N thì đến bước 7
Bước 6 : i ( i +1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị)
Bước 7 : Nếu i = N thì thông báo “N là số nguyên tố”, ngược lại thì thông báo “N không là số nguyên tố”, kết thúc;
b) Sơ đồ :



“Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N ( N là số nguyên tố”
* Cải tiến thuật toán
Ý