Info08.de - Forum des Erstsemester Jahrgangs 2008

Bin ich zu blöd, oder wo genau melde ich mich an und finde die Übungsblätter? Irgendwie seh ich da nichts dergleichen?

Sagtmal, macht hier jemand Mathe als Nebenfach (Zahlentheorie und Algebra, evt. werdende Kryptographen?) und weiß was genau wie wann verlangt ist, ich steig nicht wirklich durch was ich jetzt dafür hören sollte und wie das mit dem verlangten (Pro?)Seminar läuft!

Super, danke!

Ich würd gern für das Blatt Werte vergleichen, ich bin mir nicht sicher, ob ich was richtig habe: Zur 1: H(X) = 2? Zur 3 (Bonusaufgabe, ich brauch die Punkte glaub ich ;)): H(X) = 2.013 und mittlere Codewortlänge = 2.02? Zudem hab ich bei der 1 nur die zweite Gleichung für geometrische Reihen benutz...

Nein, noch nicht, aber ich möchte hier meinen Ansatz für die erste Aufgabe einfach mal bereitstellen ;) Das EC-Problem nennt sich Eulerkreisproblem. Um zu zeigen, dass EC in P ist, genügt es einen Algorithmus zu finden und diesen zu analysieren. Ein Eulerkreis hat dabei zwei Eigenschaften: Der Graph...

Ich find da auch nichts. Ich suche schon die ganze Zeit irgendwie ein tolle Kodierung, deren worst case besser als |w| ist. Ich hab da jetzt dann an Huffman oder so gedacht, aber das ist bei worst case schlechter, also lässt sich gar nicht als Schranke heranziehen. Die Tatsache, dass die 1 nur k mal...

Das ist die Turingmaschine, die das Wort <M2> ausgibt (das <M2> sollte im Index stehen, ich habs ausdrückt als sei es eine Funktion, nicht ganz richtig). Im Sipser war das mit der Funktion q(), also q(<M1>) = <P(<M1>)> = Code einer TM, die <M1> in einer Tabelle hartkodiert enthält und ausgibt. Danke...

Eine 2. Möglichkeit sehe ich in der 2. Version des Rekursionstheorems der VL: Man definiert sich eine Funktion t mit t(<M1>) = <M2> und t(<M2>) = <M1> Dann holt sich M1 seine eigene Gödelnummer, was ja möglich ist, berechnet t und gibt das Ergebnis aus. M2 verfährt dann genau so. Hab aber keine Ahn...

Ich glaube die 2a) lässt sich durch Reduktion auf das Halteproblem lösen. Es ist nicht entscheidbar ob eine gegebene Turingmaschine ein gegebenes Wort akzeptiert (wohl aber semi-entscheidbar). Nehmen wir an, das ginge, dann würden wir eine Turingmachine bauen, die einfach das Wort durch M jagt, umdr...

Ah perfekt, dann bin ich ja bestens ausgestattet, danke!