FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Formale Informatik

F2 blatt 3, aufgabe 3.2

F2 blatt 3, aufgabe 3.2 2003-04-26 19:28
Morpheus
sorry das andere teil wurde mir zu voll. Ich rall diese aufgabe von a bis z nich. Was sind nun genau diese erweiterungen <lex und <lg-lex. Wie definiere ich solche abstrusen Ordnungen überhaupt.Was heisst komponentenweise identisch.Wie iss die zweite bedingung zu verstehen.Was iss eine Parikh abbildung.Was iss der sinn des lebens?…

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 20:03
TriPhoenix
Am besten stellich den F2-Ordner nie wieder aufs Regal sondenr behalte ihn imemr g elich hier [img]http://www.fb18.de/gfx/7.gif[/img]

Was sind nun genau diese erweiterungen <lex und <lg-lex.
Da hat wohl wer nicht aufgepasst [img]http://www.fb18.de/gfx/22.gif[/img] Mit geschwungenem < sind lex unf lg-lex Ordnungsrelationen auf Wörtern. <lex ist die "klassische" lexikonartige Ordnung, d.h. man sortiert Wörter, wie sie im Lexikon stehen, also jeweils nach dem ersten, verschiedenen Buchstaben im Wort. lg-lex sortiert zusätzlich werst nach Länge der Wörter, sind zwei Wörter gleichlang, so sortiert es wieder lexikonartig.
Auf Tupeln gibts ähnliches, lex sortiert hier wieder nach dem ersten voneinander verschiedenen Wert, so ist z.B. (2, 3) <lex (2, 4). lg-lex sortiert hier erst nach der Summe aller Elemente, ist die Summe der Elemente gleich, so wird nach lex sortiert. Alles auch nachzulesen im Skript 2.55-2.58

Wie definiere ich solche abstrusen Ordnungen überhaupt.
So wie im Skript 2.55-2.58 [img]http://www.fb18.de/gfx/22.gif[/img] Und abstrus sidn sie nun wirklcih nicht. Oder ist es abstrus wie man ein Lexikon aufbaut?

Was heisst komponentenweise identisch.
Tupel sind komponentenweise identisch, wenn alle Teile gleich sind, also z.B. (2, 3, 4) = (2, 3, 4).

Wie iss die zweite bedingung zu verstehen.
Hab ich in http://3773.rapidforum.com/topic=101684879283&search=&reverse=1 schonmal geraten

Was iss eine Parikh abbildung.
Das ist die konfuse ABbildung die da in der Aufgabe definiert ist. Im Prinzip garnicht so schlimm. Die Parikh-Abbildung zählt nach, wie oft jeder Buchstabe in einem Wort vorkommt. Beispiel: Sigma={a, b, c, d, e} Parikh(abcdeddeaacca) = (4, 1, 3, 3, 2) wiel das Wort 4 a, 1 b, 3 c, 3 d und 2 e hat (wenn ich mich nicht verzählt habe).

Was iss der sinn des lebens?…
Nochmal ein Buch vom Regal holen…."WIEVIEL IST NEUN MULTIPLIZIERT MIT SECHS - 42" So stehts geschrieben.


Re: F2 blatt 3, aufgabe 3.2 2003-04-26 20:51
UncleOwen
Kommando zurueck. Das *patsch* geht an mich selber, weil ich meinen Hitchhiker nicht finde…


Re: F2 blatt 3, aufgabe 3.2 2003-04-26 20:53
TriPhoenix
"WIEVIEL IST NEUN MULTIPLIZIERT MIT SECHS - 42" So stehts geschrieben.

*patsch*

Er hat den Hitchhiker falsch zitiert! Steinigt ihn!

Pff…Heine Bücher - Douglas Adams - 5er-Band - Seite 433…steinig dich selber [img]http://www.fb18.de/gfx/24.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:01
UncleOwen
Argh. Jetzt muss ich mich wirklich selbst steinigen…

"What do you get if you multiply six by nine"

Gut, dann weiss ich ja, was ich naechste woche machen muss… (ausser Zimmer aufraeumen)

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:02
TriPhoenix
Argh. Jetzt muss ich mich wirklich selbst steinigen…

"What do you get if you multiply six by nine"

Gut, dann weiss ich ja, was ich naechste woche machen muss… (ausser Zimmer aufraeumen)

[img]http://www.fb18.de/gfx/15.gif[/img][img]http://www.fb18.de/gfx/24.gif[/img] SCNR

Edit: Hey, das Quote verliert die Breaks! Hey Alles verliert die Breaks (zwischen diesem hier und meinem SCNR sind ZWEI \n)



Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:03
Zaphod
Eigentlich musst du dem gesamten Jahrgang als Strafe auch noch was ausgeben [img]http://www.fb18.de/gfx/22.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:05
UncleOwen
Hmm, ich geb Tri ein Bier aus, ist das auch okay? [img]http://www.fb18.de/gfx/15.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:07
TriPhoenix
Hmm, ich geb Tri ein Bier aus, ist das auch okay? [img]http://www.fb18.de/gfx/15.gif[/img]

Hättets ud wohl gerne [img]http://www.fb18.de/gfx/15.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:08
Zaphod
Tri ist strikter Nichtalkoholiker. Und außerdem löscht das nicht auch unseren Durst [img]http://www.fb18.de/gfx/7.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:25
UncleOwen
Tri ist strikter Nichtalkoholiker.
Ach, sach bloss. Erzähl mir was, was ich noch nicht weiss.

Und außerdem löscht das nicht auch unseren Durst [img]http://www.fb18.de/gfx/7.gif[/img]
pff…

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 21:54
TriPhoenix
Tri ist strikter Nichtalkoholiker.
Ach, sach bloss. Erzähl mir was, was ich noch nicht weiss.
Du hast die Betonung verpasst [img]http://www.fb18.de/gfx/15.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 22:15
MoKrates
Wenn Tri ein Bier trinken sollte, dann glaubt er wahrscheinlich daran, dass 6*9=42…

@UO: Ezekiel 24,7: And you will know my name is Slartibartfass when I lay my vengeance upon thee… [img]http://www.fb18.de/gfx/28.gif[/img]

Mo/Ichweissdassichweissdass6*9=42/Krates

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 22:48
Morpheus
seit mir nich böse junx, aba 6*9 iss gleich 54…

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 22:53
Anonymer User
Es tut mir ja leid, dass ich eure Rechenspiele unterbrechen muss, aber es geht noch um das F Blatt! Bei der Definition der Ordnung habe ich Def. 2.52 als Vorlage genommen, doch mir fällt nichts ein wie ich die Rekursion einbauen kann.
In Def. 2.52 letzter Punkt wird die rekursion ja mit (u <lex v) erreicht, wie krieg ich das hin? oder bin ich ganz auf dem falschen Dampfer?
6*9 ist bei mir 999999 [img]http://www.fb18.de/gfx/10.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 22:53
TriPhoenix
seit mir nich böse junx, aba 6*9 iss gleich 54…

Du liest die falschen Bücher [img]http://www.fb18.de/gfx/28.gif[/img] Noch nie am Ende des Universums gespeist?

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 22:55
TriPhoenix
Es tut mir ja leid, dass ich eure Rechenspiele unterbrechen muss, aber es geht noch um das F Blatt!
Wirklich? [img]http://www.fb18.de/gfx/7.gif[/img]

Bei der Definition der Ordnung habe ich Def. 2.52 als Vorlage genommen, doch mir fällt nichts ein wie ich die Rekursion einbauen kann.
In Def. 2.52 letzter Punkt wird die rekursion ja mit (u <lex v) erreicht, wie krieg ich das hin? oder bin ich ganz auf dem falschen Dampfer?
Da du mit Tupeln arbieten musst schau dir doch mal 2.57 und 2.58 an. Vielelicht hilft dir das weiter [img]http://www.fb18.de/gfx/22.gif[/img] Denn dort geht es ja um ähnliche Probleme (Ordnungen auf Tupeln deifnieren)

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 22:57
UncleOwen
Es tut mir ja leid, dass ich eure Rechenspiele unterbrechen muss, aber es geht noch um das F Blatt!

Es tut mir auch sehr leid, aber ich glaube, dieser Thread wurde gehitchhiked. [img]http://www.fb18.de/gfx/24.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-26 23:20
Zaphod
Ezekiel 24,7: And you will know my name is Slartibartfass when I lay my vengeance upon thee…

Hmm… ich hatte da jetzt her sowas wie "Denn das Blut, das sie vergossen hat, ist noch in ihrer Mitte…." vermutet. [img]http://www.fb18.de/gfx/22.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 03:32
MoKrates
Ey Zaphod! Pass auf! Offb 2,13!

MoKrates

Ansonsten hast Du natuerlich wieder Recht. Mr Google. Es ist Ezekiel 25,17. "The path of the righteous…"

you Vogon!

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 08:25
Zaphod
Ey Zaphod! Pass auf! Offb 2,13!
Den hast du von mir [img]http://www.fb18.de/gfx/25.gif[/img]

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 21:03
Anonymer User
Hi ihr alle,

noch mal zurück zur Aufgabe…

3.2 (i)

soll man aus dem Beispiel erkennen, dass die lexikographische Ordnung umgekehrt ist? (3,4)<(2,5) weil 3<2 ???

das macht für mich keinen Sinn

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 21:12
UncleOwen
Das sollst Du auch nicht aus dem Beispiel erkennen, sondern aus der Definition [img]http://www.fb18.de/gfx/28.gif[/img]

x=(3,4), also x_1=3, x_2=4
y=(2,5), also y_1=2, y_2=5

jetzt schreibst Du Dir a_1^3a_2^4 und a_1^2a_2^5 auf und vergleichst die beiden mit lg-lex.

<edit>Wort vergessen…</edit>

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 21:36
Anonymer User
Dadurch wird das für mich immer noch nicht klar. Das würde ja bedeuten, dass

a_1^3 a_2^4 <lg-lex a_1^2 a_2^5

sein muss, weil das Beispiel das so angibt.
Aus der Definition lese ich das nicht. Für mich ist immer noch a_1^3 <lg-lex a_1^2


Re: F2 blatt 3, aufgabe 3.2 2003-04-27 21:38
Anonymer User
Sorry, berichtige mich

a_1^2 <lg-lex a_1^3 natürlich

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 21:56
UncleOwen
Dadurch wird das für mich immer noch nicht klar. Das würde ja bedeuten, dass

a_1^3 a_2^4 <lg-lex a_1^2 a_2^5

sein muss, weil das Beispiel das so angibt.

Ist es doch auch (es geht um das runde <lg-lex, s. Def. 2.55)

Aus der Definition lese ich das nicht. Für mich ist immer noch a_1^2 <lg-lex a_1^3

Stimmt ebenfalls, ist aber für diese Aufgabe irrelevant.

Nochmal zum besseren Verständnis: sei a_1 = a, a_2 = b, mit a < b. Auf unser Beispiel angewendet, müssen wir jetzt aaabbbb mit aabbbbb vergleichen. Und da gilt ja aaabbbb <rundeslg-lex aabbbbb (wegen dem b an der 3. stelle)

Re: F2 blatt 3, aufgabe 3.2 2003-04-27 22:03
Anonymer User
oh, jetzt ist alles klarm danke!

es muss einem doch gesagt werden, wie das "hoch" interpretiert werden soll, da hätt ich aber auch selbst drauf kommen müssen.

a^3 soll sein aaa…

wie dumm von mir