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.
Aber hallo
hoi
also ich fand die diesmal um einiges schwerer als das letzte mal…
wobei ich diesmal etwas besseres gefühl hab (wenn so benotet wird wie das letzte mal…) naja diesmal im TI III teil gepunktet… dafür weniger in I und II…
wie wars bei euch??
Kann mich an die letzte net erinnern. Aber wenn die hier schwerer war, dann muss ich ja ein ganzes Stück besser vorbereitet gewesen sein… Naja, könnt langen…
Ja der IIIer Teil war sehr fair … IIer naja wenn man die Automaten hat passts … ich fand den Ier übel … diese Klammern :wand: … aber es müsste langen … wenn ich mich nicht zu oft verrechnet hab
Scheiß semi thue!
Ich fand die Klausur … ok … werde wohl keine gute Note bekommen, aber das Gefühl sagt mir, dass es langen sollte
Das dachte ich bei der letzten BWL Scheinklausur auch… :#:
Sagen wir mal so … es kommt auf die Fairness des Korrigierenden an … wenn das genauso ist wie letztes mal in ThI 1 wo wegen einem kleinen Fehler fast alles durchgestichen wurde … dann wirds kritisch :-/
Wie wärs denn an dieser Stelle mit einer Umfrage?
Hat jemand außerdem noch die Punktvereilung im Kopf?
Punkteverteilung war:
Teil 1:
4 Semi Thue
5 Eigenschaften Relation
5 Algebren
6 Logik
5 Markov?
5 ?
Teil 2:
8 Grammatik / Automaten
8 ?
8 ?
6 ?
Teil 3:
10 Landau?
6 ?
8 opt. bin. Code
6 Ringel Ringel Reihe
Rekursion war irgendwo noch. Dann das Verschlüsselzeug.
@Semi Thue: ja, scheiß Klammern … verwirrt total. Im Nachhinein ist’s fast klar. Markov bah … war wohl nix bei mir 
@Lehrstuhl: wie wäre es beim nächsten Mal mitgebrachte Unterlagen zu erlauben und dafür 50% statt ein Drittel der Punkte zu verlangen? Ich bin sooo schlecht im auswendig lernen und sich daran auch noch erinnern können …
Die Punkte hab’ ich aufgeschrieben:
I-1 :4 Semi-Thue
I-2 :5
I-3 :5
I-4 :6
I-5 :5 Markov
I-6 :5 war hier Beweisbarkeit von Ausdrücken?
II-1:8 genau
II-2:8
II-3:8
II-4:hab ich übersehen…(die Punkte) primitive Rekursion?
III-1:10 (3,3,4) Landau (Binär-Wörter und Divide-and-Conquer-Rekursion)
III-2:6 (3,2,1) hier dacht ich die Code-Geschichten
III-3:8 (2,3,3) Ich denk hier war die Rekursion
III-4:6 (2,2,2) Modulare Arithmetik
sprich: Ack…
Die Aufgabe I-1 hab ich den ersten Teil abgeskribbelt, hier die volle Verwirrungsdröhnung:
I-1 (4 Punkte) Semi-Thue-Systeme
Gegeben seien Zeichenketten der Form ((x((xx,)(x, usw. über de, Alphabet {(,),x}.
Definieren sie ein Semi-Thue-System, das diese Zeichenketten auf Ketten von öffnenden, schließenden oder einer Folge von (zuerst nur) schließenden und (dann nur) öffnenden Klammern (aber kein Durcheinander) reduziert, wenn das Klammergleichgewicht nicht erfüllt ist.
I-6 war glaube ich die Induktion der Kanten bei Graphen.
Teil 3: Zuerst war glaube ich die Rekursion und dann die Code-Geschichten
Ich glaube mich zu erinnern, dass Primitive Rekursion 5 Pkte. wert war, da jedoch die anderen 8*3=24 waren befürchte ich, dass es doch 6 Pkte waren.
Solange alles noch frisch ist: Seid so lieb und versucht euch an einem braindump fuer die fsi. Bittebitte 
(Wortlaut der Aufgaben war natürlich anders)
I-1
siehe Beitrag Claudius (Semi-Thue)
II-1
a) deterministischer, vollständiger Automat für ΣabΣbaΣ* mit Σ*=a,b
b) h(a)=ab h(b)=ba Monoidmorphismus
c) L=ΣabΣ geben Sie einen regulären Ausdruck für L nicht an.
II-2
Grammatik
S-> ab|SaSb|ε
a) Zeigen Sie, dass a^nb^n für alle n ∈L(G) ist
b) Zeigen Sie, dass für m≠n a^mb^n nicht ∈ L(G) ist
c) Zeigen Sie, dass aba^n und aba^m verschiedene Nerode Äquivalenzklassen haben.
d) Zeigen Sie mit Pumping-Lemma, dass die Sprache nicht regulär ist
(kann sein, dass noch was fehlt)
II-3
Was hat es sich mit dem speziellen Halteproblem auf sich?
II-4
genau die gleiche Aufgabe über primitive Rekursion wie in der Klausur zuvor
I-letzte
Stellen Sie eine Annahme auf wie die Kantenanzahl von der Anzahl der Ecken in einem volständigen Graphen abhängt.
Beweisen Sie dies durch Induktion.
III-1
Kästchenaufgaben
glaube
-(k aus n) Wachstum bei festem k und n->∞
-speziell für (2n n)
dann Divide & Conquer
- t(2n) = 2t(n) + an
- t(2n) = 3t(n) + an
- t(2n) = ?? t(n) + a*n²
RSA
genauso bloß das Ergebnis war gesucht
Nachrichten, die mittels Zahlen m N2003 numerisch kodiert wurden, können mittels x → x17 mod 2003 verschlüsselt werden. (NB: 2003 ist Primzahl)
Welches ist der Exponent d für die zugehörige Entschlüsselungsabbildung x → xd mod 2003 ?
- Wieviele Multiplikationen und Quadrierungen benötigt man für die Entschlüsselung mit diesem d?
III-2
Aufgabe über lexicografische Ordnung … Rekursionsgleichung und … n->∞
III-3
Wahrscheinlichkeiten (pa,pb,pc,pd,pe) … optimale Codierung Längen (la,lb,lc,ld,le)
Stellen Sie die verschiedenen Längenvektoren auf (Begründung!)
III-letzte
a)
Chinesischer Restesatz: X²=±1 221=13*17
1 und -1 sind triviale Lösungen … berechne die anderen beiden nichttrivialen Lösungen. (Wortlaut der Aufgabe war natürlich anders)
b)
Wie kann man mit Kenntnis der beiden nichttrivialen Lösungen die Prinfaktorzerlegung von 221 berechnen, wenn man das vorher nicht gewusst hat.
c)
Wie kann man die Zerlegung Mithilfe der Kenntnis von φ(n) bekommen.
Ist alles schwammig … bitte nun konkreter auf Aufgaben eingehen … bzw. Falsches verbessern
in der d) sollte man ausdrücklich ohne das Pumping Lemma zeigen, dass die Sprache nicht regulär ist.
Hi,
Es wäre cool, wenn ihr eure Niederschrift im FSI-Wiki fortführen könntet. Ich hab da mal eine entspr. Seite angelegt mit dem bisher hier geschriebenen.
Einerseits wird’s da leichter gefunden als hier im Forum, andererseits können alle gemeinschaftlich am gleichen Text herumhantieren
http://fsi.informatik.uni-erlangen.de/cgi-bin/moin.cgi/EinführungInDieTheoretischeInformatik
Dort kann jeder ohne Login editieren (man kann sich natürlich auch einen Login holen, siehe oben rechts).
Falls jemand Mist baut oder die Leute sich verschieden erinnern ;), sind die Veränderungen leicht nachvollziehbar und rückgängig zu machen.
cu
Ford Prefect
Ich will eure Bemühungen ja nicht irgendwie schlecht machen, aber wieso nehmt ihr nicht einfach das Original
http://www8.informatik.uni-erlangen.de/IMMD8/Lectures/THINF3/Klausuren/F05Klausur.pdf
loooool na gut
Ui, sogar schon incl der wichtigen beiden Schreibfehler… die anderen 3 oder 4 waren ja nicht weiter tragisch… 
also ich wär da kanllhart durchgefallen. viel glück euch…
:vogel: