Title Magična matematika
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
Terms of use
Created on 2021-09-16 12:26:18