Giáo trình Tin học đại cương - Lê Đức Long (Phần 2)

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 Mina1, i2. 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 : 1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 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) Max3, i2 iMax vậy Max6, ii+1 =3 iMax vậy Max7, ii+1 =4 i<N, a4=2<Max vậy Max7, ii+1 =5 iMax vậy Max8, ii+1 =6 i=N, a6=4>Max vậy Max8, ii+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