Skript Interprozesskommunikation

Das hier frei verfügbare Skript gehört zu einer gleichnamigen Vorlesung, die von Prof. Dr. Lutz Wegner bis zum Sommersemester 2007 gehalten wurde. Davor lief sie bis 1999 unter dem etwas irreführenden Titel „Ausgewählte Themen zu Rechnernetzen“. Behandelt wird die IPC in UNIX-basierten Rechnernetzen. Dazu gehören allgemeine Kenntnisse der Prozessumgebung, die fork- und exec-Systemaufrufe, Lock Files, Signale, Pipes, das Botschaftenkonzept (message queues), Semaphore, Shared Memory, Remote Procedure Calls, Sockets und Threads. Jedes Konzept wird mit kleinen Beispielen besprochen, die in C geschrieben sind. Der Quelltext liegt auf unseren Anlagen vor (für AIX, LINUX, Solaris). Grundlage der Vorlesung und des Skripts ist das ausgezeichnete Buch von John Shapley Gray „Interprocess Communications in UNIX“ aus dem Jahr 1998 bzw. die auf Linux angepasste Auflage desselben Buches „Interprocess Communications in LINUX“ aus dem Jahr 2003.

Programmierung in Pascal

Das hier frei verfügbare Skript gehört zu einer gleichnamigen Vorlesung, die von Prof. Dr. Lutz Wegner bis zum Wintersemester 1998/99 am damaligen Fachbereich 17 Mathematik/Informatik der Universität Kassel gehalten wurde. Thema ist die Einführung in die Programmierung, wie sie am Anfang fast aller Informatik-, Mathematik- und verwandter Ingenieurstudiengänge steht. Hier erfolgt die Einführung mit der Programmiersprache Pascal, die Niklaus Wirth (ehemals ETH Zürich) bereits 1968 entwickelte. Sie gilt als letzte Vertreterin der rein prozeduralen Sprachen und führt in der Regel zu sauber strukturierten Programmen. In der damals auf PCs weit verbreiteten Turbo Pascal Variante geht es auch um Objektorientierung, die charakteristisch für das heutige Programmierparadigma mit Java ist. Alte (und neu geschriebene) Pascal-Programme lassen sich problemlos mit den Free Pascal Open Source Compilern (www.freepascal.org) übersetzen und unter allen gängigen Betriebssystemen zur Ausführung bringen. Wer hierfür eine fachlich präzise und trotzdem vergleichsweise gut lesbare Einführung mit Hinweisen auf guten und schlechten Programmierstil braucht, wird hier fündig und kommt über den Stickwortindex am Ende auch schnell zu Einzelthemen wie Parameterübergabe oder das Arbeiten mit Pointern.

Modellbildung in der algebraischen Kryptoanalyse

In der algebraischen Kryptoanalyse werden moderne Kryptosysteme als polynomielle, nichtlineare Gleichungssysteme dargestellt. Das Lösen solcher Gleichungssysteme ist NP-hart. Es gibt also keinen Algorithmus, der in polynomieller Zeit ein beliebiges nichtlineares Gleichungssystem löst. Dennoch kann man aus modernen Kryptosystemen Gleichungssysteme mit viel Struktur generieren. So sind diese Gleichungssysteme bei geeigneter Modellierung quadratisch und dünn besetzt, damit nicht beliebig. Dafür gibt es spezielle Algorithmen, die eine Lösung solcher Gleichungssysteme finden. Ein Beispiel dafür ist der ElimLin-Algorithmus, der mit Hilfe von linearen Gleichungen das Gleichungssystem iterativ vereinfacht. In der Dissertation wird auf Basis dieses Algorithmus ein neuer Solver für quadratische, dünn besetzte Gleichungssysteme vorgestellt und damit zwei symmetrische Kryptosysteme angegriffen. Dabei sind die Techniken zur Modellierung der Chiffren von entscheidender Bedeutung, so das neue Techniken entwickelt werden, um Kryptosysteme darzustellen. Die Idee für das Modell kommt von Cube-Angriffen. Diese Angriffe sind besonders wirksam gegen Stromchiffren. In der Arbeit werden unterschiedliche Varianten klassifiziert und mögliche Erweiterungen vorgestellt. Das entstandene Modell hingegen, lässt sich auch erfolgreich auf Blockchiffren und auch auf andere Szenarien erweitern. Bei diesen Änderungen muss das Modell nur geringfügig geändert werden.

Eigenschaften chromatischer Polynome

Die Berechnung des 1912 von Birkhoff eingeführten chromatischen Polynoms eines Graphen stellt bekanntlich ein NP-vollständiges Problem dar. Dieses gilt somit erst recht für die Verallgemeinerung des chromatischen Polynoms zum bivariaten chromatischen Polynom nach Dohmen, Pönitz und Tittmann aus dem Jahre 2003. Eine von Averbouch, Godlin und Makowsky 2008 vorgestellte Rekursionsformel verursacht durch wiederholte Anwendung im Allgemeinen einen exponentiellen Rechenaufwand. Daher war das Ziel der vorliegenden Dissertation, Vereinfachungen zur Berechnung des bivariaten chromatischen Polynoms spezieller Graphentypen zu finden. Hierbei wurden folgende Resultate erzielt: Für Vereinigungen von Sternen, für vollständige Graphen, aus welchen die Kanten von Sternen mit paarweise voneinander verschiedenen Ecken gelöscht wurden, für spezielle Splitgraphen und für vollständig partite Graphen konnten rekursionsfreie Gleichungen zur Berechnung des bivariaten chromatischen Polynoms mit jeweils linear beschränkter Rechenzeit gefunden werden. Weiterhin werden Möglichkeiten der Reduktion allgemeiner Splitgraphen, bestimmter bipartiter Graphen sowie vollständig partiter Graphen vorgestellt. Bei letzteren erweist sich eine hierbei gefundene Rekursionsformel durch eine polynomiell beschränkte Laufzeit als effektive Methode. Ferner konnte in einem Abschnitt zu Trennern in Graphen gezeigt werden, dass der Spezialfall der trennenden Cliquen, welcher im univariaten Fall sehr einfach ist, im bivariaten Fall sehr komplexe Methoden erfordert. Ein Zusammenhang zwischen dem bivariaten chromatischen Polynom und dem Matchingpolynom wurde für vollständige Graphen, welchen die Kanten von Sternen mit paarweise voneinander verschiedenen Ecken entnommen wurden, sowie für Bicliquen hergestellt. Die vorliegende Dissertation liefert darüber hinaus auch einige Untersuchungen zum trivariaten chromatischen Polynom, welches auf White (2011) zurückgeht und eine weitere Verallgemeinerung des bivariaten chromatischen Polynoms darstellt. Hierbei konnte gezeigt werden, dass dessen Berechnung selbst für einfache Graphentypen schon recht kompliziert ist. Dieses trifft sogar dann noch zu, wenn man die einzelnen Koeffizienten als bivariate Polynome abspaltet und einzeln berechnet. Abschließend stellt die Arbeit zu vielen Resultaten Implementierungen mit dem Computeralgebrasystem Mathematica bereit, welche zahlreiche Möglichkeiten zu eigenständigen Versuchen bieten.

Identifikation spezieller Funktionen, die durch Rodriguesformeln gegeben sind

Es ist allgemein bekannt, dass sich zwei gegebene Systeme spezieller Funktionen durch Angabe einer Rekursionsgleichung und entsprechend vieler Anfangswerte identifizieren lassen, denn computeralgebraisch betrachtet hat man damit eine Normalform vorliegen. Daher hat sich die interessante Forschungsfrage ergeben, Funktionensysteme zu identifizieren, die über ihre Rodriguesformel gegeben sind. Zieht man den in den 1990er Jahren gefundenen Zeilberger-Algorithmus für holonome Funktionenfamilien hinzu, kann die Rodriguesformel algorithmisch in eine Rekursionsgleichung überführt werden. Falls die Funktionenfamilie überdies hypergeometrisch ist, sogar laufzeiteffizient. Um den Zeilberger-Algorithmus überhaupt anwenden zu können, muss es gelingen, die Rodriguesformel in eine Summe umzuwandeln. Die vorliegende Arbeit beschreibt die Umwandlung einer Rodriguesformel in die genannte Normalform für den kontinuierlichen, den diskreten sowie den q-diskreten Fall vollständig. Das in Almkvist und Zeilberger (1990) angegebene Vorgehen im kontinuierlichen Fall, wo die in der Rodriguesformel auftauchende n-te Ableitung über die Cauchysche Integralformel in ein komplexes Integral überführt wird, zeigt sich im diskreten Fall nun dergestalt, dass die n-te Potenz des Vorwärtsdifferenzenoperators in eine Summenschreibweise überführt wird. Die Rekursionsgleichung aus dieser Summe zu generieren, ist dann mit dem diskreten Zeilberger-Algorithmus einfach. Im q-Fall wird dargestellt, wie Rekursionsgleichungen aus vier verschiedenen q-Rodriguesformeln gewonnen werden können, wobei zunächst die n-te Potenz der jeweiligen q-Operatoren in eine Summe überführt wird. Drei der vier Summenformeln waren bislang unbekannt. Sie wurden experimentell gefunden und per vollständiger Induktion bewiesen. Der q-Zeilberger-Algorithmus erzeugt anschließend aus diesen Summen die gewünschte Rekursionsgleichung. In der Praxis ist es sinnvoll, den schnellen Zeilberger-Algorithmus anzuwenden, der Rekursionsgleichungen für bestimmte Summen über hypergeometrische Terme ausgibt. Auf dieser Fassung des Algorithmus basierend wurden die Überlegungen in Maple realisiert. Es ist daher sinnvoll, dass alle hier aufgeführten Prozeduren, die aus kontinuierlichen, diskreten sowie q-diskreten Rodriguesformeln jeweils Rekursionsgleichungen erzeugen, an den hypergeometrischen Funktionenfamilien der klassischen orthogonalen Polynome, der klassischen diskreten orthogonalen Polynome und an der q-Hahn-Klasse des Askey-Wilson-Schemas vollständig getestet werden. Die Testergebnisse liegen tabellarisch vor. Ein bedeutendes Forschungsergebnis ist, dass mit der im q-Fall implementierten Prozedur zur Erzeugung einer Rekursionsgleichung aus der Rodriguesformel bewiesen werden konnte, dass die im Standardwerk von Koekoek/Lesky/Swarttouw(2010) angegebene Rodriguesformel der Stieltjes-Wigert-Polynome nicht korrekt ist. Die richtige Rodriguesformel wurde experimentell gefunden und mit den bereitgestellten Methoden bewiesen. Hervorzuheben bleibt, dass an Stelle von Rekursionsgleichungen analog Differential- bzw. Differenzengleichungen für die Identifikation erzeugt wurden. Wie gesagt gehört zu einer Normalform für eine holonome Funktionenfamilie die Angabe der Anfangswerte. Für den kontinuierlichen Fall wurden umfangreiche, in dieser Gestalt in der Literatur noch nie aufgeführte Anfangswertberechnungen vorgenommen. Im diskreten Fall musste für die Anfangswertberechnung zur Differenzengleichung der Petkovsek-van-Hoeij-Algorithmus hinzugezogen werden, um die hypergeometrischen Lösungen der resultierenden Rekursionsgleichungen zu bestimmen. Die Arbeit stellt zu Beginn den schnellen Zeilberger-Algorithmus in seiner kontinuierlichen, diskreten und q-diskreten Variante vor, der das Fundament für die weiteren Betrachtungen bildet. Dabei wird gebührend auf die Unterschiede zwischen q-Zeilberger-Algorithmus und diskretem Zeilberger-Algorithmus eingegangen. Bei der praktischen Umsetzung wird Bezug auf die in Maple umgesetzten Zeilberger-Implementationen aus Koepf(1998/2014) genommen. Die meisten der umgesetzten Prozeduren werden im Text dokumentiert. Somit wird ein vollständiges Paket an Algorithmen bereitgestellt, mit denen beispielsweise Formelsammlungen für hypergeometrische Funktionenfamilien überprüft werden können, deren Rodriguesformeln bekannt sind. Gleichzeitig kann in Zukunft für noch nicht erforschte hypergeometrische Funktionenklassen die beschreibende Rekursionsgleichung erzeugt werden, wenn die Rodriguesformel bekannt ist.

Ad elementaria mathematicae

Diese Lecture Note beinhaltet in Ergänzung zu den Elementaria drei Beiträge zur lehramts-orientierten elementaren Mathematik. Ein 1. Beitrag befasst sich mit der von Erich Chr. Wittmann kreierten Weihnachtsaufgabe 2015 zum EINS+EINS. Ein 2. Beitrag führt ein in die Theorie des Releaux-Dreiecks und allgemeinerer Gleichdicke unter Berücksichtigung ihrer technischen Bedeutung. Und schließlich ist eine 3. Beitrag der Einübung der Kreisgeometrie unter Einsatz der Software DYNA-GEO und gelenkmechanischer Aspekte sowie der Einübung des komplexen Rechnens und der Goniometrie gewidmet.

Harmonische Funktionen auf dem Bruhat-Tits-Gebäude der PGL_3 über Funktionenkörpern

Harmonische Funktionen auf dem Bruhat-Tits-Gebäude der PGL(3) über Funktionenkörpern lassen sich als ein Analogon zu den auf der oberen Halbebene definierten klassischen Spitzenformen verstehen. An die Stelle des starken Abklingens der Spitzenformen tritt hier die Endlichkeit des Trägers modulo einer gewissen Untergruppe. Der erste Teil der vorliegenden Arbeit befaßt sich mit der Untersuchung und Charakterisierung dieses Trägers. Im weiteren Verlauf werden gewisse Konzepte der klassischen Theorie auf harmonische Funktionen übertragen. So wird gezeigt, daß diese sich ebenfalls als Fourierreihe darstellen lassen und es werden explizite Formeln für die Fourierkoeffizienten hergeleitet. Es stellt sich heraus, daß sich die Harmonizität in gewissen Relationen zwischen den Fourierkoeffizienten widerspiegelt und sich umgekehrt aus einem Satz passender Koeffizienten eine harmonische Funktion erzeugen läßt. Dies wird zur expliziten Konstruktion zweier quasi-harmonischer Funktionen genutzt, die ein Pendant zu klassischen Poincaré-Reihen darstellen. Abschließend werden Hecke-Operatoren definiert und Formeln für die Fourierkoeffizienten der Hecke-Transformierten einer harmonischen Funktion hergeleitet.