Seminar on Computer Science and Applied Mathematics
PROGRAM
Upravni odbor Matematickog instituta SANU je na nedavnoj sednici doneo odluku da se dosadasnji Seminar za primenjenu matematiku, sada nazove Seminar za racunarstvo i primenjenu matematiku, a u cilju potenciranja znacaja racunarstva kao jedne od oblasti delatnosti Instituta. Istovremeno, Upravni odbor doneo je odluku o osnivanju Odeljenja za racunarstvo i primenjenu matematiku i vezao rad novog odeljenja za rad Seminara za racunarstvo i primenjenu matematiku.
Utorak, 10.05.2016. sala 301f, MI SANU
14:15-15:00 Dragan Radojevic, Institut Mihajlo Pupin, Beograd
REALNO-VREDNOSNA REALIZACIJA KONACNE BULOVE ALGEBRE: INTERPOLATIVNA BULOVA
ALGEBRA (IBA) - TEORIJSKE OSNOVE I PRIMENA
Rezime: Konvencionalne vise-vrednosne logike, fazi logika, teorija fazi
skupova, fazi relacije, za razliku od klasicne (dvo-vrednosne) logike,
klasicne teorije skupova, teorije klasicnih relacija, nisu u Bulovom okviru,
tj. nisu Bulovski konzistentna generalizacija klasicnog slucaja. U ovom
preglednom radu daju se osnove originalne realno-vrednosne realizacije
konacne Bulove algebre - Interpolativna Bulova algebra (IBA) koja cuva sve
aksiome i teoreme u vise-vrednosnim i/ili realno-vrednosnim slucajevima.
Ovaj pristup bice ilustrovan na reprezentativnim primerima.
15:00-15:45 Vladimir Jankovic, Matematicki fakultet, Beograd
KVADRATNE FORME VISE REALNIH PROMENLjIVIH
Rezime: Kvadratnu formu promenljivih cemo definisati kao homogen polinom
drugog stepena, kao sto je to uradjeno u udzbeniku Kurs v.sse. algebr. A. G.
Kurosa. Dakle, kvadratna forma promenljivih je funkcija koja se moze
zadati formulom
Da bi koeficijenti bili jednoznacno odredjeni, uvodi se da uslov vazi za
. Pod matricom kvadratne forme podrazumevamo (simetricnu) matricu . Ako sa
oznacimo stubac matricu visine sastavljen od promenljivih , , onda
kvadratnu formu mozemo zapisati u matricnom obliku
(Napomena. Na desnoj strani ove jednakosti stoji matrica reda , koju cemo
identifikovati sa brojem, koji je njen jedini clan.)
Za realnu kvadratnu formu se kaze da je pozitivno semidefinitna ako je ,
za svako . Za realnu kvadratnu formu se kaze da je pozitivno definitna
ako je pozitivno semidefinitna i ako je samo za . Neophodni uslovi za
pozitivnu definitnost i pozitivnu semidefinitnost glase:
Ako je realna kvadratna forma pozitivno definitna, onda su svi dijagonalni
minori njene matrice pozitivni.
Ako je realna kvadratna forma pozitivno semidefinitna, onda su svi
dijagonalni minori njene matrice nenegativni.
Dovoljni uslovi za pozitivnu definitnost i pozitivnu semidefinitnost glase:
Realna kvadratna forma je pozitivno definitna ako su svi vodeci minori njene
matrice pozitivni.
Realna kvadratna forma je pozitivno semidefinitna ako su svi dijagonalni
minori njene matrice nenegativni.
Napred formulisani dovoljan uslov za pozitivnu definitnost je poznat u
literaturi kao Silvesterov kriterijum. Moze se naci u mnogim udzbenicima
linearne algebre. Dovoljan uslov za pozitivnu semidefinitnost se retko
pojavljuje u udzbenicima, iako je veoma vazan za izucavanje konveksnih
funkcija
i ekstremalnih problema. Ovde cemo izloziti njegov dokaz koji nismo nasli u
poznatoj nam literaturi. Takodje cemo dati i neka njegova poboljsanja.
Utorak, 17.05.2015. u 14:15h, Sala 301f, MI SANU:
Slobodan Cuk, CEO TESLAco
NIKOLA TESLA I ENERGETSKA ELEKTRONIKA
Rezime: Nikola Tesla je podario svetu polifazni sistem generisanja i
prenosenja elektricne energije na velike distance. Taj metod je i dalje
neprevazidjen i posle 120 godina jedini nacin kojim se stotine megavata
elektricne energije prenose na sve delove sveta brzinom svetlosti! Tesla
je svoj sistem upotpunio Teslinim generatorima i motorima, koji i danas
pokrecu industriju celog sveta!
Kljucna odlika Teslinog sistema je da ne smesta elektricnu energiju vec je
prenosi. Sadasnja Energetska Elektronika je ogranicena time da svi tipovi
konvertora (DC-DC, AC-DC and DC-AC) smestaju svu energiju u samim
konvertorima. Neposredan rezultat je da velicina konvertora
eksponencijalno raste sa snagom (energijom), a istovremeno smanjuje
dramaticno efikasnost i rezultira u velikim gubicima.
Na predavanju ce biti prikazan novi prilaz Energetskoj Elektronici koji se
zasniva na konvertorima koji NE SMESTAJU vec samo PRENOSE energiju
pretvarajuci je iz jednog oblika u drugi, kao na primer, AC-DC konvertori
za punjenje baterija elektricnih automobila. To onda omogucava da rapidni
punjac baterija od 50kW bude smesten u samom automobilu i napuni baterije
za desetak minuta!
Novi sistem povezuje Teslin AC polifazni sistem transmisije i izmenjuje
energiju sa DC sistemom transmisije baziranom na solarnim celijama koje
prirodno generisu DC snagu na malom DC naponu.
Edisonov sistem DC transmisije nije uspeo jer je bio baziran na nefikasnom
DC prenosu na 100V DC. Teslin AC sistem je pobedio jer je koristio
Faradejev AC transformator da prvo prebaci 440V AC napon na 440,000V napon
vrlo male struje i prenese efikasno velike snage na veliku daljinu.
Tada nije postojao metod da se 100V DC napon pretvori u visok DC napon od
100,000V DC za prenos na daljinu.
Novi konvertorski sistem sada to omogucava po prvi put zahvaljujuci
glavnoj osobini da DC-DC konvertori novog tipa ne smestaju vec samo
prenose energiju!
Utorak, 24.05.2015. u 14:15h, Sala 301f, MI SANU:
14:15-15:00 Aleksandar Cvetkovic, Masinski fakultet, Beograd
GAUSSIAN LIKE QUADRATURE RULES
Abstract: In this talk we present some results in the theory of the
quadrature rules. We present some new types of quadrature rules, e.g.,
interval quadrature rules, quadrature rules with operator values and
quadrature rules with complex nodes and weights. We present results on
existence of the quadrature rules and we present numerical procedures that
can be applied for the construction of quadrature rules.
15:00-15:45 Boban Marinkovic, Tehnolosko-metalurski fakultet, Beograd
TEOREME ALTERNATIVE
Teoreme alternative imaju vaznu ulogu u dobijanju uslova optimalnosti za
razne klase problema optimizacije. Teorija koja se tice linearnih teorema
alternative je dobro poznata i moze se naci u mnogim knjigama i radovima
koji
se bave teorijom optimizacije i primenama. Ipak, beskonacno dimenziona
uopstenja pomenutih teorema nisu tako poznata i predstavljaju interesantno
polje za izucavanje. Takodje, neki rezultati koji se ticu pomenutih
uopstenja su
nekorektni, pa su i odgovarajuci uslovi optimalnosti, dobijeni primenom
takvih teorema, pogresni. U ovom predavanju razmotricemo sisteme strogih i
nestrogih konveksnih nejednakosti u cilju dobijanja korektnih teorema
alternative za takve sisteme. Pokazacemo neke kontraprimere za postojece
rezultate poznate u literaturi.
10:00-10:10 Vera Kovacevic-Vujcic, Matematicki institut SANU, Beograd
UVODNA REC
10:10-10:35 Zoran Ognjanovic, Matematicki institut SANU, Beograd
DIGITALIZACIJA NACIONALNE BASTINE
Rezime: U izlaganju ce biti predstavljeni rezultati grupe istrazivaca
Matematickog instituta SANU koji se bave digitalizacijom bastine. Pre svega
bice reci o glavnim projektima na kojima se radi u proteklom periodu:
- elib, Electronic editions of Serbian mathematical journals
- eCatalog of cultural monuments in Serbia
- Serbia Forum, digital library of Serbian cultural heritage
- Digitalna Narodna biblioteka Srbije
- Collaborative EuropeaN Digital/Archival Infrastructure (CENDARI),
- FP7-INFRA-2011-1.1.3.
10:35-11:00 Nenad Mladenovic, Mathematical Institute SANU, Belgrade
VARIABLE NEIGHBORHOOD PROGRAMMING - A NEW AUTOMATIC PROGRAMMING METHOD IN
ARTIFICIAL INTELLIGENCE
Coauthors: Souhir Elleuch, Bassem Jarboui, MODILS , University of Sfax,
Tunisie
Abstract: Automatic programming is an efficient technique that has
contributed to an important development in the artificial intelligence
field. We introduce a new technique called Variable Neighborhood Programming
(VNP) that was inspired by the principle of Variable Neighborhood Search
(VNS) algorithm. VNP starts from a single solution presented by a program,
and the search for the good quality global solution continues by exploring
different neighborhoods. The goal of our algorithm is to generate a good
representative program adequate to a selected problem. VNP takes the
advantages of the systematic change of neighborhood structures. To explain
more the algorithm process we apply VNP in a simple sample in symbolic
regression problem. Then the effectiveness and the good convergence of this
algorithm is proved by testing it on benchmark problems drawn from time
series prediction and classification areas. We successfully compared it with
the related techniques.
11:00-11:25 Veljko Milutinovic, Faculty of Electrical Engineering, Belgrade
DATAFLOW SUPERCOMPUTING FOR BIG DATA
Abstract: This presentation analyses the essence of DataFlow SuperComputing,
defines its advantages and sheds light on the related programming model.
DataFlow computers, compared to ControlFlow computers, offer speedups of 20
to 200 (even 2000 for some applications), power reductions of about 20, and
size reductions of also about 20. However, the programming paradigm is
different, and has to be mastered. The talk explains the paradigm, using
Maxeler as an example, and sheds light on the ongoing research in the field.
Examples include SignalProcessing, GeoPhysics, WeatherForecast, OilGas,
DataEngineering, DataMining, etc. A recent study from Tsinghua University in
China reveals that, for Shallow Water Weather Forecast, which is a BigData
problem, on the 1U level, the Maxeler DataFlow machine is 14 times faster
than the Tianhe machine, which is rated #1 on the Top 500 list (based on
Linpack, which is a smalldata benchmark). Given enough time, the talk also
gives a tutorial about the programming in space, which is the programming
paradigm used for the Maxeler dataflow machines (established in 2014 by
Stanford, Imperial, Tsinghua, and the University of Tokyo). The talk
concludes with selected examples and a tool overview (appgallery.maxeler.com
and webIDE.maxeler.com).
11:25-11:40 Pauza za kafu
11:40-12:05 Miodrag Mihaljevic, Matematicki institut SANU, Beograd
DVE DECENIJE RAZVOJA KRIPTOLOGIJE U MATEMATICKOM INSTITUTU SANU
Rezime: Kriptologija je kljucna matematicka disciplina na osnovu koje se
izgradjuje informaciona i sajber bezbednost. Ovo izlaganje sumira dostignuca
tokom dve decenije razvoja kriptologije u MI-SANU. Ukazuje se na ostvarene
rezultate u domenu osnovnih istrazivanja i tehnoloski orijentisanih
projekata
u kojima je MI-SANU postao vodeca nacionalna i regionalna institucija u
oblasti kriptologije i njenih primena za ostvarivanje informacione i sajber
bezbednosti. Posebno se ukazuje i na niz internacionalnih saradnji koje su
bitno doprinele visokoj medjunarodnoj reputaciji MI-SANU.
12:05-12:30 Jozef Kratica, Matematicki institut SANU, Beograd
VISEDIMENZIONI PROBLEM PODELE SKUPA NA DVE PARTICIJE
Koautori: Jelena Kojic, Aleksandar Savic, Matematicki fakultet u Beogradu
Rezime: Na predavanju ce biti prikazane karakteristike datog NP-teskog
problema (Multidimensional two-way number partitioning problem - MDTWNPP),
kao i nacini za njegovo resavanje. Detaljno ce biti prikazana primena dve
metaheuristicke metode: metoda promenljivih okolina (Variable Neighborhood
Search - VNS) i metaheuristika zasnovana na elektromagnetizmu (EM).
Predlozeni problem je uopstenje problema podele skupa na dve particije, pri
cemu se dele skupovi vektora umesto skupova brojeva, pri cemu je uopsteni
problem daleko tezi za resavanje, kako za egzaktne, tako i za
metaheuristicke
metode. Ideja okolina zasnovanih na k-zameni (k-swap neighborhoods), iako
jednostavna, znacajno doprinosi lokalizaciji dobrih resenja u metodi
promenljivih okolina. Procedura skaliranja dodatno poboljsava mehanizam
privlacenja/odbijanja u EM metodi. Obe metode (VNS i EM) koriste zajednicku
brzu proceduru lokalnog pretrazivanja zasnovanu na 1-zameni (1-swap).
Eksprimentalni rezultati i direktno poredjenje na 210 standardnih instanci,
pokazuju da primenjene metode u proseku nadmasuju rezultate ostalih metoda
za resavanje ovog problema.
12:30-12:55 Natasa Krejic, Faculty of Natural Sciences and Mathematics,
Novi Sad
INEXACT RESTORATION METHODS FOR STOCHASTIC PROBLEMS
Abstract: The problems we consider are stated in the form of large (possibly
infinite) sum of functions, coming from machine learning or stochastic
programming with the objective function given in the form of mathematical
expectation. The number of functions tends to be very large and thus the
main challenge is to define computationally affordable methods. We will
discuss the general framework of Inexact Restoration that allow us to work
with low level accuracy initially and gradually, but not monotonically,
increase the accuracy at the end of optimization process. The proposed
approach is completely based on the progress on optimization algorithm and
requires no heuristic elements. Furthermore, for constrained problems one
can treat infeasibility as inexactness and apply the same approach. The
convergence theory includes results for both cases - classical convergence
for the problem with finite number of loss functions and almost sure
convergence in the case of infinite sum of functions. Some numerical results
will be also presented.
12:55-14:00 Koktel
14:00-14:25 Bosko Jovanovic, Matematicki fakultet, Beograd
O NUMERICKOJ APROKSIMACIJI NEKIH NESTANDARDNIH KONTURNIH PROBLEMA ZA
PARCIJALNE DIFERENCIJALNE JEDNACINE
Rezime: Prenos energije i/ili mase je od fundamentalnog znacaja za mnoge
fizicke, hemijske, bioloske, industrijske i druge procese. Takvi procesi se
najcesce matematicki opisuju parcijalnim diferencijalnim jednacinama.
Procesi koji se odvijaju u prostorno ogranicenoj oblasti i/ili tokom
konacnog vremenskog perioda modeluju se pomocu granicnih, odnosno
pocetno-granicnih problema za parcijalne jednacine cije resavanje, pored
same
jednacine, zahteva poznavanje dodatnih (pocetnih i/ili granicnih) uslova.
Razlicite karakteristike sredine u kojoj se posmatrani proces odvija opisuju
se koeficijentima jednacine. Tako se u slucaju homogene (nehomogene) sredine
dobijaju jednacine s konstantnim (promenljivim) koeficijentima.
U primenama, narocito u inzenjerstvu, cesto se srecu slojevite ili
kompozitne
strukture, pri cemu se osobine pojedinih slojeva mogu znacajno razlikovati
od osobina okolnog materijala. Slojevi mogu imati strukturnu, termicku,
opticku ili elektromagnetsku ulogu, itd. Matematickim modelovanjem prenosa
energije i mase u oblastima sa slojevima dobijaju se tzv. transmisioni
problemi. Na granicama slojeva koeficijenti odgovarajuce parcijalne
jednacine cesto imaju prekide, sto dovodi do prekida (.preloma.) resenja.
Ponasanje resenja na takvim unutrasnjim granicama (interfejsima) opisuje se
razlicitim uslovima saglasnosti.
Zamena klasicnih izvoda izvodima razlomljenog reda omogucava modelovanje
mnogih dosada neistrazenih procesa. Zato parcijalne jednacine razlomljenog
reda predstavljaju oblast koja se u poslednje vreme veoma intenzivno
razvija.
U ovom radu cemo razmotriti nekoliko nestandardnih konturnih problema
opisanog tipa. Posebna paznja ce biti posvecena numerickim metodama za
njihovo
resavanje.
Kljucne reci: transmisioni problem, interfejs, uslovi saglasnosti, izvod
razlomljenog reda, prostori Soboljeva, slaba resenja, apriorne ocene,
konacne
razlike, greska, konvergencija.
14:25-14:50 Mirjana Cangalovic, Fakultet organizacionih nauka, Beograd
PROBLEM METRICKE DIMENZIJE NA GRAFOVIMA
Rezime: Razmatra se jedan NP - tezak optimizacioni problem na grafovima -
problem nalazenja metricke dimenzije jednog neorijentisanog grafa. Daje se
pregled nekih teorijskih rezultata vezanih za metricku dimenziju posebnih
klasa grafova, kao sto su Hamingovi grafovi, konveksni politopi, prizma
grafovi i hiperkubovi. Osim toga diskutuju se i neki slicni problemi -
problem odredjivanja stroge metricke dimenzije i problem odredjivanja
minimalnog rezolvirajuceg skupa cvorova grafa.
14:50-15:15 Predrag Stanimirovic, Prirodno-matematicki fakultet, Nis
RECURRENT NEURAL NETWORK APPROACH TO COMPUTATION OF GENERALIZED INVERSES
Abstract: The topic of this lecture is numerical computation of generalized
inverses by means of neural networks in both the time-invariant and
time-varying case.
Two gradient-based recurrent neural networks (RNNs) for generating outer
inverses with prescribed range and null space in the time-invariant case are
considered. Each of the proposed RNNs is based on the dynamic equation which
is, for itself, a generalization of dynamic equations proposed earlier for
computing the Moore-Penrose and the Drazin inverse under the condition of
zero initial state. The main problem in the time-invariant case is to avoid
restrictions on the spectrum of certain matrices. The RNNs are composed from
a number of independent subnetworks. Two additional dynamic state equations
and corresponding gradient based RNNs for generating the class of outer
inverses are proposed using general representation of outer inverses.
Appropriate Zhang functions (ZFs) and initiated Zhang Neural Networks (ZNNs)
are proposed for computing outer inverse in time-varying case.
The most important particular cases are considered.
15:15-15:30 Pauza za kafu
15:30-15:55 Miodrag Zivkovic, Matematicki fakultet, Beograd
MOGUCE KARDINALNOSTI PROSTORA VRSTA BULOVIH MATRICA
Rezime: Skup Bulovih matrica reda n sa matricnim mnozenjem i Bulovim
operacijama i, ili je semigrupa. Neka je prostor vrsta matrice A, tj.
potprostor generisan vrstama A. Analogno, neka je prostor kolona A;
poznato je da je . Neka je skup vrednosti za sve matrice . Ocigledno
je . Konieczny (1992) je dokazao da su elementi skupa u intervalu samo
brojevi , i postavio je hipotezu da je . Li i Zhang (1995) su dokazali da
ova hipoteza nije tacna, jer za n>6 broj nije u . Hong (2000) je dokazao
da skup za ne sadrzi kompletne intervale i , a sadrzi brojeve i .
Breen i Hume (2001) su odredili skup . Posle obimnog izracunavanja Zivkovic
(2006) je dobio skup . Ispostavilo se da je Zivkoviceva hipoteza o tome
koji elementi iz intervala pripadaju skupu tacna . njen dokaz uz pomoc
racunara izveo je Bojan Vuckovic.
15:55-16:20 Bozidar Radenkovic, Fakultet organizacionih nauka, Beograd
REFORMA OBRAZOVANjA U RACUNARSKIM NAUKAMA I INFORMACIONIM TEHNOLOGIJAMA -
NOVA RAZVOJNA SANSA SRPSKE PRIVREDE
Rezime: U ovom predavanju daje se analiza postojeceg stanja i predlog za
unapredjenje visokoskolskog obrazovanja u oblasti racunarskih nauka i
informacionih tehnologija. Analiza IT trzista, kako u Srbiji, tako i u
svetu, pokazuje povecanu potrebu za kadrovima koji poseduju znanja i vestine
iz savremenih oblasti racunarskih nauka i informacionih tehnologija. Oblasti
za koje se znanja traze su potpuno nova, slabo su zastupljena, ili se ne
mogu
naci u kurikulumima srpskih visokih skola i fakulteta. To su: cloud
computing, tehnologije mobilnog poslovanja, internet inteligentnih uredjaja,
sveprisutno racunarstvo, drustveni mediji, virtuelna realnost, big data, kao
i agilne metode za upravljanje softverskim projektima. Prateci preporuke ACM
i
IEEE, koje se inoviraju na 5-10 godina, visokoskolske institucije u Srbiji
ne uspevaju da dovoljno brzo inoviraju kurikulume i obrazuju kadrove sa
znanjem koje se trazi na trzistu. Kreiranje okruzenja za pruzanje usluga u
oblastima savremenih racunarskih nauka i informacionih tehnologija moze
biti razvojna sansa za Srbiju, jer nisu potrebna velika infrastrukturna
ulaganja, vec samo reforma kurikuluma, ulaganja u obrazovanje, kao i veci
stepen saradnje akademskih institucija sa privredom. Kao primer inoviranog
kurikuluma, u predavanju se daje primer doktorskih i master studija
Elektronskog poslovanja, na Fakultetu organizacionih nauka Univerziteta u
Beogradu.
16:20-16:45 Boban Stojanovic, Prirodno-matematicki fakultet, Kragujevac
PROBLEM IZNAD CUPRIJE NA DRINI
Rezime: Hidroelektrana "Visegrad" nalazi se na reci Drini, uzvodno od grada
Visegrada i vec u toku prve godine njene eksploatacije, nizvodno od brane je
uocena pojava vise izvora. Oni su ukazivali na postojanje podzemih karstnih
pukotina kroz koje je voda ponirala, prouzrokujuci gubitke iz akumulacije,
koji su se vremenom povecavali i sa prvobitnih 1,4 m3/s (1990. godine)
dosegli 14,7 m3/s (2012. godine). Dalje intenziviranje ove pojave je moglo
prouzrokovati razne ekonomske i bezbednosne posledice, pa je bilo neophodno
izvrsiti sanaciju ugradjivanjem granulisanog materijala u podzemne supljine.
Da
bi se u procesu sanacije donosile ispravne odluke, uspostavljen je sistem za
podrsku odlucivanju, koji u priblizno realnom vremenu procenjuje uspesnost
realizacije tehnoloskih postupaka i pomaze u planiranju buducih aktivnosti.
U
cilju realizacije ovakvog sistema razvijen je odgovarajuci matematicki
model,
cija je zadatak bio da, koriscenjem dobijenih osmatranja, u kontinuitetu
vrsi
procenu prostornog rasporeda glavnih karstnih provodnika, njihovih fizicih
karakteristika, kao i hidraulickih velicina u sistemu. Ovaj multi-model je
ukljucivao hidraulicki model podzemnog tecenja, model transporta
rastvorljivih
materija i model transporta i sedimentacije granulisanog materijala, koji su
podrazumevali primenu metode konacnih elemenata, metode konacnih razlika,
vremenski diskretne simulacije i visekriterijumsku optimizaciju zasnovanu na
evolucionim algoritmima. Resavanje ovako slozenih problema u prihvatljivom
vremenskom roku je zahtevalo primenu racunarstva visokih performansi i
angazovanje velikih racunarskih resursa.Zahvaljujuci razvijenim matematickim
modelima, metodama, algoritmima i softverskim komponentama, tokom 2015.
godine je uspesno izvrsena sanacija brane, tako da je procurivanje svedeno
na
4,47m3/s.
RUKOVODIOCI SEMINARA
MI SANU
Vera Kovačević-Vujčić
Milan Dražić
FON
Zorica Bogdanovic
Marijana Despotovic-Zrakic
IEEE
Bozidar Radenkovic