Institut für Informatik

Markus Blumenstock

Sommersemester 2024

Funktionsableitungen am Rechner

Aufgabe 4.1: Numerische Ableitung

Aufgabe 4.1.1: Newtonscher Differenzenquotient

Aufgabe

• Theoriefrage: Die angegebene Formeln können in dieser Aufgabe direkt auf die gemessen Daten angewendet werden, da diese in einem regelmäßigen Gitter vorliegen. Wie müssten Sie die Formel anwenden, wenn ihre Messung auf einem ungleichmäßigen Gitter erfolgt wäre?
  Hinweis: Das heißt Ihre Daten liegen als Punkte-Paare \((f_1,x_1),(f_2,x_2),\dots (f_n,x_n)\) vor.
  • Starten Sie mit einem beliebigen Polynom und werten Sie es mit numpy auf einem Gitter aus.
  • Bestimmen Sie die numerische Ableitung auf dem so entstandenen Datensatz.
  • Visualisieren Sie die Ableitung mit Matplotlib. Plotten Sie auch die tatsächliche zugehörige Ableitung, die sie auf dem Papier bestimmt haben (z. B. gestrichelt).
  • Testen Sie nun unterschiedliche Schrittweiten \(h\), Gitter und die alternative Definition aus. Was können Sie beobachten?
  • Mithilfe der Ableitung können Sie die Maxima und Minima Ihrer Funktion automatisch bestimmen (Suchen Sie nach Vorzeichenwechsel von aufeinanderfolgenden Funktionswerten und achten Sie auf die Art des Vorzeichenwechsels, um die Extrema zu unterscheiden). Visualisieren Sie die Minima und Maxima.
  • Optionale Theoriefrage (unbewertet): Im Grenzwert sind die beiden Definitionen für die Ableitung für \(h\rightarrow \infty\) äquivalent. Gilt dies auch für die numerische Verwendung mit endlich kleinem \(h\)?
• Nun zur Praxis:
  • Erstellen Sie einen Datensatz, indem Sie \(\sin(x)\) gleichmäßig abtasten und bestimmen Sie dessen numerische Ableitung.
    Wie gut approximiert die numerische Ableitung die analytische Ableitung (\(\cos(x)\))?
    
    Zeichnen Sie das numerische, sowie das tatsächliche Ergebnis der Ableitung.
  • Wie sieht es bei \(\sin(\frac{1}{x})\) aus (beachten Sie, dass diese Funktion an der Stelle \(x=0\) nicht definiert ist)?

• Ersetzen Sie nun den Datensatz durch den Wetterdatensatz und Visualisieren Sie auch hier die Extrempunkte in ihrer Darstellung.
• Testen Sie nun unterschiedliche Schrittweiten \(h\), Gitter und die alternative Definition aus. Was können Sie beobachten?
  

Aufgabe 4.1.2: Approximative Ableitung

Aufgabe

• Warum sollte die Ableitung in der Mitte des Fensters ausgewertet werden?
• Bestimmen Sie wie auf Blatt 2 zuerst eine Moving-Least-Squares Approximation. Verwenden Sie dazu ruhig numpy.polyfit, das ein Array der Koeffizienten des Polynoms als Liste zurückgibt (Koeffizienten zu hohen Potenzen sind in der Liste weiter vorne).
• Wie müssen Sie die Liste verändern, damit sie die Ableitung des Polynoms angibt?
  
  Hinweis: Rechnen Sie dies für eine Liste [a_n,...,a_2,a_1,a_0], also für das Polynom \(a_nx^n+\dots + a_2x^2+ a_1x + a_0\), nach.
• Die veränderte Liste können Sie, wie die unveränderte auf Blatt 2 auch, in np.poly1d einsetzen und so als Polynom an einer beliebigen Stelle auswerten. Danach schauen wir uns nochmal die gleichen Anwendungen an (diesmal mit besseren Ableitungen; Tipp: Code modular schreiben...):
  
• Fügen Sie Ihrem Plot das approximierte Polynom und die approximierte Ableitung an.
• Bestimmen Sie auch hier die Minima und Maxima automatisch und färben Sie diese entsprechend ein.
• Bei welchen Fensterbreiten können Sie an den Extrema Tage bzw. Jahreszeiten ablesen?

Aufgabe 4.2: Algebra auf Funktionen

Wie wir in Aufgabe 1 gesehen haben, hat das numerische Ableiten seine Tücken; Schrittweite und „Gutartigkeit“ der Funktion sind direkt dafür verantwortlich, wie groß der Fehler im Vergleich zur echten Ableitung ist. Falls es funktioniert, kann man diese Technik jedoch wunderbar für verschiedene Anwendungen verwenden (siehe nächstes Übungsblatt). Im Allgemeinen ist die numerische Ableitung jedoch instabil.

Die Symbolische Ableitung (die auf diesem Blatt nur am Rande erklärt wurde) kämpft hingegen mit dem Umstand, dass die Ableitung eines Ausdrucks stets wieder einen (einzigen) mathematischen Ausdruck zurückgeben muss. Insbesondere, wenn die abzuleitende Funktion if-Bedingungen und Schleifen aufweist kann dies sehr aufwändig werden. Hier kommt automatisches Differenzieren ins Spiel: Man merkt sich den Operationsbaum eines Ausdrucks und leitet alle Komponenten „direkt“ an der Stelle \(x\) ab, während man beim Abstieg die Kettenregel \[ (f \circ g)'(x) = f'(g(x)) \cdot g'(x) \] anwendet. Insbesondere bestimmt man also keinen geschlossenen Ausdruck für die Ableitung, sondern führt einfach die Berechnungen an der Stelle \(x\) durch. Die Folge der Operationen, also z. B. welche if-Zweige ausgeführt werden oder wie viele Schleifendurchläufe es gibt, kann dabei für jeden konkreten Wert \(x\) unterschiedlich sein.

Der Nachteil dieser Methode besteht darin, dass man häufig Zwischenergebnisse für die weitere Verwendung abspeichern muss und für jede (elementare) Operation eine Ableitung definieren muss. Außerdem benötigt die Berechnung u.U. mehr Rechenschritte, als die Auswertung des symbolisch bestimmten und ggf. vereinfachten Ausdrucks benötigen würde. Im Gegenzug bekommt man eine Methode, die numerisch sehr viel stabiler ist.

Aufgabe 4.2.1: Funktionen-Algebra

[20 Punkte]

Wir starten damit, eine Funktionen-Algebra zu implementieren. Ziel ist es, statt mit Zahlen einfach mit Funktionen zu rechnen, also etwa für zwei Funktionen \(f,g\colon \mathbb{R} \to \mathbb{R}\) soll es möglich sein, \(f + g, f - g, f \cdot g\) auszurechnen. Wir definieren also eine algebraische Struktur auf den Funktionen.

Etwas genauer wollen wir eine sogenannte „Algebra“ \((F, \oplus, \otimes)\) definieren. Die Menge \(F\) ist dabei die Menge aller reellen Funktion \[F = \{ f \mid f \colon \mathbb{R} \to \mathbb{R} \}\] und die beiden Operationen \(\oplus\) und \(\otimes\) definieren eine Addition und eine Multiplikation auf dieser Menge. Wir wollen dabei unter der Summe bzw. dem Produkt zweier Funktionen einfach die punktweise Summe bzw. Produkt der beiden Funktionen verstehen. Das heißt, das Ergebnis der Summe zweier Funktionen \(h = f \oplus g\) ist die Funktion \(h \colon \mathbb{R} \to \mathbb{R}\) mit \(h(x) = f(x) + g(x)\) für alle \(x \in \mathbb{R}\). Genauso verhält es sich mit der Multiplikation und allen anderen Operationen.

Aufgaben

• Erstellen Sie eine Klasse Function, welche eine Funktionen repräsentiert. Diese Funktion sollte den __call__ Operator überladen, der die Funktion an einer bestimmten Stelle auswertet und das Ergebnis zurück gibt.

class Function:
	def __call__(self, x):
		pass

• Erzeugen Sie nun einige Unterklassen für einige typische Funktionen (sin, cos, ...). Für die Identitätsfunktion könnte das etwa so aussehen:

class Identity(Function):
	def __call__(self, x):
		return x

• Erweitern Sie die Klasse Function nun um die üblichen Operationen +,-,*, /,**. Jede dieser Operationen soll eine neue Funktion zurückgeben, welche die entsprechende punktweise Operation darstellt. Wenn Sie alle weiteren Funktionen als Unterklasse von Function implementiert haben, dann sollten diese Operationen automatisch auch für alle diese Funktionen funktionieren. Ein möglicher Vorschlag ist der folgende Code-Schnipsel.
  
  Hinweis: Arbeiten Sie am besten mit den von Python zur Verfügung gestellten Methoden __add__, __mul__, etc. wie auch auf dem Aufgabenblatt 3, Mengenaufgabe.
  Hinweis: Sie können dabei entweder auf lambda-Ausdrücken rechnen oder das Ganze über spezielle Unterklassen AddFunction, SubFunction, ... realisieren. Die zweite Variante benötigt ein wenig mehr Code, ist dafür aber klarer strukturiert und somit einfacher zu verstehen.
  

class Function:
	...
	def __add__(self, g):
		return AddFunction(self, g)

class AddFunction(Function):
	...

	def __init__(self, f, g):
		...

	def __call__(self, x):
		return ...

• Erweitern Sie die Function Klasse um die Kompositionsoperation \((f \circ g)(x) := f(g(x))\) (z. B. als __matmul__ Operator, in Python als @ geschrieben) implementiert.
• Implementieren Sie einige klassische Funktionen als Funktionsobjekte in ihrer Algebra, z. B. die Identitätsfunktion \(id\colon x \mapsto x\), konstante Funktionen \(f_c\colon x \mapsto c\) und \(\sin, \cos, \exp, \ln\).
• (leichter aber freiwilliger) Bonus:
  Um auch mit Zahlen zu rechnen, benötigen Sie eine Möglichkeit, konstante Funktionen zu realisieren. Um die Operationen \(f \cdot n\) bzw. \(n \cdot f\) für \(f\colon\mathbb{R}\to\mathbb{R}\) und \(n \in \mathbb{R}\), also Multiplikationen und Additionen mit Zahlen, zu erlauben, müsste man eigentlich immer f * ConstFunction(42) schreiben. Erweitern Sie ihre Operationen so, dass eine Verknüpfung mit einer Zahl ebenfalls unterstützt wird. Ob der übergebene Parameter eine Zahl oder eine Funktion ist, kann man z. B. über type(x) == Function oder isinstance(x, Function) testen.
  
  Am Ende dieser Aufgabe sollten Sie in der Lage sein, neue Funktionen durch Kombination (Addition, Multiplikation, ...) zu erzeugen, z. B.

class Sin(Function):
	...

f = Sin / Cos + Exp

print(f(42), " == ", math.sin(42) / math.cos(42) + math.exp(42))

• Werten Sie mithilfe Ihrer Methoden einige beispielhafte Funktionen aus visualisieren Sie diese mit matplotlib, z. B. die Funktion \(f\colon x \mapsto \sin(\cos(x) + x^2)\).
  
  (Wir könnten dies nun verwenden, um wie in Aufgabe 1 numerisch Abzuleiten. Die Vorgehensweise sollte an dieser Stelle aber klar sein und muss daher nicht nochmals wiederholt werden.)

4.2.2: Grundprinzip des Automatischen Differenzierens:

[20 Punkte]

Die Idee des automatischen Differenzierens ist die folgende. Wenn wir die Werte einer Funktion \(f\) und einer Funktion \(g\) an der Stelle \(x\) kennen, also \(f(x)\) und \(g(x)\), so kennen wir auch den Wert von \(h = f + g\) an der Stelle \(x\), nämlich \(h(x) = f(x) + g(x)\). Ähnlich verhält es sich mit den Werten der Ableitungen. Kennen wir \(f'(x)\) und \(g'(x)\) dann auch \(h'(x)\), denn es gilt bekanntermaßen \((f + g)' = f' + g'\).

Das funktioniert für + und -, nicht jedoch für *, /, **. Um den Wert der Ableitung \(h'(x)\) von \(h = f \cdot g\) an der Stelle \(x\) zu kennen, reicht es nicht \(f'(x)\) und \(g'(x)\) zu kennen. Warum?

Nun zum eigentlichen Differenzieren:
Statt die Funktion an einigen Stellen auszuwerten und numerisch abzuleiten, schicken wir das ausgewertete Paar \((f(x), f'(x))\) durch den Graphen und definieren alle arithmetischen Operationen auf dem Paar. Wir definieren also eine neue algebraische Struktur \((D, \oplus, \otimes)\) (das sind andere Operationen als für die Funktionenalgebra der vorigen Aufgabe), wobei \[D = \mathbb{R} \times \mathbb{R}\] Paare reeller Zahlen sind. Für zwei Paare \((f(x),f'(x)) \in D\) und \((g(x),g'(x)) \in D\) soll dabei gelten, dass \((f(x),f'(x)) \oplus (g(x),g'(x)) = (f(x) + g(x), f'(x) + g'(x))\) ist, die Addition verläuft also komponentenweise. Für die Multiplikation ist das aber etwas komplizierter und benötigt die Produktregel für die Ableitungen.

Aufgaben

• Setzen Sie dies als neue Klasse um, etwa „DualNumber“. Implementieren Sie für diese Klasse die üblichen arithmetischen Operationen +, -, *, / und **. (Der Einfachheit halber können sie damit starten zunächst nur f**n für n ganze Zahl zu erlauben)

class DualNumber:
	...
	def __init__(self, wert, ableitung):
		self.wert = wert
		self.ableitung = ableitung

	def __add__(self, n):
		...
	 ...

• Spannend wird das Ganze, wenn wir nun unsere Funktionsklasse Function erweitern. Bisher repräsentierte sie eine Funktion \(f\colon \mathbb{R} \to \mathbb{R}\). Jetzt soll sie Funktionen \(f\colon D \to D\) repräsentieren, welche eine DualNumber auf eine DualNumber abbildet. Man übergibt der Funktion also nicht nur den aktuellen Wert, an dem sie ausgewertet wird, sondern auch den Wert der Ableitung und liefert auch beides zurück, den Funktionswert und den Wert der Ableitung. Beachten Sie dabei die Kettenregel \((f(g(x)))' = f'(g(x)) \cdot g'(x)\)
  
  Hinweis: Eine Möglichkeit ist, eine neue Klasse DualFunction zu implementieren, welche eine Unterklasse von Function ist und aus zwei Funktionen, nämlich \(f\) und dessen Ableitung \(f'\) besteht.

class DualNumber:
	...

class Sin(DualFunction):
	def __call__(self, x):
		return DualNumber(math.sin(x.wert), math.cos(x.wert) * x.ableitung)

• Implementieren Sie nun die Elementarfunktionen sin, cos, tan, exp, ln.
• Optional: Implementieren Sie nun \(f^g\) für beliebige Funktionen. Das klappt i.A. nur wenn \(f(x) > 0\).
  
  Hinweis: Nutzen Sie dazu am besten die Gleichung \((f^g)(x) = \exp(g(x)\cdot \ln(f(x)))\) aus.

Testen Sie nun ihr Programm:

• Probieren Sie Ihre Methoden an gewissen Beispielen aus. Ein möglicher Vergleich wäre \(\tan\) und \(\frac{\sin}{\cos}\). (Da sollte das Gleiche herauskommen.)
• Zuletzt vergleichen wir die drei kennengelernte Ansätze, indem wir die Ableitung der Funktion \(\sin(\frac{1}{x})\) aus Aufgabe 1, nun mittels Automatischer Differentiation bestimmen. Fügen Sie das Ergebnis dem Plot aus Aufgabe 1 hinzu und vergleichen Sie die Ergebnisse.

4.2.3 Optionale Aufgabe: Ausgabe des algebraischen Ausdrucks.

Zuletzt, was man mit diesem Berechnungsgraphen noch anstellen kann. Außer reellen Zahlen oder DualNumber kann man eine Funktion auch mit anderen „Werten“ aufrufen und etwas sinnvolles damit machen. Zum Beispiel könnten wir eine „Zahl“ PrintNumber erzeugen, die keinen Wert sondern eine Textdarstellung eines Ausdrucks darstellt. Die einfachste PrintNumber wäre eine Zahl "42" oder eine Variable "X". Mit diesen Zahlen kann man auch Rechnen, dabei wird eine Textdarstellung der entsprechenden Operation erzeugt, z. B. "42" + "X" wird zur Zeichenkette "42 + X".
(Natürlich ist es jetzt nicht mehr so klar, ob \((P, \oplus, \otimes)\) mit \(P\) die Menge der PrintNumber wirklich eine algebraische Struktur im Sinne der Mathematik ist: zwar gibt es Operationen \(\oplus\) und \(\otimes\), aber es ist nicht mehr klar, ob sie den üblichen Axiomen genügen. Zum Beispiel wäre "x" + "5" - "5" dann "x + 5 - 5" und damit nicht wieder "x".)

Aufgaben

• Implementieren Sie die besondere Zahl PrintNumber mit den üblichen Operationen. Erweitern Sie außerdem ihre Function-Klassen so, dass sie auch eine PrintNumber auswerten können. Das Ergebnis sollte eine Zeichenkette sein, die den Funktionsaufruf repräsentiert, z. B. Sin("42 + X") gibt "sin(42 + X)" zurück.
• Optional: Sie können auch den algebraischen Ausdruck der Ableitung mit ausgeben (Natürlich nicht vereinfacht, denn der Ausdruck wird im Allgemeinen sehr wild aussehen). Dazu müssen Sie eine Dual-PrintNumber verwenden, z. B. in dem die beiden Werte der DualNumber eben vom Typ PrintNumber statt vom Typ float sind.

Aufgabe 4.3: Parsen — Aus Zeichenketten werden Bäume

[20 Punkte]

Die letzte Aufgabe beschäftigt sich damit, mathematische Ausdrücke zu manipulieren. Dazu müssen wir diese erstmal in den Rechner bringen. Wie in der Vorlesung erklärt, sind Ausdrücke eigentlich Bäume von Operatoren. Dies ist aber relativ schwierig direkt einzugeben (man bräuchte ein komplexes GUI, und die Interaktion wäre immer noch mühsam, wenn man sich nicht eine sehr raffinierte Schnittstelle überlegt). Daher ist es sinnvoll, mathematische Ausdrücke zunächst in linearisierter Form, als einfache Zeichenketten zu repräsentieren. Die Aufgaben, aus einer solchen, linearisierten Kodierung wieder einen Baum zu rekonstruieren, ist in der Informatik als „Parsing“ bekannt. Der Formalismus dahinter ist als kontextfreie Grammatiken/Sprachen bekannt: In jeden Operator im Baum kann man beliebig komplexe, zusammengesetzte Unteroperatoren einsetzen (Teilbäume).

Wir werden im Folgenden einen Algorithmus entwickeln, der gegeben ein Ausdruck in Polnischer Notation einen Binärbaum erstellt, der die Syntax der Zeichenkette widerspiegelt. Wenig überraschend ist es, dass bei der Übersetzung von Programmiersprachen ganz ähnliche genau die gleichen Konzepte eine Rolle spielen. (Die herkömmliche Mathematische Notation (infix-Notation) zu definieren erfordert etwas mehr Aufwand; es müssen Operatoren mit Präzedenz (Operatorrangfolge) definiert werden, die durch geschicktes Ablegen und Auflegen auf einen Stack in einen Baum überführt werden. Diese Arbeit sparen wir uns an dieser Stelle durch eine sehr viel einfachere Notation.)

Polnische Notation: Beschreibt einen Ausdruck, bei dem alle Symbole durch Leerzeichen getrennt werden und auf jeden Operator eine dem Operator fest vorgegebene Anzahl an Operanden folgt. So benötigt man keine Klammern und jeder Ausdruck ist eindeutig festgelegt. Beispielsweise entspricht + 3 * 2 / 2 5 entspricht dem Term \(3+2\cdot\frac{2}{5}\).

Negation
Sie können dabei den unären Operator - (Negation) entweder durch

• auslassen (es lässt sich ja auch durch 0 - . ausdrücken)
• als Teil der Zahl sehen (einfacher)
• ein weiteres Symbol (etwa ~) als unären Operator definieren (Als Beispiel * ~ 3 / 5 2, dies ist auch nicht viel aufwändiger) realisieren.

Ausblick: Grundlagen Compilerbau in 10 Minuten

im Folgenden gibt es einen kurzen Überblick über Grammatiken für formale Sprachen und Compilerbau. Für die Aufgabe ist es nicht unbedingt nötig, alles durchzuarbeiten (es hilft aber dabei, die Prinzipien hinter den Aufgaben besser zu verstehen).
Kontextfreie Grammatiken beschreiben die Schachtelung von Bausteinen Fast alle Programmiersprachen benutzen kontextfreie Grammatiken. Das heißt, dass das Programm aus Bausteinen besteht. Jeder Baustein ist ein Platzhalter: Er besteht aus einem gewissen Anteil an festem Text sowie weiteren Platzhaltern (wie ein Baum von Objekten in einer OOP-Sprache: Zeiger auf Unterobjekte müssen einen bestimmten Typ (Oberklasse) haben; welche Teilbäume man einsetzt ist aber egal, solange der Typ des direkt eingesetzten Typen stimmt.).
Die folgende Abbildung zeigt ein Beispiel für eine kontextfreie Grammatik: Die Bausteine sind mit spitzen Klammern markiert und werden mit dem Pfeil-Operator definiert. Auf der rechten Seite steht, mit welcher Folge von weiteren Bausteinen und/oder Zeichen, man einen Baustein ausfüllen kann. Dies macht man, bis alle Lücken (Platzhalter für Bausteine) gefüllt sind:

Der Parser hat nun die Aufgabe, aus einer gegebenen Zeichenkette (hier sind die Bausteine nicht mehr direkt ersichtlich) zu rekonstruieren, welcher Baum von Bausteinen (also, welche aufeinanderfolgende Ersetzung von Platzhaltern mit rechten Seiten der Pfeile, bis keine Platzhalter für Bausteine mehr übrig sind) zu der Zeichenkette gehört:

Leider ist dieses Problem nicht immer einfach. Für unsere Beispielgrammatik gibt es z. B. keine eindeutige Lösung (und das ist ein Problem; die Bedeutung wäre damit nicht mehr klar definiert):

Für das Beispiel mit arithmetischen Ausdrücken, wie hier gezeigt, kann man die Mehrdeutigkeit zwischen Multiplikation und Addition klären, indem man die Regeln geschickter schachtelt. Das Bild unten zeigt die Standardlösung für dieses Problem:

Die gerade beobachte Mehrdeutigkeit bei der Addition löst dies aber nicht; hier muß man im Parser zusätzlich festlegen, dass die Ausdrücke nach links oder rechts geklammert werden sollen (Links-/Rechtsassoziativität'').
Man kann es sich natürlich auch einfach machen, und eine Sprache so definieren, dass es sehr einfach wird, die Grenzen der Bausteine und deren Schachtelung zu erkennen. Dazu ist hinreichend, wenn man Anfang und Ende von Blöcken eindeutig markiert, und auch den Typ des Bausteins explizit kennzeichnet. Ein Beispiel für eine solche Sprache ist LISP, in der der Berechnungsgraphen als Klammergebirge kodiert wird, und die Operation immer am Anfang direkt benannt wird:

Es gibt viele Sprachen, die speziell dafür entworfen wurden, um möglichst einfach zurück in Bäume verwandelt werden zu können. Dazu zählen z. B. XML oder JSON, sowie die meisten Binärformate (auch dies sind oft „kontextfreie“ Schachtelungen von Datenpaketen) von verschiedenen Anwendungsprogrammen, wie z. B. PDF.
Wie funktioniert nun ein Parser?
Die Theorie der kontextfreien formalen Sprachen wird also durch zwei Probleme kompliziert: Zum einen kann es unauflösliche Mehrdeutigkeiten geben, und wir müssen dafür sorgen, dass dies in unserer Codierung keinen Probleme macht. Leider ist dies nicht so einfach zu garantieren. Zum zweiten ist es nicht immer ganz einfach, zu erkennen, wo die Grenzen der Bausteine liegen, auch wenn dies durch die Grammatik eindeutig festgelegt ist. Der einfachste Ansatz wäre ein Backtrackingalgorithmus, der alle Kombinationen, den String in Bausteine aufzuteilen, einfach brute-force durchprobiert, aber das wäre exponentiell (also: viel zu) teuer.
Es gibt Parsingalgorithmen, die jede kontextfreie Sprache (in geeignet transformierter Form der Grammatik) in \(\mathcal{O}(n^3)\) Zeit in einen Baum übersetzt (für \(n\) Eingabezeichen). Das ist zwar nicht unmöglich teuer, aber immer noch sehr praxisfern. In der Praxis nutzt man daher in der Regel spezielle Typen von Grammatiken (LR(0), LR(1), LR(k), LL(k) u.ä.), die den Entwurf der Sprache zu Gunsten der Effizienz etwas einschränken. Dazu gehören dann effiziente Parsingalgorithmen wie der LR-Parser (Bottom-Up-Parser) oder Recursive Descent Parser (Top-Down-Parser). Diese Grammatiken zeichenen sich dadurch aus, dass man nur einige wenige (maximal k) aufeinanderfolgende Symbole anschauen muß, um mit Sicherheit entscheiden zu können, wie der Baum aufgabaut werden muß (eine volle Klammerung wäre z. B. eine LR(0)-Sprache — bei jeder Klammer weiß man sofort, was zu tun ist).
In unserer Aufgabe schauen wir uns eine einfache Sprache für mathematische Ausdrücke an, für die man einen einfachen Parser „direkt“ per Hand bauen kann. Für etwas komplexere Notationen benötigt man Algorithmen, siehe etwa shift-reduce parser für (im allgemeinen) LR(k)-Grammatiken.
Dieser Parser baut immer Teilbäume von links nach rechts auf. Hierzu sollten wir uns nochmal genau Abbildung 2 anschauen: geht man von links nach rechts durch die Zeichenkette, erkennt man nacheinander die Teilbäume „(42)“, dann „((42)+?)“, dann „((42)+(23))“, dann „(((42)+23) + ?)“, und so weiter. Wenn man den Baum so aufbaut, muß man zwei Entscheidungen treffen: (1) Wo ist die Grenze eines Elementes, und (2) Wie wird der Baum geordnet (hier gibt es zwei Möglichkeiten: Soll der Operator linker Teilbaum und der aktuelle Operator der neue Wurzelknoten werden, oder umgekehrt?). Um diese Frage zu beantworten, schaut der Parser immer einen Operator in die Zukunft, und legt noch ungeordnete Teillösungen auf einem Stack ab, um diese später zusammenzusetzen. Die Ordnung wird dabei entweder durch die Grammatikregeln (Schachtelungsordnung) entscheiden oder es wird eine zusätzliche Assoziativitätsregel verwendet (wenn man den Parser von Hand schreibt, wie auf diesem Aufgabenblatt, spielt diese Unterscheidung keine Rolle; wichtig wäre das nur, wenn man einen Parsergenerator schreiben wollte, der aus Grammatiken automatisch einen Parser konstruiert).
Im Prinzip kann man mit diesem Formalismus automatische Übersetzer für beliebige Programmiersprachen schreiben (Parsergeneratoren wie z. B. Lex \& Yacc); für unser Aufgabenblatt geht das natürlich zu weit; die handgeschriebene Lösung ist einfach und braucht im Vergleich nur wenige Zeilen Python oder JAVA Code.
Selbstverständlich existieren bereits sehr spezielle Parser für mathematische Ausdrücke; in dieser Aufgabe sollen jedoch Sie die Zügel in die Hand nehmen und — natürlich angeleitet — einen eigenen Parser entwickeln, der die Syntax einer Zeichenkette so in Teile zerteilt, dass die übriggebliebenen Stücke semantisch leicht in Beziehung gebracht werden können.

Aufgaben

1. Implementieren Sie nun den Parser
   Die praktische Aufgabe besteht nun darin für eine eingegebene Zeichenkette einen dazu passenden Baum auszugeben. Falls Sie, wie vorgeschlagen, für die einzelnen Operationen auf der Funktionenalgebra eigene Unterklassen erstellt haben, ist dies sehr einfach: Sie haben die nötigen Datenstrukturen nämlich bereits! Die Knoten des Baumes sind gerade Function Objekte, die Kinder sind jeweils die Operanten der Funktion. Haben Sie etwa eine + Operation erkannt und die beiden Operanten x und y schon geparst, so erzeugen Sie den neuen + Knoten im Baum einfach mit AddFunction(x,y) (die neu erstellte AddFunction Instanz ist der neue Knoten mit den beiden Kindern x und y). Ihr Parser liest also eine Zeichenkette ein und wandelt sie in ein (verschachteltes) Function Objekt um.
   
   Wir betrachten als erstes eine noch weiter vereinfachte Form der Polnischen Notation. Erlaubt sind die binären Operatoren +,-,*,/, sowie Zahlen und Symbole bestehend aus genau einem einzelnen Symbol (0,1,...,9,x,a). Wenn jedes Symbol aus genau einem Symbol besteht, können wir auch die Leerzeichen entfernen. Erlaubt sind zunächst also z. B.: +1+23 oder +*+1x3-47.
   
   Gehen Sie also Zeichen für Zeichen durch die eingegebene Zeichenkette und geben Sie den passenden Baum aus.
2. Lexikographische Analyse:
   Im ersten Aufgabenteil haben wir nur mit Symbolen gearbeitet, die nur aus einem einzigen Zeichen bestehen. In der Implementierung möchten wir auch längere Zahlen sowie Funktions- und Operatornamen wie sin oder mod erlauben, die aus mehr als nur einem Zeichen bestehen. Daher Teilen wir das Parsen in zwei Schritte auf: die lexikographische Analyse und das Aufbauen des Baumes (auch bekannt als syntaktische Analyse).
   
   Extrahieren Sie dazu beim Parsen zuerst alle im String vorkommenden Tokens in eine Liste. Tokens sind zusammenhängende Folgen von Zeichen, die elementare Sinneinheiten der Sprache bilden: In unserem Fall benötigen wir die folgenden Tokens: Zahlen (die ganze Folge von Ziffern, mit Dezimalpunkt, ist nur noch ein Tokenobjekt), Operatorenzeichen (wie +,*,-), Funktionsnamen (sin, cos) und Variablennamen. Praktischer Weise ist das erkennen der Grenzen eines Tokens in der Polnischen Notation sehr einfach: alle Zeichen, die von Leerzeichen getrennt werden sind eine Sinneinheit bzw. ein Token.
   
   Ein paar Tipps dazu:
   Hinweis 1: Gehen Sie zeichenweise durch die Zeichenkette durch und manipulieren Sie den Laufindex entsprechend des Fundes (Python erlaubt Indexmanipulation nicht in for-Schleifen. Verwenden Sie daher eine while-Schleife).
   Hinweis 2: Beginnen Sie damit Leerzeichen abzudecken und dann auch Zahlen beliebiger Länge zu erkennen (weitere Schleife beim Fund einer Ziffer). Eval-Funktionen oder ähnliches sind dabei nicht erlaubt! Speichern Sie Zahlenstrings direkt als Python-Zahlen ab. Verwenden Sie beispielsweise die unten genannten Funktionen, um aus einem String wie etwa „123.34“ eine Python-Zahl zu erstellen oder schnell zu prüfen, ob es sich um eine Ziffer handelt.
   Hinweis 3: Da wir auch längere Variablennamen und auch Funktionen und Operatoren erlauben, erstellen Sie eine Gesamtliste aller Tokens, die sie suchen möchten und ordnen Sie die Gesamtliste der Länge nach (längste Tokens zuerst). So können sie die Klasse des aktuell untersuchten Zeichens schneller herausfinden. Später benötigen wir jedoch nicht nur die Token, sondern auch die Referenz auf das tatsächliche Objekt (von Typ Function oder Operator), das diesen Token enthält, um uns die erneute Suche zu späterer Zeit zu ersparen. Es bietet sich also an eine Liste zu erstellen, die aus Tupeln der Art (obj, i) besteht und nach der Länge der Token (obj.token) sortiert wird. (Tipp: Siehe die Python-Funktion sorted und enumerate). Beginnen Sie nun mit dem längsten Token und prüfen Sie, ob dieses an der aktuellen Stelle vorhanden ist.
   
3. Der eigentliche Parser
   Der Parser bekommt eine Liste von Tokens als Eingabe (er muss sich also nicht mehr um alle kleinen Details kümmern). Sie sollten nun eine Liste aller der gültigen Tokens in Ihrem String haben (mit Wiederholungen und in der selben Reihenfolge, wie in der Zeichenkette selbst.
   
   Übersetzen Sie diese Tokenliste nun mithilfe Ihres Algorithmus aus Aufgabenteil 1 in eine Baumstruktur; jeder Eintrag in der Token-Liste kann nun als ein einzelnes Zeichen erachten werden (das macht die Anpassung des Codes relativ einfach ☺).

4.4 Interaktiver Funktionsplotter

[10 Punkte]

Implementieren Sie nun ein Programm, dass aus einem eingegebenen Ausdruck die zugehörige Funktion sowie die Ableitung zeichnet. Alles was Sie dazu benötigen sollten Sie bereits implementiert haben. Nun muss es nur noch zusammengesetzt werden.

Aufgaben

• Implementieren Sie ein PyQt-Programm mit einem Eingabefeld (QLineEdit), das einen beliebigen String erwartet und den zugehörigen Plot und seine Ableitung anzeigt. Dazu müssen Sie den Ausdruck aus dem Eingabefeld einlesen, mit Hilfe ihres Parsers in ein Function umwandeln.
  
  Hinweis: Beachten Sie, dass der eingegebene Ausdruck fehlerhaft sein kann, oder vielleicht auch ungültige Operationen durchführt (Division durch Null). Damit Ihr Programm nicht abstürzt, müssen Sie derartige Fehler abfangen und geeignet reagieren (z. B. könnten Sie dann den Wert 0 annehmen, damit der Rest des Funktionsgraphen dennoch korrekt geplottet wird).) Fehler können z. B. mit den folgenden Python-Befehlen abgefangen werden:

try:
	... # Code mit evtl. Laufzeitfehlern
except:
	... # Behandlung im Falle eines Fehlers

Mögliche Erweiterungen:

• Auswahl zwischen der numerischen und mittels Automatischem-Differenzieren berechneten Ableitung
• Zeichnen Sie auch die Tangente an frei auswählbarem Punkt (um zu sehen, dass die Ableitung auch wirklich die Ableitung ist)