Binarni polinomi

diplomski rad

• Autor: Jure Šiljeg
• Mentor: Goranka Nogo (mentor)
• Član povjerenstva: Goranka Nogo (predsjednik povjerenstva)
• Član povjerenstva: Zvonimir Tutek (član povjerenstva)
• Član povjerenstva: Dijana Ilišević (član povjerenstva)
• Član povjerenstva: Marko Tadić (č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: 2017-02-24, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo definirali binarne polinome i opisali operacije nad njima. Objasnili smo ključne točke algoritama, dali primjere izvrijednjavanja i analizirali složenosti uz popratne komentare. Za množenje i potenciranje smo ponudili nekoliko verzija algoritama dok su dijeljenje i zbrajanje zbog, respektivno, okvira rada i jednostavnosti, obrađeni na prigodi suvisao način. Faktorizaciju smo, pak, detaljno razradili i u konačnici objasnili kako doći do generaliziranog pristupa u rastavu bilo kojeg polinoma. Zaključili smo da je hibridni Karatsubin brži od Karatsubinog, a Karatsubin od naivnog množenja. Testna vremena se slažu s teorijskim predviđanjima za algoritme množenja. Također je jasno postalo da se polinomi mogu posebno efikasno zbrajati i oduzimati zbog jednostavnosti algoritma, a dali smo rezultate i za ostale operacije. Vidljivo je da za složenije ulaze ne možemo tako brzo dobiti rezultate: dijeljenje u slučaju djelitelja sa stupnjem preko milijun; faktorizacija svih polinoma stupnja većeg od dvadeset.

Sažetak (engleski)

In this thesis we presented binary polynomials through definition and operations on them. We explained key points of algorithms, gave examples of evaluation, pseudocodes of algorithms itself and analysed time complexity with comments in form suitable for appropriate thesis. We also offered few versions of algorithm for multiplication and exponentiation, and gave appropriate care and explanation with pseudocodes for division and addition. Factorization was described in detail: all necessary key steps for general approach in getting factors. We concluded that hybrid Karatsuba has better time complexity than Karatsuba, and Karatsuba is, in Big-O notation, faster than simple multiplication algorithm. Testing times are in accordance with theoretical predictions for multiplication algorithms. Also, addition and subtraction may be extremely fast because of simplicity of algorithm itself and structure of GF(2). We provided results for the rest of operations, too. It is obvious that we are not able to get results very fast when input size grows: division in case of divident’s degree higher than one million and factorization of polynomials with degree higher than twenty.

• Ključne riječi: binarni polinom; Karatsubin; operacije nad binarnim polinomima
• Ključne riječi (engleski): binary polynomials; Karatsuba; operations on binary polynomials
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:712904
• 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: 2017-04-28 10:53:30