P

-F

IT

Tin học đại cương
Introduction to Information Technology

Khoa Công Nghệ Thông Tin
Trường ĐHSP TP. Hồ Chí Minh

H

C

M

U

Nhóm biên soạn HP. Tin Học Đại Cương

Bộ môn Kĩ Thuật Dạy Học


H

C

M

U

P

-F

IT

Chương 7: Bài toán và thuật toán

Bản quyền: Khoa CNTT 2011

2


Giới thiệu

M

U

P

-F

IT

 Trong xu hƣớng phát triển của xã hội, cơng nghệ thơng tin
ngày càng đóng một vai trị rất quan trong giúp mọi ngƣời
có thể hồn thành cơng việc của mình trở nên nhanh

chóng, hiệu quả và dễ dàng hơn thơng qua các chƣơng
trình ứng dụng trên máy tính. Thuật toán và thuật giải là
nền tảng để những lập trình viên có thể xây dựng những
chƣơng trình ứng dụng phù hợp.

H

C

 Đó cũng chính là mục tiêu của chƣơng này nhằm cung
cấp các khái niệm ban đâu về bài tốn và thuật tốn .
Đơng thời đƣa ra qui trình cơ bản để giải quyết 1 bài tốn
trên máy tính nhƣ thế nào?

Bản quyền: Khoa CNTT 2011

3


Nội dung chính

IT

Chƣơng 7: Bài tốn và thuật tốn

H

C

M


U

P

-F

 Khái niệm vấn đề và bài toán.
 Thuật toán và các phương pháp biểu diễn thuật
toán.
 Các bước để giải một bài tốn trên máy tính.
 Chủn đởi bài tốn thành chương trình máy tính.

Bản quyền: Khoa CNTT 2011

4


Khái niệm vấn đề

-F

IT

 Vấn đề thƣờng đƣợc dùng với nghĩa rộng hơn bài toán,
bài toán là vấn đề mà để giải quyết nó phải liên quan ít
nhiều đến tính toán

P


 Pitago chia mọi vấn đề mà con ngƣời cần giải quyết
thành hai loại:

H

C

M

U

Theorema: vấn đề cần khẳng định tính đúng – sai
Problema: vấn đề cần tìm giải pháp để để đạt đƣợc mục
tiêu từ những điều kiện ban đầu nào đó

Bản quyền: Khoa CNTT 2011

5


Khái niệm vấn đề (tt)

P

-F

IT

 Theo nhiều kết quả nghiên cứu: việc giải quyết vấn đề bài toán mà Pitago nêu ra đều có thể diễn ra theo một
sơ đồ chung:

AB
 Trong đó:

H

C

M

U

A có thể là giả thiết, điều kiện ban đầu
B có thể là kết luận, mục tiêu cần đạt
 là suy luận, giải pháp cần xác định

Bản quyền: Khoa CNTT 2011

6


Ví dụ về vấn đề - bài tốn
1. Bài tốn kiểm tra tính nguyên tố

-F

IT

 Điều kiện ban đầu: Số nguyên dƣơng N
 Mục tiêu cần đạt: N có là số ngun tố hay khơng?


2. Bài tốn quản lý hồ sơ sinh viên

H

C

M

U

P

 Điều kiện ban đầu: Hồ sơ gốc của các sinh viên trong
trƣờng
 Mục tiêu cần đạt: Bảng thống kê, phân loại sinh viên theo
kết quả học tập

Bản quyền: Khoa CNTT 2011

7


Bài tốn trong tin học?

H

C

M


U

P

-F

IT

 Trong thực tế, khơng phải vấn đề nào cũng có thể là những bài
tốn có tính tốn (bài tốn của tốn học).
 Ví dụ:
 Làm sao giao dịch ngân hàng tự động không cần nhân viên
 Làm sao để con ngƣời nói chuyện đƣợc với nhau mà không cần
phải gặp mặt nhau.
 Làm sao để xếp loại học sinh của trƣờng học có 3000 học sinh
một cách nhanh chóng
…

Tất cả là bài tốn trong tin học
Là vấn đề mà ta muốn máy tính thực hiện để từ dữ liệu vào (Input) ta
nhân được dữ liệu – thông tin ra cần thiết (output)
Bản quyền: Khoa CNTT 2011

8


Ví dụ bài tốn trong tin học

-F


 Input: Hai số ngun M,N
 Output: ƢCLN

IT

1. Bài tốn tìm ƣớc chung lớn nhất của hai số nguyên
dƣơng M,N

P

2. Bài toán xếp thời khóa biểu cho trƣờng học

M

U

 Input: Tên giáo viên, mơn dạy
 Output: TKB của trƣờng

C

3. Bài tốn tìm điểm thi đại học của thí sinh

H

 Input: Số báo danh
 Output: Điểm thi

Bản quyền: Khoa CNTT 2011


9


Giải bài tốn trên máy tính
nhƣ thế nào?

Bằng cách nào ?

Output

P

-F

Input

IT

Bài toán

C

M

U

Giải bài toán

H


Hướng dẫn các thao tác
cho máy thực hiện

Thuật toán
Bản quyền: Khoa CNTT 2011

10


Thuật tốn là gì?

IT

(Trích từ Wikipedia)

H

C

M

U

P

-F

Từ thuật tốn (Algorithm) xuất phát từ tên
một nhà toán học người Trung Á là
Muhammad ibn Musa al-Khwarizmi,

thường gọi là al’Khwarizmi. Ông là tác giả
một cuốn sách về số học, trong đó ơng đã
dùng phương pháp mô tả rất rõ ràng, mạch lạc
cách giải những bài tốn. Sau này, phương
pháp mơ tả cách giải tốn của ông đã được
xem là một chuẩn mực và được nhiều nhà toán
học khác tuân theo. Từ algorithm ra đời dựa
theo cách phiên âm tên của ông.
Bản quyền: Khoa CNTT 2011

Muḥammad ibn Mūsā alKhwārizmī (Arabic: ‫محمد بن‬
‫ ) موسى الخوارزمي‬was a Persian
mathematician, astronomer,
astrologer and geographer. He
was born around 780, in either
Khwarizm or Baghdad, and died
around 850.
11


Khái niệm thuật toán

H

C

M

U


P

-F

IT

 Thuật toán là khái niệm cơ sở của toán học và tin học
 Thuật toán là một dãy các chỉ thị rõ ràng và có thể thi
hành được để hƣớng dẫn thực hiện hành động nhằm
đạt đƣợc mục tiêu đặt ra
 Thuật toán là sự thể hiện của một phương pháp để giải
quyết vấn đề

Bản quyền: Khoa CNTT 2011

12


Lƣu ý

C

M

U

P

-F


IT

 Cùng một bài tốn có thể có nhiều thuật toán khác nhau
để giải
 Thuật toán đơn giản, dễ hiểu, có độ chính xác cao,
đƣợc bảo đảm về mặt toán học, dễ triển khai trên máy,
thời gian thao tác ngắn, đƣợc gọi là thuật toán tối ưu
 Nghiên cứu thuật toán là một trong những vấn đề quan
trọng của tin học
 Lý thuyết về thuật toán giải quyết một số vấn đề sau:

H

Những bài toán nào giải đƣợc bằng thuật tốn, những bài
tốn nào khơng giải đƣợc bằng thuật tốn
Tìm thuật tốn tốt nhất, tối ƣu
Triển khai thuật tốn trên máy tính
Bản quyền: Khoa CNTT 2011

13


Đặc trƣng của thuật toán
 Nhập (input). Các thuật toán thƣờng có giá trị đầu vào

IT

 Xuất (output). Từ giá trị vào thuật tốn cho ra kết quả.

-F


 Tính xác định(definiteness). Các bƣớc trong thuật tốn
phải chính xác rõ ràng.

M

U

P

 Tính hữu hạn(finiteness). Thuật tốn phải cho ra lời giải
(hay kết quả) sau một số bƣớc hữu hạn.

H

C

 Tính hiệu quả(Effectiveness). Tính hiệu quả đƣợc đánh
giá dựa trên một số tiêu chuẩn nhƣ khối lƣợng tính
tốn, khơng gian và thời gian sử dụng (khi thực hiện
thuật tốn trên máy tính).
 Tính tổng qt(Generalliness) Thuật tốn phải áp dụng
đƣợc cho tất cả các bài tốn cùng dạng, chứ khơng chỉ
áp dụng đƣợc cho một
số trƣờng hợp riêng lẻ nào đó. 14
Bản quyền: Khoa CNTT 2011


Ví dụ về thuật tốn giải
phƣơng trình bậc nhất

 Bƣớc 1 : Nhập a, b.

-F

IT

 Bƣớc 2 : Nếu a = 0 thì

P

B2.1: Nếu b=0 thì thơng báo pt vơ số nghiệm

M

U

rồi qua bƣớc 5

C

B2.2: Nếu b khác 0 thì thông báo pt vô nghiệm

H

rồi qua bƣớc 5

 Bƣớc 3 : Gán cho x giá trị -b/a, rồi qua bƣớc 4.
 Bƣớc 4: Xuất ra giá trị x rồi qua bƣớc 5
 Bƣớc 5 : Kết thúc.


Bản quyền: Khoa CNTT 2011

15


Cấu trúc cơ bản của thuật toán

IT

-F

P

U

M



C



Tuần tự: thực hiện hết lệnh này đến lệnh khác
Rẽ nhánh: tùy theo dữ liệu đầu vào mà ta quyết định
thực hiện câu lệnh gì tiếp theo
Lặp: thực hiện lại nhiều lần một số câu lệnh nào đó
cho đến khi điều kiện khơng cịn thỏa mãn nữa

H




Bản quyền: Khoa CNTT 2011

16


Các phƣơng pháp
biễu diễn thuật tốn

IT

 Ngơn ngữ tự nhiên

-F

 Lƣu đồ - sơ đồ khối

H

C

M

U

P

 Mã giả


Bản quyền: Khoa CNTT 2011

17


Biểu diễn thuật tốn bằng
phƣơng pháp ngơn ngữ tự nhiên

U

P

-F

IT

 Liệt kê các thao tác, các chỉ thị bằng ngôn ngữ tự nhiên
Ví dụ: Có 43 que diêm. Hai ngƣời chơi luân phiên bốc
diêm. Mỗi lƣợt, mỗi ngƣời bốc từ 1 đến 3 que diêm.
Ngƣời nào bốc cuối cùng sẽ thắng cuộc
 Giải thuật để ngƣời đi trƣớc luôn thắng cuộc đƣợc diễn
tả bằng cách liệt kê từng bƣớc nhƣ sau:

H

C

M


Bước 1: Bốc 3 que rồi đợi đối phƣơng đi
Bước 2: Đối phƣơng bốc (giả sử x que, 0Bước 3: Đến lƣợt ngƣời đi trƣớc bốc a = (4-x) que.
Nếu cịn diêm thì quay lại Bước 2
Ngƣợc lại qua bước 4
Bước 4:Tuyên bố thắng cuộc. Kết thúc
Bản quyền: Khoa CNTT 2011

18


Biễu diễn thuật toán bằng
phƣơng pháp lƣu đồ (lowchart)

-F

IT

 Là một phƣơng tiện hình học giúp ta diễn tả giải thuật
một cách trực quan

P

 Đƣợc tạo bởi các kiểu khối cơ bản, nối với nhau bằng
các đƣờng có hƣớng

H

C

M

U

 Thuật ngữ tiếng Anh là Flow Chart

Bản quyền: Khoa CNTT 2011

19


-F

P

bắt đầu
kết thúc

IT

Các ký hiệu cơ bản trong
phƣơng pháp lƣu đồ

nhập
hoặc xuất

C

M

U

thao tác

điều kiện

H

chƣơng
trình con

Bản quyền: Khoa CNTT 2011

hƣớng xử lý

20


Ví dụ dùng phƣơng pháp lƣu đồ
để so sánh 2 số a và b

IT

Bắt đầu

P
U

Khơng

C

M

Số a có bằng
Số b khơng?

-F

Số a, Số b

H

Có

Số a bằng Số b

Số a khơng bằng Số b

Kết thúc
Bản quyền: Khoa CNTT 2011

21


Biểu diễn thuật tốn bằng
phƣơng pháp mã giả (pseudo code)
Ngồi việc sử dụng ngôn ngữ tự nhiên và lƣu đồ để
biểu diễn thuật tốn, ngƣời ta cịn sử dụng ngơn ngữ
tựa pascal, c, … đƣợc gọi là mã giả



Trong mã giả ta sử dụng cả cấu trúc của ngôn ngữ lập
trình và ngơn ngữ tự nhiên

H

C

M

U

P

-F

IT



Bản quyền: Khoa CNTT 2011

22


Ví dụ về dùng phƣơng pháp mã giả
để giải phƣơng trình bậc 2
if delta > 0 then begin

U
M
C

end
else
if delta = 0 then

P

-F

IT

X1(-b-sqrt(delta))/(2*a)
X2(-b+sqrt(delta))/(2*a)
xuất kết quả : phƣơng trình có hai nghiệm là x1 và x2

H

xuất kết quả : phƣơng trình có nghiệm kép là -b/(2*a)

else {trƣờng hợp delta < 0 }
xuất kết quả : phƣơng trình vơ nghiệm

Bản quyền: Khoa CNTT 2011

23

Các bƣớc giải
1 bài tốn trên máy tính

M

U

P

-F

IT

Bƣớc 1: Xác định vấn đề - bài toán
Bƣớc 2: Lựa chọn phƣơng pháp giải
Bƣớc 3: Xây dựng thuật toán hoặc thuật giải
Bƣớc 4: Cài đặt chƣơng trình
Bƣớc 5: Hiệu chỉnh chƣơng trình
Bƣớc 6: Thực hiện chƣơng trình

Lưu ý:

H

C









Các bước 4, 5, 6 sẽ được học chi tiết trong mơn lập trình căn bản

Bản quyền: Khoa CNTT 2011

24


Các bƣớc để thiết kế thuật toán

H

C

M

U

P

-F

IT

 Bƣớc 1: Xác định vấn đề bài tốn (input, output)
 Bƣớc 2: Hình thành ý tƣởng chính để để xây dựng thuật
tốn (bài toán giải bằng cách nào? Thuật toán sẽ dừng

khi nào?)
 Bƣớc 3: Xây dựng thuật tốn (ngơn ngữ tự nhiên, lƣu
đồ, mã giả)
 Bƣớc 4: Mô phỏng để kiểm tra tính đúng đắn của thuật
tốn (chạy thử bằng tay)

Bản quyền: Khoa CNTT 2011

25