Mục lục
Mặc dù thuật toán có thể gợi ra khá nhiều hình ảnh về các chương trình máy tính thực hiện các quá trình phức tạp về mặt toán học trong bạn. Tuy nhiên chúng lại có thể được hiểu đơn giản là một tập hợp các quy tắc để giải quyết một vấn đề.
1. Thuật toán là gì?
Việc mô tả một thuật toán bằng những từ đơn giản không khó như chúng ta nghĩ. Trong khoa học máy tính, lập trình và toán học, chúng là một chuỗi hướng dẫn trong đó mục tiêu chính là giải quyết một vấn đề cụ thể; thực hiện một hành động hoặc tính toán nhất định.
Tuy nhiên, trong đời sống hàng ngày chúng ta cũng dùng thuật toán rất nhiều lần. Và hiểu đơn giản đây là một tập hợp các nguyên tắc mô tả cách thực hiện một tác vụ.
Ví dụ nhé: Ngay cả những thứ từ đơn giản như công thức nấu ăn hay danh sách chỉ đường đến nhà của một người bạn. Đến những thứ phức tạp hơn một chút trong bối cảnh khoa học máy tính. Thì thuật ngữ này xuất hiện nhiều hơn. Chúng là một đặc tả rất rõ ràng để xử lý dữ liệu; để thực hiện các phép tính trong số nhiều tác vụ khác.
Bạn có thể đã nghe thấy điều này. Facebook quyết định hiển thị cho bạn điều này hay điều khác; dựa trên các thuật toán của họ và mối quan hệ với các hoạt động cụ thể của bạn. Do đó, một cách hay nữa để giải thích khái niệm này là nói rằng bất cứ ai tạo ra thuật toán cụ thể đó đều là người đặt ra các quy tắc của trò chơi.
2. Chúng ở khắp mọi nơi
Như đã nói, các thuật toán ở khắp mọi nơi và hiện diện trong cuộc sống của chúng ta hàng ngày, ngay cả khi chúng ta không nhận ra.
Lấy ví dụ về một công thức nấu ăn. Công thức là một danh sách các hướng dẫn được sử dụng để thực hiện một nhiệm vụ cụ thể. Ví dụ: nếu bạn làm theo thuật toán để nướng một chiếc bánh vani từ hỗn hợp hộp. Bạn sẽ làm theo số bước được ghi trên hộp hoặc trên sổ tay hướng dẫn đi kèm.
Hoặc ví dụ ở trong toán học đơn giản. Quá trình giải quyết một vấn đề toán học như “73 chia 3 bằng bao nhiêu” có thể đạt được bằng cách thực hiện thuật toán sau:
Bao nhiêu lần 3 thành 7?
Câu trả lời là 2
Còn lại bao nhiêu? 1
Đặt số 1 (mười) trước số 3.
Bao nhiêu lần 3 đi thành 13?
Câu trả lời là 4 với phần dư là một.
Và cuối cùng, câu trả lời là 24 với phần dư là 1
Một thuật toán trong toán học không khác một thuật toán trong khoa học máy tính; hoặc trong phát triển ứng dụng. Cả hai đều có cùng định nghĩa, mô tả và ý nghĩa.
3. Lịch sử thuật toán
Gần đây, thuật toán đã đi vào cuộc sống của chúng ta và đang trở nên phổ biến. Giao dịch theo thuật toán; thiên vị thuật toán; thuật toán Facebook; thậm chí cả chiến tranh thuật toán. Tất cả những thuật ngữ này đã trở thành một phần từ vựng của chúng ta trong những năm gần đây. Một số người còn tuyên bố rằng chúng ta đang sống trong một thời đại mới: thời đại của thuật toán.
Nhưng các thuật toán không phải là mới. Chúng ta đã sử dụng chúng; dù cố ý hay không, thì đã là trong hàng trăm đến hàng nghìn năm trước. Các thuật toán chỉ đơn thuần là những mô tả cụ thể về các hành động từng bước cần xảy ra để đạt được một kết quả cụ thể. Bất kỳ quá trình dạy ai đó làm điều gì đó đều sử dụng các thuật toán. Vì thế đây là một trong những công cụ chia sẻ kiến thức phổ biến nhất.
3.1. Hướng dẫn hành động con người
Thuật ngữ thuật toán (algorithm) bắt nguồn từ tên của Muhammad ibn Mūsā al’Khwārizmī, một nhà toán học Ba Tư ở thế kỷ thứ 9. Tên được Latinh hóa của ông, Algoritmi, có nghĩa là “hệ thống số thập phân”.
Các thuật toán đầu tiên được ghi lại trên giấy ở Hy Lạp cổ đại. Các học giả như Nic Gastus hay Euclid sau đó đã tạo ra các nền tảng của toán học hiện đại. Để dễ hiểu và khả năng áp dụng các ý tưởng của mình, họ đã thể hiện nhiều trong số đó dưới dạng các hành động từng bước.
Nic Gastus đã giới thiệu Sàng Eratosthenes. Đây là một thuật giải toán để đơn giản hóa quá trình tìm các số nguyên tố nhỏ trong một tập hợp nhất định. Và được sử dụng hiệu quả cho đến ngày nay bởi các sinh viên học cách viết mã máy tính.
Euclid, một học giả khác nổi tiếng hơn nhiều so với Nic gastus ngày nay, đã đưa ra một công thức để xác định ước chung lớn nhất của hai số. Một lần nữa, đây không phải là nhiệm vụ dễ dàng, nhưng lại rất cần thiết trong nhiều tình huống. Hãy tưởng tượng bạn có một căn phòng với kích thước chính xác là 612 x 2006 cm cần một tầng mới.
Thuật toán của Euclid sẽ giúp bạn tìm kích thước của những viên gạch vuông lớn nhất có thể phủ gọn gàng sàn nhà. Câu trả lời từ công thức đưa ra là 34 cm x 34 cm; dẫn đến bố cục có 18 x 59 ô. Tất nhiên, bạn biết rằng câu trả lời là sai và bạn không biết mình đang làm gì vì thuật toán không xem xét chiều rộng vữa nên không để lại khoảng trống cho nó. Đừng sợ: điều này cũng có thể được tính toán và được diễn đạt gọn gàng dưới dạng một thuật toán.
Thuật toán Sàng Eratosthenes
3.2 Hướng dẫn hành động máy tính
Vài trăm năm sau, nhiều thuật toán khác đã được tạo ra và ghi lại trên giấy. Và thuật toán đầu tiên được thực thi trên một chiếc máy được tạo ra bởi Ada Lovelace (nhũ danh Byron); và được xuất bản vào năm 1843.
Ada là một nhân vật đặc biệt. Cô sinh năm 1815 là đứa con hợp pháp duy nhất của nhà thơ Lord Byron. Cô đã phát triển tài năng tuyệt vời trong toán học. Và vì tình yêu thơ rõ ràng đã có sẵn trong gen của cô ấy. Bằng cách nào đó cô ấy đã phát triển cân bằng tình yêu khoa học và thơ ca. Là một nhà toán học lành nghề, cô biết Charles Babbage nhờ những phát minh của ông. Ông là người được gọi là “cha đẻ của máy tính”. Cả hai phát triển mối quan hệ công việc và tình bạn. Ada rất quan tâm đến một trong những thiết kế của Charles – Công cụ phân tích (Analytical Engine).
Công cụ phân tích là một máy tính cơ học và là cỗ máy cơ học Ada đã viết thuật toán được cho là đầu tiên; (điều này vẫn còn nhiều tranh luận chưa rõ ràng). Cô chỉ ra cách tính toán một chuỗi số phức tạp là chuỗi số Bernoulli bằng Công cụ phân tích. Công thức hiện được công nhận rộng rãi là thuật toán máy tính đầu tiên trong lịch sử.
Ada không chỉ giới hạn bản thân trong các phép tính toán học thuần túy. Cô ấy là một người có tầm nhìn xa trông rộng thực sự. Trong khi nhiều người cùng thời với cô ấy xem những chiếc máy tính cơ học đầu tiên chủ yếu là máy tính toán số. Thì cô ấy đang hỏi điều gì ngoài việc thực hiện các phép tính. Cô tò mò về tiềm năng rộng lớn hơn của máy tính cơ học như một công cụ hợp tác. Cô đã hy vọng thấy những chiếc máy tính sẽ làm nhiều điều hơn là chỉ thông qua việc tự động hóa các phép tính. Thật không may, việc xây dựng Công cụ phân tích chưa được hoàn thành trước khi Ada qua đời. Và vì vậy cô ấy không bao giờ có thể thấy thuật toán của mình đang hoạt động.
Thế kỷ 19 trở thành kỷ nguyên của “các thuật toán được nhúng trong máy móc”.
Có rất nhiều máy móc đã tự động hóa tất cả các loại hành động của con người. Ví dụ nhé, nếu bạn cần một họa tiết phức tạp trên một mảnh vải. Joseph Marie Jacquard, một thợ dệt và thương gia người Pháp, đã có một giải pháp cho bạn: Máy dệt Jacquard. Nó cho phép các nhà sản xuất vải tạo ra các mẫu tinh vi. Bằng cách sử dụng một loạt thẻ đục lỗ hướng dẫn cách dệt khung cửi.
Một ví dụ khác, các tổng đài điện thoại đã sử dụng các thiết bị cơ khí tinh vi để kết nối các cuộc điện thoại.
Những cỗ máy này, dù là máy dệt hay máy trao đổi; đều là đột phá vào thời điểm đó và vẫn còn ấn tượng cho đến ngày nay. Thật khó để không thán phục mức độ phức tạp của một số loại máy này. Tuy nhiên, tất cả các thiết bị này vẫn hoàn toàn là cơ khí. Chúng được làm bằng đòn bẩy, công tắc, trục. Nên chúng gây ra rất nhiều tiếng ồn và khác rất xa so với những thiết bị của chúng ta ngày nay.
3.3. Các thuật toán đa năng trên máy tính
Mãi cho đến những năm 1930, chúng ta mới thấy những đề cập đầu tiên về thuật toán trong máy tính điện tử (phi cơ học).
Alan Turing là một trong những nhà khoa học đầu tiên đã chính thức nắm bắt cách các cá nhân thực hiện các phép tính. Mục tiêu của ông là nắm bắt một quy trình chung. Thay vì một quy trình cụ thể cho một nhiệm vụ cụ thể; chẳng hạn như xác định các số nguyên tố hoặc tính ước số chung lớn nhất. Quy trình chung sau đó có thể được sử dụng để thực hiện các nhiệm vụ cụ thể.
Công trình khái niệm của Turing đã dẫn đến sự phát triển của cái mà ngày nay được gọi là Máy Turing. Đến lượt mình, Máy Turing đã dẫn đến sự xuất hiện của các máy tính đa năng. Trái ngược với các máy trước, máy tính mới sẽ thực thi các tập lệnh tùy ý. Chúng có thể được sử dụng cho các mục đích mà người tạo ra chúng thậm chí không dự đoán được. Nói cách khác: Công việc của Turing đã dẫn đến sự phát triển của các máy tính mà chúng tôi có thể cài đặt và chạy các ứng dụng.
Nhiều thập kỷ sau, các thuật toán đã trở nên cực kỳ tinh vi. Trên thực tế, tinh vi đến mức chúng ta thường không thể giải thích cách chúng hoạt động. Trong thế kỷ 20, nhiều người thích nghĩ về các thuật toán máy tính như hộp đen. Bạn không cần phải hiểu chúng hoạt động chính xác như thế nào. Tất cả những gì bạn quan tâm là đầu vào; những gì đi vào hộp đen; và đầu ra; những gì xuất hiện.
Chúng ta đang sống trong một thế giới mà thuật toán ở khắp mọi nơi – không chỉ trên giấy hay trong tâm trí chúng ta; mà còn điều khiển máy móc, máy tính và robot.
4. Kết
Thuật ngữ ‘thuật toán’ được sử dụng rộng rãi trong thế giới công nghệ và cả đời sống hàng ngày. Chúng xuất hiện từ rất lâu để chỉ những chỉ dẫn; hướng dẫn về một tác vụ cụ thể nào đó như nấu một món ăn. Hy vọng qua bài viết; bạn đã có thể hình dung được lịch sử ra đời của chúng và biết thêm về những thuật toán đầu tiên.
