Algebraične rodovne funkcije

diplomsko delo

Luka Opravš (Avtor), Matjaž Konvalinka (Mentor)

Povzetek

Kadar preučujemo neko zaporedje, si pogosto pomagamo tako, da ga predstavimo z rodovno funkcijo. Rodovno funkcijo lahko potem zapišemo v kakšni enačbi, iz katere lahko izpeljemo različne lastnosti zaporedja. To nam pomaga pri računanju členov našega zaporedja in iskanju zvez, ki veljajo zanje. Veliko kombinatoričnih problemov daje preštevalno zaporedje z rodovno funkcijo, ki ustreza kakšni D-končni enačbi. Iz take enačbe lahko izpeljemo linearno rekurzivno enačbo s polinomskimi koeficienti, ki ji zadoščajo vsi dovolj pozni členi našega zaporedja. Taki rekurzivni enačbi pravimo P-rekurzija in z njo lahko člene našega zaporedja računamo zelo hitro, poleg tega pa nam pomaga bolje razumeti problem, s katerim se ukvarjamo. D-končno enačbo, ki ji ustreza rodovna funkcija našega zaporedja, je običajno težko uganiti iz samega opisa problema. Izpeljemo jo lahko iz algebraične enačbe, ki jo dobimo iz preprostih rekurzivnih zvez, ki veljajo za naše zaporedje. Začetne člene zaporedja, ki jih potrebujemo za uporabo P-rekurzije, lahko izračunamo direktno iz algebraične enačbe, s primerjavo koeficientov pri potencah x. V diplomski nalogi je predstavljen program, ki sprejme algebraično enačbo in poišče P-rekurzijo ter z njo hitro izračuna izbrano število začetnih členov katerekoli izmed rešitev dane algebraične enačbe.

Ključne besede

rodovne funkcije;algebraične rodovne funkcije;D-končne rodovne funkcije;P-rekurzija;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[L. Opravš]
UDK:	51(043.2)
COBISS:	124538627
Št. ogledov:	268
Št. prenosov:	77
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Algebraic generating functions
Sekundarni povzetek:	When studying a sequence, it is often helpful to represent it with a generating function. The generating function can then be used in equations from which various properties of the sequence can be derived. From such equations we can often compute the terms of our sequence and derive relations that apply to them. Many combinatorial counting problems can be represented with a generating function that solves some D-finite equation. From such an equation, we can derive a linear recursive equation with polynomial coefficients that holds for all sufficiently late coefficients of our sequence. Such a recursive equation is called a P-recursion, and with it we can calculate the terms of our sequence quickly. It also helps us better understand our problem. It is often difficult to guess the D-finite equation from the problem description itself. We can derive it from an algebraic equation that can be obtained from simple recursive relations that hold for our sequence. The initial terms of the sequence that we need to use the P-recursion can be computed directly from the algebraic equation by comparing the coefficients at powers of x. In this diploma thesis, we present a program that accepts an algebraic equation and finds the P-recursion, and with it quickly computes the selected number of initial terms of any solution of the given algebraic equation.
Sekundarne ključne besede:	combinatorics;generating functions;algebraic generating functions;D-finite generating functions;P-recursion;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Kombinatorika (matematika);Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	43 str.
ID:	16487845