Hãy xây dựng thuật toán (dùng cả 3 loại: ngôn ngữ tự nhiên, lưu đồ, mã giả) cho các bài toán sau:
1. Thiết kế thuật toán theo phương pháp dùng ngôn ngữ tự nhiên cho các bài toán sau:
a) Kiểm tra 2 số a, b giống nhau hay khác nhau.
b) Kiểm tra 1 số a chẵn hay lẻ
c) Giải phương trình bậc 2: ax
2
+ bx + c = 0
2. Thiết kế thuật toán theo phương pháp dùng phương pháp lưu đồ cho các bài toán sau:
a) Nhập vào 4 số xuất ra phần tử lớn nhất và nhỏ nhất?
b) Kiểm tra xem 1 số n có phải là số nguyên tố?
c) Kiểm tra xem 1 số n có phải là số hoàn thiện?
Thiết kế thuật toán theo phương pháp dùng phương pháp mã giả cho các bài toán sau:
3. Có n hộp có khối lượng khác nhau và một cái cân dĩa. Tìm cách cân để tìm được hộp có
trọng lượng nặng nhất.
4. Tìm ước số chung lớn nhất của a và b.
5. Nhập vào 3 số nguyên dương, kiểm tra xem 3 số đã cho có tạo thành tam giác không?
Nếu có là tam giác gì? (Đều, cân, vuông, vuông cân, thường).
6. Mô phỏng thuật toán (Chạy tay)
7. Kiểm tra số nguyên tố (19, 20, 27, 29)
8. Tìm UCLN của (12,15), (19, 27), (24,45)
9. Tìm max trong dãy số: 1, 6 , 3, 15, 7, 9, 4
10. Sắp xếp dãy số tăng dần: 1, 6 , 3, 15, 7, 9, 4
230 trang |
Chia sẻ: tuanhd28 | Lượt xem: 2849 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Giáo trình Tin học đại cương - Lê Đức Long (Phần 2), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
hình hồi quy tuyến tính đơn y =
ax+b và mô hình hồi quy tuyến tính bội y = a1x1+a2x2++anxn + b (*)
Cú pháp
= LINEST(known_y’s; known_x’s; const; stats)
Nhập xong được kết thúc bằng tổ hợp phím Ctrl + Shift + Enter
Trong đó:
known_y’s, known_x’s là các giá trị hoặc vùng địa chỉ chứa giá trị đã biết của x và y
tương ứng.
const là hằng số
const = 1 (TRUE) thì tính toán hệ số tự do b
const = 0 (FALSE) bỏ qua b (b=0)
stats là các tham số thống kê.
stats = 1 thì tính các tham số thống kê
stats = 0 thì bỏ qua.
Các tham số thống kê nếu được tính bao gồm:
- Các hệ số của đa thức được sắp xếp theo thứ tự giảm dần mn, mn-1, , m2, m1 tức là an, an-
1,, a2, a1, b của mô hình (*)
- Các sai số chuẩn của các hệ số sen, sen-1, , se2, se1, seb (seb = #N/A khi const = FALSE)
- Hệ số xác định r2, sai số của giá trị y sey.
- Phân phối F, số bậc tự do df.
- Ssreg (regression sum of square) và ssresid (residual sum of square).
- Bảng stats được bố trí như sau:
an an-1 a2 a1 b
sen sen-1 se2 se1 seb
r2 sey
F df
ssreg ssresid
Bảng 6.14 Bảng stats
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 319
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Xét ví dụ 1.5.3: Lợi nhuận của doanh nghiệp (y) phụ thuộc vào giá thành sản phẩm (x1), chi phí
quản lý (x2), chi phí bán hàng (x3). Dự báo lợi nhuận của doanh nghiệp đạt được khi x1 = 600, x2
= 35, x3 = 25 bằng hàm LINEST như hình sau:
Chú ý: Trong trường hợp có hai biến ta cũng tiến hành tương tự như trường hợp có nhiều biến ở
trên
b. Sử dụng trình cài thêm Regression để hồi quy và dự báo
Ngoài việc sử dụng các hàm để dự báo cho mô hình hồi quy tuyến tính như đã trình bày ở trên, ta
có thể sử dụng trình cài thêm Regression trong bộ phân tích dữ liệu Data Analysis.
Quy trình lập bảng hồi quy tuyến tính trong MS Excel 2003:
- Nhập số liệu vào bảng tính đồng thời theo từng cột hoặc đồng thời theo từng dòng.
- Chọn Tools/ Data Analysis/ Regression/ OK. Các bảng hộp thoại lần lượt xuất hiện như
sau:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 320
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Hình 6.52Hộp thoại chứa các công cụ phân tích dữ liệu
Hình 6.53 Hộp thoại khai báo các thông số của mô hình hồi quy
- Nhấn OK để đưa ra kết quả hồi quy
- Thay các hệ số của mô hình hồi quy tính được và các giá trị đã cho trong kỳ dự báo vào
hàm hồi quy ta sẽ tính được giá trị cần dự báo.
Xét ví dụ 1.5.3 bằng công cụ Regression ta làm như sau:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 321
Trường ĐH Sư phạm Tp. Hồ Chí Minh
- Nhập số liệu vào bảng tính
- Chọn Tools/Data Analysis/Regression/OK. Bảng hộp thoại Regression xuất hiện ta điền
các thông tin như trong hình sau:
Hình 6.54Bảng hộp thoại Regression
- Nhấn OK, ta được bảng kết quả như sau:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 322
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Hình 6.55Phƣơng pháp dự báo hồi quy sử dụng Regression
Một số thuật ngữ trong bảng kết quả
- Bảng tóm tắt SUMMARY OUTPUT
Regression Statistics: Các thông số của mô hình hồi quy
Multiply R: Hệ số tương quan bộ (0<=R<=1). Cho thấy mức độ chặt chẽ của mối liên hệ
tương quan bội.
S Square: Hệ số xác định. Trong 100% sự biến động của biến phụ thuộc Y thì có bao
nhiêu % sự biến động là do các biến độc lập X ảnh hưởng, còn lại là do sai số ngẫu nhiên.
Adjusted R: Hệ số xác định mẫu điều chỉnh. Là hệ số xác định có tính đến độ lớn hay nhỏ
của bậc tự do df.
Standard Error: Sai số chuẩn của Y do hồi quy
Observation: Số quan sát hay dung lượng mẫu.
- Bảng phân tích phương sai ANOVA (Analysis of variance)
Regression: Do hồi quy
Residual: Do ngẫu nhiên
Total: Tổng cộng
df (Degree of freedom): Số bậc tự do
SS (Sum of Square): Tổng bình phương của mức động (mức sai lệch) giữa các giá trị quan
sát của Y và giá trị bình quân của chúng.
MS (Mean of Square): Phương sai hay số bình quân của tổng bình phương sai lệch kể
trên.
TTS (Total Sum of Square): Tổng bình phương của tất cả mức sai lệch giữa các giá trị
quan sát Yi và giá trị bình quân của chúng 𝑌 .
F-stat: Tiêu chuẩn F dùng làm căn cứ để kiểm định độ tin cậy về mặt khoa học (thống kê)
của toàn bộ phương trình hồi quy.
Significance F: F lý thuyết
- Bảng phân tích hồi quy
Coefficients: Cột giá trị của các hệ số hàm hồi quy
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 323
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Intercept: Hệ số tự do b. Hệ số này cho thấy xuất phát điểm của đường hồi quy
X Variable 1, X Variable 2, X Variable 3là các hệ số góc của các biến tương ứng x1, x2,
x3
Standard Error: (se) độ lệch chuẩn của mẫu theo biến xi
t-stat: Tiêu chuẩn t dùng làm căn cứ để kiểm định độ tin cậy về mặt khoa học (thống kê)
của độ co giãn ai (i = 1,2,3,n) tức là của mối liên hệ giữa X và Y.
P-value: Xác suất để t > t-stat, dùng kiểm định độ tin tin cậy về mặt khoa học (thống kê)
của độ co giãn ai (i = 1,2,3,n) tức là của mối liên hệ giữa X và Y.
Lower 95%, Upper 95%, Lower 98%, Upper 98%: là cận dưới và cận trên của khoảng
ước lượng cho các tham số với độ tin cậy 95% và độ tin cậy 98%.
Nhận xét: Dựa vào bảng kết quả trên ta có phương trình hồi quy:y = 0.204 * x1 + 3.321 * x2
+ 0.482 * x3 + 322.917
Như vậy khi x1 = 600, x2 = 35, x3 = 25 thì giá trị dự báo của y tính đượclà: y = 0.204 * 600 +
3.321 * 35 +0.452 * 25 + 322.917 = 573.731. Tức là lợinhuận sẽ đạt được là 573.731.000
đồng.
Ngoài ra, dựa vào bảng kết quả ta cũng thấy:
- Nếu chi phí quản lý x2 và chi phí bán hàng x3 không đổi thì cứ tăng 1 nghìn đồng giá
thành đơn vị x1 sẽ làm cho lợi nhuận y tăng lên 0.204 triệu đồng.
- Nếu giá thành đơn vị x1 và chi phí bán hàng x3 không đổi thì cứ tăng 1 triệu đồng chi phí
quản lý x2 sẽ làm cho lợi nhuận y tăng lên 3.321 triệu đồng.
- Nếu giá thành đơn vị x1 và chi phí quản lý x2 không đổi thì cứ tăng 1 triệu đồng chi phí
bán hàng x3 sẽ làm cho lợi nhuận y tăng lên 0.482 triệu đồng.
- Điểm xuất phát của mô hình b = 322.917 cho thấy các nhân tố khác làm tăng lợi nhuận
là 322.917 triệu đồng.
- Multiple R = 0.61 cho thấy mối quan hệ giữa các biến là tương đối chặt chẽ.
- R2 = 0.37 cho thấy trong 100% sự biến động của lợi nhuận thì có 37%biến động là do giá
thành đơn vị, chi phí quản lý và chi phí bán hàng, còn 63%là do các yếu tố ngẫu nhiên và
các yếu tố khác không có trong mô hình.
Một số thuật ngữ
Các lựa chọn nhập dữ liệu vào input
- Input X Range: Vùng địa chỉ chứa biến phụ thuộc Y.
- Input Y Range: Vùng địa chỉ chứa các biến độc lập X.
- Labels: Tùy chọn này cho phép chọn ô (các ô) đầu tiên không chứa dữ liệu hồi quy.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 324
Trường ĐH Sư phạm Tp. Hồ Chí Minh
- Constant in Zero: Chọn mục này để cho phép hệ số tự do của hàm hồi quy tuyến tính b =0
- Confidentce Level: Độ tin cậy của hồi quy (mặc định là 95%) bằng 1 – α với α là mức ý
nghĩa hay xác xuất mắc sai lầm loại một bác bỏ H0 trong khi H0 đúng.
Các lựa chọn kết xuất kết quả Output Option
- Output Range: Vùng hoặc ô phía trên bên trái của vùng chứa kết quả
- New Worksheet Ply: In kết quả ra một sheet khác
- New Workbook: In kết quả ra một file Excel mới
Một số lựa chọn khác Residuals: chọn mục này để đưa ra
- Residuals: Sai số đo ngẫu nhiên
- Standardardlized Residuals: Chuẩn hóa sai số
- Residuals Plots: Đồ thị sai số
- Line Fit Plots: Đồ thị hàm hồi quy tuyến tính
- Normal Probability: Xác suất phân phổi chuẩn
- Normal Probability Plots: Đồ thị xác xuất phân phối chuẩn
Dự báo bằng hồi quy phi tuyến
Các mô hình phi tuyến sau khi đưa được về dạng mô hình tuyến tinh ta sẽ tiến hành hồi quy,
kiểm định và dự báo như mô hình tuyến tính.
a. Các mô hình phi tuyến có thể biến đổi về mô hình tuyến tính
Để biến đối các mô hình phi tuyến về mô hình tuyến tính ta có thể sử dụng phương pháp logarit
hai vế của phương trình, đặt ẩn phụ Sau đây là một số mô hình phi tuyến có thể biến đổi về mô
hình tuyến tính:
Hàm sản xuất Cobb Douglas (CD)
Dạng hàm: Y = AX1
b1
X2
b2Xi
biXn
bn
(1)
Trong đó: Y là kết quả sản xuất. X1
b1
, X2
b2,,Xi
bi,,Xn
bn
là mức đầu tư các yếu tố sản xuất (đất
đai, lao động, công nghệ) cho sản xuất.
Đây là một hàm rất phù hợp với lý thuyết kinh tế về quy luật đầu tư thâm canh. Tính toán đơn
giản vì có thể đưa về dạng tuyến tính bằng cách logarit hoá hai vế của (1):
LnY = Ln A + b1LnX1 + + b2LnX2 ++ biLnXi ++ bnLnXn
Ta có thể viết lại là:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 325
Trường ĐH Sư phạm Tp. Hồ Chí Minh
LnY = b0 + b1LnX1 + + b2LnX2 ++ biLnXi ++ bnLnXn (2)
Đây chính là dạng mô hình tuyến tính với các biến là LnY (biến phụ thuộc) , LnX1 , LnX2
,, LnXi,, LnXn (các biến độc lập).
Phân tích các tham số của hàm CD:
- Hiệu suất của một đơn vị yếu tố i: 𝜕Y/ 𝜕Xi = bi* 𝑌 / 𝑋𝑖 ( i=1,2,...,n)
Có nghĩa là nếu đầu tư thêm 1 đơn vị của yếu tố sx i sẽ mang lại thêm 𝜕Y/𝜕Xi đơn vị sản phẩm,
với giả thiết là mức đầu tư các yếu tố khác không thay đổi.
- Độ co giãn của sản lượng theo yếu tố i: 𝜂Y Xi = (𝜕Y/ 𝑌 ) / (𝜕Xi/ 𝑋𝑖 ) = bi (i=1,2,...,n). Có
nghĩa là sản lượng tăng thêm bi% khi yếu tố sx i tăng thêm 1% , với giả thiết là mức đầu
tư các yếu tố khác không thay đổi.
Hồi quy Parabol
Hàm hồi quy Parabol là dạng phương trình của một tam thức bậc 2:
Y = aX
2
+bX + c + Ui với i = 1,2,,n
Để giải được bài toán này ta có 2 cách:
Ước lượng các tham số của dạng hồi quy Parabol theo phương pháp bình phương nhỏ
nhất:
𝑓 𝑎, 𝑏, 𝑐 = (𝑌𝑖 − 𝑎𝑋1
2 − 𝑏𝑋1 − 𝑐)
2
𝑛
𝑖=1
→ 𝑚𝑖𝑛
Do đó:
𝜕𝑓
𝜕𝑎
= 0;
𝜕𝑓
𝜕𝑏
= 0;
𝜕𝑓
𝜕𝑐
= 0
Hay:
𝑎 𝑋1
4 + 𝑏 𝑋1
3 + 𝑐 𝑋1
2 = 𝑋1
2 𝑌1
𝑎 𝑋1
3 + 𝑏 𝑋1
2 + 𝑐 𝑋1 = 𝑋1 𝑌1
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 326
Trường ĐH Sư phạm Tp. Hồ Chí Minh
𝑎 𝑋1
2 + 𝑏 𝑋1 + 𝑐𝑛 = 𝑌1
Giải hệ phương trình ta xác định được các hệ số của mô hình. Sau khi xácđịnh xong các hệ số của
mô hình ta sẽ viết được mô hình hồi quy.
Đặt X2 = X
2
= X*X rồi tiến hành ước lượng như đối với mô hình hồi quy tuyến tính.
Hồi quy Hyperbol đơn:
Hàm hồi quy Hyperbol đơn có dạng:
𝑌 =
𝑎
𝑋
+ 𝑏 + 𝑢𝑖 (𝑖 = 1, 2, , 𝑛)
Để giải được bài toán này sẽ có hai cách:
- Ước lượng các tham số của dạng hồi quy Hyperbol theo phương pháp bình phương nhỏ
nhất:
𝑓 𝑎, 𝑏 = 𝑌𝑖 –
𝑎
𝑋1
− 𝑏
2
→ 𝑚𝑖𝑛. 𝐷𝑜 đó:
𝜕𝑓
𝜕𝑎
𝑛
𝑖=1
= 0;
𝜕𝑓
𝜕𝑏
= 0
Hay: 𝑎
1
𝑋1
2 + 𝑏
1
𝑋1
=
𝑌1
𝑋1
và 𝑎
1
𝑋1
+ 𝑏𝑛 = 𝑌𝑖
Giải hệ phương trình ta tìm được các hệ số a và b rồi thay trở lại vào phương trình hồi quy
- Để đơn giản cho việc ước lượng trong MS Excel ta đặt Z=1/X rồi tiến hành ước lượng
tương tự như mô hình tuyến tính với hai ẩn Y và Z.
Hồi quy Hyperbol bội
Hàm hồi quy Hyperbol bội có dạng:
𝑌 = 𝑏0 +
𝑏1
𝑋1
+
𝑏2
𝑋2
+
𝑏3
𝑋3
+ +
𝑏𝑛
𝑋𝑛
Để chuyển về dạng hồi quy tuyến tính ta đặt Zi =1/Xi ta có phương trình được viết lại là:
Y = b0 + b1Z1 + b2Z2 + ...+ bnZn.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 327
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Với mô hình tuyến tính này ta tiến hành các bước như mô hình tuyến tính nghiên cứu ở phần trên.
Hồi quy mũ
Hàm hồi quy mũ có dạng: 𝑌 = 𝑒𝑏0+𝑏1𝑋1+𝑏2𝑋2+⋯+𝑏𝑛𝑋𝑛
Logarit cơ số e cho cả hai vế ta có: LnY = b0 + b1X1 + b2X2 + ... + bnXn.
Đây là mô hình hồi quy tuyến tính với biến phụ thuộc LnY và các biến độc lập X1, X2,, Xn.
Hồi quy dạng 𝒚 = 𝒃𝒂𝒙
Là dạng hàm mũ. Ta logarit cơ số e cho cả hai vế ta có: LnY = X.lna + lnb.
Từ số liệu điều tra thực tế ta tính được các gái trị Ln sẽ trở thành mô hình hồi quy tuyến tính đơn
với biến phụ thuộc LnY và biến độc lập X.
Xét ví dụ 1.5.4: Người ta khảo sát và thăm dò mối quan hệ của năm đại lượng Y, X1, X2,
X3, X4 được biết rằng mối phụ thuộc của chúng có dạng phương trình sau: Y = b + a1 * X1
+ a2 * LnX2 + a3 * X3
2
+ a4 * 1/X4. Với các sốliệu đã cho hãy hồi quy mô hình và dự báo Y khi
X1 = 20, X2 = 15, X3 = 50, X4= 8 với α =0.05
Hướng dẫn: Ta tiến hành theo các bước sau:
- Nhập, đặt và tính ẩn phụ cho các biến như trong hình sau:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 328
Trường ĐH Sư phạm Tp. Hồ Chí Minh
- Chọn Tools/Data Analysis/Regression/OK. Bảng hộp thoại Regression xuất hiện, điền
các thông tin như hình sau:
- Nhấn OK ta được kết quả sau
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 329
Trường ĐH Sư phạm Tp. Hồ Chí Minh
b. Sử dụng các hàm GROWTH và LOGEST
Ngoài việc sử dụng Regression cho mô hình hồi quy phi tuyến ta còn có thể sử dụng hàm
GROWTH và hàm LOGEST.
Sử dụng hàm GROWTH
- Dùng để hồi quy phi tuyến theo mô hình Y = b * mX
- Cú pháp
=GROWTH(known_y’s, known_x’s, new_x’s, const)
Trong đó:
known_y’s, known_x’s, new_x’s là các giá trị hoặc vùng địa chỉchứa giá trị đã
biết của x, y tương ứng và giá trị mới của x.
const là hằng số. Nếu const = 1 (True) tính hệ số tự do b (ngầm định), nếu const =
0 (False) bỏ qua hệ số b (b = 1).
Ví dụ 1.5.5 Giả sử giữa hai đại lượng X và Y có mối quan hệ hàm mũ: Y= b* mX. Với số liệu đã
cho ta nhập vào bảng và tiến hành dự báo Y khi X = 20 như trong hình sau:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 330
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Sử dụng hàm LOGEST
- Dùng để hồi quy phi tuyến theo mô hình:Y = b * m1
X
1* m2
X
2 ** mn
X
n
- Cú pháp:
LOGEST(known_y’s, known_x’s, const, stat)
Trong đó
known_y’s, known_x’s, stat giống như hàm LINEST.
const là hằng số. Nếu const = 1 (True) tính hệ số tự do b (ngầm
định), nếu const = 0 (False) bỏ qua hệ số b (b = 1).
Nếu bỏ qua giá trị của X thì giả thiết X = {1, 2, 3} với số
phần tử bằng số phần tử của Y.
Ví dụ 1.5.6 Giả sử giữa ba đại lượng Y, X1 và X2 có mối quan hệ hàm mũ: Y = b* m1
X
1* m2
X
2.
Với số liệu đã cho ta nhập vào bảng tính và tiến hành dự báo Y khi X1 = 12 và X2 = 25 như trong
hình sau:
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 331
Trường ĐH Sư phạm Tp. Hồ Chí Minh
TỔNG KẾT CHƢƠNG 6
Chương trình bảng tính là một dạng chương trình bao gồm nhiều ô, được tạo bởi các dòng và cột,
việc nhập dữ liệu và lập công thức tính toán trong các bảng tính điện tử.
Một số đặc tính tiêu biểu của chương trình bảng tính: Tổ chức và lưu trữ dữ liệu dưới dạng bảng;
thực hiện được các tính toán từ cơ bản đến nâng cao; tạo biểu đồ, đồ thị
Một số phần mềm bảng tính thông dụng hiện nay: Microsoft Office Excel 2003, Open Office 3.0
Calc, Google SpreadSheet
Các thành phần chính của một bảng tính điện tử: Thanh menu, Thanh công thức, Vùng làm việc
chính, Sheet tab, Panel,
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 332
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Chƣơng 7 Bài toán và thuật toán
Khái niệm vấn đề và bài toán.
Thuâṭ toán và các phương pháp biểu diêñ thuâṭ toán.
Các bước để giải một bài toán trên máy tính.
Chuyển đổi bài toán thành chương trình máy tính.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 333
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Ngày nay, công nghệ thông tin và truyền thông trở nên hết sức phổ biến. Các ứng dụng công
nghệ len lõi khắp các ngành nghề trong xã hội, chi phối cuộc sống, cách nghĩ, cách làm của con
người thời hiện đại. Sự bành trướng đó có sự góp phần không nhỏ của các chương trình máy
tính. Các chương trình máy tính được xây dựng bằng các ngôn ngữ lập trình nhưng nền tảng của
nó nằm ở các chỉ dẫn của con người, dựa trên tư duy của con người. Chương này sẽ đưa người
đọc bước đầu làm quen với những khái niệm về bài toán, thuật toán, hướng dẫn quá trình thiết kế
nên một thuật toán, các phương pháp biểu diễn thuận toán và làm cách nào chuyển đổi thuật
toán thành chương trình máy tính.
7.1 Khái niệm vấn đề - bài toán
7.1.1 Vấn đề - bài toán là gì?
Vấn đề được xem như những vướng mắc cần giải quyết. Vấn đề được biểu diễn dưới dạng bài
toán, có điều kiện ban đầu và kết quả cần đạt tới.
A B
A: Là giả thiết hay điều kiện ban đầu
B: Là kết luận hay kết quả cần đạt tới
: Là suy luận hay giải pháp giải quyết vấn đề
Bài toán trong tin học: Là việc nào đó ta muốn máy tính thực hiện.
7.1.2 Khái niệm thuật toán:
Một dãy hữu hạn các bước.
Các thao tác được sắp xếp theo một trình tự xác định.
Sau khi thực hiện dãy thao tác đó, từ giả thiết ta tìm được kết quả của bài toán.
Từ “Thuật toán" (Algorithm)? Xuất phát từ tên một nhà toán học người Trung Á là
Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả
một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc
cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được
xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời
dựa theo cách phiên âm tên của ông.
7.1.3 Các đặc trƣng khác của thuật toán
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 334
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Bên cạnh 3 đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm 3 đặc
trưng phụ khác.
Ðầu vào và đầu ra (input/output) : mọi thuật toán, dù có đơn giản đến mấy cũng
phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng.
Tính hiệu quả (effectiveness) :tính hiệu quả của thuật toán đượ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 khi thuật toán
được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá,
chọn lựa cách giải quyết vấn đề-bài toán trên thực tế.
Tính tổng quát (generalliness) :thuật toán có tính tổng quát là thuật toán phải áp
dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho
một số trường hợp riêng lẻ nào đó.
Ví dụ 1: Thuật toán giải phương trình bậc nhất ax+b=0
Bước 1: Nhập a, b.
Bước 2: Nếu a = 0 thì
B2.1: Nếu b=0 thì kết luận phương trình vô số nghiệm rồi qua bước 5
B2.2: Nếu b khác 0 thì kết luận phương trình vô nghiệm rồi qua bước 5
Bước 3: x -b/a, rồi qua bước 4.
Bước 4: Đưa ra kết quả x, qua bước 5
Bước 5: Kết thúc
Ví dụ 2: Thuật toán tìm giá trị nhỏ nhất trong dãy a1, a2, a3an
Bước 1: Nhập n và các phần tử của dãy a1, a2, a3, ,an.
Bước 2: Gán Mina1, i2.
Bước 3: Nếu i<=n thì thực hiện bước 4, còn không thì qua bước 5.
Bước 4: Nếu Min > ai thì gán Min ai
Tăng i lên một đơn vị rồi quay về bước 3.
Bước 5: Đưa ra Min rồi kết thúc.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 335
Trường ĐH Sư phạm Tp. Hồ Chí Minh
7.2 Các phƣơng pháp biểu diễn thuật toán
Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn từ toán học
như : "ta có", "điều phải chứng minh", "giả thuyết",... và sử dụng những phép suy luận toán học
như phép suy ra, tương đương, ...Thuật toán là một phương pháp thể hiện lời giải bài toán nên
cũng phải tuân theo một số quy tắc nhất định. Ðể có thể truyền đạt thuật toán cho người khác hay
chuyển thuật toán thành chương trình máy tính, ta phải có phương pháp biểu diễn thuật toán. Có
3 phương pháp biểu diễn thuật toán :
Dùng ngôn ngữ tự nhiên.
Dùng lưu đồ-sơ đồ khối (flowchart).
Dùng mã giả (pseudocode).
7.2.1 Ngôn ngữ tự nhiên
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày
để liệt kê các bước của thuật toán. Phương pháp biểu diễn này không yêu cầu người viết thuật
toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường
dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người
đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán 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.
• 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ƣớc 1: Bốc 3 que rồi đợi đối phương đi
– Bƣớc 2: Đối phương bốc (giả sử x que, 0<x<4)
– Bƣớc 3: Đến lượt người đi trước bốc a = (4-x) que. Nếu còn diêm thì quay lại
bước 2, ngược lại qua bước 4
– Bƣớc 4:Tuyên bố thắng cuộc. Kết thúc
7.2.2 Lƣu đồ - sơ đồ khối
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 336
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán
bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của
thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó
theo dõi được quá trình xử lý.
Trong sơ đồ khối, người ta dùng một số ký hiệu thể hiện các thao tác như :
Ký hiệu Mô tả
Điểm bắt đầu và kết thúc một thuật toán
Thao tác nhập hay xuất dữ liệu
Khối xử lý công việc
Khối quyết định chọn lựa
Dòng tính toán, thao tác của chương trình
Bảng 7.1 Bảng các ký hiệu trên lƣu đồ
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 337
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Ví dụ một lưu đồ thuật toán của bài toán so sánh 2 số nguyên a và b
Hình 7.1Lƣu đồ khối thuật toán so sánh 2 số nguyên a và b
7.2.3 Mã giả
Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại
cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu đồ
chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật
toán còn có thêm các thao tác lặp. Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú
pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, mọi ngôn ngữ lập trình
đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Dùng mã giả vừa tận dụng được các khái
niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất
nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và
khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 338
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Ví dụ: Một đoạn mã giả của thuật toán giải phƣơng trình bậc hai
if delta > 0 then begin
x1(-b-sqrt(delta))/(2*a)
x2(-b+sqrt(delta))/(2*a)
xuất kết quả : phương trình có hai nghiệm là x1 và x2
end
else
if delta = 0 then
xuất kết quả : phương trình có nghiệm kép là -b/(2*a)
else {trường hợp delta < 0 }
xuất kết quả : phương trình vô nghiệm
* Các từ in đậm là các từ khóa của ngôn ngữ Pascal
7.2.4 Thuật toán đệ quy
Thuật toán đệ quy là một trong những sự mở rộng cơ bản nhất của khái niệm thuật toán. Như đã
biết, một thuật toán cần phải thỏa mãn 3 tính chất :
Tính hữu hạn.
Tính xác định
Tính đúng đắn
Tuy nhiên, có những bài toán mà việc xây dựng một thuật toán với đầy đủ ba tính chất trên rất
khó khăn. Trong khi đó, nếu ta xây dựng một thuật toán vi phạm một vài tính chất trên thì cách
giải lại trở nên đơn giản hơn nhiều và có thể chấp nhận được. Một trong những trường hợp đó là
thuật toán đệ quy.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 339
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Tư tưởng giải bài toán bằng thuật toán đệ quy là đưa bài toán hiện tại về một bài toán cùng loại,
cùng tính chất (hay nói một cách nôm na là đồng dạng) nhưng ở cấp độ thấp hơn (chẳng hạn : độ
lớn dữ liệu nhập nhỏ hơn, giá trị cần tính toán nhỏ hơn, ....), và quá trình này tiếp tục cho đến lúc
bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ kết quả ở cấp độ này, ta sẽ lần
ngược để giải được bài toán ở cấp độ cao hơn cho đến lúc giải được bài toán ở cấp độ ban đầu.
Trong toán học ta cũng thường gặp những định nghĩa về những đối tượng, những khái niệm dựa
trên chính những đối tượng, khái niệm đó.
Ðịnh nghĩa giai thừa
Giai thừa của một số tự nhiên n, ký hiệu n! được định nghĩa là :
0! = 1
n! = (n-1)!n với mọi n>0
Ðịnh nghĩa dãy số Fibonacci
f0 = 1
f1 = 1
fn = fn-1 + fn-2 với mọi n>1
Theo toán học, những khái niệm được định nghĩa như vậy gọi là định nghĩa theo kiểu quy nạp.
Chính vì vậy, đệ quy có sự liên hệ rất chặt chẽ với quy nạp toán học. Ðệ quy mạnh ở điểm nó có
thể định nghĩa một tập vô hạn các đối tượng chỉ bằng một số hữu hạn các mệnh đề. Tuy nhiên,
đặc tính này của đệ quy lại vi phạm tính xác định của thuật toán. Về nguyên tắc, một bước trong
thuật toán phải được xác định ngay tại thời điểm bước đó được thi hành, nhưng với thuật toán đệ
quy, bước thứ n không được xác định ngay trong ngữ cảnh của nó mà phải xác định thông qua
một bước thấp hơn. Chẳng hạn, để tính được giá trị phần tử thứ 5 của dãy Fibonacci theo định
nghĩa ở trên, ta phải tính f3+f4, nhưng ta chưa biết giá trị f3 và f4 tại thời điểm này. Ðến đây, ta
phải lùi lại để tính f3 và f4. Ðể tính f3 ta lại phải lùi về để tính f2,...Tất nhiên, là quá trình tính lùi
này phải dừng sau một số hữu hạn bước. Trong trường hợp này, điểm dừng chính là giá trị f1 và
f0.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 340
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Ưu thế của thuật toán đệ quy là ta chỉ cần giải bài toán tại một số trường hợp đặc biệt nào đó, còn
gọi là trường hợp dừng. Sau đó, các trường hợp khác của bài toán sẽ được xác định thông qua
trường hợp đặc biệt này. Ðối với việc tính dãy Fibonacci, trường hợp dừng chính là giá trị của f0
và f1.
Nói một cách chính xác, mọi thuật toán đệ quy đều gồm hai phần:
Phần cơ sở
Là các trường hợp không cần thực hiện lại thuật toán (hay không có yêu cầu gọi đệ quy). Nếu
thuật toán đệ quy không có phần này thì sẽ dẫn đến bị lặp vô hạn và sinh lỗi khi thi hành. Vì lý
do này mà người ta đôi lúc còn gọi phần cơ sở là trường hợp dừng.
Phần đệ quy
Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại thuật toán nhưng với
một cấp độ dữ liệu thấp hơn.
7.3 Các bƣớc giải một bài toán trên máy tính
Việc sử dụng máy tính điện tử (MTÐT) để giải quyết một vấn đề nào đó thường được quan niệm
một cách không chuẩn xác, đơn giản đó chỉ là việc lập trình thuần túy. Thực ra, đó là cả một quá
trình phức tạp bao gồm nhiều giai đoạn phát triển mà lập trình chỉ là một trong các giai đoạn đó
(thậm chí chưa chắc đã là phần việc quan trọng nhất). Các bước quan trọng của toàn bộ quá trình
được liệt kê dưới đây:
7.3.1 Xác định vấn đề - bài toán.
Bước đầu tiên của bước phân tích hệ thống là nhằm phát biểu chính xác vấn đề - bài toán, làm rõ
những yêu cầu mà người sử dụng đòi hỏi. Sau khi nghiên cứu vấn đề được đặt ra, người phân tích
viên thiết lập mối phụ thuộc giữa các dữ kiện và kết quả phải tìm. Trên cơ sở có được mô hình
vấn đề - bài toán, người phân tích viên sẽ đánh giá, nhận định tính khả thi của vấn đề - bài toán
được đặt ra có đáng phải giải quyết không?
7.3.2 Lựa chọn phƣơng pháp giải.
Có thể có nhiều cách khác nhau để giải quyết vấn đề - bài toán đã thiết lập ở bước 1. Các phương
pháp có thể khác nhau về thời gian thực hiện. chi phí lưu trữ dữ liệu, độ chính xác... Nói chung
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 341
Trường ĐH Sư phạm Tp. Hồ Chí Minh
không có phương pháp tối ưu về mọi phương diện. Tùy theo nhu cầu cụ thể mà lựa chọn phương
pháp thích hợp. Việc lựa chọn trên cũng cần căn cứ vào khả năng xử lý tự động mà ta sẽ sử dụng.
7.3.3 Xây dựng thuật toán hoặc thuật giải.
Xây dựng mô hình chặt chẽ, chính xác hơn và chi tiết hóa hơn phương pháp đã lựa chọn. Xác
định rõ ràng dữ liệu vào, ra cho các bước thực hiện cơ bản và trật tự thực hiện các bước cơ bản
đó. 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
từng bước.
7.3.4 Cài đặt chƣơng trình.
Mô tả thuật giải bằng chương trình. Dựa vào thuật giải đã được xây dựng, căn cứ quy tắc của một
ngôn ngữ lập trình để soạn thảo ra chương trình thể hiện giải thuật thiết lập ở bước 3.
7.3.5 Hiệu chỉnh chƣơng trình.
Ở bước 4, nói chung chúng ta không tránh khỏi sai sót. Ở bước 5 này chúng ta cho chương trình
chạy thử để phát hiện và điều chỉnh các sai sót nếu tìm thấy.
Có hai loại lỗi:
Lỗi cú pháp là lỗi do không tuân thủ đúng các quy tắc viết chương trình trên một
ngôn ngữ lập trình cụ thể.
Lỗi ngữ nghĩa là lỗi làm sai lạc ý nghĩa hoặc dẫn đến bế tắc của chương trình. Lỗi
cú pháp thường dễ phát hiện và hiệu chỉnh hơn lỗi ngữ nghĩa. Cần phải nói rằng
việc hiệu chỉnh chương trình khá phức tạp, mất nhiều thời gian và công sức. Việc
xây dựng tốt, phù hợp, đầy đủ các bộ dữ liệu để kiểm chứng chương trình là hết
sức quan trọng, giúp phát hiện ra các lỗi ngữ nghĩa của chương trình cũng như có
thể có vấn đề gì đó bị bỏ sót.
7.3.6 Thực hiện chƣơng trình.
Cho MTÐT thực hiện chương trình. Tiến hành phân tích kết quả thu được. Việc phân tích kết quả
nhằm khẳng định kết quả đó có phù hợp hay không. Nếu không, cần kiểm tra lại toàn bộ các
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 342
Trường ĐH Sư phạm Tp. Hồ Chí Minh
bước một lần nữa. Nói chung, dù thận trọng đến mức nào đi nữa thì sau mỗi bước thực hiện nêu
trên cũng không khẳng định được kết quả thực hiện từng bước là đúng đắn tuyệt đối. Hơn nữa,
như ở bước 5, ta chỉ hiệu chỉnh tất cả các lỗi đã được phát hiện. Còn có thể có sai sót khác của
chương trình với một bộ dữ liệu nào khác phức tạp hơn mà ta chưa có cơ hội để phát hiện trước
đó. Do đó, ta không thể khẳng định được rằng, chương trình đúng tuyệt đối, không còn sai sót
nữa. Như vậy, việc giải quyết một vấn đề cụ thể thực hiện qua hai giai đoạn. Giai đoạn đầu là giai
đoạn quan niệm, gồm các bước phân tích, lựa chọn mô hình, xây dựng thuật giải, cài đặt chương
trình. Giai đoạn sau là khai thác và bảo trì chương trình. Trong quá trình sử dụng, nói chung
thường có nhu cầu về cải tiến, mở rộng chương trình do các yếu tố của bài toán ban đầu có thể
thay đổi.
7.4 Các bƣớc thiết kế thuật toán
Bước 1: Xác định vấn đề bài toán (input, output)
Bước 2: Hình thành ý tưởng chính để để xây dựng thuật toán (bài toán giải bằng cách
nào? Thuật toán sẽ dừng khi nào?)
Bước 3: Xây dựng thuật toán (ngôn ngữ tự nhiên, lưu đồ, mã giả)
Bước 4: Mô phỏng để kiểm tra tính đúng đắn của thuật toán (chạy thử bằng tay)
Một số ví dụ
Ví dụ 1: Kiểm tra một số nguyên a là số chẵn hay số lẻ
Xác định bài toán
Input: số nguyên a
Output: thông báo a chẵn hay lẻ
Hình thành ý tưởng
Một số là số chẵn khi nó chia hết cho 2, vậy thì ta chỉ cần kiểm tra xem nó có chia
hết cho 2 hay không.
Xây dưng thuật toán:
Cách 1: Dùng ngôn ngữ tự nhiên
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 343
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Bước 1: Nhập a
Bước 2: Nếu a chia hết cho 2 thì xuất a chẵn
Ngược lại thì xuất a lẻ. Qua bước 3
Bước 3: Kết thúc
Cách 2: Dùng lưu đồ
Hình 7.2Lƣu đồ khối thuật toán kiểm tra số chẵn
Mô Phỏng thuật toán:
Nhập a: 18 xuất ra: 18 là số chẵn
Ví dụ 2: Tìm số lớn nhất trong dãy số
Xác định vấn đề - bài toán:
Input: Số nguyên dương N và dãy N số nguyên
a1, a2, , aN (ai với i : 1N).
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 344
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Output: Số lớn nhất (Max) của dãy số.
Lựa chọn phương pháp giải:
Đặt giá trị Max a1.
Cho i chạy từ 2 đến N, so sánh giá trị ai với giá trị Max, nếu ai> Max thì Max
nhận giá trị mới là ai.
Max là giá trị lớn nhất cần tìm
Hình thành ý tưởng:
Ví dụ dãy số này bị che kín bằng các tấm bìa, ta lật tấm đầu tiên và xem như nó là lớn nhất, ta lần
lượt lật các tấm bìa còn lại, mỗi lần lật ta so sánh với tấm bìa đầu tiên, tấm nào lớn hơn giá trị lớn
nhất thì ta thay lại giá trị lơn nhất đó. Khi nào hết dãy số thì ta đưa ra số lớn nhất.
Xây dựng thuật toán:
Cách 1: Dùng ngôn ngữ tự nhiên
Bước 1: Nhập N và dãy a1,a2, aN;
Bước 2: Max a1; i 2;
Bước 3: Nếu i > N thì đưa ra giá trịMax rồi kết thúc;
Bước 4: Nếu ai > Max thì Max ai;
Bước 5: i i+1 rồi quay lại B3.
Cách 2: Dùng sơ đồ khối
Hình 7.3Lƣu đồ khối thuật toán tìm số lớn nhất trong dãy số
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 345
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Mô Phỏng thuật toán:
Với dãy số A: 3, 6, 7, 2, 8, 4 (N=6)
Max3, i2
iMax vậy Max6, ii+1 =3
iMax vậy Max7, ii+1 =4
i<N, a4=2<Max vậy Max7, ii+1 =5
iMax vậy Max8, ii+1 =6
i=N, a6=4>Max vậy Max8, ii+1 =7
i>N vậy Max = 8, kết thúc
7.5 Chuyển đổi bài toán thành chƣơng trình máy tính
7.5.1 Khái niệm về ngôn ngữ lập trình & chƣơng trình máy tính
Con người liên lạc với nhau thông qua ngôn ngữ, tạo ra các mẫu từ ngữ và âm thanh. Ngôn ngữ
lập trình cũng tương tự như vậy, đó là một tập từ ngữ và ký hiệu cho phép lập trình viên hoặc
người dùng có thể nói chuyện với máy tính. Cũng giống như tiếng Anh, tiếng Tây Ban Nha hoặc
tiếng Trung Quốc và những ngôn ngữ tiếng nói khác, ngôn ngữ lập trình cũng có các luật được
gọi là cú pháp (syntax) để đảm bảo ngôn ngữ đó được vận dụng một cách chính xác.
Ðó là một tập các chỉ thị (instruction) được sắp xếp theo một trật tự định trước nhằm hướng dẫn
máy tính thực hiện các thao tác, hành động cần thiết để đáp ứng một mục tiêu đã định trước của
con người như truy xuất dữ liệu, tìm kiếm, giải bài toán, ...Các chỉ thị này có thể được viết bằng
nhiều ngôn ngữ lập trình khác nhau.
7.5.2 Các loại ngôn ngữ lập trình thông dụng
Có hàng trăm loại ngôn ngữ lập trình khác nhau, mỗi loại ngôn ngữ đều có cú phápriêng của nó.
Một số ngôn ngữ thì được phát triển để dùng trên các loại máy tính chuyên biệt, một số ngôn ngữ
khác thì - do sự thành công của nó - đã trở thành chuẩn và được áp dụng trên đa số các máy tính.
Ngôn ngữ lập trình có thể được phân chia thành 3 loại chính : ngôn ngữ máy, hợp ngữ và ngôn
ngữ cấp cao.
7.5.2.1 Ngôn ngữ máy
Ngôn ngữ máy (mã máy) là ngôn ngữ nền tảng của bộ vi xử lý. Các chương trình được viết trong
tất cả các loại ngôn ngữ khác cuối cùng đều được chuyển thành ngôn ngữ máy trước khi chương
trình đó được thi hành. Vì tập lệnh của ngôn ngữ máy phụ thuộc vào loại vi xử lý nên ngôn ngữ
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 346
Trường ĐH Sư phạm Tp. Hồ Chí Minh
máy sẽ khác nhau trên những máy tính có sử dụng bộ vi xử lý khác nhau. Lợi điểm của viết
chương trình bằng ngôn ngữ máy là lập trình viên có thể điều khiển máy tính trực tiếp và đạt
được chính xác điều mình muốn làm. Do đó, các chương trình ngôn ngữ máy được viết tốt là
những chương trình rất hiệu quả (tốc độ thi hành nhanh, kích thước nhỏ). Bất lợi của chương
trình ngôn ngữ máy là thông thường sẽ mất rất nhiều thời gian để viết, rất khó đọc, theo dõi để
tìm lỗi. Thêm vào đó, bởi vì chương trình được viết bằng tập lệnh phụ thuộc vào bộ vi xử lý nên
chương trình chỉ chạy được trên những máy tính có cùng bộ vi xử lý mà thôi. Ngôn ngữ máy
cũng được gọi là ngôn ngữ cấp thấp (low-level language).
7.5.2.2 Hợp ngữ
Hợp ngữ được phát triển nhằm giúp các lập trình viên dễ nhớ các chỉ thị của chương trình hơn.
Hợp ngữ tương tự như ngôn ngữ máy nhưng lại sử dụng các ký hiệu gợi nhớ (mnemonics hay mã
lệnh hình thức - symbolic operation code) để biểu diễn cho các mã lệnh của máy. Một đặc điểm
khác nữa là hợp ngữ thông thường cho phép định địa chỉ hình thức (symbolic addressing), nghĩa
là một vị trí bộ nhớ trong máy tính có thể được tham chiếu tới thông qua một cái tên hoặc ký
hiệu, chẳng hạn như TOTAL thay vì phải sử dụng địa chỉ thực sự của nó (bằng con số nhị phân)
trong ngôn ngữ máy. Các chương trình hợp ngữ còn bao gồm các chỉ thị vĩ mô (macro
instruction) có thể tạo ra nhiều lệnh mã máy. Các chương trình hợp ngữ được chuyển sang mã
máy thông qua một chương trình đặc biệt gọi là trình hợp dịch (assembler). Mặc dù hợp ngữ
tương đối dễ dùng hơn mã máy nhưng hợp ngữ vẫn được xem là ngôn ngữ cấp thấp bởi vì nó vẫn
còn rất gần với từng thiết kế của máy tính.
7.5.2.3 Ngôn ngữ cấp cao
Cuộc cách mạng của ngôn ngữ máy tính bắt đầu với sự phát triển của ngôn ngữ cấp cao vào cuối
thập kỷ 1950 và 1960. Ngôn ngữ cấp cao gần gũi hơn với ý niệm ngôn ngữ mà hầu hết mọi người
đều biết, nó bao gồm các danh từ, động từ, ký hiệu toán học, liên hệ và các thao tác luận lý. Các
yếu tố này có thể được phối hợp, liên kết với nhau tạo thành một hình thức của câu. Các "câu"
này được gọi là các mệnh đề của chương trình (program statement). Chính vì những đặc điểm
này, các lập trình viên dễ dàng đọc và dễ học ngôn ngữ cấp cao hơn so với ngôn ngữ máy hoặc
hợp ngữ. Một lợi điểm quan trọng là ngôn ngữ cấp cao thông thường không phụ thuộc vào máy
tính, nghĩa là các chương trình viết bằng ngôn ngữ cấp cao có thể chạy trên các loại máy tính
khác nhau (sử dụng các bộ vi xử lý khác nhau).
7.5.3 Trình thông dịch và biên dịch
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 347
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Mọi chương trình được viết bằng các ngôn ngữ không phải là ngôn ngữ máy cuối cùng đều phải
được chuyển đổi sang ngôn ngữ máy trước khi được thi hành. Chương trình ngôn ngữ cấp cao
được dịch sang ngôn ngữ máy bằng một trong hai cách : bằng trình biên dịch (compiler) hoặc
trình thông dịch (interpreter).
7.5.3.1 Trình biên dịch :
Sẽ chuyển đổi toàn bộ chương trình sang mã máy, rồi chứa kết quả vào đĩa để có thể thi hành về
sau. Chương trình ngôn ngữ cấp cao được chuyển đổi được gọi là chương trình nguồn (source
program) và chương trình ngôn ngữ máy được tạo ra được gọi là chương trình đối tượng (object
program) hoặc mã đối tượng (object code). Khi người dùng muốn chạy chương trình, chương
trình đối tượng sẽ được nạp lên bộ nhớ chính của CPU và các chỉ thị của chương trình sẽ được thi
hành. Khi được hướng dẫn bởi các chỉ thị của chương trình, CPU sẽ truy xuất dữ liệu và tạo ra
các kết quả. Trình biên dịch sẽ kiểm tra cú pháp chương trình, thực hiện các phép kiểm tra logic
và đảm bảo các dữ liệu sắp được sử dụng trong các phép so sánh, tính toán đã được định nghĩa
một cách hợp lý ở một nơi nào đó trong chương trình. Một chức năng quan trọng của trình biên
dịch là nó sẽ tạo ra một danh sách lỗi của tất cả mệnh đề trong chương trình vi phạm cú pháp của
ngôn ngữ. Danh sách này giúp lập trình viên dễ dàng sửa đổi chương trình.
Do ngôn ngữ máy phụ thuộc vào bộ vi xử lý nên các máy tính khác nhau sẽ cần có các trình biên
dịch khác nhau đối với cùng một ngôn ngữ cấp cao. Ví dụ, một máy mainframe, máy mini và
máy tính cá nhân cần có các trình biên dịch khác nhau để biên dịch cùng một chương trình nguồn
sang mã máy của từng loại máy này.
7.5.3.2 Trình thông dịch
Thay vì chuyển đổi toàn bộ chương trình nguồn như trình biên dịch, trình thông dịch chỉ chuyển
đổi một mệnh đề của chương trình và thực hiện đoạn mã kết quả ngay, sau đó nó tiếp tục chuyển
đổi mệnh đề thứ 2 rồi thi hành đoạn mã kết quả thứ 2 và cứ thế. Khi sử dụng trình thông dịch,
mỗi lần chạy chương trình là mỗi lần chương trình nguồn được thông dịch sang ngôn ngữ máy.
Không có chương trình đối tượng nào được tạo ra.
Các trình thông dịch thường được dùng trên các máy tính cá nhân không có đủ bộ nhớ hoặc sức
mạnh tính toán cần thiết để dùng trình biên dịch. Lợi điểm của trình thông dịch là lập trình viên
vẫn có thể chạy một chương trình vẫn còn lỗi cú pháp. Chỉ đến lúc thông dịch đến câu lệnh có lỗi
cú pháp, quá trình thi hành chương trình mới bị ngừng lại và trình thông dịch sẽ thông báo lỗi.
Ðiểm bất lợi là các chương trình thông dịch chạy không nhanh bằng các chương trình được biên
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 348
Trường ĐH Sư phạm Tp. Hồ Chí Minh
dịch vì quá trình chuyển đổi sang ngôn ngữ máy được thực hiện cùng với quá trình thi hành
chương trình. Vì lý do này, ngày nay, đa số các ngôn ngữ cấp cao đều dùng trình biên dịch.
7.5.4 Các ngôn ngữ lập trình thông dụng
Mặc dù đã có hàng trăm ngôn ngữ lập trình được sinh ra, chỉ có một số ít là được sử dụng rộng
rãi và được xem là một chuẩn công nghiệp. Các ngôn ngữ này đều có thể được sử dụng trên nhiều
loại máy tính khác nhau.
BASIC: viết tắt của cụm từ Beginner's All-Purpose Symbolic Instruction Code, được
phát triển bởi John Kermeny và Thomas Kurtz vào năm 1964 tại trường đại học
Dartmouth. Ban đầu, họ thiết kế BASIC là một ngôn ngữ lập trình đơn giản, có tính tương
tác để các sinh viên học tập và sử dụng. BASIC đã trở thành một trong những ngôn ngữ
lập trình thông dụng nhất được sử dụng trên các máy vi tính và máy tính mini ngày nay.
COBOL: viết tắt của COmmon Business Oriented Language, được giới thiệu vào năm
1960. Ðược hỗ trợ bởi bộ quốc phòng Hoa Kỳ, COBOL được phát triển bởi một hội đồng
bao gồm các đại diện từ phía chính phủ và công nghiệp. Grace M.Hopper là người chính
yếu trong hội đồng và được xem là nhà phát triển chính của ngôn ngữ COBOL. COBOL
đã từng là một trong những ngôn ngữ được dùng rộng rãi nhất cho các ứng dụng thương
mại. Bằng cách dùng một hình thức tựa tiếng Anh, các câu lệnh của COBOL được sắp
xếp vào trong các câu và nhóm lại thành từng đoạn (paragraph). Hình thức tiếng Anh giúp
COBOL dễ viết và đọc nhưng cũng làm cho chương trình nguồn dài hơn. COBOL rất tốt
trong việc xử lý các tập tin lớn và thực hiện nhưng phép tính thương mại tương đối đơn
giản.
C: được phát triển bởi tác giả Dennis Ritchie tại phòng thí nghiệm Bell vào năm 1972.
Ban đầu, C được thiết kế như là một ngôn ngữ để viết các phần mềm hệ thống, nhưng
ngày nay, nó được xem là một ngôn ngữ công dụng chung. C là một ngôn ngữ lập trình
mạnh mẽ đòi hỏi kỹ năng lập trình chuyên nghiệp mới có thể sử dụng hiệu quả được. Nhu
cầu dùng C để phát triển nhiều loại phần mềm kể cả các ứng thương mại đang gia tăng.
Các chương trình C thường được dùng với hệ điều hành Unix (phần lớn hệ điều hành
Unix được viết bằng C).
FORTRAN: viết tắt của FORmula TRANslator được phát triển bởi một nhóm lập trình
viên của công ty IBM dưới sự lãnh đạo của John Backus. Công bố vào năm 1957,
FORTRAN được thiết kế như là một ngôn ngữ lập trình dành cho các nhà khoa học, kỹ sư
và toán học. FORTRAN được xem như là ngôn ngữ lập trình cấp cao đầu tiên và được
chú ý bởi khả năng của nó cho phép dễ dàng diễn đạt và tính toán các phương trình toán
học.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 349
Trường ĐH Sư phạm Tp. Hồ Chí Minh
PASCAL: ngôn ngữ sẽ được sử dụng để giảng dạy trong giáo trình này, được phát triển
vào năm 1968 bởi Niklaus Wirth, một nhà khoa học máy tính tại Zurich, Thụy Sĩ. Pascal
được phát triển để giảng dạy lập trình. Tên Pascal không phải là từ viết tắt, đó là tên của
một nhà toán học, Blaise Pascal (1623 - 1662) người đầu tiên tạo ra máy tính. Pascal,
dùng trong cả máy tính cá nhân và máy tính lớn là một trong những ngôn ngữ lập trình
đầu tiên được phát triển trong đó khuyến khích phương pháp lập trình cấu trúc.
ALGOL (ALGOrithmetic Language): ngôn ngữ lập trình cấu trúc dùng cho các ứng
dụng khoa học và toán học.
APL(AProgramming Language). Một ngôn ngữ mạnh mẽ, dễ dùng, rất tốt trong việc xử
lý dữ liệu được lưu dưới dạng bảng (ma trận)
FORTH: tương tự như C, tạo ra các mã chương trình nhanh và hiệu quả. Ban đầu được
phát triển để điều khiển kính viễn vọng không gian.
LISP - LISt Processing: ngôn ngữ trí tuệ nhân tạo thông dụng.
LOGO: chủ yếu được biết đến như là một công cụ để dạy khả năng giải quyết vấn đề.
MODULA-3: tương tự như PASCAL, dùng chủ yếu để phát triển các phần mềm hệ
thống.
PILOT -Programmed Inquiry Learning Or Teaching: dùng bởi các nhà giáo dục để viết
các chương trình hướng dẫn CAD.
PL/I - Programming Language/ One: ngôn ngữ thương mại và khoa học phối hợp nhiều
chức năng của FORTRAN và COBOL.
PROLOG - PROgramming Logic: dùng trong trí tuệ nhân tạo.
RPG - Report Program Generator: dùng các mẫu đặc biệt để giúp người dùng xác định
dữ liệu vào, dữ liệu ra và các yêu cầu tính toán của một chương trình.
ADA: lấy tên của Augusta Ada Bryon, người được xem là đã viết chương trình đầu tiên,
được thiết kế để phục vụ cho việc viết, bảo trì các chương trình lớn trong một khoảng thời
gian dài.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 350
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Bài tập chƣơng 7
Hãy xây dựng thuật toán (dùng cả 3 loại: ngôn ngữ tự nhiên, lưu đồ, mã giả) cho các bài toán sau:
1. Thiết kế thuật toán theo phương pháp dùng ngôn ngữ tự nhiên cho các bài toán sau:
a) Kiểm tra 2 số a, b giống nhau hay khác nhau.
b) Kiểm tra 1 số a chẵn hay lẻ
c) Giải phương trình bậc 2: ax2 + bx + c = 0
2. Thiết kế thuật toán theo phương pháp dùng phương pháp lưu đồ cho các bài toán sau:
a) Nhập vào 4 số xuất ra phần tử lớn nhất và nhỏ nhất?
b) Kiểm tra xem 1 số n có phải là số nguyên tố?
c) Kiểm tra xem 1 số n có phải là số hoàn thiện?
Thiết kế thuật toán theo phương pháp dùng phương pháp mã giả cho các bài toán sau:
3. Có n hộp có khối lượng khác nhau và một cái cân dĩa. Tìm cách cân để tìm được hộp có
trọng lượng nặng nhất.
4. Tìm ước số chung lớn nhất của a và b.
5. Nhập vào 3 số nguyên dương, kiểm tra xem 3 số đã cho có tạo thành tam giác không?
Nếu có là tam giác gì? (Đều, cân, vuông, vuông cân, thường).
6. Mô phỏng thuật toán (Chạy tay)
7. Kiểm tra số nguyên tố (19, 20, 27, 29)
8. Tìm UCLN của (12,15), (19, 27), (24,45)
9. Tìm max trong dãy số: 1, 6 , 3, 15, 7, 9, 4
10. Sắp xếp dãy số tăng dần: 1, 6 , 3, 15, 7, 9, 4
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 351
Trường ĐH Sư phạm Tp. Hồ Chí Minh
TÀI LIỆU THAM KHẢO
Chương 1
Tiếng Việt
[1] ThS. Đỗ Thanh Liên Ngân, Ks. Hồ Văn Tú (2005), Giáo trình Tin học căn bản,
trường Đại học Cần Thơ.
[2] TS. Nguyễn Thanh Phương, ThS. Đặng Bình Phương (2010), Giáo trình Tin học cơ
sở, trường Đại học Khoa Học Tự Nhiên TPHCM.
[3] Giáo trình Học Điện tử Chính thức của Microsoft(2006) ,Căn bản về máy tính.
Chương 2
Tiếng Việt
[1] Nguyễn Quang Tấn. (2004). Giáo trình Mạng Máy Tính, lưu hành nội bội, Đại học Sư
Phạm TP.HCM.
[2] Vũ Thị Nha. (2007). Tìm kiếm thông tin trên Internet, tài liệu cho học viên, Trung
Tâm Thông Tin Phát Triển Việt Nam
Tiếng Anh
[1] Open University. (2009). Information on the web. Retrieved 8/2011
[2] UNESCO. (2001). The Internet as an Information Resource, ICT for Library and
Information Professionals.
Retrieved 8/2011.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 352
Trường ĐH Sư phạm Tp. Hồ Chí Minh
[3] Strickland, Jonathan. (5/2010).How does the Internet work?HowStuffWorks.com.
Retrieved 8/2011
[4] Tyson, Jeff. (4/2001). How Internet Infrastructure Works. HowStuffWorks.com.
Chương 3
Tiếng Việt
[1] Trung Tâm Tin Học, đại học Sư phạm TPHCM (2007), Bài giảng Microsoft Word.
Tiếng Anh
[2] Microsoft Office Word 2007 QuickSteps
Website
Chương 4
Tiếng Việt
[1] Trần Thanh Phong(27/08/2008), Trình diễn báo cáo bằng PowerPoint 2007,Chương
Trình Giảng Dạy Kinh tế Fulbright.
[2] Công ty Cổ phần MISA biên soạn(4/2007),Trình diễn hội thảo OpenOffice.org
Impress.
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 353
Trường ĐH Sư phạm Tp. Hồ Chí Minh
[3] Bộ khoa học và công nghệ(2009), Hướng dẫn sử dụng OpenOffice.org Impress 3.0.
[4] Đậu Quang Tuấn, cử nhân toán – kỹ sư tin học (2008), Xây dựng diễn hình bằng
Microsoft PowerPoint 2007, nhà xuất bản Giao Thông Vận Tải.
Website
[1]
[2]
Chương 5
Tiếng Anh
[1] Mohamed Amin Embi (2011), Web 2.0 Tools in Education: A Quick Guide, Centre of
Academic Advencement, University Kebangsaan, Malaysia.
[2] Baker, P. 1999, Creating learning communities: The unfinished agenda, In B.A.
[3] Pescosolido & R. Aminzade (Eds.), The social works of higher education (pp. 95-
109), Thousand Oaks, CA: Pine Forge Press.
[4] Caroline Lego Muñoz & Terri L Towner (2009), Opening Facebook: How to
UseFacebook in the College Classroom
[5] Carmen Holotescu & Gabriela Grosseck (2008), Using microblogging in
education
[6] Mazer, J. P., Murphy, R.E., & Simonds, C. J. 2007, I‟ll see you on „Facebook‟:
Theeffects of computer-mediated teacher self-disclosure on student motivation,affective
learning, and classroom climate, Communication Education, 56, 1-17.
[7] PennState. 2007, 7 Things You Need to Know about Facebook Applications.
Chương 6
Giáo trình Tin học đại cương
Bản quyền thuộc Khoa Công nghệ thông tin Trang 354
Trường ĐH Sư phạm Tp. Hồ Chí Minh
Tiếng Việt
[1] Nguyễn Anh Dũng, Microsoft Excel 2003, Trung tâm công nghệ thông tin, đại học
Huế.
Chương 7
[1] Lê Hoài Bắc, Lê Hoàng Thái, Nguyễn Phương Thảo, Nguyễn Tấn Trần Minh Khang
(2005), Giáo trình Tin học Đại cương A2, NXB Đại học Quốc gia Tp.HCM.
[2] GS.TS Hoàng Kiếm, Giải một bài toán trên máy tính như thế nào, NXB Giáo Dục,
2011
[3] Nguyễn Tiến Hu, Dạy lập trình với AML, ĐH Khoa Học Tự Nhiên, 2006
Các file đính kèm theo tài liệu này:
- _bq_giao_trinh_tin_hoc_dai_cuong_p2_402.pdf