›

Bài giảng Thuật toán và chương trình - Nguyễn Thanh Trung

ppt 55 trang huongle 3290
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán và chương trình - Nguyễn Thanh Trung", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_thuat_toan_va_chuong_trinh_nguyen_thanh_trung.ppt

Nội dung text: Bài giảng Thuật toán và chương trình - Nguyễn Thanh Trung

  1. THUẬT TOÁN & CHƯƠNG TRÌNH Nguyễn Thanh Trung Giải thuật & chương trình 1
  2. MỤC TIÊU ◼ Giới thiệu tổng quan về thuật toán và cách chuyển từ 1 thuật toán thành 1 chương trình bằng một ngôn ngữ lập trình cụ thể (C). ◼ Những yêu cầu khi xây dựng thuật toán: tính đúng đắn, khả thi, cũng như xác định độ phức tạp của thuật toán. Giải thuật & chương trình 2
  3. Bố cục ◼ Giới thiệu tổng quan ◼ Trình bày và triển khai thuật toán ◼ Đánh giá thuật toán ◼ Cài đặt Chương trình Giải thuật & chương trình 3
  4. Tài liệu tham khảo ◼ -Chương 5,6 Computer Science ◼ -Chương 5 bài giảng Giới thiệu Khoa học Máy tính. Giải thuật & chương trình 4
  5. 5.1. Tổng quan ◼ Máy tính? ❑ Làm theo “lệnh” của con người. ❑ Điểm mạnh là tính toán với tốc độ cao (hàng tỷ phép tính trên giây). ◼ Làm thế nào để “ra lệnh”cho máy tính? ❑ Lập chương trình cho máy tính ◼ Chương trình? ❑ Nói cho máy tính biết phải làm gì, như thế nào, Giải thuật & chương trình 5
  6. ◼ Muốn “ra lệnh” cho máy tính: Sử dụng một “ngôn ngữ” chung → ngôn ngữ lập trình (programming language) ◼ Lập trình (computer programming) ❑ Dùng ngôn ngữ lập trình lập nên chương trình hoạt động cho máy tính. ◼ Các thế hệ của ngôn ngữ lập trình ❑ Thế hệ 1 (bậc thấp): ngôn ngữ máy, assembly. ❑ Thế hệ 2: Gần với ngôn ngữ tự nhiên hơn, phục vụ những nhu cầu lập trình nhất định (FORTRAN, COBOL, ALGOL, ) ❑ Thế hệ 3: Gần gũi, vạn năng (PASCAL, C, C++, ) ❑ Thế hệ 4: Truy vấn, hỗ trợ quyết định, lập trình trí tuệ nhân tạo ❑ (SQL, LISP, PROLOG, ) Giải thuật & chương trình 6
  7. Thuật toán ◼ Giải thuật, thuật giải, thuật toán đều dùng để ám chỉ một thuật ngữ tiếng Anh có tên là ALGORITHM. ◼ Chúng ta sẽ tìm hiểu: ❑ Giải thuật theo cách hiểu thông thường ❑ Các thao tác trong giải thuật ❑ Định nghĩa giải thuật Giải thuật & chương trình 7
  8. ◼ Theo nghĩa rộng, khái niệm “giải thuật” (algorithm) được sử dụng ở mọi nơi, không riêng gì trong lĩnh vực tin học. ◼ Giải thuật là một loạt các thao tác (operation) có thứ tự (order) nhằm giải quyết một bài toán nào đó. ◼ Ví dụ: “Thuật toán nấu cơm” ❑ Bước 0: Ước lượng gạo cần thiết ❑ Bước 1: Vo gạo ❑ Bước 2: Cho gạo và nước thích hợp vào nồi cơm điện(NCĐ) ❑ Bước 3: Cắm điện, chuyển chế độ “cook” ❑ Bước 4: Chờ đến khi NCĐ chuyển sang chế độ “warm” ❑ Bước 5: Chờ thêm 10 phút nữa ❑ Bước 6: Cơm chín, kết thúc. Giải thuật & chương trình 8
  9. Các thao tác trong giải thuật ◼ Thao tác tuần tự (sequential operation): Một công việc đã được xác định rõ ràng, thực hiện xong thì chuyển sang công việc khác. ◼ Thao tác kiểm tra điều kiện (conditional operation): Kiểm tra điều kiện đưa ra có thoả mãn hay không để quyết định thao tác tiếp theo. ◼ Thao tác lặp (iterative operation): Quay trở lại bước nào đó trong dãy thao tác. Một thao tác có thể được lặp đi lặp lại nhiều lần tới khi một điều kiện nào đó được thoả mãn Giải thuật & chương trình 9
  10. Định nghĩa về giải thuật ◼ Giải thuật là một dãy các câu lệnh chặt chẽ và rõ ràng xác định một trình tự thao tác trên một đối tượng nào đó sao cho sau một số bước hữu hạn thực hiện, ta thu được kết quả mong muốn. ◼ Câu lệnh (statement/instruction): đơn vị thao tác, tính toán, xử lý ◼ Trình tự rõ ràng (well-ordered): thực hiện xong bước này mới chuyển sang bước khác, không nhập nhằng. ◼ Đối tượng (object): các dữ kiện của bài toán, dữ liệu trung gian, kết quả, ◼ Kết quả (result): Thông tin, lời giải cho bài toán, Giải thuật & chương trình 10
  11. Yêu cầu đối với giải thuật ◼ Tính dừng: Một giải thuật bất kỳ phải đảm bảo dừng sau một số hữu hạn bước. ◼ Tính đúng đắn: Giải thuật phải đảm bảo giải quyết bài toán một cách đúng đắn, cho kết quả “chính xác” và “đầy đủ” theo yêu cầu. ◼ Tính đơn giản và hiệu quả ❑ Đơn giản: Dễ hiểu, dễ lập trình. ❑ Hiệu quả: Tiêu tốn ít thời gian và tài nguyên máy tính Giải thuật & chương trình 11
  12. Mọi bài toán đều có giải thuật ? ◼ Có những bài toán không có giải thuật tổng quát để giải quyết. ◼ Có những bài toán chưa có giải thuật hữu hiệu để giải quyết. ◼ Có những bài toán chưa có giải thuật tìm lời giải. Giải thuật & chương trình 12
  13. 5.2. Trình bày và triển khai thuật toán ◼ Liệt kê từng bước ◼ Sơ đồ khối ◼ Sử dụng giả ngôn ngữ Giải thuật & chương trình 13
  14. 5.2.1. Liệt kê từng bước ◼ Các thao tác của giải thuật được liệt kê từng bước ◼ Tại mỗi bước, sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm. ◼ Bước đứng trước (có số thứ tự nhỏ hơn) được thực hiện trước. ◼ Ưu nhược điểm ❑ Dễ hiểu, dễ làm ❑ Phụ thuộc vào “cách hành văn” của người diễn đạt ❑ Với những giải thuật phức tạp, cách diễn đạt này trở nên rườm rà ❑ Giải thuật & chương trình 14
  15. Ví dụ 1: Giải phương trình bậc nhất ax+b=0 ◼ 1. Nhập a,b. ◼ 2. Nếu a=0 và b=0 thì viết “Phương trình nghiệm đúng với mọi x” rồi sang bước 5. ◼ 3. Nếu a=0 và b # 0 thì viết “Phương trình vô nghiệm” rồi sang bước 5. ◼ 4. Nếu a # 0 thì tính x=-b/a rồi viết x là nghiệm. ◼ 5. Kết thúc Giải thuật & chương trình 15
  16. VD2: Nhập n phần tử a1 an, sau đó tính tổng n số: S=a1+ a2+a3+ +an ◼ Bước 1: Nhập n. ◼ Bước 2: Cho S=0 (lưu trữ số 0 trong S) ◼ Bước 3: Cho i=1 (lưu trữ số 1 trong i) ◼ Bước 4: Kiểm tra nếu i<=n thì thực hiện bước 5, ngược lại thực hiện bước 8. ◼ Bước 5: Nhập ai ◼ Bước 6: Cho S=S+ai (lưu trữ giá trị S + ai trong S) ◼ Bước 7: Tăng i lên 1 đơn vị và quay lại bước 4. ◼ Bước 8: In S và kết thúc chương trình. Giải thuật & chương trình 16
  17. VD3: Viết GT nhập vào 2 giá trị a, b tìm số lớn hơn - Bước 1: Nhập 2 số a và b - Bước 2: Nếu a >b thì viết a lớn hơn b, sang thực hiện bước 5, (còn không sang bước 3) - Bước 3: Nếu a=b thì viết a=b, sang thực hiện bước 5, (còn không sang bước 4). - Bước 4: viết b lớn hơn a -Bước 5:kết thúc. Giải thuật & chương trình 17
  18. VD4: Xây dựng TT nhập n giá trị a1, a2, ,an. in ra giá trị lớn nhất ◼ Bước 1: Nhập số n ◼ Bước 2: Nhập số thứ nhất a1 ◼ Bước 3: Gán max=a1 ◼ Bước 4: Gán i=2 ◼ Bước 5: Nếu i<=n thì thực hiện bước 6, ngược lại thực hiện bước 9 ◼ Bước 6: Nhập ai ◼ Bước 7: Nếu max < ai thì gán max=ai. ◼ Bước 8: Tăng i lên một đơn vị và quay lại bước 5 ◼ Bước 9: In max - kết thúc Giải thuật & chương trình 18
  19. VD5: Xây dựng TT nhập n giá trị a1, a2, , an. Sắp theo thứ tự tăng dần ◼ Bước 1: Gán i=1 ◼ Bước 2: Gán j=i+1 ◼ Bước 3: Nếu i aj thì hoán đổi ai và aj cho nhau (nếu không thì thôi). ◼ Bước 6: Tăng j lên một đơn vị và quay lại bước 4 ◼ Bước 7: Tăng i lên một đơn vị và quay lại bước 3 ◼ Bước 6: In dãy số a1, a2, , an - Kết thúc. Giải thuật & chương trình 19
  20. 5.2.2. Diễn đạt giải thuật bằng sơ đồ khối (block diagram) ◼ Sử dụng các hình khối để minh hoạ cho các lệnh hay thao tác. ◼ Sử dụng mũi tên để diễn đạt thứ tự thực hiện ◼ Đây là cách diễn đạt khoa học, có tính nhất quán cao Giải thuật & chương trình 20
  21. ◼ Sơ đồ khối (Lưu đồ) ❑ Các ký hiệu được sử dụng trong lưu đồ: ◼ Nhập – Input ◼ Xử lý – Process ◼ Quyết định – Decision ◼ Thủ tục – Procedure ◼ Đường kết nối - Flow line Giải thuật & chương trình 21
  22. ◼ Giải thuật và Lưu đồ (tt) ❑ Các ký hiệu được sử dụng trong lưu đồ (tt): ◼ Bắt đầu và Kết thúc – Start and Stop ◼ Kết nối trên cùng một trang – On page connector ◼ Kết nối ở trang khác – Off page connector ◼ Chú thích – Annotation ◼ Hiển thị - Display/Output Giải thuật & chương trình 22
  23. ◼ Lưu đồ sau đây nhập hai số, tính tích và hiển thị tích của hai số. Giải thuật & chương trình 23
  24. Lưu đồ sau đây hiển thị số lớn hơn trong hai số đã nhập. Giải thuật & chương trình 24
  25. ? Bắt đầu Đọc một số Chia số đó cho 2 Sai Đúng remainder=0? Là số lẻ Là số chẵn Dừng Giải thuật & chương trình 25
  26. Giải thuật & chương trình 26
  27. Các qui tắc vẽ lưu đồ American National Standards Institute (ANSI) đề nghị một số qui luật cần phải tuân theo khi vẽ lưu đồ như sau: ◼ Toàn bộ lưu đồ nên được biểu diễn bằng ký hiệu chuẩn. ◼ Lưu đồ nên rõ ràng, chính xác và dễ theo dõi. ◼ Lưu đồ chỉ nên có một điểm bắt đầu và một điểm kết thúc. ◼ Các bước trong lưu đồ nên đi từ trên xuống và đi từ trái sang phải. ◼ Tất cả dữ liệu nhập phải được liệt kê hết theo một thứ tự hợp lý. Giải thuật & chương trình 27
  28. Các qui tắc vẽ lưu đồ ◼ Ký hiệu bắt đầu và kết thúc chỉ nên có một đường kết nối duy nhất. ◼ Ký hiệu nhập dữ liệu, xử lý, xuất dữ liệu, hiển thị nên có hai đường kết nối để nối ký hiệu đứng trước và đứng sau chúng. ◼ Ký hiệu quyết định nên có một đường kết nối với ký hiệu trước nó và có hai đường kết nối đến hai ký hiệu đứng sau nó. ◼ Nếu có quá nhiều đường kết nối làm cho lưu đồ trở nên phức tạp thì nên dùng ký hiệu kết nối trang để giảm số đường kết nối. Giải thuật & chương trình 28
  29. ◼ Điểm mạnh của lưu đồ ❑ Lưu đồ là phương pháp tốt để truyền đạt lập luận của giải thuật. ❑ Lưu đồ giúp phân tích vấn đề một cách hiệu quả. ❑ Lưu đồ đóng vai trò như người hướng dẫn trong giai đoạn phát triển chương trình. ❑ Dễ tìm và sửa lỗi bằng lưu đồ. ❑ Lưu đồ trợ giúp đắc lực trong việc bảo trì chương trình. Giải thuật & chương trình 29
  30. ◼ Điểm yếu của lưu đồ ❑ Lưu đồ dài có thể trãi ra trên nhiều trang, làm giảm tính dễ đọc. ❑ Việc vẽ lưu đồ bằng các công cụ đồ hoạ là việc làm tốn nhiều thời gian. ❑ Thay đổi chỉ một bước nào đó có thể dẫn đến việc vẽ lại toàn bộ lưu đồ. ❑ Lưu đồ biểu diễn giải thuật phức tạp có thể chứa rất nhiều đường kết nối. Điều này làm giảm tính dễ đọc, tốn thời gian để vẽ và hiểu lập luận của giải thuật. Giải thuật & chương trình 30
  31. 5.3.3. Diễn đạt giải thuật bằng ngôn ngữ giả ◼ Dựa trên ngôn ngữ lập trình bậc cao ◼ Gần với ngôn ngữ tự nhiên của con người ◼ Ví dụ: Ngôn ngữ giả Pascal (tựa Pascal) có các ký pháp khá giống với ngôn ngữ lập trình Pascal, được rút gọn sao cho dễ diễn đạt ◼ Giả ngôn ngữ được đưa ra với mục đích diễn đạt các giải thuật sao cho gần với ngôn ngữ lập trình và ngôn ngữ tự nhiên. ◼ Sử dụng giả ngôn ngữ khiến việc chuyển từ giải thuật sang chương trình dễ dàng hơn. Giải thuật & chương trình 31
  32. Ví dụ: Giải thuật tính tổng N số tự nhiên đầu tiên ◼ Nhập N ◼ i:=0 ◼ S:=0 ◼ REPEAT ◼ S:=S+i ◼ i:=i+1 ◼ UNTIL (i>N) ◼ In S Giải thuật & chương trình 32
  33. 5.3. Đánh giá thuật toán ◼ Phân tích thuật toán: tìm một cách đánh giá về thời gian và “không gian” cần thiết để thực hiện thuật toán ◼ Đánh giá về thời gian của thuật toán không phải là xác định thời gian tuyệt đối mà là mối liên quan giữa dữ liệu đầu vào và chi phí để thực hiện thuật toán T=f(input) ◼ Thông thường chỉ quan tâm đến mối liên quan giữa độ lớn của dữ liệu đầu vào và chi phí T=f(n) trong trường hợp tốt nhất và xấu nhất Giải thuật & chương trình 33
  34. Độ phức tạp của thuật toán Giải thuật & chương trình 34
  35. Độ phức tạp của thuật toán ◼ Chi phí chung = chi phí so sánh + chi phí gán ◼ Trong mọi trường hợp, phép so sánh ai>amax luôn được thực hiện và số lần thực hiện là n-1: chi phí cố định (bất biến) của bài toán ◼ Trường hợp tốt nhất: số lớn nhất ở đầu dãy. Do đó phép gán amax= ai không cần thực thi, như vậy chi phí chung cho trường hợp này chính là chi phí cố định T=f(n)=n-1 ◼ Trường hợp xấu nhất: số lớn nhất ở cuối dãy. Do đó phép gán amax= ai luôn cần thực thi, số lần thực thi là n- 1, như vậy chi phí chung cho trường hợp này là T=f(n)=2(n-1)=2n-2 ◼ Độ phức tạp của thuật toán là O(n), tuyến tính Giải thuật & chương trình 35
  36. 5.4. Xây dựng chương trình 1. Xác định vấn đề - bài toán 2. Lựa chọn phương pháp giải 3. Xây dựng thuật toán hoặc thuật giải 4. Cài đặt chương trình 5. Hiệu chỉnh chương trình 6. Thực thi chương trình Giải thuật & chương trình 36
  37. Phương pháp lập trình ◼ Lập trình cấu trúc có các đặc trưng ❑ Tính đơn thể ❑ Cấu trúc điều khiển: phối hợp cấu trúc tuần tự, cấu trúc chọn và cấu trúc lặp ❑ Tính vào/ra đơn ◼ Lập trình hướng đối tượng: một tiếp cận mới trong lập trình sử dụng khái niệm đối tượng, kết hợp cả dữ liệu và các câu lệnh của chương trình Giải thuật & chương trình 37
  38. Ngôn ngữ lập trình ◼ Tập từ ngữ và cú pháp 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 ◼ Chương trình máy tính là tập các chỉ thị nhằm thực hiện nhiệm vụ cụ thể được viết bằng ngôn ngữ lập trình ◼ Các loại ngôn ngữ lập trình ❑ Ngôn ngữ máy ❑ Hợp ngữ ❑ Ngôn ngữ cấp cao Giải thuật & chương trình 38
  39. Ngôn ngữ lập trình 5GLs artificial intelligence 4GLs ORACLE, SEQUEL, INGRES, HIGH-LEVEL ForTran, COBOL, C, C++, LANGUAGES LISP, Pascal, Java, ASSEMBLER LANGUAGES MACHINE CODE Giải thuật & chương trình 39
  40. ◼ Ngôn ngữ lập trình ❑ Ngôn ngữ lập trình là phương tiện truyền thông giữa Lập trình viên và máy tính. ❑ Lập trình viên sử dụng ngôn ngữ lập trình để viết các lệnh yêu cầu máy tính thực hiện một công việc nào đó. Tập hợp các lệnh này được gọi là chương trình. ❑ Các loại ngôn ngữ lập trình: Giải thuật & chương trình 40
  41. Ngôn ngữ máy: • Từ vựng được tạo nên từ mã nhị phân 0-1 để tạo ra các câu lệnh, các chỉ dẫn nhằm yêu cầu máy tính thực hiện một công việc nào đó. • Các lệnh được máy tính thực hiện trực tiếp (không qua mã trung gian). • Ngoài ngôn ngữ máy, các NNLT khác đều cần được dịch ra mã trung gian trước khi thực thi. Ngôn ngữ Assembly: • Còn gọi là ngôn ngữ máy tính thế hệ thứ 2 là ngôn ngữ sử dụng bảng mã chữ cái và các ký hiệu để đưa ra các chỉ dẩn Ngôn ngữ cấp cao: • Đây là ngôn ngữ thân thiện với người sử dụng vì dùng những từ ngữ thông dụng tiếng Anh để đưa ra các chỉ dẩn cho máy tính víGi dụải thu ậnhưt & chươ ngPRINT, trình GOTO 41
  42. ◼ Ví dụ về các ngôn ngữ lập trình cấp cao ❑ Một số ngôn ngữ lập trình cao cấp là: • BASIC • Pascal • C • Java • C# ◼ Giải thuật & chương trình 42
  43. ◼ Lựa chọn ngôn ngữ lập trình Một số các yếu tố khi lựa chọn ngôn ngữ lập trình: • Tiêu chí 1: lựa chọn đầu tiên là tùy thuộc vào loại ứng dụng cần phát triển. Ví dụ: - Tạo ra chương trình thực hiện các phép toán đơn giản (+ - * /) ta có thể sử dụng Pascal. - Để phát triển ứng dụng dùng trong gia đình hoặc doanh nghiệp nhỏ có thể dùng Visual BASIC • Tiêu chí 2: Nếu có nhiều ngôn ngữ phù hợp để phát triển ứng dụng thì bạn nên chọn ngôn ngữ mà bạn thông thạo nhất. • Tiêu chí 3: Nếu bạn không thông thạo ngôn ngữ nào cả thì nên chọn ngôn ngữ lập trình dễ học và dễ sử dụng. Giải thuật & chương trình 43
  44. Cài đăt chương trình từ 1 thuật toán ◼ Ví dụ: Chuyển một số giải thuật cơ bản ❑ Lặp ❑ Đệ quy ❑ Sắp xếp ❑ Tìm kiếm ❑ Giải thuật & chương trình 44
  45. Tóm tắt và một số câu hỏi ◼ Tại sao cần có thuật toán ? ◼ Một số phương pháp biểu diễn thuật toán? ◼ Những yêu cầu đối với 1 thuật toán ? ◼ Biểu diễn thuật toán tìm số lớn nhất giữa 2 số a và b ? ◼ Biểu diễn thuật toán giải PT bậc 2? ◼ Tìm giá trị lớn nhất của 1 dãy số ? ◼ Đánh giá độ phức tạp và cài đặt 3 thuật toán trên bằng C hoặc Pascal ? Giải thuật & chương trình 45
  46. Thuật toán đệ quy ◼ Đư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 (đồng dạng) nhưng ở cấp độ thấp 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, lần ngược để giải được bài toán ở cấp độ cao đến lúc ban đầu ❑ Định nghĩa giai thừa: 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 → Định nghĩa theo kiểu quy nạp Giải thuật & chương trình 46
  47. Thuật toán đệ quy ◼ Mọi thuật toán đệ quy gồm hai phần: ❑ Phần cơ sở: các trường hợp không cần thực hiện lại thuật toán (không gọi đệ quy), chính là các điểm dừng ❑ Phần đệ quy: có yêu cầu gọi đệ quy, tức yêu cầu thực hiện lại thuật toán với cấp độ dữ liệu thấp hơn Giải thuật & chương trình 47
  48. Thuật toán đệ quy Giải thuật & chương trình 48
  49. Trình thông dịch và biên dịch ◼ Mọi chương trình đều phải được chuyển đổi qua ngôn ngữ máy trước khi thực thi ◼ Trình hợp dịch (assembler) ◼ Trình biên dịch (compiler): chuyển đổi toàn bộ chương trình cấp cao nguồn sang chương trình đối tượng để thực thi ◼ Trình thông dịch (interpreter): chuyển đổi từng mệnh đề và thực thi đoạn mã kết quả ngay, không tạo ra chương trình đối tượng Giải thuật & chương trình 49
  50. ◼ Trình biên dịch ❑ Là chương trình (phần mềm) được sử dụng để chuyển các câu lệnh được viết bằng ngôn ngữ cấp cao sang ngôn ngữ máy tính có thể hiểu được. ❑ Mỗi ngôn ngữ lập trình cấp cao có một trình biên dịch riêng tương ứng. Giải thuật & chương trình 50
  51. ◼ Trình biên dịch (tiếp theo) ❑ Hình vẽ sau thể hiện sự hoạt động của trình biên dịch: Giải thuật & chương trình 51
  52. ◼ Trình biên dịch (tiếp theo) ❑ Khi trình biên dịch dịch một chương trình, nó sẽ kiểm tra Từ vựng và Cú pháp các câu lệnh. ❑ Nếu trình biên dịch tìm thấy lỗi trong chương trình nguồn thì nó sẽ hiển thị danh sách các lỗi. ❑ Trình biên dịch sẽ không sinh ra mã trung gian nếu như tất cả các lỗi của chương trình nguồn chưa được sửa hết. Giải thuật & chương trình 52
  53. ◼ Bộ liên kết ❑ Mỗi NNLT sẽ có các thư viện chứa các từ khóa với các chức năng được định nghĩa trước. Người lập trình sẽ sử dụng những từ khóa này kết hợp với các cú pháp để viết chương trình. ❑ Khi dịch, trình biên dịch sẽ sinh ra mã trung gian. ❑ Để sinh mã thực thi từ mã trung gian thì chức năng của các từ khóa (lưu trong các thư viện) và các thư viện cũng cần được đưa vào mã trung gian. ❑ Bộ liên kết thực hiện việc gắn chức năng của các từ khóa với mã trung gian để tạo ra mã thực thi. Giải thuật & chương trình 53
  54. ◼ Bộ liên kết (tiếp theo) ◼ Quá trình liên kết này được thể hiện bằng hình vẽ sau đây: Giải thuật & chương trình 54
  55. ◼ Trình thông dịch Một số ngôn ngữ lập trình cấp cao sử dụng cơ chế dịch khác gọi là thông dịch. Chương trình dịch theo cơ chế này được gọi là trình thông dịch. ❑ Trình thông dịch sẽ đọc một lệnh được viết bằng ngôn ngữ lập trình cấp cao, chuyển sang mã máy, thực thi câu lệnh này và không lưu mã trung gian. ❑ Chương trình thực thi dùng trình thông dịch sẽ tiết kiệm được thời gian hơn trình biên dịch. ❑ Trình thông dịch cũng giúp cho việc dò tìm lỗi dễ dàng hơn vì nó chỉ ra chính xác những dòng nào phát sinh lỗi. ❑ Ngôn ngữ lập trình sử dụng trình thông dịch như PERL, BASIC, VisualGiảBasic,i thuật & chươngv trình.v 55