{"id":5965,"date":"2017-11-17T21:50:17","date_gmt":"2017-11-17T19:50:17","guid":{"rendered":"https:\/\/www.ftf.or.at\/?p=5965"},"modified":"2017-11-17T21:50:17","modified_gmt":"2017-11-17T19:50:17","slug":"asymptotic-analysis-of-lattice-paths-and-related-structures","status":"publish","type":"post","link":"https:\/\/www.ftf.or.at\/?p=5965","title":{"rendered":"Asymptotic Analysis of Lattice Paths and Related Structures"},"content":{"rendered":"
\n
\n
\n

\"hackl\"<\/a>\u2026 ist der Titel des\u00a01. Platzes des Roland-Mittermeir-Preises 2015\/2016<\/strong>\u00a0und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit\u00a0EUR 1.500,\u2013<\/strong>ausgezeichnet. Dem Autor und Preistr\u00e4ger, Herrn\u00a0Dipl.-Ing. Benjamin Hackl<\/strong>, wurde der Preis im Rahmen des Festakts\u00a010-j\u00e4hriges Jubil\u00e4um der Fakult\u00e4t f\u00fcr Technische Wissenschaften<\/a>\u00a0<\/strong>\u00fcbergeben und die Arbeit wird hier kurz vorgestellt:<\/p>\n

Zusammenfassung. Wa\u0308hrend sich die klassische Kombinatorik \u201enur\u201c mit dem Abza\u0308hlen diskreter Objekte bescha\u0308ftigt, interessieren wir uns im Rahmen der analytischen Kombinatorik fu\u0308r pra\u0308zise Analysen des entsprechenden asymptotischen Verhaltens. In weniger technischen Worten sind wir also an einer mo\u0308glichst genauen Charakterisierung des Wachstums von gewissen Klassen kombinatorischer Objekte interessiert. Fu\u0308r 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.<\/p>\n

Innerhalb dieser Masterarbeit spielen neben den im Titel angedeuteten Gitterpfaden auch Ba\u0308ume, 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 fu\u0308r die asymptotische Analy- se no\u0308tigen Grundlagen und Werkzeuge aus Kombinatorik (z.B. kombinatorische Klassen und erzeugende Funktionen), Funktionentheorie (Singularita\u0308tenanalyse, Mellin-Transformation), sowie Wahrscheinlichkeitstheorie (Grenzverteilungen, Martingale).<\/p>\n

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 gekla\u0308rt wird, werden in den Abschnitten 2.2 sowie 2.3 di- verse elementare Gitterpfadklassen (Bru\u0308cken, Ma\u0308ander, Exkursionen) asymptotisch analysiert.<\/p>\n

Abschnitt 2.4 bildet den Kern der Masterarbeit, in ihm werden sogenannte kulminierende Pfade untersucht. Das sind Gitterpfade mit Schritten \u2197 und \u2198, die auf minimaler Ho\u0308he starten und auf maximaler Ho\u0308he enden. Zu den wichtigsten Bausteinen dieser Analyse za\u0308hlen die Erkenntnis, dass die wohlbekannten Chebyshev-Polynome eine zentrale Rolle spielen, sowie die asymptotische Entwicklung von Binomialkoeffizienten (2n,n\u2212\u03b1) in einem zentralen Bereich. Neben\u00a0Resultaten wie der asymptotischen Grenzverteilung und beliebig pra\u0308zisen asymptotischen Entwicklungen fu\u0308r die Anzahl kulminierender Pfade gegebener La\u0308nge, wurde in diesem Kontext auch eine zahlentheoretische Vermutung von Zhao aus dem Jahr 2010 bewiesen.<\/p>\n

Die Inhalte dieses Abschnittes wurden in einer geringfu\u0308gig adaptierten Version 2016 in den Annals of Combinatorics publiziert.<\/p>\n

In Kapitel 3, Analysis of Trees, liegt der Fokus schlie\u00dflich auf der asymptotischen Analyse von Ba\u0308umen, wobei besonderer Wert auf das Aufzeigen der Zusammenha\u0308nge zwischen Gitterpfaden und Ba\u0308umen gelegt wird.<\/p>\n

Zuletzt sei noch erwa\u0308hnt, dass die aufwa\u0308ndigeren Berechnungen (insbesondere in Abschnitt 2.4) mit der Hilfe des quelloffenen Computermathematiksystems SageMath durchgefu\u0308hrt 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 fu\u0308r ein Google Summer of Code-Projekt einzureichen, welches genehmigt und erfolgreich von mir durch- gefu\u0308hrt wurde, sodass ein Modul fu\u0308r asymptotische Entwicklungen mittlerweile zum Basisbestandteil von SageMath geho\u0308rt.<\/p>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

\u2026 ist der Titel des\u00a01. Platzes des Roland-Mittermeir-Preises 2015\/2016\u00a0und wurde vom F\u00f6rderverein Technische Fakult\u00e4t mit\u00a0EUR 1.500,\u2013ausgezeichnet. Dem Autor und Preistr\u00e4ger, Herrn\u00a0Dipl.-Ing. Benjamin Hackl, wurde der Preis im Rahmen des Festakts\u00a010-j\u00e4hriges Jubil\u00e4um der Fakult\u00e4t f\u00fcr Technische Wissenschaften\u00a0\u00fcbergeben und die Arbeit wird … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"sfsi_plus_gutenberg_text_before_share":"","sfsi_plus_gutenberg_show_text_before_share":"","sfsi_plus_gutenberg_icon_type":"","sfsi_plus_gutenberg_icon_alignemt":"","sfsi_plus_gutenburg_max_per_row":"","footnotes":""},"categories":[9,12],"tags":[],"class_list":["post-5965","post","type-post","status-publish","format-standard","hentry","category-studienabganger","category-news"],"_links":{"self":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/5965","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5965"}],"version-history":[{"count":4,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/5965\/revisions"}],"predecessor-version":[{"id":5990,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=\/wp\/v2\/posts\/5965\/revisions\/5990"}],"wp:attachment":[{"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5965"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5965"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ftf.or.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5965"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}