GIAO AN

§4. BÀI TOÁN VÀ THUẬT TOÁN Tuần 5/Tiết 9,10
Ngày soạn: 17/09/2010
Ngày giảng: 23/09/2010
I. Mục đích, yêu cầu:
1. Về kiến thức
- Hiểu được hai khái niệm then chốt: bài toán và thuật toán.
- Nắm được các tính chất cơ bản của thuật toán.
- Biết cách diễn tả thuật toán bằng một trong hai phương pháp: liệt kê và sơ đồ khối.
2. Về kỹ năng
- Diễn tả được thuật toán theo cách liệt kê hoặc bước đầu thể hiện thuật toán bằng sơ đồ khối.
- Hiểu và diễn tả được thuật toán của một số bài toán cơ bản.
3. Về thái độ
- Rèn luyện tư duy khoa học đúng đắn, chính xác, lôgic.
- Tác phong làm việc độc lập, sáng tạo.
- Nâng cao lòng say mê học tập bộ môn.
II. Phương pháp:
- Thuyết trình, gợi mở, vấn đáp, so sánh.
III. Lên lớp:
1. Ổn định lớp: kiểm tra sỉ số
2. Kiểm tra bài cũ:
Học viên 1: Cho biết khái niệm về chương trình.
Học viên 2: Cho biết cách vào ra hệ thống
3. Dạy bài mới:

NỘI DUNG CỦA BÀI DẠY
HOẠT ĐỘNG THẦY TRÒ

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.
Vd: Đưa một dòng chữ ra màn hình, giải phương trình bậc 2, quản lý cán bộ của một cơ quan, quản lý thông tin về học sinh,...là bài toán.
- Các yếu tố cần quan tâm khi giải bài toán trên máy tính:
+) Input (thông tin đưa vào máy).
+) Output (thông tin muốn lấy từ máy).
Vd1: Bài toán tìm ước chung lớn nhất của hai số nguyên dương M và N.
+) Input : Hai số nguyên dương M & N
+) Output : UCLN(M,N).
Vd2: Cho biết Input & Output của bài toán giải PTB2 ax2 + bx + c = 0.
+) Input : ? Các số thực: a,b,c (a(0)
+) Output: ? tất cả các số thực x thoả mãn ax2 + bx + c = 0. x có thể là 1 hoặc hai số thực hoặc câu trả lời không có số thực nào như vậy.
- ĐVĐ:
Để máy tính hoạt động được xcần phải đưa vào máy tính các chương trình. Vậy để viết được chương trình cho máy tính thực hiện được trước hết ta cần hiểu đúng về bài toán đưa vào và thuật toán giải quyết bài toán đó.
Trong toán học ta nhắc nhiều đến khái niệm bài toán "đó là những việc mà con người 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?
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ừ 5 trở lên, đó là bài toán. Đơn giản hơn là yêu cầu máy tính cho ra kết quả của các phép tính nhân, chia,... Đó là bài toán. Vậy bài toán là gì?
Để giải một bài toán thì công việc đầu tiên là gì?
Hv: trả lời - Input & Output của bài toán


NỘI DUNG CỦA BÀI DẠY
HOẠT ĐỘNG THẦY TRÒ

Vd3: Bài toán kiểm tra tính nguyên tố
Input: ? số nguyên dương N.
Output: ? "N là số nguyên tố" hoặc "N không là số nguyên tố".
Vd4: Xếp loại học tập của các hv trong lớp.
Input: ? Bảng điểm của học sinh.
Output: ? Bảng xếp loại học tập.
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.
Vd: Tìm giá trị lớn nhất của một dãy số nguyên.
+) Xác định:
Input: số nguyên dương N và dãy N số nguyên a1, a2,...., aN.
Output: max của dãy số.
+) Ý tưởng:
Khởi tạo giá trị max = ai
Lần lượt với i =
, so sánh giá trị ai với giá trị max, nếu ai > max thì max nhận giá trị ai.
+) Thuật toán:
Để giải bài toán này ta có thể mô tả bài toán bằng các phương pháp biểu diễn thuật toán liệt kê và sơ đồ khối.
Mô tả thuật toán bằng liệt kê