You are not logged in.

Wanja

Junior Schreiberling

  • "Wanja" started this thread

Posts: 150

Date of registration: Feb 4th 2003

1

Tuesday, September 5th 2006, 3:18pm

KvA Übungen?

Ich wollte mal anfragen, ob zufällig wer Lösungen zu den Übungsaufgaben hat, von denen man ausgehen kann das sie richtig sind. Unser Übungsleiter hat leider immer nur so 2 Aufgaben mit uns besprechen können und Musterlösungen gibts ja keine...

mfG Wanja

This post has been edited 2 times, last edit by "Wanja" (Sep 5th 2006, 3:18pm)


iriania

Junior Schreiberling

  • "iriania" is female

Posts: 222

Date of registration: Nov 24th 2003

Location: Waqwaq

Occupation: Wie? Ich studiere? seit wann denn?

2

Thursday, September 7th 2006, 2:40pm

Hätte ich auch gerne, falls jemand das hat
...und sie dreht sich doch!

Justus

Junior Schreiberling

  • "Justus" is male

Posts: 152

Date of registration: Oct 16th 2004

Occupation: ich will auch mal Käptain sein!

3

Monday, September 18th 2006, 2:10pm

ich auch, bitte

asbas

Trainee

Posts: 32

Date of registration: Jul 6th 2006

4

Monday, September 18th 2006, 2:29pm

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.

This post has been edited 1 times, last edit by "asbas" (Sep 18th 2006, 2:31pm)


Panschk[FP]

Junior Schreiberling

  • "Panschk[FP]" is male

Posts: 148

Date of registration: Oct 21st 2005

Location: H-town

Occupation: Informatik Master

5

Wednesday, September 20th 2006, 8:15pm

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 :)

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

6

Thursday, September 21st 2006, 10:44am

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 :D ;)

This post has been edited 2 times, last edit by "DrChaotica" (Sep 21st 2006, 10:48am)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

7

Thursday, September 21st 2006, 11:25am

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Panschk[FP]

Junior Schreiberling

  • "Panschk[FP]" is male

Posts: 148

Date of registration: Oct 21st 2005

Location: H-town

Occupation: Informatik Master

8

Friday, September 22nd 2006, 11:44pm

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. :D
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?

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

9

Saturday, September 23rd 2006, 10:11am

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. :D
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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Sep 23rd 2006, 10:12am)


oixio

Senior Schreiberling

  • "oixio" is male

Posts: 517

Date of registration: Oct 3rd 2004

10

Saturday, September 23rd 2006, 1:03pm

Bei der Kombiklausur nur 1 Blatt - oder je ein Blatt für jeden Teil?
Dieser Post wurde aus 100 % chlorfrei gebleichten, handelsüblichen, freilaufenden, glücklichen Elektronen erzeugt!

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

11

Saturday, September 23rd 2006, 3:12pm

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/.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

12

Sunday, September 24th 2006, 1:24pm

Frage zu TM

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

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

13

Sunday, September 24th 2006, 1:43pm

RE: Frage zu TM

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 :)

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

14

Sunday, September 24th 2006, 6:42pm

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?

SUPERDIM

Junior Schreiberling

  • "SUPERDIM" is male

Posts: 171

Date of registration: Oct 7th 2004

Location: Hannover

Occupation: 1. Semester M.Sc. Informatik

15

Sunday, September 24th 2006, 8:09pm

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

asbas

Trainee

Posts: 32

Date of registration: Jul 6th 2006

16

Sunday, September 24th 2006, 10:31pm

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

This post has been edited 1 times, last edit by "asbas" (Sep 25th 2006, 1:52am)


Teklan

Erfahrener Schreiberling

Posts: 267

Date of registration: Nov 13th 2004

Location: Hannover

17

Monday, September 25th 2006, 12:54am

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.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

18

Monday, September 25th 2006, 8:24am

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

19

Monday, September 25th 2006, 8:25am

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

hyperion

Erfahrener Schreiberling

  • "hyperion" is male

Posts: 422

Date of registration: Oct 8th 2004

20

Monday, September 25th 2006, 6:55pm

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?
"Der Klügere gibt nach! Eine traurige Wahrheit, sie begründet die Weltherrschaft der Dummheit." --Marie von Ebner-Eschenbach