Bài giảng Tin học đại cương - Chương 7: Bài toán và thuật toán

Tin học đại cương

Introduction to Information Technology

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

Khoa Công Nghệ Thông Tin

Trường ĐHSP TP. Hồ Chí Minh

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

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

Bản quyền: Khoa CNTT 2011

2

Giới thiệu

. 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ể hoà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.

. Đó 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 toán và thuật toán .

Đông thời đƣa ra qui trình cơ bản để giải quyết 1 bài toán

trên máy tính nhƣ thế nào?

Bản quyền: Khoa CNTT 2011

3

Nội dung chính

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

. 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 toán trên máy tính.

. Chuyꢄn đꢆi bꢂi toá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 đề

. 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

. Pitago chia mọi vấn đề mà con ngƣời cần giải quyết

thành hai loại:

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)

. 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 đó:

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 toán

1. Bài toán kiểm tra tính nguyên tố

. Điều kiện ban đầu: Số nguyên dƣơng N

. Mục tiêu cần đạt: N có là số nguyên tố hay không?

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

. Đ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 toán trong tin học?

. Trong thực tế, không phải vấn đề nào cũng có thể là những bài

toán có tính toán (bài toán của toá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 toá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 toán trong tin học

1. Bài toán tìm ƣớc chung lớn nhất của hai số nguyên

dƣơng M,N

. Input: Hai số nguyên M,N

. Output: ƢCLN

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

. Input: Tên giáo viên, môn dạy

. Output: TKB của trƣờng

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

. Input: Số báo danh

. Output: Điểm thi

Bản quyền: Khoa CNTT 2011

9

Giải bài toán trên máy tính

nhƣ thế nào?

Bài toán

Input

Output

Bằng cách nào ?

Giải bài toán

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 toán là gì?

(Trích từ Wikipedia)

Từ thuật toá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 toán. Sau này, phương

pháp mô tả cách giải toá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

Muḥammad ibn Mūsā al-

Khwārizmī (Arabic:

بن

محمد

ي

الخوارزم

موسى

) was a Persian

mathematician, astronomer,

astrologer and geographer. He

was born around 780, in either

Khwarizm or Baghdad, and died

around 850.

theo cách phiên âm tên của ông.

Bản quyền: Khoa CNTT 2011

11

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

. 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ùng một bài toá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:

Những bài toán nào giải đƣợc bằng thuật toán, những bài

toán nào không giải đƣợc bằng thuật toán

Tìm thuật toán tốt nhất, tối ƣu

Triển khai thuật toá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

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

. Tính xác định(definiteness). Các bƣớc trong thuật toán

phải chính xác rõ ràng.

. Tính hữu hạn(finiteness). Thuật toán phải cho ra lời giải

(hay kết quả) sau một số bƣớc hữu hạn.

. 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

toán, không gian và thời gian sử dụng (khi thực hiện

thuật toán trên máy tính).

. Tính tổng quát(Generalliness) Thuật toán phải áp dụng

đƣợc cho tất cả các bài toá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 đó.

Bản quyền: Khoa CNTT 2011

14

Ví dụ về thuật toán giải

phƣơng trình bậc nhất

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

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

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

rồi qua bƣớc 5

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

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ản quyền: Khoa CNTT 2011

15

. Bƣớc 5 : Kết thúc.

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

. 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

Bản quyền: Khoa CNTT 2011

16

Các phƣơng pháp

biễu diễn thuật toán

. Ngôn ngữ tự nhiên

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

. Mã giả

Bản quyền: Khoa CNTT 2011

17

Biểu diễn thuật toán bằng

phƣơng pháp ngôn ngữ tự nhiên

. 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:

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<x<4)

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)

. 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

. Đƣợ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

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

Bản quyền: Khoa CNTT 2011

19

Các ký hiệu cơ bản trong

phƣơng pháp lƣu đồ

bắt đầu

kết thúc

điều kiện

nhập

thao tác

hoặc xuất

chƣơng

hƣớng xử lý

trình con

Bản quyền: Khoa CNTT 2011

20