Bài giảng Cơ sở lập trình: Thuật toán (Algorithm) - Trịnh Tấn Đạt

Bài giảng Cơ sở lập trình: Thuật toán (Algorithm), chương này trình bày những nội dung gồm: vấn đề, bài toán; khái niệm thuật toán, các đặc trưng của thuật toán, phương pháp biểu diễn thuật toán: mã giả, lưu đồ khối; giải bài toán trên máy tính;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở lập trình: Thuật toán (Algorithm) - Trịnh Tấn Đạt Thuật Toán (Algorithm) Trịnh Tấn Đạt Khoa CNTT - Đại Học Sài Gòn Email: trinhtandat@sgu.edu.vn Website: https://sites.google.com/site/ttdat88/ Nội dung  Vấn đề, bài toán  Thuật toán o Khái niệm o Các đặc trưng của thuật toán o Phương pháp biểu diễn thuật toán : mã giả, lưu đồ khối.  Giải bài toán trên máy tính Vấn đề, bài toán  Vấn đề (issue/problem): o Những vướng mắc, khó khăn trong cuộc sống mà ta cần giải quyết  Bài toán (problem): o Một loại vấn đề mà để giải quyết, cần đến tính toán (phép toán số, luận lí, quan hệ). o Khi giải bài toán, cần quan tâm 02 yếu tố: đầu vào (input) và đầu ra (output) Giải quyết vấn đề, bài toán  Bất kỳ vấn đề, bài toán ngoài đời nào cũng có thể được chia thành trình tự nhiều công việc nhỏ hơn.  Trình tự các công việc nhỏ này được gọi là giải thuật giải quyết công việc ngoài đời.  Mỗi công việc nhỏ hơn cũng có thể được chia nhỏ hơn nữa nếu nó còn phức tạp,... Ví dụ: ???  Vấn đề mấu chốt của việc dùng máy tính giải quyết công việc ngoài đời là lập trình. Thuật toán Thuật toán (Algorithm):  Là cách biểu diễn lời giải 'bài toán“ rõ ràng (không mập mờ), chi tiết để có thể thực thi được trên máy tính.  Là một dãy hữu hạn các bước nhằm xác định các thao tác mà máy tính có thể thực hiện được sao cho sau khoảng thời gian hữu hạn (có tính dừng) thì cho ra kết quả. Ví dụ: Bài toán giải phương trình bậc 1 (1 ẩn ; ax + b = 0). Ví dụ:  Thuật toán giải PT bậc nhất: ax + b = 0 (a, b là các số thực). Đầu vào: a, b thuộc R Đầu ra: nghiệm phương trình ax + b = 0 • Nếu a = 0 • b = 0 thì phương trình có nghiệm bất kì. • b ≠ 0 thì phương trình vô nghiệm. • Nếu a ≠ 0 • Phương trình có nghiệm duy nhất x = -b/a Các đặc trưng của thuật toán  Tính hữu hạn: có hữu hạn bước và phải dừng.  Tính xác định: các bước rõ ràng, thực thi được.  Tính đúng: quá trình thực thi theo các bước đã chỉ ra phải đi đến kết quả như ý.  Tính hiệu quả: khối lượng, không gian, thời gian tính toán không quá “lớn”.  Tính tổng quát: áp dụng được cho mọi trường hợp của bài toán. Ví dụ – Một lớp học cần chọn lớp trưởng theo các bước: 1. Lập danh sách sinh viên 2. Sắp thứ tự 3. Chọn người đứng đầu làm lớp trưởng – Danh sách cần gì? – Sắp theo thứ tự nào? (tăng giảm, tiêu chí nào) – Nếu trùng tiêu chí thì giải quyết ra sao? Ví dụ Sửa lại: a) Lập danh sách theo: họ tên, ngày tháng năm sinh, điểm các môn, điểm trung bình cuối năm. b) Sắp xếp theo ĐTB giảm. Nếu ĐTB bằng nhau  cùng hạng. c) Nếu có 01 HS đứng đầu  chọn, ngược lại chọn người có điểm toán cao nhất, nếu không chọn được  bốc thăm.  Phân biệt mập mờ và lựa chọn có quyết định: – Mập mờ là thiếu thông tin hoặc có nhiều lựa chọn nhưng không đủ điều kiện quyết định, ví dụ: bước 1, 2. – Lựa chọn có quyết định là hoàn toàn xác định duy nhất trong điều kiện cụ thể của vấn đề, ví dụ bước c. Ví dụ  Tính thực thi được, ví dụ: – Tính  10 ? – Chạy xe thẳng từ ĐHSG đến sân bay TSN?  Tính dừng, ví dụ: – B1 nhập n; – B2 s=0; – B3 i=1; – B4 nếu i=n+1 sang B8, ngược lại sang B5 – B5 cộng i vào s – B6 cộng 2 vào i – B7 quay lại B4 – B8 Tổng cần tính là s Phương pháp biểu diễn thuật toán  Thuật toán thường được biểu diễn bằng các ngôn ngữ sau: o Dùng ngôn ngữ tự nhiên (NNTN - natural language) o Dùng mã giả (pseudocode): ngôn ngữ tự nhiên (NNTN) + ngôn ngữ lập trình (NNLT) o Dùng lưu đồ - sơ đồ khối (flowchart) Biểu diễn bằng ngôn ngữ tự nhiên  Dùng ngôn ngữ thường ngày để liệt kê các bước của thuật toán.  Không thể hiện rõ cấu trúc của thuật toán.  Dài dòng, có thể gây hiểu lầm hoặc khó hiểu  KHÔNG yêu cầu người viết hay đọc nắm quy tắc. o Không có một quy tắc cố định  Tính dễ đọc: o Viết các bước con lùi vào bên phải o Đánh số bước theo quy tắc phân cấp như 1, 1.1, ... Biểu diễn bằng mã giả  Vay mượn các cú pháp của một ngôn ngữ lập trình o dùng một phần ngôn ngữ tự nhiên o bị phụ thuộc vào ngôn ngữ lập trình.  Mọi ngôn ngữ lập trình đều có những thao tác cơ bản o xử lý, rẽ nhánh và lặp o tận dụng được các khái niệm trong ngôn ngữ lập trình  Dễ dàng nắm bắt nội dung thuật toán Biểu diễn bằng mã giả - Ví dụ Một đoạn mã giả của thuật toán giải pt bậc hai if Delta > 0 then 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 Biểu diễn bằng lưu đồ  Các nhà lập trình đưa ra dạng lưu đồ để minh họa từng bước quá trình xử lý một vấn đề (bài toán). Biểu diễn bằng lưu đồ  Công cụ trực quan diễn đạt thuật toán. o Biểu diễn bằng mô hình – hình vẽ  Theo dõi được: o Sự phân cấp các trường hợp o Quá trình xử lý của thuật toán  Phân biệt hai loại thao tác: o Chọn lựa theo một điều kiện nào đó o Xử lý, hành động Biểu diễn bằng lưu đồ  Chọn lựa theo một điều kiện nào đó: o Biểu diễn bằng một hình thoi, bên trong chứa biểu thức điều kiện.  Ví dụ: thao tác 'nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4' là thao tác chọn lựa Biểu diễn bằng lưu đồ  Thao tác chọn lựa: có thể có hai hướng đi o một hướng ứng với điều kiện thỏa o một hướng ứng với điều kiện không thỏa. o 2 nhánh có nhãn • Đ/Đúng,Y/Yes • S/Sai,N /N o Biểu diễn bằng lưu đồ  Xử lý, hành động: o Biểu diễn bằng một hình chữ nhật, bên trong chứa nội dung xử lý.  Ví dụ: 'Chọn một môn học và in ra.' là một thao tác thuộc loại hành động. Biểu diễn bằng lưu đồ  Quá trình thực hiện các thao tác: o Đường đi – route o Biểu diễn bằng cung có hướng • nối giữa 2 thao tác: thực hiện lần lượt ...