Tiết 10, 11, 12, 13, 14
&4. BÀI TOÁN VÀ THUẬT TOÁN
Ngày soạn : 28/9/2007
Tiết : 10
Lớp : 10
I. MỤC ĐÍCH YÊU CẦU
* Kiến thức:
- Hiểu đúng khái niệm bài toán trong Tin học.
- Hiểu rõ khái niệm thuật toán là cách giải bài toán mà về nguyên tắc có thể giao cho máy tính thực hiện;
- Hiểu và thực hiện được một số thuật toán đơn giản trong SGK như tìm giá trị lớn nhất của một dãy số nguyên, sắp xếp dãy số, tìm một giá trị cho trước trong số dãy số.
* Kĩ năng:
Xây dựng thuật toán cho một số bài toán đơn giản. Qua đó, hình thành một số kĩ năng chuẩn bị tiếp thu việc học ngôn ngữ lập trình: cách dùng biến, khởi tạo giá trị biến.
* Kiến thức:
Các kiến thức trên góp phần phát triển khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như cuộc sống.
II. CHUẨN BỊ
Thầy:
- Soạn giáo án, nghiên cứu sách giáo khoa, sách bài tập, tài liệu tham khảo.
- Máy tính cá nhân và máy chiếu ( nếu có).
Trò: Đọc trước ở nhà Sách giáo khoa.
III.TIẾN TRÌNH LÊN LỚP.
1. Ổn định tổ chức, kiểm tra sĩ số (1’).
2. Kiểm tra bài cũ (5’).
Câu hỏi: Nêu các nguyên lí hoạt động của máy tính?
Đáp án:
* Nguyên lí mã hoá nhị phân: Mọi thông tin khi đưa vào máy tính đều được biến đổi thành dãy bit nhị phân .
* Nguyên lí điều khiển bằng chương trình:
- Máy tính hoạt động theo chương trình.
* Nguyên lí lưu trữ chương trình:
- Lệnh được đưa vào máy tính dưới dạng mã nhị phân để lưu trữ, xử lí như những dữ liệu khác.
* Nguyên lí truy cập theo địa chỉ.
- Việc truy cập dữ liệu trong máy tính được thực hiện thông qua địa chỉ nơi lưu trữ dữ liệu đó.
* Nguyên lí Phôn Nôi-man:- Mã hoá nhị phân, điều khiển bằng chương trình, lưu trữ chương trình và truy cập theo địa chỉ tạo thành một nguyên lí chung gọi là nguyên lí Phôn Nôi-man.
- Đối tượng HS: HS trung bình.
3. Nội dung bài học mới.
Nội dung
Hoạt động của GV
Hoạt động của HS







1. Khái niệm bài toán (15’)
- Bài toán là một việc nào đó ta muốn máy tính thực hiện để từ thông tin đưa vào tìm được thông tin ra.









* Các yếu tố liên quan đến giải bài toán trên máy tính:
- Input: đưa thông tin vào máy.
- Output: thông tin muốn lấy ra từ máy.

Vídụ1: Bài toán tìm UCLN của hai số nguyên dương M và N.
- Input: Hai số nguyên dương M và N.
- Output: UCLN(M, 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.
- Output: Nghiệm x của phương trình:



2. Khái niệm thuật toán (20’)
a)Khái niệm thuật 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.
b)Các 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á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 kết thúc thuật toán, ta phải nhận được Output cần tìm.
c) Cách thức diễn tả thuật toán:
- Liệt kê từng bước: Từng bước diễn tả bằng ngôn ngữ tự nhiên.
- Sơ đồ khối:


thể hiện thao tác so sánh


thể hiện các phép tính toán.


thể hiện thao tác nhập; xuất dữ liệu.
Các mũi tên qui định trình tự thực hiện các thao tác.
GV: Trong toán học ta nhắc nhiều đến khái niệm “bài toán” và ta hiểu đó là những việc mà mình cần phải thực hiện sao cho từ những dữ kiện đã có phải tìm ra hay chứng minh một kết quả nào đó.Vậy khái niệm “bài toán” trong Tin học có gì khác không?
GV: Gọi HS nêu ví dụ về bài toán quen thuộc trong