Discrete modelling

2022/2023
Programme:
Practical Mathematics
Year:
3 year
Semester:
first or second
Kind:
optional
Group:
I1
ECTS:
5
Language:
slovenian
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
0
Tutorial
1
Lab
1
Content (Syllabus outline)

Generation of discrete mathematical structures (subsets, permutations).
Linear programming and the simplex method with the help of a computer.
Dynamical programming (longest increasing subsequence, maximum sum contiguous subsequence, optimal multiplication of matrices, etc.).
Graph algorithms with the help of a computer (shortest paths, minimum spanning tree, Hungarian method, etc.)
Simple modelling with spreadsheets. Computer modelling tools.

Readings

D. L. Kreher, D. R. Stinson: Combinatorial Algorithms: Generation, Enumeration, and Search, CRC, Boca Raton, 1999.
G. Appa, L. Pitsoulis, H. P. Williams (uredniki): Handbook on Modelling for Discrete Optimization, Springer, 2006.
priročniki za uporabljena računalniška orodja / manuals for the computer tools used

Objectives and competences

Students learn basic tools and methods for modelling with discrete mathematical structures. They also learn the necessary computer tools.

Intended learning outcomes

Knowledge and understanding: Understanding of the basic concepts of mathematical modelling, especially with discrete structures. Using computer tools for modelling.
Application: Forecasting the behaviour of the model. Choice of the appropriate tools for the desired goal.
Reflection: Combining mathematics and computer skills from different areas when solving problems.
Transferable skills: Stating real-life problems in a formal mathematical form, study of the models.
Solving problems with the help of a computer.

Learning and teaching methods

lectures, exercises, computer labs, homeworks, consultations

Assessment

2 midterm exams instead of written exam, written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

Matjaž Konvalinka:
KONVALINKA, Matjaž, PAK, Igor. Geometry and complexity of O'Hara's algorithm. Advances in applied mathematics, ISSN 0196-8858, 2009, vol. 42, iss. 2, str. 157-175. [COBISS-SI-ID 15545945]
KONVALINKA, Matjaž, PAK, Igor. Triangulations of Cayley and Tutte polytopes. Advances in mathematics, ISSN 0001-8708, 2013, vol. 245, str. 1-33. [COBISS-SI-ID 16706905]
DOLŽAN, David, KONVALINKA, Matjaž, OBLAK, Polona. Diameters of connected components of commuting graphs. The electronic journal of linear algebra, ISSN 1081-3810, 2013, vol. 26, str. 433-445. [COBISS-SI-ID 16707161]