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

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

2

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

Nội dung chí nh

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

2. Quá trì nh giải quyết bài toá n bằng

má y tí nh

3. Phương pháp giải quyết bài toán

bằng máy tí nh

01-Jan-16

3

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

1. Khái niệm bài toá n

Problem – Bài toán hay vấn đề?

• Theo Socrate (470-399 TCN): 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 phải liên

quan í t nhiều đến tí nh toá n

– Bài toá n trong vật lý, hóa học, xâ y

dựng, kinh tế,…

01-Jan-16

4

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

1. Khái niệm bài toá n

Phân loại vấn đề (Pytago)

• Theorema:

– Vấn đề cần khẳng định đúng sai

• Ví dụ: Chứng minh cá c định lý trong toán học

• Problema:

– Vấn đề cần tìm giải pháp để đạt mục tiêu xác

định từ những điều kiện ban đầu

• Ví dụ: Bài toá n dựng hình, tì m đường đi ngắn nhất,

tổng hợp chất hó a học…

01-Jan-16

5

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

1. Khái niệm bài toá n

Biểu diễn vấn đề (1/3)

A → B

• A: Giả thiết, điều kiện ban đầu

• B: Kết luận, mục tiêu cần thực hiện

• →: Suy luận, giải pháp cần xác định

01-Jan-16

6

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

1. Khái niệm bài toá n

Biểu diễn vấn đề (2/3)

• Cho vấn đề/bài toá n:

Cho A vàB

• Giải quyết vấn đề/bài toá n:

Từ A dùng một số hữu hạn các bước

suy luận có lý hoặc hành động thí ch hợp

để đạt B.

Cần xác định tập các thao tác cơ bản được

dùng trong suy luận và hành động

01-Jan-16

7

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

1. Khái niệm bài toá n

Biểu diễn vấn đề (3/3)

Trong tin học

A → B

• A: Input

• B: Output

• →: Chương trì nh cho phé p biến

đổi A thành B .

01-Jan-16

8

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

1. Khái niệm bài toá n

Chương trì nh

• Chương trì nh

– Cách mã hóa lại thuật toán/thuật giải để giải

quyết vấn đề/bài toá n đã cho

– Tạo thành từ các lệnh cơ bản của máy tí nh

• Khó khăn:

– Tồn tại các yếu tố không xác định

• A và B khô ng đầy đủ, rõ ràng

• Giải quyết bài toá n trên má y tí nh?

– Vấn đề tổ chức dữ liệu và thiết kế giải thuật

Cấu trúc dữ liệu + Giải thuật = Chương trình

01-Jan-16

9

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

1. Khái niệm bài toá n

Thiết kế thuật giải

• Thực hiện bởi con người

– Là cá ch thức chủ yếu, dựa trên

• Những thô ng tin được phản ánh rõ ràng trong A, B

hoặc →

• Cá c tri thức của con người

• Tự động hóa xâ y dựng thuật giải

– Lĩnh vực mới, đang được nghiên cứu

– Cần phải biểu diễn nội dung và các tri thức liên

quan dưới dạng tương minh và đầy đủ

01-Jan-16

10

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

Nội dung chí nh

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

2. Quá trì nh giải quyết bài toá n bằng

má y tí nh

3. Phương pháp giải quyết bài toán

bằng máy tí nh

01-Jan-16

11

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

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

Má y tí nh & Lập trì nh viên

• Má y tí nh

– Chỉ làm được những gì được bảo.

– Khô ng thô ng minh: không thể tự phâ n tích vấn đề

và đưa ra giải phá p.

– Khô ng thể dùng giải quyết các vấn đề liên quan đến

hành động vật lý hoặc biểu thị cảm xúc

• Lập trình viên

– Phâ n tích vấn đề

– Tạo ra các chỉ dẫn để giải quyết vấn đề (xây dưng

chương trình).

• Má y tí nh sẽ thực hiện các chỉ dẫn này.

01-Jan-16

12

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

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

Cá c bước giải quyết bài toá n

1. Xá c định bài toá n

2. Lựa chọn phương pháp giải

3. Xâ y dựng thuật toán hoặc thuật giải

4. Cài đặt chương trì nh

5. Hiệu chỉnh chương trì nh

6. Thực hiện chương trì nh

01-Jan-16

13

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

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

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

• Mô tả bài toán cần giải quyết

– Dữ liệu vào: Danh sá ch cá c dữ kiện vào

– Điều kiện vào: Ràng buộc, quan hệ giữa chúng

– Dữ liệu ra: Danh sá ch cá c dữ liệu ra

– Điều kiện ra: Ràng buộc, quan hệ giữa chúng

• Đánh giá, nhận định tí nh khả thi của bài toá n

– Thời gian, kinh phí, nguồn lực,…

Ví dụ: Bài toá n tìm ƯSCLN của 2 số nguyên dương

– Nhập: 2 số X, Y

– Điều kiện nhập: X, Y nguyên dương

– Dữ liệu ra: Z

– Điều kiện ra: Z là ƯSCLN(X,Y)

01-Jan-16

14

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

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

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

• Tồn tại nhiều phương pháp khá c nhau

– Khá c nhau về thời gian thực hiện, chi phí lưu

trữ dữ liệu, độ chí nh xác…

• Tùy theo nhu cầu cụ thể và khả năng xử lý

tự động được sử dụng để lựa chọn phương

phá p thí ch hợp

Ví dụ: Bài toá n sắp xếp dã y số

– Nổi bọt, Vun đống, Sắp xếp nhanh,…

01-Jan-16

15

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

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

Bước 3: Xâ y dựng thuật giải

• Xây dựng mô hình chặt chẽ, chí nh xá c và chi tiết

cho phương pháp đã lựa chọn

• Lặp liên tiếp các bước sau để thuật toán ngày càng

hoàn chỉnh hơn (quá trì nh tinh chỉnh từng bước)

1. Xác định và chí nh xá c hó a cá c thao tá c

– Để đạt được kết quả cần làm gì ?

2. Xác định cá c dữ liệu cần dùng và tính chất của chúng

– Để thực hiện, thao tác cần gì và sẽ tạo ra gì ?

3. Xác định trình tự các thao tá c

– Thao tác nào cần làm trước

– Thao tác thực hiện 1 hay nhiều lần, thực hiện trong điều kiện

nào..?

01-Jan-16

16

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

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

Bước 3: Xâ y dựng thuật giải (tiếp)

• Quá trình tinh chỉnh từng bước dừng lại khi

– Yêu cầu cho biết 1 hay nhiều đại lượng

– Tính một đại lượng theo cô ng thức đã biết rõ

– Thông báo một hay nhiều kết quả đã xử lý

• Sau khi tinh chỉnh cần phải diễn tả giải thuật

dưới dạng chuẩn

– Ngôn ngữ liệt kê cá c hành động

– Sơ đồ khối…

01-Jan-16

17

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

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

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

Mã hóa giải thuật bằng một ngô n ngữ lập trì nh

• Thay thế các thao tác bằng cá c lệnh tương ứng

của ngô n ngữ sử dụng

– Thao tá c: In ra một thô ng bá o

– Câ u lệnh: printf(“….”)/ write(“…..”);

• Lựa chọn ngôn ngữ lập trì nh, tùy theo bài toán giải

quyết

– NNLT bậc thấp: Hợp ngữ

– NNLT bậc cao: C, Pascal, Java,..

01-Jan-16

18

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

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

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

Chạy thử để phát hiện và điều chỉnh cá c sai

só t có thể có ở bước 4.

– Lỗi cú phá p:

• Viết sai cú phá p của ngôn ngữ lập trì nh

lựa chọn

– Lỗi ngữ nghĩa

• Mã hó a sai giải thuật

• Giải thuật sai

01-Jan-16

19

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

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

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

• Cho má y tí nh thực hiện chương trì nh.

• Tiến hành phâ n tích kết quả thu được

– Kết quả đó có phù hợp hay khô ng.

– Không phù hợp kiểm tra lại toàn bộ cá c bước.

01-Jan-16

20

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