Uporaba polkolobarjev z zaprtjem : delo diplomskega seminarja

Slivnik, Nina (author), Pretnar, Matija (mentor), Oblak, Polona (co-mentor)

Polkolobar je algebrska struktura, ki podpira seštevanje in množenje, med katerima veljajo določene relacije. Ko dodamo še unarno operacijo zaprtje, dobimo polkolobar z zaprtjem. V diplomskem delu si bomo ogledali, kako definiramo zaprtje na polkolobarju matrik, tri algoritme za izračun zaprtja matrike ter nekaj primerov uporabe polkolobarjev z zaprtjem v programskem jeziku Haskell: dosegljivost v grafu, poti v grafu, polinome in potenčne vrste in 0-1 nahrbtnik s ponavljanjem.

• Language: Slovenian
• Keywords: Polkolobar, zaprtje, polkolobar matrik, Jacobijev algoritem, algoritem Warshall-Floyd-Kleene, Gaussova metoda, Haskell
• Work type: Final seminar paper
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2019
• PID: 20.500.12556/RUL-110678
• UDC: 512
• COBISS.SI-ID: 18820185
• Publication date in RUL: 18.09.2019

Secondary language

• Language: English
• Title: Application of closed semirings

Abstract

Semiring is an algebraic structure where we have two binary operations ('addition' and 'multiplication') and relations between them. If we add a unary operation called closure we obtain a closed semiring. In this work we define a closed semiring of matrices, describe three algorithms for computing the closure and some applications of closed semirings in Haskell: reachability in graphs, paths in graphs, polynomials and power series and 0-1 knapsack with repetition.

• Keywords: Semiring, closure, matrix semiring, Jacobi's algorithm, Warshall-Floyd- Kleene's algorithm, Gauss method, Haskell