Do not be scared by the mathematics word in the title. Discrete mathematics is the region of mathematics planet that works best with computers. In mathematics we are often satisfied with a single solution to the problem, in computer science this is almost never the case. Among all possible solutions we shall look for the one that can be rewritten as an efficient algorithm (or, not equivalent, can be efficiently rewritten as an algorithm).
Mostly we shall work on problems in graph theory. Let me pin out a pair of problems that we shall keep running into: graph coloring and the problem of disjoint paths. In general, graph coloring problems are hard (in the theoretical sense). Yet if we only consider a subclass of graphs, planar graphs for example, even graph coloring problems become easy enough to work on. The problem of disjoint paths can be generalized into several directions, directed or undirected graphs, vertex- or edge- disjoint, separate terminals or not, looking for bottlenecks, maximizing flows.
Most of the problems we shall work with will become easy on a restricted set of graphs having the property, that a small collection of cops can catch a fast robber, which will lead us to the land of graph decompositions.
Finally we shall dig into a collection of problems from computational geometry: segment intersections, polygon triangulations, Voronoi diagrams and Delaunay triangulations.
The students are required to have sufficient knowledge in the area of algorithms and data structures and have a command on time and space complexity of algorithms.
Student work includes weekly homework assignments and a final exam.
- nosilec: Gašper Fijavž
- nosilec: Tadej Kanduč
- nosilec: Tadej Kanduč
- nosilec: Aljaž Zalar
Computer scientists seek inspiration for solving current problems from various sources. Many times, they find it in nature, as through evolution living organisms have discovered simple and elegant solutions to common problems. A number of known algorithms uses biomimicry. For example, there is an algorithm that in order to find the shortest path to a destination copies the approach of ants, and an algorithm that in order for a fast wireless network setup emulates the flocking of birds. The goal of the course is to present to students the use of the emulation of nature’s time-tested patterns and strategies in order to create products, processes, computer systems and algorithms. Besides the specific knowledge, the students will gain an insight into the theoretical background by means of which they will be able to adapt more easily to the fast changes in current computer and information science. The acquired competences are transferrable as most of the covered topics are applicable to a wide variety of applications.
Lectures overview:
1. Introductory lecture (motivation, fuzzy logic, biomimicry, collective behaviour)
2. Cinder++ (C++ API for creative coding, OpenGL)
3.-7. Fuzzy logic (fuzzy sets, membership functions, FIS, time and fuzzy logic, fuzzy arithmetic, fuzzy type 2, use cases)
8-12. Autonomous agents and collective behaviour (modelling and simulation of collective behaviour, particle systems, boids, SPP model, animats, modelling perception, drives, action selection, verification)
13-15. Artificial life and artificial worlds (learning agents, learning collective behaviour, framstics, stickyfeet, fuzzy evolution and fuzzy genetic algorithms)
Lab work:
Group project in modelling and simulation related to the topics covered in the course.- nosilec: Iztok Lebar Bajec
Computational topology is a relatively new, but lively field somewhere between computer science and mathematics. On the mathematical side it is closely connected to topology. Topology is a somewhat loose form of geometry, where sizes, distances, angles and other numerical measures are not really important. Instead, objects are described using qualitative measures like the number of connected pieces, the number of holes of different shapes and of tunnels. Because of this, topological methods have turned out as useful in several problems where too high precision is unnecessary or even bad. Topological approaches and methods are used for example for analyzing big data sets, for modelling networks, reconstructing objects from samples, in robot motion planning, distributing tasks among processors, and so on.
The course will have a strong emphasis on student projects. Several typical problems suitable for a topological approach will be described. Through solving these problems, the basic topological concepts, structures and algorithms will be introduced, and tested on real data.
To successfully pass this course, the student has to complete 3 homework assignments (deadlines at the ends of months March, April, and May), one group project (in May), and pass a theoretical exam at the end of the semester.
- nosilec: Žiga Virk