[Seminar] SINH HOẠT KHOA HỌC: “CÂY ĐỒ THỊ VÀ ỨNG DỤNG”

Vào 15h30 chiều thứ Sáu ngày 29 tháng 11 năm 2024, Khoa Khoa học Cơ sở tổ chức sinh hoạt khoa học với chủ đề: “Cây đồ thị và ứng dụng”.

Người trình bày: ThS. Nguyễn Mai Quyên, GV Khoa Khoa học Cơ sở, ĐHKTQD.

Thành phần tham dự: Toàn thể GV Khoa Khoa học Cơ sở và các giảng viên quan tâm

Người trình bày đã trình bày các nội dung:

• Cây đồ thị, các thuật ngữ về cây đồ thị
• Cây và mô hình
• Một số loại cây và ứng dụng

Một số ý kiến trao đổi:

• Khái niệm cây trong lý thuyết đồ thị và được ứng dụng rộng rãi trong việc giải quyết các bài toán tối ưu, tìm kiếm, phân loại, mô hình hóa mối quan hệ, và tổ chức dữ liệu. 
• Cây là một trong những cấu trúc dữ liệu cơ bản trong lập trình, đặc biệt là trong các thuật toán và hệ thống quản lý dữ liệu phức tạp. Một số ứng dụng cụ thể của cây trong cấu trúc dữ liệu: Cây nhị phân; Cây quyết định; Cây tìm kiếm nhị phân.
• Cây được sử dụng trong nhiều thuật toán tìm kiếm và duyệt đồ thị. Duyệt cây theo chiều sâu là thuật toán tìm kiếm trong cây, nơi thuật toán đi từ một đỉnh, lần lượt duyệt hết các đỉnh con trước khi quay lại các đỉnh trước đó. Thuật toán này thường được sử dụng trong các bài toán liên quan đến đồ thị như tìm kiếm, phát hiện chu trình, hoặc tìm đường đi. Duyệt cây theo chiều rộng (BFS – Breadth First Search) là thuật toán tìm kiếm trong đó thuật toán khám phá tất cả các đỉnh ở một mức độ trước khi đi vào các đỉnh ở mức độ tiếp theo. BFS có thể được sử dụng để tìm đường đi ngắn nhất trong các đồ thị không có trọng số.
• Trong lý thuyết mạng, cây thường được sử dụng để mô hình hóa các kết nối mạng, đặc biệt là trong các tình huống có sự phân bố tài nguyên tối ưu. Cây phân phối (Spanning Tree) là cây bao gồm tất cả các đỉnh của đồ thị mà không có chu trình. Mạng LAN, mạng kết nối các máy tính có thể được tối ưu hóa sử dụng cây phân phối để giảm chi phí và đảm bảo tính liên thông giữa các máy tính. Thuật toán cây bao trùm nhỏ nhất (Minimum Spanning Tree) tìm cây con trong một đồ thị có trọng số sao cho tổng trọng số của các cạnh là nhỏ nhất, giúp tối ưu hóa việc xây dựng mạng, kết nối các điểm trong mạng mà không có chu trình. Thuật toán Prim và Kruskal là các thuật toán phổ biến để tìm cây bao trùm nhỏ nhất.
• Cây đồ thị cũng có ứng dụng trong các bài toán mô hình hóa các mối quan hệ trong mạng xã hội (Facebook, Twitter), hệ thống tài nguyên, hoặc cấu trúc cây phân cấp (cấu trúc tổ chức trong doanh nghiệp (quản lý, nhân viên), phân loại sản phẩm, hoặc phân loại tài liệu).
• Trong lý thuyết đồ thị, cây có nhiều ứng dụng trong việc giải quyết các bài toán tối ưu và phân tích đồ thị. Cây được sử dụng trong các thuật toán như Thuật toán Dijkstra và Thuật toán Bellman-Ford để tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh còn lại trong đồ thị. Một số bài toán phân tích đồ thị có thể được giải quyết bằng cách chia đồ thị thành các cây con, như trong thuật toán phân chia đồ thị (Graph Partitioning).
• Trong các hệ quản trị cơ sở dữ liệu, cây được sử dụng để tổ chức và tối ưu hóa việc truy vấn và lưu trữ dữ liệu. Cây B (B-tree) được sử dụng rộng rãi trong các hệ cơ sở dữ liệu và hệ thống lưu trữ để duy trì dữ liệu có thứ tự và giúp thực hiện các thao tác tìm kiếm, chèn, sửa, xóa một cách hiệu quả. Các cây B+ và cây B* là những biến thể của cây B được sử dụng trong các hệ cơ sở dữ liệu quan hệ. Cây phân cấp (Hierarchical Tree) được sử dụng trong các hệ thống quản lý dữ liệu phân cấp, như trong các cơ sở dữ liệu tài liệu, hay các hệ thống quản lý file.
• Trong xử lý ngôn ngữ tự nhiên, cây được sử dụng để phân tích cấu trúc cú pháp của câu. Cây cú pháp (Parse Tree) là cây biểu diễn cấu trúc cú pháp của câu trong ngôn ngữ tự nhiên, với các đỉnh là các từ hoặc cụm từ và các nhánh là mối quan hệ cú pháp giữa chúng. Cây cú pháp giúp máy tính hiểu được cách thức các từ và cụm từ liên kết với nhau để tạo thành câu có nghĩa. Cây quyết định (Decision Trees) là một trong những thuật toán học máy phổ biến giúp phân loại và dự đoán bằng cách xây dựng cây, trong đó mỗi nhánh biểu thị một quyết định dựa trên các đặc trưng của dữ liệu, và các lá của cây biểu thị kết quả phân loại hoặc dự đoán.

Một số hình ảnh