Numerik und Informatik

Programmbibliotheken

Mathematische Symbole unter Windows

Ich schreibe mathematische Texte mit Word; dabei fehlen mir die Symbole für Zahlenmengen, also $\mathbb{N}$, $\mathbb{Q}$, $\mathbb{R}$, …, diese Großbuchstaben mit Doppelbalken.

Bookshelf Symbol 5 (Office 97) enthält einige dieser Zeichen und außerdem Euclid Math 2 (Math Type 4). Diese kannst Du Dir auf der Seite http://www.mathtype.com/support/fonts/default.stm herunterladen. Da sind noch andere sehr brauchbare und schöne Schriften bzw. Zeichen dabei.

Stephan Bielicke <ed.enilno-t|ekcileib#ed.enilno-t|ekcileib>

Auch an dieser Stelle sei noch einmal auf LaTeX verwiesen; Informationen dazu gibt es unter http://www.dante.de sowie in de.comp.text.tex.

Gibt es algorithmisch unlösbare Probleme?

Zunächst sei zur Präzisierung der Fragestellung genauer dargelegt, was wir unter einem Problem und einem Lösungsalgorithmus verstehen wollen. Ein Problem ist ein Paar, bestehend aus einer Eingabe und einer gewünschten Ausgabe. Ein Beispiel hierfür:

Eingabe: ein Text T und eine ganze Zahl n.
Ausgabe: ,,ja", wenn der Text T länger als n Zeichen ist, ,,nein" sonst.

Unter einem Lösungsalgorithmus verstehen wir einen Algorithmus, d.h. ein Programm, eine Prozedur, eine Turingmaschine, …, der für alle möglichen Eingaben nach endlicher Zeit die gewünschte Ausgabe macht. Insbesondere darf der Lösungsalgorithmus für keine gültige Eingabe in eine Endlosschleife geraten. In unserem Beispiel wäre ein Lösungsalgorithmus also beispielsweise eine Prozedur ZÄHLE(T,n), die für alle Paare (T,n) nach endlicher Zeit entweder ,,ja" oder ,,nein" ausgibt, je nachdem, ob der Text T länger als n Zeichen ist oder nicht. Hierfür kann sicherlich jeder sofort eine kleine Pascal-Prozedur angeben, womit dieses Problem algorithmisch lösbar ist.

Ein im Bereich der Computeralgebra unlösbares Problem ist es zu entscheiden, ob ein beliebiger Ausdruck f(x) in einer Variablen x, der neben den natürlichen Zahlen und den vier Grundrechenarten auch den natürlichen Logarithmus, die Exponentialfunktion sowie die trigonometrischen und hyperbolischen Funktionen und ihre Umkehrungen enthalten darf, die Eigenschaft

für alle x in $\mathbb{C}$ gilt f(x)=0

hat. Die gängigen Computeralgebrasysteme wie Maple, MuPAD, Axiom oder Mathematica lösen dieses Problem nur teilweise, d.h. für gewisse, ,,einfach aufgebaute" Ausdrücke f(x). Für beliebige f(x) ist das Problem algorithmisch nicht lösbar.

Das Paradebeispiel für ein algorithmisch unlösbares Problem und meines Wissens das erste, für das der Beweis der Unlösbarkeit erbracht wurde, ist das berühmte Halteproblem, mit dem jeder Informatiker während seines Grundstudiums zusammenstößt. Den Unlösbarkeitsbeweis kann man auf viele verschiedene Arten formulieren, die Idee ist aber immer dieselbe. Hier ist ein Beweis, der eine Pascal-ähnliche Notation zur Darstellung von Algorithmen benutzt:

Satz: Das Halteproblem

Eingabe: Programmquelltext P und Eingabetext E
Ausgabe: ,,ja", wenn P(E) nach endlicher Zeit hält, ,,nein" sonst

ist algorithmisch unlösbar.

Beweis. Nehmen wir an, das Problem wäre algorithmisch lösbar, d.h. es gibt ein Programm HALT, das für alle Paare (P,E) nach endlicher Zeit gemäß obiger Spezifikation die Anwort ,,ja" oder ,,nein" ausgibt.

Unter Benutzung dieses Programmes schreiben wir ein weiteres Programm SELTSAM, das einen Text T als Eingabe erhält:

PROCEDURE SELTSAM(T);

LOCAL PROCEDURE HALT(P,E); …; (* hier steht die HALT-Prozedur *)

BEGIN
IF HALT(T,T)="ja" THEN (* (XXX) siehe unten *)
WHILE 1=1 DO
nop
ENDWHILE; (* Endlosschleife *)
ELSE
Write("Hallo"); (* Programm terminiert mit Ausgabe *)
ENDIF;
ENDPROC;

Nun stellen wir uns die Frage, was passiert, wenn man dem Programm SELTSAM den eigenen Quelltext als Eingabe gibt. Es gibt prinzipiell nur die beiden Möglichkeiten, dass SELTSAM(SELTSAM) terminiert (nach endlicher Zeit anhält) oder dies eben nicht tut. Wir untersuchen beide Fälle:

Fall 1: SELTSAM(SELTSAM) terminiert.

In diesem Fall liefert HALT(SELTSAM,SELTSAM) das Ergebnis ,,ja". Im obigen Programm wird also an der Stelle (XXX) in den THEN-Teil verzweigt, wo sich eine Endlosschleife befindet. Das heißt aber, dass der Aufruf SELTSAM(SELTSAM) nicht terminiert, ein Widerspruch.

Dieser Fall kann also nicht eintreten. Untersuchen wir den anderen Fall:

Fall 2: SELTSAM(SELTSAM) terminiert nicht.

Also liefert HALT(SELTSAM,SELTSAM) das Ergebnis ,,nein", und in obigem Programm wird in den ELSE-Teil verzweigt. Dort wird ,,Hallo" ausgegeben und anschließend korrekt terminiert. Also terminiert SELTSAM(SELTSAM), ein Widerspruch.

Dieser Fall kann also auch nicht eintreten. Da es aber nur diese beiden Fälle geben kann, heißt dies, dass wir grundsätzlich an einen Widerspruch geraten, solange wir die Annahme aufrecht erhalten, dass es ein Programm HALT gibt.

Somit ist die Annahme, das Halteproblem sei algorithmisch lösbar, falsch, d.h. der Satz ist bewiesen.

Andreas Jung <ed.kcotsor-inu.kitamrofni|gnuja#ed.kcotsor-inu.kitamrofni|gnuja>

Computeralgebrasysteme

Zu den wohl bekanntesten Computeralgebrasystemen zählen:

Tjark Weber <ed.xmg|rebew.krajt#ed.xmg|rebew.krajt>

Was bedeutet ,,Algorithmus"?

Der Algorithmus hat weder etwas zu tun mit dem Rhythmus noch mit dem Logarithmus, sondern ist die lateinisch adaptierte Form des Namens des Mathematikers Abu Ja'far Muhammad ibn Musa Al-Khwarizmi. Vom Titel eines seiner Manuskripte ist übrigens auch das Wort Algebra abgeleitet.

http://www.kk.s.bw.schule.de/mathge/alhwariz.htm
http://www-history.mcs.st-and.ac.uk/history/Mathematicians/Al-Khwarizmi.html

Hermann Kremer <ed.enilno|remerk.nnamreh#ed.enilno|remerk.nnamreh>

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-NoDerivs 3.0 License