Tlakovanje trikotnika s polinominami

delo diplomskega seminarja

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2024
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[D. Hrovat ]
UDK:	519.1
COBISS:	207925251
Št. ogledov:	28
Št. prenosov:	8
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Signed polyomino tilings of a triangular area
Sekundarni povzetek:	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.
Sekundarne ključne besede:	cell;polyominos;polynomials;tiles;tiling;signed tiling;lattices;rings;reduction;ideal;syzygy;saturation;Gröbner basis;Buchberger algorithm;
Vrsta dela (COBISS):	Delo diplomskega seminarja/zaključno seminarsko delo/naloga
Študijski program:	0
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Strani:	31 str.
ID:	25050659