Скуп (структура података)

У информатици, скуп је апстрактан тип података који може да складишти одређене вредности. Односи се на примену математичке замисли коначног скупа. Елементи скупа су организовани без експлицитног уређења и хијерархије и без понављања вредности. За разлику од већине других врста колекција, обично се испитује припадност елемента скупу а не тражи се његова вредност.

Неке скуповне структуре направљене су за статичку употребу и не мењају се након што су направљене. Статички скупови дозвољавају само операције упита над својим елементима — као што су провере да ли вредност припада скупу, или набрајања вредности у неком произвољном редоследу. Друге варијанте називају се динамички или променљиви скупови, и они дозвољавају уметање или брисање елемената из скупа.

Теорија типова

У теорији типова, скупови су одређени индикатор функцијом (карактеристичном функцијом): према томе, скуп вредности типа А може се означити са $2^{A}$ или ${\mathcal {P}}(A)$. Карактеристична функција $F$ скупа $A$ се дефинише као:

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

У теорији, многе друге апстрактне структуре података могу се посматрати као скуповне структуре са додатно дефинисаним операцијама и/или правилима наметнутих стандардним операцијама. На пример, хип се може посматрати као скуповна структура са дефинисаном операцијом min(A) која враћа елемент најмање вредности.

Операције

Конкретна реализација у неком програмском језику би могла да примени неки од наведених интерфејса.

Опште скуповне операције

Могу се дефинисати следеће операције алгебре скупова:

• unija(A,B): враћа унију скупова A и B.
• presek(A,B): враћа пресек скупова A и B.
• razlika(A,B): враћа разлику скупова A и B.
• podskup(A,B): предикат који проверава да ли је скуп A подскуп скупа B.

Статички скупови

Типичне операције за статички скуп су:

• da_li_pripada(n, A): проверава да ли је вредност n у скупу A.
• da_li_je_prazan(A): проверава да ли је скуп А празан.
• veličina(A) или kardinalnost(A): враћа број елемената у A.
• iterator(A): враћа функцију која враћа следћу вредност из А приликом сваког позива, у неком произвољном редоследу.
• nabrajanje(A): враћа листу која садржи елементе из А у неком произвољном редоследу.
• napravi(k1, k2, ... ,kn): ствара одређену структуру са вредностима к₁, к₂, … , к_n.
• napravi_od(kolekcija): ствара нови скуп структуру која садржи све елементе дате колекције.

Динамички скупови

Динамичке структуре обично имају::

• stvori(): ствара нови, почетно празан скуп.
• stvori_sa_kapacitetom_N(n): креира нови скуп, у почетку празан, али у стању да држи до n елемената.
• dodaj(A,k): додаје елемент k на А, ако већ није присутан.
• izbaci(A,k): уклања елемент k из А, ако је присутан.
• kapacitet(A): враћа највећи број вредности које се могу сачувати у A.

Неке структуре могу дозволити само неке од ових операција. Ефикасност сваке операције ће зависити од реализације, а можда и од вредности које се налазе у скупу или редоследа којим су уметнуте.

Додатне операције

Постоје многе друге операције које се могу дефинисати, као што су:

• pop(A): враћа произвољан елемент из А и брише га.
• map(F,A): враћа скуп различитих вредности које проистичу из примене функција F на сваки елемент из А.
• ocisti(A): избрисати све елементе из A.
• jednaki(A,B): проверава да ли је скуп A једнак B (тј. садржи све и само те исте елементе).

Друге операције могу да се дефинишу за скупове са елементима посебног типа:

• zbir(A): враћа збир свих елемената A за неку дефиницију „збира”.
• najbliži(A,k): враћа елемент из A који је најближи вредности k (по неком критеријуму).
• min(A), max(A): враћа најмањи или највећи елемент из A.

Примене

Скупови се могу применити коришћењем различитих структура података, који пружају различите компромисе временске и просторне сложености за различите операције. Неке примене направљене су да побољшају делотворност специјализованих операција, као што су najblizi или unija. Примене за „општу употребу” обично настоје да оптимизују операције element_od, dodati, izbrisati. Једноставан начин је да се користи листа, занемарујући редослед елемената и водећи рачуна да се избегне понављање вредности. Ово је једноставна, али неучинковита примена, како су операције попут da_li_pripada или obrisi_element сложености $O(n)$, јер захтевају пролазак кроз целу листу. Скупови су често примењени помоћу делотвронијих структура података као што су разне врсте дрвећа или хеш табела.

Низови су други популарни начини примене. Посебно, скуп целих бројева $1..n$ се може ефикасно применити као $n$-битни битски низ, који подржава веома ефикасне операције уније и пресека.

Подршка у прогамским језицима

Један од најранијих језика са подршком за скупове био је Паскал. Данас, у многим језицима постоји подршка било у основном језику или у стандардној библиотеци.

• Java нуди Set интерфејс за подршку за рад са скуповима.
• Python има уграђне типове set и frozenset од верзије 2.4, а од 3.0 i 2.7, подржава непразан скуп коришћењем витичастих заграда, нпр: {x, y, z}.
• .NET Framework пружа генеричке класе HashSet и SortedSet које примењују генерички ISet интерфејс.
• Ruby стандардна библиотека укључује модул који садржи класе set , Set и SortedSet које примењују скупове помоћу хеш табеле, а други омогућава итерацију у сортираном редоследу.
• C++, стандардна библиотека шаблона (STL) обезбеђује шаблон set, који примењује сортиран скуп користећи бинарно претраживачко дрво.

Спољашње везе

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