Uporaba polkolobarjev z zaprtjem : delo diplomskega seminarja

Slivnik, Nina (avtor), Pretnar, Matija (mentor), Oblak, Polona (komentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: Polkolobar, zaprtje, polkolobar matrik, Jacobijev algoritem, algoritem Warshall-Floyd-Kleene, Gaussova metoda, Haskell
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2019
• PID: 20.500.12556/RUL-110678
• UDK: 512
• COBISS.SI-ID: 18820185
• Datum objave v RUL: 18.09.2019

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Application of closed semirings

Izvleček

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.

• Ključne besede: Semiring, closure, matrix semiring, Jacobi's algorithm, Warshall-Floyd- Kleene's algorithm, Gauss method, Haskell