Trong toán học và khoa học máy tính, một thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.[1][2] Các thuật toán luôn rõ ràng và được sử dụng chỉ rõ việc thực hiện các phép tính, xử lý dữ liệu, suy luận tự động và các tác vụ khác.
Là một phương pháp hiệu quả, một thuật toán có thể được biểu diễn trong một khoảng không gian và thời gian hữu hạn,[3] và bằng một ngôn ngữ hình thức được xác định rõ ràng [4] để tính toán một hàm số.[5] Bắt đầu từ trạng thái ban đầu và đầu vào ban đầu (có thể trống),[6] các hướng dẫn mô tả một phép tính, khi được thực thi, sẽ tiến hành qua một số [7] hữu hạn các trạng thái kế tiếp được xác định rõ, cuối cùng tạo ra “đầu ra” [8] và chấm dứt ở trạng thái kết thúc cuối cùng. Sự chuyển đổi từ trạng thái này sang trạng thái tiếp theo không nhất thiết phải mang tính xác định; một số thuật toán, được gọi là thuật toán ngẫu nhiên, kết hợp đầu vào ngẫu nhiên.[9]
Khái niệm thuật toán đã tồn tại từ thời cổ đại. Các thuật toán số học, chẳng hạn như thuật toán chia, được sử dụng bởi các nhà toán học Babylon cổ đại vào khoảng 2500 TCN và các nhà toán học Ai Cập vào khoảng 1550 TCN.[10] Các nhà toán học Hy Lạp sau đó đã sử dụng các thuật toán trong sàng Eratosthenes để tìm số nguyên tố,[11] và thuật toán Euclide để tìm ước chung lớn nhất của hai số.[12] Các nhà toán học Ả Rập như al-Kindi vào thế kỷ thứ 9 đã sử dụng các thuật toán mật mã để phá mã, dựa trên phân tích tần số.[13]
Bản thân từ thuật toán (algorithm) từ bắt nguồn từ nhà toán học thế kỷ thứ 9 Muḥammad ibn Mūsā al-Khwārizmī, tên ông được Latinh hóa thành Algoritmi.[14] Việc chính thức hóa một phần những gì sẽ trở thành khái niệm thuật toán hiện đại bắt đầu với nỗ lực giải Entscheidungsproblem (vấn đề quyết định) do David Hilbert đặt ra vào năm 1928. Các công thức hóa sau này được đóng khung như những nỗ lực để xác định ” khả năng tính toán hiệu quả ” [15] hoặc “phương pháp hiệu quả”.[16] Những công thức hóa đó bao gồm các hàm đệ quy Gödel – Herbrand – Kleene của các năm 1930, 1934 và 1935, phép tính lambda của Alonzo Church năm 1936, Công thức 1 của Emil Post năm 1936 và các máy Turing của Alan Turing năm 1936–37 và 1939.
Biểu diễn thuật toán bằng sơ đồ khối
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ỏ ”.[27]
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”.[28]
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.
Các thuật toán có thể được thể hiện bằng nhiều loại ký hiệu, bao gồm ngôn ngữ tự nhiên, mã giả, lưu đồ, biểu đồ drakon, ngôn ngữ lập trình hoặc bảng điều khiển (được xử lý bởi trình thông dịch). Các biểu thức ngôn ngữ tự nhiên của các thuật toán có xu hướng dài dòng và mơ hồ, và hiếm khi được sử dụng cho các thuật toán phức tạp hoặc kỹ thuật. Mã giả, lưu đồ, biểu đồ drakon và bảng điều khiển là những cách có cấu trúc để thể hiện các thuật toán tránh nhiều sự mơ hồ thường gặp trong các câu lệnh dựa trên ngôn ngữ tự nhiên. Các ngôn ngữ lập trình chủ yếu nhằm mục đích thể hiện các thuật toán dưới dạng có thể được thực thi bởi máy tính, nhưng cũng thường được sử dụng như một cách để định nghĩa hoặc tài liệu hóa các thuật toán.
Có thể có nhiều cách biểu diễn khác nhau và người ta có thể thể hiện một chương trình máy Turing nhất định dưới dạng một chuỗi các bảng máy (xem máy trạng thái hữu hạn, bảng chuyển đổi trạng thái và bảng điều khiển để biết thêm), dưới dạng lưu đồ và biểu đồ drakon (xem biểu đồ trạng thái để biết thêm), hoặc như một dạng mã máy thô sơ hoặc mã lắp ráp được gọi là “bộ tứ” (xem máy Turing để biết thêm).
Các đại diện của thuật toán có thể được phân loại thành ba cấp độ được chấp nhận của mô tả máy Turing, như sau:[29]
“… Văn xuôi để mô tả một thuật toán, bỏ qua các chi tiết triển khai. Ở cấp độ này, chúng tôi không cần phải đề cập đến cách máy quản lý băng hoặc đầu từ của nó.”
“… Văn xuôi được sử dụng để xác định cách máy Turing sử dụng đầu vào của nó và cách nó lưu trữ dữ liệu trên băng của nó. Ở cấp độ này, chúng tôi không đưa ra thông tin chi tiết về các trạng thái hoặc chức năng chuyển tiếp. “
Chi tiết nhất, “mức thấp nhất”, đưa ra “bảng trạng thái” của máy Turing.
Thiết kế thuật toán đề cập đến một phương pháp hoặc một quy trình toán học để giải quyết vấn đề và các thuật toán kỹ thuật. Việc thiết kế các thuật toán là một phần của nhiều lý thuyết giải pháp nghiên cứu hoạt động, chẳng hạn như lập trình động và chia để trị. Các kỹ thuật thiết kế và triển khai các thiết kế thuật toán còn được gọi là các mẫu thiết kế thuật toán,[30] với các ví dụ bao gồm mẫu phương pháp mẫu và mẫu trang trí.
Một trong những khía cạnh quan trọng nhất của thiết kế thuật toán nằm ở việc tạo ra thuật toán có thời gian chạy hiệu quả, còn được gọi là Big O của nó.
Các bước điển hình trong quá trình phát triển thuật toán:
Đặc điểm kỹ thuật của thuật toán
Kiểm tra tính đúng đắn của thuật toán
Thuật toán NAND logic được triển khai điện tử trong chip 7400
Hầu hết các thuật toán được thiết kế để thực hiện như các chương trình máy tính. Tuy nhiên, các thuật toán cũng được thực hiện bằng các phương tiện khác, chẳng hạn như trong mạng nơ-ron sinh học (ví dụ, não người thực hiện phép tính số học hoặc côn trùng đang tìm kiếm thức ăn), trong mạch điện hoặc trong một thiết bị cơ khí.
Các ví dụ về lưu đồ về cấu trúc Böhm-Jacopini chính tắc: SEQUENCE (hình chữ nhật xuống trang), WHILE-DO và IF-THEN-ELSE. Ba cấu trúc được tạo bởi GOTO có điều kiện nguyên thủy ({{{1}}}) (hình thoi), GOTO không điều kiện (hình chữ nhật), các toán tử gán khác nhau (hình chữ nhật) và HALT (hình chữ nhật). Việc lồng các cấu trúc này vào bên trong các khối gán dẫn đến các sơ đồ phức tạp (xem Tausworthe 1977: 100, 114).
Trong các hệ thống máy tính, thuật toán về cơ bản là một ví dụ của logic được viết trong phần mềm bởi các nhà phát triển phần mềm, để có hiệu quả đối với (các) máy tính “đích” nhằm tạo ra đầu ra từ đầu vào (có thể là rỗng) nhất định. Một thuật toán tối ưu, thậm chí chạy trong phần cứng cũ, sẽ tạo ra kết quả nhanh hơn thuật toán không tối ưu (độ phức tạp thời gian cao hơn) cho cùng mục đích, chạy trong phần cứng hiệu quả hơn; đó là lý do tại sao các thuật toán, như phần cứng máy tính, được coi là công nghệ.
Chương trình “thanh lịch” (nhỏ gọn), chương trình “tốt” (nhanh): Khái niệm “đơn giản và thanh lịch” xuất hiện không chính thức ở Knuth và chính xác là ở Chaitin:
Knuth: “… chúng tôi muốn có các thuật toán tốt theo một khía cạnh thẩm mỹ được xác định lỏng lẻo. Một tiêu chí… là khoảng thời gian thực hiện thuật toán…. Các tiêu chí khác là khả năng thích ứng của thuật toán với máy tính, tính đơn giản và sang trọng của nó, v.v. ” [31]
Chaitin: “… một chương trình là ‘thanh lịch’, theo ý tôi thì đó là chương trình nhỏ nhất có thể để tạo ra kết quả đầu ra mà nó thực hiện” [32]
Chaitin mở đầu cho định nghĩa của mình bằng: “Tôi sẽ cho bạn thấy rằng bạn không thể chứng minh rằng một chương trình là ‘thanh lịch ‘” —chẳng hạn như một bằng chứng sẽ giải quyết được bài toán tạm dừng (ibid).
Thuật toán so với hàm có thể tính toán bằng một thuật toán: Đối với một hàm đã cho, nhiều thuật toán có thể tồn tại. Điều này đúng, ngay cả khi không mở rộng tập lệnh có sẵn cho lập trình viên. Rogers nhận xét rằng “Điều quan trọng là phải phân biệt giữa khái niệm thuật toán, tức là thủ tục và khái niệm hàm có thể tính toán bằng thuật toán, tức là ánh xạ được tạo ra bởi thủ tục. Cùng một chức năng có thể có một số thuật toán khác nhau “.[33]
Thật không may, có thể có sự cân bằng giữa tính tốt (tốc độ) và tính thanh lịch (tính nhỏ gọn) —một chương trình thanh lịch có thể cần nhiều bước để hoàn thành một phép tính hơn một chương trình kém thanh lịch hơn. Ví dụ sử dụng thuật toán Euclid xuất hiện bên dưới.
Máy tính, các mô hình tính toán: Máy tính (hay “máy tính” của con người [34]) là một loại máy bị hạn chế, một “thiết bị cơ khí xác định rời rạc” [35] làm theo hướng dẫn của nó một cách mù quáng.[36] Các mô hình sơ khai của Melzak và Lambek [37] giảm khái niệm này thành bốn yếu tố: (i) các vị trí rời rạc, dễ phân biệt, (ii) các bộ đếm rời rạc, không thể phân biệt được [38] (iii) một tác nhân, và (iv) một danh sách các hướng dẫn có hiệu quả so với khả năng của tác nhân.[39]
Minsky mô tả một biến thể phù hợp hơn của mô hình “bàn tính” của Lambek trong “Các cơ sở rất đơn giản để tính toán ” của ông.[40] Máy của Minsky tiến hành tuần tự thông qua năm (hoặc sáu, tùy thuộc vào cách đếm) lệnh, trừ khi IF – THEN GOTO có điều kiện hoặc GOTO không điều kiện thay đổi luồng chương trình không theo trình tự. Bên cạnh HALT, máy của Minsky bao gồm ba hoạt động gán (thay thế, thay thế) [41]: ZERO (ví dụ: nội dung của vị trí được thay thế bằng 0: L ← 0), SUCCESSOR (ví dụ: L ← L + 1) và DECREMENT (ví dụ: L ← L – 1).[42] Hiếm khi một lập trình viên phải viết “mã” với một tập lệnh giới hạn như vậy. Nhưng Minsky cho thấy (Melzak và Lambek cũng vậy) rằng cỗ máy của anh ấy là Turing hoàn chỉnh với chỉ bốn loại lệnh chung: GOTO có điều kiện, GOTO vô điều kiện, gán / thay thế / thay thế và HALT. Tuy nhiên, một số hướng dẫn gán khác nhau (ví dụ: DECREMENT, INCREMENT và ZERO / CLEAR / EMPTY cho máy Minsky) cũng được yêu cầu đối với tính năng Turing-completeness; đặc điểm kỹ thuật chính xác của chúng phần nào tùy thuộc vào nhà thiết kế. GOTO vô điều kiện là một sự tiện lợi; nó có thể được xây dựng bằng cách khởi tạo một vị trí chuyên dụng bằng 0, ví dụ như lệnh “Z ← 0”; sau đó lệnh IF Z = 0 THEN GOTO xxx là vô điều kiện.
Mô phỏng thuật toán: ngôn ngữ máy tính (computor): Knuth khuyên người đọc rằng “cách tốt nhất để học một thuật toán là thử nó.. Lấy ngay giấy bút và làm việc với một ví dụ”.[43] Nhưng những gì về một mô phỏng hoặc thực hiện các điều thực tế? Lập trình viên phải dịch thuật toán sang ngôn ngữ mà trình mô phỏng / máy tính / trình biên dịch có thể thực thi một cách hiệu quả. Stone đưa ra một ví dụ về điều này: khi tính toán căn bậc hai, người tính toán phải biết cách lấy căn bậc hai. Nếu không, thì thuật toán, để có hiệu quả, phải cung cấp một bộ quy tắc để trích xuất căn bậc hai.[44]
Điều này có nghĩa là lập trình viên phải biết một “ngôn ngữ” có hiệu quả so với tác nhân tính toán mục tiêu (máy tính). Nhưng mô hình nào nên được sử dụng cho mô phỏng? Van Emde Boas nhận xét “ngay cả khi chúng ta đặt lý thuyết phức tạp dựa trên lý thuyết trừu tượng thay vì máy móc cụ thể, sự tùy tiện trong việc lựa chọn mô hình vẫn còn. Chính tại thời điểm này, khái niệm mô phỏng đi vào “.[45] Khi tốc độ đang được đo, tập lệnh quan trọng. Ví dụ, chương trình con trong thuật toán Euclid để tính phần còn lại sẽ thực thi nhanh hơn nhiều nếu lập trình viên có sẵn lệnh ” modulus ” thay vì chỉ phép trừ (hoặc tệ hơn: chỉ “giảm dần” của Minsky).
Lập trình có cấu trúc, cấu trúc chuẩn: Theo luận điểm của Church – Turing, bất kỳ thuật toán nào cũng có thể được tính toán bằng một mô hình được gọi là Turing hoàn chỉnh và theo các minh chứng của Minsky, tính đầy đủ của Turing chỉ yêu cầu bốn loại lệnh — GOTO có điều kiện, GOTO không điều kiện, phép gán, HALT. Kemeny và Kurtz nhận thấy rằng, trong khi việc sử dụng “vô kỷ luật” GOTO vô điều kiện và IF-THEN GOTO có điều kiện có thể dẫn đến ” mã spaghetti “, một lập trình viên có thể viết các chương trình có cấu trúc chỉ bằng các hướng dẫn này; mặt khác “cũng có thể, và không quá khó, để viết các chương trình có cấu trúc tồi bằng một ngôn ngữ có cấu trúc”.[46] Tausworthe tăng cường ba cấu trúc kinh điển Böhm-Jacopini:[47] SEQUENCE, IF-THEN-ELSE và WHILE-DO, với hai cấu trúc khác: DO-WHILE và CASE.[48] Một lợi ích bổ sung của chương trình có cấu trúc là nó tự cho mình các bằng chứng về tính đúng đắn bằng cách sử dụng quy nạp toán học.[49]
Các ký hiệu lưu đồ hợp quy: Phụ tá đồ họa được gọi là lưu đồ, đưa ra cách mô tả và ghi lại một thuật toán (và một chương trình máy tính của một thuật toán). Giống như quy trình chương trình của máy Minsky, lưu đồ luôn bắt đầu ở đầu trang và tiếp tục xuống. Các ký hiệu chính của nó chỉ có bốn: mũi tên có hướng hiển thị luồng chương trình, hình chữ nhật (SEQUENCE, GOTO), hình thoi (IF-THEN-ELSE) và dấu chấm (OR-tie). Các cấu trúc kinh điển Böhm – Jacopini được tạo ra từ những hình dạng nguyên thủy này. Cấu trúc con có thể “lồng” trong hình chữ nhật, nhưng chỉ khi một lối ra duy nhất xảy ra từ cấu trúc thượng tầng. Các ký hiệu và cách sử dụng chúng để xây dựng các cấu trúc chính tắc được thể hiện trong sơ đồ.
tag: tổng dãy lẻ s=1+2+3+ +n trung bình cộng online