Akademska 2021/22. godina

U okviru predavanja bice dat neformalan uvod u jednu sasvim novu granu kriptografije i teorije racunarstva, neinteraktivne sazete dokaze - SNARKs, kao i njihovo formalno prosirenje - ZKSnarks. Predmet istrazivanja se svodi na dokazivanje znanja resenja NP problema ciji se rezultat moze proveriti u linearnom ili polinomijalnom vremenu. Neka od glavnih pitanja su i:

• Da li je moguce dokazati bilo koje NP izracunavanje?
• Da li je moguce sakriti neke delove bez gubitka korektnosti?

Bice dat osvrt na istoriju moderne kriptografije i teorije izracunavanja kao i osnove trenutnih ZkSnarks sistema. Bice dat uvod u neke od aplikacija modernih kriptografskih alata kao sto su Circom, Halo2, Artworks, Snarkjs, … Zatim kratak formalan uvod u fundamentalne teoreme izracunavanja i neinteraktivnih dokaza: Soundness, Correctness, Honest Verifier Zero Knowledge i praktican primer Schnorr Zero Knowledge argumenta za znanje diskretnog logaritma.

Fokus drugog dela predavanja bice na aplikativnom delu i primeni ZkSnarkova u skaliranju decentralizovanih distribuiranih sistema i privatnim finansijama. Bice predstavljene neke od modernih ideja kao sto su ZeroKnowledge virtuelna masina, Rollups, FunctionalCommitments, OrchardCircuits, ...

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

У раду су размотрене особине и односи протеина у интерактомима одабраних подскупова протеома вируса SARS-CoV-2 – мембрански протеин, неструктурни протеини, као и целокупан протеом. Као особине од интереса издвојени су степен неуређености протеина према различитим критеријумима, као и степен повезаности (број суседа) одговарајућих чворова у мрежи. Вирусни интерактоми такође су спојени са оним људског плућног ткива, како би се омогућила анализа веза између протеина вируса и домаћина, али и испитала повезаност тих интеракција са степеном неуређености интерактора.

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

Programiranje ograničenja je deklarativna programska paradigma u okviru koje se problemi koji se rešavaju modeluju skupom promenljivih koje uzimaju vrednosti iz zadatih domena i skupom ograničenja koje rešenje problema, izraženo dodelom vrednosti promenljivama, mora da zadovoljava. U okviru ovog izlaganja daćemo kratak uvod u programiranje ograničenja, a zatim ćemo razmotriti jedan od aktuelnih problema u ovoj oblasti koji se tiče enumeracije minimalnih nezadovoljivih podskupova ograničenja u slučaju da je posmatrani problem programiranja ograničenja nezadovoljiv. Poslednje dve decenije objavljen je veliki broj radova na ovu temu, a pristupi koji se u njima javljaju su raznovrsni (upotreba dualnosti sa pogađajućim skupovima, upotreba naprednih mogućnosti modernih SAT/SMT rešavača u slučaju da je dati problem programiranja ograničenja SAT/SMT problem, heuristike zasnovane na lokalnoj pretrazi, itd.). Osim samih algoritama, istovremeno se radi i na razvijanju brojnih optimizacionih tehnika, koje su univerzalne za sve algoritme. U okviru ovog izlaganja posvetićemo pažnju tehnici poznatoj kao rotacija modela. Enumeracija minimalnih nezadovoljivih podskupova ima brojne primene, od kojih je značajno pomenuti VLSI dizajn, bi-dekompoziciju logičkih funkcija, proveru tipova promenljivih u kodu, validaciju teorija, itd.

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

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

Истраживања у оквиру рада на докторској дисертацији биће усмерена на вишекритеријумске дискретне лоацијске проблеме. У истраживањима се полази од два дискретна локацијска проблема: Проблем максималног покривања локација са преференцијама корисника (енг. Maximal Covering Loacation Problem with Customer Preferences, MCLPCP) и уопштени проблем постављања регенератора у оптичким мрежама (енг. Generalized Regenerator Location Problem, GRLP). Најпре су разматране постојеће једнокритеријумске варијанте ових проблема, при чему је предложена нова варијанта MCLPCP са ограниченим буџетом која до сада није разматрана у литератури. Затим су формулисане нове вишекритерјумске варијанте ова два проблема које боље одсликавају реалну ситуацију у односу на варијанте ових проблема са једном функцијом циља.

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