Bài giảng "Kiến trúc máy tính - Chương 3: Thuật toán" cung cấp cho người học các kiến thức: Khái niệm, tính chất của thuật toán, biểu diễn thuật toán, các cấu trúc thuật toán cơ bản. Cuối bài giảng có phần bài tập để người học ôn tập và củng cố kiến thức. | Bài giảng Kiến trúc máy tính (Phần 1): Chương 3 - Nguyễn Văn Huy 1 Khái niệm Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên những dữ liệu vào sao cho sau một số hữu hạn bước thực hiện các thao tác đó ta thu được kết quả của bài toán. Dữ liệu vào (Input) Thuật toán Kết quả đầu ra (Output) 22 Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật Ví dụ Thuật toán Euclid là thuật toán tìm ước số chung lớn nhất (USCLN) của hai số nguyên dương a và b. Input: a, b là số nguyên dương Output: USCLN của a và b Thuật toán tìm Euclid có thể được mô tả như sau: Bước 1: Nếu a < b thì hoán vị hai số a, b cho nhau Bước 2: Nếu b = 0 thì USCLN là a Bước 3: Ngược lại a > b, thì thực hiện : • Tìm số dư r của phép chia a cho b; • Gán a= b, b= r, rồi quay trở lại bước 2. 33 Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật Tính chất của thuật toán Tính đúng: Thuật toán phải cho ra kết quả chính xác; Tính tổng quát: thuật toán phải áp dụng để giải một lớp bài toán có dạng tương tự, chứ không phải chỉ áp dụng những bài toán cụ thể riêng lẻ ; Tính xác định: Các bước trong thuật toán phải rõ ràng, trật tự thực hiện phải xác định và là duy nhất ; Tính dừng: thuật toán phải cho ra kết quả sau một số hữu hạn các bước ; Tính hiệu quả: một thuật toán được gọi là hiệu quả nếu nó đơn giản, dễ hiểu, thời gian thực hiện nhanh và chiếm ít bộ nhớ ; . 44 Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật Biểu diễn thuật toán Người ta thường biểu diễn thuật toán theo các cách sau : Dùng ngôn ngữ tự nhiên (Liệt kê các bước) Vẽ lưu đồ (Flowchart) Mã giả 55 Khoa CNTT - Bài giảng THDC - Khối ngành kỹ thuật Biểu diễn thuật toán bằng ngôn ngữ tự nhiên Ta sử dụng ngôn ngữ con người để liệt kê từng bước thực hiện của thuật toán. Ví dụ: Thuật toán tính tổng hai số a và b: Bước 1 : Nhập vào các số a và b; Bước 2 : Tính tổng a+b; .
