Info08.de - Forum des Erstsemester Jahrgangs 2008

Bei der 12.1b) habe ich folgende Maschine (als Programmcode für http://ironphoenix.org/tril/tm/): Weil diese Simulation nur einen Haltezustand H kennt, habe ich die 3 verschiedenen Haltezustände durch die Ausgaben E (gleich), G (größer), L (kleiner) gekennzeichnet. 1,1,14,1,> 1,0,1,a,> 1,a,1,a,> 1,b...

Hi, ich habe folgende Turingmaschinen-Simulation im Netz gefunden: http://ironphoenix.org/tril/tm/ Der Programmcode für die Aufgabe 12.2 b) sieht so aus: 1,_,2,_,< 1,a,1,c,> 1,b,1,d,> 1,c,1,c,> 1,d,1,d,> 2,_,H,_ 2,a,2,a,< 2,b,2,b,< 2,c,3,a,> 2,d,4,b,> 3,_,2,a,< 3,a,3,a,> 3,b,3,b,> 3,c,3,c,> 3,d,3,d,...

Hi, mein Vorschlag wäre f(n)=\begin{cases}n! & \text{, gerade n}\\(n-1)! & \text{, ungerade n}\end{cases}\\g(n)=\begin{cases}(n-1)! & \text{, gerade n}\\n! & \text{, ungerade n}\end{cases} Die würden sowohl die Bedingungen erfüllen und den Hinweis auf dem Blatt benutzen. Außerdem ist...

Thomas hat geschrieben:die summer der natürlichen zahlen bis n ist doch n(n+1)/2 oda? also nicht, dass es groß was ändert.

Stimmt natürlich^^

MfG,
mfs.

Hi, mein Beweis sieht so aus: f\in O(n)\\\Leftrightarrow f(n)\leq c\cdot n\\\sum_{k=0}^nf(k)\leq \sum_{k=0}^n c\cdot k = c \sum_{k=0}^n k = c\frac{n(n+1)}{2}=\frac{c}{2}(n^2+n)\\\\\text{Es ist }n^2+n\in O(n^2) \text{ und damit auch }\frac{c}{2}(n^2+n)\in O(n^2)\\\text{Da}\\\sum_{k=0}^n f(k)\leq \fra...

Hi,

ich habe mal den Algorithmus aus Aufgabe 9.1 in ein kleines Programm umgesetzt. Wenn ihr keine Lust habt, den Algorithmus selbst durchzugehen, dann probiert ihn damit einfach aus.

MfG,
mfs.

salami hat geschrieben:Ich habe bei a vier Bäume gefunden und bei b drei. Hat das noch jemand?

Das hab ich auch

MfG,
mfs.

Lucky, damit bin ich nicht einverstanden: bei a: falsch wenn L:={a}*{b}* {ba} liegt in L dann hast die bedienung net ! hast auch L geschriben dann das leere wort (€ :lol: oder so) liget auch in L ? no ! mußt L+ schreiben. Meiner Meinung nach liegt ba nicht in L, wie Reini es definiert hat. Denn nach...

Zur 3.2 c) Ich hab das folgendermaßen gelöst: Zunächst beim Induktionsanfang i=0 => b^a = b^a Dann hab ich den Induktionsschluss folgendermaßen (hier ebenfalls mit i statt mit k, denke mal das geht auch): P_{i+1} \cdot Y_{i+1}^{X_{i+1}} = b^a soweit so gut. Dann kann man ja die Sachen aus der "...

Hi, ich habe die 3.2 bis jetzt folgendermaßen: a) P=b^a b) im k-ten Schleifendurchlauf gilt: P_k\cdot Y_k^{X_k}=b^a c) Induktionsanfang: k=0: P_0\cdot Y_0^{X_0}=1\cdot b^a=b^a Induktionsvoraussetzung: Sei k\in\mathbb{N}: P_k\cdot Y_k^{X_k}=b^a Induktionsschluss: zu zeigen: P_{k+1}\cdot Y_{k+1}^{X_{k...