Algebraične rodovne funkcije

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[L. Opravš]
UDC:	51(043.2)
COBISS:	124538627
Views:	268
Downloads:	77
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Algebraic generating functions
Secondary abstract:	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.
Secondary keywords:	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;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	43 str.
ID:	16487845