Bài báo đề xuất nguyên lý kế thừa trong việc thiết kế các thuật toán tổ hợp. Dựa trên nguyên lý kế thừa phát triển bài toán dãy bị chặn được đề xuất trong thành một số bài toán dãy bị chặn dạng đặc biệt và giải quyết chúng bằng các thuật toán ngắn gọn. | Tạp chí Tin học và Điều khiển học, , (2013), 79–91 NGUYÊN LÝ KẾ THỪA VÀ MỘT SỐ BÀI TOÁN DÃY BỊ CHẶN∗ HOÀNG CHÍ THÀNH Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Tóm t t. Bài báo đề xuất nguyên lý kế thừa trong việc thiết kế các thuật toán tổ hợp. Dựa trên nguyên lý kế thừa phát triển bài toán dãy bị chặn được đề xuất trong [5] thành một số bài toán dãy bị chặn dạng đặc biệt và giải quyết chúng bằng các thuật toán ngắn gọn. Áp dụng các thuật toán này cho các bài toán tổ hợp có nhiều ứng dụng như: bài toán tập con, bài toán tập con bội, bài toán tập con k -phần tử và bài toán phân hoạch tập hợp. T khóa. Nguyên lý kế thừa, bài toán dãy bị chặn, bài toán tổ hợp. Abstract. In this paper, we propose an inheritance principle for combinatorial algorithm design. Based on the principle we extend the bounded sequence problem presented in [4] to some special bounded sequence problems and solve them by shorter algorithms. Then we apply these algorithms to solve some well-known combinatorial problems, such as subset problem, multi-subset problem, k -element subset problem and partition problem. Key words. Inheritance principle, bounded sequence problems, combinatorial problems. 1. MỞ ĐẦU Các khái niệm tập con, tập con bội, phân hoạch. được ứng dụng nhiều trong tính toán khoa học và xử lý thông tin, đặc biệt là trong các bài toán mang tính “vét cạn”. Do vậy, việc xây dựng các thuật toán hữu hiệu để sinh ra các tập con của một tập hợp, các tập con bội của một tập bội, các phân hoạch của một tập hợp. vẫn được nhiều người quan tâm. Đã có một số thuật toán giải bài toán tập con của tập hợp, bài toán tập con bội của tập bội, bài toán tập con k -phần tử, bài toán phân hoạch [1, 2, 4]. Những bài toán này có nhiều ứng dụng trong thực tế. D. Singh et al. đã tổng quan một số ứng dụng của tập bội trong toán học và công nghệ thông tin [3]. Trong [5] tác giả đã đề xuất và giải quyết bài toán dãy bị chặn bằng một thuật toán ngắn gọn. Các nghiệm của bài toán
