Diskrete Strukuturen Klausuren aus SS08 und WS0809

Dies, das, einfach so verschiedene Dinge

Date of registration: Sep 30th 2007

Tuesday, July 12th 2011, 9:09am

Dieser Thread soll der Diskussion der Lösungen der Klausuren zur Vorlesung Diskrete Strukturen aus dem SS08 und dem WS0809 dienen.

In diesem ersten Beitrag werden die diskutierten Lösungen laufend zusammengefasst. Ergänzungen und Korrekturen bitte als Antwort zum Thema. Einige Lösungen sind direkt zum Beitrag im Thread verlinkt, da die Forumssoftware nur 10.000 Zeichen pro Eintrag erlaubt, und sie daher nicht mehr in diesen Beitrag übernommen werden konnten.

Klausur SS08
Aufgabe 1
a)
Anzahl der Gebiete: Eulersche Polyederformel nach Anzahl der Gebiete umstellen => |Gebiete| = 2 - |V| + |E|

|V| = 8, |E| = 1/2 * Summe der Grade aller Vertizes = 16 => |Gebiete| = 10

Zeichnung eines solchen Graphen: Zuerst v8 in die Mitte von v1 bis v7 zeichnen und mit diesen verbinden. v6 mit v5, v4 und v3 sowie v7 mit v1, v2 und v3 verbinden. Abschließend v6 mit v7, v5 mit v4 und v1 mit v2 verbinden.

Eine andere Variante ist diese Zeichnung:

b)
Ist H planar?

Notwendige Bedingung für Planarität: |E| <= 3 * |V| - 6

H hat |V| = 9 und |E| = 24 (zur Berechnung siehe oben) => 24 <= 3 * 9 -6 falsche Aussage => H ist nicht planar

Ist H eulersch?

Prüfen: Graph zusammenhängend (trifft zu), alle Vertexgrade gerade (trifft zu) => H ist eulersch

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

$\tau_i^2 =\ \mbox{id}$ gilt für

, denn es ist:

$\tau_1 \circ \tau_1 = \begin{pmatrix}1&2&3&4&5&6\\3&5&1&4&2&6\\1&2&3&4&5&6\end{pmatrix}$

b)
Bei einer Permutation 2- Zykeln werden nur die Elemente hin- und hergetauscht:
Die erste Permutation führt also dazu das z.B. 1 und 3 vertauscht werden.
Die zweite Permutation führt dann dazu das 3 und 1 wieder zurückgetauscht werden
1- Zykel haben keinen einfluss, die Elemente bleiben an ihrer Position.

Bei n- Zykeln braucht man n Permutatioen um ein Element wieder an seine Ursprungspostion getauscht zu haben.

c)
Für Zykeltyp (2,2,2): $\frac {6!} {3!*2^3}=15$
Für Zykeltyp (2,2,1,1): $\frac {6!} {2!*2^2*2!*1^2}=45$
Für Zykeltyp (2,1,1,1,1): $\frac {6!} {1!*2^1*4!*1^4}=15$
Für Zykeltyp (1,1,1,1,1,1): ...=1

Aufgabe 3
a)

	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

Alle Bäume haben genau 3 Blätter und gehören deswegen alle zu A.

Beispiel für T1 (Prüfer-Code: 4542):

123456
4542

1, 3 und 6 kommen nicht im Prüfer-Code vor:

123456
4542

Jetzt für jede Stelle im Prüfer-Code von Links nach Rechts:

123456
4542

Verbindung: 4-1

123456
4542

Verbindung: 5-3
(5 Kommt nicht mehr im Prüfer-Code vor)

123456
4542

Verbindung: 4-5
(4 Kommt nicht mehr im Prüfer-Code vor)

123456
4542

Verbindung: 2-4
(2 Kommt nicht mehr im Prüfer-Code vor)

123456
4542

Prüfer-Code abgearbeitet, die letzten verbleibenden Vertizes verbinden:

Verbindung: 2-6

b)

und

sind offensichtlich isomorph. Wie gibt man einen expliziten Isomorphismus an? Z.B. mit einer Permutation, hier also (1 4) (2 6 3) (5).

c)
Der Prüfercode hat die Länge 4 (=6Knoten-2). Dann sollen einmal deg(v2)=3, einmal deg(v3)=3, einmal deg(v4)=3 und einmal deg(v5)=3 sein. Daraus folgt jeweils, dass jeweils die Markierungen (3-1)mal vorkommen. Also für alle $\begin{pmatrix} 4 \\ 2 \end{pmatrix}$ . Diese werden addiert, also hierbei $\begin{pmatrix} 4 \\ 2 \end{pmatrix}\cdot4=\frac{4!}{2!\cdot2!}\cdot4=\frac{24}{4}\cdot4=24$ .

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

$\varphi(100) = \varphi (2^2 \cdot 5^2) = 2^{2-1} \cdot (2-1) \cdot 5^{2-1} \cdot (5-1) = 2 \cdot 5 \cdot 4 = 40$

b)
Damit $\overline{31}$ im Ring $\mathbb{Z}_{100}$ invertierbar ist, müssen 31 und 100 teilerfremd sein. Da 31 eine Primzahl ist und 100 kein Vielfaches von 31, ist dies der Fall. Wir können also mit dem erweiterten Euklidischen Algorithmus das Inverse berechnen:

	Source code
1 2 3 4 5	100 1 0 31 0 1 7 3 1 -3 3 4 -4 13 1 2 9 -29

Damit ist $\overline{-29}$ bzw. $\overline{71}$ das Inverse von $\overline{31}$ .

c)
$31^{399} mod 100$ kann man auch schreiben als $31^{400-1} mod 100 = (31^{40})^{10} * 31^{-1} mod 100$
Dabei ist $31^{40} = 1$ => 31^399 mod 100 = 71.

d)

	Source code
1 2	p 2 3 5 7 11 13 17 19 23 29 31 37 41 ... p-1 1 2 4 6 10 12 16 18 22 28 30 36 40 ...

Teiler von phi(n) = 40:

	Source code
1 2	p-1 1 2 4 10 40 p 2 3 5 11 41

Die erste Zahl für m ist direkt ablesbar weil phi(p) = p - 1 ist, demnach gibt es m = 41

	Source code
1 2 3 4 5 6 7	i phi(2^i) phi(3^i) phi(5^i) phi(11^i) 0 1 1 1 1 1 1 2 4 10 2 2 6 20 110 3 4 18 4 8

2 Wege:

	Source code
1 2 3 4 5 6 7	a b c d phi() 1 1 4 10 i 0 0 1 1 phi() 1 2 20 1 i 0 1 2 0

40 = phi(n) = phi(2^a)*phi(3^b)*phi(5^c)*phi(11^d)

Also:

40 = phi(5*11) = phi(55)
40 = phi(3*25) = phi(75)
40 = phi(41)

Die Zahlen für m sind 55,75 und 41

Aufgabe 5
a)
...

b)
...

c)
...

Klausur WS0809
Aufgabe 1
a)
Anzahl der Gebiete: |V| = 8, |E| = 17 => |Gebiete| = 11 (Berechnung siehe oben)

Zeichnung: Vertizes in drei Zeilen gruppieren: Erste Zeile v1 bis v3, zweite Zeile v7 und v8 sowie dritte Zeile v4 bis v6. v7 mit v1, v2, v4, v5 und v8 sowie v8 mit v2, v3, v5 und v6 verbinden. Nun v1 mit v2, v2 mit v3, v3 mit v6, v6 mit v5, v5 mit v4 und v4 mit v1 verbinden. Abschließend v1 mit v3 sowie v6 mit v4 verbinden.

Eine andere Variante ist diese Zeichnung:

Hat G einen Euler-Weg?

Prüfen: Graph zusammenhängend (trifft zu), zwei Vertexgrade ungerade (trifft zu) => G hat einen Euler-Weg

b)
Ist H planar?

H hat |V| = 9 und |E| = 23 => 23 <= 3 * 9 -6 falsche Aussage => H ist nicht planar (Berechnung siehe oben)

Ist H eulersch?

Prüfen: Graph zusammenhängend (trifft zu), alle Vertexgrade gerade (trifft nicht zu) => H ist nicht eulersch

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}$ .[/quote]

c)

d)
...

Aufgabe 4
a) + b)

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

c)
ausführliche Lösung

Aufgabe 5
a)
...

b)
...

c)
...

Zusätzliches
Rekursionsformeln mit konstanten Koeffizienten p und q

This post has been edited 11 times, last edit by "Bastian" (Jul 15th 2011, 3:32pm)

Go to the top of the page

hamena314

Zerschmetterling

Posts: 2,032

Date of registration: Aug 31st 2003

Location: Hannover

Occupation: Informatikstudent (d'uh)

2

Tuesday, July 12th 2011, 10:25am

Ich glaube es reicht nicht zu sagen dass ein Graph einen Eulerkreis / Hamiltonkreis / etc. hat, sondern man muss diesen auch angeben / markieren, oder?

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

3

Tuesday, July 12th 2011, 10:35am

Bei der Aufgabenstellung halte ich es für ausreichend, die Gültigkeit der jeweils äquivalenten Aussage (zusammenhängend, Vertexgrade gerade bzw. zwei ungerade Vertexgrade) zu zeigen. Sonst würde da vermutlich eher direkt stehen "Geben Sie einen Euler-Kreis/-Weg an!".

Go to the top of the page

Kanubis

Praktikant

Posts: 18

Date of registration: May 2nd 2011

4

Tuesday, July 12th 2011, 1:46pm

Ich stimme Bastian zu, erstens steht in der Aufgabe ist der Graph planar, zweitens handelt es sich um deinen EulerKreis (Start, bzw Endpunkt ist frei wählbar) daher wäre die Angabe witzlos. Zeichnen und dann den Kreis angeben ist auch n bissel doppelt gemoppelt, ich glaub da das Zeichnen ja manchmal nicht hinhaut wollten die nicht so gemein sein =)

Go to the top of the page

Kanubis

Praktikant

Posts: 18

Date of registration: May 2nd 2011

5

Tuesday, July 12th 2011, 1:48pm

Hat jemand Lust morgen am Mittwoch unterm Lichthof die ganzen Übungszettel durchzugehen und ein bisschen zu lernen?
Ich habe volle Punkte in den Testaten, kann bei den Sachen also viel weiterhelfen, habe aber noch ein paar Probleme mit den neueren Sachen.
Wenn jemand Zeit und Lust hat, schreibt mir bitte ne Mail oder SMS oder ins Forum rein(weiß aber nicht ob ich heute noch da rein schaue).
Ich habe heute und Morgen den ganzen Tag Zeit =)

LG

Stephan

Go to the top of the page

Kanubis

Praktikant

Posts: 18

Date of registration: May 2nd 2011

6

Tuesday, July 12th 2011, 1:48pm

Achja hier meine Mail und Handynr

hannvoer@sofatutor.com
01636976167

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

7

Tuesday, July 12th 2011, 2:51pm

Ich mache dann mal weiter...

Klausur SS08

Aufgabe 2
a)

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

$\tau_i^2 =\ \mbox{id}$ gilt für

, denn es ist:

$\tau_1 \circ \tau_1 = \begin{pmatrix}1&2&3&4&5&6\\3&5&1&4&2&6\\1&2&3&4&5&6\end{pmatrix}$

b)

Hat ja Ähnlichkeit mit dem zweiten Teil von a). Bei "Zeigen Sie" fehlt mir allerdings immer die richtige Formulierung, es ist aber so, dass bei einem Zykel von > 3 mehr als eine Komposition nötig ist, damit die Stelle sich wiederholt. Und wie sagt man das jetzt "richtig"?

c)

folgt...

Aufgabe 3
a)

	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

Alle Bäume haben genau 3 Blätter und gehören deswegen alle zu A.

b)

und

sind offensichtlich isomorph. Wie gibt man einen expliziten Isomorphismus an?

c)

Öhm, ja... erinnert mich ein wenig an 2 c)...

Aufgabe 4
a)

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

$\varphi(100) = \varphi (2^2 \cdot 5^2) = 2^{2-1} \cdot (2-1) \cdot 5^{2-1} \cdot (5-1) = 2 \cdot 5 \cdot 4 = 40$

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

Go to the top of the page

Pudge

Trainee

Posts: 84

Date of registration: Oct 13th 2010

Location: Hannover

8

Tuesday, July 12th 2011, 4:24pm

Eine Frage zu 4a) Wintersemester

o-o-o-o-o-o

o
|
o-o-o
| |
o-o

o
|
o-o-o-o
|
o

sind das die drei fehlenden Isomorphitypen, oder liege ich damit falsch, weil soweit ich das
sehe sind die ja nicht isomorph zu den anderen 3.
Achso als kleine Anregung an den Threadersteller, die vermeintlich richtigen Lösungen könntest
du doch vll im ersten Post zusammenfassen, damit man sich die Lösungen nicht zusammensuchen
muss (falls der Thread noch zugespammt wird mit Lösungen).

Edit: hm... die abbildungen verrutschen leider, der erste ist richtig dargestellt, der zweite, da soll der rechts abstehende nach links dran
sodass dort ein 4er ensteht und beim dritten sollen die oben und unten abstehenden einen nach rechts gerückt werden,
damit dort auch ein 4er ensteht, hoffe das war jetz verständlich

Dumm ist, wer dummes tut :sleeping:

This post has been edited 3 times, last edit by "Pudge" (Jul 12th 2011, 4:28pm)

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

9

Tuesday, July 12th 2011, 4:45pm

Quoted from "SammysHP"

Klausur SS08

Aufgabe 2
b)

Hat ja Ähnlichkeit mit dem zweiten Teil von a). Bei "Zeigen Sie" fehlt mir allerdings immer die richtige Formulierung, es ist aber so, dass bei einem Zykel von > 3 mehr als eine Komposition nötig ist, damit die Stelle sich wiederholt. Und wie sagt man das jetzt "richtig"?

In der Übung würde ja nur gesagt, dass es gilt, wenn ich mich jetzt richtig erinnere, aber nicht warum.

Quoted from "SammysHP"

c)

folgt...

Wenn man nun b) bewiesen hat, weiß man, dass nur folgende Zykeltypen in Frage kommen: (2, 2, 2), (2, 2, 1, 1), (2, 1, 1, 1, 1) sowie (1, 1, 1, 1, 1, 1).

Für (2, 2, 2) gibt es (6 über 2) * (4 über 2) * (2 über 2) = 15 * 6 * 1 = 90 mögliche Permutationen.
Für (2, 2, 1, 1) gibt es (6 über 2) * (4 über 2) = 15 * 6 = 90 mögliche Permutationen.
Für (2, 1, 1, 1, 1) gibt es (6 über 2) = 15 mögliche Permutationen.
Für (1, 1, 1, 1, 1, 1) gibt es (6 über 6) = 1 mögliche Permutation.

In der Summe ergeben sich 196 mögliche Permutationen.

Quoted from "SammysHP"

Aufgabe 3
b)

und sind offensichtlich isomorph. Wie gibt man einen expliziten Isomorphismus an?

Z.B. mit einer Permutation, hier also (1 4) (2 6 3) (5).

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

10

Tuesday, July 12th 2011, 4:48pm

Das habe ich bisher gemacht:

Quoted
Sommer 2008:

Aufgabe 1:

"Der eulersche Polyedersatz für planare Graphen":
Knotenzahl + Gebietszahl − Kantenzahl = 2

a)

|G| = 2 - |V| + |E|

|G| = 2 - 8 + (5*3 + 2*5 + 7)/2 = 10

b)

|V| = 9
|E| = (5*4 + 2*6 + 8 + 8 )/2 = 24

Notwendige Bedingung für Planarität: |E| <= 3 * |V| - 6 (Aus Bastians Lösung, woher kommt die, bzw. wie heisst das?)

24 <= 21

Aussage nicht wahr: H ist nicht planar.

Graph muss zusammenhängend sein und er alle Knoten müssen gradgradig sein, damit er eulersch ist.

Der Graph ist zusammenhängen und alle Knoten sind gradgradig: H ist eulersch.

Aufgabe 2:

a)

1. (13)(25)(4)(6)
2. (126)(354)

1. 123456 1.^0
351426 1.^1
123456 1.^2 (id!); Also für i = 1
2. 123456 2.^0
265341 2.^1
614532 2.^2
[123456 2.^3 (id!)]

b)

Bei einer Permutation 2- Zykeln werden nur die Elemente hin- und hergetauscht:
Die erste Permutation führt also dazu das z.B. 1 und 3 vertauscht werden.
Die zweite Permutation führt dann dazu das 3 und 1 wieder zurückgetauscht werden
1- Zykel haben keinen einfluss, die Elemente bleiben an ihrer Position.

Bei n- Zykeln braucht man n Permutatioen um ein Element wieder an seine Ursprungspostion getauscht zu haben.

c)

6 Elemente sollen auf beliebig viele 1- Zykel oder 2- Zykel verteilt werden:

(Lösung von Bastian)

Für (2, 2, 2) gibt es (6 über 2) * (4 über 2) * (2 über 2) = 15 * 6 * 1 = 90 mögliche Permutationen.
Für (2, 2, 1, 1) gibt es (6 über 2) * (4 über 2) = 15 * 6 = 90 mögliche Permutationen.
Für (2, 1, 1, 1, 1) gibt es (6 über 2) = 15 mögliche Permutationen.
Für (1, 1, 1, 1, 1, 1) gibt es (6 über 6) = 1 mögliche Permutation.

Gesamtanzahl der Permutationen: 90+90+15+1 = 196

Aufgabe 3:

a)

Beispiel für T1 (Prüfer-Code: 4542):

123456
4542

1, 3 und 6 kommen nicht im Prüfer-Code vor:

123456
4542

Jetzt für jede Stelle im Prüfer-Code von Links nach Rechts:

123456
4542

Verbindung: 4-1

123456
4542

Verbindung: 5-3
(5 Kommt nicht mehr im Prüfer-Code vor)

123456
4542

Verbindung: 4-5
(4 Kommt nicht mehr im Prüfer-Code vor)

123456
4542

Verbindung: 2-4
(2 Kommt nicht mehr im Prüfer-Code vor)

123456
4542

Prüfer-Code abgearbeitet, die letzten verbleibenden Vertizes verbinden:

Verbindung: 2-6

123456
4542

Fertig

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

T1,T2 und T3 gehören zu A

b)

T1 ist isomorph zu T2
Source code
1
2
3
4
5
6
7
    T1 T2 oder T1 T2
    4  1       4  1
    1  4       1  4
    2  5       2  6
    6  2       6  3
    5  6       5  5
    3  3       3  2
c)

Aufgabe 4:

a)
phi(100)
100=2*2*5*5

100=2^2*5^2

2*2*(1-1/2) = 4-4/2 = 2
5*5*(1-1/5) = 25-25/5 = 20

phi(100) = 2*20 = 40

b)

c)

d)
Source code
1
2
p    2 3 5 7 11 13 17 19 23 29 31 37 41 ...
p-1  1 2 4 6 10 12 16 18 22 28 30 36 40 ...
Teiler von phi(n) = 40:
Source code
1
2
p-1  1 2 4 10 40 
p    2 3 5 11 41
Die erste Zahl für m ist direkt ablesbar weil phi(p) = p - 1 ist, demnach gibt es m = 41
Source code
1
2
3
4
5
6
7
i     phi(2^i) phi(3^i) phi(5^i) phi(11^i)
  
0       1        1        1        1
1       1        2        4       10
2       2        6       20      110
3       4       18
4       8
2 Wege:
Source code
1
2
3
4
5
6
7
        a        b        c        d

phi()   1        1        4       10
i       0        0        1        1

phi()   1        2       20        1
i       0        1        2        0
40 = phi(n) = phi(2^a)*phi(3^b)*phi(5^c)*phi(11^d)

Also:

40 = phi(5*11) = phi(55)
40 = phi(3*25) = phi(75)
40 = phi(41)

Die Zahlen für m sind 55,75 und 41

Aufgabe 5:

a)
b)
c)

Es fehlt aber noch sehr viel und einiges kann auch falsch sein. Mathe ist absolut nicht meine Stärke momentan.

//Edit: Ein bisschen verschönert und aktualisiert

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

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

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

11

Tuesday, July 12th 2011, 4:53pm

Quoted from "Pudge"

Achso als kleine Anregung an den Threadersteller, die vermeintlich richtigen Lösungen könntest
du doch vll im ersten Post zusammenfassen, damit man sich die Lösungen nicht zusammensuchen
muss (falls der Thread noch zugespammt wird mit Lösungen).

Gute Idee, wir können ja noch ein wenig sammeln, und ich würde dann morgen Mittag eine erste Zusammenfassung wagen.

Quoted from "Pudge"

Edit: hm... die abbildungen verrutschen leider, der erste ist richtig dargestellt, der zweite, da soll der rechts abstehende nach links dran
sodass dort ein 4er ensteht und beim dritten sollen die oben und unten abstehenden einen nach rechts gerückt werden,
damit dort auch ein 4er ensteht, hoffe das war jetz verständlich

Du kannst für solche Zwecke das code-Tag des Editors benutzen, das enthaltenen Text in gleicher Dickte darstellt, siehe auch weiter oben im Beitrag von SammysHP.

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

12

Tuesday, July 12th 2011, 5:23pm

Quoted from "Bastian"

Quoted from "Pudge"

Achso als kleine Anregung an den Threadersteller, die vermeintlich richtigen Lösungen könntest
du doch vll im ersten Post zusammenfassen, damit man sich die Lösungen nicht zusammensuchen
muss (falls der Thread noch zugespammt wird mit Lösungen).

Gute Idee, wir können ja noch ein wenig sammeln, und ich würde dann morgen Mittag eine erste Zusammenfassung wagen.

Wenn du willst, schicke ich dir dann mein LaTeX zu, dann brauchst du das nicht nochmal eintippen.

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

13

Tuesday, July 12th 2011, 6:28pm

Quoted from "SammysHP"

Quoted from "Bastian"

Quoted from "Pudge"

Achso als kleine Anregung an den Threadersteller, die vermeintlich richtigen Lösungen könntest
du doch vll im ersten Post zusammenfassen, damit man sich die Lösungen nicht zusammensuchen
muss (falls der Thread noch zugespammt wird mit Lösungen).

Gute Idee, wir können ja noch ein wenig sammeln, und ich würde dann morgen Mittag eine erste Zusammenfassung wagen.

Wenn du willst, schicke ich dir dann mein LaTeX zu, dann brauchst du das nicht nochmal eintippen.

Danke, wird aber nicht notwendig sein: Wenn ich einen Deiner Beiträge kurz zum Zitieren öffne, kann ich den Code direkt daraus kopieren.

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

14

Tuesday, July 12th 2011, 7:05pm

Quoted from "Bastian"

|V| = 8, |E| = 1/2 * Summe der Grade aller Vertizes = 16 => |Gebiete| = 10

Zeichnung eines solchen Graphen: Zuerst v8 in die Mitte von v1 bis v7 zeichnen und mit diesen verbinden. v6 mit v5, v4 und v3 sowie v7 mit v1, v2 und v3 verbinden. Abschließend v6 mit v7, v5 mit v4 und v1 mit v2 verbinden.

Ganz so einfach war es dann doch nicht..
Ich hätte übrigens nur 9 Gebiete gezählt, aber das aussen scheint man auch dazuzählen zu müssen.

Quoted

Aufgabe 1:

a)

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

This post has been edited 3 times, last edit by "vogelj" (Jul 12th 2011, 7:07pm)

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

15

Tuesday, July 12th 2011, 7:17pm

Quoted from "vogelj"

Quoted from "Bastian"

|V| = 8, |E| = 1/2 * Summe der Grade aller Vertizes = 16 => |Gebiete| = 10

Zeichnung eines solchen Graphen: Zuerst v8 in die Mitte von v1 bis v7 zeichnen und mit diesen verbinden. v6 mit v5, v4 und v3 sowie v7 mit v1, v2 und v3 verbinden. Abschließend v6 mit v7, v5 mit v4 und v1 mit v2 verbinden.

Ganz so einfach war es dann doch nicht..
Ich hätte übrigens nur 9 Gebiete gezählt, aber das aussen scheint man auch dazuzählen zu müssen.

Ich hatte halt v8 in den Mittelpunkt eines Kreises aus den anderen Vertizes gesetzt, insgesamt sieht mein gezeichneter Graph etwas "runder" aus und ist symmetrisch.

Das 10. Gebiet ist tatsächlich das äußere.

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

16

Tuesday, July 12th 2011, 7:52pm

Wir haben heute eine allgemeine erzeugende Funktion hergeleitet, die für alle Rekursionsformeln mit konstanten Koeffizienten p und q gilt:

Quoted

$a_{n} = p\cdot a_{n-1} + q\cdot a_{n-2}$

Wird zu:

$a(x) = \frac{a_{0} + (a_{1} - pa_{0}) x}{1 - px - qx^{2}}$

Faktorisierung:

$a(x) = \frac{a_{0} + (a_{1} - pa_{0}) x}{(1 - \alpha x)(1 - \beta x)}$

mit

$\alpha = \frac{p}{2}+\sqrt{\frac{p^{2}}{4} + q}$

$\beta = \frac{p}{2}-\sqrt{\frac{p^{2}}{4} + q}$

Partialbruchzerlegung:

$a(x) = \frac{a_{0} + (a_{1} - pa_{0}) x}{(1 - \alpha x)(1 - \beta x)}$

wird zu

$a(x) = \frac{f}{1-\alpha x} + \frac{g}{1-\beta x}$

mit

$g = \frac{(a_{1}-\frac{p}{2}a_{0})\sqrt{\frac{p^{2}}{4}+q} - a_{0}(\frac{p^{2}}{4}+ q))}{-\frac{p^{2}}{2}-2q}$

$f = a_{0} - g$

ergibt

$\sum_{n=0}^{\infty }(f \cdot \alpha^{n} + g \cdot \beta^{n}) \cdot x^{n}$

$a_{n} = f \cdot \alpha^{n} + g \cdot \beta^{n}$

Oder für drei Koeffizienten:

Quoted

$a_{n} = k_{1}\cdot a_{n-1} + k_{2}\cdot a_{n-2} + k_{3}\cdot a_{n-3}$

Wird zu:

$a(x) = \frac{a_{0} + (a_{1} - k_{1}a_{0})x + (a_{2}-k_{1}a_{1}-k_{2}a_{0})x^{2}}{1 - k_{1}x - k_{2}x^{2}-k_{3}x^{3}}$

This post has been edited 2 times, last edit by "nano" (Jul 12th 2011, 11:33pm)

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

17

Tuesday, July 12th 2011, 11:36pm

Gerade gesehen, dass das Aufgabe von Übungsblatt 12 war. Dort wird auch noch beschrieben, wie man mit doppelten Nullstellen umgehen muss.

Go to the top of the page

vogelj

Yahniggck Pføgæhl

Posts: 107

Date of registration: Oct 11th 2010

Location: Hannover, Nordstadt

18

Wednesday, July 13th 2011, 12:31pm

Ich habe bei mir oben meine Lösung für 4d reineditiert.
Die Spalte a (p=2) kann man sich eigentlich sparen weil sie bei "i ungleich 0" dazu führt das m gerade wird. Aus dem Grund wird i dort immer 0 sein.

Mit dem Rest der Aufgaben habe ich jedoch teilweise Probleme, also von mir kommt glaube ich nichts mehr für die "Sommer 2008" Klausur.

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

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

19

Wednesday, July 13th 2011, 1:12pm

Mache ich mal weiter mit

Aufgabe 4
b)

Damit $\overline{31}$ im Ring $\mathbb{Z}_{100}$ invertierbar ist, müssen 31 und 100 teilerfremd sein. Da 31 eine Primzahl ist und 100 kein Vielfaches von 31, ist dies der Fall. Wir können also mit dem erweiterten Euklidischen Algorithmus das Inverse berechnen:

	Source code
1 2 3 4 5	100 1 0 31 0 1 7 3 1 -3 3 4 -4 13 1 2 9 -29

Damit ist $\overline{-29}$ bzw $\overline{71}$ das Inverse von $\overline{31}$ . (Ist das so richtig? Oder nur das negative oder ist das egal, weil es ja ein Ring ist?)

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

Go to the top of the page

Bastian

Dies, das, einfach so verschiedene Dinge

Posts: 988

Date of registration: Sep 30th 2007

20

Wednesday, July 13th 2011, 2:05pm

Quoted from "vogelj"

Notwendige Bedingung für Planarität: |E| <= 3 * |V| - 6 (Aus Bastians Lösung, woher kommt die, bzw. wie heisst das?)

Satz 2.15 aus der achten Vorlesung, siehe auch siebte Übung.

Quoted from "SammysHP"

Damit ist $\overline{-29}$ bzw $\overline{71}$ das Inverse von $\overline{31}$ . (Ist das so richtig? Oder nur das negative oder ist das egal, weil es ja ein Ring ist?)

a soll nach der Aufgabenstellung aus [100] kommen, also a = 71.

Go to the top of the page

	Source code
1 2 3 4 5 6 7	T1 T2 oder T1 T2 4 1 4 1 1 4 1 4 2 5 2 6 6 2 6 3 5 6 5 5 3 3 3 2