Thuật toán, quy trình có hệ thống tạo ra một số bước hữu hạn, câu trả lời cho một câu hỏi hoặc giải pháp cho một vấn đề. Tên này bắt nguồn từ bản dịch tiếng Latinh, Algoritmi de numero Indorum, của nhà toán học Hồi giáo thế kỷ thứ 9 al-Khwarizmi chuyên luận số học Al-Khwarizmi Liên quan đến nghệ thuật tính toán của Ấn Độ giáo.
khoa học máy tính: Thuật toán và độ phức tạp
Một thuật toán là một thủ tục cụ thể để giải quyết một vấn đề tính toán được xác định rõ. Sự phát triển và phân tích các thuật toán là cơ bản
Đối với các câu hỏi hoặc vấn đề chỉ có một tập hợp hữu hạn các trường hợp hoặc giá trị, thuật toán luôn tồn tại (ít nhất là về nguyên tắc); nó bao gồm một bảng các giá trị của các câu trả lời. Nói chung, đây không phải là một quy trình tầm thường để trả lời các câu hỏi hoặc vấn đề có số lượng trường hợp hoặc giá trị vô hạn để xem xét, chẳng hạn như Hồi là số tự nhiên (1, 2, 3,..) hoặc là số chia chung lớn nhất của các số tự nhiên a và b? Câu hỏi đầu tiên thuộc về một lớp gọi là quyết định; một thuật toán tạo ra câu trả lời có hoặc không được gọi là thủ tục quyết định. Câu hỏi thứ hai thuộc về một lớp gọi là tính toán; một thuật toán dẫn đến một câu trả lời số cụ thể được gọi là thủ tục tính toán.
Các thuật toán tồn tại cho nhiều lớp câu hỏi vô hạn như vậy; Các yếu tố của Euclid, được xuất bản khoảng 300 bc, chứa một để tìm ước số chung lớn nhất của hai số tự nhiên. Mỗi học sinh tiểu học được khoan theo cách chia dài, đó là một thuật toán cho câu hỏi Sau khi chia một số tự nhiên a cho một số tự nhiên khác b, thương số và phần còn lại là gì? Việc sử dụng thủ tục tính toán này dẫn đến câu trả lời cho câu hỏi có thể quyết định được. Có phải b chia một? (câu trả lời là có nếu phần còn lại bằng không). Ứng dụng lặp đi lặp lại của các thuật toán này cuối cùng tạo ra câu trả lời cho câu hỏi có thể quyết định được. (câu trả lời là không nếu a chia hết cho số tự nhiên nhỏ hơn ngoài 1).
Đôi khi một thuật toán không thể tồn tại để giải quyết một lớp vấn đề vô hạn, đặc biệt khi một số hạn chế tiếp theo được thực hiện theo phương pháp được chấp nhận. Chẳng hạn, hai vấn đề từ thời Euclid chỉ cần sử dụng la bàn và thước thẳng (thước kẻ không dấu) trong việc tạo góc và xây dựng một hình vuông có diện tích bằng một hình tròn đã cho đã được theo đuổi trong nhiều thế kỷ trước khi chúng được chứng minh là không thể. Vào đầu thế kỷ 20, nhà toán học người Đức có ảnh hưởng David Hilbert đã đề xuất 23 vấn đề cho các nhà toán học để giải quyết trong thế kỷ tới. Vấn đề thứ hai trong danh sách của ông yêu cầu một cuộc điều tra về tính nhất quán của các tiên đề của số học. Hầu hết các nhà toán học ít nghi ngờ về việc đạt được mục tiêu cuối cùng cho đến năm 1931, khi nhà logic học người Áo Kurt Gödel chứng minh kết quả đáng ngạc nhiên rằng phải tồn tại các mệnh đề số học (hoặc câu hỏi) không thể chứng minh hoặc bác bỏ. Về cơ bản, bất kỳ đề xuất nào như vậy đều dẫn đến một quy trình xác định không bao giờ kết thúc (một điều kiện được gọi là vấn đề tạm dừng). Trong một nỗ lực không thành công để xác định ít nhất các mệnh đề nào không thể giải được, nhà toán học và nhà logic học người Anh Alan Turing đã định nghĩa chặt chẽ khái niệm lỏng lẻo của thuật toán. Mặc dù Turing cuối cùng đã chứng minh rằng phải tồn tại những đề xuất không thể giải quyết được, nhưng mô tả của ông về các tính năng thiết yếu của bất kỳ máy thuật toán đa năng hay máy Turing nào đã trở thành nền tảng của khoa học máy tính. Ngày nay, các vấn đề về tính quyết định và khả năng tính toán là trọng tâm trong thiết kế chương trình máy tính, một loại thuật toán đặc biệt.
