Diskrete Strukuturen Klausuren aus SS08 und WS0809 - Page 2 - Mathematik - Fachrat Informatik

Pudge

Trainee

Posts: 84

Date of registration: Oct 13th 2010

Location: Hannover

21

Wednesday, July 13th 2011, 3:06pm

Edit: Hat sich erledigt, hatte i-wie ein Brainlag

Dumm ist, wer dummes tut :sleeping:

This post has been edited 2 times, last edit by "Pudge" (Jul 13th 2011, 6:24pm)

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

22

Wednesday, July 13th 2011, 3:19pm

Quoted from "Pudge"

@ Basti, ich glaube du hast einen Fehler bei Aufgabe 1.b der SoSe klausur.
Du berechnest ja zuerst ob der Graph H planarität hat. Das ist falsch,
die frage ist ob er planar ist dafür ist die Formel:
In einem zusammenhängenden planaren Graphen gilt nach dem eulersche Polyedersatzt stets:
Knotenzahl + Gebietszahl - Kantenzahl = 2.
Das wäre hier : 9 + (aus rechnung 13) - 20 = 2
demnach ist der Graph planar (was nicht heißt das planarität vorliegt).

Die Frage ist doch, ob H planar ist. Um den eulerschern Polyedersatz anwenden zu können, musst Du dieses erstmal feststellen. Und die notwendige Bedingung dafür ist eben |E| <= 3 * |V| - 6.

Quoted from "Pudge"

Edit: in der WiSe Klausur berechnest du auch nicht ob der Graph planar ist, sondern ob er Planarität besitzt.

Ich bin mir nicht ganz sicher, was Du mit diesen Begriffen genau unterscheiden möchtest.

Quoted from "Pudge"

Und für die frage ob er eulersch ist, gibst du ja die richtige Begründung, aber das falsche Ergebnis:
Prüfen: Graph zusammenhängend (trifft zu), alle Vertexgrade gerade (trifft zu) => H ist eulersch

Die Vertexgrade sind einfach nicht gerade, deswegen ist H nicht eulersch.

In H haben v1 bis v5 Grad 4, v6 sowie v7 Grad 6 und v8 sowie v9 Grad 8. Das sind alles gerade Grade.

This post has been edited 2 times, last edit by "Bastian" (Jul 13th 2011, 3:23pm)

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

23

Wednesday, July 13th 2011, 3:28pm

Also bei mir haben die Vertizes die Grade 4, 6 und 8, damit ist das Teil eulersch (SS08 ). Und der Rest scheint mir auch richtig.

edit: Hui, ich sollte meine Tabs nicht so lange offen stehen lassen.

This post has been edited 2 times, last edit by "SammysHP" (Jul 13th 2011, 3:30pm)

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

24

Wednesday, July 13th 2011, 4:48pm

Klausur WS08

Aufgabe 1
a)

Aufgabe 2
a)

$\tau_1 = (1\ 3\ 5\ 4)(2\ 6)\qquad\qquad\tau_2 = (1\ 4)(2\ 6\ 3)(5)$

Die Ordnung ist die Anzahl der Hintereinanderausführung einer Permutation, bis die Identität erreicht wird. Einfach berechnen lässt sie sich durch den kgV des Zykeltyps. $\tau_1$ hat die Ordnung $4 \cdot 1 = 2 \cdot 2 = 4$ , $\tau_2$ die Ordnung $3 \cdot 2 \cdot 1 = 6$ . Somit

.

b) + c)

Damit eine Permutation die Ordnung 6 hat, muss das kgV des Zykeltyps 6 sein. Bei einer 6-elementigen Permutation kommen nur die Typen (3, 2, 1) und (6) in Frage. Damit gibt es $2 \cdot \binom{6}{3} \cdot \binom{3}{2} + (6 - 1)! = 2 \cdot 20 \cdot 3 + 120 = 240$ Möglichkeiten.

Aufgabe 3
a)

aus $\varphi(n) = \prod_{p\mid n} p^{k_p-1}(p-1)$ ergibt sich:

$\varphi(108) = \varphi (2^2 \cdot 3^3) = 2^{2-1} \cdot (2-1) \cdot 3^{3-1} \cdot (3-1) = 2 \cdot 1 \cdot 9 \cdot 2 = 36$

b)

Damit $\overline{77}$ im Ring $\mathbb{Z}_{108}$ invertierbar ist, müssen 77 und 108 teilerfremd sein. Wir wenden den erweiterten Euklidischen Algorithmus an um zu prüfen, ob der $\operatorname{ggT}(77,\ 108) = 1$ ist und um dann das Inverse zu berechnen:

	Source code
1 2 3 4 5	108 1 0 77 0 1 31 1 1 -1 15 2 -2 3 1 2 5 -7

Damit ist $\overline{101}$ das Inverse von $\overline{77}$ .

This post has been edited 4 times, last edit by "SammysHP" (Jul 13th 2011, 6:59pm)

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

25

Wednesday, July 13th 2011, 4:56pm

Quoted from "SammysHP"

b)

Damit eine Permutation die Ordnung 6 hat, muss der kgV des Zykeltyps 6 sein. Bei einer 6-elementigen Permutation kommt nur der Typ (3, 2, 1) in Frage. Dieser hat $\binom{6}{3} \cdot \binom{3}{2} = 20 \cdot 3 = 60$ Möglichkeiten.

Müsste man nicht auch noch zusätzlich den Zykeltyp (6) betrachten?

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

26

Wednesday, July 13th 2011, 5:07pm

Stimmt, also +1.

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

27

Wednesday, July 13th 2011, 5:22pm

Zwei kleine Korrekturen:

Quoted from "SammysHP"

Klausur WS08
Aufgabe 3
a)

aus $\varphi(n) = \prod_{p\mid n} p^{k_p-1}(p-1)$ ergibt sich:

$\varphi(108) = \varphi (2^1 \cdot 3^3) = 2^{1-1} \cdot (2-1) \cdot 3^{3-1} \cdot (3-1) = 1 \cdot 1 \cdot 9 \cdot 2 = 18$

$\varphi(108) = \varphi (2^2 \cdot 3^3) = 2^{2-1} \cdot (2-1) \cdot 3^{3-1} \cdot (3-1) = 2 \cdot 1 \cdot 9 \cdot 2 = 36$

Quoted from "SammysHP"
b)

Damit im Ring invertierbar ist, müssen 77 und 108 teilerfremd sein. Wir wenden den erweiterten Euklidischen Algorithmus an um zu prüfen, ob der ist und um dann das Inverse zu berechnen:
Source code
1
2
3
4
5
108      1     0
 77      0     1
 31  1   1   -31
 15  2  -2    63
  1  2   5  -103
Damit ist das Inverse von .

Du hast einmal mit dem falschen Wert multipliziert:

	Source code
1 2 3 4 5	108 1 0 77 0 1 31 1 1 -1 15 2 -2 3 1 2 5 -7

=> a = 101, kann man auch leicht überprüfen, da $\overline{77}$ * $\overline{101}$ = $\overline{1}$ . Hingegen ist $\overline{77}$ * $\overline{5}$ = $\overline{61}$ .

Noch einmal zum Zykeltyp (6) und zum Zählen allgemein:

Quoted from "SammysHP"

Aufgabe 2
b) + c)

Damit eine Permutation die Ordnung 6 hat, muss der kgV des Zykeltyps 6 sein. Bei einer 6-elementigen Permutation kommen nur die Typen (3, 2, 1) und (6) in Frage. Damit gibt es $\binom{6}{3} \cdot \binom{3}{2} + \binom{6}{6} = 20 \cdot 3 + 1 = 61$ Möglichkeiten.

Beim Zykeltyp (3, 2, 1): Beim Zykel der Länge 3 weiß man eigentlich nur, dass der kleinste Wert an erster Stelle in der Zykelschreibweise steht, die zweite und dritte Stelle lassen sich noch tauschen. Selbes Argument bei den Permutationen mit Zykeltyp (6), hier weiß man nur, dass die 1 an der ersten Stelle steht. Daher halte ich folgende Rechnung für richtig:
$2 \cdot \binom{6}{3} \cdot \binom{3}{2} + (6 - 1)! = 2 \cdot 20 \cdot 3 + 120 = 240$

This post has been edited 1 times, last edit by "Bastian" (Jul 13th 2011, 5:45pm)

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

28

Wednesday, July 13th 2011, 5:45pm

Quoted from "SammysHP"

Klausur WS08
Einfach berechnen lässt sie sich durch den kgV des Zykeltyps. $\tau_1$ hat die Ordnung $4 \cdot 2 = 8$ , $\tau_2$ die Ordnung $3 \cdot 2 \cdot 1 = 6$ . Somit .

"Das" kleinste gemeinsame Vielfache, nicht "den".

Und die Ordnung von $\tau_1$ ist auch nicht 8 sondern 4: 1*4 = 2*2 = 4.
Die gefragte Lösung für $\tau_2$ ist jedoch richtig (2*3 = 3*2 = 6)

Crowdfunding! Kinderleicht dazuverdienen! Low-Risk = Supergut! Hier klicken!

Go to the top of the page

Pudge

Trainee

Posts: 84

Date of registration: Oct 13th 2010

Location: Hannover

29

Wednesday, July 13th 2011, 6:19pm

Argh... dicker Denkfehler meinerseits, nehme alles zurück.... :wacko:

Dumm ist, wer dummes tut :sleeping:

This post has been edited 2 times, last edit by "Pudge" (Jul 13th 2011, 6:22pm)

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

30

Wednesday, July 13th 2011, 6:59pm

Gut, dann habe ich das mal so übernommen... :whistling:

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

31

Wednesday, July 13th 2011, 8:03pm

Und nochmal die sachen die ich für die Wintersemester Klausur gemacht habe

Quoted

Aufgabe 2:

a)

1. (1354)(26)
2. (14)(263)(5)

1. kgv(4,2) = 4
2. kgv(2,3,1) = 6; Für i = 2 ist die Ordnung 6

b)

Alle kombinationen aus 1,2,3 und 6 Zykeln weil:
kgv(1,2,3,6) = 6

Sechs 1-Zykel
Ein 2 und vier 1-Zykel
Zwei 2 und zwei 1-Zykel
Drei 2-Zykel
Ein 3 und drei 1-Zykel
Ein 3, ein 2 und ein 1-Zykel
Zwei 3-Zykel
Ein 6-Zykel

Falsch

Aufgabe 3:

a) phi(108 ) = 18 * 2 = 36

108 = 2^2*3^3
27-27/3 = 18
4-4/2 = 2

Aufgabe 4:

T1: Verbindungen: 1-4;2-5;3-5;4-6;5-6
T2: Verbindungen: 1-2;3-6;5-4;2-4;2-6
T3: Verbindungen: 1-2;3-5;4-2;2-5;5-6

Crowdfunding! Kinderleicht dazuverdienen! Low-Risk = Supergut! Hier klicken!

This post has been edited 2 times, last edit by "vogelj" (Jul 13th 2011, 9:33pm)

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

32

Wednesday, July 13th 2011, 8:24pm

2 b) stimmt bei dir irgendwie nicht. Du listest alle möglichen Zykeltypen auf, von denen musst du jetzt noch das kgV berechnen.

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

33

Wednesday, July 13th 2011, 8:37pm

Das kgv gebe ich doch schon an. Danach liste ich alle möglichen Kombinationen dieser Zykeltypen auf mit denen man eine Permutation mit 6 Elementen (und zwangsweise der Ordnung 6 - aufgrund des kgv der einzelnen Zykel) erhält.

Du hast eigentlich das gleiche, nur fehlen bei dir diverse Zykelstrukturen weil du scheinbar nur welche im Stil von (xxx)(xx)(x) und (xxxxxx) betrachtest.
Ich liste folgende auf:

(x)(x)(x)(x)(x)(x)
(xx)(x)(x)(x)(x)
(xx)(xx)(x)(x)
(xx)(xx)(xx)
(xxx)(x)(x)(x)
(xxx)(xx)(x)
(xxx)(xxx)
(xxxxxx)

Denn die sind alle der Ordnung 6. Ich denke um alle Möglichkeiten für c) herausszufinden muss man all diese Strukturen einzeln betrachten und dann zusammenaddieren (Was ich in deiner Rechnung jedoch nicht erkennen kann).

Bin mir bei der Aufgabe aber auch absolut unsicher, also kann es auch gut sein dass du dort Recht hast.

Crowdfunding! Kinderleicht dazuverdienen! Low-Risk = Supergut! Hier klicken!

This post has been edited 1 times, last edit by "vogelj" (Jul 13th 2011, 8:39pm)

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

34

Wednesday, July 13th 2011, 8:53pm

Quoted from "vogelj"

Das kgv gebe ich doch schon an. Danach liste ich alle möglichen Kombinationen dieser Zykeltypen auf mit denen man eine Permutation mit 6 Elementen (und zwangsweise der Ordnung 6 - aufgrund des kgv der einzelnen Zykel) erhält.

Du hast eigentlich das gleiche, nur fehlen bei dir diverse Zykelstrukturen weil du scheinbar nur welche im Stil von (xxx)(xx)(x) und (xxxxxx) betrachtest.
Ich liste folgende auf:

(x)(x)(x)(x)(x)(x)
(xx)(x)(x)(x)(x)
(xx)(xx)(x)(x)
(xx)(xx)(xx)
(xxx)(x)(x)(x)
(xxx)(xx)(x)
(xxx)(xxx)
(xxxxxx)

Denn die sind alle der Ordnung 6. Ich denke um alle Möglichkeiten für c) herausszufinden muss man all diese Strukturen einzeln betrachten und dann zusammenaddieren (Was ich in deiner Rechnung jedoch nicht erkennen kann).

Bin mir bei der Aufgabe aber auch absolut unsicher, also kann es auch gut sein dass du dort Recht hast.

(3, 2, 1) und (6) sind die einzigen Zykeltypen mit Ordnung 6. Es gilt "kleinste Potenz m mit pi^m = id" = "Ordnung von pi" = "kgV aller Zykellängen".

Was Du aufgeschrieben hast, sind alle möglichen Zykeltypen in S6, wie SammysHP oben ja schon schrieb.

This post has been edited 1 times, last edit by "Bastian" (Jul 13th 2011, 9:01pm)

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

35

Wednesday, July 13th 2011, 9:32pm

Ach stimmt.. (xx)(xx)(xx) z.B. wäre ja Ordnung 2.
Mein Fehler.

Crowdfunding! Kinderleicht dazuverdienen! Low-Risk = Supergut! Hier klicken!

Go to the top of the page

hamena314

Zerschmetterling

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

36

Wednesday, July 13th 2011, 10:10pm

Noch ne kleine Frage nebenbei:
In den Klausuren sehe ich nichts zu Kombinatorik, wurde das ausgeschlossen?

HAVE PHUN!

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

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

37

Wednesday, July 13th 2011, 10:11pm

Quoted from "hamena314"

Noch ne kleine Frage nebenbei:
In den Klausuren sehe ich nichts zu Kombinatorik, wurde das ausgeschlossen?

Also bei den beiden Aufgaben 2c) und dann 3c) bzw. 4c) geht's ja schon ums Zählen.

Go to the top of the page

hamena314

Zerschmetterling

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

38

Thursday, July 14th 2011, 11:56am

So, meine Ergänzungen betreffen SS08:
2c) (1,1,1,1,1,1,) ... hat das nicht kgV 1? Bin unsicher ob man diese Permutationen dann noch mitzählen muss

3b)

	Source code
1 2 3 4 5	C1 C2 C3 3--5--4--2--6 2--5--1--6--3 2--5--1--6--4 \| \| \| 1 4 3

T1 kann man auch spiegelverkehrt zeichnen, so dass als Isomorphie-Permutations-Zykel (14)(256)(3) rauskommt.

3c)
$31^{399} mod 100$ kann man auch schreiben als $31^{400-1} mod 100 = (31^{40})^{10} mod 100$
Dabei ist $31^{40} = 1$ Was war die genaue Begründung dass das 1 ist?
Ab hier bin ich unsicher wie man weiter vorgeht. Da 1^10 immer noch 1 ist, kann man sagen dass 71 (= das Inverse von 31!) und 31 die gleiche Ordnung haben? Denn dann wäre das kleinste n hier 71.
Wolfram Alpha sagt auch dass 31^399 mod 100 = 71 sei.
http://www.wolframalpha.com/input/?i=31^399+mod+100

3d) Da hier nur nach ungeraden Zahlen gesucht wird, ist die $\varphi (2^{i})$ Spalte überflüssig. Dafür fehlt imho die Spalte mit $\varphi (41^{i})$

HAVE PHUN!

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

This post has been edited 1 times, last edit by "hamena314" (Jul 14th 2011, 11:59am)

Go to the top of the page

miata

Praktikant

Posts: 20

Date of registration: Aug 28th 2010

39

Thursday, July 14th 2011, 1:43pm

Eine Frage: Darf ein planarer Graph eigentlich Schleifen besitzen?
Ich habe den Graphen für A1 (SS2008 ) wie folgt gezeichnet:

This post has been edited 1 times, last edit by "miata" (Jul 14th 2011, 1:44pm)

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

40

Thursday, July 14th 2011, 3:18pm

Entscheidend ist wohl die Definition 2.2 aus der fünften Vorlesung:

Quoted

Hat ein Multigraph weder Schleifen noch Mehrfachkanten, so heißt er schlichter Graph

Also, wenn in einer Aufgabe Graph steht, keine Schleifen und Mehrfachkanten, bei Multigraph ist beides erlaubt.

This post has been edited 1 times, last edit by "Bastian" (Jul 14th 2011, 3:21pm)

Go to the top of the page

	Source code
1 2 3 4 5	108 1 0 77 0 1 31 1 1 -31 15 2 -2 63 1 2 5 -103