[Diskrete] Fragen zu alten Klausuren

[AfI] Analysis für Informatiker
[Diskrete] Diskrete Strukturen
[LA] Lineare Algebra
[Stocha] Einführung in die angewandte Stochastik
[NumRech] Numerisches Rechnen

Fragen zu alten Klausuren

Beitragvon Mustermann » 18.03.09 20:07

Zuerst zur Schoenwaelder Klausur von 04
http://www.math.rwth-aachen.de/homes/Klausuren/Diskrete_Strukturen/Schoenwaelder_04_vl.pdf
Aufgabe 4)
Wie berechnet man die Abbildungen und Surjektiven Abbildungen?

Aufgabe 5) Die Zykeldarstellung bekomme ich hin, aber bei den anderen Sachen ahb ich kA.



Zu unserer ersten Klausur:
http://www2.math.rwth-aachen.de:8037/klausur-lsg.pdf

Aufgabe 4)
Zu a) In dieser Variante
Bild
hätte ich (178) (24) (38) (5) geschrieben, aber das ist das selbe, oder?

Zu c) und d) Wie geh ich an die beiden Aufgaben ran?

Aufgabe 5c)
Die Aufgabe löst man mit der Eulerschen phie Funktionm so viel weiss ich.
Bei (relativ) kleinen Zahlen komme ich auch schnell auf das Ergebniss, aber bei 246 komm ich ins schwitzen. Ich überlege wie ich die Zahl aufteilen kann, was ich aber bei 246 recht schwer finde.
Gibt es einen Trick wie man leichter darauf kommt?
Mustermann
 
Beiträge: 81
Registriert: 17.02.09 14:09

Re: Fragen zu alten Klausuren

Beitragvon Mighty Max » 18.03.09 20:50

Mustermann hat geschrieben:Zuerst zur Schoenwaelder Klausur von 04
http://www.math.rwth-aachen.de/homes/Klausuren/Diskrete_Strukturen/Schoenwaelder_04_vl.pdf
Aufgabe 4)
Wie berechnet man die Abbildungen und Surjektiven Abbildungen?


Schau dir mal an, was die Stirlingzahlen darstellen. Dann einfach Ausrechnen :-p

Aufgabe 5) Die Zykeldarstellung bekomme ich hin, aber bei den anderen Sachen ahb ich kA.


Ordnung ist kgV der disjunkten Zykellängen, hier kgV(2,6) = 6
Zykeldarstellung der Inversen: In der Aufgabe sind die Zykel disjunkt, du kannst einfach die innere Reihenfolge der Zykel umdrehen, so gehst du eben "den Schritt zurück". Sind die Zykel nicht disjunkt, musst du die Reihenfolge der Zykel untereinander ebenfalls umdrehen (halt alles Rückwärts machen)
Hohe Exponenten der Perutation p^k mit k >= Ordnung(p): Berechne p^(k modulo Ordnung(p)), da p^Ordnung(p) = p
Die Verkettung der nun bekannten t^-1 * p * t wirst du dann wohl hinbekommen.

Zu unserer ersten Klausur:
http://www2.math.rwth-aachen.de:8037/klausur-lsg.pdf

Aufgabe 4)
Zu a) In dieser Variante
Bild
hätte ich (178) (24) (38) (5) geschrieben, aber das ist das selbe, oder?


Sollte wohl 6 sein, Tippfehler? Ja (a,b,c) entspricht (b,c,a) entspricht (c,a,b).

Zu c) und d) Wie geh ich an die beiden Aufgaben ran?

zu c) Du weisst, wie die disjunkten Zykel aussehen (aus a), du erkennst, dass der erste gegeben Zykel aus zwei Teilen besteht, die zu disjunkten Zykel stammen, also musst du die vorher Trennen. Wird mit den Randwerten der disjunkten vorgabe begonnen, muss der andere Zykelanteil übersprunge werden.

Disjunkt: (13)(458) ...
Kombiniert (14583) ... t

Die ... stehen jeweils für weitere disjunkte Teile die uns nicht interessieren, da sie ja bereits korrekt sind.
Damit du mit (14583) von 1 nach 3 kommst muss du vorher von der 1 zur 8. also t = (18) Teste mit 8: 8->1->4.

zu d) Das ist gerade die Definition der Ordnung. Also kgV(disjunkter Zykellängen) also kgV(2,2,3,1) = 6

Aufgabe 5c)
Die Aufgabe löst man mit der Eulerschen phie Funktionm so viel weiss ich.
Bei (relativ) kleinen Zahlen komme ich auch schnell auf das Ergebniss, aber bei 246 komm ich ins schwitzen. Ich überlege wie ich die Zahl aufteilen kann, was ich aber bei 246 recht schwer finde.
Gibt es einen Trick wie man leichter darauf kommt?


Zerlege sie in die Primzahlfaktoren und Exponenten, deren phi kannst du einfach ausrechnen. Also 2^1 * 3^1 * 41^1. Dieses sind Teilerfremd, und so kannst du deren phi multiplizieren und erhälst das für 246.
Mighty Max
 
Beiträge: 15
Registriert: 31.01.07 16:21

Re: Fragen zu alten Klausuren

Beitragvon Mustermann » 19.03.09 13:10

Mighty Max hat geschrieben:Schau dir mal an, was die Stirlingzahlen darstellen. Dann einfach Ausrechnen :-p

Erster Art= Anzahl Permutationen einer n Elemtigen Menge, die genau k-Zyklen haben.
Zweiter Art= Anzahl k-elementige Partitionen, einer n elemetigen Menge.

Würde ich jetzt nicht drauf kommen, wie ich die bei den Aufgaben benutzen sollte

Die Verkettung der nun bekannten t^-1 * p * t wirst du dann wohl hinbekommen.


Wie verkette man Zyklen?^^

zu c) (...) Wird mit den Randwerten der disjunkten vorgabe begonnen, muss der andere Zykelanteil übersprunge werden.

und wenn es nicht so wäre?
Disjunkt: (13)(458) ...
Kombiniert (14583) ... t

Die ... stehen jeweils für weitere disjunkte Teile die uns nicht interessieren, da sie ja bereits korrekt sind.
Damit du mit (14583) von 1 nach 3 kommst muss du vorher von der 1 zur 8. also t = (18) Teste mit 8: 8->1->4.

Sorry versteh ich nicht (wahrscheinlich weil ich nicht weiss, wie man Zyklen verkettet).


Zerlege sie in die Primzahlfaktoren und Exponenten, deren phi kannst du einfach ausrechnen. Also 2^1 * 3^1 * 41^1. Dieses sind Teilerfremd, und so kannst du deren phi multiplizieren und erhälst das für 246.


Bei 276 würde ich dann in: 2*2*3*23 (also 1*1*2*22) Aufteilen, dann komme ich aber auf 44, das Ergebnis ist aber 88. Was hab ich falsch gemacht?
Mustermann
 
Beiträge: 81
Registriert: 17.02.09 14:09

Beitragvon Baha » 19.03.09 17:33

276 = 23 * 12
23 ist Primzahl
12 = 4 * 3
3 ist Primzahl
4 = 2^2 = 2^(2-1) * (2 - 1) = 2
23^(1-1) * (23 - 1) = 22
3 = 3^(1-1) * (3 - 1) = 2

2*2*22 = 88
Baha
 
Beiträge: 10
Registriert: 31.01.09 11:32

Re: Fragen zu alten Klausuren

Beitragvon Mighty Max » 19.03.09 18:21

Mustermann hat geschrieben:
Mighty Max hat geschrieben:Schau dir mal an, was die Stirlingzahlen darstellen. Dann einfach Ausrechnen :-p

Erster Art= Anzahl Permutationen einer n Elemtigen Menge, die genau k-Zyklen haben.
Zweiter Art= Anzahl k-elementige Partitionen, einer n elemetigen Menge.

Würde ich jetzt nicht drauf kommen, wie ich die bei den Aufgaben benutzen sollte


Folien, Seite 26:
Wieviele surjektive Abbildungen n → m gibt es?

Stirlingzahlen 2. Ordnung geben (die Formulierung von Oben einfach mal ein wenig umformen) die Anzahl der Möglichkeiten an, k nichtleere Partitionen aus n zu bilden. Also eben genau jedes Element einer k-mächtigen Menge mindestens einmal von einem Element aus einer n-mächtigen Menge abzubilden (surjektivität)


Die Verkettung der nun bekannten t^-1 * p * t wirst du dann wohl hinbekommen.


Wie verkette man Zyklen?^^


Elemente durchgehen von rechts beginnend die Zykel anwenden.
(Anwenden: Ersetzen eines Elementes mit seinem Nachfolger in dem Zykel, Nachfolger der Letzen ist das erste Element)

zu c) (...) Wird mit den Randwerten der disjunkten vorgabe begonnen, muss der andere Zykelanteil übersprunge werden.

und wenn es nicht so wäre?


Wenn was nicht so wäre?

Disjunkt: (13)(458) ...
Kombiniert (14583) ... t

Die ... stehen jeweils für weitere disjunkte Teile die uns nicht interessieren, da sie ja bereits korrekt sind.
Damit du mit (14583) von 1 nach 3 kommst muss du vorher von der 1 zur 8. also t = (18) Teste mit 8: 8->1->4.

Sorry versteh ich nicht (wahrscheinlich weil ich nicht weiss, wie man Zyklen verkettet).


Dringend nachvollziehen was ein Zykel macht, damit wirds definitiv leichter ;-)
Mighty Max
 
Beiträge: 15
Registriert: 31.01.07 16:21

Re: Fragen zu alten Klausuren

Beitragvon Mustermann » 19.03.09 19:14

Mighty Max hat geschrieben:Folien, Seite 26:
Wieviele surjektive Abbildungen n → m gibt es?

Stirlingzahlen 2. Ordnung geben (die Formulierung von Oben einfach mal ein wenig umformen) die Anzahl der Möglichkeiten an, k nichtleere Partitionen aus n zu bilden. Also eben genau jedes Element einer k-mächtigen Menge mindestens einmal von einem Element aus einer n-mächtigen Menge abzubilden (surjektivität)

Okay :D

Elemente durchgehen von rechts beginnend die Zykel anwenden.
(Anwenden: Ersetzen eines Elementes mit seinem Nachfolger in dem Zykel, Nachfolger der Letzen ist das erste Element)

Habs mir ein bisschen anders aufgeschrieben dann ging es.


Wenn was nicht so wäre?

Vergiss es ^^


(...)
Dringend nachvollziehen was ein Zykel macht, damit wirds definitiv leichter ;-)

Okay ich kann es.




Bedanke ich mich bei dir, hast alle meine Fragen beantwortet :D
Mustermann
 
Beiträge: 81
Registriert: 17.02.09 14:09


Zurück zu Mathematik