Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące zbiorów

SPIS TREŚCI
Podrozdziały

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:

obrazek

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:

obrazek

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

Zbiór pusty jest podzbiorem każdego zbioru:

Zapis:

obrazek

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

Zapis:

obrazek

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 ):

obrazek

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:

obrazek

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:

obrazek

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

obrazek

Na początek:  podrozdziału   strony 

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.

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.