Výpočetní složitost základních algoritmů počítačové algebry

• Název práce v češtině: Výpočetní složitost základních algoritmů počítačové algebry
• Název v anglickém jazyce: Computational complexity of basic computer algebra algorithms
• Akademický rok vypsání: 2007/2008
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: doc. RNDr. David Stanovský, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.11.2007
• Datum zadání: 22.11.2007
• Datum a čas obhajoby: 29.06.2009 00:00
• Datum odevzdání elektronické podoby: 29.06.2009
• Datum proběhlé obhajoby: 29.06.2009
• Oponenti: Mgr. Jan Zvánovec

Zásady pro vypracování

Cílem práce je pečlivá statistická analýza složitosti vybraných algoritmů pro polynomiální aritmetiku na náhodných datech. Zajímat nás budou zejména algoritmy na výpočet NSD a faktorizace polynomů, jak v případě konečných těles, tak celočíselných polynomů.
Pro testy se využije implementace těchto algoritmů v knihovně NTL, případně vlastní vylepšení těchto algoritmů. Výsledkem by měly být grafy závislosti výpočetního času na parametrech jako stupeň polynomu, počet nenulových členů, či velikost koeficientů. Výsledky budou zpracovány pomocí jednoduché regresní analýzy k získání odhadu střední složitosti.

Seznam odborné literatury

Joachim von zur Gathen, Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Cambridge 1999,

K. O. Geddes, S. R. Czapor, G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston 1992,

Karel Zvára, Regresní analýza, Academia, Praha 1989,

a další dle pokynů vedoucího práce