Magična matematika

diplomski rad

• Naslov (engleski): Magical mathematics
• Autor: Ana Travica
• Mentor: Matija Kazalicki (mentor)
• Član povjerenstva: Matija Kazalicki (predsjednik povjerenstva)
• Član povjerenstva: Mladen Jurak (član povjerenstva)
• Član povjerenstva: Pavle Goldstein (član povjerenstva)
• Član povjerenstva: Zoran Vondraček (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2021-07-22, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Postoji čitav niz zanimljivih trikova za čije se izvođenje koriste znanja iz matematike. U ovom radu istražuju se trikovi i različite primjene koje se oslanjaju na matematički pojam de Bruijnovih nizova. Poglavlje 1 započinje kartaškim trikom koji se koristi teorijom grafova, alatima konačnih polja te kombinatorikom [5]. Tu se uvodi pojam de Bruijnovih nizova te je dan odgovor na pitanje koliko de Bruijnovih nizova postoji i opisane su neke metode za konstrukciju de Bruijnovih nizova, a ona koju valja istaknuti jest konstrukcija pomoću de Bruijnovog grafa. U Poglavlju 2 opisane su primjene de Bruijnovih nizova; načini na koji se oni koriste za robotski vid, u kriptografiji za stvaranje tajnog ključa [3], za rekonstrukciju DNA te računanje udaljenosti između dvije DNA vrpce [4] (gdje se osobito korisnom pokazuje upravo primjena de Bruijnovog grafa). Poglavlje 3 ponovo se vraća na kartaške trikove čija se izvedba bazira na, primjerice, principu produkta te koji uključuju generalizaciju de Bruijnovih nizova, tj. ono što je definirano kao univerzalni ciklusi. U poglavlju 4 dana je programska realizacija de Bruijnovih nizova. Program je rađen u programskom jeziku C# i ima mogućnosti provjere je li zadani niz de Bruijnov, ispis elemenata potrebnih za konstrukciju de Bruijnovog grafa te ispis de Bruijnovih nizova za dane parametre (duljinu alfabeta \(n\) i red niza \(k\)).[6].

Sažetak (engleski)

There is an entire class of interesting tricks that can be performed by using math knowledge. In this master thesis, a variety of tricks and different applications relying on de Bruijn sequences are explored. Chapter 1 starts with a card trick that relies on graph theory, finite fields, and combinatorics[5]. The definition of de Bruijn sequences is given and some methods of construction are described; one of the methodes that should be emphasized is the construction using de Bruijn graph. Also, the answer to the question of the number of de Bruijn sequences is given. In Chapter 2, applications of de Bruijn sequences are described; in robotic vision, in cryptography for the creation of a corrupting string [3], for DNA reconstruction and for calculating the distance between two DNA strings[4] (for which the use of the de Bruijn graph is remarkably practical). Chapter 3 goes back to card tricks which are executed based on, for example, the rule of product, and they include the generalization of de Brujin sequences, that is, what is defined as universal cycles. Chapter 4 gives the program realization of de Bruijn sequences. The program is made in the programming language C# and has the ability to check whether the default string is de Bruijn sequence, print the elements needed to construct a de Bruijn graph and print de Bruijn strings for given parameters (length of the alphabet \(n\) and order of sequence \(k\))[6].

• Ključne riječi: de Bruijnovi nizovi; de Bruijnov graf; kombinatorika; kriptografija; rekonstrukcija DNA; kartaški trikovi; programski jezik C
• Ključne riječi (engleski): de Bruijn sequences; de Bruijn graph; combinatorics; cryptography; DNA reconstruction; card tricks; programming language C
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:377907
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-09-16 12:26:18