Bài giảng Tin học đại cương - Phần 2: Giải quyết bài toán

Phần 2: Giải quyết bài toá n

Nội dung chí nh

1. Chương 1: Giải quyết bài toá n

• Khái niệm về bài toá n

• Quá trình giải quyết bài toán bằng má y tí nh

• Phương pháp giải quyết bài toán bằng MT

2. Chương 2: Thuật toá n

• Khá i niệm

• Biểu diễn thuật toá n

• Thuật toán đệ quy

• Thuật giải heuristic

• Một số thuật toá n thô ng dụng

01-Jan-16

33

Sai

Bạch Tuyết

đẹp hơn

Thỏa mã n

Đúng

Tì m cá ch hại

Ngừng

Đến nhà 7 chú lùn

Lừa Bạch Tuyết

Về lâ u đài

01-Jan-16

34

Chương 2: Thuật toá n

Nội dung chí nh

1. Khá i niệm

2. Biểu diễn thuật toá n

3. Thuật toán đệ quy

4. Thuật giải heuritic

5. Một số thuật toán thông dụng

01-Jan-16

35

Chương 2: Thuật toá n

1. Khá i niệm

Khá i niệm

• Thuật toán (algorithm) là khá i niệm cơ sở

của Toá n học và Tin học

• Nghiên cứu thuật toán đóng vai trò quan

trọng trong khoa học má y tí nh

– Má y tí nh chỉ có khả năng thực hiện công

việc theo một thuật toá n.

– Thuật toá n chỉ đạo máy tính từng bước phải

làm gì .

Thuật toán là gì ?

01-Jan-16

36

Chương 2: Thuật toá n

1. Khá i niệm

Khá i niệm

• Một tập các lệnh hay chỉ thị nhằm hướng

dẫn việc thực hiện một công việc nào đó

• Bao gồm một dãy hữu hạn các chỉ thị rõ

ràng và có thể thi hành được, được bố trí

theo một trì nh tự nhất định, cần thực hiện

trên những dữ liệu vào sao cho sau một số

hữu hạn bước ta thu được kết quả của bài

toá n cho trước

• Thuật toán là sự thể hiện của một phương

pháp để giải quyết một vấn đề

01-Jan-16

37

Chương 2: Thuật toá n

1. Khá i niệm

Ví dụ

Tì m phần tử lớn nhất trong một dãy hữu hạn

các số nguyên

1. Đặt giá trị lớn nhất tạm thời (Max) bằng số

nguyên đầu tiên của dã y

Max là giá trị lớn nhất ở mỗi giai đoạn thực hiện

2. Nếu tất cả số nguyên nào trong dãy đã được xét,

thực hiện bước 5

3. So sánh số nguyên kế tiếp trong dãy với Max

• Nếu lớn hơn Max thì thay Max bằng số nguyên này.

4. Lặp lại bước 2

5. Thô ng bá o: Max là giá trị lớn nhất trong dã y số.

01-Jan-16

38

Chương 2: Thuật toá n

1. Khá i niệm

Ví dụ

Đổi số thập phâ n sang dạng nhị phâ n

1

2

1. Cho biết N

2. Chia N cho 2

3

4

5

3. Ghép phần dư vào bên trái kết quả

4. Lấy phần thương làm N mới

5. Nếu N khác 0, lặp lại Bước 2

6. Xong

6

01-Jan-16

39

Chương 2: Thuật toá n

1. Khá i niệm

Định nghĩa (KHMT)

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 và trì nh tự thực hiện

cá c thao tá c đó sao cho sau khi thực hiện

dã y thao tá c này theo trì nh tự đã chỉ ra,

với đầu vào (input) ta thu được kết quả

đầu ra (output) mong muốn

01-Jan-16

40

Chương 2: Thuật toá n

1. Khá i niệm

Thao tác/lệnh

• Là hành động cần được thực hiện bởi cơ chế

của thuật toá n

• Cá c thao tá c (lệnh) sẽ biến đổi bài toán từ trạng

thá i trước tới trạng thái sau

• Dã y cá c thao tác cần thiết sẽ biến đổi bài toán từ

trạng thá i ban đầu đến kết quả

• Cá c thao tác có thể phân tích thành thao tác

khác nhỏ hơn

• Thứ tự thao tác là quan trọng

– Cùng tập thao tác, thứ tự khác nhau dẫn đến kết quả

khá c nhau

• Cơ cấu thể hiện trình tự thực hiện các thao tá c

gọi là Cấu trúc điều khiển

Có 3 loại cơ bản: Tuần tự, Lặp, Rẽ nhá nh

–

01-Jan-16

41

Chương 2: Thuật toá n

1. Khá i niệm

Các đặc trưng của thuật toá n

Khi mô tả thuật toá n, cần chú ý các đặc trưng

– Nhập (input)

– Xuất (output)

– Tí nh xá c định (definiteness)

– Tính hữu hạn (finiteness)

– Tính hiệu quả

– Tính tổng quá t

01-Jan-16

42

Chương 2: Thuật toá n

1. Khá i niệm

Nhập/Xuất

• Nhập (input):

– Cá c giá trị “đầu vào” (input values) từ một

tập hợp nhất định nào đó.

• Xuất (output):

– Những giá trị trả về (output values) thuộc

một tập hợp nhất định nào đó thể hiện lời

giải cho bài toán/vấn đề

– Tương ứng với tập hợp cá c giá trị nhập

01-Jan-16

43

Chương 2: Thuật toá n

1. Khá i niệm

Tí nh xá c định (definiteness)

• Các bước trong thuật toá n phải chính

xá c rõ ràng, khô ng gâ y sự nhập

nhằng nhầm lẫn

• Cùng một điều kiện nhập, cùng một

giải thuật thì 2 bộ VXL (người, má y)

phải cho ra cùng một kết quả

01-Jan-16

44

Chương 2: Thuật toá n

1. Khá i niệm

Tính hữu hạn (finiteness)

• Trong mọi trường hợp của dữ liệu

vào, thuật toá n phải cho ra hay kết

quả sau một thời gian hữu hạn

– Thời gian có thể phụ thuộc vào từng

bài toá n cụ thể hoặc phụ thuộc vào cá c

thuật toán khá c nhau cho một bài toá n

01-Jan-16

45

Chương 2: Thuật toá n

1. Khá i niệm

Tính hiệu quả

• Thực hiện thuật toán cần

– Thời gian

– Cá c cô ng cụ hỗ trợ (giấy, bộ nhớ,..)

• Để ghi kết quả trung gian

• Độ phức tạp thuật toán: Thời gian và cá c cô ng

cụ hỗ trợ

– Thuật toán càng hiệu quả độ phức tạp càng bé

– Trong máy tính, thường quan tâm tới

• Thời gian thực hiện

– Số thao tác cơ bản cần thựchiện

• Độ lớn của bộ nhớ mà thuật toán sử dụng

01-Jan-16

46

Chương 2: Thuật toá n

1. Khá i niệm

Tính tổng quá t

Thuật toá n có tí nh tổng quá t cao nếu có

thể giải bất kỳ bài toá n nào trong một lớp

lớn cá c bài toá n

Ví dụ

Thuật toá n giải phương trình ax²+bx+c=0 phổ

dụng hơn thuật toán giải phương trì nh x²+5x+6=0

01-Jan-16

47

Chương 2: Thuật toá n

Nội dung chí nh

1. Khá i niệm

2. Biểu diễn thuật toá n

3. Thuật toán đệ quy

4. Thuật giải heuristic

5. Một số thuật toán thông dụng

01-Jan-16

48

Chương 2: Thuật toá n

2. Biểu diễn thuật toá n

Đặt vấn đề

• Tại sao:

– Truyền đạt thuật toán cho người khá c

– “Truyền đạt” thuật toán cho má y tí nh

• Chuyển thành chương trình điều khiển

• Phương phá p:

1. Ngôn ngữ tự nhiên

2. Ngôn ngữ lưu đồ(sơ đồ khối)

3. Ngô n ngữ tựa ngô n ngữ lập trình (mã giả)

4. Ngôn ngữ lập trì nh

01-Jan-16

49

Chương 2: Thuật toá n

2. Biểu diễn thuật toá n

1. Ngô n ngữ tự nhiên

• Nguyên tắc:

– Sử dụng ngôn ngữ tự nhiên để liệt kê cá c

bước của thuật toá n

• Đặc điểm

– Khô ng yêu cầu phải có một số kiến thức

đặc biệt

– Dài dò ng

– Không làm nổi bật cấu trúc của thuật toá n

01-Jan-16

50

Chương 2: Thuật toá n

2. Biểu diễn thuật toá n

1. Ngô n ngữ tự nhiên→Ví dụ 1

Giải phương trình ax+ b = 0

• B1: Nhập a

• B2: Nhập b.

• B3: Nếu a =0 thực hiện B6

• B4: Thô ng bá o: Nghiệm –b/a

• B5: Thực hiện B10

• B6: Nếu b = 0, thực hiện B9

• B7: Thô ng bá o: Phương trình vô nghiệm.

• B8: Thực hiện B10

• B9: Thô ng bá o: Phương trình vô số nghiệm.

• B10: Kết thúc

01-Jan-16

51

Chương 2: Thuật toá n

2. Biểu diễn thuật toá n

1. Ngô n ngữ tự nhiên→Ví dụ 2

Tì m giá trị lớn nhất của một dãy N số nguyên

• B1:Nhập N

• B2: Nhập dãy số a_igồm N số.

• B3:Gá n giá trị a₁cho Max, 2 cho biến i (i2)

• B4:Nếu i > N, thực hiện bước 8

• B5:Nếu a_i> Max, gá n giá trị a_ichoMax.

• B6:Tăng i lên 1 đơn vị.

• B7:Quay lên B4.

• B8:Thô ng bá o: Max là giá trị lớn nhất dã y

• B9:Kết thúc.

01-Jan-16

52

Bài giảng Tin học đại cương - Phần 2: Giải quyết bài toán - Chương 2: Thuật toán