Tầm quan trọng của việc hiểu biết thuật toán
December 25, 2024Theo cuốn Giới thiệu về thuật toán (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein): “Thuật toán là bất kỳ quy trình tính toán rõ ràng nào có đầu vào (input) là giá trị hoặc tập hợp các giá trị, và đầu ra (output) là giá trị hoặc tập hợp các giá trị.”
Có rất nhiều phiên bản đời thực của Thuật Toán: Một kịch bản, lời thoại Phim chi tiết có input là các diễn viên, trường quay, nhà sản xuất => output là bộ phim. Hoặc, một dự luật kinh tế của một quốc gia với đầu vào là nhân lực, vật lực, mối quan hệ, tài nguyên thiên nhiên => output là lương thực và công ăn việc làm cho người dân của nước đó trong 50 năm. Gần gũi hơn, một tấm bản đồ hướng dẫn rõ ràng đường đi để hoàn thành một cuộc du hành trong thành phố cũng là một phiên bản đời thực của Thuật Toán.
Ngay cả một phép tính cộng hai số với nhau cũng có thể gọi là một thuật toán, cho dù nói như vậy là hơi cẩu thả.
Một số thuật toán, như thuật toán sắp xếp từ lớn đến nhỏ, nó rất trực quan để đưa vào tư duy logic và kĩ năng giải quyết vấn đề của chúng ta. Nhưng có một vài thuật toán sẽ phức tạp hơn, chúng ta vẫn cần nghiên cứu để chúng làm các khối xây dựng giải quyết vấn đề logic hiệu quả hơn trong tương lai.
Trong tự nhiên, hiếm khi chúng ta thấy một hình tròn hay một hình vuông tuyệt đối để mà áp dụng công thức tính diện tích cho chúng (gì nhỉ, bình phương và số Pi phải không). Nhưng các kĩ sư rất hay phải tính diện tích các hồ nước hoặc các mảnh đất quá lớn và méo mó. Bằng quan sát và chia nhỏ chúng chúng thành những hình dạng tương tự như các hình tuyệt đối, một kĩ sư sẽ dễ dàng tính được diện tích của một cái hồ hay mảnh đất từ những công thức mà họ đã biết. Họ đã lập trình, bấm máy tính hay giấy bút viết để làm, không biết, chỉ chắc chắn là họ làm được nhờ có được công thức – chính là một phiên bản của Thuật Toán.
Ví dụ này minh họa cho việc các Thuật Toán (dù là phức tạp hay không) đóng vai trò là các khối tư duy hữu ích để giải quyết các vấn đề logic chúng ta gặp trong tương lai hiệu quả hơn.
Vậy còn ngôn ngữ lập trình, ví dụ như Java, nó có liên quan gì?
Một đoạn mã (code), ví dụ như Java, để tìm ra những sản phẩm hay những tin tức đang được quan tâm nhất trên Internet chẳng hạn, được gọi là một triển khai của một thuật toán cụ thể. Ngôn ngữ lập trình có ý nghĩa là công cụ triển khai các thuật toán để nó hoạt động trên máy tính. Chúng ta chọn Java cho khóa học này vì “công cụ” này tiện dụng hơn cho người tạo khóa học, chứ không phải vì Java có gì đó nổi trội so với ngôn ngữ khác.
Chúng ta cần trở thành một nhà khoa học máy tính chứ không chỉ là một Coder. Vì vậy điều quan trọng là phải hiểu tất cả các loại thuật toán này để ta có thể sử dụng chúng đúng cách.
Nếu bạn đang làm việc trên một phần mềm quan trọng, bạn có thể sẽ cần phải ước tính tốc độ của nó. Một ước tính sẽ rất kém chính xác nếu không có sự hiểu biết về phân tích thời gian chạy. Hơn nữa, bạn cần hiểu chi tiết về các thuật toán có liên quan để bạn có thể dự đoán liệu có trường hợp đặc biệt nào mà phần mềm của bạn có thể hoạt động quá chậm không.
Bạn cũng hay gặp phải vấn đề chưa được nghiên cứu trước đây. Trong những trường hợp này, bạn phải đưa ra một thuật toán mới, hoặc áp dụng một thuật toán cũ theo một cách mới. Bạn càng biết nhiều về các thuật toán thì bạn càng có nhiều cơ hội tìm ra một cách tốt để giải quyết vấn đề.
Còn lại, trong hầu hết trường hợp, một vấn đề mới là kết hợp của nhiều vấn đề cũ chồng chéo lên nhau, khi đó bạn sẽ cần có một sự hiểu biết cơ bản về các vấn đề cũ. Hiểu biết rộng về thuật toán sẽ hữu dụng vào lúc này, bạn sẽ không cần quá nhiều nỗ lực để giải quyết.
Ví dụ về việc này:
Một lớp học nhận được M nhiệm vụ, mỗi nhiệm vụ dành cho một học sinh và một học sinh chỉ được làm tối đa 1 nhiệm vụ, khi thực hiện xong nhà trường sẽ chấm điểm mức độ hoàn thành từ 1-100.
Lớp chỉ có N học sinh, bạn là giáo viên chủ nhiệm và bạn hiểu rõ học sinh của mình. Với mỗi nhiệm vụ, bạn biết rõ từng đứa sẽ làm nó tốt đến đâu (theo thang điểm 1 – 100). Giờ thì bạn cần giao nhiệm vụ sao cho sau khi hoàn thành thì lớp sẽ nhận được số điểm tối đa.
Có thể bạn sẽ chọn lần lượt những cặp (nhiệm vụ, học sinh) mang lại điểm số tiềm năng nhất cho đến khi không còn học sinh hay nhiệm vụ để giao thêm. Phương pháp này sẽ cho một kết quả khá tốt, nhưng bạn sẽ không tự tin.
Hãy xem thử nếu M = 2 và N = 2 và:
Điểm (học sinh 1, nhiệm vụ 1) = 80;
Điểm (học sinh 1, nhiệm vụ 2) = 40;
Điểm (học sinh 2, nhiệm vụ 1) = 60;
Điểm (học sinh 2, nhiệm vụ 2) = 10;
Nếu theo cách trên, bạn sẽ chọn ra cặp (học sinh 1, nhiệm vụ 1) trước, và cặp (học sinh 2, nhiệm vụ 2) sau => Lớp bạn sẽ đạt 90 điểm. Nhưng rõ ràng kết quả (học sinh 1, nhiệm vụ 2) + (học sinh 2, nhiệm vụ 1) = 100 lại tốt hơn.
Bạn làm sao biết được sẽ có những tình huống nào nữa, nếu số học sinh và nhiệm vụ có thể lên tới con số 100?
Trong trường hợp này, hóa ra có một thuật toán được gọi là “Cặp ghép Cực đại” được áp dụng trực tiếp cho vấn đề này. Mặc dù thoạt nhìn qua thì thì tại mỗi lần ghép một đôi, việc chọn một bộ (học sinh, nhiệm vụ) đồng thời có điểm cao mà vẫn mang lại kết quả hoàn hảo khi chọn những bộ đôi tiếp theo dường như là không thể.
Nhưng có một số thuật toán, mà tại mỗi bước bạn được phép điều chỉnh các bước trước đó theo một nguyên tắc nhất định thì sẽ mang lại kết quả cuối cùng tốt nhất. Một trong số đó đã giải quyết tuyệt đối được vấn đề này, bạn chỉ có thể tìm ra nó thông qua kiến thức và hiểu biết về thuật toán có sẵn mới có thể phát hiện ra những nguyên tắc như vậy.
