• Course code:63828
  • Credits:5
  • Semester: summer
  • Contents
In  this course we will introduce a mathematical model to solve many problems in computer science, such as scheduling, network analysis, pathfinding problems in graphs, hierarchical clustering, parsing,... We will define an algebraic structure called a semiring and show its capability to solve such problems in diverse situations. 

We will study a distinguished class of ordered semirings, which are called dioids. In dioids, we will learn several algorithms for solving linear systems of equations. We will work with matrices with entries from a certain semiring and see, how linear algebra over semirings differs from the classical linear algebra over complex numbers.

As semirings allow far more general and joint solutions to various problems, while reducing the time complexity of existing algorithms, they are a very active research area in computer science. This algebraic structure has properties that are quite different from other classical algebraic structures as groups, rings and fields. Thus, over last decades, many developments in mathematics have been devoted to the research of semirings. A particular class of canonically ordered semirings (also called dioids) come rather naturally into play in connection with algebraic models for many problems arising from computer science.

  • Study programmes
  • Distribution of hours per semester
30
hours
lectures
15
hours
laboratory work
15
hours
tutorials
  • Professor
Course Organiser
Room:R3.08