Magična matematika

master's thesis

• Title (english): Magical mathematics
• Author: Ana Travica
• Mentor: Matija Kazalicki (mentor)
• Committee member: Matija Kazalicki (predsjednik povjerenstva)
• Committee member: Mladen Jurak (član povjerenstva)
• Committee member: Pavle Goldstein (član povjerenstva)
• Committee member: Zoran Vondraček (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-07-22, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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].

Abstract (english)

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].

• Keywords: de Bruijnovi nizovi; de Bruijnov graf; kombinatorika; kriptografija; rekonstrukcija DNA; kartaški trikovi; programski jezik C
• Keywords (english): de Bruijn sequences; de Bruijn graph; combinatorics; cryptography; DNA reconstruction; card tricks; programming language C
• Language: croatian
• URN:NBN: urn:nbn:hr:217:377907
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-09-16 12:26:18