Chương 5 - TẬP HỢP

Tập hợp là một cấu trúc cơ bản của toán học. Trong thiết kế thuật toán, chúng ta thường xuyên phải sử dụng đến mô hình dữ liệu tập hợp. Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu tập hợp, các phương pháp cài đặt tập hợp. Sau đó chúng ta sẽ nghiên cứu một số kiểu dữ liệu trừu tượng, đó là từ điển và hàng ưu tiên, được xây dựng dựa trên khái niệm tập hợp, nhưng chỉ quan tâm đến một số phép toán nào đó....
Nội dung trích xuất từ tài liệu:
Chương 5 - TẬP HỢP Ch¬ng 5 TËp hîp TËp hîp lµ mét cÊu tróc c¬ b¶n cña to¸n häc. Trong thiÕt kÕthuËt to¸n, chóng ta thêng xuyªn ph¶i sö dông ®Õn m« h×nh d÷ liÖutËp hîp. Trong ch¬ng nµy chóng ta sÏ nghiªn cøu m« h×nh d÷ liÖu tËphîp, c¸c ph¬ng ph¸p cµi ®Æt tËp hîp. Sau ®ã chóng ta sÏ nghiªn cøumét sè kiÓu d÷ liÖu trõu tîng, ®ã lµ tõ ®iÓn vµ hµng u tiªn, ®îc x©ydùng dùa trªn kh¸i niÖm tËp hîp, nhng chØ quan t©m ®Õn mét sèphÐp to¸n nµo ®ã. 5.1. TËp hîp vµ c¸c phÐp to¸n trªn tËp hîp. Chóng ta xem r»ng, ®éc gi¶ ®· lµm quen víi tËp hîp. Do ®ã chóngta chØ tr×nh bµy ng¾n gän mét sè kh¸i niÖm ®îc sö dông ®Õn saunµy. Trong to¸n häc, cã hai ph¬ng ph¸p ®Ó x¸c ®Þnh mét tËp hîp A.§¬n gi¶n nhÊt lµ liÖt kª tÊt c¶ c¸c phÇn tö cña tËp A (nÕu tËp A h÷uh¹n). Ch¼ng h¹n, A = {1, 2, 3} cã nghÜa lµ A tËp hîp chØ gåm 3 phÇntö 1, 2, 3. C¸ch kh¸c, ta còng cã thÓ x¸c ®Þnh mét tËp A b»ng c¸ch nªulªn c¸c ®Æc trng cho ta biÕt chÝnh x¸c mét ®èi tîng bÊt kú cã lµ métphÇn tö cña tËp A hay kh«ng. VÝ dô, A = {x| x lµ sè nguyªn ch½n}. TacÇn quan t©m ®Õn mét tËp ®Æc biÖt : tËp trèng φ, ®ã lµ tËp hîpkh«ng chøa phÇn tö nµo c¶. Víi hai tËp bÊt kú A, B vµ mét ®èi tîng x bÊt kú, ta cã c¸c quan hÖsau ®©y: x ∈ A (x thuéc A), quan hÖ nµy ®óng nÕu vµ chØ nÕu x lµphÇn tö cña tËp A. A ⊆ B (A lµ tËp con cña B), quan hÖ nµy ®óng nÕu vµ chØnÕu mäi phÇn tö cña tËp A lµ phÇn tö cña tËp B. A = B nÕu vµ chØ nÕu A ⊆ B vµ B ⊆ A. C¸c phÐp to¸n c¬ b¶n trªn tËp hîp C¸c phÐp to¸n c¬ b¶n trªn tËp hîp lµ hîp, giao, hiÖu. Cho hai tËpA vµ B, khi ®ã hîp cña A vµ B, A ∪ B , lµ tËp hîp gåm tÊt c¶ c¸c phÇntö thuéc A hoÆc thuéc B. Cßn giao cña A vµ B lµ tËp A ∩ B gåm tÊt c¶c¸c phÇn tö võa thuéc A, võa thuéc B. HiÖu A-B lµ tËp hîp gåm tÊt c¶c¸c phÇn tö thuéc A nhng kh«ng thuéc B. Ch¼ng h¹n, nÕu A = {1, 2, 3, 1224} vµ B = { 3, 4, 5} th× A ∪ B = {1, 2, 3, 4, 5}, cßn A ∩ B = {3, 4} vµ A-B= {1, 2}. TÝch ®ª-cac cña hai tËp hîp A vµ B lµ tËp hîp A x B gåm tÊt c¶c¸c cÆp phÇn tö (a, b), trong ®ã a ∈ A vµ b ∈ B. Ch¼ng h¹n, nÕu A ={1, 2}, B = {a, b, c} th× A x B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. Quan hÖ nhÞ nguyªn trªn tËp hîp Khi xÐt mét tËp hîp, trong nhiÒu trêng hîp ta cÇn quan t©m ®Õnquan hÖ gi÷a c¸c phÇn tö cña tËp hîp. Mét quan hÖ nhÞ nguyªn (gäit¾t lµ quan hÖ) R trªn tËp A lµ mét tËp con nµo ®ã cña tÝch ®ª-cac Ax A, tøc lµ R ⊆ A x A. NÕu a, b lµ c¸c phÇn tö cña tËp A vµ (a, b) ∈ R th× ta nãi a cãquan hÖ R víi b vµ ký hiÖu lµ aRb. VÝ dô : A = {a, b, c} vµ R = {(a, a),(a, c), (b, a), (c, b)}, khi ®ã a cã quan hÖ R víi c v× (a,c) ∈ R cßn bkh«ng cã quan hÖ R víi c v× cÆp (b, c) ∉ R. Mét quan hÖ R cã thÓ cã c¸c tÝnh chÊt sau : - Quan hÖ R trªn tËp A cã tÝnh ph¶n x¹, nÕu aRa, víi mäi a ∈ A. - Quan hÖ R cã tÝnh ®èi xøng, nÕu mçi khi cã aRb th× còng cãbRa. - Quan hÖ R cã tÝnh b¾c cÇu, nÕu mçi khi cã aRb vµ bRc th×còng cã aRc. - Quan hÖ R cã tÝnh ph¶n ®èi xøng, nÕu mçi khi cã aRb vµ a ≠b th× kh«ng cã bRa. VÝ dô nÕu A lµ tËp c¸c sè nguyªn Z vµ R lµ quan hÖ nhá h¬n ( Mét quan hÖ R trªn tËp A ®îc gäi lµ quan hÖ thø tù bé phËn,nÕu nã tho¶ m·n c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu. Khitrªn tËp A ®îc x¸c ®Þnh quan hÖ thø tù bé phËn, ta nãi A lµ tËp ®îcs¾p thø tù bé phËn. Ch¼ng h¹n, A lµ tËp c¸c sè nguyªn d¬ng, quan hÖR ®îc x¸c ®Þnh nh sau : nRm nÕu vµ chØ nÕu n lµ íc cña m. Khi ®ã Rcã c¶ ba tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu, do ®ã nã lµquan hÖ thø tù bé phËn. Quan hÖ thø tù bé phËn R sÏ ®îc ký hiÖu lµ≤, do ®ã aRb sÏ ®îc viÕt lµ a ≤ b. TËp ®îc s½p thø tù bé phËn A ®îcgäi lµ tËp ®îc s¾p thø tù hoµn toµn, hay tËp ®îc s¾p thø tù tuyÕntÝnh, nÕu víi mäi cÆp phÇn tö a, b thuéc A ta lu«n lu«n cã a ≤ bhoÆc b ≤ a. Ch¼ng h¹n, tËp c¸c sè nguyªn, tËp c¸c sè thùc ®Òu lµ c¸ctËp ®îc s¾p thø tù tuyÕn tÝnh víi quan hÖ ≤ th«ng thêng. M« h×nh d÷ liÖu tËp hîp Trong thiÕt kÕ thuËt to¸n, khi sö dông tËp hîp nh mét m« h×nhd÷ liÖu, ngoµi c¸c phÐp to¸n hîp, giao, hiÖu, chóng ta ph¶i cÇn ®ÕnnhiÒu phÐp to¸n kh¸c. Sau ®©y chóng ta sÏ ®a ra mét sè phÐp to¸nquan träng nhÊt, c¸c phÐp to¸n nµy sÏ ®îc m« t¶ bëi c¸c thñ tôc hoÆchµm.1. PhÐp hîp : Procedure Union (A, B : set; var C : set); Thñ tôc t×m hîp cña tËp A vµ tËp B, kÕt qu¶ lµ tËp C.2. PhÐp giao : Procedure Intersection (A, B : set; var C : set); Thñ tôc t×m giao cña tËp A vµ tËp B, kÕt qu¶ lµ tËp C.3. PhÐp trõ : Procedure Difference ( A,B: set ; var C: set); Thñ tôc t×m hiÖu cña tËp A vµ tËp B, kÕt qu¶ lµ C.4. X¸c ®Þnh mét phÇn tö cã thuéc tËp hîp hay kh«ng : Function Member ( x: element ; A: set) : boolean ; Hµm Member nhËn gi¸ trÞ true nÕu x∈A vµ false nÕu kh«ng.5. PhÐp xen vµo : Procedure Insert ( x: element ; var A: set); 124 Thñ tôc nµy thªm phÇn tö x vµo tËp A, do ®ã sau khi thùc hiÖnthñ tôc, gi¸ trÞ míi cña A lµ A ∪{x}.6. PhÐp lo¹i bá : Procedure Delete ( x : element ; var A: set); Thñ tôc nµy lo¹i bá x khái tËp A . Sau thñ tôc nµy ,tham biÕn AnhËn gi¸ trÞ míi lµ A-{x}.7. T×m phÇn tö nhá nhÊt ( phÇn tö lín nhÊt ). Procedure Min ( A: set ; var x: element ); PhÐp to¸n nµy chØ ¸p dông trªn c¸c tËp hîp s¾p thø tù tuyÕntÝnh . Sau khi thùc hiÖn thñ tôc, x lµ phÇn tö nhá nhÊt cña tËp A . VÊn ®Ò ®îc ®Æt ra b©y giê lµ , ta cÇn biÓu diÔn tËp hîp nh thÕnµo ®Ó c¸c phÐp to¸n ®îc thùc hiÖn víi hiÖu qu¶ cao .5.2.Cµi ®Æt tËp hîp. Cã nhiÒu ph¬ng ph¸p biÓu diÔn tËp hîp. Trong tõng ¸p dông, tuúthuéc vµo c¸c phÐp to¸n cÇn thùc hiÖn vµ cì ( sè phÇn tö ) cña tËp hîpmµ ta lùa chän c¸ch cµi ®Æt sao cho c¸c phÐp to¸n thùc hiÖn cã hiÖuqu¶ . ...