CHƯƠNG 4: GIẢI QUYẾT VẤN ĐỀ, BÀI TOÁN BẰNG MÁY TÍNH

GV: Trần Phước Tuấn EMAIL: tranphuoctuan.khoatoan.dhsp@gmail.com

Nội dung bài học

Page 2

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

1

1. Vấn đề - bài toán 2. Thuật toán - thuật giải 3. Các phương pháp biểu diễn thuật toán 4. Các bước để giải một bài toán trên máy tính 5. Tổng quan về ngôn ngữ lập trình

1. Vấn đề - bài toán Khái niệm

• 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

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

Page 3

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

• Pitago chia mọi vấn đề mà con người cần giải

1. Vấn đề - bài toán Khái niệm

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

AA  BB

• Ở đây:

Page 4

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

2

–– AA có thể là giả thiết, điều kiện ban đầu –– BB 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

1. Vấn đề - bài toán Khái niệm

• Ví dụ 1: Bài toán kiểm tra tính nguyên tố

– Cho: Số nguyên dương N – Cần biết: N có là số nguyên tố hay không? • Ví dụ 2: Bài toán quản lý hồ sơ sinh viên

– Cho: Hồ sơ gốc của các sinh viên trong trường – Cần biết: Bảng thống kê, phân loại sinh viên

Page 5

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

theo kết quả học tập

1. Vấn đề - bài toán Khái niệm

• Cấu trúc một bài toán:

– Thông tin đầu vào (input): cái cho trước – Thông tin đầu ra (output): cái cần tìm

Page 6

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

3

• Giải bài toán: là việc xác định tường minh output theo input bằng một quá trình có thể thực hiện một cách hiệu quả

1. Vấn đề - bài toán Một số phương pháp giải quyết vấn đề - bài toán bằng máy tính

Page 7

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

1. KĨ THUẬT CHIA ÐỂ TRỊ 2. KĨ THUẬT “THAM LAM” 3. QUY HOẠCH ÐỘNG 4. KĨ THUẬT QUAY LUI 5. KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG

2. Thuật toán – thuật giải Thuật toán – khái niệm

và tin học

• Thuật toán là khái niệm cơ sở của toán 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 đề

Page 8

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

4

2. Thuật toán – thuật giải Thuật toán – đặc trưng

• 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ả. 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. 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 đó.

Page 9

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

2. Thuật toán – thuật giải Thuật toán

toán khác nhau để giải

• Cùng một bài toán có thể có nhiều thuật

Page 10

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

5

• 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à thuthuậật tot toáán tn tốối ưui ưu

2. Thuật toán – thuật giải Thuật toán

vấn đề quan trọng của tin học

• Nghiên cứu thuật toán là một trong những

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

• Lý thuyết về thuật toán giải quyết một số

Page 11

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

– 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

2. Thuật toán – thuật giải Thuật toán – ví dụ

.

Thuật toán giải phương trình bậc hai: AX2 + BX + C = 0 (A  0) -Bước 1 : Tính DELTA = B*B-4*A*C -Bước 2 : So sánh DELTA với số 0 -Bước 3 : Rẽ làm 3 trường hợp : -Trường hợp DELTA < 0 : vô nghiệm;

-Trường hợp DELTA = 0 :

X

X

 

1

2

B 2*

A -Trường hợp DELTA > 0 :

2

4

ac

b  

X

1,2

b a 2

Page 12

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

6

2. Thuật toán – thuật giải Thuật toán – các cấu trúc cơ bản

lệnh khác

1. Tuần tự: thực hiện hết lệnh này đến

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

Page 13

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

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

2. Thuật toán – thuật giải Thuật giải

cửa khép kín cho việc giải các bài toán vì: – Nhiều bài toán không thỏa các đặc trưng cơ bản

• Khái niệm thuật toán đã trình bày chính là cánh

của thuật toán.

– Có nhiều bài toán chưa tìm ra thuật toán hoặc chưa chứng minh được là có thuật toán hay không.

– Có những bài toán có thuật toán nhưng khó thực

Page 14

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

7

hiện hoặc không thực hiện được

2. Thuật toán – thuật giải Thuật giải

THUẬT GIẢI CŨNG LÀ THUẬT TOÁN NHƯNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN

• Từ những nhận định trên người ta thấy rằng: cần phải có những đổi mới cho khái niệm thuật toán  “Thuật giải”

Page 15

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

– Tính xác định – Tính đúng đắn

2. Thuật toán – thuật giải Thuật giải – mở rộng tính xác định

• Tính xác định thực chất là tính đơn trị của cách giải

của một thuật toán và sự rõ ràng tối đa.

• Trong thực tế có nhiều bài toán vi phạm tính xác định mà vẫn cho kết qủa. Như vậy thay cho việc xây dựng toàn bộ quá trình giải chỉ cần chỉ ra cách chuyển từ bước i sang bước i+1.

• Cách gỉai ngẫu nhiên, đệ quy là mở rộng tính xác

định

Page 16

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

8

2. Thuật toán – thuật giải Thuật giải – mở rộng tính đúng đắn

đúng.

• Tính đúng đắn được hiểu là cho kết quả

nhận được

• Trong thực tế thì số gần đúng là có thể chấp

Page 17

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

• Ngoài ra dùng cách giải heuristic đơn giản, độc đáo vẫn có thể cho kết qủa một cách sáng tạo

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

Page 18

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

9

• Mã giả

3. Các phương pháp biểu diễn thuật toá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

Page 19

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

Ngôn ngữ tự nhiên

3. Các phương pháp biểu diễn thuật toán

Ngôn ngữ tự nhiên

• 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ưBướớc 1:c 1: Bốc 3 que rồi đợi đối phương đi –– BưBướớc 2:c 2: Đối phương bốc (giả sử x que, 0

que. Nếu còn diêm thì quay lại BưBướớc 2c 2

Page 20

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

10

– Tuyên bố thắng cuộc. KKếết tht thúúcc

3. Các phương pháp biểu diễn thuật toán

Ngôn ngữ tự nhiên – Bài tập

môn Toán, Lý, Hóa.

1. Tính điểm trung bình của học sinh gồm các

nhau.

2. Kiểm tra 2 số a, b giống nhau hay khác

Page 21

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

3. Kiểm tra 1 số a chẵn hay lẻ 4. Giải pt: ax+b=0 5. Giải phương trình bậc 2: ax2 + bx + c = 0

3. Các phương pháp biểu diễn thuật toán

Sơ đồ khối

giải thuật một cách trực quan

• Là một phương tiện hình học giúp ta diễn tả

nhau bằng các đường có hướng

• Được tạo bởi các kiểu khối cơ bản, nối với

Page 22

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

11

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

3. Các phương pháp biểu diễn thuật toán

Sơ đồ khối

điều kiện bắt đầu kết thúc

thao tác

input

Chương trình con

Page 23

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

output Hướng xử lý

3. Các phương pháp biểu diễn thuật toán

Sơ đồ khối – ví dụ

Bắt đầu

Bắt đầu

Thùng = 0 Lon

Bắt đầu

Số a, Số b

1 Lon

a, b

Thêm 1 Lon vào thùng

Không

c = a + b

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

Chưa

Thùng = 24 Lon?

Có

c

Bằng

Số a bằng Số b

Số a không bằng Số b

Kết thúc

Kết thúc

Kết thúc

Page 24

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

12

3. Các phương pháp biểu diễn thuật toán

Sơ đồ khối – Bài tập

môn Toán, Lý, Hóa.

1. Tính điểm trung bình của học sinh gồm các

nhau.

2. Kiểm tra 2 số a, b giống nhau hay khác

Page 25

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

3. Kiểm tra 1 số a chẵn hay lẻ 4. Giải pt: ax+b=0 5. Giải phương trình bậc 2: ax2 + bx + c = 0

3. Các phương pháp biểu diễn thuật toán

Mã giả

• Ngoài việc sử dụng ngôn ngữ tự nhiên và lưu đồ để biểu diễn thuật toán, người ta còn sử dụng ngôn ngữ tựa pascal, c, … được gọi là mã giả

ngôn ngữ lập trình và ngôn ngữ tự nhiên

Page 26

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

13

• Trong mã giả ta sử dụng cả cấu trúc của

3. Các phương pháp biểu diễn thuật toán

Mã giả - ví dụ

Biến

A,B,C,DELTA,X1,X2 : SốThực ;

BắtĐầu

Nhập A,B,C; DELTA:=B*B-4*A*C; Nếu DELTA <0 Thi

Xuất 'Phương trinh vô nghiệm '; Dừng; Nếu DELTA =0 Thi X1:=(-B/2/A); X2:=X1; Xuất 'Nghiệm kép X1,X2 '; Dừng; Nếu DELTA =0 Thi

X1:=(-B-CanBậcHai(DELTA))/2/A; X2:=(-B+CanBậchH(DELTA))/2/A; Xuất 'Nghiệm phân biệt X1,X2 '; Dừng;

KếtThúc.

Page 27

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

3. Các phương pháp biểu diễn thuật toán

Mã giả – Bài tập

môn Toán, Lý, Hóa.

1. Tính điểm trung bình của học sinh gồm các

nhau.

2. Kiểm tra 2 số a, b giống nhau hay khác

3. Kiểm tra 1 số a chẵn hay lẻ 4. Giải pt: ax+b=0 5. Giải phương trình bậc 2: ax2 + bx + c = 0

Page 28

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

14

SSửử ddụụng ngôn ng a pascal ng ngôn ngữữ ttựựa pascal

4. Các bước để giải một bài toán trên máy tính

Page 29

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

4. Các bước để giải một bài toán trên máy tính

• 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

Bước 1: Xác định vấn đề - bài toán

• Phân tích hệ thống nhằm phát biểu chính xác vấn đề, làm rõ yêu cầu của người sử dụng

Page 30

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

15

• Đánh giá, nhận định tính khả thi của vấn đề

4. Các bước để giải một bài toán trên máy tính

Bước 2: Lựa chọn phương pháp giải

• Có nhiều cách khác nhau để giải quyết vấn đề, tùy theo nhu cầu cụ thể mà ta lựa chọn phương pháp thích hợp

Page 31

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

4. Các bước để giải một bài toán trên máy tính

• Việc lựa chọn phương pháp cũng cần căn cứ vào khả năng xử lý tự động mà ta cần sử dụng

Bước 3: Xây dựng thuật toán hoặc thuật giải

• Xác định input, output

liệu đầu vào và đầu ra

• Xác định các bước thực hiện cơ bản cho dữ

Page 32

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

16

• Nên áp dụng phương pháp thiết kế có cấu trúc, từ thiết kế tổng thể tiến hành làm mịn dần các bước

4. Các bước để giải một bài toán trên máy tính

Bước 4: Cài đặt chương trình

• Mô tả thuật giải thành chương trình

Page 33

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

4. Các bước để giải một bài toán trên máy tính

• Cần nắm vững ngôn ngữ lập trình và thể hiện một cách chính xác thuật toán đã được đưa ra.

Bước 5: Hiệu chỉnh chương trình

những sai sót

• Cho chương trình chạy thử và hiệu chỉnh

• Trong bước này ta cần khắc phục hai loại lỗi:

– Lỗi cú pháp (có sự hỗ trợ của IDE)

– Lỗi ngữ nghĩa (thường khó phát hiện hơn lỗi cú

Page 34

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

17

pháp)

4. Các bước để giải một bài toán trên máy tính

Bước 6: Thực hiện chương trình

khác nhau để kiểm tra

• Cho chương trình chạy với những bộ dữ liệu

• Lưu ý các trường hợp đặc biệt

Page 35

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

• Lưu ý các trường hợp người dùng nhập dữ liệu có kiểu không phù hợp với kiểu dữ liệu sử dụng trong chương trình

5. Tổng quan về ngôn ngữ lập trình

Con người làm việc

Ôi nhiều việc quá

VẤN ĐỀ

NAN GIẢI?

PP giải (giải thuật)

Page 36

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

18

VẤN ĐỀ TƯƠNG TỰ KẾT QUẢ

5. Tổng quan về ngôn ngữ lập trình

Sự hỗ trợ của máy tính

Có máy tính Sướng thật, đi làm việc khác thôi!

VẤN ĐỀ TƯƠNG TỰ

KẾT QUẢ

VẤN ĐỀ

Page 37

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

PP giải (giải thuật) NAN GIẢI?

5. Tổng quan về ngôn ngữ lập trình

Giải bài toán này thế nào đây?

Chương trình biên dịch

(Bộ máy của NNLT)

Sự hỗ trợ của máy tính

File Ngôn ngữ máy

Source code

Kiến thức Chuyên môn

Kiến thức về NNLT

Cách giải được diễn đạt bằng ngôn ngữ tự nhiên

Page 38

T.P.Tuấn-TIN HỌC ĐẠI CƯƠNG

9/16/2008

19

(exe, dll, com, ...)