beginners

Das Beispiel der dinierenden Philosophen ist eines der populärsten Standardprobleme aus dem Bereich der Parallelprogrammierung. Es erlaubt, die Kooperation der beteiligten Threads in einer lebendigen Simulation darzustellen.

Wir stellen eine Standard-Lösung für dieses Problem vor und gehen dabei vor allem auf die Klasse std::mutex und das RAII-Idiom näher ein. Basiswerkzeuge zur nebenläufigen Programmierung in C++ wie std::async, std::future oder auch std::scoped_lock werden eingesetzt.

Ist eine Menge von n Elementen gegeben, so bezeichnet man die möglichen Anordnungen aller dieser n Elemente als Permutationen (lat. permutare: vertauschen). Die Berechnung der Permutationen einer beliebigen Menge von Elementen steht im Mittelpunkt dieser Fallstudie. Als Elemente verwenden wir zunächst Zeichen, also char-Variablen. Dies soll aber verallgemeinerbar sein, also auch für Variablen eines beliebigen Datentyps funktionieren.

Für zwei Zeichen A und B gibt es nur die zwei Permutationen AB und BA. Drei Zeichen, angenommen A, B und C, können hingegen in sechs verschiedenen Permutationen dargestellt werden: ABC, ACB, BAC, BCA, CAB und CBA. Sind alle n Elemente voneinander verschieden, was wir in dieser Aufgabe zu Grunde legen, so gibt es dafür n! Anordnungen (n-Fakultät).

Die Fakultät ist in der Mathematik eine Funktion, die einer natürlichen Zahl n das Produkt aller natürlichen Zahlen kleiner und gleich dieser Zahl zuordnet: n! = 1 * 2 * 3 * … * n. In der Kombinatorik spielt die Fakultät ebenfalls eine große Rolle, weil n! die Anzahl der Möglichkeiten ist, unterschiedliche Gegenstände der Reihe nach anzuordnen. Bei diesen Überlegungen kommen auch Binomialkoeffizienten ins Spiel. Sie geben an, auf wie viele verschiedene Arten man k Objekte aus einer Menge von n verschiedenen Objekten auswählen kann.

Sowohl Fakultäten als auch Binomialkoeffizienten weisen eine unangenehme Eigenschaft auf: Ihre Werte können sehr schnell sehr groß werden – und sind damit in Variablen des Typs long oder size_t nicht mehr darstellbar. Ein Satz von Legendre verschafft hier Abhilfe: Er befasst sich mit der Frage, wie oft ein Primfaktor in der Primfaktorzerlegung von n! für ein n ∈ N vorkommt – um damit eine alternative Darstellung für Fakultäten und Binomialkoeffizienten zu ermöglichen, die das Problem des Überlaufs umgehen kann.

Wir betrachten in dieser Fallstudie die Berechnung von Fakultäten und Binomialkoeffizienten sowohl in ihrer klassischen Definition als auch mit Hilfe des Satzes von Legendre als Produkt von Primfaktorzerlegungen.

Die Notation eines mathematischen Ausdrucks, wie wir ihn aus der Mathematik kennen, zum Beispiel 2 * (7 + 5), bezeichnet man als Infix-Notation. Das Gegenstück dazu heißt Postfix-Notation oder UPN (umgekehrte polnische Notation, engl. reverse polish notation oder abgekürzt RPN). Die umgekehrte polnische Notation wurde 1920 von dem Polen Jan Lukasiewicz erfunden, um mathematische Ausdrücke ohne Vorrangregeln (Klammern) schreiben zu können.

In dieser Fallstudie behandeln wir einen Taschenrechner für arithmetische Ausdrücke in UPN-Darstellung. Reguläre Ausdrücke (std::sregex_iterator, smatch) und Type Traits (std::is_integral, std::is_floating_point) fließen neben anderen Modern C++–Sprachmitteln in der Implementierung mit ein.

Im Jahr 1857 hat der Amerikaner Samuel Morse das Morsealphabet erfunden. Damals war es noch nicht möglich, gesprochenen Text über Telegrafenleitungen zu übermitteln. Also verwendete Samuel Morse für jeden Buchstaben kurze und lange Piepstöne (Punkte und Striche). Diese Punkte und Striche kann man aber auch als Lichtblitze, Pfeiftöne etc. weitergeben. So ist es möglich, ganze Worte mit anderen über große Distanzen zu „sprechen”.

Schreiben Sie zwei Funktionen encode und decode, die eine lesbare Nachricht in Morseschrift verschlüsseln bzw. entschlüsseln.

Unter dem Gray-Code versteht man eine Folge binärer Zahlenketten, die nach dem Ingenieur Frank Gray, einem Forscher in den Bell Laboratories, benannt wurde. Er erhielt im Jahre 1953 für die Nutzung des nach ihm benannten Codes das U.S. Patent No. 2 632 058 „Pulse Code Communication”. Durch die Anzahl der Bits wird die Länge n eines Gray-Codes festgelegt. Man kann sich leicht überlegen, dass es zu einem bestimmten n 2ⁿ unterschiedliche Gray-Codes gibt.

Wir benutzen die Gray-Code-Darstellung, um an Hand einer Reihe von C++–Klassen das Zusammenspiel unterschiedlicher C++–Sprachkonstrukte zu üben und zu vertiefen. Das Endergebnis dieser Aufgabe, die Berechnung von Gray-Codes zu einem beliebigen n, ließe sich sicherlich auch kürzer und direkter erzielen, nur würden wir dabei keinen Lerneffekt erreichen.

Eine natürliche Zahl, die identisch ist mit ihrer Kehrzahl wie z.B. 131, wird Palindrom genannt. In dieser Fallstudie betrachten wir eine nicht deterministische Methode zur Berechnung beliebig großer Palindrome.

Die in C++ eingebauten elementaren Datentypen (wie int oder long) stellen keine echte Hilfe dar, wenn wir potentiell unendlich große Palindrome berechnen wollen. Zu diesem Zweck entwerfen wir im Folgenden zunächst eine Klasse Number, mit deren Hilfe sich sehr große Zahlen darstellen lassen. Im Anschluss daran gehen wir auf die Klasse PalindromCalculator ein, um Palindrome zu berechnen.

In dieser Fallstudie betrachten wir ein sehr „martialisches” Problem, das durch den jüdischen Historiker Flavius Josephus überliefert worden ist. Dieser soll im römisch–jüdischen Krieg mit 41 Kameraden den Selbstmord der Gefangenschaft vorgezogen haben. Details finden Sie gleich weiter unten vor – umso interessanter die Fragestellung, wie Informatiker bei dieser Fallstudie ins Spiel kommen: Josephus fand nämlich heraus, an welche Position im Kreis er sich stellen musste, um als letzter übrig zu bleiben, also um überleben zu können.

Damit sind schlagartig vielen Türen der Informatik geöffnet, zum Beispiel einfach-verkettete Listen, Arrays und sogar das Prinzip der Vererbung, um nur einige wenige anzusprechen. Lassen Sie sich überraschen, wie wir mit den Hilfsmitteln des Modern C++ die Lösung des Josephus-Problems bestimmen.

Das Collatz-Problem, auch als „3n + 1”-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem und wird dem Mathematiker Lothar Collatz zugeschrieben.

Diese Fallstudie zeigt, wie sich die Berechnung der Elemente einer Zahlenfolge in einen C++–Iterator einbetten lässt, um auf diese Weise mit Hilfe der STL performante und elegant in das C++–Programmiermodell integrierte Algorithmen formulieren zu können.

In der Zahlentheorie oder in der Kombinatorik ist eine Partition einer natürlichen Zahl n eine Möglichkeit, n als Summe natürlicher Zahlen zu schreiben. Zwei Summen, die sich nur in der Reihenfolge ihrer Summanden unterscheiden, werden als dieselbe Partition aufgefasst. Zum Beispiel kann die natürliche Zahl 4 auf fünf verschiedene Arten aufgeteilt werden:

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1 

Wir beschäftigen uns in dieser Fallstudie mit der Fragestellung, auf wie viele Arten sich eine natürliche Zahl als Summe von natürlichen Zahlen – auch Partition oder Zerlegung genannt – schreiben lässt und wie sich diese mit den Hilfsmitteln von Modern C++ berechnen lassen.