Giải thuật và lập trình - C: I, II. Khái niệm, Kiểu dữ liệu trừu tượng tập hợp

I. KHÁI NIỆM TẬP HỢP

Tập hợp là một khái niệm cơ bản trong toán học. Tập hợp được dùng để mô hình hoá hay biểu diễn một nhóm bất kỳ các đối tượng trong thế giới thực cho nên nó đóng vai trò rất quan trọng trong mô hình hoá cũng như trong thiết kế các giải thuật.

Khái niệm tập hợp cũng như trong toán học, đó là sự tập hợp các thành viên (members) hoặc phần tử (elements). Tất cả các phần tử của tập hợp là khác nhau. Tập hợp có thể có thứ tự hoặc không có thứ tự, tức là, có thể có quan hệ thứ tự xác định trên các phần tử của tập hợp hoặc không. Tuy nhiên, trong chương này, chúng ta giả sử rằng các phần tử của tập hợp có thứ tự tuyến tính, tức là, trên tập hợp S có quan hệ < và = thoả mản hai tính chất:

Với mọi a,b Î S thì a<b hoặc b<a hoặc a=b Với mọi a,b,c Î S, a<b và b<c thì a<c

II. KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP

Cũng như các kiểu dữ liệu trừu tượng khác, các phép toán kết hợp với mô hình tập hợp sẽ tạo thành một kiểu dữ liệu trừu tượng là rất đa dạng. Tùy theo nhu cầu của các ứng dụng mà các phép toán khác nhau sẽ được định nghĩa trên tập hợp. Ở đây ta đề cập đến một số phép toán thường gặp nhất như sau

  • Thủ tục UNION(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = A ÈB.

  • Thủ tục INTERSECTION(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy giao của hai tập A và B và trả ra kết quả là tập hợp C = A Ç B.

  • Thủ tục DIFFERENCE(A,B,C) nhận vào 3 tham số là A,B,C; Thực hiện phép toán lấy hợp của hai tập A và B và trả ra kết quả là tập hợp C = A\B

  • Hàm MEMBER(x,A) cho kết quả kiểu logic (đúng/sai) tùy theo x có thuộc A hay không. Nếu x Î A thì hàm cho kết quả là 1 (đúng), ngược lại cho kết quả 0 (sai).

  • Thủ tục MAKENULLSET(A) tạo tập hợp A tập rỗng

  • Thủ tục INSERTSET(x,A) thêm x vào tập hợp A