Bài giảng Môn Tin học lớp 10 - Tuần 5 - Tiết 10 - Bài toán và thuật toán

, ta cần quan tâm đến hai yếu tố: 
-	Đưa vào máy thông tin gì? (Input) 
-	Cần lấy ra thông tin gì? (Output). 
b. Ví dụ:
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 hai ax2+bx+c = 0 (a≠0)
Input: Các số thực a, b, c (a≠0);
Output: Nghiệm của PT hoặc trả lời PT vô nghiệm.
Ví dụ 3. Bài toán kiểm tra tính nguyên tố của mốt số nguyên dương.
Input: Số nguyên dương N;
Output: Thông báo "N là số nguyên tố" hoặc "N không là số nguyên tố".
Ví dụ 4. Bài toán xếp loại học tập của một lớp.
Input: Bảng điểm của HS trong lớp;
Output: Bảng xếp loại học lự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.
Trong tin học, bài toán là gì?
Khẳng định lại khái niệm bài toán.
Vậy khi yêu cầu MT giải bài toán ta cần quan tâm đến những yếu tố nào?
Như vậy, để phát biểu một bài toán chúng ta cần trình bày rõ Input và Output của bài toán là gì?
Cụ thể các em hãy xét các ví dụ sau.
Trình bày ví dụ 1.
Nêu bài toán trong ví dụ 2 và gọi học sinh trình bày Input và Output của bài toán này là gì?
Khẳng định lại câu trả lời.
Tương tự trong ví dụ 3. Gọi học sinh trình bày Input và Output của bài toán này là gì?
Khẳng định lại câu trả lời.
Trong ví dụ 4. Hãy trình bày Input và Output của bài toán này là gì?
Khẳng định lại câu trả lời.
Tóm lại, Input là những thông tin như thế nào?. Output là những thông tin như thế nào?.
Khẳng định lại câu trả lời.
Đọc sách và giơ tay phát biểu.
Lắng nghe, ghi bài.
Đọc sách và giơ tay phát biểu.
Lắng nghe, ghi bài.
Lắng nghe, ghi bài.
Chú ý, lắng nghe, trả lời câu hỏi.
Ghi bài.
Chú ý, lắng nghe, trả lời câu hỏi.
Ghi bài.
Chú ý, lắng nghe, trả lời câu hỏi.
Ghi bài.
Chú ý, lắng nghe, giơ tay phát biểu.
Ghi bài.
2. Khái niệm thuật toán:
 a. Khái niệm: 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 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, ta nhận được Output cần tìm.
Có 2 cách để diễn tả thuật toán:
- Liệt kê các bước;
- Vẽ sơ đồ khối.
b. Ví dụ: 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,..., 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 ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai;
• Thuật toán: (Liệt kê các bước)
B1: Nhập N và dãy a1,..., aN;
B2: Max ¬ a1, i ¬ 2;
B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
B4: 4.1. Nếu ai > Max thì Max ¬ ai;
 4.2. i ¬ i + 1 rồi quay lại B3.
Đặt vấn đề:
Việc nêu bài toán là mô tả rõ Input và Output. Vậy: Làm thế nào để tìm ra Output? 
Việc chỉ ra một cách giải để từ Input của bài toán ta có Output được gọi là một thuật toán của bài toán đó.
Hãy nêu khái niệm thuật toán?
Khẳng định lại khái niệm và nhấn mạnh hơn về đặc điểm: Dãy hữu hạn các thao tác và trình tự sắp xếp các thao tác.
Xét bài toán tìm giá trị lớn nhất của một dãy số nguyên. 
Gọi HS xác định lại bài tóan.
Viết bảng. Nhận xét, chốt lại ý chính.
Trình bày ý tưởng của bài toán.
Từ ý tưởng đó chúng ta có thể xây dựng thuật toán như sau.
Nêu và phân tích thuật toán.
Chú ý lắng nghe. 
Trả lời câu hỏi.
Lắng nghe, ghi bài.
Đọc sách và giơ tay phát biểu.
Lắng nghe, trả lời.
Chú ý lắng nghe, ghi bài.
Chú ý lắng nghe, ghi bài.
Chú ý lắng nghe, ghi bài.
IV.	Củng cố:
-	Phát biểu lại khái niệm bài toán? Xác định bài toán là cần xác định điều gì?
-	Khái niệm thuật toán? Viết thuật toán tìm giá trị Max của một dãy số nguyên theo cách liệt kê các bước?
V.	Dặn dò:
-	Học kỹ nội dung bài học hôm nay. Trả lời câu hỏi 1, 2 trang 44 sách giáo khoa.
-	Đọc sách trước phần còn lại của mục 2.	
	Tuần: 6	Tiết: 11
-------------------------------------------------------------------------------------------------------------------------------------------------------------
Ngày soạn:	11/9/2008
Chương 1: Một số khái niệm cơ bản của Tin học
§4. Bµi to¸n vµ thuËt to¸n (tt)
I.	Mục đích, yêu cầu:
	1. Kiến thức	
HS hiểu và thực hiện được thuật toán đơn giản: Tìm giá trị lớn nhất của một dãy số;
HS hiểu được các tính chất của một thuật toán.
2. Kỹ năng
Hình thành khả năng xây dựng thuật toán cho một bài toán đơn giản.
Phát triển cho HS khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống.
II.	Phương pháp - phương tiện dạy học:
Đặt câu hỏi, gợi mở. Tóm tắt và ghi ý chính;
Đặt vấn đề, giải quyết vấn đề;
Giáo viên chuẩn bị: Giáo án, sách giáo viên, minh họa mô phỏng thuật toán;
Học sinh chuẩn bị: Đọc trước nội dung bài, vở ghi, sách giáo khoa.
III.	NộI dung dạy – học:
Nội dung bài giảng
Hoạt động của thầy
Hoạt động của trò
Ổn định lớp.
Ghi sổ đầu bài.
Chào thầy
Báo cáo sĩ số
Kiểm tra bài cũ:
1. Nêu khái niệm thuật toán? Viết thuật toán theo cách liệt kê để giải bài toán: Tìm giá trị lớn nhất của một dãy số nguyên.
2. Nêu khái niệm bài toán? Cho ví dụ và phát biểu bài toán? Input là những thông tin như thế nào? output là những thông tin như thế nào?
Gọi tên 1 HS lên trả lời khái niệm và viết thuật toán lên bảng.
Gọi HS thứ 2 lên trả lời câu 2.
Nhận xét và cho điểm HS thứ 2.
Gọi HS nhận xét thuật toán của HS thứ nhất trên bảng.
Nhận xét, sửa bài, cho điểm.
Lên bảng trả lời và viết thuật toán.
Trả lời câu hỏi.
Nhận xét, bổ sung.
Lắng nghe.
2. Khái niệm thuật toán (tt).
a. Khái niệm:
b. Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên.
Qui ước hình khối sử dụng trong sơ đồ khối:
 Thao tác nhập, xuất dữ liệu;
 Các phép tính toán; 
Thao tác so sánh;
Các mũi tên (→) quy định trình tự thực hiện các thao tác.
• Thuật toán: (Mô tả bằng sơ đồ khối)
Hình 21_ trang 34_sách giáo khoa.
Tiết trước các em đã được học về khái niệm thuật toàn và đã làm quen với thuật toán tìm giá trị lớn nhất của một dãy số nguyên mô tả theo cách liệt kê. Hôm nay chúng ta tiếp tục xây dựng thuật toán này theo cách khác đó là, mô tả theo sơ đồ khối.
 
Hãy cho biết, người ta dùng những hình khối nào, với ý nghĩa như thế nào để xây dựng sơ đồ khối?
Nhận xét, chốt lại ý chính.
Từ các qui ước đó, các em hãy xây dựng sơ đồ khối mô tả thuật toán tìm giá trị lớn nhất của một dãy số nguyên.
Chia thành 4 nhóm để làm bài.
Quan sát HS hoạt động nhóm.
Giới thiệu sơ đồ khối mô tả thuật toán giải bài toán tìm giá trị lớn nhất của dãy số nguyên.
Nhận xét, chốt lại sơ đồ đúng.
Trình chiếu, mô phỏng cách thực hiện thuật toán theo sơ đồ khối.
Lắng nghe, mở sách giáo khoa, vở ghi, ghi bài.
Đọc sách và trả lời câu hỏi.
Lắng nghe, ghi bài.
Lắng nghe, làm bài theo nhóm.
Các nhóm trình bày bày làm.
Nhận xét bài làm từng nhóm
Lắng nghe, ghi bài.
Chú ý, lắng nghe, quan sát.
c. Lưu ý: Các thao tác trong thuật toán phải được mô tả đủ chi tiết để đối tượng thực hiện thuật toán có thể thực hiện được. 
Ví dụ. Trong thuật toán giải phương trình bậc hai, cần tính đại lượng Δ. Tuỳ thuộc đối tượng thực hiện mà việc tính Δ có thể được mô tả chi tiết khác nhau, chẳng hạn:
• Với đối tượng đã biết công thức tính Δ thì chỉ cần mô tả một bước là: Tính Δ;
• Với đối tượng chưa biết công thức tính Δ thì cần phải mô tả chi tiết hơn, chẳng hạn: 
B1.	Tính b2; 
B2.	Tính 4ac; 
B3.	Giá trị Δ là kết quả của B1 trừ đi kết quả của B2.
d.Tính chất: Qua định nghĩa, ta thấy thuật toán có các tính chất sau:
• 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.
Các thao tác trong thuật toán phải được mô tả đủ chi tiết để đối tượng thực hiện thuật toán có thể thực hiện được.
Thuyết trình và viết bảng để phân tích ví dụ.
Dù đối tượng thực hiện không hề biết khái niệm Δ là gì nhưng thực hiện theo các bước nêu trên thì vẫn nhận được giá trị Δ cần tính.
Một em hãy nhắc lại khái niệm về thuật toán.
Ghi ý chính lên bảng:
- Dãy hữu hạn các thao tác.
- Sắp xếp theo trình tự xác định
- Từ Input cho ra Output.
Qua đó em nào cho biết thuật toán có những tính chất nào?
Chốt lại và phân tích 3 tính chất cơ bản của thuật toán.
Em nào cho biết với thuật toán tìm giá trị lớn nhất ở trên thì 3 tính chất đó thể hiện ở chỗ nào?
Nhận xét, chốt lại câu trả lời.
Lắng nghe.
Chú ý, lắng nghe, ghi bài.
Giơ tay, phát biểu.
Lắng nghe, quan sát.
Lắng nghe, trả lời câu hỏi.
Lắng nghe, ghi bài
Lắng nghe, Trả lời câu hỏi.
IV.	Củng cố:
Mô tả thuật toán tìm giá trị lớn nhất của dãy số nguyên theo sơ đồ khối?;
Nêu các tính chất của thuật toán?
V.	Dặn dò:
Làm bài tập 1 - 5 trang 44 sách giáo khoa.
Xem sách trước ví dụ: Kiểm tra tính nguyên tố của một số nguyên dương.
	Tuần: 6	Tiết: 12
-------------------------------------------------------------------------------------------------------------------------------------------------------------
Ngày soạn:	12/9/2008
Chương 1: Một số khái niệm cơ bản của Tin học
§4. Bµi to¸n vµ thuËt to¸n (tt)
I.	Mục đích, yêu cầu:
	1. Kiến thức	
HS hiểu và thực hiện được thuật toán: Kiểm tra tính nguyên tố của một số nguyên dương;
2. Kỹ năng
Hình thành khả năng xây dựng thuật toán cho một bài toán đơn giản.
Phát triển cho HS khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống.
II.	Phương pháp - phương tiện dạy học:
Đặt câu hỏi, gợi mở. Tóm tắt và ghi ý chính;
Giáo viên chuẩn bị: Giáo án, sách giáo viên, minh họa mô phỏng thuật toán;
Học sinh chuẩn bị: Đọc trước nội dung bài, vở ghi, sách giáo khoa, bảng phụ.
III.	NộI dung dạy – học:
Nội dung bài giảng
Hoạt động của thầy
Hoạt động của trò
Ổn định lớp.
Ghi sổ đầu bài.
Chào thầy
Báo cáo sĩ số
Kiểm tra bài cũ:
1. Vẽ sơ đồ khối mô tả thuật toán tìm giá trị lớn nhất của một dãy số nguyên.
2. Nêu khái niệm thuật tóan và các tính chất cơ bản của thuật toán?
Đặt câu hỏi. Gọi tên 1 HS lên vẽ sơ đồ khối.
Gọi HS thứ 2 lên trả lời câu 2.
Nhận xét và cho điểm HS thứ 2.
Gọi HS nhận xét sơ đồ của HS vẽ trên bảng.
Nhận xét, sửa bài, cho điểm.
Lắng nghe, lên bảng trả lời câu hỏi.
Nhận xét bài làm.
Lắng nghe.
3. Một số ví dụ về thuật toán
Ví 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ố;
- Nếu 1<N<4 thì N là số nguyên tố;
- Nếu N ³ 4 và không có ước số trong phạm vi từ 2 đến [] thì N là số nguyên tố.
• Thuật toán
a) Thuật toán diễn tả theo 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 là số nguyên tố rồi kết thúc;
B3.	Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc;
B4.	i ¬ 2;
B5.	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 N không nguyên tố rồi kết thúc;
B7.	i ¬ i + 1 rồi quay lại B5.
b) Sơ đồ khối
Trang 37_sách giáo khoa.
Nêu bài toán và gọi HS hãy xác định Input và output của bài toán.
Lắng nghe và viết bảng câu trả lời của HS.
Số nguyên tố là số như thế nào?
Nhận xét, chốt lại ý chính.
Một số nguyên dương N là số nguyên tố nếu nó có đúng hai ước số là 1 và chính nó.
Để giải bài toán này ta làm thế nào?
Sử dụng phương pháp vấn đáp và phân tích ý tưởng để xây dựng thuật toán.
[] là phần nguyên căn bậc hai của N. VD: [] = 3
Từ ý tưởng đó, các em gấp sách lại, hình thành 4 nhóm viết thuật thuật toán theo cách liệt kê để giải bài toán này?
Quan sát, hướng dẫn, cùng thảo luận với từng nhóm.
Nhận xét, bài làm của từng nhóm, chốt lại cách làm đúng.
Biến i nhận giá trị nguyên thay đổi trong phạm vi từ 2 đến []+1 và dùng để kiểm tra N có chia hết cho i hay không.
Thực hiện mô phỏng thuật toán xét tính nguyên tố của số 29 và số 45.
Bây giờ, các em gấp sách lại và hãy vẽ sơ đồ khối mô tả thuật toán này.
Gọi 1 HS lên bảng vẽ.
Quan sát và hướng dẫn.
Nhận xét, đưa ra sơ đồ đúng.
Mô phỏng thuật toán theo sơ đồ khối, với các số 29 và 45
Lắng nghe, ghi bài, trả lời câu hỏi.
Quan sát, lắng nghe, ghi bài.
Trả lời câu hỏi.
Lắng nghe, ghi bài.
Lắng nghe, đọc sách, trả lời câu hỏi.
Lắng nghe, ghi bài.
Hoạt động thảo luận làm bài theo nhóm.
Các nhóm trình bày bài làm.
Lắng nghe, theo dõi, ghi bài.
Chú ý, quan sát, lắng nghe.
1 HS vẽ sơ đồ khối trên bảng còn lại vẽ trên giấy nháp.
Lắng nghe, ghi bài.
Chú ý, quan sát, lắng nghe.
IV.	Củng cố:
Dùng bảng phụ chỉ có hình khối (không có nội dung) mô tả thuật toán kiểm tra tính nguyên tố của một số nguyên dương và gọi học sinh hoàn thiện thuật toán.
Gọi HS khác nêu thuật toán theo cách liệt kê.
V.	Dặn dò:
Xem sách trước ví dụ 2: Bài toán sắp xếp.
	Tuần: 7	Tiết: 13
-------------------------------------------------------------------------------------------------------------------------------------------------------------
Ngày soạn:	19/9/2008
Chương 1: Một số khái niệm cơ bản của Tin học
§4. Bµi to¸n vµ thuËt to¸n (tt)
Mục đích, yêu cầu:
	1. Kiến thức	
HS hiểu và thực hiện được thuật toán: Sắp xếp bằng tráo đổi.
2. Kỹ năng
Hình thành khả năng xây dựng thuật toán;
Phát triển cho HS khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống.
II.	Phương pháp - phương tiện dạy học:
Đặt câu hỏi, gợi mở. Tóm tắt và ghi ý chính;
Giáo viên chuẩn bị: Giáo án, sách giáo viên, minh họa mô phỏng thuật toán;
Học sinh chuẩn bị: Đọc trước nội dung bài, vở ghi, sách giáo khoa, bảng phụ.
NộI dung dạy – học:
Nội dung bài giảng
Hoạt động của thầy
Hoạt động của trò
Ổn định lớp.
Ghi sổ đầu bài.
Chào thầy
Báo cáo sĩ số
Kiểm tra bài cũ:
1. Vẽ sơ đồ khối mô tả thuật toán kiểm tra tính nguyên tố của một số nguyên dương.
2. Viết thuật toán theo cách liệt kê giải bài toán kiểm tra tính nguyên tố của một số nguyên dương.
Đặt câu hỏi.
Gọi tên 2 HS lên bảng làm bài.
Gọi HS nhận xét từng phần trên bảng.
Nhận xét, sửa bài, cho điểm.
Lắng nghe.
Lên bảng làm bài.
Nhận xét bài làm
Lắng nghe.
3. Một số ví dụ về thuật toán
Ví dụ 2: Bài toán sắp xếp.
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
• 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 đứ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 lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
• Thuật toán (Cách liệt kê)
B1:Nhập N, các số hạng a1,a2,..., aN;
B2:	M ¬ N;
B3:	Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
B4:	M ¬ M - 1, i ¬ 0;
B5:	i ¬ i + 1;
B6:	Nếu i > M thì quay lại B3;
B7:	Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8:	Quay lại B5.
• Thuật toán (Sơ đồ khối)
Trang 39_sách giáo khoa.
Trong cuộc sống, ta thường gặp những việc liên quan đến sắp xếp như học sinh xếp hàng theo thứ tự từ thấp đến cao; giáo viên xếp loại học lực học sinh trong lớp,... Dưới đây ta chỉ xét bài toán sắp xếp dạng đơn giản sau: 
Cho dãy A gồm N số nguyên a1, a2,...,aN. Cần 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).
Ví dụ: Với A là dãy gồm các số nguyên: 6, 1, 5, 3, 7, 8, 10, 7, 12, sau khi sắp xếp ta có dãy: 1, 3, 5, 6, 7, 7, 8, 10, 12.
Thực hiện mô phỏng trên máy.
Với bài toán TQ trên HS hãy xác định input và output của bài toán.
Nhận xét, chốt lại ý đúng.
Để giải bài toán này ta làm thế nào?
Sử dụng phương pháp vấn đáp và phân tích ý tưởng để xây dựng thuật toán.
Từ ý tưởng đó em nào hãy nêu thuật thuật toán theo cách liệt kê để giải bài toán này?
Nhận xét, nêu thuật tóan đúng.
Vì sao khởi tạo biến i có giá trị là 0 trong khi chỉ số của số hạng đầu tiên là 1?
Thực hiện minh họa với dãy: 6, 1, 5, 3, 7, 8, 10, 7, 12.
Các em hãy thảo luận theo nhóm để vẽ sơ đồ khối mô tả thuật toán này.
Quan sát và hướng dẫn.
Nhận xét, sửa bài từng nhóm, chốt lại sơ đồ đúng nhất.
Lắng nghe, ghi bài.
Chú ý quan sát, lắng nghe.
Lắng nghe, trả lời câu hỏi.
Phát biểu ý tưởng giải bài toán.
Lắng nghe, đọc sách, nêu thuật tóan.
Trả lời: Để dễ viết thuật toán, ở B5, giá trị i tăng lên 1 đơn vị, nên trên thực tế đúng là số hạng đầu tiên của dãy là a1.
Thảo luận nhóm, làm bài trên bảng phụ.
Trình bày bài làm.
Lắng nghe, quan sát.
Củng cố: 
Dùng bảng phụ chỉ có hình khối (không có nội dung) mô tả thuật toán sắp xếp bằng tráo đổi và gọi học sinh hoàn thiện thuật toán;
Gọi HS khác nêu thuật toán theo cách liệt kê.
Dặn dò:
Xem sách trước ví dụ 3: Bài toán tìm kiếm.
	Tuần: 7	Tiết: 14
-------------------------------------------------------------------------------------------------------------------------------------------------------------
Ngày soạn:	20/9/2008
Chương 1: Một số khái niệm cơ bản của Tin học
§4. Bµi to¸n vµ thuËt to¸n (tt)
Mục đích, yêu cầu:
	1. Kiến thức	
HS hiểu và thực hiện được thuật toán: tìm kiếm tuần tự, tìm kiếm nhị phân.
2. Kỹ năng
Hình thành khả năng xây dựng thuật toán;
Phát triển cho HS khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống.
II.	Phương pháp - phương tiện dạy học:
Đặt câu hỏi, gợi mở. Tóm tắt và ghi ý chính;
Giáo viên chuẩn bị: Giáo án, sách giáo viên, minh họa mô phỏng thuật toán;
Học sinh chuẩn bị: Đọc trước nội dung bài, vở ghi, sách giáo khoa, bảng phụ.
NộI dung dạy – học:
Nội dung bài giảng
Hoạt động của thầy
Hoạt động của trò
Ổn định lớp.
Ghi sổ đầu bài.
Chào thầy
Báo cáo sĩ số
Kiểm tra bài cũ:
1. Vẽ sơ đồ khối mô tả thuật toán sắp xếp bằng tráo đổi.
2. Viết thuật toán theo cách liệt kê giải bài toán sắp xếp bằng tráo đổi.
Đặt câu hỏi.
Gọi tên 2 HS lên bảng làm bài.
Gọi HS nhận xét từng phần trên bảng.
Nhận xét, sửa bài, cho điểm.
Lắng nghe, lên bảng làm bài.
Nhận xét.
Lắng nghe.
3. Một số ví dụ về thuật toán:
Ví dụ 3: Bài toán tìm kiếm.
Thuật toán tìm kiếm tuần tự:
• Xác định bài toán
- Input: Dãy A gồm N số nguyên đôi một khác nhau a1, a2,..., aN và số nguyên k.
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
• Ý tưởng: 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 k cho đến khi hoặc gặp một số hạng bằng k hoặc dãy đã được xét hết và không có giá trị nào bằng k. Trong trường hợp thứ hai dãy A không có số hạng nào bằng k.
• Thuật toán:
a) Cách liệt kê:
B1.	Nhập N, các số hạng a1, a2,..., aN và khoá k;
B2.	i ¬ 1;
B3.	Nếu ai = k thì thông báo chỉ số i, rồi kết thúc.
B4.	i ¬ i + 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.
B6.	Quay lại B3.
b) Sơ đồ khối:
Trang 41_Sách giáo khoa.
Thuật toán tìm kiếm nhị phân:
Cách liệt kê:
B1: Nhập N, các số hạng a1, a2,..., aN và khoá k;
B2: Dau ¬ 1; Cuoi ¬ N;
B3: Giua ¬ (Dau+Cuoi)/2;
B4: Nếu aGiua = k thì đưa ra chi so Giua, rồi kết thúc;
B5: Nếu aGiua > k thì Cuoi ¬ Giua – 1, chuyển sang B7;
B6: Dau ¬ Giua + 1;
B7: Nếu Dau > Cuoi thì thông báo dãy A không có số hạng nào bằng k, rồi kết thúc;
B8: Quay lại B3.
Sơ đồi khối: 
Trang 43_sách giáo khoa.
Tìm kiếm là việc thường xảy ra trong cuộc sống, VD tìm cuốn sgk Tin học 10 trên giá sách, tìm tên của 1 HS trong danh sách lớp. TQ: cần tìm một đối tượng cụ thể nào đó trong tập các đối tượng cho trước. Dưới đây ta chỉ xét bài toán tìm kiếm dạng đơn giản sau:
 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ố nguyên k được gọi là khoá tìm kiếm (gọi tắt là khoá). 
Với bài toán TQ trên hãy xác định Input và output của bài toán.
Nhận xét câu trả lời của HS. Chốt lại ý chính.
Ví dụ: cho dãy A gồm các số: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51.
• Với khoá k = 2, trong dãy trên có số hạng a5 có giá trị bằng k. Vậy chỉ số cần tìm là i = 5.
• Với khoá k = 6 thì không có số hạng nào của dãy A có giá trị bằng k.
Để giải bài toán này ta làm t