Uporaba polkolobarjev z zaprtjem : delo diplomskega seminarja

Slivnik, Nina (author), Pretnar, Matija (mentor), Oblak, Polona (comentor)

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
• Typology: 2.11 - Undergraduate Thesis
• 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