Sie sind nicht angemeldet.

Kiki der Gecko

Regenbogeneidechse

  • »Kiki der Gecko« ist der Autor dieses Themas

Beiträge: 513

Registrierungsdatum: 01.10.2008

1

07.07.2010, 17:58

Musterlösungen zu DS Bonustests SS10 [hier!]

Hallo alle miteinander,

Um mich auf die DS-Klausur vorzubereiten und gleichzeitig meine Fertigkeiten im Umgang mit Latex ein wenig zu verbessern habe ich mich mal daran gemacht, Musterlösungen für die Bonustests zu Diskrete Strukturen zu erarbeiten.

Die Lösungen sind auch garantiert richtig, ich stehe derzeit in Schriftverkehr mit Herrn Erné, er meinte es wären nur noch "ein paar Kleinigkeiten" zu korrigieren. Freundlicherweise arbeitet er die Ergänzungen direkt in meinen Quelltext ein. Sobald ich die finale Version wieder zurück bekomme, werde ich die Dateien natürlich austauschen. Da aber vermitluch viele schon mitten im Lernen drin sind, gibts halt schonmal Version 1 :)

Besonder Dank geht auch an Oli/killroy und Jan/gothos, die zusammen mit mir die Lösungen erarbeitet haben.

Ich hoffe es bringt der einen oder anderen Lerngruppe noch etwas :)

Viel Erfolg schon mal,

Kiki
»Kiki der Gecko« hat folgende Dateien angehängt:
  • bonus1.pdf (135,48 kB - 273 mal heruntergeladen - zuletzt: 14.12.2018, 16:57)
  • bonus2.pdf (145,4 kB - 263 mal heruntergeladen - zuletzt: 25.01.2019, 01:35)
  • bonus3.pdf (145,62 kB - 246 mal heruntergeladen - zuletzt: 21.01.2019, 11:01)
  • bonus4.pdf (140,98 kB - 245 mal heruntergeladen - zuletzt: 05.01.2019, 16:09)
"Alles ist eins - außer der Null." - Wau Holland

epix

Junior Schreiberling

  • »epix« ist männlich

Beiträge: 191

Registrierungsdatum: 28.09.2009

Wohnort: Hannover

2

07.07.2010, 18:02

Coole Sache! Vielen dank :)

hamena314

Zerschmetterling

  • »hamena314« ist männlich

Beiträge: 2 032

Registrierungsdatum: 31.08.2003

Wohnort: Hannover

Beruf: Informatikstudent (d'uh)

3

07.07.2010, 18:40

Vielen Dank auch von mir! :)

HAVE PHUN!
Nicht der Wind bestimmt die Richtung, sondern das Segel! (Lao Xiang, China)

newgame

Trainee

Beiträge: 45

Registrierungsdatum: 30.09.2009

4

07.07.2010, 19:25

Gute Sache!

Sebastian

Trainee

  • »Sebastian« ist männlich

Beiträge: 101

Registrierungsdatum: 21.09.2007

Wohnort: Hannover

5

07.07.2010, 23:14

Super Sache, danke!

Zu den kombinatorischen Beweisen: da kann man sich die Sätze etc. sparen indem man einfach Bildchen malt.
Z.B. für den ersten Test:
(n choose k) bedeutet, aus n Elementen k auszuwählen.
Die rechte Seite der Gleichung ist einfach eine Fallunterscheidung: man betrachtet 2 bestimmte Elemente, die man entweder auswählen oder nicht auswählen will:
(n-2 choose k) bedeutet, dass ich die 2 Elemente auf keinen Fall auswählen möchte (also k aus den restlichen Elementen auswähle).
2*(n-2 choose k-1) bedeutet, dass ich nur genau eins von den beiden Element auswählen möchte und das andere nicht. 2 mal, weil man 2 Möglichkeiten hat (eben das eine, oder das andere auswählen).
(n-2 choose k-2) ist dann der letzte Fall, in dem ich beide Elemente auf jeden Fall auswählen möchte, also wähle ich aus dem Rest nur noch k-2 aus.

Dazu malt man am besten noch ein kleines Bildchen mit der Menge n, den 2 festen Elementen und dann 3 Kreise für die Summanden.

Im Test gab es auf diese Lösung volle Punktzahl.
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Sebastian« (07.07.2010, 23:14)


Mehrad

Trainee

  • »Mehrad« ist männlich

Beiträge: 53

Registrierungsdatum: 01.10.2009

Wohnort: Hannover

6

08.07.2010, 11:59

super Ding danke ;)

Kiki der Gecko

Regenbogeneidechse

  • »Kiki der Gecko« ist der Autor dieses Themas

Beiträge: 513

Registrierungsdatum: 01.10.2008

7

08.07.2010, 12:01

Super Sache, danke!

Zu den kombinatorischen Beweisen: da kann man sich die Sätze etc. sparen indem man einfach Bildchen malt.


Hast du schonmal in Tex mit Bildern gearbeitet? Ist die Hölle :P
"Alles ist eins - außer der Null." - Wau Holland

8

11.07.2010, 20:50

Danke erstmal an Karoline Busse und Co. für die Arbeit.

Ich glaube, das bei der Lösung vom Bonustest "DS_2010_bonus1a" zur Aufgabe 3 ein kleiner Fehler ist.

Und zwar ist der Graph zum Aufgabenteil c) nicht richtig. Die Matrix D ist richtig angegeben, die Produktrelation R^2 besagt dagegen, dass folgende Verbindungen gelten: (1,3),(2,3),(2,4). Im Graph der Lösung ist jedoch anstatt (1,3) ein Pfeil (1,4), den es jedoch nur in R gibt.

Nochmals vielen Dank dafür, das Ergebnis eurer Arbeit geteilt zu haben :thumbup:

  • »Schokoholic« ist männlich

Beiträge: 2 516

Registrierungsdatum: 04.10.2006

Wohnort: Hannover

Beruf: Haarspaltung

9

12.07.2010, 15:57

Hast du schonmal in Tex mit Bildern gearbeitet? Ist die Hölle :P
Nur als Anmerkung: PGF/TikZ (steht für "TikZ ist kein Zeichenprogramm") ist cool. Hat zwar auch eine relativ steile Lernkurve, ist dann aber doch recht intuitiv und die resultierenden Grafiken sind klasse. ;)

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »Schokoholic« (12.07.2010, 15:57)


Kiki der Gecko

Regenbogeneidechse

  • »Kiki der Gecko« ist der Autor dieses Themas

Beiträge: 513

Registrierungsdatum: 01.10.2008

10

14.07.2010, 12:48

So, mit leider ganz schöner Verspätung noch die Korrekturn von Herrn Erné. Leider hat er nur Zeit gefunden, die erste Musterlösung zu verbessern. Ich fass hier mal schnell die Änderungen zusammen:

"Kombinatorisches Argument" bedeutet wirklich argumentieren, also genau so wie schon die Anmerkung von Sebastian kan.

Bei der Aufstellung der Inzidenzmatrix der Relation macht es auch gleich Sinn, alle interessanten Potenzen der Matrix (bzw. Der Relation) aufzuschreiben, dann fällt die folgende Aufgabe leichter.

Viel Erfolg allen schonmal bei der Klausur am Freitag Abend :)
»Kiki der Gecko« hat folgende Datei angehängt:
  • bonus1ME.pdf (74,72 kB - 183 mal heruntergeladen - zuletzt: 15.12.2018, 23:50)
"Alles ist eins - außer der Null." - Wau Holland

newgame

Trainee

Beiträge: 45

Registrierungsdatum: 30.09.2009

11

14.07.2010, 15:52

Ich habe eine Anmerkung zur Musterloesung "bonus4.pdf" zur Aufgabe 2c zur Bonusklausur 2a.

Man soll die Anzahl aller totalen und antisymmetrischen Relationen bestimmen. Als Antwort ist gegeben. Meiner Meinung nach muessen es Relationen sein.

* Insgesamt gibt es Eintraege
* Die Diagonale ist fest mit 1en belegt, also interessieren uns Eintrage schonmal nicht
* Fuer das obere Dreieck (ohne die Diagonale) gibt es also Eintraege, die frei gewaehlt werden duerfen
* Der an der Diagonalen gespiegelte Eintrag ist damit immer fest - eine 0 wenn fuer den gespiegelten Eintrag im oberen Dreieck eine 1 gewaehlt wurde und eine 1, wenn fuer den gespiegelten Eintrag im oberen Dreieck eine 0 gewaehlt wurde

Somit gibt es Relationen, weil man eben fuer das obere Dreieck ohne die Diagonale die freie Wahl hat.

Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von »newgame« (14.07.2010, 18:46)


Nagezahn

Junior Schreiberling

  • »Nagezahn« ist männlich

Beiträge: 198

Registrierungsdatum: 09.02.2010

Wohnort: Nordstadt

12

14.07.2010, 16:30

Im Prinzip stimme ich dir zu: die Fakultät hat meiner Ansicht nach an der Stelle nichts zu suchen. Da gehört eine Summe von 1 bis (n-1) hin, die sich mit Gauss zu ergibt.

Aber wie kommst du von auf ?

newgame

Trainee

Beiträge: 45

Registrierungsdatum: 30.09.2009

13

14.07.2010, 16:36

Im Prinzip stimme ich dir zu: die Fakultät hat meiner Ansicht nach an der Stelle nichts zu suchen. Da gehört eine Summe von 1 bis (n-1) hin, die sich mit Gauss zu ergibt.

Aber wie kommst du von auf ?


sind alle Eintraege ohne die Diagonale. sind die Haelfte dieser Eintraege und damit interpretierbar als die Eintraege in der oberen Dreieckshaelfte (ausgenommen der Diagonalen) der Matrix. Und diese sind gerade frei waehlbar.

newgame

Trainee

Beiträge: 45

Registrierungsdatum: 30.09.2009

14

14.07.2010, 16:45

Und da ich gerade dabei bin, noch eine Anmerkung zur Musterloesung "bonus2.pdf" zur Testatklausur 3a zu Aufgabe 2c.

Meiner Meinung nach ist die Anzahl der irreflexiven und antisymmetrischen Relationen auf .

* Die Diagonale ist fest mit nullen (n Eintrage)
* Fuer die obere Dreieckshaelfte ohne die Diagonale ( Eintrage) und ihrem gespiegelten Eintrag gibt es drei moegliche Paare: (1,0), (0,1) und (0,0). Hieraus ergibt sich die Basis 3.

Nagezahn

Junior Schreiberling

  • »Nagezahn« ist männlich

Beiträge: 198

Registrierungsdatum: 09.02.2010

Wohnort: Nordstadt

15

14.07.2010, 16:49

sind alle Eintraege ohne die Diagonale. sind die Haelfte dieser Eintraege.
Also wenn mich meine Mathekenntnisse nicht vollständig verlassen haben, ist die Hälfte von .

newgame

Trainee

Beiträge: 45

Registrierungsdatum: 30.09.2009

16

14.07.2010, 17:00

Und da ich gerade dabei bin, noch eine Anmerkung zur Musterloesung "bonus2.pdf" zur Testatklausur 3a zu Aufgabe 2c.

Meiner Meinung nach ist die Anzahl der irreflexiven und antisymmetrischen Relationen auf .

* Die Diagonale ist fest mit nullen (n Eintrage)
* Fuer die obere Dreieckshaelfte ohne die Diagonale ( Eintrage) und ihrem gespiegelten Eintrag gibt es drei moegliche Paare: (1,0), (0,1) und (0,0). Hieraus ergibt sich die Basis 3.


Ausserdem noch zum letzten Aufgabenteil. In der Musterloesung wird von mehreren Aequivalezklassen gesprochen, wobei die symmetrisch-reflexiv-transitive Huelle in dem Fall die Allrelation ist. Deshalb gibt es nur eine Komponente und auch nur eine Aequivalenzklasse wobei ein Repraesentant ist.

newgame

Trainee

Beiträge: 45

Registrierungsdatum: 30.09.2009

17

14.07.2010, 17:40

Und da ich gerade dabei bin, noch eine Anmerkung zur Musterloesung "bonus2.pdf" zur Testatklausur 3a zu Aufgabe 2c.

Meiner Meinung nach ist die Anzahl der irreflexiven und antisymmetrischen Relationen auf .

* Die Diagonale ist fest mit nullen (n Eintrage)
* Fuer die obere Dreieckshaelfte ohne die Diagonale ( Eintrage) und ihrem gespiegelten Eintrag gibt es drei moegliche Paare: (1,0), (0,1) und (0,0). Hieraus ergibt sich die Basis 3.


Genau die selbe Argumentation wuerde ich auch fuer 'bonus3.pdf' zur Testatklausur 4a zu Aufgabe 2c benutzen, nur dass eben reflexiv mit irreflexiv vertauscht werden sollte.


Die letzte Anmerkung, da ich jetzt durch bin:

Die kombinatorischen Beweise der Stirling Formeln kann man soweit ich weiss direkt aus dem Skript entnehmen. Fuer den kombinatorischen Beweis zu Testat 2a Aufgabe 1b haette ich folgenden Vorschlag (ohne Gewaehr):
" ist die Anzahl aller n-elementigen Teilmengen von . Nehme ein Element x dazu. Aus jeder Teilmenge von X kann durch Ersetzen eines Elements in der Teilmenge durch x eine neue geschaffen werden. Die Anzahl der Teilmengen verdoppelt sich also und daher kommt und das ist eben genau , naemlich die Anzahl aller Teilmengen der Menge "

Das waren also nun meine Verbesserungsvorschlaege der Musterloesungen (ohne Gewaehr auf Korrektheit). Ich finde die Sache (also das Bereitstellen von studentischen Musterloesungen zu Aufgaben) gut und wollte meinen Beitrag dazu leisten, auch wenn es etwas spaet kommt. Vielleicht waere es angebracht zu ueberlegen, ob man fuer so etwas eine Art Wiki erstellen koennte oder sowas wie http://piratepad.net/.