Theoretische Informatik: Komplexität und co.

[kas]

Was haltet ihr von folgender Ausage?

1. Bei der Bestimmung der asymptotischen Komplexität fallen Konstanten weg.

Richtig oder falsch? Kann man das so verallgemeinern?

der ratlose

 

[medikit]

Die Abschätzung der Komplexität hängt von der Art der Menge ab, wofür die Komplexität eingeschätzt werden soll. Schätzt man die Komplexität des Verhaltens eines Bechers mit Murmeln beim Umkippen ein hat man mehr zu tun als wenn man man das Verhalten aller natürlichen Zahlen bei der Subtraktion von 1 einschätzen will. Für die Murmeln habe ich viele physikalische Faktoren zu kalkulieren, für die Subtraktion reicht einmal Induktion.

Ich verstehe nicht, worauf sich die Konstanten beziehen soll und rate: richtig, aber nicht verallgemeinerbar; (z.B. bei Kostenfunktionen).

Die richtige Anwort teilst Du uns dann mit?

 

[kas]

Naja es geht um die Zeitkomplexität bei Automaten. Wenn ich mir so Funktion wie:

g= 5n^3 + 7n + 10 log tief5

ansehe, dann könnten doch alle Konstanten wegfallen, weil sie differentiell klein sind, da n gegen unendlich strebt.

Oder nicht?

der hier möglicherweise verständigungsprobleme hat
.
EDIT (autom. Beitragszusammenführung) :

.
Nachtrag: In O-Notation Ausgedrückt: T element O(n^4)

 

[catch22]

Ja. Denn du betrachtest Grenzwerte.
http://de.wikipedia.org/wiki/Landau-Notation

Beispiel:
Angenommen du hast eine Funktion foo, welche bei jedem Aufruf n Operationen durchfuehrt. Foo waechst also hoechstens linear. Dann liegt foo in O.
Eine zweite Funktion bar, welche bei jedem Aufruf n+1 Operationen durchfuehrt, waechst aber ebenfalls linear. Damit liegt auch bar in O.

Ich hoffe das beantwortet die Frage.

 

[kas]

Ja, cool, danke!

Hatte genau das gleiche (und anderes darüber) bei Wiki gefunden. War mir nur nicht sicher, ob ich es richtig verstanden habe.

Es handelte sich um eine Kalusuraufgabe. Ich hab noch mehr so "dinger". Bin der Meinung (also nicht nur ich), dass mein Prof nen kleinen Schaden hat. Er hat, gerade über C++ und Visual Studio, mehrere Bücher über den Hansa Verlag rausgebracht. Oh, hoffentlich hab ich nicht zuviel gesagt...

 

[kas]

OK, dann interessiert mich noch die Richtigkeit folgender Aussage:

2. Produktionen kontextfreier Grammatiken haben links Terminale.
Ich sage NIEN, mein Prof sagt JA.

Wer hat folgendes nicht richtig verstanden:
http://de.wikipedia.org/wiki/Chomsky-Hierarchie#Typ-2-Grammatik_.28kontextfreie_Grammatik.29

 

[catch22]

Au Backe... das ist alles schon eine Weile her.
Aber wenn du mir noch eure Definition von 'links Terminal' gibst, kann ich dir darauf bestimmt auch eine Antwort geben.
Ich habe im Moment auch leider meine ganze Literatur zu diesem Thema ausgeliehen....

 

[kas]

Die Aussage habe ich original aus der Klausur abgeschrieben.

Aus Wiki und co. interpretiere ich das:

A->y links (vom Pfeil) ein Nichtterminal ist und rechts das y als Platzhalter für das Wort dient, dass aus Terminalen und Nichtterminalen bestehen kann.

Die Wiki'sche Definition sagt aber nicht genau das A ein Nichtterminal sein MUSS. Es steht lediglich da, dass es ein Nichtterminal ist. Möglicherweise ist der Artikel unvollständig. Ich möchte da aber, solange ich nicht sicher bin, den Artikel anpassen.

 

[JpG]

irgendwie treibt mir die diskussion hier die idee wirklich informatik zu studieren gründlich aus *gggggg*

 

[subnote]

Ach, so schwer ist das gar nicht. Bisschen Mathe und Physik

Automaten hatten wir z.B. nur ein Semester - interessanter sind da Themen wie Prozessautomatisierung, Digital- und Analogtechnik, etc.

 

[Gelöschtes Mitglied 27096]

aber was bringt es ein terminalsymbol noch weiter zu zerlegen ?
auf der linken seiten stehen immer die Nichtterminale bzw. das Startsymbol

 

[catch22]

Die Wiki'sche Definition sagt aber nicht genau das A ein Nichtterminal sein MUSS. Es steht lediglich da, dass es ein Nichtterminal ist. Möglicherweise ist der Artikel unvollständig. Ich möchte da aber, solange ich nicht sicher bin, den Artikel anpassen.

Also, nachdem ich mir den Artikel nochmal durchgelesen habe, muss ich sagen: Er ist schlecht, und sogar teilweise falsch.
So koennen kontextfreie Gramatiken von auch von deterministischen Kellerautomaten erkannt werden. Nicht nur von nichtdeterministischen. Nichtdeterministische Kellerautomaten sind ungleich maechtiger und koennen sogar Turingmaschienen simmulieren! (wenn ich mich nicht irre; ach da verleiht man einmal seine Literatur )
Und nichdeterministische Turingmaschienen erkennen _jede_ Sprache nicht nur kontextsensitive.

Kontextfreie Sprachen erweitern die Regulaeren lediglich um Pallindrome und aehnlich Konstrkte. Also Worte wie a^n b^m a^n oder (ab)^n c^n mit n,m aus N.

Und ja, auf der linken Seite der Konstruktionsvorschrift sollte immer ein Nonterminalsymbol stehen, keine Terminalsymbole.

Ich habe dazu noch eine englische Wikipediaseite gefunden die besser ist: http://en.wikipedia.org/wiki/Context-free_grammar

Aber wenn dein Prof das in seiner Vorlesung anders Definiert hat, kannst du wenig machen. Denn die Definition aus der Vorlesung ist bindend fuer die Klausur.

Du kannst lediglich hoffen das man mit dem Menschen reden kann. Die meisten Professoren die ich kenne lassen sich auch mal von Studenten korrigieren.

Ach, so schwer ist das gar nicht. Bisschen Mathe und Physik

Automaten hatten wir z.B. nur ein Semester - interessanter sind da Themen wie Prozessautomatisierung, Digital- und Analogtechnik, etc.

Das hoert sich aber mehr nach Elektrotechnik an.
Ich fuer meinen teil finde Komplexitaetstheorie garnicht so schlecht. Immmer noch besser als Logik und automatische Beweisfuehrung oder Verifikation.

aber was bringt es ein terminalsymbol noch weiter zu zerlegen ?
auf der linken seiten stehen immer die Nichtterminale bzw. das Startsymbol

Genau. Zumindest bei kontextfreien Sprachen. Bei rekusiven kann man durchsauch Kosntuktionen wie St -> Stt haben, mit S aus der Menge der Nonterminalsymbole und t,u aus der Menge der Terminalsymbole.

 

[kas]

...g= 5n^3 + 7n + 10 log tief5 ...

...Nachtrag: In O-Notation Ausgedrückt: T element O(n^4)

Die asymptotische Komplexität wird durch den größten Exponenten festgelegt.
Ich muss also meine Feststellung korrigieren:

T element O(n^3)

ist nun richtig!

 

[medikit]

Chomsky lebt noch, möglichwerweise könnte man den Meister selbst fragen.