Thuật toán – một thuật ngữ nghe quen thuộc trong kỹ thuật, trong cuộc sống, đặc biệt là trong lĩnh vực công nghệ khoa học. Khái niệm thuật toán là gì? Thuật toán có tính chất, vai trò, phân loại ra sao? Những thông tin trong bài viết sau đây của trường THPT Ngô Thì Nhậm sẽ giúp bạn hiểu rõ hơn nhé!
Thuật toán là gì?
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.
Thuật toán thực ra cũng đơn giản, không phải cái gì đó phức tạp. Nó là những phương pháp, những cách mà người ta yêu cầu mình làm đúng theo những quy trình như vậy thì nó sẽ ra được kết quả tối ưu.
Phương pháp này có thể đến từ nhiều nguồn khác nhau, có thể là một nhà khoa học họ sáng chế ra, cũng có thể là một nhóm người nào đó hoặc kinh nghiệm truyền nhiều năm, khi mà mình áp dụng đúng quy cách như vậy thì mình sẽ có những kết quả tốt hơn là những cái gì đó mình tự làm.
Thuật toán khác gì với cách lập trình thông thường? Nếu không biết về thuật toán thì có thể lập trình được không?
Bạn không biết thuật toán, bạn vẫn có thể lập trình và cũng có thể lập trình giỏi, tuy nhiên nếu bạn biết thuật toán bạn sẽ có thêm những phương pháp hay hơn. Tôi ví dụ thuật toán đơn giản như vậy, tôi cho bạn dãy số, và tôi yêu cầu bạn hãy tìm một con số mà tôi đưa có nằm trong dãy số đó không? Nếu như bạn không học thuật toán thì rất đơn giản, bạn cứ so sánh mỗi số một lần miễn sao bạn tìm được con số có nằm trong dãy số này hay không. Còn người khi học thuật toán, họ sẽ nghĩ khác, thứ nhất họ sẽ nghĩ những con số mà người ta đưa ra liệu nó có lớn hay không, tại vì nếu như người ta đưa lớn quá sẽ gây hiện tượng tràn số và nếu như mình phải làm thêm thao tác cộng, trừ, nhân, chia.
Số lượng người ta đưa ra bao nhiêu cũng ảnh hưởng đến việc sử dụng thuật toán, ví dụ người ta đưa ra 10 số, 20 số thì làm dễ, còn người ta đưa 1 tỷ số hoặc 10 tỷ số thì việc tìm kiếm đó nó rất không khả thi nếu mình tìm bình thường, như vậy thì mình phải áp dụng thêm thuật toán vào, bằng cách mình có thể sắp xếp trước những con số đó lại và khi mình sắp xếp như vậy thì mình sẽ tốn thời gian cho việc sắp xếp đó nhưng sau đó mình tìm kiếm rất là nhanh. Cuối cùng thời gian tìm kiếm rất là nhanh, dù là 1 tỷ số hay 10 tỷ số thì tìm kiếm trong vòng 1s cũng ra kết quả được. Còn nếu mình không áp dụng thuật toán, mình cứ làm hoài, cứ so sánh hoài, rồi khi người ta tăng lên thì thời gian chạy rất là lâu.
Tại sao cần dùng thuật toán?
Lập trình chính là để yêu cầu, chỉ thị máy thực hiện, giải quyết 1 công việc, bài toán cụ thể nào đó của cuộc sống. Mỗi bài toán thực tế sẽ có cách giải quyết khác nhau. Am hiểu và sử dụng đúng thuật toán, sẽ giúp bạn giải quyết một cách dễ dàng, cùng với độ chính xác cao trong thời gian ngắn nhất. Bỏ qua thuật toán sắp xếp các số trong dãy số nguyên hay thuật toán tìm số nguyên tố đi nhé, bài đó chỉ dùng để học và minh hoạ về thuật toán thôi. Ở đây, mình muốn giới thiệu với các bạn những thuật toán có tính ứng dụng khá lớn trong các sản phẩm/hệ thống phần mềm hiện tại nhé:
- Đầu tiên là thuật toán tìm đường đi ngắn nhất. Đại khái cho bạn một danh sách các đường đi giữa các địa điểm, hãy tìm đường đi ngắn nhất (về khoảng cách) hoặc chi phí tối thiểu khi đi từ điểm X đến điểm Y. Bạn biết thuật toán này dùng ở đâu rồi chứ? Hiện tại tôi nghĩ, bạn có thể sẽ biết nó xuất hiện trong các phần mềm chỉ đường và ứng dụng liên quan tới ngành giao thông vận tải (ví dụ google map, grab, uber, giao hàng nhanh, ….), nhưng bạn có biết nó còn dùng ở đâu nữa không? Xin nói với các bạn rằng, trong các hệ thống mạng, viễn thông người ta cũng dùng thuật toán này để định hướng đường truyền và tín hiệu. Cuộc điện thoại từ 1 người ở thành phố Hà Nội gọi cho 1 người ở thành phố Hồ Chí Minh đi qua các cột thu phát sóng, dữ liệu internet từ máy tính của bạn đi tới máy chủ của nhà cung cấp mạng cũng phải sử dụng thuật toán này để đạt được tốc độ tối đa.
- Tiếp theo, một thuật toán khá nổi tiếng khác là thuật toán tìm kiếm. Bạn có thể nhìn thấy nó ở khá nhiều sản phẩm phần mềm hiện tại, điển hình như Google. Bạn có thể nghĩ rằng, tìm kiếm khá là đơn giản, khi bạn lần lượt soi vào từng ô, từng dòng dữ liệu xem có thứ mà mình tìm kiếm hay không? Nhưng hãy đặt địa vị, bạn có hàng tỷ tỷ món đồ dùng được vứt lộn xộn trong 1 căn nhà, bạn sẽ mất bao nhiêu lâu để tìm được món đồ mà bạn mong muốn. Hãy biết chắc chắn rằng, việc Google trả ra được kết quả mà bạn yêu cầu tìm kiếm trong vòng 1 vài giây là vô cùng khó. Điều ấy yêu cầu 1 thuật toán cực mạnh, và vẫn liên tục cần cải tiến cho đến ngày hôm nay.
- Các thuật toán mã hoá được sử dụng để mã hoá thông tin, được sử dụng nhiều trong việc truyền nhận và lưu trữ giữ liệu, giúp bảo vệ thông tin cá nhân và tổ chức khỏi các cuộc tấn công hay khai thác.
Bỏ qua những thuật toán cao siêu như bên trên vì bạn ít có cơ hội làm những sản phẩm như vậy, trong quá trình làm phần mềm, bạn cũng có thể sẽ gặp các bài toán hay vấn đề nhỏ yêu cầu bạn phải chọn đúng giải thuật để giải, ví dụ như:
- Hãy tìm kiếm 1 cái máy tính có giá từ X->Y, đáp ứng tối đa các tiêu chí của người dùng chỉ trong 1 cái click chuột
- Hãy đưa ra các bài viết hoặc sản phẩm mà người dùng quan tâm dựa trên lịch sử truy cập của họ
Khi bạn lập trình đủ lâu và đủ nhiều, tôi nghĩ chắc chắn bạn sẽ gặp nhiều bài toán khó hơn tôi. Trong quá trình phát triển sản phẩm CodeLearn, tôi và những đồng đội cũng đôi lúc phải giải quyết những bài toán kiểu như thế này:
- Hãy tính toán và sắp xếp thứ hạng của người dùng dựa trên lịch sử học và làm bài
- Đếm số lượng truy cập của người dùng trong 1 khoảng thời gian để dự đoán tấn công
- Đưa ra gợi ý các bài tập mà người dùng nên làm dựa vào lịch sử truy cập và thao tác của họ trên hệ thống
Tất nhiên những bài toán trên là không khó với tập dữ liệu và người dùng nhỏ. Nhưng hãy thử tưởng tượng, khi hệ thống có hàng nghìn hàng vạn người cùng truy cập và bạn phải trả về kết quả là cực kì nhanh, bạn sẽ làm như thế nào để đảm bảo điều đó? Thực tế đã trả lời chúng tôi rằng, khi chọn đúng giải thuật, tốc độ xử lí có thể tăng lên từ hàng chục tới hàng trăm lần. Và tôi nghĩ rằng, một ngày nào đó, chúng tôi vẫn sẽ phải nâng cấp thuật toán để giải quyết bài toán với lượng dữ liệu và người dùng lớn hơn.
Phân loại thuật toán
Dựa vào nhiều tiêu chí đa dạng khác nhau, thuật toán được phân chia thành nhiều loại, nhiều yếu tố, cụ thể như sau:
Phân loại theo tính năng
Đối với việc phân chia dựa vào tính năng, thuật toán được phân chia thành các loại cơ bản sau:
- Thuật toán tìm kiếm: là loại thuật toán áp dụng để tìm kiếm các dữ liệu, thông tin trong 1 tập hợp và bao gồm các phân tử khác nhau.
- Thuật toán sắp xếp được biết đến để sắp xếp các thứ tự trong từng phân tử của 1 tập hợp theo cách khoa học, đáp ứng được yêu cầu logic.
- Thuật toán đồ thị là dạng thuật toán sử dụng để xử lý các vấn đề liên quan đến bài có sử dụng đồ thị.
Phân loại theo cách thức thực hiện
Cách phân loại thứ hai đó là theo cách thức thực hiện. Cách phân loại này chia thuật toán thành 2 loại chính đó là:
- Thuật toán chia để trị: nói cách dễ hiểu hơn, nó sẽ chia bài toán lớn thành các phần nhỏ, chia vấn đề lớn thành những vấn đề nhỏ để xử lý và giải quyết dần.
- Thuật toán tham lam: Đây là dạng thuật toán thay đổi trạng thái của bài toán thông qua những hành động cụ thể. Nó giúp người giải quyết có thể tiếp cận vấn đè từ từ để tìm ra hướng giải quyết nhanh chóng và hiệu quả hơn.
Đó là những loại thuật toán cơ bản được chia theo từng tiêu chí riêng mà chúng ta có thể tham khảo.
Tính chất của thuật toán
Thuật toán có những tính chất nào? Đâu là đặc trưng tiêu biểu cơ bản của thuật toán? Thuật toán có 5 tính chất cơ bản sau đây:
Tính chính xác
Tính chính xác là tính chất tiêu biểu, đầu tiên khi nhắc đến thuật toán. Nó là một trong những yếu tố quan trọng hàng đầu đảm bảo kết quả cũng như thao tác thực hiện chính xác, hiệu quả và khả thi hơn trong các bài toán và công thức.
Tính rõ ràng minh bạch
Tính chất thứ 2 của thuật toán là sự rõ ràng, minh bạch. Tính chất này được thực hiện trên nguyên tắc lệnh. Các câu lệnh trong thuật toán đưa ra rõ ràng, dễ hiểu và được sắp xếp theo trình tự nhất định.
Tính khách quan
Tính khách quan là đặc trưng của thuật toán, bởi nó được thực hiện bởi hệ thống máy tính hay con người cũng đều phải đưa ra kết quả giống nhau, duy nhất, chỉ 1 kết quả. Kết quả sẽ được đưa ra bởi 2 phương pháp này không tương đồng thì cần xem xét lại bởi điều đó chứng tỏ thuật toán sai hoặc vô lý.
Tính phổ dụng
Tính phổ dụng cũng là đặc trưng tiêu biểu của thuật toán, nó đòi hỏi tính ứng dụng cao. Nó không chỉ dùng để giải quyết duy nhất 1 bài toán mà còn có khả năng giải quyết được những bài toán tương tự.
Tính kết thúc
Thuật toán nhất định không thể thiếu tính kết thúc. Bởi nó là tập hợp hữu hạn vì thế, luôn có điểm kết thúc, điểm kết thúc chính là kết quả đã tìm ra phù hợp.
Các thuật toán được sử dụng ở đâu trong cuộc sống thực?
Từ ‘thuật toán‘ thoạt nghe có vẻ đáng sợ, nhưng nó thực sự là một khái niệm đơn giản. Mọi người sử dụng thuật toán mọi lúc trong thói quen hàng ngày của họ để hoàn thành công việc, chẳng hạn như pha cà phê hoặc soạn thảo văn bản.
Các thuật toán nằm ở trung tâm của máy tính. Nếu quan sát môi trường xung quanh, chúng ta có thể tìm thấy một số thuật toán đang hoạt động để giải quyết các vấn đề trong cuộc sống hàng ngày của chúng ta: Mạng truyền thông xã hội, ứng dụng GPS, bộ máy tìm kiếm của Google, nền tảng thương mại điện tử, hệ thống đề xuất của YouTube hoặc Netflix, v.v. các ứng dụng được cung cấp bởi thuật toán.
Ngày nay, các thuật toán được sử dụng hàng tỷ lần mỗi ngày cho nhiều nhiệm vụ khác nhau. Dưới đây là một số cách thuật toán khác nhau được sử dụng.
- Thuật toán giúp điều khiển đèn giao thông.
- Máy tính sử dụng các thuật toán để chuyển đổi dữ liệu (ví dụ: chuyển đổi số thập phân thành nhị phân ).
- Tìm kiếm của Google sử dụng thuật toán Pagerank, RankBrain, … để sắp xếp các kết quả được tìm kiếm.
- Mã hóa dữ liệu và giải mã thông tin và giữ an toàn cho dữ liệu là một thuật toán.
- GPS sử dụng các thuật toán tìm kiếm đồ thị để tìm đường tốt nhất đến một điểm đến.
- Điện thoại thông minh, Wi Fi và giao tiếp không dây sử dụng các thuật toán để giao tiếp.
- Phát hiện thư rác e-mail sử dụng các thuật toán để lọc ra những e-mail xấu.
- Nén dữ liệu để nhận thông tin nhanh hơn (ví dụ: video của YouTube) sử dụng các thuật toán.
Thuật toán đầu tiên ra đời khi nào?
Bởi vì một công thức nấu ăn có thể được coi là một thuật toán, thuật toán đầu tiên có thể quay ngược lại với ngôn ngữ viết. Tuy nhiên, nhiều người nhận thấy thuật toán Euclid tìm ước số chung lớn nhất là thuật toán đầu tiên. Thuật toán này được mô tả lần đầu tiên vào năm 300 trước Công nguyên
Ada Lovelace được ghi nhận là lập trình viên máy tính đầu tiên và là người đầu tiên phát triển thuật toán cho máy.
Biểu diễn thuật toán như thế nào?
Lưu đồ (Flowchart) là một biểu diễn đồ họa của một thuật toán. Các lập trình viên thường sử dụng lưu đồ như một công cụ lập kế hoạch chương trình để giải quyết một vấn đề.
Lưu đồ sử dụng các ký hiệu được kết nối giữa chúng để chỉ ra luồng thông tin và quá trình xử lý. Quá trình vẽ một lưu đồ cho một thuật toán được gọi là “lưu lượng”.
25 thuật toán hàng đầu mà mọi lập trình viên nên biết
Kiến thức tốt về các thuật toán tiêu chuẩn cũng quan trọng không kém việc lựa chọn cấu trúc dữ liệu phù hợp. Sau đây là danh sách 25 thuật toán hàng đầu mà mọi lập trình viên và sinh viên khoa học máy tính nên biết.
- Thuật toán tìm kiếm nhị phân
- Thuật toán tìm kiếm đầu tiên theo chiều rộng (BFS)
- Thuật toán tìm kiếm đầu tiên theo chiều sâu (DFS)
- Thuật toán Sắp xếp Hợp nhất
- Thuật toán Quicksort
- Thuật toán Kruskal
- Thuật toán Floyd Warshall
- Thuật toán Dijkstra
- Thuật toán Bellman Ford
- Thuật toán Kadane
- Thuật toán Lee
- Thuật toán lấp đầy lũ
- Thuật toán phát hiện chu kỳ của Floyd
- Thuật toán tìm Union
- Thuật toán sắp xếp tôpô
- Thuật toán KMP
- Thuật toán sắp xếp chèn
- Thuật toán sắp xếp lựa chọn
- Thuật toán sắp xếp đếm
- Thuật toán sắp xếp đống
- Thuật toán Kahn’s Topological Sort
- Thuật toán nén mã hóa Huffman
- Thuật toán chọn nhanh
- Thuật toán bỏ phiếu cho đa số Boyer – Moore
- Thuật toán Euclid
Video về thuật toán là gì?
Kết luận
Hy vọng bài toán trên đây giúp bạn hiểu thuật toán là gì cùng với những thông tin liên quan, để xác định mục tiêu cho bản thân. Chúc các bạn thành công!
Đăng bởi: THPT Ngô Thì Nhậm
Chuyên mục: Tổng hợp
