P1-WS04-MusterLoesung02.txt

Aus Fachschaft_Informatik
Zur Navigation springen Zur Suche springen
Die druckbare Version wird nicht mehr unterstützt und kann Darstellungsfehler aufweisen. Bitte aktualisiere deine Browser-Lesezeichen und verwende stattdessen die Standard-Druckfunktion des Browsers.
Musterlösung Blatt 2
(P1, [[WiSe]] 04/05)
Özgür Özcep

Aufgabe 1
---------

Ad a) und c)
<tag> ::= ( [('0'|'1'|'2')]('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9') ) | '3'('0'|'1')
<monat>::= (['0']('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | '1'('0|'1'|'2'|)
<jahr>::= (('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'){('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')})
<datum> ::=  <tag> '.'<monat>'.'<jahr>

In einer einzigen Regel formuliert:
<datum>::= ( (['0']('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | (('1'|'2')('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | '3'('0'|'1'))'.'
((['0']('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | '1'('0|'1'|'2'|))'.'
(('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'){('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')})
 
Anmerkung:
Mit der angegebenen EBNF für Datumsangaben werden auch faktisch nicht
mögliche Termine wie "31.04.2004" erzeugt. (--> Korrektheit nicht
erfüllt!?) Ebenfalls unbedacht sind die Schaltjahre.

Nicht erfasst werden:
1.  Datumsangaben in anderen natürlichen  Sprachen wie z.B. im Englischen;
2. "unvollständige" bzw. "grobe" Datumsangaben wie "Im Jahre 1992". 
(--> Vollständigkeit nicht erfüllt!);
3. Datumsangaben des Typs "12. Dezember 1999" mit einer
natürlichsprachlichen Monatsangabe. Ausgeschlossen wird eine
Datumsangabe der Form "Der 35. Mai" (Titel eines Erich Kästners
Buches), obwohl dieses als eine Datumsangabe verstanden werden könnte. 
(Probleme bereitet dann allerdings die Semantik dieses Ausdrucks,
ähnlich der Problematik für Eigennamen von fiktiven Gegenständen:
"Pegasus","Die Büchse der Pandorra" etc.)

Ad b)

gsed 's/\(\([012]\?[0-9]\|3[01]\)\.\(0\?[1-9]\|1[012]\)\.[0-9]\+\)/<date> \1 <\/date>/g' spenden.txt > spenden.anno




Aufgabe 2 (Rekursive Einbettung)
--------------------------------

Ad a)
[1]	<atomares element> ::= (<alphanum. Zeichen>){<alphanum. Zeichen>}
[2]	<alphanum. Zeichen> := <Buchstabe>|<Ziffer>
[3]	<Buchstabe>::= 'A' | 'B' | 'C' | ....  'Z' | 'a' | ... | 'z'
[4]	<Ziffer> ::= '0' | '1' | ... | '9'
[5]	<einfache Menge> ::= '{' {<atomares Element>', '}  <atomares Element> '}' | '{ }'

"Testen" der VollstŠndigkeit und Korrektheit:
- Ableitung der leeren Menge:  Regel 5
- Ableitung für { a,b,c }: 
<einfache Menge>  -->[5] 
 '{' {<atomares Element>}, }  <atomares Element>'}' -->[Def. Wdh.]
{<atomares Element>, <atomares Element>, <atomares Element>} --> 3 mal [1]
{<alphanum. Zeichen>, <alphanum. Zeichen>, <alphanum. Zeichen>}  --> 3 mal [2]
{<Buchstabe>, <Buchstabe>, <Buchstabe>} --> 3 mal [3]
{a, b, c}

Legende: 
uxw -->[R] uyw bedeutet: Die rechte Seite entsteht aus einer
Anwendung der Regel mit der Regelnummer R auf x (mit y als Ergebnis).

Ad b)
Füge zu obigen Regeln hinzu:

[6]	<Menge> ::=  '{' {(<Menge>|<atomares Element>)', '}  (<atomares Element>|<Menge>) ' }'  | '{ }'


- Ableitung für {{a,b}, c, d}

<Menge> -->[6]  
'{' {(<Menge>|<atomares Element>), }  (<atomares Element>|<Menge>) ' }'  -->[Def. Wdh.]
'{'(<Menge>|<atomares Element>), (<Menge>|<atomares Element>), (<Menge>|<atomares Element>)'}' -->[Def. Alternative]
'{'<Menge>, <atomares Element>, <atomares Element>'}' -->[6]
'{''{' {(<Menge>|<atomares Element>), }  (<atomares Element>|<Menge>) ' }' , <atomares element>, <atomares Element>} --> [Def. Wdh.]
'{''{'(<Menge>|<atomares Element>), (<Menge>|<atomares Element>)'}',<atomares element>, <atomares Element>'}' -->[Def. Alternative]
'{''{'<atomares Element>, <atomares Element>'}', <atomares Element>, <atomares Element>'}'  --> 4 mal [1],[2] und Def. der Alternative
{{a, b}, c, d}


Aufgabe 3 (Prologanfragen)
--------------------------

ad a) und b) 

Script started on Mon Oct 25 13:56:30 2004
[wsv9:Aufgaben[[/Blatt02/Vorlagen_Blatt02]]] oessi% swipl
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.0)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- consult(familie).
% familie compiled 0.00 sec, 2,204 bytes

Yes
?- listing(vater_von)UTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENT.

:- dynamic vater_von/2.

vater_von(otto, hans).
vater_von(otto, helga).
vater_von(gerd, otto).
vater_von(johannes, klaus).
vater_von(johannes, andrea).
vater_von(walter, barbara).
vater_von(walter, magdalena).

Yes
?- listing(mutter_von)?- listing(mutter_von).

:- dynamic mutter_von/2.

mutter_von(marie, hans).
mutter_von(marie, helga).
mutter_von(julia, otto).
mutter_von(barbara, klaus).
mutter_von(barbara, andrea).
mutter_von(charlotte, barbara).
mutter_von(charlotte, magdalena).

Yes
?- mutter_von(barbara,klaus) % Ist Barbara die Mutter von Klaus?

Yes
?- vater_von(otto,gerd). 	% Ist Otto der Vater von Gerd? 

No
?- vater_von(X,andrea). 	% Wer ist der Vater von Andrea?

X = johannes ; 	

No		% Andrea hat keinen weiteren Vater
?- mutter_von(X,marie).	%Wer ist die Mutter von Marie?

No
?- vater_von(otto,X). 	
% Welche Kinder hat Otto? Hier wird vorausgesetzt,
% dass Otto nicht Mutter sein kann; 
% ansonsten hätte man
%  zu fragen: 
% ?-vater_von(otto,X);mutter_von(otto,X).

X = hans ;

X = helga ;

No
% Wer hat welche Kinder:
?- vater_von(X,Y).

X = otto
Y = hans ;

X = otto
Y = helga ;

X = gerd
Y = otto ;

X = johannes
Y = klaus ;

X = johannes
Y = andrea ;

X = walter
Y = barbara ;

X = walter
Y = magdalena ;

No
?- mutter_von(X,Y).

X = marie
Y = hans ;

X = marie
Y = helga ;

X = julia
Y = otto ;

X = barbara
Y = klaus ;

X = barbara
Y = andrea ;

X = charlotte
Y = barbara ;

X = charlotte
Y = magdalena ; 

No
% Alternativ hätte man eine einzige Anfrage mithilfe
% von ';' stellen koennen:
% ?- vater_von(X,Y);mutter_von(X,Y).


% Ad c)?- assert(vater_von(bert,lisa)).

Yes?- asserta(mutter_von(lisa,anna)).

Yes
?- assertz(mutter_von(lisa,moritz)).

Yes
?- listing. % Was hat sich in der Datenbasis getan?

%   Foreign: rl_read_init_file/1

:- dynamic vater_von/2.

vater_von(otto, hans).
vater_von(otto, helga).
vater_von(gerd, otto).
vater_von(johannes, klaus).
vater_von(johannes, andrea).
vater_von(walter, barbara).
vater_von(walter, magdalena).
vater_von(bert, lisa).

%   Foreign: rl_add_history/1

:- dynamic mutter_von/2.

mutter_von(lisa, anna).
mutter_von(marie, hans).
mutter_von(marie, helga).
mutter_von(julia, otto).
mutter_von(barbara, klaus).
mutter_von(barbara, andrea).
mutter_von(charlotte, barbara).
mutter_von(charlotte, magdalena).
mutter_von(lisa, moritz).

Yes
?- halt.
[wsv9:Aufgaben[[/Blatt02/Vorlagen_Blatt02]]] oessi% exit
exit

Script done on Mon Oct 25 14:00:56 2004

ad c) 
Die Fakten werden der Datenbasis hinzugefügt.

asserta fügt das Faktum an den Anfang und  
assertz ans Ende der Datenbasis an. 
assert  ist ein Alias auf assertz.





Aufgabe 4) (Dirk Knoblauch)
---------------------------

Beispiel: Übungsgruppen 
Ein Beispiel sind die Informationen zu den Übungsgruppen P1 letzten Jahres:

uebungsgruppe(di,12,14,d125a,chen).
uebungsgruppe(di,12,14,f132,wiegreffe).
uebungsgruppe(di,14,16,d125a,koethe).
uebungsgruppe(di,14,16,f132,wiegreffe).
uebungsgruppe(fr,10,12,f132,dreschler).
uebungsgruppe(fr,12,14,f132,stelldinger).
uebungsgruppe(mi,8,10,f132,knoblauch).
uebungsgruppe(mi,10,12,f132,knoblauch).
uebungsgruppe(mi,12,14,d129,finck).
uebungsgruppe(mi,12,14,f132,chen).
uebungsgruppe(mi,14,16,f535,schmidtke).
uebungsgruppe(mi,16,18,f535,obendorf).
uebungsgruppe(fr,10,12,d125a,foth).


Beispielanfragen:

1. Welche Übungsgruppen gibt es?

1 ?- uebungsgruppe(Tag,Anfang,Ende,Raum,Leitung).

Tag = di
Anfang = 12
Ende = 14
Raum = d125a
Leitung = chen ;

Tag = di
Anfang = 12
Ende = 14
Raum = f132
Leitung = wiegreffe ;

Tag = di
Anfang = 14
Ende = 16
Raum = d125a
Leitung = koethe ;

Tag = di
Anfang = 14
Ende = 16
Raum = f132
Leitung = wiegreffe ;

Tag = fr
Anfang = 10
Ende = 12
Raum = f132
Leitung = dreschler ;

Tag = fr
Anfang = 12
Ende = 14
Raum = f132
Leitung = stelldinger ;

Tag = mi
Anfang = 8
Ende = 10
Raum = f132
Leitung = knoblauch ;

Tag = mi
Anfang = 10
Ende = 12
Raum = f132
Leitung = knoblauch ;

Tag = mi
Anfang = 12
Ende = 14
Raum = d129
Leitung = finck ;

Tag = mi
Anfang = 12
Ende = 14
Raum = f132
Leitung = chen ;

Tag = mi
Anfang = 14
Ende = 16
Raum = f535
Leitung = schmidtke ;

Tag = mi
Anfang = 16
Ende = 18
Raum = f535
Leitung = obendorf ;

Tag = fr
Anfang = 10
Ende = 12
Raum = d125a
Leitung = foth ;

No

2. Welche finden in d129 statt?

1 ?- uebungsgruppe(Tag,Anfang,Ende,d129,Leitung).

Tag = mi
Anfang = 12
Ende = 14
Leitung = finck ;

No



3. Welche Übungen führt Herr Knoblauch durch? 
 
1 ?- uebungsgruppe(Tag,Anfang,Ende,Raum,knoblauch).

Tag = mi
Anfang = 8
Ende = 10
Raum = f132 ;

Tag = mi
Anfang = 10
Ende = 12
Raum = f132 ;

No

4. Gibt es am Mittwoch eine Übungsgruppe von Herrn Obendorf?

1 ?- uebungsgruppe(mi,Anfang,Ende,Raum,obendorf).

Anfang = 16
Ende = 18
Raum = f535 ;

No