Kiểm tra bài cũ


CHƯƠNG 1
BÀI 3
GIỚI THIỆU VỀ MÁY TÍNH
1. Nêu khái niệm hệ thống tin học ?
Hệ thống tin học dùng để nhập, xử lý, xuất, truyền và lưu trữ thông tin.
2. Nêu các thành phần của một hệ thống tin học ?
Phần cứng (Hardware) gồm máy tính và một số thiết bị liên quan;
Phần mềm (Software) gồm các chương trình. Chương trình là một dãy lệnh, mỗi lệnh là một chỉ dẫn cho máy tính biết thao tác cần thực hiện;
Sự quản lý và điều khiển của con người.
3. Kể tên một số thiết bị nhập, xuất dữ liệu (output/input device) ?
Thiết bị vào : bàn phím, chuột, máy quét, micro, webcam,…
Thiết bị ra: màn hình, máy in, máy chiếu, loa và tai nghe,…
4. Hãy nêu vai trò của CPU ?
Chức năng : CPU là thành phần quan trọng nhất của máy tính, đó là thiết bị chính thực hiện và điều khiển việc thực hiện chương trình.
4. Điền vào phần còn trống trong sơ đồ cấu trúc máy tính :
Bộ nhớ ngoài
Thiết bị ra
Thiết bị vào
Bộ điều khiển
Bộ số học
Bộ nhớ trong
Chương I


Bài 4. BÀI TOÁN và
THUẬT TOÁN
GV: Huỳnh Bảo Thiên
Email: baothien22784@yahoo.com
I. BÀI TOÁN
Xét các yêu cầu sau :
Trong TIN HỌC
Trong TOÁN HỌC
Yêu cầu 1 và 4 được xem là bài toán
Tất cả các yêu cầu trên đều được xem là bài toán
Trong các yêu cầu trên, yêu cầu nào được xem như là một bài toán?

VẬY BÀI TOÁN TRONG TIN HỌC LÀ GÌ ????
Khái niệm bài toán trong
Tin học?
Bài toán là việc nào đó ta muốn máy tính thực hiện.
Các yếu tố cần quan tâm khi giải một bài toán
 Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó.
CÁC VÍ DỤ
VD1 : Giải 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 : Số thực x thỏa : ax2+bx+ c = 0

VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.
Input : Các số trong dãy số.
Output : Giá trị nhỏ nhất trong dãy số.
VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Input :
Output :

VD4 : Xếp loại học tập các học sinh trong lớp.
Input :
Output :
UCLN của a và b.
Hai số nguyên dương a và b.
CÁC VÍ DỤ (tt)‏

?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
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ụ trong phiếu học tập.Tìm một ví dụ về bài toán, xác định các thành phần input, output, báo cáo và điền vào phiếu học tập.
Thời gian: 5 phút
HOẠT ĐỘNG NHÓM
Nêu một bài toán và chỉ rõ Input, Output của bài toán đó?
Xem thêm các ví dụ trong SGK/24, 25
TÓM LẠI
Một bài toán được cấu tạo bởi 2 thành phần cơ bản :

Input (Các thông tin đã có)‏
Output (Các thông tin cần tìm từ Input)‏
II. THUẬT TOÁN
Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải
Bài toán
Input
Output
Bằng cách nào?
Giải bài toán
Thuật toán
Từ Input
làm thế nào để tìm ra Output ?
Các bạn cần tìm ra cách giải
của bài toán.
Input
Output
THUẬT TOÁN
(Thao tác 1Thao tác 2...Thao tác n)‏
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 đó, từ Input của bài toán này, ta nhận được Output cần tìm.
BÀI TOÁN
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ác thao tác được sắp xếp theo một trình tự xác định.
Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.
Tính dừng
Tính xác định
Tính đúng đắn
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 thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện tiếp theo.
Tính đúng đắn: Khi thuật toán kết thúc, ta phải nhận được Output cần tìm
Xác định bài toán :
- Input
- Output
Các bước xây dựng thuật toán
Hình thành ý tưởng chính để giải quyết bài toán, lưu ý xác định điểm dừng của thuật toán.
Mô phỏng để kiểm tra tính đúng đắn.
Xây dựng thuật toán bằng 1 trong 2 cách:
- Cách liệt kê
- Vẽ sơ đồ
MÔ TẢ CÁC THAO TÁC
TRONG THUẬT TOÁN
Có 2 cách mô tả
Liệt kê
Dùng sơ đồ khối
Nêu ra tuần tự các thao tác cần tiến hành
Dùng một số biểu tượng thể hiện các thao tác
Giải toán thông thường:
Nếu a = 0 thì () không phải là pt bậc nhất.
+ Nếu b = 0 thì () vô số nghiệm.
+ Nếu b ≠ 0 thì () vô nghiệm.
Nếu a ≠ 0 thì () có nghiệm x = -b/a.
a) LIỆT KÊ

LIỆT KÊ :
Bước 1 : Nhập a, b.
Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4 : Đưa ra kết quả x và kết thúc.
VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 ()‏
: Thể hiện các thao tác so sánh
b) DÙNG SƠ ĐỒ KHỐI
Trong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như :
: Thể hiện các phép toán
: Quy định trình tự thực hiện các thao tác
: Thể hiện các thao tác nhập, xuất dữ liệu
VD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0

Bước 1 : Nhập a, b.
Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3.
Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4.
Bước 4 : Đưa ra kết quả x và kết thúc.
SƠ ĐỒ KHỐI
LIỆT KÊ
Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là chương trình.
LƯU Ý
CÁC THUẬT NGỮ CHÍNH
Là việc nào đó ta muốn máy tính thực hiện
Các thông tin đã có (các giả thiết)‏
Các thông tin cần tìm từ Input (kết luận)‏
*Một dãy hữu hạn các thao tác.
*Các thao tác được sắp xếp theo một trình tự xác định.
*Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.
Dùng các biểu tượng qui ước để thể hiện các thao tác trong thuật toán
Bài toán
Input
Output
Thuật toán
Sơ đồ khối
BÀI TẬP VỀ NHÀ
Bài 1, 3, 4, 5, 6
trang 27 – 28 (SGK)‏