Tin học căn bản

CHUONG III
GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH
CHUONG III
GIẢI QUYẾT BÀI TOÁN BẰNG MÁY TÍNH
3.1 Kỹ thuật lập trình
3.2 Thuật toán và Thuật giải
3.3 Biểu diễn thuật toán
3.4 Các bước giải quyết bài toán trên máy

3.1 Kỹ thuật lập trình
Khái quát
Kỹ thuật xây dựng phần mềm chính là kỹ thuật lập trình. Lập trình vừa là một kỹ thuật vừa là một nghệ thuật.
Lập trình (Programming) thực chất là điều khiển - bằng một ngôn ngữ lập trình cụ thể - cách xử lý thông tin trên máy theo yêu cầu của bài toán đặt ra.
Để lập trình, phải biết cách tổ chức dữ liệu (nguyên liệu để máy xử lý) và cách thức xử lí dữ liệu (thuật giải) để cho ra kết quả mong muốn.

PROGRAMMING
=
ALGORITHMS
+
DATA STRUCTURE
PHẢI TỔ CHỨC DỮ LIỆU THEO CÁCH TỐT NHẤT :
Dữ liệu trong tin học phải được phân loại, xác định một cách rạch ròi theo những quy định chặt chẽ, chính xác để máy có thể phân biệt, nhận biết, lưu trữ và xử lý
PHẢI TÌM ĐƯỢC THUẬT TOÁN TỐT NHẤT, TỐI ƯU NHẤT

4 TIÊU CHUẨN ĐÁNH GIÁ MỘT CHƯƠNG TRÌNH :
� Tính tin cậy
� Tính uyển chuyển
� Tính trong sáng
� Tính hữu hiệu
LẬP TRÌNH CẤU TRÚC
� Cấu trúc về mặt dữ liệu
� Từ những lệnh đơn giản đã có hoặc những lệnh đã có cấu trúc, có thể xây dựng những lệnh có cấu trúc phức tạp hơn
� Cấu trúc về mặt chương trình :
?Một chương trình lớn có thể chia thành nhiều modun chương trình con độc lập
?Mỗi chương trình con lại có thể phân chia thành các chương trình con khác.
?PASCAL là một trong các ngôn ngữ tiêu biểu về có cấu trúc
3.2 Thuật toán
và
Giải thuật
KHÁI NIÊM 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 (Algorithm) là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên nh?ng đối tượng, sao cho sau một số h?u hạn bước thực hiện các thao tác ta đạt được mục tiêu định trước.

Người hoặc máy thực hiện một thuật toán được gọi là một bộ xử lý.
Như vậy một bộ xử lý của một thuật toán T nào đó là một cơ chế có kh? nang thực hiện các thao tác trên các đối tượng theo một trỡnh tự do T quy định.

Cùng một bài toán có thể có nhiều thuật toán khác nhau.
Thuật toán đơn giaỷn, dễ hiểu, có độ chính xác cao, được baỷo đaỷ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 nhất của Tin học.

Lý thuyết về thuật toán phaỷi giaỷi quyết các vấn đề sau :
-Nhửừng bài toán nào giaỷi được bằng thuật toán; bài toán nào không giaỷi được bằng thuật toán
-Tỡm thuật toán tốt nhất, tối ưu của một bài toán
-Triển khai thuật toán trên máy tính

Vài ví dụ
Thuật toán giaỷi phương trỡnh bậc hai :
A X2 + 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 :
thông báo phương trỡnh vô nghiệm ; kết thúc thuật toán.
-Trường hợp DELTA = 0 : tính nghiệm kép :
X1 = X2
thông báo nghiệm kép; kết thúc thuật toán.
-Trường hợp DELTA > 0 :tính hai nghiệm phân biệt:
X1, X2
� thông báo nghiệm ; kết thúc thuật toán.
Thuật toán Hoocne tính giá trị của đa thức :
Cho Pn(X)=AnXn + An-1Xn-1 +........ +A1X1 +A0
Tính Pn(c) ?

Pn(c)=(...((An.c +An-1).c + An-2 )...).c + A0
�
- Bước 1 : Cho i = n ; Q = An
- Bước 2 : Cho i nhận giá trị cũ của i trừ 1 : i = i - 1
So sánh i với 0.
- Bước 3 : Rẽ làm 2 trường hợp :
1-Trường hợp i >= 0 :
tính Q bằng giá trị cũ của Q nhân với c cộng với Ai ;
Quay trở lại bước 2.
2-Trường hợp i < 0 :
thông báo kết quaỷ Q; Kết thúc thuật toán.

ý nghĩa của thuật toán hoocne


Cho Pn(X)=AnXn + An-1Xn-1 +........ +A1X1 +A0

Viết đa thức dưới dạng :
Pn(c)=(...((An.c +An-1).c + An-2 )...).c + A0
Chỉ bao gồm các phép nhân, cộng liên tiếp

P2(c)=(A2.c +A1).c + A0
P3(c)=((A3.c +A2).c + A1).c + A0
6 TÍNH CHẤT
CỦA THUẬT TOÁN
1-tính dừng - kết thúc
2-tính xác định
3-tính hàng loạt
4-tính KH? THI
5-tính đầy đủ-vét cạn
6-tính đúng đắn
TÍNH DỪNG
Thuật toán phaỷi kết thúc sau một số hửừu haùn bước.
Ví dụ : Thuật toán không dừng
1) Xoá b?ng
2) Viết số 9
3) Thực hiện bước 1

Ví dụ 7 : Thuật toán không dừng
Dọc các số tự nhiên liên tiếp, bắt đầu từ 1

Các thao tác ở mỗi bước ph?i hết sức rõ ràng và chỉ được hiểu theo một nghĩa duy nhất.
Trong cùng một điều kiện, hai bộ xử lý khác nhau hoặc hai lần thao tác khác nhau ph?i cho cùng một kết qu? khi thực hiện cùng một thuật toán.
Các người khác nhau cùng sử dụng một thuật toán, sẽ hành động giống nhau cho dù họ không hiểu gỡ về b?n chất và ý nghĩa của vấn đề.
TÍNH XÁC ĐỊNH
Thuật toán có hiệu lực như nhau đối với các bài toán cùng loại, có cùng miền áp dụng thuật toán.

Thuật toán Hooc-ne có tính hàng loạt trên tập s? th?c R v� bất kỡ đa thức đại số bậc nào.
Thuật toán Gi?i phuong trỡnh b?c 2 khụng có tính hàng loạt nếu số liệu gán cho a, b,c nhập từ bàn phím.
Chẳng hạn khi nhập a=0 hoặc a không ph?i là số ..
TÍNH HÀNG LOẠT

ThuỊt to�n ph?i bao gơm nh?ng thao t�c m� m�y cê th� th�c hi�n ���c.
Mây t�nh ch� cê th� th�c hi�n ���c nh?ng ph�p to�n sỉ hôc, c�c ph�p so s�nh, c�c ph�p logic, c�c ph�p nhỊp xuÍt th�ng tin ti�u chuỈn.
ThuỊt to�n Hooc-ne cê t�nh kh? thi.
ThuỊt to�n Gi?i phuong tr�nh b?c 2 kh�ng cê t�nh kh? thi trong tr�íng h�p DELTA > 0 v� m�y kh�ng th� th�c hi�n ph�p t�nh khai can DELTA.

TÍNH KHẢ THI
Thuật toán ph?i vét được hết các tỡnh huống, các kh? nang có thể x?y ra, không bỏ sót bất k? một trường hợp nào trong miền áp dụng.
Thuật toán Hooc-ne v� Gi?i phuong trỡnh b?c 2 không có tính đầy đủ nếu d? liệu nhập từ bàn phím

TÍNH ĐẦY ĐỦ-VÉT CẠN
TÍNH ĐÚNG ĐẮN
Thuật toán ph?i cho kết qu? đúng của bài toán nghĩa là ph?i được chứng minh về mặt toán học .
Thuật toán tỡm bội số chung nhỏ nhất của hai số nguyên dương a,b ký hiệu c=BSCNN(a,b) :
-B1 : Nếu a = 1 thỡ c = b , dừng
Nếu b = 1 thỡ c = a , dừng
-B2 : Nếu a >1 và b >1 thỡ c = a*b , dừng
Có thể kiểm tra 100 trường hợp của a, b đều cho kết q?a đúng, nhưng với a = 4, b = 2 thỡ sai.
Thuật toán n�y không có tính đúng đắn trên N
MỘT THUẬT TOÁN PHẢI THOẢ MÃN ĐỒNG THỜI CÁC TÍNH CHẤT TRÊN
CẤU TRÚC CƠ BẢN CỦA THUẬT TOÁN
�

CẤU TRÚC TUẦN TỰ
THAO TÁC 2
THAO TÁC 3
THAO TÁC 1
CẤU TRÚC RẼ NHÁNH
ĐIỀU KIỆN
THAO TÁC 1
THAO TÁC 2
CẤU TRÚC VÒNG LẶP
ĐIỀU KIỆN
THAO TÁC
THAO TÁC
CÁC PHƯƠNG PHÁP BIỂU DIỄN THUẬT TOÁN

1) Dùng ngôn ng? m? d? ho?c ngụn ng? mó gi?
2) Ngôn ng? lưu đồ
3) Ngôn ng? lập trỡnh

Biểu diễn thuật toán bằng ngôn ng? lập trỡnh chính là th?o chương, mục tiêu quan trọng trong Tin học.

Ngôn ngữ mã giả
ThuậtToánPhươngTrinhBậcHai;
Biến
A,B,C,DELTA,X1,X2 : SốThực ;
BắtDầ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.
Lưu đồ
BEGIN

Nhập A,B,C

DELTA =B*B-4*A*C

DELTA ?

V� NGHI�M
TH�C

X1=X2=-B/2/A

X1=
X2=

IN K�t QUa

END
Ngôn ngữ lập trình PASCAL

PROGRAM Phuongtrinh BacHai;
USES Crt;
LABEL 20;
VAR
a, b, c : Real;
Delta, X1, X2: Real;
BEGIN
20 : Clrscr;
GoTOXY(10,4); Writeln(` Giai phuong trinh bac hai`);
GoTOXY(10,5); Writeln(`**************************`);
Write(`Ban hay nhap vao gia tri cua A : `);
Readln(a);
IF a = 999999999 THEN Halt;
IF a = 0 THEN
BEGIN
Writeln(` a khong hop le !`);
Delay(500);
GOTO 20;
END;

Write(`Ban hay nhap vao gia tri cua B: `);
Readln(b);
Write(`Ban hay nhap vao gia tri cua C: `);
Readln(c);
Delta := spr(b)- 4*a*c;
IF Delta <0 then
Writeln(` Phuong trinh vo nghiem `);
IF Delta = 0 THEN
BEGIN
Writeln(`Phuong trinh co nghiem kep`);
Writeln(` X = `, -b/(2*a) :9 :2);
END;
IF Delta > 0 THEN
BEGIN
Writeln(`Phuong trinh coự 2 nghiem : `);
X1 := (-b+sqrt(delta))/(2*a);
X2 := (-b-sqrt(delta))/(2*a);
Writeln(` X1 = `, X1: 9 : 2);
Writeln(` X2 = `, X2: 9 : 2);
END;
Readln;
END.
     Kh¸i niÖm thuËt to¸n đã trình bày chÝnh lµ c¸nh cöa khÐp kÝn cho viÖc gỉai 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 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 hiÖn hoÆc kh«ng thùc hiÖn ®­îc
THUËT GI¶I
�ã����� Có nh?ng bài toán được gi?i tuy vi phạm các quy định của thuật toán nhưng lời gi?i vẫn được thực tiễn chấp nhận
THUẬT GIẢI CŨNG LÀ THUẬT TOÁN NHƯNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN
NHỮNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN

��������� 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
     Më réng tÝnh ®óng ®¾n
TÝnh ®óng ®¾n ®­îc hiÓu lµ cho kÕt quả ®óng. Nh­ng trong thùc tÕ thì sè gÇn ®óng lµ cã thÓ chÊp nhËn. Ngoµi ra dïng c¸ch gỉai heuristic ®¬n giản, ®éc ®¸o vÉn cã thÓ cho kÕt qủa mét c¸ch s¸ng t¹o.
NĂM BƯỚC GIẢI BÀI TOÁN TRÊN MÁY TÍNH
a) Bước 1
Nghiên cứu kĩ nội dung, yêu cầu của bài toán và tỡm phương pháp, thuật toán gi?i bài toán Với bài toán lớn, phức tạp việc tỡm phương pháp và thuật toán rất khó khan. Nhiều trường hợp ph?i có sự cộng tác, giúp đỡ của các chuyên gia về phương pháp tính toán và thuật toán .
b) Bước 2
Diễn t? thuật toán bằng lưu đồ hoặc bằng ngôn ng? Mụ t? thu?t toỏn.

c) Bước 3
Diễn t? thuật toán bằng bằng ngôn ng? Lập trỡnh
Dây là công việc chuyển lưu đồ hoặc ngôn ng? Mụ t? thu?t toỏn thành ngôn ng? lập trỡnh. Quá trỡnh này gọi là th?o chương .
d) Bước 4
Chạy thử và sửa lỗi. Bước này có thể thực hiện xen kẽ trong bước 3 và thực hiện nhiều lần với nhiều người khác nhau nhằm phát hiện tối đa các sai sót . Ph?i sửa hết tất c? các lỗi dù nhỏ nhất.

e) Bước 5
Dánh giá sự đúng đắn và độ tin cậy của kết qủa.Việc đánh giá này thường dựa trên :
- ý nghĩa thực tiễn của bài toán
- Kinh nghiệm dự đóan kết qủa của người gi?i
- So sánh kết qủa với kết qủa của bài toán đã có lời giai đúng
- Gi?i bài toán trong nh?ng trường hợp đặc biệt, trường hợp thu gọn dễ thấy kết qủa là đúng hay sai.

Nếu kết qu? sai ph?i rà soát lại từ bước 1 v� có thể sai từ thuật toán. Công việc tỡm lỗi sai và sửa lỗi của thuật toán rất khó
Nếu kết q?a tỡm được là đúng đắn và tin cậy, ghi chương trỡnh lên đĩa để lưu .
CÁC PHƯƠNG PHÁP THÔNG DỤNG
PH��ng ph�p �ĩng
Ph��ng ph�p g�n �ĩng -ph��ng ph�p t�nh
Ph��ng ph�p ng�u nhi�n
Ph��ng ph�p kinh nghiƯm
HEURISTIC