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ć