Föstudaginn 19. janúar kl. 15:00, mun Guðjón Helgi Auðunsson kynna meistraprófsritgerð sýna. Fyrirlesturinn fer fram í stofu 138 í VR2 og verður fluttur á ensku.
Titill: Additive functionals with product toll functions on Galton-Watson trees
Ágrip: Additive functionals on binary trees represent the cost of many divide-and-conquer algorithms. In this study, we derive the growth rate of the mean in two cases, which generalize known results. The first case involves a more general toll function that allows for a product of two sequences, which we call the product toll function. We focus on a two-dimensional toll function represented as the product of one-dimensional toll functions in each variable. We analyse this function in depth when each sequence is the size of the subtree with the same exponent, and derive the limiting distribution using the method of moments. We then calculate the growth rate of the mean of the tree functional when we allow for possibly distinct exponents. Finally, we consider unary-binary trees in a similar situation, using singularity analysis on generating functions to determine the growth rate.
Leiðbeinandi Guðjóns er Sigurður Örn Stefánsson.
Prófdómari er Hermann Þórisson, prófessor emeritus.