Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Mindbender

Praktikant

  • "Mindbender" started this thread

Posts: 20

Date of registration: Oct 10th 2002

1

Tuesday, February 4th 2003, 7:32pm

Theoretische Informatik: Lösungen der Aufgaben

Hallo zusammen,
hat jemand von euch die Lösungen der Übungsaufgaben in elektronischer Form vorliegen?
Ich habe leider irgendwie einen Teil der Lösungen versiebt.

Danke!

Have fun,
Gerd
Unsere Familie war so arm, wir konnten uns nicht einmal eine Signatur leisten...
  • Send private message

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

2

Friday, February 7th 2003, 9:15am

Ich wollte diesem Beitrag nochma/auch etwas Betonung verabreichen. :)

Auch ich wäre sehr dankbar, wenn jemand die Lösungen der TheoInf-Aufgaben online stellen würde oder mailen könnte. Mir fehlen leider auch ein paar der Lösungen. Die TheoInf-Klausur rückt ja auch näher.

Die Musterlösungen bekommen wir ja leider wohl nicht :(
(dies war ein insgeheimer Aufruf an cbe usw)

edited: Wenn ihr mir die Lösungen mailt, die ihr habt, kann ich die auch sammeln und alle gemeinsam online stellen für alle, die sie haben wollen.
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

3

Saturday, February 8th 2003, 10:44pm

also, ich habe eine seite von der TU BS gefunden, die für das gleiche thema übungsblätter MIT lösungen im netz stehen hat.
die sollten zum lernen auf jeden fall hilfreich sein, denke ich.

http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/ATFS/

Cipher
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

4

Sunday, February 9th 2003, 12:08pm

Also auf meiner Seite sind die Lösungen der letzten 4 Übungsblätter online...
www.ukn-tot.de/4_uni und dann auf theo.inf
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

5

Sunday, February 9th 2003, 2:37pm

Lösung der Weihnachtsaufgabe (Übungsblatt 10)

Norbert
Gelb
Lakritz
Karl May
[Stern]

Uwe
Blau
Karamel
Skateboard
Eisblume

Ernst
Rot
Schoko
Eisenbahn
Engelchen

Stefan
Weiß
Gummibärchen
Bildatlas
Krippe

Jens
Grün
Zuckerstäbchen
[Feuerwehrauto]
Tannenbaum


Antwort: Norbert hat den Stern im Fenster und Jens bekommt das Feuerwehrauto.

Aber kann mir mal jemand sagen, wie man im Hinblick auf das Thema "Automatentheorie" an die Lösung gelangt? Ich habs jetzt rausgekriegt, indem ich einfach geguckt habe, was passt usw. Aber auf diesem Wege kann es auch jeder machen, der noch nie was von Automatentheorie gehört... Gibt es also noch andere Möglichkeiten auf diese Lösung zu kommen (und bitte auch nicht Brute Force vorschlagen ;) ).


Cipher
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

6

Sunday, February 9th 2003, 3:38pm

Noch eine Lösung zu einer Aufgabe:

2. Übungsblatt - Aufgabe 2 - 1. Teil

Geben Sie für die Sprache {w element {a,b}* | |w|a ist durch 2 teilber } eine Grammatik vom Typ 3 an.

Eine mögliche Lösung lautet:

G = {V,E,P,S}
V = {A,B,S}
E = {a,b}
P = { S -> aA
A -> aB
B -> bB
B -> aA
B -> b }


2. Teil

Geben Sie für die Sprache {w element {a,b,c}* | |w|a=|w|b=|w|c} eine Grammatik vom Typ 1 an.

Dazu habe ich einfach die Grammatik aus dem Buch "Theo. Inf. kurzgefasst" genommen und um S->[leeres Wort] erweitert, damit es nicht nur für n>=1 gilt.

Liege ich da richtig?
Ich denke mal, dass die dann zulässig wäre:

G = {V,E,P,S}
V = {A,B,C,S}
E = {[leeres Wort],a,b,c}
P = { S -> [leeres Wort],
S -> aSBC,
S -> aBC,
CB -> BC,
aB -> ab,
bB -> bb,
bC -> bc,
cC -> cc }


Cipher
  • Send private message

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

7

Sunday, February 9th 2003, 4:01pm

meine lösung für 3. übungsblatt 1)

venturemedia.de - you don't need eyes to see, you need a vision
  • Send private message

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

8

Sunday, February 9th 2003, 4:17pm

Hm, mit Hingucken würde ich bei dem 4.Übungsblatt das hier als Lösung für 1 und 2 denken, oder ? ist es wirklich so einfach ?

venturemedia.de - you don't need eyes to see, you need a vision
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

9

Sunday, February 9th 2003, 4:26pm

Quoted

Original von Cipher
Geben Sie für die Sprache {w element {a,b}* | |w|a ist durch 2 teilber } eine Grammatik vom Typ 3 an.

Eine mögliche Lösung lautet:

G = {V,E,P,S}
V = {A,B,S}
E = {a,b}
P = { S -> aA
A -> aB
B -> bB
B -> aA
B -> b }
Stimmt leider nicht. Gesucht sind ja alle Wörter, die eine gerade Anzahl von "a"s enthalten. In Deiner Lösung werden aber nur Wörter erfaßt, die mit "a" beginnen und in denen die "a"s nur paarweise auftreten.


Korrekt wäre z. B. diese Lösung (hoffe ich zumindest):

G = ({a, b}, {S, A}, P, S) mit

P = {
S -> aA,
S -> bS,
S -> epsilon,
A -> bA,
A -> aS
}

(Ich gehe davon aus, daß das Startsymbol auf der rechten Seite einer Produktion zulässig ist. Kann sein, daß Herr Vollmer das anders definiert hat -- dann müßte man ein paar kleinere Anpassungen vornehmen.)
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

10

Sunday, February 9th 2003, 4:31pm

ach so ist das gemeint...
hmm. dann muss der 2. teil von mir auch anders aussehen.
(wär ja auch zuu einfach) :)

Cipher
  • Send private message

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

11

Sunday, February 9th 2003, 4:54pm

6.Übungsblatt 1. Aufgabe

Geben Sie einen Kellerautomaten an, der die Sprache {a^i b^i | i>=1 } akzeptiert

† soll das Kellersymbol sein, § = sigma, e=epsilon

K := ({a,b},{s0,s1,sf},{a,†}, §1, s0,†, {sf})^
mit §1 := {
(s0,e,†,sf,e),
(s0,a,†,s0,a†),
(s0,a,a,s0,aa),
(s0,b,a,s1,e),
(s1,b,a,s1,e),
(s1,e,†,sf,e) }
venturemedia.de - you don't need eyes to see, you need a vision
  • Send private message

Pak

Zuhörer

  • "Pak" is male

Posts: 2

Date of registration: Oct 21st 2002

Location: H.

12

Sunday, February 9th 2003, 5:14pm

Quoted

Original von sebi
meine lösung für 3. übungsblatt 1)




Dein Automat ist nicht ganz vollständig, weil hier ein Deterministischer Automat gesucht ist, fehlen Übergänge und ein Zustand.

  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

13

Sunday, February 9th 2003, 6:45pm

und hier die hoffentlich richtige Aufgabe 2 vom Übungsblatt 3 :



Cipher
  • Send private message

doofi

Praktikant

Posts: 18

Date of registration: Aug 9th 2002

14

Sunday, February 9th 2003, 7:25pm

kann mir mal jemand mit übungszettel 1 und 4 weiterhelfen ? danke :)
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

15

Sunday, February 9th 2003, 8:44pm

@sebi: deine lösung von übungszettel 4 aufgabe 1 ist ganz ok, außer dass da mehr 0,1 zwischendurch stehen sollten (am anfang und am ende zum beispiel). aber das ist dann nur die lösung für aufgabe 1 nicht für 2.

Cipher
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

16

Sunday, February 9th 2003, 10:40pm

ein kumpel von mir und ich haben uns heute mal die mühe gemacht gemeinsam ein klausurenwissen für die theo inf klausur zusammenzustellen.. ist online auf meiner page unter theo inf.. link siehe signatur ;)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

17

Sunday, February 9th 2003, 11:36pm

danke für die arbeit, jungs!
so, das wissen auf nur 3 seiten sieht schon wieder "schaffbar" aus. :)

Cipher
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

18

Monday, February 10th 2003, 2:04pm

Quoted

Original von Cipher
@sebi: deine lösung von übungszettel 4 aufgabe 1 ist ganz ok, außer dass da mehr 0,1 zwischendurch stehen sollten (am anfang und am ende zum beispiel). aber das ist dann nur die lösung für aufgabe 1 nicht für 2.

Cipher




@Cipher: Das ist ein bisschen unpräzise. Wenn wir die Zustände von links nach rechts mit z1, z2, z3, z4 und z5 bezeichnen, dann fehlen folgende Pfeile: z2 -0-> z5, z3 -0-> z4 und z5 -0-> z5. Und damit ist es dann als DEA tatsächlich eine Lösung für 1 und 2.
Matthias Galota
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

19

Monday, February 10th 2003, 2:23pm

Quoted

Original von sebi
6.Übungsblatt 1. Aufgabe

Geben Sie einen Kellerautomaten an, der die Sprache {a^i b^i | i>=1 } akzeptiert

† soll das Kellersymbol sein, § = sigma, e=epsilon

K := ({a,b},{s0,s1,sf},{a,†}, §1, s0,†, {sf})^
mit §1 := {
(s0,e,†,sf,e),
(s0,a,†,s0,a†),
(s0,a,a,s0,aa),
(s0,b,a,s1,e),
(s1,b,a,s1,e),
(s1,e,†,sf,e) }


Fast perfekt! Der Befehl (s0,e,†,sf,e) führt aber dazu, dass das leere Wort von diesem Automaten akzeptiert wird. Da aber nur Wörter mit mindestens einem a und einem b akzeptiert werden dürfen (wegen "i>=1"), ist das leere Wort aber nicht in der Sprache. Der Befehl muss also ersatzlos gestrichen werden. Dann entspricht der Automat exakt der Musterlösung :)
Matthias Galota
  • Send private message

pj

Praktikant

Posts: 13

Date of registration: Nov 27th 2002

20

Monday, February 10th 2003, 2:41pm

Quoted

Original von Cipher
Lösung der Weihnachtsaufgabe (Übungsblatt 10)

...

Aber kann mir mal jemand sagen, wie man im Hinblick auf das Thema "Automatentheorie" an die Lösung gelangt?
...
Gibt es also noch andere Möglichkeiten auf diese Lösung zu kommen (und bitte auch nicht Brute Force vorschlagen ;) ).


Cipher



Ja, natürlich gibt es noch andere Möglichkeiten! Man kann strukturiert vorgehen. Z.B. hat die Zeitschrift PM auch ähnliche Aufgaben gestellt, deren Lösung man mit Hilfe von Tabellen und Ankreuzverfahren erhält, da mit jeder Festlegung einige andere ausgeschlossen sind.

Zudem kann man das mit Verfahren aus der KI (AI) lösen - allerdings sind das mehr oder minder Suchverfahren, die auf Brute Force (worst case) hinauslaufen. Aber das macht man ja auch nicht mehr per Hand...

Zudem gibt es noch den Logik-Ansatz, man kann aus den Aussagen Formeln mit Variablen aufstellen und versuchen, diese zu vereinfachen und zu lösen, ist aber etwas kompliziert zu überschauen. Dann werden zum Schluss den Variablen Werte aus {0,1} zugewiesen und es sollte sich ergeben, dass eine Zuweisung hinkommt. Oft lassen sich einige "falsche" Zuweisungen schon bei Betrachten der Formel ausschließen. Das Problem besteht allerdings, welcher Aussage man in welcher Form welche Variable zuordnet und dabei noch den Überblick behält...

Letztendlich hat es dann was mit Automaten zu tun, wenn man einen Computer zur Lösung einsetzt. Ein Computer ist ein DEA. Allerdings ist die Aufgabe höchstwahrscheinlich nicht klausurrelevant...

pj
--------------------
  • Send private message