Akademska 2020/21. godina

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

Идентификатори истих појмова могу се разликовати између база података те је семантичка претрага погодно, а у неким случајевима и једино решење за претраживање појмова. Проналажењем и унификацијом семантичких веза између (мета)података који долазе из различитих извора са потенцијално различитoм структурoм и применом метода истраживања података на тако установљене везе, обезбеђује се њихова агрегација у унификовану структуру метаподатака која подржава семантичку претрагу.

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

Ментор: Миодраг Живковић

Теорија графова има велике примене у наукама и технологијама као што су математика, информатика, инжињерство, лингвистика, физика, хемија, компијутерске мреже, биологија и социјалне науке.

Предавање ће одговорити на следећа питања:

• Шта су дијаметар 2 критични графови?
• Начини на које се до њих може доћи и проблеми на које се наилази
• Резултати досадашњег истраживања као и у ком правцу ће се истраживања даље одвијати.

Растојање d(u,v) чворова u и v у графу G=(V,E) са скупом чворова V и грана E је дужина најкраћег пута од u до v. Дијаметар графа G је највеће растојање d(u,v) за било која два чвора u,v из V. Предмет истраживања су графови дијаметра 2. Интуитивно се намеће представа да су графови дијаметра 2 једноставне структуре. Међутим, испоставља се да су асимптотски скоро сви графови дијаметра 2. Због тога је интересантна ужа класа - класа D2C критичних графова дијаметра 2, графова код којих уклањање било које гране води повећавању дијаметра.

Претрага дијаметар 2 критичних графова се може обавити у наставку наведеним методама

• Налажење дијаметар 2 критичних графова уклањањем грана из потпуног графа
• Налажење дијаметар 2 критичних графова додавањем грана на скуп неизоморфних стабала
• Филтрирањем каталога неизоморфних повезаних графова

Као резултат истраживања добијени су значајни резултати. Пронађена је листа дијаметар 2 критичних графофа до реда графа 13, минимални примитивни дијаметар 2 критични графови до реда графа 15, максимални примитивни дијаметар 2 критични графови до реда графа 13 убацивањем филтрирања дијаметар 2 критичних графова у програм „geng“, и убрзавањем постојећег алгоритма за налажење дијаметра 2 у графу.

Ментор: Миодраг Живковић

Булове функције играју важну улогу у науци и технологији. Булове функције од n променљивих се могу сматрати еквивалентним ако се једна у другу могу превести трансформацијама из неке од четири групе: пермутације променљивих (S′_n), пермутације и комплементирања променљивих (G_n), линеарна група (GL_n) и афина група (AGL_n). Проблем израчунавања броја нееквивалентних Булових функција U_n, односно броја инвертибилних векторских Булових функција V_n, у суштини се своди на израчунавање циклусних индекса за наведене групе трансформација.

Овај рад мотивисан је чињеницом да, иако су познати експлицитни (али компликовани) изрази за бројеве класа еквиваленција (Harrison, 1964.), сами циклусни индекси, односно бројеви U_n и V_n, израчунати су само за релативно мале вредности n. Fripertinger је 1997. године имплементирао рачунање циклусног индекса за GL_n и AGL_n у оквиру програмског пакета SYMMETRICA, уз приказ временског извршавања за n ≤ 17. Тренутна верзија програма, на нашем рачунару, рачуна циклусни индекс за n ≤ 21, с обзиром да заузеће меморије расте експоненцијално са n. Користећи овај резултат није тешко израчунати U_n, V_n за GL_n и AGL_n за n ≤ 21. Циљ ове дисертације је опис поступка за рачунање вредности циклусних индекса, односно U_n и V_n, за нешто веће вредности n.

Имајући у виду да се са порастом броја n значајно повећава време за добијање циклусног индекса као и заузеће меморије за његово смештање, потребно је радити са компримованим обликом циклусног индекса и убрзати његово израчунавање. Важан корак у том правцу је представљање монома у циклусном индексу полиномом од једне променљиве у коме коефицијенти и степени, респективно, одговарају степенима и индексима променљивих у моному. Други важан корак је припрема помоћних табела које значајно убрзавају израчунавање циклусног индекса за сваку групу трансформација. Занимљиво је да се у суштини процеси рачунања циклусног индекса своде на сумирање по партицијама броја n, на основу истог израза за све четири групе, тј. израчунавања се разликују само по садржају припремљених табела.

Следећа табела сумира добијене у односу на претходно познате резултате.

Још један интересантан проблем у овој области је израчунавање броја M_n нееквивалентних (у односу на пермутацију променљивих) монотоних Булових функција од n промењених. Бројеви M_n израчунати су до сада за n ≤ 7. Циљ је усавршити поступак за ефективно рачунање M_n и израчунавање M₈.

Fazi relacioni modeli baza podataka, zasnovani na dobro definisanoj teoriji fazi skupova i fazi logici, pružaju mogućnost za prevazilaženje ograničenja tradicionalnog relacionog modela. Takvi modeli pojavili su se 80. tih godina 20. vijeka a nova dostignuća i primjene posljednjih godina unijeli su novi talas u istraživanja fazi baza podataka.

Jedan od prvih pokušaja da se postavi čvrsta teorijska osnova za proširenje sadržaja relacionih baza podataka nepotpunim i nepreciznim informacijama bio je fazi relacioni model Buckles-a i Petry-ja iz 1982 godine. Ova struktura zasnivala se na dva uopštenja tradicionalnog relacionog modela:

1. komponenta torke je u opštem slučaju bilo koji neprazni podskup odgovarajućeg domena, a ne samo jedan element (odstupanje od 1NF) i
2. na svakom domenu definisana je relacija sličnosti (refleksivna, simetrična i max-min tranzitivna, koja svakom paru elemenata iz domena pridružuje realni broj iz intervala [0,1]) i koja, zajedno sa operacijom pripajanja (eng. merge operacijom) predstavlja uopštenje eliminacije duplikata zasnovane na relaciji jednakosti u tradicionalnom relacionom modelu.

Validnost ključnih svojstava ovog modela omogućila je činjenica da je relacija sličnosti – relacija ekvivalencije. Ipak, strogost svojstva max-min tranzitivnosti relacije sličnosti komplikuje konstrukciju ove relacije za neke tipove domena. Krajem osamdesetih godina prošlog vijeka Shenoi i Melton su uopštili ovaj model i pokazali kako njegova glavna karakteristika - postojanje klasa ekvivalencije nad domenima atributa - može biti sačuvana i relacijom koja zadovoljava samo svojstva refleksivnosti i simetričnosti (relacija blizine, eng. proximity relation). Ova relaksacija relacije sličnosti omogućuje prirodniji način izražavanja odnosa među podacima linearno uređenih domena. Istovremeno, tranzitivno zatvorenje relacije blizine omogućuje uspostavljanje relacija ekvivalencije. Važna karakteristika Shenoi-Melton modela jeste da su relacije ekvivalencije definisane na takozvanim vremenskim domenima i da zavise od trenutnog sadržaja baze podataka. Ova karakteristika, zajedno s načinom na koji je relacija ekvivalencije konstruisana relacijom blizine, obezbjeđuje da je blizina elemenata dovoljan ali ne i potreban uslov za njihovu pripadnost istoj klasi ekvivalencije.

Fazi klasifikacija ima primjene u širokom spektru oblasti kao što su medicinska dijagnostika, obrada slika, analiza i predviđanje ponašanja potrošača, klasifikovanje tekstova prema temi, stavu, osjećanju i sl. U tekstuelnom obliku nalazi se mnogo korisne informacije – od mejlova, veb stranica, društvenih mreža, novinskih članaka, izvještaja o istraživanju tržišta, preko CV-ja, pisama žalbi potrošača i internih izvještaja. Za fazi klasifikaciju koriste se fazifikovane metode tradicionalne klasifikacije – metode zasnovane na pravilima kao i statističke metode mašinskog učenja – bajesovske mreže, regresija, kNN, SVM, a posljednjih godina sve više neuronske mreže i dubinske neuronske mreže (deep neural networks).

Predmet ove disertacije biće analiza i rešavanje sljedećih problema:

• Definisanje probabilističke relacione algebre nad fazi relacionom bazom u kojoj su vrijednosti atributa predstavljene posibilističkom raspodjelom (raspodjelom mogućih vrednosti)
• Definisanje fazi klasa ekvivalencije zasnovanih na relaciji blizine na način koji obezbjeđuje da je blizina elemenata ne samo dovoljan već i potreban uslov za njihovu pripadnost, sa određenim stepenom, istim klasama ekvivalencije; izgradnja upitnog jezika za rad sa fazi klasama ekvivelncije
• Primjena fazi klasifikacije na kolekcije digitalizovanih tekstova