dev1_account1

T&igrave;m kiếm nhị ph&acirc;n l&agrave; một trong những kiến thức đầu ti&ecirc;n bạn học trong c&aacute;c kh&oacute;a học về&nbsp; khoa học m&aacute;y t&iacute;nh. Đ&acirc;y l&agrave; v&iacute; dụ về c&aacute;ch sử dụng lối tư duy linh hoạt để l&agrave;m mọi thứ hiệu quả hơn theo cấp số nh&acirc;n.
T&igrave;m kiếm nhị ph&acirc;n lấy đầu v&agrave;o l&agrave; một mảng được sắp xếp v&agrave; li&ecirc;n tục chia c&aacute;c khoảng t&igrave;m kiếm th&agrave;nh một nửa v&agrave; so s&aacute;nh phần tử cần t&igrave;m với mỗi nửa khoảng, cho đến khi t&igrave;m thấy phần tử.

Tìm kiếm nhị phân

Thuật to&aacute;n sắp xếp l&agrave; một trong những c&ocirc;ng cụ cơ bản nhất m&agrave; lập tr&igrave;nh vi&ecirc;n cần phải biết. Bubble sort, Insertion sort, Selection sort l&agrave; những thuật to&aacute;n đầu ti&ecirc;n m&agrave; bạn sẽ học. Bạn sẽ kh&ocirc;ng sử dụng thuật to&aacute;n n&agrave;y trong c&aacute;c b&agrave;i to&aacute;n cần tối ưu ho&aacute; tốc độ xử l&yacute;, tuy nhi&ecirc;n kiến thức li&ecirc;n quan sẽ được sử dụng cho c&aacute; b&agrave;i to&aacute;n thao t&aacute;c v&agrave; duyệt mảng.

Bubble sort, Insertion sort, Selection sort

Tương tự như #2, thuật to&aacute;n sắp xếp chủ yếu gi&uacute;p bạn l&agrave;m quen với mảng, nhưng Quicksort v&agrave; Mergesort đ&atilde; ph&aacute;t triển th&agrave;nh t&iacute;nh năng quan trọng trong ứng dụng thực tế. Hai thuật to&aacute;n n&agrave;y l&agrave; yếu tố quan trọng gi&uacute;p bạn trở th&agrave;nh lập tr&igrave;nh vi&ecirc;n hiệu quả hơn.

Quicksort và Mergesort

M&atilde; h&oacute;a Huffman l&agrave; nền tảng của kỹ thuật n&eacute;n dữ liệu hiện nay. N&oacute; hoạt động bằng c&aacute;ch x&aacute;c định số lần xuất hiện của c&aacute;c k&yacute; tự trong văn bản v&agrave; sắp xếp th&agrave;nh c&acirc;y dựa tr&ecirc;n tần suất.
<img style="width: 700px;" src="https://tek4.vn/public_files/da19e367-8110-4ec8-bea0-52199a522157" alt="Huffman Coding" />
M&atilde; h&oacute;a Huffman gi&uacute;p bạn l&agrave;m quen với biểu diễn dữ liệu v&agrave; duyệt c&acirc;y, đ&acirc;y l&agrave; hai trong số những b&agrave;i to&aacute;n quan trọng nhất m&agrave; c&aacute;c nh&agrave; khoa học m&aacute;y t&iacute;nh phải giải quyết.

Mã hóa Huffman

C&acirc;y nhị ph&acirc;n l&agrave; yếu tố cốt l&otilde;i của rất nhiều thuật to&aacute;n v&agrave; phần mềm. Do đ&oacute;, kiến thức cơ bản về duyệt c&acirc;y rất quan trọng đối với lập tr&igrave;nh vi&ecirc;n.
T&igrave;m kiếm theo chiều rộng duyệt qua c&acirc;y từ n&uacute;t bắt đầu đến khi t&igrave;m thấy n&uacute;t kết th&uacute;c. V&igrave; giải thuật t&igrave;m kiếm theo từng cấp độ n&ecirc;n chắc chắn sẽ t&igrave;m ra n&uacute;t đ&iacute;ch.
<img style="width: 700px;" src="https://tek4.vn/public_files/d81f8c29-bbe6-4653-a3e9-fe5a9859df28" alt="Breadth First Search" />

Giải thuật tìm kiếm theo chiều rộng (Breadth First Search)

Tiếp tục với duyệt qua c&acirc;y, T&igrave;m kiếm theo chiều s&acirc;u l&agrave; một c&aacute;ch kh&aacute;c để t&igrave;m phần tử trong c&acirc;y. Thay v&igrave; tiến h&agrave;nh theo cấp độ như BFS, giải thuật n&agrave;y đi s&acirc;u v&agrave;o từng nh&aacute;nh c&acirc;y.
<img style="width: 700px;" src="https://tek4.vn/public_files/46b4e476-c26b-4cc9-bd84-a55fd4806e57" alt="Depth First Search" />
Trong trường hợp c&acirc;y kh&ocirc;ng c&oacute; nh&aacute;nh mở rộng v&ocirc; hạn, DFS sẽ lu&ocirc;n hoạt động. C&aacute;ch triển khai hai thuật to&aacute;n t&igrave;m kiếm n&agrave;y kh&aacute; đơn giản, tuy nhi&ecirc;n điều quan trọng l&agrave; biết khi n&agrave;o th&igrave; n&ecirc;n sử dụng thuật to&aacute;n n&agrave;o. Nhiều phần mềm hiện nay c&oacute; khả năng ph&acirc;n t&iacute;ch cấu tr&uacute;c th&ocirc;ng tin v&agrave; chọn thuật to&aacute;n tối ưu h&oacute;a cho cấu tr&uacute;c đ&oacute;.

Giải thuật tìm kiếm theo chiều sâu (Depth First Search)

Kh&ocirc;ng phải lĩnh vực kỹ thuật n&agrave;o cũng y&ecirc;u cầu sử dụng thuật to&aacute;n Gradient Descent. Tuy nhi&ecirc;n, nếu bạn đang l&agrave;m bất cứ thứ g&igrave; li&ecirc;n quan đến hồi quy hoặc học m&aacute;y, c&ocirc;ng việc sẽ chủ yếu xoay quanh thuật to&aacute;n Gradient Descent.
<img style="width: 700px;" src="https://tek4.vn/public_files/ce4432da-5992-4388-8206-8082eb5612ff" alt="Gradient Descent" />
Gradient Descent l&agrave; một thuật to&aacute;n tối ưu h&oacute;a lặp sử dụng c&aacute;c ph&eacute;p to&aacute;n. Trong hồi quy v&agrave; học m&aacute;y, đ&oacute; l&agrave; t&igrave;m c&aacute;c gi&aacute; trị gi&uacute;p giảm thiểu lỗi trong thuật to&aacute;n dự đo&aacute;n. Gradient Descent chủ yếu li&ecirc;n quan đến to&aacute;n học nhưng nếu bạn đang l&agrave;m việc với dữ liệu v&agrave; dự đo&aacute;n th&igrave; những hiểu biết về c&aacute;ch thức hoạt động của gradient descent l&agrave; rất quan trọng.

Gradient Descent

Một b&agrave;i to&aacute;n quan trọng kh&aacute;c m&agrave; lập tr&igrave;nh vi&ecirc;n phải giải quyết l&agrave; t&igrave;m đường đi ngắn nhất. Đồ thị l&agrave; một dạng biểu diễn linh hoạt để thể hiện mối li&ecirc;n kết giữa c&aacute;c đối tượng.
<img style="width: 700px;" src="https://tek4.vn/public_files/448599ce-502f-4dbc-bce5-1821bbb2ea64" alt="Dijkstra&rsquo;s Algorithm" />
Thuật to&aacute;n Dijkstra được sử dụng để t&igrave;m khoảng c&aacute;ch ngắn nhất giữa hai n&uacute;t trong đồ thị. Đ&acirc;y l&agrave; nền tảng để giải quyết nhiều b&agrave;i to&aacute;n t&igrave;m đường v&agrave; được sử dụng trong mọi lĩnh vực từ tr&iacute; tuệ nh&acirc;n tạo đến thiết kế tr&ograve; chơi.

Thuật toán Dijkstra

Trao đổi kh&oacute;a Diffie-Hellman gi&uacute;p l&yacute; giải c&aacute;ch thức hoạt động của tiền m&atilde; h&oacute;a. Cụ thể, thuật to&aacute;n n&agrave;y kết hợp c&aacute;c kh&oacute;a public v&agrave; kh&oacute;a private (c&aacute;c số d&agrave;i) để m&atilde; h&oacute;a th&ocirc;ng tin khi dữ liệu được trao đổi giữa c&aacute;c b&ecirc;n kh&aacute;c nhau.
<img style="width: 700px;" src="https://tek4.vn/public_files/99e4503c-4a70-4f3b-b2c7-03ca2fb592a2" alt="Diffie-Helllman Key Exchange" />
Ngay cả khi bạn kh&ocirc;ng l&agrave;m việc trong lĩnh vực an ninh mạng th&igrave; những hiểu biết về m&atilde; h&oacute;a v&agrave; giao tiếp an to&agrave;n cũng v&ocirc; c&ugrave;ng quan trọng đối với c&ocirc;ng việc lập tr&igrave;nh. Ngo&agrave;i ra, mặc d&ugrave; Diffie-Helman kh&ocirc;ng phải l&agrave; thuật to&aacute;n tốt nhất, nhưng n&oacute; giống với nhiều phương thức giao tiếp được m&atilde; h&oacute;a kh&aacute;c v&agrave; điểm cộng l&agrave; c&aacute;ch triển khai rất đơn giản.

Trao đổi khóa Diffie-Hellman

9 thuật to&aacute;n tr&ecirc;n cung cấp c&aacute;ch giải quyết c&aacute;c b&agrave;i to&aacute;n điển h&igrave;nh nhất. Tuy nhi&ecirc;n tr&ecirc;n thực tế, khi l&agrave;m việc bạn sẽ thường bắt gặp c&aacute;c vấn đề mới lạ. Thay v&igrave; cố gắng ghi nhớ tất cả thuật to&aacute;n, tốt hơn hết l&agrave; bạn h&atilde;y ph&aacute;t triển c&aacute;c kỹ năng giải quyết vấn đề theo lối tư duy thuật to&aacute;n.
Một số trang web thực h&agrave;nh:
<ul style="text-align: justify;">
<li style="font-weight: 400;" aria-level="1"><a href="https://leetcode.com/">https://leetcode.com/</a>&nbsp;</li>
<li style="font-weight: 400;" aria-level="1"><a href="https://projecteuler.net/">https://projecteuler.net/</a> (Chủ yếu li&ecirc;n quan đến to&aacute;n học)</li>
<li style="font-weight: 400;" aria-level="1"><a href="https://www.hackerrank.com/">https://www.hackerrank.com/</a>&nbsp;</li>
</ul>
Đ&acirc;y l&agrave; những trang web cung cấp c&aacute;c b&agrave;i to&aacute;n kh&oacute; chưa c&oacute; lời giải sẽ gi&uacute;p bạn trau dồi kỹ năng.
Lời kết
Cần phải nhắc lại rằng, đừng cố ghi nhớ c&aacute;c thuật to&aacute;n v&agrave; nghĩ rằng như thế l&agrave; đủ để th&agrave;nh thạo tất cả. Kỹ thuật phần mềm tập trung v&agrave;o khả năng hiểu v&agrave; ph&acirc;n t&iacute;ch vấn đề, sau đ&oacute; đưa ra giải ph&aacute;p. Hiểu thuật to&aacute;n l&agrave; một chuyện nhưng biết c&aacute;ch triển khai ch&iacute;nh x&aacute;c mới l&agrave; điều ta cần. Qua việc triển khai bạn sẽ học được c&aacute;ch tiếp cận vấn đề.
Bạn c&ograve;n muốn bổ sung thuật to&aacute;n n&agrave;o nữa kh&ocirc;ng? H&atilde;y b&igrave;nh luận b&ecirc;n dưới nh&eacute;!

10 thuật toán quan trọng cần phải ghi nhớ

Top bài viết nổi bật: