Trắc nghiệm: Mô tả thuật toán là: A. Liệt kê các bước thực hiện công việc. B. Liệt kê các cách thực hiện công việc. C. Liệt kê một bước thực hiện công việc D. Tất cả đều đúng Lời giải: Đáp án đúng: A. Liệt kê các bước thực hiện công việc. Mô tả thuật toán là việc liệt kê các bước thực hiện công việc. Các bước của thuật toán thực hiện tuần tự từ trên xuống dưới. Cùng Top Tài Liệu tìm hiểu thêm về thuật toán để hiểu rõ hơn về câu hỏi trên nhé. Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề – bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề – 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.  Phân loại theo tính năng – Thuật toán tìm kiếm: Đây là thuật toán được áp dụng để tìm kiếm dữ liệu, thông tin trong một tập hợp bao gồm các phần tử khác nhau. – Thuật toán sắp xếp: Đây là thuật toán được dùng để sắp xếp thứ tự từng phần tử trong tập hợp một cách khoa học, đáp ứng yêu cầu ban đầu. – Thuật toán đồ thị: Thuật này được sử dụng để xử lý các dạng bài có sử dụng đồ thị. Phân loại theo cách thức thực hiện – Thuật toán chia để trị: Thuật toán này sẽ chia bài toán lớn thành những phần nhỏ để giải quyết dần. Từ những bài toán nhỏ, bạn có thể hiểu được thuật toán là gì và tìm được kết quả cho bài toán lớn. – Thuật toán tham lam: Thuật toán này là cách thay đổi trạng thái của bài toán thông qua các hành động cụ thể. Nó sẽ giúp bạn tiếp cần từ từ đến vấn đề của bài toán và tìm được hướng giải quyết nhanh chóng, hiệu quả. a. Tính xác định Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn. Số bước hữu hạn của thuật toán và tính chất dừng của nó được gọi chung là tính hữu hạn. Số bước hữu hạn của thuật toán là một tính chất khá hiển nhiên. Ta có thể tìm ở đâu một lời giải vấn đề – bài toán có vô số bước giải ? Tính “không mập mờ” và “có thể thực thi được” gọi chung là tính xác định. Tính “thực thi được” cũng là một tính chất khá hiển nhiên. Rõ ràng nếu trong “thuật toán” tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là “thực thi được” xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói “lấy căn bậc hai của một số âm” là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác “lấy căn bậc hai của một số âm” là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được. b. Tính hữu hạn Tính “dừng” hay hữu hạn là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng “thuật toán” bị lặp vô tận hoặc bị quẩn. Ðể tính tổng các số nguyên dương lẻ trong khoảng từ 1 đến n ta có thuật toán sau : B1. Hỏi giá trị của n. B2. S = 0 B3. i = 1 B4. Nếu i = n+1 thì sang bước B8, ngược lại sang bước B5 B5. Cộng thêm i vào S B6. Cộng thêm 2 vào i B7. Quay lại bước B4. B8. Tổng cần tìm chính là S. Ta chú ý đến bước B4. Ở đây ta muốn kết thúc thuật toán khi giá trị của i vượt quá n. Thay vì viết là “nếu i lớn hơn n” thì ta thay bằng điều kiện “nếu i bằng n+1” vì theo toán học “i = n+1” thì suy ra “i lớn hơn n”. Nhưng điều kiện “i=n+1” không phải lúc nào cũng đạt được. Vì ban đầu i = 1 là số lẻ, sau mỗi bước, i được tăng thêm 2 nên i luôn là số lẻ. Nếu n là số chẵn thì n+1 là một số lẻ nên sau một số bước nhất định, i sẽ bằng n+1. Tuy nhiên, nếu n là một số lẻ thì n+1 là một số chẵn, do i là số lẻ nên dù có qua bao nhiêu bước đi chăng nữa, i vẫn khác n+1. Trong trường hợp đó, thuật toán trên sẽ bị quẩn. c. Tính đúng Tính “đúng” là một tính chất khá hiển nhiên nhưng là tính chất khó đạt tới nhất. Thực vậy, khi giải quyết một vấn đề-bài toán, ta luôn luôn mong muốn lời giải của mình sẽ cho kết quả đúng nhưng không phải lúc nào cũng đạt được. Mọi học sinh khi làm bài kiểm tra đều muốn bài làm của mình có đáp số đúng nhưng trên thực tế, trong lớp học chỉ có một số học sinh nhất định là có khả năng đưa ra lời giải đúng! d. Tính hiệu quả 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ế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán. e. Tính tổng quát 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 đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi. Bên cạnh định nghĩa của thuật toán, chúng ta hãy cùng tìm hiểu vai trò của thuật toán là gì trong phần tiếp theo này. Nhìn chung vai trò của thuật toán bao gồm: – Thuật toán là phần quan trọng, không thể thiếu khi tiếp cận các vấn đề liên quan đến lĩnh vực lập trình. – Thuật toán tốt mang đến hiệu quả cao, giúp các chương trình hoạt động hiệu quả với tốc độ xử lý nhanh chóng, tiết kiệm tài nguyên. – Thuật toán giúp lập trình viên hiểu rõ và sâu hơn về ứng dụng, chương trình.
Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm. 1. Khái niệm bài toán - Bài toán là một việc nào đó mà con người muốn máy tính thực hiện. - Các yếu tố của một bài toán: + Input: Thông tin đã biết, thông tin đưa vào máy tính. + Output: Thông tin cần tìm, thông tin lấy ra từ máy tính. - Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương, khi đó: + Input: hai số nguyên dương A, B. + Output: ước chung lớn nhất của A và B 2. Khái niệm thuật toán a) Khái niệm Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm. b) Biểu diễn thuật toán - Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành. - Sử dụng sơ đồ khối để mô tả thuật toán. c) Các tính chất của thuật toán - Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác. - Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo. - Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. 3. Một số ví dụ về thuật toán Ví dụ 1: Kiểm tra tính nguyên tố của 1 số nguyên dương • Xác định bài toán - Input: N là một số nguyên dương; - Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″. • Ý tưởng: - Đị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″ - Nếu N = 1 thì N không là số nguyên tố. - Nếu 1 < N < 4 thì N là số nguyên tố. - N ≥ 4: Tìm ước i đầu tiên > 1 của N. + Nếu i < N thì N không là số nguyên tố (vì N có ít nhất 3 ước 1, i, N). + Nếu i = N thì N là số nguyên tố. • 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ố nguyên tố″, ngược lại thì thông báo ″N không là số nguyên tố″, kết thúc; b) Sơ đồ khối Lưu ý: 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 thì N là số nguyên tố. Ví dụ 2: Sắp xếp bằng cách tráo đổi • Xác định bài toán - Input: Dãy A gồm N số nguyên a1, a2,…, an - Output: Dãy A được sắp xếp thành dãy không giảm. • Ý tưởng - Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. (Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy). - Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa. • Xây dựng thuật toán a) Cách liệt kê - Bước 1: Nhập N, các số hạng a1, a2,…, an; - Bước 2: M ← N; - Bước 3: Nếu M < 2 thì đưa ra dãy A đã được sắp xếp, rồi kết thúc; - Bước 4: M ← M – 1, i ← 0; - Bước 5: i ← i + 1; - Bước 6: Nếu i > M thì quay lại bước 3; - Bước 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; - Bước 8: Quay lại bước 5; b) Sơ đồ khối Ví dụ 3: Bài toán tìm kiếm • Xác định bài toán - 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) Ví dụ : 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) • Ý 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, ta 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. • Xây dựng thuật toán a) Cách liệt kê - 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; b) Sơ đồ khối Ví dụ 4: Tìm kiếm nhị phân • Xác định bài toán - Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,…, an và một số nguyên k. Ví dụ: Dãy A gồm các số nguyên 2 4 5 6 9 21 22 30 31 33 và k = 21 (k = 25) - 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 21 trong dãy là 6 (không tìm thấy 25) • Ý tưởng Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm (agiữa), khi đó chỉ xảy ra một trong ba trường hợp: - Nếu agiữa= k thì tìm được chỉ số, kết thúc; - Nếu agiữa > k thì việc tìm kiếm thu hẹp chỉ xét từ adầu (phạm vi) → agiữa - 1; - Nếu agiữa < k việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1→acuối (phạm vi). Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng. • Xây dựng thuật toán a) Cách liệt kê - Bước 1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k; - Bước 2: Đầu ←1; Cuối ←N; - Bước 3: Giữa←[(Đầu+Cuối)/2]; - Bước 4: Nếu agiữa = k thì thông báo chỉ số Giữa, rồi kết thúc; - Bước 5: Nếu agiữa > k thì đặt Cuối = Giữa - 1 rồi chuyển sang bước 7; - Bước 6: Đầu ←Giữa + 1; - Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k trên dãy, rồi kết thúc; - Bước 8: Quay lại bước 3. b) Sơ đồ khối Loigiaihay.com |
