Tin học căn bản chương 3

5
PROGRAMMING
=
ALGORITHMS
+
DATA STRUCTURE
6
•
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

7
•
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
8
LẬP TRÌNH CẤU TRÚC
L Cấu trúc về mặt dữ liệu
C 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
p 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
9
3.2 Thuật toán
và
Giải thuật
10
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
Tht 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.
11
Ng­êi hc m¸y thùc hiƯn
mét tht to¸n ®­ỵc gäi lµ mét
bé xư lý.
Nh­ vËy mét bé xư lý cđa
mét tht to¸n T nµo ®ã lµ mét
c¬ chÕ cã kh n ng 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.
12
Cïng mét bµi to¸n cã thĨ cã
nhiỊu tht to¸n kh¸c nhau.
Tht 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µ tht
to¸n tèi ­u.
13
Nghiªn cøu tht to¸n lµ mét trong
những vÊn ®Ị quan träng nhÊt cđa Tin häc.
Lý thut vỊ tht to¸n phải giải
qut c¸c vÊn ®Ị sau :
-Những bµi to¸n nµo giải ®­ỵc b»ng
tht to¸n; bµi to¸n nµo kh«ng giải ®­ỵc
b»ng tht to¸n
-Tìm tht to¸n tèt nhÊt, tèi ­u cđa
mét bµi to¸n
-TriĨn khai tht to¸n trªn m¸y tÝnh
14
Vài ví dụ
Tht to¸n giải ph­¬ng trình bËc hai :
A X
2
+ 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 :
DELTA
DELTA
-Tr­êng hỵp DELTA < 0 :
th«ng b¸o ph­¬ng trình v« nghiƯm ; kÕt thóc tht 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 tht 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 tht to¸n.

Xem chi tiết: Tin học căn bản chương 3