SS 1998 - Fachhochschule Köln
Fachbereich Nachrichtentechnik
Dr. Matthias Groß

Praktikum Datenverarbeitung - 7. Arbeitsblatt

Abgabetermin für alle: Montag 22.06. 1998 im DV-Labor

Bei dieser Praktikumsaufgabe sollen alle erlernten Fähigkeiten noch einmal gesammelt verwendet und zu einem Programm vereinigt werden. Diese Aufgabe enthält auch viele Komponenten, die für die Klausur am Ende des Semesters wichtig sind. Es werden zur konkreten Bearbeitung folgende theoretische Hilfsmittel benötigt:

• Bäume und die
• Anwendung dieser Baumstrukturen für sortierte Ausgaben und Auswertungen in Verbindung mit
• dynamischer Speicherverwaltung,
• Stringbearbeitung und die
• Verwendung rekursiver Funktionen.

Es soll ein Programm zum symbolischen Differenzieren geschrieben werden, d.h. aus einem Ausdruck der Form

    f(x)=a*x^3+x*(x+2*x^2) soll

    f'(x)=a*3*x^2+1*(x+2*x^2)+x*(1+2*2*x^1)

    oder noch besser f'(x)=a*3*x^2+x+2*x^2+x*(1+4*x)

werden.

Wer noch Lust hat, kann auch leicht Erweiterungen wie sin(x), cos(x), exp(x) etc. hinzunehmen und so ein komplettes Produkt herstellen.

Beachten Sie bitte auch alle weiteren Hinweise aus der Vorlesung. Um den Einstieg leichter zu finden verwenden Sie bitte das Beispielprogramm ableit.c mit dem zugehörigen Headerfile ableit.h.

Bei dieser Aufgabe stellen sich Ihnen mehrere Probleme:

• Wie soll die Funktion f(x) gespeichert werden? (Thema: Bäume und dynamische Speicherverwaltung)
• Wie soll f(x) eingelesen werden? (Thema: Stringbearbeitung)
• Wie wird die Generierung der Ableitung realisiert? (Thema: Rekursive Funktionen)

Die Speicherung der Funktion f(x)=a*x^3+x*(x+2*x^2) erfolgt in Form eines Binär-Baumes, der sich schrittweise wie folgt aufbaut:

     __+__
a*x^3     x*(x+2*x^2)

    _____+____
 __*__      __*__
a     x^3  x     x+2*x^2

    ____+______
 __*__       __*__
a   __^__   x   __+__
   x     3     x   __*__
                  2   __^__
                     x     2

Man erkennt im obigen Beispiel recht gut, wie an jedem Knoten des B-Baumes (Binären Baums), der jeweils (maximal) zwei Nachfolger hat, jeweils ein Operator (+, -, *, /, ^) steht und an den Blättern jeweils eine konkrete Zahl oder x bzw. evtl. eine andere Variable. Eine Speicherung mathematischer Ausdrücke in dieser Form nennt man Syntaxbaum. Hat man diesen Syntaxbaum einmal aufgebaut, so kann man davon ausgehend verschiedene Dinge tun. Die erste Aufgabe ist die Ausgabe des eingegebenen und im B-Baum abgespeicherten Ausdruckes sowohl in Postfix-Notation (2 x 3 ^ * x x 2 x 2 ^ * + * +) als auch wieder in Infix-Notation (a*x^3+x*(x+2*x^2)). Das fertige Programm sollte nachher ein kurzes Menue wie folgt aufweisen:

• Eingeben eines neuen Ausdrucks.
• Ausgabe des Ausdrucks in Infix- und Postfix-Notation
• n-te Ableitung ausgeben (n natürliche Zahl), Ausgabe erfolgt als Infix- und Postfix-Notation
• Berechnung des Ausdrucks für x als beliebige eingegebene reelle Zahl.

Tips und Anregungen:

• Wie sieht ein Baumknoten aus? (vgl. Headerfile ableit.h.)
• Machen Sie sich Gedanken zu der Rangfolge der Operatoren.
• Wie kann man die Ausdrücke evtl. etwas kürzen?  (vgl. Headerfile ableit.h.)
• Was machen Sie mit Klammern (a+x)*(2+x^2)? Dieses Problem stellt sich sowohl beim Einlesen, als auch bei der Ausgabe.
• Wie lesen Sie den mathematischen Ausdruck ein? (Die einfachste Version ist das Einlesen als Postfixnotation von hinten aus...)

Literatur: Algorithmen in C, Robert Sedgewick, Addison-Wesley 1992.

Seite zuletzt aktualisiert am 28.05.1998 von Matthias Groß. Diese Seite ist Teil des WWW-Dienstes der FH-Köln, Germany.