Podstawowe pojęcia dotyczące zbiorów


Tematy pokrewne   Podrozdziały
Zbiory
Podstawowe pojęcia dotyczące zbiorów
Reprezentacja zbiorów na listach
Reprezentacja zbiorów w tablicach
Reprezentacja zbiorów w mapach bitowych
Reprezentacja zbiorów w drzewach binarnych
  Definicje
Zbiory jako struktura danych

Definicje

Zbiór (ang. set) składa się z elementów (dokładnej definicji nie podamy, bo nie jest nam potrzebna). Elementy mogą być liczbami lub dowolnymi innymi obiektami, które da się reprezentować za pomocą bitów w komputerze (znaki, teksty, obrazki, filmy, struktury...). My zajmiemy się głównie zbiorami liczbowymi, ponieważ inne zbiory da się łatwo odwzorować na zbiory liczbowe (np. nadając elementom numer zwany kluczem).

 

Zbiór pusty (ang. empty set) to zbiór, który nie zawiera żadnego elementu. Oznaczamy go symbolem Ø.

 

Zbiór skończony (ang. finite set) to zbiór, który zawiera skończoną liczbę elementów. Np. zbiorem skończonym jest zbiór liczb {1 2 3}.

 

Zbiór nieskończony (ang. infinite set), to zbór, który nie jest skończony, czyli zawiera nieskończoną liczbę elementów. Zbiorami nieskończonymi są przykładowo zbiory liczb naturalnych, wymiernych, rzeczywistych, pierwszych, itp.

 

Przestrzeń (ang. space) jest zbiorem, który zawiera wszystkie możliwe elementy zbiorów. Na przykład umawiamy się, że nasze zbiory mogą zawierać liczby od 0 do 99. Zatem przestrzenią dla tych zbiorów będzie zbiór, który zawiera elementy {0, 1, 2, ..., 98, 99}.

 

Podzbiór (ang. subset) jest zbiorem, który zawiera się w innym zbiorze. Mówimy, że zbiór A jest podzbiorem zbioru B, jeśli wszystkie elementy zbioru A są również elementami zbioru B. Relację tę zapisujemy matematycznie jako:

Mówimy, że zbiór A nie jest podzbiorem zbioru B, jeśli żaden element zbioru A nie jest elementem zbioru B. Zapisujemy to jako:

Dwa zbiory są równe, jeśli są nawzajem swoimi podzbiorami, czyli:

Zbiór pusty jest podzbiorem każdego zbioru:

 

Zapis:

oznacza, że element x należy do zbioru A (czyli jest w zbiorze A).

 

Zapis:

oznacza, że element x nie należy do zbioru A (czyli nie ma go w zbiorze A).

 

Liczbę elementów zbioru A oznaczamy jako |A| i nazywamy mocą zbioru.

 

Sumą (ang. union) zbiorów A i B jest zbiór C, którego elementami są wszystkie elementy zbioru A i wszystkie elementy zbioru B (czyli każdy element zbioru A jest elementem zbioru C, każdy element zbioru B jest elementem zbioru C, każdy element zbioru C jest elementem zbioru A lub jest elementem zbioru B):

 

Iloczynem (ang. intersection) zbiorów A i B jest zbiór C, którego wszystkie elementy należą jednocześnie do zbioru A i do zbioru B:

 

Różnicą (ang. difference) zbiorów A i B jest zbiór C, którego wszystkie elementy należą do zbioru A, lecz żaden nie należy do zbioru B:

 

Dopełnienie (ang. complement) zbioru A do przestrzeni U jest zbiorem A' wszystkich możliwych elementów, których nie zawiera zbiór A:

 

Zbiory jako struktura danych

Aby korzystać ze zbiorów tworzonych programach, musimy posiadać odpowiednią strukturę danych. Struktura ta powinna udostępniać następujący zestaw operacji (na początku nazw operacji dodaliśmy s_, aby uniknąć konfliktów nazw):

 

s_create(n) tworzy pusty zbiór o maksymalnej pojemności n elementów
s_union(A,B) zwraca sumę zbiorów A i B
s_intersection(A,B) zwraca iloczyn zbiorów A i B
s_difference(A,B) zwraca różnicę zbioru A i B
s_complement(A) zwraca dopełnienie zbioru A
s_subset(A,B) zwraca true, jeśli zbiór A jest podzbiorem zbioru B, inaczej zwraca false.
s_empty(A) zwraca true, jeśli zbiór A jest pusty, inaczej zwraca false
s_size(A) zwraca liczbę elementów zawartych w zbiorze A
s_add(A,x) dodaje element x do zbioru A, jeśli jeszcze go tam nie ma
s_remove(A,x) usuwa element x ze zbioru A, jeśli się tam znajduje
s_isin(A,x) zwraca true, jeśli element x jest w zbiorze A, inaczej zwraca false
s_clear(A) usuwa wszystkie elementy ze zbioru A. Zbiór A staje się zbiorem pustym.

 

Zbiór można zaimplementować w różnych strukturach danych. Najczęściej są to listy, tablice, mapy bitowe lub drzewa poszukiwań binarnych. Wybór odpowiedniej struktury ma na celu optymalizację powyższych operacji. W kolejnych artykułach przedstawiamy proste implementacje zbiorów w tych strukturach danych.

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2018 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe