From Wikipedia, the free encyclopedia
У информатици, скуп је апстрактан тип података који може да складишти одређене вредности. Односи се на примену математичке замисли коначног скупа. Елементи скупа су организовани без експлицитног уређења и хијерархије и без понављања вредности. За разлику од већине других врста колекција, обично се испитује припадност елемента скупу а не тражи се његова вредност.
Неке скуповне структуре направљене су за статичку употребу и не мењају се након што су направљене. Статички скупови дозвољавају само операције упита над својим елементима — као што су провере да ли вредност припада скупу, или набрајања вредности у неком произвољном редоследу. Друге варијанте називају се динамички или променљиви скупови, и они дозвољавају уметање или брисање елемената из скупа.
У теорији типова, скупови су одређени индикатор функцијом (карактеристичном функцијом): према томе, скуп вредности типа А може се означити са или . Карактеристична функција скупа се дефинише као:
У теорији, многе друге апстрактне структуре података могу се посматрати као скуповне структуре са додатно дефинисаним операцијама и/или правилима наметнутих стандардним операцијама. На пример, хип се може посматрати као скуповна структура са дефинисаном операцијом 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)
: ствара одређену структуру са вредностима к1, к2, … , к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
сложености , јер захтевају пролазак кроз целу листу. Скупови су често примењени помоћу делотвронијих структура података као што су разне врсте дрвећа или хеш табела.
Низови су други популарни начини примене. Посебно, скуп целих бројева се може ефикасно применити као -битни битски низ, који подржава веома ефикасне операције уније и пресека.
Један од најранијих језика са подршком за скупове био је Паскал. Данас, у многим језицима постоји подршка било у основном језику или у стандардној библиотеци.
Set
интерфејс за подршку за рад са скуповима.set
и frozenset
од верзије 2.4, а од 3.0 i 2.7, подржава непразан скуп коришћењем витичастих заграда, нпр: {x, y, z}
.HashSet
и SortedSet
које примењују генерички ISet
интерфејс.set
, Set
и SortedSet
које примењују скупове помоћу хеш табеле, а други омогућава итерацију у сортираном редоследу.set
, који примењује сортиран скуп користећи бинарно претраживачко дрво.Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.