Tlakovanje trikotnika s polinominami : delo diplomskega seminarja

Hrovat, Dominik (avtor), Vavpetič, Aleš (mentor)

Problem tlakovanja je geometrijski problem pri katerem želimo določen lik pokriti z vnaprej podanimi ploščicami. Ker so tovrstni problemi v splošnem težki, smo definirali označena pokritja, ki nam podajajo potreben pogoj za obstoj tlakovanja. V diplomskem delu smo opisali, kako preidemo iz geometrijskega na algebraičen problem. Našli smo izomorfizem, ki slika ploščice v polinome in dokazali, da je problem iskanja označenega pokritja ekvivalententen problemu vsebovanosti polinoma v idealu. Dokazali smo, da je polinom vsebovan v idealu natanko takrat, ko se reducira v 0 po modulu Gröbnerjeve baze. Za iskanje Gröbnerjeve baze ideala, smo uporabili Buchbergerjev algoritem. Na koncu smo na trikotnem mrežastem območju uporabili izpeljano teorijo in dokazali izrek Conwaya in Lagariasa.

• Jezik: Slovenski jezik
• Ključne besede: celica, polinomina, polinom, ploščica, tlakovanje, označeno pokritje, mrežasto območje, kolobar, redukcija, ideal, sizigija, nasičenost, Gröbnerjeva baza, Buchbergerjev algoritem
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2024
• PID: 20.500.12556/RUL-161810
• UDK: 519.1
• COBISS.SI-ID: 207925251
• Datum objave v RUL: 14.09.2024

HROVAT, Dominik, 2024, Tlakovanje trikotnika s polinominami : delo diplomskega seminarja [na spletu]. Diplomsko delo. [Dostopano 26 april 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=161810

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Signed polyomino tilings of a triangular area

Izvleček

Tiling problem is a geometric problem in which we aim to cover a certain figure with pre-defined tiles. Since such problems are generally challenging, we have defined signed tilings, which give us a necessary condition for the existence of a tiling. In the thesis, we described how we transition from a geometric problem to an algebraic one. We found an isomorphism that maps tiles to polynomials and proved that the problem of finding a signed tiling is equivalent to the problem of polynomial containment in an ideal. We proved that a polynomial is contained in an ideal exactly when it reduces to 0 with respect to the Gröbner basis. To find the Gröbner basis of the ideal, we used Buchberger's algorithm. Finally, on a triangular lattice region, we applied the derived theory and proved Conway's and Lagarias's theorem.

• Ključne besede: cell, polyomino, polynomial, tile, tiling, signed tiling, lattice, ring, reduction, ideal, syzygy, saturation, Gröbner basis, Buchberger algorithm