Trừ khi bạn thích toán học hoặc lập trình, từ “thuật toán” có thể là tiếng Hy Lạp đối với bạn, nhưng nó là một trong những nền tảng của mọi thứ bạn đang sử dụng để đọc bài viết này. Dưới đây là giải thích nhanh về chúng là gì và cách chúng hoạt động.
Tuyên bố từ chối trách nhiệm: Tôi không phải là giáo viên toán hoặc khoa học máy tính, vì vậy không phải tất cả các thuật ngữ tôi sử dụng đều là kỹ thuật. Đó là bởi vì tôi đang cố gắng giải thích mọi thứ bằng tiếng Anh đơn giản cho những người không hoàn toàn thoải mái với môn toán. Điều đó đang được nói, có một số toán học liên quan, và điều đó là không thể tránh khỏi. Những người đam mê toán học, vui lòng sửa chữa hoặc giải thích tốt hơn trong các nhận xét, nhưng xin vui lòng giữ nó đơn giản cho những người không thích về mặt toán học trong chúng ta.
Hình ảnh của Ian Ruotsala
Thuật toán là gì?
Từ ‘thuật toán’ có từ nguyên tương tự như ‘đại số’, ngoại trừ điều này đề cập đến chính nhà toán học Ả Rập, al-Khwarizmi (chỉ là một mẩu tin thú vị). Thuật toán, đối với những người không phải là lập trình viên trong số chúng ta, là một tập hợp các lệnh lấy đầu vào, A và cung cấp đầu ra, B, thay đổi dữ liệu liên quan theo một cách nào đó. Các thuật toán có rất nhiều ứng dụng. Trong toán học, chúng có thể giúp tính toán các hàm từ các điểm trong tập dữ liệu, trong số những thứ nâng cao hơn nhiều. Ngoài việc sử dụng trong lập trình, chúng đóng vai trò quan trọng trong những thứ như nén tệp và mã hóa dữ liệu.
Một bộ hướng dẫn cơ bản
Giả sử bạn của bạn đang gặp bạn trong một cửa hàng tạp hóa và bạn đang hướng dẫn anh ấy về phía bạn. Bạn nói những điều như “vào qua cửa bên phải”, “vượt qua phần cá ở bên trái” và “nếu bạn nhìn thấy sữa, bạn đã vượt qua tôi.” Các thuật toán hoạt động như vậy. Chúng tôi có thể sử dụng lưu đồ để minh họa các hướng dẫn dựa trên các tiêu chí mà chúng tôi biết trước hoặc tìm hiểu trong quá trình thực hiện.
(hình ảnh có tên “Quy trình phá băng” CHỈNH SỬA: lịch sự của Trigger và Freewheel)
Từ BẮT ĐẦU, bạn sẽ đi theo con đường, và tùy thuộc vào điều gì xảy ra, bạn đi theo “dòng chảy” đến kết quả cuối cùng. Lưu đồ là công cụ trực quan có thể trình bày dễ hiểu hơn một tập hợp các hướng dẫn được sử dụng bởi máy tính. Tương tự, các thuật toán giúp làm điều tương tự với nhiều mô hình dựa trên toán học hơn.
Đồ thị
Hãy sử dụng biểu đồ để minh họa các cách khác nhau mà chúng ta có thể đưa ra hướng đi.
Chúng ta có thể biểu diễn đồ thị này như một kết nối giữa tất cả các điểm của nó. Để tái tạo hình ảnh này, chúng tôi có thể đưa ra một tập hợp các hướng dẫn cho người khác.
Phương pháp 1
Chúng ta có thể biểu diễn điều này dưới dạng một chuỗi các điểm và thông tin sẽ tuân theo dạng chuẩn của đồ thị = {(x1, y1), (x2, y2),…, (xn, yn)}.
graph = {(0,0), (3,0), (3,3), (5,5), (7,10), (8,7), (9,4), (10,1) }
Khá dễ dàng để vẽ từng điểm, điểm này đến điểm khác và kết nối chúng với điểm trước đó. Tuy nhiên, hãy tưởng tượng một biểu đồ có một nghìn điểm hoặc nhiều đoạn thẳng theo mọi cách. Danh sách đó sẽ có rất nhiều dữ liệu, phải không? Và sau đó phải kết nối từng người, từng người một, có thể là một nỗi đau.
Phương pháp 2
Một điều khác chúng ta có thể làm là đưa ra điểm bắt đầu, độ dốc của đường thẳng giữa điểm đó và điểm tiếp theo, và chỉ ra vị trí mong đợi điểm tiếp theo bằng cách sử dụng dạng chuẩn của đồ thị = {(điểm bắt đầu}, [m1, x1, h1],…, [mn, xn, hn]}. Ở đây, biến ‘m’ đại diện cho độ dốc của đường, ‘x’ đại diện cho hướng cần đếm (cho dù là x hay y) và ‘h’ cho bạn biết có bao nhiêu để đếm theo hướng đã nói. Bạn cũng có thể nhớ vẽ một điểm sau mỗi chuyển động.
đồ thị = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,1], [-3,x,1], [-3,x,1]}
Bạn sẽ kết thúc với cùng một đồ thị. Bạn có thể thấy rằng ba thuật ngữ cuối cùng trong biểu thức này giống nhau, vì vậy chúng tôi có thể cắt bớt điều đó bằng cách chỉ nói “lặp lại ba lần” theo một cách nào đó. Giả sử rằng bất cứ khi nào bạn thấy biến ‘R’ xuất hiện, nó có nghĩa là lặp lại điều cuối cùng. Chung ta co thể lam được việc nay:
đồ thị = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,1], [R=2]}
Điều gì sẽ xảy ra nếu các điểm riêng lẻ không thực sự quan trọng và chỉ có bản thân biểu đồ thì sao? Chúng tôi có thể hợp nhất ba phần cuối cùng như vậy:
đồ thị = {(0,0), [0,x,3], [0,y,3], [1,x,2], [2.5,x,2], [-3,x,3]}
Nó rút ngắn mọi thứ lên một chút so với trước đây.
Phương pháp 3
Hãy thử làm theo cách khác.
y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤8
y = -3x + 29, 8≤x≤9
y = -3x + 29, 9≤x≤10
Ở đây chúng tôi có nó trong điều kiện đại số thuần túy. Một lần nữa, nếu bản thân các điểm không quan trọng và chỉ có biểu đồ thì chúng ta có thể hợp nhất ba mục cuối cùng.
y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤10
Bây giờ, bạn chọn phương pháp nào tùy thuộc vào khả năng của bạn. Có thể bạn giỏi toán và vẽ đồ thị nên bạn chọn phương án cuối cùng. Có lẽ bạn giỏi điều hướng nên bạn chọn phương án thứ hai. Tuy nhiên, trong lĩnh vực máy tính, bạn đang thực hiện nhiều loại tác vụ khác nhau và khả năng của máy tính không thực sự thay đổi. Do đó, các thuật toán được tối ưu hóa cho các nhiệm vụ mà chúng hoàn thành.
Một điểm quan trọng khác cần lưu ý là mỗi phương pháp dựa trên một khóa. Mỗi bộ hướng dẫn đều vô dụng trừ khi bạn biết phải làm gì với chúng. Nếu bạn không biết rằng bạn phải vẽ từng điểm và kết nối các điểm, thì tập hợp điểm đầu tiên chẳng có nghĩa lý gì. Trừ khi bạn biết ý nghĩa của từng biến trong phương pháp thứ hai, bạn sẽ không biết cách áp dụng chúng, giống như chìa khóa của mật mã. Chìa khóa đó cũng là một phần không thể thiếu của việc sử dụng các thuật toán và thường thì chìa khóa đó được tìm thấy trong cộng đồng hoặc thông qua một “tiêu chuẩn”.
Nén tệp
Khi bạn tải xuống tệp .zip, bạn sẽ giải nén nội dung để có thể sử dụng bất cứ thứ gì bên trong tệp. Ngày nay, hầu hết các hệ điều hành có thể đi sâu vào các tệp .zip giống như chúng là các thư mục bình thường, làm mọi thứ trong nền. Trên máy tính Windows 95 của tôi hơn một thập kỷ trước, tôi phải giải nén mọi thứ theo cách thủ công trước khi tôi có thể nhìn thấy bất kỳ thứ gì khác ngoài tên tệp bên trong. Đó là vì những gì được lưu trữ trên đĩa dưới dạng tệp .zip không ở dạng có thể sử dụng được. Hãy nghĩ về một chiếc ghế dài. Khi bạn muốn sử dụng nó như một chiếc giường, bạn phải tháo đệm ra và mở ra, điều này sẽ chiếm nhiều diện tích hơn. Khi không cần dùng đến hoặc muốn vận chuyển, bạn có thể gấp lại.
Các thuật toán nén được điều chỉnh và tối ưu hóa đặc biệt cho các loại tệp mà chúng được nhắm mục tiêu. Ví dụ: mỗi định dạng âm thanh sử dụng một cách khác nhau để lưu trữ dữ liệu mà khi được giải mã bởi codec âm thanh, sẽ tạo ra một tệp âm thanh tương tự như dạng sóng gốc. Để biết thêm thông tin về sự khác biệt đó, hãy xem bài viết trước của chúng tôi, Sự khác biệt giữa tất cả các định dạng âm thanh đó là gì? Các định dạng âm thanh không mất dữ liệu và tệp .zip có một điểm chung: cả hai đều mang lại dữ liệu gốc ở dạng chính xác của nó sau quá trình giải nén. Bộ giải mã âm thanh Lossy sử dụng các phương tiện khác để tiết kiệm dung lượng đĩa, chẳng hạn như cắt bớt các tần số mà tai người không thể nghe thấy và làm mịn dạng sóng trong các phần để loại bỏ một số chi tiết. Cuối cùng, mặc dù chúng ta có thể không thực sự nghe được sự khác biệt giữa bản nhạc MP3 và CD, nhưng chắc chắn có sự thiếu hụt thông tin trong bản nhạc trước.
Mã hóa dữ liệu
Các thuật toán cũng được sử dụng khi bảo mật dữ liệu hoặc đường truyền thông. Thay vì lưu trữ dữ liệu để sử dụng ít dung lượng đĩa hơn, nó được lưu trữ theo cách mà các chương trình khác không thể phát hiện được. Nếu ai đó đánh cắp ổ cứng của bạn và bắt đầu quét, họ có thể lấy dữ liệu ngay cả khi bạn xóa tệp vì bản thân dữ liệu vẫn còn ở đó, mặc dù vị trí chuyển tiếp đến đó đã biến mất. Khi dữ liệu được mã hóa, bất kỳ thứ gì được lưu trữ sẽ không giống như những gì nó vốn có. Nó thường trông ngẫu nhiên, như thể sự phân mảnh đã tích tụ theo thời gian. Bạn cũng có thể lưu trữ dữ liệu và hiển thị nó dưới dạng một loại tệp khác. Ví dụ: các tệp hình ảnh và tệp nhạc rất tốt cho việc này, vì chúng có thể khá lớn mà không gây nghi ngờ. Tất cả những điều này được thực hiện bằng cách sử dụng các thuật toán toán học, lấy một số loại đầu vào và chuyển nó thành một loại đầu ra khác, rất cụ thể. Để biết thêm thông tin về cách hoạt động của mã hóa, hãy xem Giải thích HTG: Mã hóa là gì và Nó hoạt động như thế nào?
Thuật toán là công cụ toán học cung cấp nhiều mục đích sử dụng trong khoa học máy tính. Chúng hoạt động để cung cấp một đường dẫn giữa điểm bắt đầu và điểm kết thúc một cách nhất quán và cung cấp các hướng dẫn để đi theo nó. Biết nhiều hơn những gì chúng tôi đã đánh dấu? Chia sẻ giải thích của bạn trong các ý kiến!
