Am Ende des ersten Skriptes wird auf die verschiedenen O-Notationen eingegangen.
Frage ist nun: dieses n index 0, das immer kleiner gleich n sein soll.
Was ist das? Eine Zahl, die frei wählbar ist?
natürlich? reell? Skript schweigt sich dazu freundlich aus..
Dieses n index 0 soll dann aber die Untergrenze sein, für die die Definition bzw. im Speziellen dann der Anwendungsfall gilt?

Kann ich auch noch einen draufsetzen.
Was hat man sich unter
O(f(n) + g(n)) = O(max(|f(n)|,|g(n)|)
vorzustellen? (das max interessiert mich da)
(jojo sry, is easy mathe aber soweit bin ich noch nicht ^^)

1. Zu Fragen ist nicht dumm.

2.
"n0 < n" heißt in diesem Zusammenhang Folgendes: Es gibt ein n0 (irgendeine natürliche Zahl), so dass für alle Zahlen, die größer sind als n0 die folgende Aussage gilt.
Da bei der O-Notation ja die Komplexität z.B. eines Algorithmus betrachtet werden soll, ist der Wert der Funktion f oder g für kleine Zahlen gar nicht so interessant. Erst im großen Bereich sind die Aussagen wichtig.

Z.B. Ab n0=20000 gilt f(n) > n³ für n > n0


max(a,b) ist eine Funktion, die dir das Maximum der Werte a und b zurückgibt. In diesem Fall also |f(n)| bzw. |g(n)|, je nachdem, welches größer ist.

Jo vielen dank

Zu der Max-Funktion noch:
Ist es ein Unterschied, ob man max(a,b) oder max{a,b} (bzw. min im skript) schreibt? Denn im skript gibt es beide Versionen. Besteht da ein Unterschied?

Ja, aber er ist für euch erstmal vernachlässigbar.

Die Funktion "max(a, b)" berechnet das Maximum zweier gegebener Parameter (Werte) a und b.
Die Funktion "max{a,b}" berechnet das Maximum der in der als Parameter übergebenen Menge {a, b}.
Einmal wird dser Funktion also zwei Werte, einmal eine Menge als Parameter übergeben. Es sind also unterschiedliche Funktionen, die aber das Gleiche berechnen.

Wobei ich max{a, b} fuer eine unschoene Notation halte. Klarer waere: max({a, b})

Mo

Da habe ich auch gleich zwei Fragen:

1) Was bedeutet eigentlich das * z.B. beim Eingabealfabet der TM? Beim Bandalfabet heißt es ja Gamma \ {#}, und bei Sigma? Oder auch später bei der Chomsky Grammatiken bei Vn oder Vt (Typ-0 G:={Vn,Vt,P,S}? Heißt * ohne leeres Wort/Eingabe?

2) Kann mir jemand sprachlich erklären, wie der µ-Operator definiert ist und was er tolles leistet bzw. was so toll an ihm ist. Irgendwie kann ich mit der Definition im Skript nichts anfangen - verstehe sie irgendwie nicht!

Vielen Dank!

so ein Alphabet wie in allen von dir genannten Kontexten ist eine Menge von Buchstaben,
Beispiel A = {a,b,c,7,#}

Interessant ist die Menge der daraus zusammenstellbaren Wörter,
z.B.
abc, bbbbbc, lambda (leeres Wort), ##77 usw.

die Menge aller möglichen Wörter ist A*,
eine unbeschränkt lange aber möglicherweise auch leere Folge von Elementen aus A,

A+ ist auch wichtig, A+ = A* \ {lambda}, also alle Wörter nur nicht das leere Wort

die zweite Frage, naja, also ich versuchs lieber gar nicht erst,
scheitere da auch oft genug, vielleicht machts jemand anders ;)

das ist wohl die schwierigste Definition überhaupt im Skript,
wenn nicht gar in allen Vorlesungen,
darüber kannst du nachdenken wenn du Fragen wie die obere im Schlaf beherrscht

Kann mir jemand sprachlich erklären, wie der µ-Operator definiert ist und was er tolles leistet bzw. was so toll an ihm ist. Irgendwie kann ich mit der Definition im Skript nichts anfangen - verstehe sie irgendwie nicht!

Also ich kann es mal versuchen. Die primitiv rekursiven
Funktionen reichen ja noch nicht aus, um alle
(Turing-)berechenbaren Funktionen zu definieren (das ist auch
recht einleuchtend: die primitiv-rekursiven Funktionen sind
überall definiert, während nicht alle Turing-berechenbare
Funktionen überall definiert sind - die berechnende TM muss
nicht auf jeder Eingabe anhalten).

Das kann man erst, wenn man den µ-Operator hinzunimmt, d.h.:
erlaubt man primitiv-rekursive Grundfunktionen, Substituion,
primitive Rekursion und den µ-Operator, dann können alle
(Turing-)berechenbaren Funktionen definiert werden.

Da man den µ-Operator braucht, um die Turing-berechenbaren
Funktionen zu bekommen, ist zu erwarten, dass der µ-Operator
Funktionen liefert, die nicht überall definiert sind.

Und zwar funktioniert er so: Wenn man ihn auf eine Funktion f
mit r Argumenten anwendet, so erhält man eine neue Funktion,
nennen wir sie [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi[/img], mit r-1 Argumenten, die
zu vorgegebenen Argumenten [img]http://mokrates.de/cgi-bin/texstring?x_1%2C%5Cldots%2Cx_%7Br-1%7D[/img]
die kleinste Zahl y liefert, mit der gilt
[img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy)%3D0.[/img]
Da zu gibt es allerdings eine Ausnahme:
Wenn [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy')[/img] für irgendein
y'<y nicht definiert ist, so ist [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(x_1%2C%5Cldots%2Cx_%7Br-1%7D)[/img] auch nicht definiert.

Das wars. Man kann es auch so formulieren: Der µ-Operator liefert zu gegebenen Anfangsargumenten (das waren die [img]http://mokrates.de/cgi-bin/texstring?%0D%0Ax_1%2C%5Cldots%2Cx_%7Br-1%7D[/img]) die kleinste Nullstelle von f
bzgl. des letzten Arguments, aber nur dann, wenn f auf _allen_
kleineren "letzten Argumenten" auf den vorgegebenen
Anfangsargumenten definiert ist.

(Wegen der Obergrenze für die Anzahl von Bildern, hier der
Rest des Postings:)

Man erkennt, dass es zwei Situationen geben kann, in denen [img]http://mokrates.de/cgi-bin/texstring?%5Cpsi(x_1%2C%5Cldots%2Cx_%7Br-1%7D)[/img] nicht definiert
ist:
1. Wenn [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy)[/img] niemals (d.h.
für kein einziges y) 0 wird oder

2. Wenn zwar [img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy)%3D0[/img], aber
es ein y'<y gibt, so dass
[img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy')[/img] undefiniert ist
(das kann z.B. der Fall sein, wenn f selbst schon mit
µ-Operator entstanden ist).


Das ganze natürlich ohne Gewähr, jeder ist eingeladen,
Fehler zu beseitigen. [img]http://www.fb18.de/gfx/23.gif[/img]

Das ganze natürlich ohne Gewähr, jeder ist eingeladen,
Fehler zu beseitigen.

[img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D)[/img] undefiniert ist

[img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy')[/img], oder?

Das ganze natürlich ohne Gewähr, jeder ist eingeladen,
Fehler zu beseitigen.

[img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D)[/img] undefiniert ist

[img]http://mokrates.de/cgi-bin/texstring?f(x_1%2C%5Cldots%2Cx_%7Br-1%7D%2Cy')[/img], oder?

Stimmt! Fehler beseitigt [img]http://www.fb18.de/gfx/23.gif[/img]