Schwartz - Zippelov teorem i neke njegove primjene

diplomski rad

• Autor: Klara Nesterović
• Mentor: Juraj Šiftar (mentor)
• Član povjerenstva: Juraj Šiftar (predsjednik povjerenstva)
• Član povjerenstva: Goran Muić (član povjerenstva)
• Član povjerenstva: Vedran Krčadinac (član povjerenstva)
• Član povjerenstva: Goranka Nogo (č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: 2015-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu izložen je rezultat poznat pod nazivom Schwartz - Zippelova lema ili Schwartz - Zippelov teorem. Tema rada pripada pretežno algebri, ali ima značajne primjene u drugim matematičkim područjima kao što je na primjer teorija algoritama, te kombinatorika. Rad se sastoji od tri poglavlja. U uvodu je ukratko opisana tema i cilj rada. Prvo poglavlje sadrži kratku povijest nastanka teorema, različite oblike rezultata pojedinih autora, te kratki opis pojmova korištenih u samom radu. Drugo poglavlje sastoji se od iskaza i dokaza Schwartz - Zippelovog teorema, a u trećem poglavlju izložene su neke primjene tog teorema na probleme koji se mogu svesti na testiranje jednakosti polinoma. Takvi su, primjerice, problem postojanja savršenog sparivanja u grafu i ispitivanje svojstva asocijativnosti u grupoidu. Uz svaku primjenu navedeni su i prikladni primjeri.

Sažetak (engleski)

In this diploma thesis we present the result usually called the Schwartz-Zippel lemma or the Schwartz-Zippel theorem. The nature of this theorem is basically algebraic, but it has significant applications in other areas of mathematics, such as the theory of algorithms and combinatorial theory. The thesis consists of three chapters. The main theme and objective are briefly described in the introduction. The first chapter contains a short history of the theorem’s origins, various forms of the main results by different authors and some comments of basic concepts related to this topic. The statement and a proof of the Schwartz-Zippel theorem are given in the second chapter, together with the general outline of its applications. The third and final chapter consists of some applications to problems which can be reduced to polynomial identity testing, including the existence of a perfect matching in a graph and testing of the associativity property in a groupoid

• Ključne riječi: Schwartz - Zippelova lema; testiranje jednakosti polinoma
• Ključne riječi (engleski): Schwartz-Zippel lemma; polynomial identity testing
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:928517
• Studijski program: Naziv: Matematika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike (mag. educ. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-28 09:49:04