Seminar on Computer Science and Applied Mathematics
PROGRAM
Matematički Institut SANU, Beograd
Knez Mihajlova 36
Fakultet organizacionih nauka, Univerzitet u Beogradu,
Jove Ilica 154
IEEE Chapter Computer Science (CO-16) Belgrade, Republic of Serbia
SEMINAR ZA RAČUNARSTVO I PRIMENJENU MATEMATIKU
MI SANU, Knez Mihailova 36, sala 301f
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.
PLAN RADA SEMINARA ZA MAJ 2016. GODINE
Obelezavanje jubileja Matematickog instituta SANU
Odeljenje za racunarstvo primenjenu matematiku daje svoj doprinos obelezavanju jubileja Matematickog instituta odrzavanjem jednodnevnog skupa pod nazivom Dan Odeljenja za racunarstvo i primenjenu matematiku u petak 27.5.2016. godine i organizovanjem dva prosirena sastanka Seminara za racunarstvo i primenjenu matematiku u utorak 10.5.2016. i utorak 24.5.2016. godine.
PROSIRENI SASTANCI 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, 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.
DAN ODELjENjA ZA RACUNARSTVO I PRIMENjENU MATEMATIKU
10:00-10:10 Vera Kovacevic-Vujcic,
Matematicki institut SANU, Beograd
UVODNA REČ
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 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