Trang chủ

Dẫn dắt Tech Talk 20 vẫn là “cặp bài trùng” Hoàng Tuấn Anh Văn và Trần Lê Hoàng đến từ Trung tâm Công nghệ & Phân tích dữ liệu. Tuy nhiên, lần trở lại này, 2 speaker nói riêng và team Coding Skill đã ở một “cương vị” mới với thành tích xuất sắc sở hữu Tech Talk được yêu thích nhất năm 2023, được vinh danh tại Chương trình tri ân “Người gieo những hạt mầm” của VDS diễn ra vào dịp 20/11 vừa qua. Một lần nữa, chúc mừng các chàng trai! 

Tại Tech Talk 20, 2 speakers mang đến những vấn đề mới: cây khung nhỏ nhất và đường đi ngắn nhất. Bên cạnh đó, Tech Talk cũng giới thiệu những ứng dụng thực tế của các bài toán này trong lĩnh vực công nghệ thông tin nói chung và tại VDS nói riêng.

Như thường lệ, hai anh chàng công nghệ bắt đầu Tech Talk với lý thuyết của những thuật toán thuộc chủ đề này, mở đầu với việc giới thiệu cấu trúc dữ liệu dạng cây cũng như disjoint set union, là nền tảng để triển khai thuật toán tìm cây khung nhỏ nhất tiếp sau. Cây khung của đồ thị (spanning tree) là một tập hợp các cạnh của đồ thị thỏa mãn tập cạnh này không chứa chu trình và liên thông (từ một đỉnh bất kì có thể đi tới bất kỳ đỉnh nào khác theo mà chỉ dùng các cạnh trên cây khung). Trong đồ thị có trọng số, cây khung nhỏ nhất là cây khung có tổng trọng số các cạnh trong cây nhỏ nhất. Về cơ bản, cây khung nhỏ nhất được sử dụng để tìm đường kết nối tất cả các nút trong một đồ thị mà có tổng trọng số nhỏ nhất. Các ứng dụng phổ biến của cây khung là:

• Lập kế hoạch mạng dân sự
• Giao thức định tuyến mạng máy tính
• Cluster Analysis

Nhắc đến giải thuật duyệt đồ thị, có hai thuật toán cơ bản phần lớn dân CNTT đều biết: Depth-First Search (DFS) và Breadth-First Search (BFS). Về mặt ý nghĩa, cả 2 thuật toán đều thực hiện trên đồ thị không có trọng số. Trong đồ thị có trọng số, vấn đề sẽ khó hơn do phải duy trì thêm trọng số của từng cạnh, nó nảy sinh ra 1 bài toán, đó là làm sao để tìm được đường đi ngắn nhất giữa 2 đỉnh trong đồ thị có trọng số. Và 2 thuật toán là Dijkstra và Floyd–Warshall đã được giới thiệu trong Tech Talk 20 lần này để giải quyết vấn đề trên.

Sau phần lý thuyết khô khan, không khí Tech talk trở nên sôi động hơn hẳn khi các speakers đi sâu vào ứng dụng thực tế của các thuật toán. Phần bài luyện tập cuối buổi, tuy gặp khá nhiều khó khăn trong hướng giải quyết nhưng các học viên cũng đã vượt qua trong khuôn khổ 2 giờ của buổi đào tạo cùng với sự hỗ trợ của hai speakers.

Hoàng Tuấn Anh Văn chia sẻ: “Các bạn đã có nền tảng tốt từ các buổi Tech Talk về đồ thị trước đó nên tiếp cận bài toán này tương đối nhanh và thuận lợi. Lúc thực hành, mọi người có gặp đôi chút khó khăn nhưng team mình sẵn sàng hỗ trợ nên mọi bài toán đều đã được giải quyết. Cuối năm, bản thân speaker chúng mình cũng bận rộn nhưng cố gắng hoàn thành series này tốt nhất có thể, các bạn tham gia cũng rất cố gắng thu xếp thời gian để đồng hành cùng chúng mình. Mình rất cảm ơn vì điều này!”

Tech Talk đã truyền tải được các thuật toán để giải quyết bài toán tìm đường đi ngắn nhất và tìm cây khung nhỏ nhất, qua đó giúp những thành viên tham gia nâng cao được kiến thức và kỹ năng chuyên môn về chủ đề này, cũng như giới thiệu những ứng dụng thực tế của chúng như bài toán chỉ đường trên các ứng dụng bản đồ, bài toán tối ưu chi phí của một mạng máy tính. Đây sẽ là bước đệm để các học viên tiếp tục khám phá các thuật toán và nâng cao kĩ năng chuyên môn của mình để phục vụ cho mục tiêu sản xuất kinh doanh của VDS.

Tài liệu Tech Talk 20: Minimum Spanning Tree & Shortest Paths đã có mặt tại Tập san Tech Talk trên nền tảng Confluence: http://10.254.136.32:8090/x/pW24Ag