**Seminar on
Applied Mathematics**

**PROGRAM**

Matematički fakultet

Fakultet organizacionih nauka

JUPIM

MI SANU, Knez Mihailova 36, sala 305

**
**

**
Utorak, 02.12.2008. u 14:15, Sala 305, MI SANU:
**

**
Dejan
Mišković, Novi Sad
JEDNO REŠENJE OPTIMIZACIJE ASEMBLERSKOG KODA TEHNIKOM
ZAMENE REDOSLEDA INSTRUKCIJA
**

**
Sadrzaj: U radu se razmatra tehnika optimizacija visokog nivoa
DSP (digital signal processing) prevodioca sa otvorenom protocnom strukturom koristeci kompaktovanje
koda na medjujeziku
niskog nivoa (low-level intermediate representation). Izlaganje je
fokusirano na
- razloge za uvodjenje komponente za kompaktovanje koda - obrazlozenje osnovne ideje pomenute tehnike
optimizacije - opis algoritma - rezultate optimizacije i granicne slucajeve - primenu rezultata
optimizacije.
**

**
Utorak, 09.12.2008. u 14:15, SALA 305, MI SANU:
**

**
Slavik Jablan, Visoka škola strukovnih studija za informacione i
komunikacione tehnologije
ON KNOTS AND EVERYTHING...
**

**
Abstract: Knot theory is a new and rich field of mathematics.
Although "real" knots are familiar to everyone and many ideas in
knot theory can be formulated in everyday language, it is an area
abundant with open questions.
One of our main ideas is to avoid obvious classification of knots
and links according to their number of components. For this reason
knots and links are referred to as $KL$s and treated together
whenever possible. $KL$s are denoted by Conway symbols, a
geometrical-combinatorial way to describe and derive $KL$s. The
same notation is used in the {\it Mathematica} based computer
program {\it LinKnot}. {\it LinKnot} is not only a supplementary
computer program, but the best and most efficient tool for
obtaining almost all of the knot-theory results that belong to the
field of {\it experimental mathematics}.
Hands-on computations using {\it Mathematica} or the {\it
webMathematica} package {\it LinKnot} along with detailed
illustrations facilitate better learning and understanding. The
program {\it LinKnot} can be downloaded from the web address
http://www.mi.sanu.ac.yu/vismath/linknot/ and used as a powerful
educational and research tool for experimental mathematics--
implementation of Caudron's ideas and the Conway notation enables
working with large families of knots and links. The electronic
version of the book and the program {\it LinKnot} that provides
{\it webMathematica} on-line computations are available at the
address http://math.ict.edu.yu/.
Each knot theory problem is accompanied with the corresponding
{\it LinKnot} function that enables the reader to actively use the
program {\it LinKnot}, not only for illustrating some problems,
but for computations and experimentation. {\it LinKnot} is
software open to future development: a reader can change it or add
new functions. For the systematic and exhaustive derivation of
$KL$s we have accepted the concept proposed by J.H. Conway and A.
Caudron, supported and used in a form adapted for computer
implementation. As a prerequisite for the use of the Conway
notation, the complete list of basic polyhedra up to 20 crossings
is given in the program {\it LinKnot}.
The key idea is the `vertical'' classification of $KL$s into
well-defined categories-- worlds, subworlds, classes, and {\it
families}, according to new sets of recursively computed
invariants. Patterns obtained from computing $KL$ invariants imply
the existence of more general $KL$ family invariants that agree
with all proposed conjectures. We strongly believe that the
concept of family invariants will be placed on a firm theoretical
foundation in the future. New $KL$ tables, organized according to
$KL$ families can be downloaded from the address
http://www.mi.sanu.ac.yu/vismath/Appendix.pdf.
After a short graph-theoretical introduction, we consider
different notations for $KL$s: Gauss, Dowker, and Conway notation,
along with their advantages and disadvantages. All basic $KL$
invariants such as the minimum crossing number, minimum writhe,
linking number, unknotting or unlinking number, cutting number,
and $KL$ properties such as chirality, periodicity, unlinking gap,
and braid family representatives of $KL$s will be discussed. We
will consider two important problems: recognition and generation
of $KL$s. As recognition criteria we can use $KL$ colorings, $KL$
groups, and more powerful tools such as polynomial $KL$
invariants. Again, we try to show that polynomial $KL$ invariants
can be recovered from the Conway notation and recursively computed
for $KL$ families.
We will also make a short excursion into the history of knot
theory and place an emphasis on the beauty, universality, and
diversity of knot theory through various non-standard applications
such as mirror curves, fullerenes, self-referential systems, and
$KL$ automata.
**

**
Utorak, 16.12.2008. u 14:15, sala 305, MI BG:
**

**
Dragan Urošević, Matematički institut SANU
REŠAVANJE PROBLEMA LINEARNOG PROGRAMIRANJA UZ
POMOĆ ILOG CPLEX ALATA
**

**
Sadrzaj: ILOG CPLEX je komercijalni softverski paket namenjen za
resavanje optimizacionih problema definisanih u formi linearnog
programa. Matematicki institut SANU od pre nekoliko godina ima
ovaj softver, a ove godine je nabavljena nova verzija 11.2. Cilj
ovog predavanja je da se siri krug korisnika upozna sa nacinom koriscenja ILOG CPLEX-a, kao i sa nekim njegovim dodatnim
mogucnostima. Naglasak je na povezivanju CPLEX rutina sa korisnickim programima napisanim u jezicima C ili C++.
Pored CPLEX paketa, Institut je nabavio i softverske pakete AMPL
(za algebarsko modeliranje problema linearnog, nelinearnog i
celobrojnog programiranja) kao i CP (za Constraint Programming
aplikacije). Ovi paketi jos nisu detaljno prouceni, pa ce biti tema nekog narednog izlaganja.
**

**
Utorak, 23.12.2008. u 14:15, sala 305, MI BG:
**

**
Dragan Stevanović, Prirodno-matematički fakultet, Niš
THE LAPLACIAN COEFFICIENTS AND THE LAPLACIAN-LIKE
ENERGY OF GRAPHS
**

**
Abstract: Let $G$ be a simple graph with the Laplacian matrix $L$
and let $P(G,x)=\sum_{k=0}^n (-1)^k c_k x^{n-k}$ be the
characteristic polynomial of $L$. The coefficients $c_k$ are
called the Laplacian coefficients of $G$.
Using the fact that in acyclic graphs $c_k(G)=m_k(S(G))$, where
$m_k$ is the number of $k$-matchings and $S(G)$ is the subdivision
graph of $G$, Zhou and Gutman, and independently Mohar, proved
that for any $n$-vertex tree $T$, $c_k(S_n)\leq c_k(T)\leq
c_k(P_n)$, where $S_n$ and $P_n$ are the $n$-vertex star and path,
respectively.
We argue that, in this particular case, it is more fruitful to go
back to the basics and exploit an old characterization of $c_k$ by
Kelmans and Chelnokov in terms of the number of spanning forests
of $G$. This characterization enables to generalize the results of
Mohar and to introduce a handful of graph transformations which
monotonically change all Laplacian coefficients at once. As a
consequence, we have found, together with Aleksandar Ili\cj, for
example, that the cycle has largest, while the star with an
additional edge between two of its leaves has the smallest
Laplacian coefficients among unicyclic graphs.
The results on the Laplacian coefficients will then be promoted to
the study of the Laplacian-like energy, which is defined as
$LEL(G)=\sum_{i=1}^n \sqrt{\mu_i}$, where
$\mu_1\geq\dots\geq\mu_n=0$ are the eigenvalues of $L$. This will
be established by using an important lemma that, if for two graphs
$G$ and $H$, $c_k(G)\leq c_k(H)$ for $k=1,\dots,n$, then
$LEL(G)\leq LEL(H)$.
**

**
**

**
RUKOVODIOCI SEMINARA
**

**
Vera Kovačević-Vujčić
Milan Dražić
**