Ngày soạn: 22/9/2008
Bài 4: BÀI TOÁN VÀ THUẬT TOÁN (Tiết 1)
A. MỤC TIÊU
1. Kiến thức:
Biết được khái niệm bài toán và thuật toán.
Hiểu cách biểu diễn thuật toán bằng ngôn ngữ liệt kê.
2. Kỷ năng:
Xác định được Input và Output của bài toán.
Biểu diễn được thuật toán bằng ngôn ngữ liệt kê.
B. PHƯƠNG PHÁP:
Nêu và giải quyết vấn đề.
C. CHUẨN BỊ CỦA GIÁO VIÊN VÀ HỌC SINH:
1. Chuẩn bị của GV: SGK
2. Chuẩn bị của HS: SGK
D. TIẾN TRÌNH LÊN LỚP:
1. Ổn định lớp: Kiểm tra sĩ số
2. Kiểm tra bài cũ:
Hãy trình bày hiểu biết của em về nguyên lý Phôn Nôi-man?
3. Bài mới:
a, Đặt vấn đề:
Ta biết máy tính hoạt động theo chương trình. Để viết được chương trình cho máy tính thực hiện ta cần biết thế nào là bài toán, thuật toán.
b, Triển khai bài:
HOẠT ĐỘNG CỦA THẦY VÀ TRÒ
NỘI DUNG KIẾN THỨC


Hoạt động 1: Khái niệm bài toán
GV: Khái niệm bài toán trong toán học?
HS: Trả lời “Đó là những việc mà con người phải thực hiện sao cho từ một dữ kiện đã có phải tìm ra hay chứng minh 1 kết quả nào đó”
GV: Trong nhà trường có phần mềm quản lý học sinh, nếu ta yêu cầu đưa ra những học sinh có điểm trung bình từ 7 trở lên → đó là bài toán. Hay đơn giản là yêu cầu máy cho ra kết quả của một phép tính nhân chia → đó cũng là bài toán. Vậy trong tin học theo em hiểu bài toán là gì?
HS: Suy nghĩ trả lời.
GV: Hãy nêu ví dụ về bài toán?
HS: Nêu ví dụ
GV: Để giải một bài toán (thông thường) trước tiên ta cần xác định cái gì?
HS: Xác định giả thiết (cái đã cho) và cái cần tìm, cần chứng minh.
GV: Vậy để giải một bài toán trong tin học đầu tiên ta cần xác định cái gì?
HS: Xác định thông tin đưa vào máy và thông tin cần lấy ra khỏi máy.




GV: Ghi các ví dụ lên bảng. Input? Output?
HS: Đứng tại chỗ trả lời câu hỏi.
GV: Ghi câu trả lời lên bảng và giải thích thêm.






GV: Khi ta đã có Input muốn máy tính đưa ra Output cần phải có chương trình, mà muốn viết được chương trình cần có thuật toán.
Hoạt động 2: Khái niệm thuật toán
GV: 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 giải bài toán đó. Hãy nêu khái niệm thuật toán?
HS: Dựa vào SGK để trả lời.




















GV: Đây là cách biểu diễn thuật toán dưới dạng liệt kê.
1. Khái niệm bài toán:

















* Khái niệm: Bài toán là những việc mà con người muốn máy tính thực hiện.
Ví dụ: Giải phương trình bậc 2, quản lý thông tin về học sinh.







* Để giải một bài toán ta cần xác định:
- Input (thông tin đưa vào máy)
- Output (thông tin muốn lấy ra từ máy)
* Các ví dụ:
Ví dụ 1: Bài toán tìm số lớn nhất trong 3 số a, b, c.
Input: 3 số a, b, c
Output: Số lớn nhất trong 3 số
Ví dụ 2: Bài toán kiểm tra một số N nguyên dương có phải là số nguyên tố hay không?
Input: Số nguyên dương N
Output: “N là số nguyên tố” hoặc “N không phải là số nguyên tố”
Ví dụ 3: Xếp loại học sinh một lớp.
Input: Bảng điểm của học sinh trong lớp.
Output: Bảng xếp loại học lực.



2. Khái niệm thuật toán:




* 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.
Ví dụ: Thuật toán tìm USCLN của 2 số nguyên dương M, N.


- Xác định bài toán:
Input: M, N
Output: USCLN(M,N)
- Ý tưởng:
Nếu M = N thì USCLN = M