ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
ĐINH VĂN VIỆT
MỘT THUẬT TOÁN HIỆU QUẢ CHO TẬP ĐỈNH THỐNG TRỊ CÓ
TRỌNG SỐ NHỎ NHẤT
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
HÀ NỘI – 2021
3
Lời Cảm Ơn
Đầu tiên, tôi xin gửi lời cảm ơn đến PGS. TS. Hoàng Xuân Huấn, giảng
viên tại bộ môn khoa học máy tính thuộc khoa công nghệ thông tin. Trong khi
làm luận văn, thầy đã hướng dẫn tôi rất tận tình chu đáo. Không chỉ giới thiệu
những kiến thức hữu ích, thầy còn truyền cảm hứng đến tôi về những ứng dụng
tự nhiên lý thú. Tôi ngày càng trưởng thành hơn không chỉ về nhiều kiến thức
hơn, mà còn cả về nhận thức về đời sống thực tại. Tôi vô cùng kính phục và cám
ơn thầy.
Tiếp theo, tôi vô cùng cảm ơn bố mẹ đã luôn ở bên cạnh hỗ trợ tôi, giúp
tôi trong hầu hết các vấn đề gặp phải trong cuộc sống. Tôi xin cảm ơn gia đình
tôi, nơi tôi được sinh ra và lớn lên, nơi có rất nhiều kỷ niệm đẹp ảnh hưởng sâu
sắc đến những tư duy của tôi trong luận văn này. Nhờ tình thương vô bờ bến của
họ, tôi đã không phải chịu quá nhiều áp lực của cuộc sống mưu sinh đầy vất vả,
có thêm nhiều thời gian dành cho luận văn này. Đây là động lực chính giúp tôi
hoàn thành xong luận văn này.
Cuối cùng, tôi cảm ơn bạn bè và đồng nghiệp đã tạo điều kiện giúp tôi,
cùng tôi đi tiếp trên những chặng đường đầy thách thức không chỉ trong công
việc mà còn các vấn đề ngoài cuộc sống. Tôi xin gửi lời cảm ơn đến toàn bộ tập
thể trường đại học Công Nghệ, trực thuộc đại học quốc gia Hà Nội. Ở đây, tôi đã
được sống trong môi trường năng động, trẻ trung, tràn trề cơ hội và thách thức.
Cảm ơn tất cả đã mở ra cánh cửa tương lai tươi sáng cho chính tôi!
Tác giả
Đinh Văn Việt
4
Lời Cam Đoan
Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự giám sát
của PGS.TS Hoàng Xuân Huấn. Các phần đóng góp trong luận văn này chưa
được nộp cho một trình độ hoặc bằng cấp tại đây hoặc bất cứ các tổ chức nghiên
cứu giáo dục đại học. Các đóng góp và kết quả được trình bày trong luận văn
này hoàn toàn được kiểm nghiệm rõ ràng bằng các thực nghiệm dựa trên nhiều
bộ dữ liệu được chấp thuận và sử dụng bởi cộng đồng khoa học. Các phần có sự
đóng góp của người khác vào luận văn này đều được xin phép và có được sự
đồng ý chấp thuận của họ. Các phần kiến thức liên quan được sử dụng trong
luận văn này đều được tham chiếu rõ ràng từ các nguồn tham khảo được công
đồng khoa học công nhận và được liệt kê đầy đủ tại mục liệt kê tham khảo.
Tác giả
Đinh Văn Việt
5
Danh sách ký hiệu và viết tắt
NP
Nondeterministic polynomial Problem
P
Polynomial Problem
MDS
Minimum dominating set
MCDS
Minimum Connected Dominating Set
MIDS
Minimum Independent Dominating Set
MkDS
Minimum k-dominating Set
MWDS
Minimum Weighted Dominating Set
GA
Genetic Algorithm
ACO
Ant Colony Optimization
PSO
Particle Swarm Optimization
MA
Memetic Algorithm
LS
Local Search
LNS
Large Neighborhood Search
IP
Integer Programming
MMAS
Max-Min Ant System
GRASP
Greedy Randomized Adaptive Search Procedure