Notation (Komplexitätstheorie)

28.03.2012, 13:44	MI	Auf diesen Beitrag antworten »
Notation (Komplexitätstheorie) Hallo allerseits, Ich muss mich derzeit in Komplexitätstheorie (im Hinblick auf Quantencomputer, aber dafür lohnt es sich wohl, vorne anzufangen ) einlesen und benutze als Leitfaden das Skript zur Komplexitätstheorie hier: http://www.logic.rwth-aachen.de/Teaching...9/index.html.de Jetzt habe ich ein kleines Notationsproblem. Es geht um die Notation f#x, genauer: Auf Seite 11 (Abschnitt Hierarchy Theorems) werden allgemeine Komplexitätsklassen definiert. Dann (letzter Paragraph) wird angenommen es existiere eine Funktion $\begin{eqnarray} \rho \end{eqnarray}$ , die Maschinen über dem Alphabet $\begin{eqnarray} \{0,1\} \end{eqnarray}$ so codiert, dass die Struktur einer solchen Maschine und ihr Verhalten effektiv von $\begin{eqnarray} \rho(M) \end{eqnarray}$ rausgeholt werden kann. Mir ist nicht ganz klar, was damit gemeint ist, was vielleicht das Problem erklärt: In der Definition 1.23 (Seite 12) schriebt er: \rho(M)#x (das Symbol # will er nicht in LaTeX darstellen). Und das ist leider nicht erklärt. In anderen Texten, die ich zum Einarbeiten habe, gibt es diese Symbolik nicht - im Internet habe ich Ähnliches nur in Texten über Komplexitätstheorie gefunden, auch dort ohne Erklärung. Da diese Art der Notation noch häufiger vorkommt - kann mich da vielleicht jemand aufklären? Gruß MI
30.03.2012, 23:32	Abakus	Auf diesen Beitrag antworten »
RE: Notation (Komplexitätstheorie) Hallo, ich kann nur rumvermuten. Könnte das ein Hintereinanderschreiben-Symbol sein? Abakus
31.03.2012, 01:41	SusiQuad	Auf diesen Beitrag antworten »
RE: Notation (Komplexitätstheorie) Ich kenne $\begin{eqnarray} \sharp \end{eqnarray}$ 'sharp' aus der Ecke asymptotischer Dichten () als Abzähl-Op. (von Mengen bzw. Folgen). Immerhin spricht der Verf. auf S. 92 von $\begin{eqnarray} \color{blue}\sharp ~\exists,\forall, R-\small\text{operators} \end{eqnarray}$ , beachte die Komma-Setzung. _____________ () i.S.v. $\begin{eqnarray} \lim \sup \frac{\sharp \{ a_n \leq n \}}{n} \end{eqnarray}$ als Bsp.
31.03.2012, 08:47	MI	Auf diesen Beitrag antworten »
RE: Notation (Komplexitätstheorie) Danke für eure Erklärungsversuche! @abakus: Ja, ich denke mittlerweile auch, dass das irgendeine Form von Hintereinanderschreiben ist. Vielleicht ist der Output der Funktion eine Menge von Werten und mit dem # wird angezeigt welche der Werte jetzt genommen werden soll. @SusiQuad: Zumindest vorne kann ich mir das eher nicht vorstellen, aber danke für den Hinweis. Ich werde zumindest mal schauen, was es damit genau auf sich hat. Nachher sehe ich noch einen ehemaligen Kommilitonen, der bei dem Professor einige Vorlesungen gehört hat, vielleicht kann der mir helfen. Ich hatte nur gedacht, dass das eventuell einfach Standardnotation ist, die ich aufgrund meines Quereinstiegs einfach nicht kenne. Aber ganz so einfach scheint es ja nicht zu sein. Gruß MI

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »