Fachrat Informatik - Forum

Hätte ich auch gerne, falls jemand das hat

ich auch, bitte

habt ihr was bekommen?
ich werde morgen nach Hannover fahren und mir einen Haufen lösungen kopieren. Wer sie sich auch kopieren möchte, kann mich bis Mittwoch noch in der Uni erreichen.

Wanja und ich haben zum Glück Kopien der Mitschriften von den Übungen bekommen, das hilft schon. Ein größerer Vorrat an Lösungen würde natürlich auch nicht schaden, aber da gibt es wohl nicht viel

Mh...also ich denke, zuviele davon schaden dann aber auch wieder, weil es doch am meisten bringt, wenn man selbst auf die Lösungsidee gekommen ist.
An einer Aufgabe zu üben, die man schon einmal gelöst gesehen oder von der man die Lösung gehört hat, ist imho sinnlos da die Idee unterbewusst schon da ist, man wird sich später immer daran erinnern. Das spezielle Problem kennt man dann womöglich, aber transferieren fällt bestimmt viel schwerer...und dann übt man bloss nur noch Beweistechniken, die so in der Klausur aber wenig nützen, wenn einem nichts einfällt worauf man sie anwenden kann.
Lieber selber viele Probleme kennenlernen, und verstehen was diese überhaupt aussagen wollen...wenn man einmal dahinter gekommen ist, wird alles gleich viel einfacher. Selbst wenn man dann die Klausuraufgaben vielleicht nicht komplett bearbeiten kann, hat man doch sicher genug eigene Ideen für gute Ansätze und ist in der Lage zumindest zu nennen, worauf man reduzieren könnte und wie man an die Lösung herangegangen wäre... das zusammen mit sicherem Beherrschen der Grundaufgaben, von denen sowieso jedesmal einige drankommen werden (ihr wisst ja, welche) sollte zumindest zum Bestehen reichen.

Oder ich bilde mir das alles nur ein, und das Problem LöseKVA liegt gar nicht in TIME(90min), schließlich hat ja bisher noch niemand die Kombi THI/KVA bestanden

Quoted

Original von DrChaotica
Mh...also ich denke, zuviele davon schaden dann aber auch wieder, weil es doch am meisten bringt, wenn man selbst auf die Lösungsidee gekommen ist.
An einer Aufgabe zu üben, die man schon einmal gelöst gesehen oder von der man die Lösung gehört hat, ist imho sinnlos da die Idee unterbewusst schon da ist, man wird sich später immer daran erinnern. Das spezielle Problem kennt man dann womöglich, aber transferieren fällt bestimmt viel schwerer...und dann übt man bloss nur noch Beweistechniken, die so in der Klausur aber wenig nützen, wenn einem nichts einfällt worauf man sie anwenden kann.

Exakt das ist auch der Grund, warum es in diesem Semester sehr viele Übungsaufgaben gab, aber nur einige wenige in den Übungen besprochen wurden. Ein wichtiges Lernziel dieser Lehrveranstaltung ist eben das "Selberdenken" und insbesondere die Entwicklung eines Gefühls dafür, was ein Problem "schwer" oder "einfach" macht. Und das lernt man nun einmal nicht durch das Reproduzieren der Gedanken anderer. Die schlechteste Lernstrategie ist daher sicherlich das Ausweniglernen.

Quoted

Selbst wenn man dann die Klausuraufgaben vielleicht nicht komplett bearbeiten kann, hat man doch sicher genug eigene Ideen für gute Ansätze und ist in der Lage zumindest zu nennen, worauf man reduzieren könnte und wie man an die Lösung herangegangen wäre...

Vollkommen richtig. Es ist überhaupt kein Problem, bei der einen oder anderen Aufgabe mal nicht die richtige oder keine Idee zu haben. Das gibt dann zwar nicht die volle Punktzahl, aber viele Punkte lassen sich in einem solchen Fall dadurch holen, daß man beschreibt, wo hier das Problem liegt, was man versucht hat und warum dies nicht funktioniert hat.

Zu den Hilfsmitteln: Ein DIN A4-Blatt ist ja erlaubt. Muss dieses handschriftlich verfasst sein und darf man beide Seiten beschreiben?

Ich habe heute versucht, die WS05/06 Klausur zu lösen, da ein Großteil der Aufgaben schon in den Übungen dran war, war es gar nicht so schlimm Allerdings konnte ich mit Aufgabe 4, wo es um den Platzbedarf einer regulären Sprache geht, nicht viel anfangen. Theoretische Informatik war im 1. Semester, ich bin jetzt im 6.
Ich nehme an, es wäre sinnvoll, sich mit den Definitionen der verschiedenen Sprachklassen wieder vertraut zu machen, die grundsätzliche Funktionsweise einer Turing Maschine weiß ich glücklicherweise noch...

Aufgabe 3 gab 3 TM an, die verschiedene Laufzeitverhalten (O(n²), O(2^n), O(n+5)) haben. Gefragt war, ob man bei einer Eingabe der Länge 12 sagen könnte, welche Maschine die wenigsten Rechenschritte braucht.
Ich würde jetzt sagen, dass die O-Notation ja nur die Entwicklung der Laufzeit abhängig von der Eingabelänge aufzeigt, konkrete Vergleiche scheitern daran, dass man nicht weiß, wie viele Rechenschritte die Maschine für ein bestimmtes n genau braucht. So könnte es sein, dass der 3. Algorithmus einen deutlich größeren konstanten Faktor hat und die anderen erst bei Eingabelänge >13 "überholt".
Ist das so richtig?

Quoted

Original von Panschk[FP]
Zu den Hilfsmitteln: Ein DIN A4-Blatt ist ja erlaubt. Muss dieses handschriftlich verfasst sein und darf man beide Seiten beschreiben?

Du darfst das Blatt mit beliebigem Inhalt beschreiben oder bedrucken (und zwar beidseitig, denn sonst hätten wir "Seite" statt "Blatt" geschrieben ).

Quoted

Ich habe heute versucht, die WS05/06 Klausur zu lösen, da ein Großteil der Aufgaben schon in den Übungen dran war, war es gar nicht so schlimm Allerdings konnte ich mit Aufgabe 4, wo es um den Platzbedarf einer regulären Sprache geht, nicht viel anfangen. Theoretische Informatik war im 1. Semester, ich bin jetzt im 6.
Ich nehme an, es wäre sinnvoll, sich mit den Definitionen der verschiedenen Sprachklassen wieder vertraut zu machen, die grundsätzliche Funktionsweise einer Turing Maschine weiß ich glücklicherweise noch...

Die Lehrveranstaltung "Grundlagen der Theoretischen Informatik" wird in "Komplexität von Algorithmen" inhaltlich vorausgesetzt. Du solltest dich also dem entsprechend gut auskennen.

Quoted

Aufgabe 3 gab 3 TM an, die verschiedene Laufzeitverhalten (O(n²), O(2^n), O(n+5)) haben. Gefragt war, ob man bei einer Eingabe der Länge 12 sagen könnte, welche Maschine die wenigsten Rechenschritte braucht.
Ich würde jetzt sagen, dass die O-Notation ja nur die Entwicklung der Laufzeit abhängig von der Eingabelänge aufzeigt, konkrete Vergleiche scheitern daran, dass man nicht weiß, wie viele Rechenschritte die Maschine für ein bestimmtes n genau braucht. So könnte es sein, dass der 3. Algorithmus einen deutlich größeren konstanten Faktor hat und die anderen erst bei Eingabelänge >13 "überholt".
Ist das so richtig?

Genau so ist es. Die Aufgabe soll zeigen, daß Laufzeitangaben in O-Notation zwar ein gutes Hilfsmittel sind, wenn die zu erwartenden Eingabelängen "groß" sind, für eine konkrete (und meist eher "kleine") Eingabelänge kann jedoch auch ein Trivialalgorithmus schneller sein als ein ausgeklügeltes Verfahren.

Bei der Kombiklausur nur 1 Blatt - oder je ein Blatt für jeden Teil?

Quoted

Original von oixio
Bei der Kombiklausur nur 1 Blatt - oder je ein Blatt für jeden Teil?

Ein Blatt. Siehe http://www.thi.uni-hannover.de/lehre/ss06/klausuren/.

Wir haben in der Uebung folgende Aufgabe geloest, aber jetzt kann ich nicht die Logik verstehen. Die Aufgabestellung lautet:

Man soll eine 2-bandige TM konstruieren, dei die folgende Sprache entscheidet
L:{ww/ w aus {a,b}^* }
Die Loesung:
z0 aooo()->z1 aaRR
z0 b()->z1 bbRR
z0 ()()->z1 ()()LL
z1 aa->z2 aaNL
z1 ab->z2 abNL
z1 ba->z2 baNL
z1 bb->z2 bbNL
z2 aa->z1 aaLL
z2 ab->z1 abLL
z2 ba->z1 baLL
z2 bb->z1 bbLL
z2 a()->zp a()RR
z2 b()->zp a()RR
zp aa->zp aaRR
zp bb->zp aaRR
zp ()a->ze ()aNN
zp ()b->ze ()bNN

was mir nicht klar ist, warum man nach z0, nach dem ersten Lesen vom 1. Band in z1 ein zweites Symbol auf 2. Band erwartet
() steht fuer das leere Smbol
Wenn jemand Idee hat, wuerde ich dankbar
Gruesse

Quoted

Original von Jojo
was mir nicht klar ist, warum man nach z0, nach dem ersten Lesen vom 1. Band in z1 ein zweites Symbol auf 2. Band erwartet

Diese TM geht einfach so wie sie da steht nicht richtig mit der Eingabe um...schreib lieber schnell einen neuen Algorithmus. Das bringt mehr, als lange über diesen Fehler nachzudenken

Danke fuer den Hinweis aber fuer dieses Problem finde ich keine Loesung und dachte mir dass die Loesung von dem Betreuer mir helfen wird. Hast du irgendwelche Vorschlaege?

Tip: Schreib die Eingabewortlänge geteilt durch 2 aufs zweite Band.

die lösung ist vielleicht falsch übernommen worden.
nichtdeterministisch funktioniert sie so:
lesen bis das 2. wort anfängt. dieses auf das 2. band schreiben.
z0 a() -> z0 aa RR
z0 b() -> z0 bb RR
hier erkennt die maschine das 2. wort und geht auf dem 2. band wieder zum anfang.
z0 a() -> z1 a() NL
z0 b() -> z1 b() NL
z1 xy -> z1xy NL x=y=(a|b)
z1 x() -> z2 x() NR
jetzt das 2. w, mit dem auf das 2. band geschriebenem 1.w vergleichen
z2 aa -> z2 aa RR
z2 bb -> z2 bb RR
z2 ()() -> Z3 NN
Z3 akzeptierender Zustand.

Alle nicht definierten Übergänge führen in eine endlosschleife
(ich erinnere mich daran, das unser Übungsbetreuer meinte, das wir diesen Satz erwähnen sollten)
gruß,
baass

Bezüglich der KLausur:

Werden die Punkte zu den jeweiligen Aufgaben angegeben?
Falls nicht, dann würde ich gerne den Grund erfahren, denn beeinträchtigen würde eine Angabe der Punkt sicherlich keine Partei.

Quoted

Original von Teklan
Werden die Punkte zu den jeweiligen Aufgaben angegeben?
Falls nicht, dann würde ich gerne den Grund erfahren, denn beeinträchtigen würde eine Angabe der Punkt sicherlich keine Partei.

Wie ich hier im Forum bereits mehrfach erwähnte, wird die kommende Klausur so ähnlich aussehen (abgesehen von den Aufgaben) wie die aus dem vergangenen Semester. Schau' Dir doch diese am besten mal an.

Quoted

Original von asbas
Alle nicht definierten Übergänge führen in eine endlosschleife
(ich erinnere mich daran, das unser Übungsbetreuer meinte, das wir diesen Satz erwähnen sollten)

Ja, das ist wichtig. Denn sonst wäre die Maschine unvollständig definiert.

Hallo,

ich würde mich freuen, wenn mir jemand bei Aufgabe 7 aus der Klausur vom Wintersemester 05/06 auf die Sprünge helfen könnte.

Wie kann ich beweisen, dass CFL in NSPACE(n) liegt? Ich würde sagen, dass Gramatiken endlich sind und diese dann gödelisiert werden können und max. n Platz brauchen.

Von NSPACE würde ich über TIME auf SPACE gehen.

Wäre diese Vorgehensweise so richtig?