Department of Algorithms and Systems Modelling | Faculty of Electronics, Telecommunications and Informatics at the Gdańsk University of Technology

Department of Algorithms and System Modeling was created in September 2003 as a successor of the activity of Department of Foundations of Computer Science in the Institute of Informatics. The department takes care of didactics within specialization Internet Technology and Algorithms that focuses on algorithmic and technological aspects of computer science, and is in charge of the scientific group SFERA. Department's staff conducts research in the field of design and analysis of algorithms for selected problems of discrete optimization. In particular, these include models and methods of graph coloring, task scheduling in multiprocessor environment, construction of class-teacher timetables, computer-aided estimation of Ramsey and Shannon numbers, and reconfiguration phylogenetic trees. Scientific personnel of our Department has published approximately 30 monographs and textbooks as well as over 150 articles in impact-factor journals. The main position is a book entitled Graph Colorings published by American Mathematical Society in 2004. Middle-age scientists with Doctor of Science degree (dr hab.) constitute the main part of Department. This group has been awarded with numerous prestigious prizes such as awards granted by the Prime Ministry of Poland, MEN, PTI, PAN, FNP, Hevelius, GTN Polityka journal, "Primus inter Pares" "Red Rose", Prof. Lipski Award — to mention just a few examples. A former member of the Department, dr. hab. Adrian Kosowski, has been elected to Polish Academy of Young Scientists.

Department of Algorithms and System Modeling cooperates with Polish Universities (e.g. Gdańsk University, University of Zielona Góra) and foreign scientific institutions (e.g. Rochester Institute of Technology (USA), Memorial University of Newfoundland (Canada), LaBRI (France), Aix-Marseille University (France)).

Department of Algorithms and System Modeling conducts research in the scope of design and analysis of selected topics in discrete optimization and operations research. In particular these include:

- algorithms in graph theory, especially graph coloring in various modes and models,

- task scheduling in multiprocessor systems,

- algorithms for school timetabling,

- selected topics in computational biology,

- artificial intelligence in programming of logical games,

- computing of small Ramsey numbers and computer-aided estimating of Shannon capacity.

The study of concepts and models of graph theory aims at estimating the computational complexity of various generalizations of classical coloring of the vertices and edges of a graph arising in practical applications.

As long as task scheduling is concerned, our research is focused on the construction of schedules which are optimal with respect of makespan and mean flow time criterion. An additional aim is construction of schedules for processors working in an open shop and flow shop. A special attention is laid on scheduling of deteriorating tasks.

Construction of school timetables aims at designing of efficient algorithms for scheduling class-teacher timetables for university faculty, which would result in a solution to the problem which is not worse than a solution produced by a human being.

In programming of logical games we are interested in techniques for computer learning of a strategy on the basis of observations from already performed games.

Within Ramsey and Shannon problems we focus on the estimation of small 2- and 3-color Ramsey numbers as well as on lower bounds on the Shannon capacity of noisy channels. This research is supported with massive computation in a distributed environment.