Tlakovanje trikotnika s polinominami

delo diplomskega seminarja

Dominik Hrovat (Author), Aleš Vavpetič (Mentor)

Abstract

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.

Keywords

celica;polinomine;polinomi;ploščice;tlakovanje;označeno pokritje;mrežasto območje;kolobarji;redukcija;ideal;sizigija;nasičenost;Gröbnerjeva baza;Buchbergerjev algoritem;

Data

Language:	Slovenian
Year of publishing:	2024
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[D. Hrovat ]
UDC:	519.1
COBISS:	207925251
Views:	28
Downloads:	8
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Signed polyomino tilings of a triangular area
Secondary abstract:	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.
Secondary keywords:	cell;polyominos;polynomials;tiles;tiling;signed tiling;lattices;rings;reduction;ideal;syzygy;saturation;Gröbner basis;Buchberger algorithm;
Type (COBISS):	Final seminar paper
Study programme:	0
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages:	31 str.
ID:	25050659