Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
C-Rek. Transfermatrix
Wie kommt man denn auf die Transfermatrix der MIU-Aufgabe?
Der kleinere Automat hat doch 32 Zustände, wie bekommt man daraus eine 33 Matrix (siehe Lösung MIU Aufgabe, S. 3)?
von Zustand z0 habe ich eine Möglichkeit im z0 zu bleiben
von z0 habe ich eine Möglichkeit in den z1 zu kommen
von z0 habe ich 0 Möglichkeiten in den z2 zu kommen
Dadurch ergibt sich die erste Zeile der Matrix: 1 1 0
bei Zeile 2 teste ich, wo ich von z1 aus mit wievielen Symbolen komme…
Anfangswerte der C-Rekursion
Ach ja, stimmt, danke.
Noch eine Frage: Woher kenne ich denn μ0 bis μ3 (die Anfangswerte)?
bei dem char. polynom kommt ja λ³ - 3λ² + 3λ - 2 raus.
Man nehme die Potenz der char. Fkt als Index für die Rekursion:
μn-3 - 3μn-2 + 3μn-1 - 2μn = 0
bisschen hübscher hingeschrieben:
μn-3 = 3μn-2 - 3μn-1 + 2μn
Die Anfangswerte ergeben sich aus dem Automaten. Wörter der Länge 0 gibt es nicht in der Sprache also μ0 = 0. Wörter mit Länge 1 gibts auch nicht also μ1 = 0. Wörter der Länge 2 gibt es 1 Stück ( “MI” ) μ2 = 1. Wörter der Länge 3 gibt es 3 Stück (MUI, MIU, MII) μ3 = 3. Die anderen Wörter bekommt man über die Rekursionsformel.
Achso, danke.
Aber da gibt es noch ein Problem: ich habe keine Ahnung, wie die Partialbruchzerlegung vorsich geht. Habe alle Folien vom WS 2004/2005 heruntergeladen, die auf Prof. Strehl’s homepage mit ‘NEU’ gekennzeichnet waren. Aber in asymp4.pdf (C-Rekursion) wird die Partialbruchzerlegung einfach durchgeführt, aber nirgends erklärt. Oder habe ich etwas übersehen? Muss ich noch mehr pdf’s herunterladen?
Such mal lieber im Mathe Script oder im Bronstein. Die Rechnung ist aber nicht wirklich trivial und ich wage mal zu bezweifeln, dass die Partialbruchzerlegung drankommen wird. Aber so erzeugende Funktion herleiten wäre schon eher was.
Ok noch eine letzte Frage: wie sieht die modulare Darstellung des Bruches 2333/(91011) aus (Aufgabe 34-3)? Muss leider alles hier fragen weil die Übungsleiter antworten nicht auf meine mails 
also bei mir is es 35/3 aber egal
und es heißt 2333 / 900 bei mir
900 = 4 * 9 * 25
eggt berechnen von (255, 4) (100,9) (36, 25)
Diesmal interessiert aber nur das Inverse zu 255, 100 und 36.
- Schritt Ganzahligen Anteil bestimme:
2333 div 900 = 2 Rest 533
Die Lösung muss so aussehen: 2 + x/4 + y / 9 + z/ 25
x:
533 mod 4 = 1
ausgerechnetes Inverse (Bezout) von 255 ist 1
also 1 * 1 mod 4 = 1 = x
y:
533 mod 9 = 2
ausgerechnetes Inverse (Bezout) von 100 ist 1
1 * 2 mod 9 = 2 = y
z:
533 mod 25 = 8
ausgerechnetes Inverse (Bezout) von 36 ist -9
8 * (-9) mod 25 = -22 = 3
=> 2 + 1/4 + 2/9 + 3 / 25 = 2333 / 900
Bei mir ist es wirklich Aufgabe 34-5 und du hast Recht, ich habe 990 gelesen weil dafür die Primfaktorzerlegung schon drübersteht 
Aber 9*25 ist 225, nicht 255, oder ?!?
Danke!
Ich bin von dem Übungsaufgaben dieses WS ausgegangen, da wars halt die 35
Ja, hast recht, da hab ich mich vertippt - dafür aber sehr konsequent. Es muss überall 225 heißen. Der Bezout passt aber, ich habs nur falsch abgetippt.
Häh, ich habe auch WS 2004/2005, auf dem Blatt steht ‚12. Januar 2005‘, und es ist aufgabe 34-3! :-p
Scheint eine neuere Version zu sein, als ich habe. Wahrscheinlich kommt in der Klausur die Aufgabe dran, die jetzt bei mir fehlt
Dann fehlt dir also die Aufgabe, wo man die Entropie, der durch die erzeugende Funktion gegebenen Sprache mittels schneller Fouriertransformation ausrechnet? :*)
OH MEIN GOTT! FOURIER!!!
WARUM???
SEHR witzig!
Fast wäre ich drauf reingefallen! Aber in meinen Blättern gibt es zwei mal die Aufgabe 32, DA liegt der Fehler!!! 
Inverses in Zn
Nur mal zur Sicherheit: das Inverse von a ist doch das s aus dem erweiterten Euklidischen Algorithmus (wenn a>b)?
Beispiel:
eggT(36,25) ergibt:
-936+1325=1
=> Inverse von 36 ist -9
eggT(225,4) ergibt:
1225-564=1
=> Inverse von 225 ist 1
Stimmt doch, oder?
korrekt!
Das Inverse bestimmt man auch bei den Verschlüsselungsaufgaben nach dem selben Prinzip. Dort muss ja das Inverse des Verschlüsselungsexponenten bestimmt werden. Nur rechnet man dort im Ring Phi von dem Verschlüsselungsmodul. Also beim symetrischen Verschlüsseln ist ja phi(primzahl) = primzahl -1. Beim RSA ist phi(p*q) = phi(p) * phi(q) = (p-1) * (q-1).