Tin học đại cương - Chương 7: Bài toán và thuật toán

Tin học đại cương Introduction to Information Technology Nhóm biên soạn HP. Tin Học Đại Cương Khoa Công Nghệ Thông Tin Trường ĐHSP TP. Hồ Chí Minh Bộ môn Kĩ Thuật Dạy Học Chương 7: Bài toán và thuật toán 2Bản quyền: Khoa CNTT 2011 Giới thiệu  Trong xu hƣớng phát triển của xã hội, công nghệ thông tin ngày càng đóng một vai trò rất quan trong giúp mọi ngƣời có thể hoàn thành công việc của mình trở nên nhanh chóng, hiệu quả và dễ dàng hơn thông qua các chƣơng trình ứng dụng trên máy tính. Thuật toán và thuật giải là nền tảng để những lập trình viên có thể xây dựng những chƣơng trình ứng dụng phù hợp.  Đó cũng chính là mục tiêu của chƣơng này nhằm cung cấp các khái niệm ban đâu về bài toán và thuật toán . Đông thời đƣa ra qui trình cơ bản để giải quyết 1 bài toán trên máy tính nhƣ thế nào? 3Bản quyền: Khoa CNTT 2011 Nội dung chính Chƣơng 7: Bài toán và thuật toán  Khái niệm vấn đề và bài toán.  Thuật toán và các phương pháp biểu diễn thuật 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. 4Bản quyền: Khoa CNTT 2011 Khái niệm vấn đề  Vấn đề thƣờng đƣợc dùng với nghĩa rộng hơn bài toán, bài toán là vấn đề mà để giải quyết nó phải liên quan ít nhiều đến tính toán  Pitago chia mọi vấn đề mà con ngƣời cần giải quyết thành hai loại: Theorema: vấn đề cần khẳng định tính đúng – sai Problema: vấn đề cần tìm giải pháp để để đạt đƣợc mục tiêu từ những điều kiện ban đầu nào đó 5Bản quyền: Khoa CNTT 2011 Khái niệm vấn đề (tt)  Theo nhiều kết quả nghiên cứu: việc giải quyết vấn đề - bài toán mà Pitago nêu ra đều có thể diễn ra theo một sơ đồ chung: A B  Trong đó: A có thể là giả thiết, điều kiện ban đầu B có thể là kết luận, mục tiêu cần đạt  là suy luận, giải pháp cần xác định 6Bản quyền: Khoa CNTT 2011 Ví dụ về vấn đề - bài toán 1. Bài toán kiểm tra tính nguyên tố  Điều kiện ban đầu: Số nguyên dƣơng N  Mục tiêu cần đạt: N có là số nguyên tố hay không? 2. Bài toán quản lý hồ sơ sinh viên  Điều kiện ban đầu: Hồ sơ gốc của các sinh viên trong trƣờng  Mục tiêu cần đạt: Bảng thống kê, phân loại sinh viên theo kết quả học tập 7Bản quyền: Khoa CNTT 2011 Bài toán trong tin học?  Trong thực tế, không phải vấn đề nào cũng có thể là những bài toán có tính toán (bài toán của toán học).  Ví dụ:  Làm sao giao dịch ngân hàng tự động không cần nhân viên  Làm sao để con ngƣời nói chuyện đƣợc với nhau mà không cần phải gặp mặt nhau.  Làm sao để xếp loại học sinh của trƣờng học có 3000 học sinh một cách nhanh chóng  Tất cả là bài toán trong tin học Là vấn đề mà ta muốn máy tính thực hiện để từ dữ liệu vào (Input) ta nhân được dữ liệu – thông tin ra cần thiết (output) 8Bản quyền: Khoa CNTT 2011 Ví dụ bài toán trong tin học 1. Bài toán tìm ƣớc chung lớn nhất của hai số nguyên dƣơng M,N  Input: Hai số nguyên M,N  Output: ƢCLN 2. Bài toán xếp thời khóa biểu cho trƣờng học  Input: Tên giáo viên, môn dạy  Output: TKB của trƣờng 3. Bài toán tìm điểm thi đại học của thí sinh  Input: Số báo danh  Output: Điểm thi 9Bản quyền: Khoa CNTT 2011 Giải bài toán trên máy tính nhƣ thế nào? OutputInput Bài toán Bằng cách nào ? Giải bài toán Hướng dẫn các thao tác cho máy thực hiện Thuật toán 10Bản quyền: Khoa CNTT 2011 Thuật toán là gì? Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Muhammad 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. Muḥammad ibn Mūsā al- Khwārizmī (Arabic: نب دمحم يمزراوخلا ىسوم ) was a Persian mathematician, astronomer, astrologer and geographer. He was born around 780, in either Khwarizm or Baghdad, and died around 850. (Trích từ Wikipedia) 11Bản quyền: Khoa CNTT 2011 Khái niệm thuật toán  Thuật toán là khái niệm cơ sở của toán học và tin học  Thuật toán là một dãy các chỉ thị rõ ràng và có thể thi hành được để hƣớng dẫn thực hiện hành động nhằm đạt đƣợc mục tiêu đặt ra  Thuật toán là sự thể hiện của một phương pháp để giải quyết vấn đề 12Bản quyền: Khoa CNTT 2011 Lƣu ý  Cùng một bài toán có thể có nhiều thuật toán khác nhau để giải  Thuật toán đơn giản, dễ hiểu, có độ chính xác cao, đƣợc bảo đảm về mặt toán học, dễ triển khai trên máy, thời gian thao tác ngắn, đƣợc gọi là thuật toán tối ưu  Nghiên cứu thuật toán là một trong những vấn đề quan trọng của tin học  Lý thuyết về thuật toán giải quyết một số vấn đề sau: Những bài toán nào giải đƣợc bằng thuật toán, những bài toán nào không giải đƣợc bằng thuật toán Tìm thuật toán tốt nhất, tối ƣu Triển khai thuật toán trên máy tính 13Bản quyền: Khoa CNTT 2011 Đặc trƣng của thuật toán  Nhập (input). Các thuật toán thƣờng có giá trị đầu vào  Xuất (output). Từ giá trị vào thuật toán cho ra kết quả.  Tính xác định(definiteness). Các bƣớc trong thuật toán phải chính xác rõ ràng.  Tính hữu hạn(finiteness). Thuật toán phải cho ra lời giải (hay kết quả) sau một số bƣớc hữu hạn.  Tính hiệu quả(Effectiveness). Tính hiệu quả đƣợ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 sử dụng (khi thực hiện thuật toán trên máy tính).  Tính tổng quát(Generalliness) Thuật toán phải áp dụng đƣợc cho tất cả các bài toán cùng dạng, chứ không chỉ áp dụng đƣợc cho một số trƣờng hợp riêng lẻ nào đó. 14Bản quyền: Khoa CNTT 2011 Ví dụ về thuật toán giải phƣơng trình bậc nhất  Bƣớc 1 : Nhập a, b.  Bƣớc 2 : Nếu a = 0 thì B2.1: Nếu b=0 thì thông báo pt vô số nghiệm rồi qua bƣớc 5 B2.2: Nếu b khác 0 thì thông báo pt vô nghiệm rồi qua bƣớc 5  Bƣớc 3 : Gán cho x giá trị -b/a, rồi qua bƣớc 4.  Bƣớc 4: Xuất ra giá trị x rồi qua bƣớc 5  Bƣớc 5 : Kết thúc. 15Bản quyền: Khoa CNTT 2011 Cấu trúc cơ bản của thuật toán  Tuần tự: thực hiện hết lệnh này đến lệnh khác  Rẽ nhánh: tùy theo dữ liệu đầu vào mà ta quyết định thực hiện câu lệnh gì tiếp theo  Lặp: thực hiện lại nhiều lần một số câu lệnh nào đó cho đến khi điều kiện không còn thỏa mãn nữa 16Bản quyền: Khoa CNTT 2011 Các phƣơng pháp biễu diễn thuật toán  Ngôn ngữ tự nhiên  Lƣu đồ - sơ đồ khối  Mã giả 17Bản quyền: Khoa CNTT 2011 Biểu diễn thuật toán bằng phƣơng pháp ngôn ngữ tự nhiên  Liệt kê các thao tác, các chỉ thị 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 18Bản quyền: Khoa CNTT 2011 Biễu diễn thuật toán bằng phƣơng pháp lƣu đồ (lowchart)  Là một phƣơng tiện hình học giúp ta diễn tả giải thuật một cách trực quan  Đƣợc tạo bởi các kiểu khối cơ bản, nối với nhau bằng các đƣờng có hƣớng  Thuật ngữ tiếng Anh là Flow Chart 19Bản quyền: Khoa CNTT 2011 Các ký hiệu cơ bản trong phƣơng pháp lƣu đồ 20 bắt đầu kết thúc chƣơng trình con hƣớng xử lý điều kiện nhập hoặc xuất thao tác Bản quyền: Khoa CNTT 2011 Ví dụ dùng phƣơng pháp lƣu đồ để so sánh 2 số a và b 21 Bắt đầu Kết thúc Số a, Số b Số a bằng Số b Số a có bằng Số b không? Số a không bằng Số b Có Không Bản quyền: Khoa CNTT 2011 Biểu diễn thuật toán bằng phƣơng pháp mã giả (pseudo code)  Ngoài việc sử dụng ngôn ngữ tự nhiên và lƣu đồ để biểu diễn thuật toán, ngƣời ta còn sử dụng ngôn ngữ tựa pascal, c, đƣợc gọi là mã giả  Trong mã giả ta sử dụng cả cấu trúc của ngôn ngữ lập trình và ngôn ngữ tự nhiên 22Bản quyền: Khoa CNTT 2011 Ví dụ về dùng phƣơng pháp mã giả để giải phƣơng trình bậc 2 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 23Bản quyền: Khoa CNTT 2011 Các bƣớc giải 1 bài toán trên máy tính  Bƣớc 1: Xác định vấn đề - bài toán  Bƣớc 2: Lựa chọn phƣơng pháp giải  Bƣớc 3: Xây dựng thuật toán hoặc thuật giải  Bƣớc 4: Cài đặt chƣơng trình  Bƣớc 5: Hiệu chỉnh chƣơng trình  Bƣớc 6: Thực hiện chƣơng trình 24 Lưu ý: Các bước 4, 5, 6 sẽ được học chi tiết trong môn lập trình căn bản Bản quyền: Khoa CNTT 2011 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) 25Bản quyền: Khoa CNTT 2011 ví dụ 1: Kiểm tra một số nguyên a là số chẵn hay 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. 26Bản quyền: Khoa CNTT 2011 Ví dụ 1: (tt)  Xây dụng thuật toán  Cách 1: Dùng ngôn ngữ tự nhiên 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 27  Cách 2: Dùng sơ đồ khối Nhập a a 2 a chẵn a chẵn Bắt đầu Kết thúc  Mô phỏng thuật toán  Nhập a: 18  18 chia hết cho 2  Xuất ra 18 là số chẵn Bản quyền: Khoa CNTT 2011 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). 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 28Bản quyền: Khoa CNTT 2011 Mô phỏng ý tƣởng Bản quyền: Khoa CNTT 2011 Quả này lớn nhất Quả này mới lớn nhất Tìm ra quả lớn nhất rồi! MAX Ồ! Quả này lớn hơn Mô phỏng ý tưởng 29 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 lưu đồ B1 B2 B3 B4 B5 30 Kết thúc i > N ai > Max Max  a1; i  2 Max  ai Đ S S Đ i  i + 1 Max N, a1, a2,,an Bắt đầu Ma Bản quyền: Khoa CNTT 2011 Mô phỏng thuật toán Nhập n=7 Nhập dãy A có 7 phần tử 7654321i 69122781A[i] Max= 1 Max= 8 Max=8 Max=8 Max=12 Max=12 Max=1 2 Max <8 Max <12 31Bản quyền: Khoa CNTT 2011 Ví dụ 3: Bài toán kiểm tra tính nguyên tố  Xác định bài toán  Input: Số nguyên dƣơng N  Output: N là số nguyên tố hoặc N không là số nguyên tố Số nguyên tố : Định nghĩa : “Một số nguyên dương N là số nguyên tố nếu nó chỉ có đúng hai ước là 1 và N” Các tính chất : - Nếu N = 1  N không là số nguyên tố - Nếu 1 < N < 4  N là số nguyên tố 32Bản quyền: Khoa CNTT 2011 Bài toán kiểm tra tính nguyên tố (tt)  Ý tƣởng  N<4 : Xem như bài toán đã được giải quyết  N>=4 : Tìm ước i đầu tiên > 1 của N - Nếu i < N  N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N) - Nếu i = N  N là số nguyên tố N 1 : N không là số nguyên tố  Kết thúc 1<N<4 : N là số nguyên tố  Kết thúc N>=4 : N không là số nguyên tố : Tìm thấy iÎ[2..(N-1)]  Kết thúc N là số nguyên tố : Không tìm thấy iÎ[2..(N-1)], i=N  Kết thúc 33Bản quyền: Khoa CNTT 2011 Kiểm tra tính nguyên tố (tt)  Xây dựng thuật toán a) Cách liệt kê : Bước 1 : Nhập số nguyên dƣơng N; Bước 2 : Nếu N=1 thì thông báo “N không là số nguyên tố”, kết thúc; Bước 3 : Nếu N<4 thì thông báo “N là số nguyên tố”, kết thúc; Bước 4 : i  2 ; Bước 5 : Nếu i là ƣớc của N thì đến bƣớc 7 Bước 6 : i  i +1 rồi quay lại bƣớc 5; (Tăng i lên 1 đơn vị) Bước 7 : Nếu i = N thì thông báo “N là số 34Bản quyền: Khoa CNTT 2011 Kiểm tra nguyên tố (tt) b) Sơ đồ khối : Bước 1 : Nhập số nguyên dương N; Bước 2 : Nếu N=1 thì thông báo “N không là số nguyên tố”, kết thúc; Bước 3 : Nếu N<4 thì thông báo “N là số nguyên tố”, kết thúc; Bước 4 : i  2 ; Bước 5 : Nếu i là ước của N thì đến bước 7 Bước 6 : i  i +1 rồi quay lại bước 5; (Tăng i lên 1 đơn vị) Bước 7 : Nếu i = N thì thông báo “N là số nguyên tố”, ngược lại thì thông báo “N không là số nguyên tố”, kết thúc 35Bản quyền: Khoa CNTT 2011 Bắt đầu N=1 Kết thúc N<4 i  2 i là ƣớc của N i  i+1 i = N Thông báo N không là SNT Thông báo N là SNT Nhập N Đ S Đ S Đ S Đ S Nhập N N là SNTN là không SNT Kiểm tra tính nguyên tố (tt)  Cải tiến thuật toán  Nếu N=2500 thì bƣớc 5,6 lặp lại 2499 lầnCần phải tìm cách giảm số lần xuống Dựa vào một tính chất của số nguyên tố: Nếu N >= 4 và không có ước trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N  N là số nguyên tố Ý tưởng : Tìm i tăng dần trong phạm vi từ 2 đến phần nguyên √N thỏa điều kiện là ước của N : - Nếu không tìm được  N là số nguyên tố - Ngược lại  N không là số nguyên tố Các bạn hãy viết lại thuật toán theo ý tưởng mới 36Bản quyền: Khoa CNTT 2011 Ví dụ 3: Bái toán tìm kiếm  Input : Dãy A gồm N số nguyên khác nhau a1, a2,,an và một số nguyên k (khóa) VD : Dãy A gồm các số nguyên 5 7 1 4 2 9 8 11 25 51 Và k = 2 (k = 6)  Output : Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy Vị trí của 2 trong dãy là 5 (không tìm thấy 6) 37Bản quyền: Khoa CNTT 2011 Hình thành ý tƣởng  Tìm kiếm tuần tự đƣợc thực hiện một cách tự nhiên :  Lần lƣợt đi từ số hạng thứ nhất,  So sánh giá trị số hạng đang xét với khóa  Cho đến khi gặp một số hạng bằng khóa hoặc dãy đã đƣợc xét hết mà không tìm thấy giá trị của khóa trên dãy. 38Bản quyền: Khoa CNTT 2011 Xây dựng thuật toán 39 Bước 1: Nhập N, các số hạng a1, a2,, aN và giá trị khoá k; Bước 2: i  1; Bước 3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc; Bước 4: i  i + 1; Bước 5: Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc; Bước 6: Quay lại bước 3; Nhập N, a1, a2,,an và k Đƣa ra i ; Kết thúc ai = k ? i > N ? i  1 i  i + 1 B.1 B.2 B.3 B.4 B.5 B.6 Đ S S Đ Thông báo dãy A không có số hạng có giá trị bằng k; Kết thúc Đƣa ra i rồi kết thúc Thông báo trong dãy số A không có số hạng nào bằng k N p N, a1, a2, , an và k Bản quyền: Khoa CNTT 2011 Mô phỏng thuật toán 40 5i 5125118924175A - Với k = 2 Tại vị trí i = 5 có a5 = 2 = k 54321 109876 4321 i 5125118924175A - Với k = 6 Không tìm thấy k = 6 trên dãy 11 Bản quyền: Khoa CNTT 2011 Bài tập 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, b số nào lớn hơn c. Giải phƣơng trình bậc 2: ax2 + bx + c = 0 41Bản quyền: Khoa CNTT 2011 Bài tập 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. Chạy tay thuật toán kiểm tra xem 1 số n có phải là số nguyên tố ( với n = 19, 24, 27, 29)? c. Kiểm tra xem 1 số n có phải là số hoàn thiện 42Bản quyền: Khoa CNTT 2011 Bài tập 3 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: a. 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. b. Tìm ƣớc số chung lớn nhất của a và b. c. 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). 43Bản quyền: Khoa CNTT 2011 Thuật giải  Khái niệm thuật toán đã trình bày chính là cánh cửa khép kín cho việc giải các bài toán vì: Nhiều bài toán không thỏa các đặc trƣng cơ bản của thuật toán. Có nhiều bài toán chƣa tìm ra thuật toán hoặc chƣa chứng minh đƣợc là có thuật toán hay không. Có những bài toán có thuật toán nhƣng khó thực hiện hoặc không thực hiện đƣợc 44Bản quyền: Khoa CNTT 2011 Thuật giải (tt)  Từ những nhận định trên ngƣời ta thấy rằng: cần phải có những đổi mới cho khái niệm thuật toán  “Thuật giải”  Thuật giải cũng là thuật toán nhƣng đƣợc mở rộng của tính chất: Tính xác định Tính đúng đắn 45Bản quyền: Khoa CNTT 2011 Ví dụ về thuật giải  Bài toán nấu cơm • Gạo, củi} • Nấu cơm : –Vo gạo –Chuẩn bị lửa –Nấu, canh giờ –Kết thúc • Nồi cơm chín} TÍNH ĐÚNG Không là thuật toán mà là thuật giải 46Bản quyền: Khoa CNTT 2011 Ví dụ về thuật giải  Bài toán đổ nước Có hai bình đựng nước là B5 có dung tích 5lít , B8 có dung tích 8lít. Hãy chỉ ra cách đong để có được hai lít nước. Các thao tác có thể thực hiện được là :  Hứng đầy nƣớc vào bình B5 hoặc B8.  Đổ hết nƣớc trong một bình.  Đổ nƣớc tƣ̀ bình này sang bình khác cho đến lúc bình kia đầy.  Thuật giải :  Đổ đầy nước vào bình B5 (B5=5) .  Đổ hết nước từ bình B5 sang bình B8 (B5=0, B8=5).  Đổ đầy nước bình B5 (B5=5, B8=5).  Đổ nước từ bình B5 cho đến khi B8 đầy (B5=2, B8=8). TÍNH XÁC ĐỊNH VÀ TÍNH ĐÚNG 47Bản quyền: Khoa CNTT 2011 48 VẤN ĐỀ NAN GIẢI? PP giải (giải thuật) VẤN ĐỀ TƢƠNG TỰ KẾT QUẢ Ôi nhiều việc quá Con người làm việc Khái niệm về ngôn ngữ lập trình Bản quyền: Khoa CNTT 2011 49 VẤN ĐỀ NAN GIẢI? PP giải(giải thuật) VẤN ĐỀ TƢƠNG TỰ KẾT QUẢ Có máy tính Sƣớng thật, đi làm việc khác thôi! Sự hỗ trợ của máy tính Khái niệm về ngôn ngữ lập trình Bản quyền: Khoa CNTT 2011 50 Giải bài toán này thế nào đây? Cách giải được diễn đạt bằng ngôn ngữ tự nhiên Source code Kiến thức về NNLT Kiến thức Chuyên môn Chƣơng trình biên dịch (Bộ máy của NNLT) File Ngôn ngữ máy (exe, dll, com, ...) Sự hỗ trợ của máy tính Khái niệm về ngôn ngữ lập trình Bản quyền: Khoa CNTT 2011 Phân loại ngôn ngữ lập trình  Ngôn ngữ máy  Hợp ngữ  Ngôn ngữ bậc cao 51Bản quyền: Khoa CNTT 2011 Ngôn ngữ máy  Là ngôn ngữ duy nhất mà máy tính có thể trực tiếp hiểu và thực hiện.Mỗi loại máy có ngôn ngữ máy của riêng nó được tập hợp dưới dạng các câu lệnh.  Ưu điểm: cho phép khai thác triệt để và tối ưu khả năng của máy tính  Nhược điểm: khó viết, chương trình nhận được cồng kềnh và khó hiệu chỉnh 52Bản quyền: Khoa CNTT 2011 Hợp ngữ (Assembly)  Có cấu trúc rất giống ngôn ngữ máy. Mã lệnh được thay bằng tên viết tắt tương ứng. Hợp ngữ chỉ chạy được sau khi đã được dịch ra ngôn ngữ máy thông qua chương trình hợp dịch (Assembler)  Ưu điểm: khắc phục được nhược điểm của ngôn ngữ máy  Nhược điểm: không phù hợp với số đông người lập trình 53Bản quyền: Khoa CNTT 2011 Ngôn ngữ bậc cao  Mô phỏng ngôn ngữ tự nhiên, sử dụng các ký hiệu toán học thống nhất chung  Không phụ thuộc vào loại máy tính cụ thể  Chỉ chạy được sau khi đã được dịch ra ngôn ngữ máy thông qua chương trình thông dịch (Interpreter) hoặc biên dịch (Compiler)  Ưu điểm: dễ viết, chương trình dễ hiểu, dễ hiệu chỉnh và dễ nâng cấp hơn 54Bản quyền: Khoa CNTT 2011 Chƣơng trình dịch  Là chương trình đặc biệt dùng để chuyển chương trình trên ngôn ngữ ban đầu (chương trình nguồn) sang chương trình tương đương trên ngôn ngữ máy.  Chương trình dịch chia làm 2 loại:  Kỹ thuật thông dịch (Interpreter)  Kỹ thuật biên dịch (Compiler) 55Bản quyền: Khoa CNTT 2011 Kỹ thuật thông dịch  Là kiểu dịch từng dòng lệnh để hiểu công việc cần làm và thực hiện ngay chứ không nhất thiết phải tạo ra các đoạn mã tương đương trong ngôn ngữ máy  Nếu một câu lệnh phải thực hiện nhiều lần thì cũng phải dịch nhiều lần  Ứng dụng: môi trường đối thoại giữa người và hệ thống 56Bản quyền: Khoa CNTT 2011 Kỹ thuật biên dịch  Là kiểu dịch toàn bộ chương trình ban đầu thành một chương trình tương ứng trong ngôn ngữ máy (chương trình đích), sau đó nạp chương trình đích vào máy tính để thực hiện  Ứng dụng: phù hợp với các chương trình ổn định và phải thực hiện nhiều lần 57Bản quyền: Khoa CNTT 2011 Một số ngôn ngữ lập trình thông dụng  Basic đƣợc thiết kế bởi John G. Kemeny và Thomas E. Kurtz tại ĐH Dartmouth vào 1963  Pascal đƣợc Niklaus Wirth phát thiết kế năm 1970  C do Dennis Richie thiết kế năm 1972 tại phòng thí nghiệp Bell Telephone của hãng AT&T sử dụng trong hệ điều hành Unix  Java đƣợc phát triễn bởi James Gosling thuộc Sun Microsystem vào 6/1991 58Bản quyền: Khoa CNTT 2011 59 THE END Bản quyền: Khoa CNTT 2011