Asymptotic Analysis of Lattice Paths and Related Structures

hackl… ist der Titel des 1. Platzes des Roland-Mittermeir-Preises 2015/2016 und wurde vom Förderverein Technische Fakultät mit EUR 1.500,–ausgezeichnet. Dem Autor und Preisträger, Herrn Dipl.-Ing. Benjamin Hackl, wurde der Preis im Rahmen des Festakts 10-jähriges Jubiläum der Fakultät für Technische Wissenschaften übergeben und die Arbeit wird hier kurz vorgestellt:

Zusammenfassung. Während sich die klassische Kombinatorik „nur“ mit dem Abzählen diskreter Objekte beschäftigt, interessieren wir uns im Rahmen der analytischen Kombinatorik für präzise Analysen des entsprechenden asymptotischen Verhaltens. In weniger technischen Worten sind wir also an einer möglichst genauen Charakterisierung des Wachstums von gewissen Klassen kombinatorischer Objekte interessiert. Für eine solche asymptotische Analyse werden Resultate aus einem breiten Spektrum von mathematischen Disziplinen, wie beispielsweise der klassischen Kombinatorik, der Funktionentheorie, und auch der Wahrscheinlichkeitstheorie verwendet.

Innerhalb dieser Masterarbeit spielen neben den im Titel angedeuteten Gitterpfaden auch Bäume, beides klassische diskrete Objekte mit zahllosen Anwendungen in verschiedenen na- turwissenschaftlichen und technischen Bereichen, eine zentrale Rolle. Die Arbeit ist in drei Kapitel gegliedert. In Kapitel 1, Preliminaries, geht es um die für die asymptotische Analy- se nötigen Grundlagen und Werkzeuge aus Kombinatorik (z.B. kombinatorische Klassen und erzeugende Funktionen), Funktionentheorie (Singularitätenanalyse, Mellin-Transformation), sowie Wahrscheinlichkeitstheorie (Grenzverteilungen, Martingale).

Mit Hilfe der in Kapitel 1 skizzierten Techniken geht es dann in Kapitel 2, Analysis of Lattice Paths, um die asymptotische Analyse von Gitterpfaden. Nach einer kurzen Einleitung in Ab- schnitt 2.1, in der die Terminologie geklärt wird, werden in den Abschnitten 2.2 sowie 2.3 di- verse elementare Gitterpfadklassen (Brücken, Mäander, Exkursionen) asymptotisch analysiert.

Abschnitt 2.4 bildet den Kern der Masterarbeit, in ihm werden sogenannte kulminierende Pfade untersucht. Das sind Gitterpfade mit Schritten ↗ und ↘, die auf minimaler Höhe starten und auf maximaler Höhe enden. Zu den wichtigsten Bausteinen dieser Analyse zählen die Erkenntnis, dass die wohlbekannten Chebyshev-Polynome eine zentrale Rolle spielen, sowie die asymptotische Entwicklung von Binomialkoeffizienten (2n,n−α) in einem zentralen Bereich. Neben Resultaten wie der asymptotischen Grenzverteilung und beliebig präzisen asymptotischen Entwicklungen für die Anzahl kulminierender Pfade gegebener Länge, wurde in diesem Kontext auch eine zahlentheoretische Vermutung von Zhao aus dem Jahr 2010 bewiesen.

Die Inhalte dieses Abschnittes wurden in einer geringfügig adaptierten Version 2016 in den Annals of Combinatorics publiziert.

In Kapitel 3, Analysis of Trees, liegt der Fokus schließlich auf der asymptotischen Analyse von Bäumen, wobei besonderer Wert auf das Aufzeigen der Zusammenhänge zwischen Gitterpfaden und Bäumen gelegt wird.

Zuletzt sei noch erwähnt, dass die aufwändigeren Berechnungen (insbesondere in Abschnitt 2.4) mit der Hilfe des quelloffenen Computermathematiksystems SageMath durchgeführt wurden. Der entsprechende Sourcecode findet sich in Anhang A der Arbeit. Im weiteren Umfeld der Arbeit bildete diese Implementation auch einen Teil der Motivation, ein Proposal für ein Google Summer of Code-Projekt einzureichen, welches genehmigt und erfolgreich von mir durch- geführt wurde, sodass ein Modul für asymptotische Entwicklungen mittlerweile zum Basisbestandteil von SageMath gehört.

Posted in News, Studienabgänger | Leave a comment

Schreib einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

This blog is kept spam free by WP-SpamFree.