Lời giải chuẩn nhất cho câu hỏi: “ Tiêu chuẩn lựa chọn thuật toán: ” và phần kiến thức mở rộng thú vị do TOP TÀI LIỆU biên soạn là tài liệu hay dành cho các bạn học sinh và thầy cô giáo tham khảo
Câu hỏi
Tiêu chuẩn lựa chọn thuật toán:
A. Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép
B. Độ phức tạp của thuật
toán
C. Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…
D. Cả 3 ý trên đều đúng
Lời giải :
đáp án đúng: D
Khi lựa chọn thuật toán để giải một bài toán cụ thể cần căn cứ vào các tiêu chí sau:
+ Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép
+ Độ phức tạp của thuật toán
+ Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…
Kiến thức tham khảo
Khái niệm, cách phân loại thuật toán
1. Khái niệm thuật toán
– Thuật toán hay giải thuật [tiếng anh là Algorithm] có khá nhiều định nghĩa phức tạp. Bạn có thể đọc ở nhiều nguồn để hiểu thêm về nó. Cá nhân tôi định nghĩa dễ hiểu rằng, thuật toán là “thuật” [phương pháp] để giải quyết 1 bài toán. Nói dễ hiểu hơn, mỗi một bài toán giống như một chiếc hòm chứa đựng kho báu [kết quả, đáp án], và chiếc chìa khoá để mở cái hòm đó chính là “giải thuật”. Nếu dùng sai chìa khoá, bạn vẫn có thể mở được hòm, nhưng mà sẽ mất nhiều thời gian, hoặc mở được hòm thì kho báu ở bên trong bị méo mó, không toàn vẹn. Sử dụng đúng chìa khoá, sẽ giúp bạn lấy được kho báu 1 cách dễ dàng, nhanh chóng. Tất nhiên mỗi chiếc hòm sẽ luôn cần loại chìa khoá khác nhau, giống như một bài toán luôn có những giải thuật xác định. Không có chiếc chìa khoá nào mở được tất cả các hòm, cũng như không có giải thuật nào giải được toàn bộ các bài toán.
2. Cách phân loại thuật toán
– Nếu không hiểu rõ thuật toán sẽ rất khó để phân loại chúng. Tùy thuộc vào hoàn cảnh sử dụng, các tiêu chí khác nhau mà thuật toán được phân ra nhiều loại.
a. 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ị.
b.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ả.
Các hình thức hóa của thuật toán
Các hình thức hóa của thuật toán
Các thuật toán rất cần thiết cho cách máy tính xử lý dữ liệu. Nhiều chương trình máy tính chứa các thuật toán trình bày chi tiết các hướng dẫn cụ thể mà máy tính phải thực hiện — theo một thứ tự cụ thể — để thực hiện một nhiệm vụ cụ thể, chẳng hạn như tính tiền lương của nhân viên hoặc in phiếu điểm của học sinh. Vì vậy, một thuật toán có thể được coi là bất kỳ chuỗi hoạt động nào có thể được mô phỏng bởi một hệ thống hoàn chỉnh Turing. Các tác giả khẳng định luận điểm này bao gồm Minsky [1967], Savage [1987] và Gurevich [2000]:
Minsky: “Nhưng chúng tôi cũng sẽ duy trì, với Turing… rằng bất kỳ thủ tục nào có thể” tự nhiên “được gọi là hiệu quả, trên thực tế, có thể được thực hiện bởi một chiếc máy [đơn giản]. Mặc dù điều này có vẻ cực đoan, nhưng những lập luận… ủng hộ nó thì khó có thể bác bỏ ”.
Gurevich:
“… Lập luận không chính thức của Turing ủng hộ luận điểm của ông ấy biện minh cho luận điểm mạnh mẽ hơn: mọi thuật toán đều có thể được mô phỏng bởi máy Turing… theo Savage [1987], thuật toán là một quá trình tính toán được xác định bởi máy Turing”.
Máy Turing có thể xác định các quy trình tính toán không kết thúc. Các định nghĩa không chính thức của thuật toán thường yêu cầu thuật toán luôn kết thúc. Yêu cầu này làm cho nhiệm vụ quyết định xem một thủ tục chính thức có phải là một thuật
toán không trong trường hợp chung – do một định lý chính của lý thuyết tính toán được gọi là bài toán dừng.
Thông thường, khi một thuật toán được liên kết với xử lý thông tin, dữ liệu có thể được đọc từ nguồn đầu vào, được ghi vào thiết bị đầu ra và được lưu trữ để xử lý thêm. Dữ liệu được lưu trữ được coi là một phần của trạng thái bên trong của thực thể thực hiện thuật toán. Trong thực tế, trạng thái được lưu trữ trong một hoặc nhiều cấu trúc dữ liệu.
Đối với một số quá trình tính toán này, thuật toán phải được xác định chặt chẽ: được chỉ định theo cách nó áp dụng trong mọi trường hợp có thể phát sinh. Điều này có nghĩa là mọi bước có điều kiện phải được xử lý một cách có hệ thống, theo từng trường hợp cụ thể; các tiêu chí cho từng trường hợp phải rõ ràng [và có thể tính toán được].
Bởi vì một thuật toán là một danh sách chính xác của các bước chính xác, thứ tự tính toán luôn quan trọng đối với hoạt động của thuật toán. Các hướng dẫn thường được giả định là được liệt kê rõ ràng và được mô tả là bắt đầu “từ trên cùng” và đi “xuống dưới cùng” —một ý tưởng được mô tả chính thức hơn bằng luồng kiểm soát.
Cho đến nay, cuộc thảo luận về việc chính thức hóa một thuật toán đã giả định các tiền đề của lập trình mệnh lệnh. Đây là quan niệm phổ biến nhất – một quan niệm cố gắng mô tả một nhiệm vụ bằng các phương tiện “máy móc”, rời rạc. Duy nhất cho quan niệm về các thuật toán chính thức hóa này là phép toán gán, đặt giá trị của một biến. Nó bắt nguồn từ trực giác của ” bộ nhớ ” như một bàn di chuột. Dưới đây là một ví dụ về sự phân công như vậy.
Đối với một số quan niệm thay thế về những gì tạo thành một thuật toán, hãy xem lập trình hàm và lập trình logic.