Skup (struktura podataka)

U informatici, skup je apstraktan tip podataka koji može da skladišti određene vrednosti. Odnosi se na primenu matematičke zamisli konačnog skupa. Elementi skupa su organizovani bez eksplicitnog uređenja i hijerarhije i bez ponavljanja vrednosti. Za razliku od većine drugih vrsta kolekcija, obično se ispituje pripadnost elementa skupu a ne traži se njegova vrednost.

Neke skupovne strukture napravljene su za statičku upotrebu i ne menjaju se nakon što su napravljene. Statički skupovi dozvoljavaju samo operacije upita nad svojim elementima — kao što su provere da li vrednost pripada skupu, ili nabrajanja vrednosti u nekom proizvoljnom redosledu. Druge varijante nazivaju se dinamički ili promenljivi skupovi, i oni dozvoljavaju umetanje ili brisanje elemenata iz skupa.

Teorija tipova

U teoriji tipova, skupovi su određeni indikator funkcijom (karakterističnom funkcijom): prema tome, skup vrednosti tipa A može se označiti sa $2^{A}$ ili ${\mathcal {P}}(A)$. Karakteristična funkcija $F$ skupa $A$ se definiše kao:

$F(x)={\begin{cases}1,&{\mbox{if }}x\in A\\0,&{\mbox{if }}x\not \in A\end{cases}}$

U teoriji, mnoge druge apstraktne strukture podataka mogu se posmatrati kao skupovne strukture sa dodatno definisanim operacijama i/ili pravilima nametnutih standardnim operacijama. Na primer, hip se može posmatrati kao skupovna struktura sa definisanom operacijom min(A) koja vraća element najmanje vrednosti.

Operacije

Konkretna realizacija u nekom programskom jeziku bi mogla da primeni neki od navedenih interfejsa.

Opšte skupovne operacije

Mogu se definisati sledeće operacije algebre skupova:

• unija(A,B): vraća uniju skupova A i B.
• presek(A,B): vraća presek skupova A i B.
• razlika(A,B): vraća razliku skupova A i B.
• podskup(A,B): predikat koji proverava da li je skup A podskup skupa B.

Statički skupovi

Tipične operacije za statički skup su:

• da_li_pripada(n, A): proverava da li je vrednost n u skupu A.
• da_li_je_prazan(A): proverava da li je skup A prazan.
• veličina(A) ili kardinalnost(A): vraća broj elemenata u A.
• iterator(A): vraća funkciju koja vraća sledću vrednost iz A prilikom svakog poziva, u nekom proizvoljnom redosledu.
• nabrajanje(A): vraća listu koja sadrži elemente iz A u nekom proizvoljnom redosledu.
• napravi(k1, k2, ... ,kn): stvara određenu strukturu sa vrednostima k₁, k₂, … , k_n.
• napravi_od(kolekcija): stvara novi skup strukturu koja sadrži sve elemente date kolekcije.

Dinamički skupovi

Dinamičke strukture obično imaju::

• stvori(): stvara novi, početno prazan skup.
• stvori_sa_kapacitetom_N(n): kreira novi skup, u početku prazan, ali u stanju da drži do n elemenata.
• dodaj(A,k): dodaje element k na A, ako već nije prisutan.
• izbaci(A,k): uklanja element k iz A, ako je prisutan.
• kapacitet(A): vraća najveći broj vrednosti koje se mogu sačuvati u A.

Neke strukture mogu dozvoliti samo neke od ovih operacija. Efikasnost svake operacije će zavisiti od realizacije, a možda i od vrednosti koje se nalaze u skupu ili redosleda kojim su umetnute.

Dodatne operacije

Postoje mnoge druge operacije koje se mogu definisati, kao što su:

• pop(A): vraća proizvoljan element iz A i briše ga.
• map(F,A): vraća skup različitih vrednosti koje proističu iz primene funkcija F na svaki element iz A.
• ocisti(A): izbrisati sve elemente iz A.
• jednaki(A,B): proverava da li je skup A jednak B (tj. sadrži sve i samo te iste elemente).

Druge operacije mogu da se definišu za skupove sa elementima posebnog tipa:

• zbir(A): vraća zbir svih elemenata A za neku definiciju „zbira”.
• najbliži(A,k): vraća element iz A koji je najbliži vrednosti k (po nekom kriterijumu).
• min(A), max(A): vraća najmanji ili najveći element iz A.

Primene

Skupovi se mogu primeniti korišćenjem različitih struktura podataka, koji pružaju različite kompromise vremenske i prostorne složenosti za različite operacije. Neke primene napravljene su da poboljšaju delotvornost specijalizovanih operacija, kao što su najblizi ili unija. Primene za „opštu upotrebu” obično nastoje da optimizuju operacije element_od, dodati, izbrisati. Jednostavan način je da se koristi lista, zanemarujući redosled elemenata i vodeći računa da se izbegne ponavljanje vrednosti. Ovo je jednostavna, ali neučinkovita primena, kako su operacije poput da_li_pripada ili obrisi_element složenosti $O(n)$, jer zahtevaju prolazak kroz celu listu. Skupovi su često primenjeni pomoću delotvronijih struktura podataka kao što su razne vrste drveća ili heš tabela.

Nizovi su drugi popularni načini primene. Posebno, skup celih brojeva $1..n$ se može efikasno primeniti kao $n$-bitni bitski niz, koji podržava veoma efikasne operacije unije i preseka.

Podrška u progamskim jezicima

Jedan od najranijih jezika sa podrškom za skupove bio je Paskal. Danas, u mnogim jezicima postoji podrška bilo u osnovnom jeziku ili u standardnoj biblioteci.

• Java nudi Set interfejs za podršku za rad sa skupovima.
• Python ima ugrađne tipove set i frozenset od verzije 2.4, a od 3.0 i 2.7, podržava neprazan skup korišćenjem vitičastih zagrada, npr: {x, y, z}.
• .NET Framework pruža generičke klase HashSet i SortedSet koje primenjuju generički ISet interfejs.
• Ruby standardna biblioteka uključuje modul koji sadrži klase set , Set i SortedSet koje primenjuju skupove pomoću heš tabele, a drugi omogućava iteraciju u sortiranom redosledu.
• C++, standardna biblioteka šablona (STL) obezbeđuje šablon set, koji primenjuje sortiran skup koristeći binarno pretraživačko drvo.

Spoljašnje veze

• A Practical Theory of Programming, 2012-3-30 edition