Zusätzliche Materialien zu Übungen und Tutorien

An dieser Stelle finden Sie zusätzliche Materialien zu den Übungsaufgaben und den in den Tutorien zu schreibenden Programmen, z.B. Lösungen der Aufgaben in der Programmiersprache C, die von einem der Übungsleiter, der Tutoren oder auch von einem Studierenden/einer Studierenden erstellt wurden. (Wenn Sie eine besonders gute Lösung für eine Aufgabe gefunden zu haben glauben, schicken sie diese per E-mail an Christian Borgelt. Ggf. finden Sie diese Lösung dann wenig später hier oder auf der Diskussionsseite wieder.) Einige dieser Materialien gehen über das hinaus, was in den Übungen und Tutorien behandelt werden kann, so daß es sich auch bei regelmäßigem Besuch der Übungen und Tutorien lohnt, diese Materialien anzusehen. Wenn Sie etwas nicht verstehen, helfen Ihnen die Übungsleiter und Tutoren gerne weiter.

• Text ex1-3.ps ex1-3.tex
  Lösungen der Aufgaben 1 bis 3 des 1. Übungsblattes.
• C-Programm euler.c (Version vom 12.11.1997)
  Lösung der Aufgabe 4 des 1. Übungsblattes. Die Zahl e wird in drei Funktionen berechnet, von denen jede eine andere der auf dem Übungsblatt angegebenen Formeln verwendet.
  (All comments in this program are written in English, so be prepared.)
• C-Programm heron.c (Version vom 17.11.1997)
  Programm zur Berechnung der Quadratwurzel einer Zahl mit Hilfe des Heron-Verfahrens. Die Vorgehensweise ist der in dem Programm euler.c verwendeten sehr ähnlich. Außerdem wird in diesem Programm gezeigt, wie man Kommandozeilenparameter auswertet.
  (All comments in this program are written in English, so be prepared.)
• C-Programm simple.c (Version vom 14.05.1998)
  Lösung der Aufgabe 5 des 1. Übungsblattes. Es werden drei Zahlen eingelesen und ihre Summe, ihr Produkt, ihr arithmetisches Mittel und ihr Maximum berechnet.
  (All comments in this program are written in English, so be prepared.)
• C-Programm loops.c (Version vom 14.05.1998)
  Lösung der Aufgabe 6 des 1. Übungsblattes. Die Summe 1+5+9+13+...+1001 wird mit den drei verschiedenen Schleifenanweisungen der Programmiersprache C berechnet
  (All comments in this program are written in English, so be prepared.)
• C-Programm dow.c (Version vom 08.11.1997)
  Lösung der Aufgabe 7 des 1. Übungsblattes. Außer einer Erläuterung der switch-Anweisung enthält dieses Programm eine Einführung in die Verwendung von Vektoren (auch Arrays genannt) und behandelt bedingte Übersetzung. (Der Name 'dow' leitet sich ab von dem englischen Ausdruck `day of the week' für `Wochentag'.)
  (All comments in this program are written in English, so be prepared.)
• Erklärungen zu Duff's Device / switch-Anweisung duff.ps duff.tex
  Duff's Device ist ein Programmstück, in dem die switch-Anweisung in sehr ungewöhnlicher Weise verwendet wird. Obwohl man solche Konstrukte lieber meiden sollte, eignet es sich gut, um die Besonderheiten der switch-Anweisung zu erläutern.
  (Written in English, so be prepared.)
• C-Programm euclid.c (Version vom 05.11.1997)
  Lösung der Aufgabe 8 des 2. Übungsblattes. Vier verschiedene Versionen des euklidischen Algorithmus (rekursiv mit Suktraktion, rekursiv mit Restbildung, iterativ mit Subtraktion, iterativ mit Restbildung) werden benutzt, um den größten gemeinsamen Teiler zweier Zahlen zu bestimmen.
  (All comments in this program are written in English, so be prepared.)
• C-Programm prime.c (Version vom 14.11.1997)
  Lösung der Aufgabe 9 des 2. Übungsblattes. Ausgehend von der einfachsten Version des Primzahltest wird dieser in fünf Schritten verbessert, so daß insgesamt 6 unterschiedlich schnelle Funktionen vorliegen, die eine Zahl daraufhin prüfen, ob sie eine Primzahl ist.
  (All comments in this program are written in English, so be prepared.)
• C-Programm perfect.c (Version vom 18.11.1997)
  Lösung der Aufgabe 10 des 2. Übungsblattes. Ob eine Zahl vollkommen (oder perfekt) ist, wird auf zwei verschiedene Weisen geprüft. In der ersten Version wird eine Beziehung ausgenutzt, die schon zur Beschleunigung des Primzahltests herangezogen wurde, in der zweiten Version wird mit einer Primfaktorzerlegung gearbeitet.
  (All comments in this program are written in English, so be prepared.)
• C-Programm pfacts.c (Version vom 17.11.1997)
  Auskopplung der Primfaktorzerlegung aus dem Programm perfect.c. Eine gegebene Zahl wird in ihre Primfaktoren zerlegt.
  (All comments in this program are written in English, so be prepared.)
• C-Programm convert.c (Version vom 16.02.1998)
  Lösung der Aufgabe 11 des 2. Übungsblattes. Mit Hilfe dieses Programms können Zahlen aus einem beliebigen Zahlensystem mit Basis 2 bis 36 in ein beliebiges anderes Zahlensystem mit Basis 2 bis 36 umgewandelt werden. Außerdem enthält dieses Programm einige Erläuterungen zu Zeichenketten (Strings), Vektoren und Zeigern.
  (All comments in this program are written in English, so be prepared.)
• C-Programm change.c (Version vom 13.05.1998)
  Lösung der Aufgabe 12 des 2. Übungsblattes und der Aufgabe 33 des 8. Übungsblattes. Es wird die Zahl der Möglichkeiten zum Wechseln eines beliebigen Geldbetrages zwischen 0.01 DM und 10000.00DM in verschiedenen Versionen berechnet, insbesondere in einer, die dynamische Programmierung verwendet.
  (All comments in this program are written in English, so be prepared.)
• Text ex13-14.ps ex13-14.tex
  Lösungen der Aufgaben 13 und 14 des 2. Übungsblattes.
• Text ex15.ps ex15.tex
  Lösung der Aufgabe 15 des 2. Übungsblattes. Es wird gezeigt, warum die Funktion f = kgV (kleinstes gemeinsames Vielfaches) ist, und es werden zwei applikative Algorithmen zur Berechnung des kgV angegeben.
• C-Programm rmsim.c regmach.c regmach.h (Version vom 08.12.1997)
  Illustration zu den Aufgaben 16 und 17 des 2. Übungsblattes. Mit Hilfe einiger Präprozessordefinitionen wird es ermöglicht, ein Registermaschinenprogramm in eine C-Funktion zu schreiben. Auf diese Weise können Registermaschinen sehr einfach simuliert werden. Die Definitionen der Registermaschinenbefehle wurden in eine eigene Header-Datei geschrieben, um sie in verschiedenen Programmen benutzen zu können.
  (All comments in this program are written in English, so be prepared.)
• C-Programm rmnum.c (Version vom 08.12.1997)
  Illustration der Registermaschinenbefehle mit indirekter Adressierung. Dieses Programm enthält zwei Registermaschinenprogramme, die eine n-stellige Dualzahl lesen und ihren Wert im ersten Speicherregister ablegen, sowie ein Registermaschinenprogramm, das eine n-stellige Zahl eines beliebigen Zahlensystems liest und das Ergebnis im ersten Speicherregister ablegt. Um das Program übersetzen zu können, werden die Dateien regmach.c und regmach.h aus dem vorhergehenden Eintrag benötigt.
  (All comments in this program are written in English, so be prepared.)
• C-Programm eratos.c (Version vom 18.12.1997)
  Lösung der Aufgabe 18 des 3. Übungsblattes. Das Sieb des Eratosthenes ist in diesem Program in zwei Versionen implementiert, deren erste Zeichen-Flags (Datentyp char) und deren zweite Bit-Flags benutzt, um gestrichene Zahlen zu markieren. Die zweite Version ist zwar langsamer, benötigt aber wesentlich weniger Speicher.
  (All comments in this program are written in English, so be prepared.)
• Text ex19.ps ex19.tex
  Lösung der Aufgabe 19 des 2. Übungsblattes. Es werden allgemeine Formeln für die Zeitkomplexität der Registermaschine aus Beispiel 3.8 für Eingaben n > 2 abgeleitet. Mit diesen kann die Aufgabe leicht gelöst werden.
• Shellscript ex19.csh
  Mit Hilfe dieses Shellscripts und dem als Illustration zu den Aufgaben 16 und 17 angegebenen Registermaschinensimulator kann das Ergebnis der Aufgabe 19 durch eine Simulation der Registermaschine aus Beispiel 3.8 überprüft werden.
• Text c_ass_mc.ps c_ass_mc.tex
  Gegenüberstellung einer Registermaschine und eines realen Prozessors (Motorola 68000). Diese Gegenüberstellung zeigt, daß das theoretische Konstrukt der Registermaschine durchaus praxisrelevant ist.
• C-Programm random.c (Version vom 19.11.1997)
  Mit Hilfe dieses Programms können Folgen von Zufallszahlen erzeugt werden. Solche zufälligen Folgen sind ggf. zum Testen der Lösung von Aufgabe 20 des dritten Übungsblattes hilfreich. Mit diesem Programm wurden die auf dem Übungsblatt erwähnten Dateien n1000.dat und n10000.dat erzeugt.
  (All comments in this program are written in English, so be prepared.)
• C-Program mps.c (Version vom 05.12.1997)
  Lösung der Aufgabe 20 des 3. Übungsblattes. Dieses Programm enthält eine Implementierung jeder der vier Algorithmen zur Lösung des Problems der maximalen Teilsummen (maximal partial sums, daher mps). Zum Testen können bis zu 10000 Zahlen eingelesen werden. Der Algorithmus wird über einen Kommandozeilenparameter ausgewählt.
  (All comments in this program are written in English, so be prepared.)
• C-Programm gcd.c (Version vom 05.01.1998)
  Lösung der Aufgabe 21 des 4. Übungsblattes. Dieses Programm enthält fünf verschiedene Versionen der Berechnung des größten gemeinsamen Teilers nach der Schulmethode. Die erste dieser Versionen ist eine direkte Umsetzung des in der Vorlesung angegebenen Algorithmus, die übrigen Versionen sind auf verschiedenen Ideen beruhende Verbesserungen.
  (All comments in this program are written in English, so be prepared.)
• C-Programm poly.c (Version vom 13.12.1997)
  Lösung der Aufgabe 22 des 4. Übungsblattes. Der Wert eines gegebenen Polynoms, das maximal 64-ten Grad hat, wird an einem gegebenen Punkt berechnet, und zwar einmal durch sukzessive Addition der Terme des Polynoms, einmal nach dem Hornerschema. Die Addition der Terme kann allerdings gegenüber einem trivialen Ansatz verbessert werden, so daß das Programm hierzu zwei Versionen enthält.
  (All comments in this program are written in English, so be prepared.)
• Text ex23.ps ex23.tex
  Lösung der Aufgabe 23 des 4. Übungsblattes. In einer Tabelle sind die Kosten und Ausführungszahlen der einzelnen Programmzeilen angegeben.
• C-Programm power.c (Version vom 07.01.1998)
  Lösung der Aufgabe 24 des 4. Übungsblattes. Die Potenzfunktion wird durch drei verschiedene rekursive Funktionen berechnet, die jeweils in einer unsicheren und einer sicheren Variante (d.h. mit Abfangen eines Zahlenüberlaufs) vorliegen.
  (All comments in this program are written in English, so be prepared.)
• Text exc1-6.ps exc1-6.tex
  Lösung der Aufgaben C1 bis C6 des 5. Übungsblattes für Informatiker und Wirtschaftsinformatiker.
• C-Programm choose.c (Version vom 19.11.1997)
  Aufgabe C2 des 5. Übungsblattes als vollständiges C-Programm.
  (All comments in this program are written in English, so be prepared.)
• C-Programm frac.c (Version vom 19.01.1998)
  Aufgabe C4 des 5. Übungsblattes als vollständiges C-Programm.
  (All comments in this program are written in English, so be prepared.)
• C-Programm match.c (Version vom 18.12.1997)
  Aufgabe C6 des 5. Übungsblattes als vollständiges C-Programm.
  (All comments in this program are written in English, so be prepared.)
• C-Programm horner.c (Version vom 21.01.1998)
  Lösung der Aufgabe 25 des 6. Übungsblattes. Ein Polynom wird auf zwei Arten mit dem erweiterten Hornerschema ausgewertet.
  (All comments in this program are written in English, so be prepared.)
• C-Programm recsum.c (Version vom 14.05.1998)
  Lösung der Aufgabe 26 des 6. Übungsblattes. Rekursive Berechnung der Summe der ersten n natürlichen Zahlen.
  (All comments in this program are written in English, so be prepared.)
• C-Programm numsort.c (Version vom 15.07.1998)
  Lösung der Aufgaben 27 und 28 des 6. Übungsblattes, der Aufgabe 29 des 7. Übungsblattes und der Aufgabe 50 des 11. Übungsblattes. Implementierung verschiedener Algorithmen zum Sortieren eines Feldes von Fließkommazahlen. Dieses Programm enthält die Algorithmen bubblesort, insertion sort, selection sort, shellsort, mergesort, heapsort, quicksort (in 2 Varianten) und binsort/bucketsort/radixsort.
  (All comments in this program are written in English, so be prepared.)
• C-Programm skeleton.c mit Erläuterungen skeleton.ps skeleton.tex (Version vom 11.11.1997)
  Dieses Programm ist ein Grundgerüst eines Kommandozeilenprogramms mit Auswertung fester und optionaler Kommandozeilenparameter. Dazu gibt es eine ausführliche Erläuterung.
• C-Programm polymult.c (Version vom 07.04.1998)
  Lösung der Aufgabe 30 des 7. Übungsblattes. Multiplikation zweier Polynome durch direkte Multiplikation der Koeffizienten.
  (All comments in this program are written in English, so be prepared.)
• C-Programm knapsack.c (Version vom 06.04.1998)
  Lösung der Aufgabe 31 des 7. Übungsblattes. Lösung des Rucksackproblems durch zwei Greedy-Algorithmen und durch dynamische Programmierung.
  (All comments in this program are written in English, so be prepared.)
• C-Programm change.c (Version vom 13.05.1998)
  Lösung der Aufgabe 12 des 2. Übungsblattes und der Aufgabe 33 des 8. Übungsblattes. Es wird die Zahl der Möglichkeiten zum Wechseln eines beliebigen Geldbetrages zwischen 0.01 DM und 10000.00DM in verschiedenen Versionen berechnet, insbesondere in einer, die dynamische Programmierung verwendet.
  (All comments in this program are written in English, so be prepared.)
• C-Programm wld.c (Version vom 08.04.1998)
  Lösung der Aufgabe 34 des 8. Übungsblattes. Dieses Programm berechnet die gewichtete Levenshtein-Distanz zweier Zeichenketten, wobei die Gewichte der Editieroperationen über Kommandozeilenschalter angegeben werden können.
  (All comments in this program are written in English, so be prepared.)
• C-Programme intlists.c (Version vom 04.06.1998) und intvecs.c (Version vom 04.06.1998)
  Beispiellösungen für die Belegaufgabe zu linearen Listen unter Verwendung der (nur minimal veränderten) Vorgaben aus den ausgeteilten Unterlagen.
  (All comments in this program are written in English, so be prepared.)
• C-Programm sclists.h sclists.c scl_vec.c scl_test.c (Version vom 02.09.1998) mit (leider noch unvollständigen) Erläuterungen sclists.tex sclists.ps.
  Allgemeine Verwaltung für einfach verkettete Listen mit beliebigem Datentyp. In jedem Listenelement kann ein beliebiges Datenobjekt abgelegt werden. Lediglich seine Größe ist anzugeben. Außerdem enthält dieses Programm, ebenso wie die folgenden beiden, eine Lösung der Aufgabe 37 des 9. Übungsblattes.
  (All comments in this program are written in English, so be prepared.)
• C-Programm dclists.h dclists.c dcl_vec.c dcl_test.c (Version vom 02.09.1998) mit (leider noch unvollständigen) Erläuterungen dclists.tex dclists.ps.
  Allgemeine Verwaltung für doppelt verkettete Listen mit beliebigem Datentyp. In jedem Listenelement kann ein beliebiges Datenobjekt abgelegt werden. Lediglich seine Größe ist anzugeben. Dieses Programm ist eine auch Lösung der Aufgabe 36 des 9. Übungsblattes.
  (All comments in this program are written in English, so be prepared.)
• C-Modul lists.h lists.c (Version vom 02.09.1998) leider noch ohne Erläuterungen.
  Alternative Implementierung einer Verwaltung doppelt verketteter Listen. In dieser Version muß die Listenelementstruktur redefiniert werden, um Daten des gewünschten Typs speichern zu können. Auch dies ist eine Lösung der Aufgabe 36 des 9. Übungsblattes.
  (All comments in this program are written in English, so be prepared.)
• C-Programme in2post.c, postfix.c, stack.h, stack.c stack_l.c (Version vom 15.07.1998)
  Lösung der Aufgabe 38 des 9. Übungsblattes. in2post.c wandelt mit Hilfe eines Stacks einen arithmetischen Infixausdruck in einen Postfixausdruck, postfix.c wertet einen arithmetischen Postfixausdruck mit Hilfe eines Stacks aus. stack.c und stack_l.c sind zwei alternative Implementierungen eines Stacks. Erstere benutzt einen Vektor, letztere eine einfach verkettete Liste.
  (All comments in this program are written in English, so be prepared.)
• Text ex39.ps ex39.tex
  Lösung der Aufgabe 39 des 10. Übungsblattes. Verschiedene Darstellungen eines Graphen.
• C-Programm graph.c (Version vom 08.07.1998)
  Lösung der Aufgaben 40 bis 42 des 10. Übungsblattes. Umwandlung verschiedener Darstellungen gerichteter Graphen ineinander, Einfügen von Knoten und Kanten in die verschiedenen Darstellungsformen und topologisches Sortieren in den verschiedenen Darstellungsformen.
  (All comments in this program are written in English, so be prepared.)
• C-Programm bstree.c, bstree.h, bst_test.c (Version vom 02.09.1998)
  Lösung der Aufgaben 43 und 45 des 10. Übungsblattes und der Aufgaben 46 und 47 des 11. Übungsblattes. Einfügen und Löschen von Elementen in binären Suchbäumen, sowohl für einfache als auch für ausgeglichene Bäume (AVL-Bäume). Wie dieses Programm zu übersetzen ist, ist in bst_test.c beschrieben.
  (All comments in this program are written in English, so be prepared.)
• C-Programm expr.c (Version vom 30.06.1998)
  Lösung der Aufgabe 44 des 10. Übungsblattes. Auswertung eines arithmetischen Ausdrucks, der durch einen (Parse-)Baum gegeben ist. Außerdem enthält dieses Programm einen einfachen Parser zum Einlesen eines Infix-Ausdrucks und zum Aufbauen eines Parsebaums.
  (All comments in this program are written in English, so be prepared.)
• C-Programm numsort.c (Version vom 15.07.1998)
  Lösung der Aufgaben 27 und 28 des 6. Übungsblattes, der Aufgabe 29 des 7. Übungsblattes und der Aufgabe 50 des 11. Übungsblattes. Implementierung verschiedener Algorithmen zum Sortieren eines Feldes von Fließkommazahlen. Dieses Programm enthält die Algorithmen bubblesort, insertion sort, selection sort, shellsort, mergesort, heapsort, quicksort (in 2 Varianten) und binsort/bucketsort/radixsort.
  (All comments in this program are written in English, so be prepared.)
• C-Programm hardsort.c (Version vom 04.03.1998)
  Zusatzprogramm zu der Aufgabe 50 des 11. Übungsblattes. Für verschiedene Varianten des Quicksort-Algorithmus wird eine Folge von Zahlen erzeugt, die zum schlechtesten Fall führt (quadratische Zeitkomplexität).
  (All comments in this program are written in English, so be prepared.)
• C-Programm hashtab.c hashtab.h hashtest.c (Version vom 02.09.1998)
  Beispielprogramm zu statischen Hashtabellen mit doppeltem Hashing (vgl. Aufgabe 49 des 11. Übungsblattes).
  (All comments in this program are written in English, so be prepared.)
• C-Modul symtab.h symtab.c (Version vom 02.09.1998) mit Erläuterungen symtab.tex
  Implementierung einer Symboltabelle z.B. für die Verwendung in einem Compiler durch eine Hashtabelle mit Überlauflisten (vgl. Aufgabe 49 des 11. Übungsblattes).
  (All comments in this program are written in English, so be prepared.)