Hallo! Hier ist eine Auswahl der (meiner bescheidenen Meinung nach) wichtigsten Aufgaben aller DS-Klausuren seit 1998. Die Nummerierung der Themen entspricht der des DS Trainers und für die Auflistung der Aufgaben habe ich das Format Klausur Aufgabe (Teilaufgabe(n)) gewählt. Neben jeder Aufgabe ist eine ganz kurze Zusammenfassung von dem Inhalt der Aufgabe. Über Mails mit Fragen, Vorschlägen und Fehlermeldungen freue ich mich immer! Einfach eine E-Mail an cfcamino@gmail.com schicken. Viel Spaß beim Üben und viel Erfolg! Carlos WICHTIG: - Zu den Themen DPLL-Algorithmus, Resolution und RSA-Verfahren gibt es kaum Klausuraufgaben, weil diese erst seit dem Wintersemester 2013/14 Teil der DS-Vorlesung sind. - Lasst euch nicht von komischen Schreibweisen verwirren! Die Notationen sind nicht jedes Jahr gleich (z.B. → und ⇒ für Implikationen oder {x|P(x)} und {x;P(x)} für Mengen). Wenn ihr euch nicht sicher seid was etwas heißt, schreibt mir gerne eine kurze E-Mail oder fragt in der Facebook-Gruppe nach. - Informiert euch darüber, welche Themen dieses Jahr nicht klausurrelevant sind. Es werden immer welche ausgeschlossen! ================================================================================================================================================= 2. Grundlagen ================================================================================================================================================= ------------------------------------------------------------------------------------------------------------------------------------------------- 2.1. Mengen ------------------------------------------------------------------------------------------------------------------------------------------------- 2.1.1. Wichtige Begriffe Mengengleichungen 2010-wdh 2 (1) Beweisen: (P ∪ Q) ∩ (Q ∪ R) ∩ (R ∪ P) = (P ∩ Q) ∪ (Q ∩ R) ∪ (R ∩ P) 2010-wdh 2 (2) Gilt (P ∪ Q) ∩ (Q ∪ R) = (P ∩ Q) ∪ (Q ∩ R)? 2011-end-2 2 (2) Beweisen: (A\B) ∪ (B\C) ∪ (C\A) = (A ∪ B ∪ C)\(A ∩ B ∩ C). 2012-mid 2 (1) Widerlegen: (A\B)\C = A\(B\C). 2012-mid 2 (2) Beweisen: (A\B)\C = A\(B ∪ C). 2012-wdh 2 (1) Beweisen: (A Δ B) Δ B = A. 2012-wdh 2 (2) Widerlegen: (A Δ B) Δ C̅ = A̅ Δ (B Δ C). Sonstige Aufgaben 2005-wdh 1 (1) ges.: Anzahl Teilmengen von A, die B enthalen. 2006-wdh-1 1 (b) Gilt A ∉ P(A)? 2007-mid 1 (1) Gilt |P(∅)| = 0? 2007-mid 2 (a) ges.: Anzahl Partitionen mit 4 Elementen. 2014-end 1 (1) Gilt |P(A)| = 8 für A = {∅,{1,x},{x,x},{x}}? 2014-wdh 1 (1) Gilt |P({{∅} ∩ P(∅)})| = 4? 2.1.2. Tupel und Wörter 2006-mid 1 (h) Gilt P(A) = A x A für eine zweielementige Menge A? 2.1.3. Mathematische Aussagen ------------------------------------------------------------------------------------------------------------------------------------------------- 2.2. Relationen und Abbildungen ------------------------------------------------------------------------------------------------------------------------------------------------- 2.2.1. Wichtige Begriffe 2007-wdh 1 (3) Gibt es eine Relation mit ∀x,y∊M: (x,y)∊R ⇒ (x,y)∉R? 2.2.2. Erkennen von Eigenschaften 2000-mid 4 Eigenschaften von (x,y)∊R ⇔ |x|≤|y|? Info: "linear" heißt hier "total". 2004-wdh 1 (e) Gibt es eine Relation, die symmetrisch und transitiv, aber nicht reflexiv ist? 2005-mid 1 (2) Anzahl nicht-transitiver Relationen über [2]? 2009-mid 1 (1) Ist jede reflexive Relation über {a,b} transitiv? 2011-end-2 2 (3) Ist jede totale Relation transitiv? 2.2.3. Beweisen von Eigenschaften 2.2.4. Relationenprodukt 2008-mid 1 (1) Gilt S∘T = T∘S falls S,T reflexiv? 2008-mid 1 (2) R⁺ sym. ⇒ R sym.? 2008-wdh 1 (6) R antisymmetrisch und reflexiv ⇒ R⁺ partielle Ordnung? 2009-mid 1 (2) |S∘S| = |S|²? 2010-wdh 1 (2) R = {(1,2),(2,3),(3,1)} ⇒ R∘R transitiv? 2011-wdh 4 Benachbarte Gitterpunkte. 2.2.5. Äquivalenzrelationen 2005-wdh 1 (4) Anzahl an Relationen über [3], die reflexiv, symmetrisch und transitiv sind? 2014-wdh 1 (3) Gibt es eine antisymmetrische Äquivalenzrelation über ℕ? 2.2.6. Partielle Ordnungen 2006-mid 1 (i) Ist ⊆ eine totale Ordnung? 2007-wdh 1 (4) Mehr Äquivalenzrelationen oder totale Ordnungen über [3]? 2011-end-1 2 (2) Ist R ∪ (R∘R) für R über [5] transitiv? Was ist das Hasse-Diagramm zu R*? 2.2.7. Zählen von Relationen 2008-wdh 1 (3) Wie viele Relationen gibt es über einer 2-elementigen Menge? 2009-wdh 1 (1) Wie viele reflexive Relationen gibt es über einer 3-elementigen Menge? 2013-end 6 (a) Wie viele reflexive Relationen gibt es über [10]? 2013-end 6 (b) Wie viele antisymmetrische Relationen gibt es über [10]? 2013-wdh 6 (a) Wie viele symmetrische Relationen gibt es über [10]? 2013-wdh 5 (b) Wie viele asymmetrische Relationen gibt es über [10]? 2.2.8. Abbildungen 2000-mid 2 6 Aussagen über injektive, surjektive und bijektive Funktionen über endliche und unendliche Mengen. 2006-wdh-1 1 (d) Gibt es gleich viele injektive wie surjektive Funktionen? 2009-wdh 1 (2) g surjektiv und f nicht surjektiv ⇒ f∘g nicht surjektiv? 2015-wdh 7 Zeige (a) B^∅ = {∅} und (b) ∅^A = ∅, wenn A ≠ ∅. ------------------------------------------------------------------------------------------------------------------------------------------------- 2.3. Aussagenlogik I ------------------------------------------------------------------------------------------------------------------------------------------------- 2.3.1. Wichtige Begriffe Wahrheitstafeln 2005-mid 2 (1,2) (A → B) → C ≡ A → (B → C) 2008-mid 1 (3) Anzahl der minimalen, erfüllenden Belegungen von (x ∧ y) ∨ (x ∧ ¬z) 2008-mid 2 (1) Ist ((a → (a ∧ b) ∧ ((a ∨ b) → a)) → (a ↔ b) Tautologie? 2013-wdh 1 (a) Wahrheitstafel zu einer komplizierten Formel 2014-end 7 (1a) Wahrheitstafel zu ¬(q ∨ r) → ¬((q → p) ∨ (p → r)). 2015-wdh 1 (a,b) Syntaxbaum und Wahrheitstafel zu (((p ∨ q) ∧ ¬(q → r)) ∧ (p ∨ ¬(s ⊕ ¬q))). 2015-end 2 (a,b,c) Syntaxbaum, Wahrheitstafel und KV-Diagramm zu (((p → q) ∧ ¬(q ↔ r)) ∨ ¬(¬p ∨ ¬¬q)). Sonstiges 2008-wdh 1 (9) ¬F erfüllbar ⇒ F Widerspruch? 2009-mid 2 Junktoren ⊙ mit x ⊙ false ≡ false. 2010-mid 1 (2) F und ¬F erfüllbar ⇒ F ∧ ¬F erfüllbar? 2012-mid 1 (6) F erfüllbar ⇒ ¬F nicht erfüllbar? 2015-wdh 2 ITE und x²y mod 4 = z 2.3.2. Logische Äquivalenz 2006-mid 3 (b) Ist ((p ∨ q) ∧ (¬p ∨ r) ∧ (s ∨ ¬s)) → (q ∨ r) eine Tautologie. 2006-wdh-1 8 (a) z.z.: (A ↔ ¬B) ∧ ¬(B ∨ A) ≡ false. 2006-wdh-1 8 (b) z.z.: Die gegebene Formel ist äquivalent zu einer ihrer Variablen. 2008-mid 2 (2) z.z.: x ∨ ¬(y ∨ ¬x) ≡ x. 2008-end 2 Formeln G (gültig), E (erfüllbar) und U (unerfüllbar). 2009-end 2 (1,2) Formel nur mit ¬ und ∨ bzw. nur mit → darstellen. ------------------------------------------------------------------------------------------------------------------------------------------------- 2.4. Aussagenlogik II ------------------------------------------------------------------------------------------------------------------------------------------------- 2.4.1. DNF und KNF 2010-wdh 2 (3) DNF zu (p ∨ q) ∧ (¬q ∨ r), aber minimal. 2011-end-1 2 (1) Von DNF zu KNF. 2011-end-2 2 (1) KNF zu a → (¬b ∨ ¬c). 2012-mid 2 (3) DNF zu a ∧ ¬(b ∧ ¬c). 2013-wdh 1 (b) KNF zu einer komplizierten Formel. 2014-end 7 (1b) KNF zu ¬(q ∨ r) → ¬((q → p) ∨ (p → r)). 2014-wdh 2 (1b) DNF zu (p → (r → q)) ↔ ((p → q) → r). 2015-wdh 1 (c,d) DNF und KNF zu (((p ∨ q) ∧ ¬(q → r)) ∧ (p ∨ ¬(s ⊕ ¬q))), aber minimal. 2015-end 2 (d) KNF zu (((p → q) ∧ ¬(q ↔ r)) ∨ ¬(¬p ∨ ¬¬q)). 2.4.2. DPLL-Algorithmus 2014-wdh 2 (1a) (p → (r → q)) ↔ ((p → q) → r) ohne KNF. 2.4.3. Resolution 2013-end 1 z.z.: Formel in DNF ist gültig. 2013-wdh 2 Klauseln einer gegeben Resolution bestimmen. 2.4.4. Logische Inferenz 2008-mid 1 (5) Gilt ¬(F ∨ G) ⊢ (¬F ∧ ¬G)? (Achtung, kein Kalkülbeweis nötig. S. Folie 462!) 2014-wdh 1 (4) Ist ¬B → ¬A eine Tautologie, falls A ⊢ B gilt? ------------------------------------------------------------------------------------------------------------------------------------------------- 2.5. Prädikatenlogik ------------------------------------------------------------------------------------------------------------------------------------------------- 2.5.1. Wichtige Begriffe der Prädikatenlogik 2008-mid 4 (2) Unäre Prädikate P und Q. 2008-wdh 1 (4) Ist Ex(P(x)) gültig? 2008-wdh 3 Minimales Modell für F = ∀x∃xR(x,y) ∧ ∀x∀y(¬R(x,y) ∨ ¬R(y,x)) 2009-mid 3 Formel mit |U_S| = 3 und Prädikaten Kgl und Maximum. 2009-wdh 3 (2) Binäres Prädikat P. 2014-end 7 (2) Binäres Prädikat P. 2015-end 4 ∀x∃y∀z(P(x,f(z)) → ¬P(y,f(y))) 2.5.2. Logische Äquivalenz und Inferenz 2006-mid 3 (a) ∀x∃y(P(x,y) → Q(x,y)) negieren. 2008-mid 4 (1) z.z.: Wenn ∃x(G → H) gültig, dann ist ∀x(G ∧ ¬H) unerfüllbar. 2009-mid 1 (3) Ist ∀x∃yP(x,y) ∧ ∃u∀v¬P(u,v) erfüllbar? 2009-wdh 3 (1) Sehr Komplizierte Formel negieren. 2012-wdh 1 (1) Ist ∃x¬∃yP(x,y) ∧ ∀u∃vP(u,v) erfüllbar? 2013-end 2 Äquivalenz von zwei komplizierten Formeln. 2014-end 1 (4) Ist ∃x∀yQ(x,y) ∧ ∀x∃y¬Q(x,y) erfüllbar? ------------------------------------------------------------------------------------------------------------------------------------------------- 2.6. Beweismethoden ------------------------------------------------------------------------------------------------------------------------------------------------- 2.6.1. Beweisen von Implikationen 2.6.2. Vollständige Induktion Summen 2006-mid 2 z.z.: ∑_(i=0 bis n) q^i = (q^(n+1)-1)/(q-1). 2007-mid 4 z.z.: ∑_(i=0 bis n-1) (i⁰+i¹+i²) = n(n²+2)/3. 2011-end-1 4 (1) z.z.: ∑_(i=0 bis n-1) z^2i = (z^2n-1)/(z²-1). Rekursionsgleichungen 2004-mid 0 (b) Finde den Fehler. 2012-mid 4 (1) Rekursion von Grad 2. 2015-end 5 Rekursion von Grad 2. 2015-wdh 3 Rekursion von Grad 3. ------------------------------------------------------------------------------------------------------------------------------------------------- 2.7. Wachstum von Funktionen ------------------------------------------------------------------------------------------------------------------------------------------------- 2.7.1. Wichtige Begriffe der O-Notation 2000-mid 3 (e) f∊O(g) ⇒ f∊o(g) 2000-mid 3 (f) f∊ω(g) ⇒ g∊o(f) 2003-wdh 1 (a,b,c) 3 verschiedene Beziehungen 2008-wdh 1 (2) Gilt stets |f|∊O(|g|) oder |g|∊O(|f|)? 2.7.2. Beweisrezepte 2000-mid 3 (c) 1 + sin n∊O(1) 2007-mid 5 n(n²+5) ∉ ω(n³) 2.7.3. Rechenregeln Rechenregeln erkennen bzw. widerlegen 2000-mid 3 (g) Limes-Regel nachschauen. 2000-mid 3 (h) Gilt f(n)+g(n)∊O(f(n)g(n))? 2000-wdh M2 (c) Gilt ∑_(i=1 bis n) f(i) in O(f(n))? 2000-wdh M2 (d) Gilt kf(n)∊Ω(f(n)) 2003-wdh 1 (d-j) Von allem ein bisschen. 2004-end 1 (b) Gilt log_3 n∊ω(n)? 2004-end 1 (c) Gilt n^(3/2)∊o(n)? 2004-wdh 1 (c) Stirling-Formel für Stirling-Zahlen? 2004-wdh 6 (c) In welcher Beziehung stehen 3^n und 2^n? 2012-wdh 1 (2) Gilt √n∊Ω(ln(n^(ln n)))? Mit Limes Rechnen 2000-mid 3 (a) Gilt 2n²+lnn∊O(n²lnlnn)? 2000-mid 3 (d) Gilt e^(n²+n)∊O(e^n²)? 2000-wdh M2 (b) Gilt n²+n∊ω(n²)? 2006-wdh-1 7 (b) Gilt e^(3ln n)∊o(n³)? 2006-wdh-1 7 (c) Gilt 3^n+2^n+π²n⁵∊O(5^n)? 2008-mid 1 (6) Gilt √(2n)∊O(n)? 2009-mid 1 (4) Gilt 2*3^n∊O(3*2^n)? 2012-mid 4 (2) Gilt 2^(n+2) - 2*3^n∊O(e^n)? 2012-end 1 (3) Gilt 3^n∊Ω(e^(n ln n))? 2014-end 1 (2) Gilt e^(n ln n)∊O(2^(2n))? Mengenbeziehungen erkennen 2004-wdh 1 (a) Gibt es ein f mit f∊ω(log n) und f∊o(log n)? 2004-wdh 1 (b) Gibt es ein f mit f∊Ω(n log n) und f∊O(log n)? 2005-mid 7 (1) O(n²) = O(n³)? 2006-wdh-1 1 (c) θ(n²) ⊆ O(n³)? 2007-wdh 1 (2) o(n²) ⊆ O(n)? 2010-mid 1 (1) Gibt es ein f mit n∊o(f) und f∊o(n²)? ================================================================================================================================================= 3. Kombinatorik ================================================================================================================================================= ------------------------------------------------------------------------------------------------------------------------------------------------- 3.1. Ziehen von Elementen aus einer Menge ------------------------------------------------------------------------------------------------------------------------------------------------- 1999-mid-1 5 Jury zusammenstellen. 2003-mid-1 5 (a) Lotto: 4 aus 8. 2003-wdh 5 (c) 6 aus 49 vs. 7 aus 49. 2004-mid 5 (a) Anzahl Geraden aus 15 Punkten? 2006-wdh-1 9 (a) Aussage mit fallender Faktorielle. 2012-wdh 7 (1) Induktion mit steigender Faktorielle. ------------------------------------------------------------------------------------------------------------------------------------------------- 3.2. Kombinatorische Beweisprinzipien ------------------------------------------------------------------------------------------------------------------------------------------------- Produktregel 2001-mid 4 (a) Reihenfolgen Karten 2 As, 2 Bs und 2 Cs? 2002-mid 1 Anagramme von MIDTERMTEST? 2003-end 5 (c) Minister und Resorts. 2004-wdh 4 (c) Wörter mit genau 3 a's, 2 b's und 1 c? 2009-wdh 6 (3) Wörter mit genau 1 a, 2 b's und 3 x's? 2010-wdh 6 (1) Wörter mit genau 3 a's, 3 bs und 3 c's? 2014-wdh 3 (2) Anzahl der Teiler von 10⁴. 2015-end 1 HTPGs Summenregel 2000-mid 14 Wörter der Länge 5 über {a,b,c} mit |a| = |b| 2007-mid 2 (c) Wörter über {a,b,c} der Länge 4 mit jedem Zeichen höchstens 2 mal? 2009-wdh 6 (1) Wörter über {a,b} mit |a| < 2 und |b| < 3 (Fehler in der Musterlösung: 9 statt 11) Prinzip des doppelten Abzählens 2008-end 5 (1b) 3 Kanten pro Gebiet. z.z.: 2|E| ≥ 3|R|. Prinzip von Inklusion und Exklusion ("Siebformel") 2006-mid 6 C, Java, OCaml mit Abschätzung. 2006-wdh-1 5 (b) Permutationen ohne ungeraden Fixpunkten. 2009-mid 5 (2) Zugführer. 2009-wdh 7 Fehlerhafte Pakete. 2014-end 6 (1) Anzahl der ungeraden Zahlen aus [990], die weder durch 9, noch durch 11 und auch nicht durch 15 teilbar sind. 2014-end 6 (2) Anzahl der Wörter über {a,b,c} der Länge k, bei denen nicht alle 3 Zeichen vorkommen. 2014-wdh 6 (1) Anzahl der Zahlen aus [1000], die von 2 und 5, 9 und 12 oder 6 und 8 geteilt werden. Schubfachprinzip 1999-mid-2 3 11 Spieler mit Geburtstag am selben Monat 1999-wdh-2 3 Europameisterschaft 2000-mid 6 (a) 261 Würfe auf Dartscheibe mit 20 Sektoren 2006-mid 4 (a) 3 Mitbewohner Hannover mit selben Initialien und Geburtstag 2014-wdh 3 (1) z.z.: f: [10⁴] → [10] surjektiv oder es gibt eine Menge A mit |A|>10³ und ∀x,y∊A: f(x) = f(y). ------------------------------------------------------------------------------------------------------------------------------------------------- 3.3. Fundamentale Zählkoeffizienten ------------------------------------------------------------------------------------------------------------------------------------------------- 3.3.1 Binomialkoeffizienten 1999-mid-3 2 Koeffizient von a⁴b¹²c² in (a²+b³+c)⁸? 2000-wdh 3 Gleichung mit Vandermondscher Identität beweisen. 2003-mid-1 5 (b) (15 über 10) = (15 über 5)? 2003-wdh 5 (b) Koeffizient von a³b⁴c² in (a+b+c)⁹? 2007-mid 1 (5) (n über k) = (n über (n-k))? 2009-end 5 (1) Gleichung mit Binomischer Formel beweisen. 2011-wdh 3 (1) Induktionsbeweis. 2014-end 2 Induktionsbeweis und Beweis mit der binomischen Formel. 3.3.2 Stirling-Zahlen erster Art 2000-end M2 4 Rechenregeln überprüfen 2009-wdh 1 (4) 1 Rechenregel überprüfen 2014-end 5 (3) Anzahl Permutationen mit 1 Fixpunkt und 2 Zyklen? 3.3.3 Stirling-Zahlen zweiter Art 2000-end M6 Anzahl Äquivalenzrelationen von n Elementen mit k Klassen? 2003-wdh 5 (a) Anzahl Partitionen von 11 Elementen in 2 Klassen? 2008-mid 5 (4) Induktionsbeweis von S_n,3 ≥ (n über 3). 2010-end 1 (3) Gilt S_n,k ≤ s_n,k? 2012-end 1 (5) Gilt S_n,k < s_n,k, falls 2k < n? 2014-end 5 (4) z.z.: S_n,k ≤ n!. 3.3.4 Zahlpartitionen 3.3.5 Sonstige Zählkoeffizienten ------------------------------------------------------------------------------------------------------------------------------------------------- 3.4. Bälle und Urnen ------------------------------------------------------------------------------------------------------------------------------------------------- 3.4.1. Goldene Tabelle Abbildungen bzw. Funktionen 1999-mid-1 1 Permutationen. 1999-mid-2 1 Permutationen. 1999-mid-3 1 Permutationen. 1998-end 1 Surj. Abbildungen. 1999-mid-4 1 Inj. Abbildungen. 1999-pro 1 Bij. Abbildungen. 2003-mid-1 5 (d) Inj. Abbildungen. 2004-mid 5 (c) Inj. Abbildungen. 2004-end 1 (d,e) Surj. und inj. Abbildungen. 2004-wdh 4 (a) Surj. Abbildungen. 2005-wdh 1 (2) Surj. Abbildungen. 2006-mid 7 (a) Gilt für f: X → X, X endlich: f surj. ⇒ f bij.? 2006-wdh-1 5 (a) Surj. Abbildungen. 2008-mid 5 (2) Surj. Abbildungen. 2014-wdh 6 (2) Surj. Abbildungen. Direkt 1998-pro 5 3 Aufgaben zu Wörtern. 1999-mid-3 4 Murmeln auf Kinder. 1999-mid-3 5 Brute-force-Algorithmus. 1999-mid-4 4 Würfel. 1999-pro 4 Brute-force-Algorithmus 2000-mid 5 Trikots auf Basketballspielerinnen. 2000-mid 16 n = x_1 + ... + x_k. 2001-wdh 4 3 Aufgaben zu Würfeln. 2002-mid 6 (c) Zimtsterne und Teller. 2002-wdh 1 (a) Codes der Länge 10. 2003-mid-1 5 (c) Goldstücke und Erben. 2003-end 5 (a,b) Minister und Resorts. 2003-wdh 5 (d,e,f) Studenten und Flaschen. 2004-mid 5 (d) Chemiker und Experimente. 2004-end 3 (b) Bälle auf Urnen. 2005-end 1 (1) Gegenstände und Schachteln. 2005-wdh 1 (3) Fußbälle und Vereine. 2007-wdh 2 (1) Münzen und Beutel. 2010-end 3 (a,c) Gewinne und Personen. 2012-wdh 8 (3) Kupfer- und Silber-Münzen. 2015-end 6 (a,b,c) Wörter. 2015-wdh 5 (b) Scheiben und Türme. Gemischte Bälle und unterscheidbare Urnen 1999-pro 2 Präsidium wählen. Tipp: verteile 1xV, 1xS und 8xM injektiv auf n Personen. 2001-end 4 Farbige Bauklötze und Kisten. 2002-end 4 (a) 10 studenten in fünf 2er-Gruppen. 2008-wdh 5 Vier 3er-Mannschaften. 2011-end-1 7 Rote, blaue und gelbe Bälle. 2012-end 6 (1,3) Äpfel und Birnen. 2012-wdh 8 (1,2) Kupfer- und Silber-Münzen. 2014-wdh 3 ges.: Anzahl k-Partitionen von [10] mit gleich großen Klassen für (a) k=2 und (b) k=5. Sonstige Aufgaben mit Produktregel 1998-pro 1 52 Karten anordnen. 1999-mid-1 2 5 weiße und n-5 schwarze Türme. 2001-mid 4 (b) Karten A, B, C mit "X". 2002-wdh 1 (b) Code über {0,...,9} der Länge 8 mit |3| = 5. 2004-mid 5 (b) 12 Aufgaben lösen, zuerst 4, dann 8. 2010-wdh 6 (2,3) Bälle auf Boxen mit 2 leeren Boxen. 2011-wdh 7 Wörter über A = {a,b} und X = {x,y}. Sonstige Aufgaben mit Summenregel 2007-mid 2 (b) ges.: Anzahl Permutationen über [5] mit mindestens 2 Fixpunkten. 2009-mid 5 (1) Züge mit Waggons. 2010-end 3 (2) Spieler und Gewinne. 2013-end 5 Noten und Studenten. 2014-wdh 6 (2) Münzen und Boxen. 2015-wdh 5 (a) Wurzelbäume mit höchstens Höhe 3 und n+1 Knoten. Urnen mit Kapazitäten (Negative Bälle bzw. Antibälle) 2002-wdh 2 (a) Studenten und Busse. 2006-mid 10 2n+1 Bälle auf 3 Boxen. 2008-end 3 Personen und Arbeitstunden. 3.4.2. Leere Urnen und Zwischenräume 2003-end 5 (d) Minister und Autos. 2008-mid 3 Parkplätze und große Autos. 2009-mid 4 "4 aus 25" ohne benachbarte Zahlen. 2009-wdh 6 (2) 2xa und 9xb und 2 as zwischen den bs. 2011-end-2 3 Personen im Theater. ================================================================================================================================================= 4. Graphentheorie ================================================================================================================================================= ------------------------------------------------------------------------------------------------------------------------------------------------- 4.1. Grundlagen Graphen ------------------------------------------------------------------------------------------------------------------------------------------------- 4.1.1. Wichtige Begriffe Handshaking-Theorem 1999-mid-2 5 Gibt es einen Graph mit 151 Knoten und nur Knotengrade 3,5 und 7? 1999-mid-4 6 Gibt es einen 3-regulären Graph mit 21 Knoten? 2000-end M4 (g) Gibt es einen 3-regulären Graph mit 5 Knoten? 2000-wdh M8 (f) Gibt es einen 4-regulären Graph mit 7 Knoten? 2003-wdh 4 (a) Gibt es einen Graph mit ungerader Anzahl an Knoten mit geradem Grad. 2008-end 5 (1a) z.z.: 4-regulär ⇒ |E| = 2|V|. 2014-end 4 (1) ges.: Anazhl Kanten eines k-regulären Graphen. 2014-wdh 5 (1) z.z.: |V| > 2|E| ⇒ ∃v∊V: deg(v) = 0. Satz von Havel-Hakimi 2004-end 3 (a) Gibt es einen Graph mit Gradfolge (5,2,2,2,2,2)? 2004-end 4 (b) Gibt es einen Graph mit Gradfolge (1,1,2,3,4)? 2007-end 1 (2) Gibt es einen Graph mit Gradfolge (2,2,3,3,3)? 2010-end 1 (5) Gibt es einen Graph mit Gradfolge (3,3,3,2,2,1)? 2013-end 9 (a) Gibt es einen Graph mit Gradfolge (1,2,3,4,4,5)? 2013-end 9 (b) Gibt es einen Graph mit Gradfolge (2,2,3,5,5,5)? 2013-wdh 7 (b) Gibt es einen Graph mit Gradfolge (2,2,2,3,3)? 2015-end 7 Konstruiere einen Graph mit Gradfolge (1,2,2,2,3,4,4). Sonstige Aufgaben: 1999-mid-3 8 Gilt G = (A,B,E) bipartit und k-regulär ⇒ |A| = |B|? 1999-wdh2 6 (a) z.z.: G = (A,B,E) bipartit und k-regulär ⇒ |A| = |B|. 2000-end M4 (a) Gilt immer |V| ≤ |E|? 2000-wdh M8 (e) Definition Spannbaum erkennen. 2000-wdh 1 Party mit n Personen. Haben zwei gleich viele Bekannte? 2001-mid 5 (a) ges.: Anzahl Graphen über 4 Knoten. 2001-mid 5 (b) Siebformel mit Spezialfall. 2002-end 1 (a) Können zwei Knoten gleichen Grad haben? 2002-mid 2 (a) ges.: Maximale Anzahl an Kanten, falls n Knoten und Graph bipartit. 2002-mid 3 (d) Ist jeder Graph mit Gradfolge (2,2,3,4,4,4,5) zusamenhängend? 2002-wdh 6 (c) Sind Graphen mit identischer Gradfolge isomorph? 2004-end 4 (b) Enthält jeder k-reguläre Graph (k≥2) einen Kreis? 2008-end 1 (4) Gibt es einen zusammenhängenden Graph mit |V|=|E|+2? 2008-wdh 1 (8) Sind alle Graphen mit Gradfolge (2,2,2,2,2,2) isomorph? 2010-end 1 (4) Gibt es einen 2-regulären Graph mit einem echten 2-regulären Teilgraphen? 2010-wdh 1 (6) Sind alle Graphen mit Gradfolge (3,3,3,1,1,1) isomorph? 2011-wdh 1 (3) Gibt es einen bipartiten Graphen mit Gradfolge (3,3,2,2,2,2)? 2012-end 1 (1) Gibt es einen nicht-kreisfreien Graph mit |E|=|V|-2? 2013-wdh 7 (a) Ist jeder Graph mit Gradfolge (1,3,3,4,4,5) zusamenhängend? 2014-end 4 (2) G = (A,B,E) bipartit und k-regulär ⇒ |A| = |B|? 2015-wdh 4 (a) Ist jeder Graph mit Gradfolge (1,1,2,2,2,2,3,3) zusamenhängend? 2015-wdh 4 (b) Sind alle Graphen mit Gradfolge (4,4,4,4,4) isomorph zueinander? 4.1.2. Wichtige Klassen von Graphen 1999-mid-4 2 ges.: Anzahl Kanten von Q_8. 2000-end M4 (b) Hat K_6 genau 15 Kanten? 2000-end M4 (c) Hat K_5,4 einen Kreis der Länge 7? 2000-end M4 (e) Ist die Summe der Knotengrade im K_17,25 ist gerade? 2000-end M4 (f) Enthält der K_10 einen 4-regulären Induzierten Teilgraphen? 2000-wdh M8 (a) Ist jeder bipartite Graph mit n Knoten ein Teilgraph des K_n,n? 2000-wdh M8 (c) Enthält der K_8 einen Kreis der Länge 4 als induzierten Teilgraphen? 2007-mid 1 (6) Kann ein bipartiter Graph einen vollst. Teilgraphen enthalten? (Klar, K_1 ist immer Teilgraph!) 2011-end-1 9 (1) z.z.: K_3 Teilgraph von G ⇒ G nicht bipartit 2014-end 1 (3) Hat K_100 4950 Kanten? 4.1.3. Sonstige Arten von Graphen ------------------------------------------------------------------------------------------------------------------------------------------------- 4.2. Bäume ------------------------------------------------------------------------------------------------------------------------------------------------- 4.2.1. Wichtige Begriffe 1998-end 5 z.z.: Jeder Graph mit genau k Komponenten erfüllt die Ungleichung |E|-|V|+k ≥ 0. 1998-pro 9 G Baun ⇔ min_(v∊V) deg(v) ≥ 1 und ∑_(v∊V) deg(v) = 2(|V|-1)? 1999-mid-4 5 ges.: Anzahl Bäume mit 14 Knoten. 2000-end M4 (h) Kreisfrei ⇒ bipartit? (Achtung, nicht immer. Nur falls |V|≥2!) 2002-mid 3 (b) Gibt es Bäume mit Gradfolge (2,2,3,4,4,4,5)? 2002-wdh 6 (a) Ist ∑_(v∊V) deg(v) in einem Baum kleiner als 2|V|? 2004-end 3 (c) Ist jeder Graph mit m Kanten und m+1 Knoten ein Baum? 2004-end 3 (d) Enthält ein Wald mit 9 Knoten und 6 Kanten 3 Bäume? 2004-wdh 3 (e) Ist jeder Baum bipartit? (Achtung, nicht immer. Nur falls |V|≥2!) 2003-wdh 4 (c) Ist jeder zusammenhängende Graph ein Baum? 2005-wdh 8 (1a) ges.: Anzahl Spannbäume von K_8. 2007-end 1 (1) ges.: Kanten eines kreisfreien Graphen mit n Knoten und 3 Zusammenhangskomponenten. 2011-end-1 9 (2) ges.: Spannbaum von K_3,5. 2013-end 8 ges.: der Wurzelbäume und Wurzelwälder mit n Knoten. 2013-end 9 (c) Gibt es einen Baum mit Gradfolge (1,2,3,4,4,5)? 2013-end 9 (d) Ist jeder Graph mit Gradfolge (1,1,2,2,2,2) ein Baum? 2013-wdh 7 (c) Ist jeder Graph mit Gradfolge (1,1,2,2,2) ein Baum? 2014-end 4 (3) z.z.: Jeder k-reguläre Graph mit k ≥ 3 hat einen Kreis. 2014-wdh 5 (3) z.z.: G zshg. und |V| = |E| ⇒ G enthält genau einen Teilgraph, der ein Kreis ist. 2015-end 8 (b) Ist jeder zusammenhängende Graph mit Gradfolge (1,1,1,1,2,4) ein Baum? 4.2.2. Prüfer-Code 1998-pro 7 (a) ges.: Anzahl Blätter im Baum mit Prüfer-Code (2,2,3,5,1,2,3,5,3). 1998-pro 7 (b) Code zu Baum (selber Code). 1999-mid-3 9 ges.: Anzahl Blätter im Baum mit Prüfer-Code (5,4,3,2,1,1,1,1,1). 1999-mid-4 9 ges.: Anzahl Blätter im Baum mit Prüfer-Code (5,4,3,2,1,1,1,1,1). 2000-end M3 Von Code zu Baum (n=7) und Fragen zum Baum. 2000-wdh M7 Baum zu Code (n=12) als Multiple Choice. 2001-end 6 (a) Von Code zu Baum (n=9). 2001-end 6 (b) Baum mit Prüfer-Code 1^k = 1,1,...,1? 2002-wdh 5 ges.: Anzahl Blätter im Baum mit Prüfer-Code (1,2,3,4,5,6,7,8). 2003-end 7 ges.: Anzahl Kanten vom Baum mit Prüfer-Code (4,1,3,3,2,3,1,5,4). Grad von Knoten 3? 2005-end 5 (2) Von Baum zu Code (n=8). 2005-end 5 (3) Von Code zu Baum (n=7). 2005-end 5 (4) Wie sehen Prüfer-Codes von Pfaden aus? 2006-end 1 (a) Gibt es isomorphe Bäume mit verschiedenen Prüfer-Codes? 2006-end 1 (b) Gibt es zu jedem Prüfer-Code einen eindeutigen Baum? 2007-wdh 6 Prüfer-Code um k 1en erweitert. 2009-end 1 (3) Besitzt der Baum mit Prüfer-Code (5,5,5) die Gradfolge (1,1,1,1,4)? 2011-end-2 6 (1) Von einem beschriebenen Baum zu Code (n=9). 2011-end-2 6 (2) Baum zum Prüfer-Code (k,k-1,...,2,1,2,---,k-1,k)? 2011-end-1 8 (1) Von Baum zu Code (n=7). 2011-end-1 8 (2) Von Code zu Baum (n=10). ------------------------------------------------------------------------------------------------------------------------------------------------- 4.3. Euler-Touren und Hamilton-Kreise ------------------------------------------------------------------------------------------------------------------------------------------------- 4.3.1. Euler-Touren 1999-mid-1 8 Enthält jeder zusammenhängende 6-reguläre Graph eine Euler-Tour? 2000-wdh M8 (b) Gibt es einen eulerschen Graph, der eine Brücke enthält? 2002-mid 3 (c) Gibt es Graphen mit Gradfolge (2,2,3,4,4,4,5), die eine Euler-Tour besitzen? 2002-wdh 6 (d) Enthält jeder 2-reguläre Graph eine Euler-Tour? 2003-wdh 4 (f) Besitzt jeder vollständige Graph eine Euler-Tour? 2004-end 3 (e) Enthält jeder zusammenhängende, 4-reguläre Graph eine Euler-Tour? 2004-end 3 (f) Ist jede Euler-Tour ein Kreis? 2004-wdh 3 (a) Enthält jeder vollständige Graph K_n eine Euler-Tour? 2008-end 1 (3) Hat jeder vollständige Graph K_n eine Euler-Tour? 2008-wdh 1 (5) Besitzt jeder reguläre Graph mit 4 Knoten eine Euler-Tour? 2009-end 1 (1) Besitzt jeder 17-reguläre Graph eine Euler-Tour? 2013-wdh 7 (d) Enthält jeder Graph mit Gradfolge (4,4,4,4,4,4,4,4,4,4) eine Euler-Tour? 2015-end 8 (d) Enthält jeder Graph mit Gradfolge (2,2,2) eine Euler-Tour? 4.3.2. Hamilton-Kreise 1999-mid-2 6 Ist jeder 2-reguläre zusammenhängende Graph hamiltonsch? 1999-mid-2 8 Enthält kein bipartiter Graph mit ungerader Knotenanzahl einen Hamilton-Kreis? 2000-wdh M8 (d) Ist jeder zusammenhängende, bipartite Graph hamiltonsch? 2002-mid 2 (b) Wie viele Hamilton-Kreise besitzt der K_n? Info: Ohne Richtung und ohne Startknoten. Beispielsweise besitzt der K_3 genau einen Hamilton-Kreis. 2002-wdh 6 (b) Enthält jeder 7-reguläre Graph mit 10 Knoten einen Hamilton-Kreis? 2004-end 3 (g) Besitzt der K_4 genau 3 verschiedene Hamilton-Kreise? Info: Ohne Richtung und ohne Startknoten. Beispielsweise besitzt der K_3 genau einen Hamilton-Kreis. 2004-wdh 3 (b) Enthält jeder vollständige Graph K_n einen Hamilton-Kreis? 2006-mid 1 (e) Ist der vollständige Graph K_317 hamiltonsch? 2006-wdh-1 1 (f) Enthält jeder eulersche Graph einen Hamilton-Kreis? 2013-wdh 7 (e) Gibt es einen Graph mit Gradfolge (1,2,3,3,4,5), der einen Hamilton-Kreis enthält? 2013-wdh 7 (f) Gibt es einen Graph mit Gradfolge (1,4,4,4,4,4), der einen Hamilton-Kreis enthält? 2015-end 8 (c) Enthält jeder Graph mit Gradfolge (3,3,3,3,4,4,4) einen Hamilton-Kreis? ------------------------------------------------------------------------------------------------------------------------------------------------- 4.4. Planarität und Färbung ------------------------------------------------------------------------------------------------------------------------------------------------- 4.4.1. Planarität 1998-pro 10 Ist der gegebene Graph planar? 1998-end 4 z.z.: Ein planarer Graph mit deg(v) ≥ 3 für alle v∊V hat mindestens einen Knoten vom Grad höchstens 5. 1999-mid-1 6 Gibt es einen 6-regulären planaren Graphen mit 17 Knoten? 1999-mid-3 6 Gibt es einen planaren Graphen mit 17 Knoten, der einen Knoten mit Grad 16 enthält? 1999-mid-4 7 Gibt es einen 3-regulären planaren Graphen mit 21 Knoten? 2001-wdh 6 (a) Ist der gegebene Graph planar? 2002-mid 3 (a) Sind alle Graphen mit Gradfolge (2,2,3,4,4,4,5) planar? 2002-end 1 (b) z.z.: Jeder Baum mit drei zusätzlichen Kanten ist planar. 2002-end 7 (c) Ist der gegebene Graph planar? 2002-wdh 6 (f) Enthält jeder nicht-planare Graph, der keine Unterteilung des K_3,3 enthält, mehr als hundert Spannbäume? 2003-wdh 4 (h) Gibt es ein n≥5, so dass K_n planar ist? 2004-wdh 3 (f) Gibt es einen planaren Graphen mit 5 Knoten und 10 Kanten? 2006-wdh-1 3 Ist jeder Graph mit 20 Knoten und deg(v)≥6 für alle v∊V planar? 2007-wdh 2 (2) ges.: Anzahl vollständiger planaren Teilgraphen von K_7. 2009-wdh 1 (6) Ist jeder Graph mit |V|=|E|+1 planar? 2008-end 5 (2,3) Planare, 4-reguläre Graphen mit genau 3 Kanten pro Gebiet. 2011-end-1 9 (3) ges.: Planarer Teilgraph von K_3,5 mit |V|=8 und |E|=12. 2012-end 4 (2) ges.: 3-regulärer, planarer, bipartiter Graph. 2013-end 9 (e) Gibt es einen planaren Graph mit Gradfolge (4,4,5,5,5,5)? 2014-end 4 (4) z.z.: Es gibt keinen planaren bipartiten 3-regulären Graphen mit weniger als 8 Knoten. 2014-end 4 (5) z.z.: Für alle n≥2 gibt es einen planaren 3-regulären bipartiten Graphen mit 4n Knoten. 2014-wdh 5 (2) z.z.: G hat keinen Kreis der Länge l>5 als Teilgraph ⇒ G planar 2014-wdh 5 (4) Gibt es einen planaren bipartiten Graphen mit |v| = 6 und |E| = 2|V|-4 Kanten? 2015-end 8 (a) Gibt es einen planaren Graphen mit Gradfolge (4,4,4,4,5,5)? 4.4.2. Färbung 1998-end 3 (a) Gibt es für alle n∊ℕ einen Graph G mit χ(G)=n? 2001-wdh 6 (b) Welche chromatische Zahl hat der gegebene Graph? 2002-mid 3 (f) Gibt es Graphen mit Gradfolge (2,2,3,4,4,4,5) mit chromatischer Zahl 5? 2002-wdh 6 (e) Ist jeder 3-reguläre Graph 4-färbbar? 2006-wdh-1 2 Gibt es für alle n∊ℕ einen Graph G mit chromatischer Zahl (bzw. chromatischem Index) n? 2007-end 1 (3) Welche chromatische Zahl hat ein Baum mit 10 Knoten? 2008-end 4 Färbung von 2-Baum-Graphen. 2013-end 9 (f) Ist jeder Graph mit Gradfolge (2,2,2,2,3,3,3,3) 4-färbbar? 2015-wdh 4 (c) Gibt es einen vier-färbbaren Graphen mit Gradfolge (2,2,4,4,4,4,4)? ------------------------------------------------------------------------------------------------------------------------------------------------- 4.5. Matchings ------------------------------------------------------------------------------------------------------------------------------------------------- 1999-mid-1 9 Hat jeder 3-regulär, bipartite Graph ein perfektes Matching? 1999-mid-3 7 Hat jeder 3-reguläre Graph ein perfektes Matching? 1999-wdh-2 6 (b) z.z.: G = (A,B,E) bipartit und k-regulär ⇒ G hat perfektes Matching. 2002-end 1 (c) Hat jeder 2-regulär, bipartite Graph ein perfektes Matching? 2002-mid 3 (e) Hat jeder Graph mit Gradfolge (2,2,3,4,4,4,5) ein perfektes Matching? 2002-wdh 6 (g) Hat jeder bipartite Graph mit |V| gerade und δ(G)=2 ein perfektes Matching? 2004-end 4 (c) Hat jeder 2-regulär, bipartite Graph ein perfektes Matching? 2004-wdh 3 (d) Hat jeder Baum mit |V| gerade ein perfektes Matching? 2006-end 1 (d) Hat K_n für n gerade ein perfektes Matching? 2006-wdh-2 1 (j) Hat K_i,j immer ein perfektes Matching? 2007-end 2 (1) ges.: Anzahl perfekter Mathings in K_3,3. 2009-wdh 1 (7) Hat jeder Graph mit Gradfolge (1,1,1,1,1,5) ein perfektes Matching? 2014-wdh 1 (2) Besitzt jeder Baum mit Gradfolge (3,2,2,1,1,1) ein perfektes Matching? 2015-wdh 4 (d) Besitzt jeder Graph mit Gradfolge (2,2,2,2,2,2) ein perfektes Matching? ================================================================================================================================================= 5. Algebraische Strukturen ================================================================================================================================================= ------------------------------------------------------------------------------------------------------------------------------------------------- 5.1. Algebren ------------------------------------------------------------------------------------------------------------------------------------------------- 2001-end 2 (c) ges.: Anzahl Monoide mit zwei Elementen. 2002-end 2 (a,b) Was sind (ℕ,ggT) und ({1,2,3,4,6,12},ggT)? 2006-wdh-2 1 (f) Gilt in jedem Monoid das Kommutativgeetz? 2007-wdh 5 Algebra über Funktionen F_a,b(x) = ax + b. 2012-end 2 Algebra über Mengen aus P(X). ------------------------------------------------------------------------------------------------------------------------------------------------- 5.2. Gruppen ------------------------------------------------------------------------------------------------------------------------------------------------- 5.2.1. Wichtige Begriffe Eigenschaften von Gruppen 1999-wdh2 9 Kürzungsregel mit |G|=6 2000-wdh M5 6 Aussagen 2001-wdh 2 (b) Kürzungsregel mit G = {a,b,c,d}. 2008-end 1 (5) Gilt für eine kommutative Gruppe ({g_1,...,g_n},∘) mit neutralem Element e die Gleichung g_1²∘...∘g_n² = e? 2008-end 8 Gruppe mit S = {e,a,b,c} und a²=e. 2009-end 1 (7) Bildet genau eine boolesche Operation eine Gruppe mit 1 als neutrales Element? Generierung von Elementen, Untergruppen und Elementenordnung 2004-end 2 (b) Ist jede zyklische Gruppe kommutativ? 2009-end 1 (8) Ist jede Gruppe mit 7 Elementen zyklisch? 2009-wdh 1 (8) Ist jede Gruppe mit 7 Elementen kommutativ? 2010-mid 1 (3) Gibt es eine endliche Untergruppe von (ℤ,+) außer ({0},+)? 2010-mid 5 Nicht-zyklische Gruppen mit S = {e,a,b,c}. 2010-wdh 1 (1) Gilt in einer zyklischen Gruppe x²yx⁻¹ = y²xy⁻¹? 2011-end-1 1 (6) Gibt es unendlich viele endliche Untergruppen von (ℤ,+)? 2014-wdh 4 (2) z.z.: Wenn |G|=9, dann enthält G eine 3-elementige zyklische Untergruppe. 5.2.2. Additive Gruppe Modulo n Rechnen mit Modulo I (ohne den Satz von Euler) 2002-mid 7 (a) Was ist (n+2)! mod n? 2002-mid 7 (b) Was ist (n-1)(n+1) mod n? 2002-wdh 4 (a) Was ist 14! mod 15? 2002-wdh 4 (c) Was ist (17+16!) mod 15? 2005-wdh 2 (2) ((-2)·(-3)³⁰) mod 12? 2007-end 2 (2) ges.: Anzahl der Elemente x mit x ≡_30 -100 und 0 ≤ x ≤ 100. 2007-wdh 2 (3) Was ist n! mod (2n)? 2008-end 1 (6) Gilt (m²-n²) mod (m-n) = 0? 2009-end 1 (6) Gilt (k mod 5) mod 2 = (k mod 2) mod 5 für jedes k? 2010-mid 1 (5) Gilt (-13) mod 7 = 6? 2012-mid 1 (2) Gilt (k mod 7) mod 5 = (k mod 5) mod 7 für jedes k? 2015-end 9 (a) Berechne 5⁵³ mod 107 und 3⁵³ mod 107. (Mit Hinweisen!) Sonstige Aufgaben 2000-wdh M3 ges.: Anzahl Untergruppen von (ℤ_11,+_11). Info: Mit "ℤ/11ℤ" ist hier "ℤ_11" gemeint. 2007-end 2 (3) ges.: ord(8) in ℤ_20. 2009-end 1 (4) (ℤ_2,+_2) Untergruppe von (ℤ,+)? 2014-wdh 4 (1) ges.: Eine 9-elementige Gruppe. 5.2.3. Multiplikative Gruppe Modulo n Die Menge ℤ*_n 2013-end 10 (b) Was ist |ℤ*_9991|? 2014-wdh 4 (3a) Was ist |ℤ*_81|? Euklidischer Algorithmus 2002-wdh 7 (b) Was ist (p-2)⁻¹ in ℤ*_p? (p≥3 prim, also p auch ungerade) 2006-wdh-2 6 (a) Für welche a,b∊ℤ gilt ggT(90,147) = 90a + 147b? 2010-mid 6 (1) Was ist ggT(1000,69)? 2010-mid 6 (2) Für welche a,b∊ℤ gilt 1000a + 69b = ggT(1000,69)? 2010-mid 6 (3) Was ist 69⁻¹ in ℤ*_1000? 2012-mid 6 (1) Hat 39 ein Inverses in ℤ*_4851? 2012-mid 6 (2) Was ist 221⁻¹ in ℤ*_4851? 2013-end 10 (b) Was ist 23⁻¹ in ℤ*_9991? (Taschenrechner erlaubt!) 2014-end 3 (2b) Was ist 81⁻¹ in ℤ*_100? 2014-end 3 (2c) Für welches x∊ℤ*_100 gilt 81 ·_100 x = 41? 2014-wdh 4 (3c) Was ist 64⁻¹ in ℤ*_81? 2015-end 9 (c) Was ist 32⁻¹ in ℤ*_107? Rechnen mit modulo II (mit dem Satz von Euler) 2001-end 1 (a) 5¹²¹³ mod 7? 2001-end 1 (b) 7^17²³ mod 9? 2002-mid 7 (d) (p-1)^(p+1) mod p? (p prim.) 2002-mid 7 (e) 2⁴⁹ mod 49? 2002-wdh 4 (d) n^(2^n) mod 2^n? (n ungerade.) 2003-mid-1 10 (b) Was ist 5²⁶ in ℤ*_23? 2004-wdh 5 (a) 32¹⁰⁰ mod 7? 2005-mid 1 (1) (-10¹⁰⁰) mod 13 2008-wdh 1 (7) 30⁹⁹ mod 7 2011-end-2 1 (4) (-2)¹⁰⁰¹ mod 5 = 2? 2014-end 3 (2a) 81 ·_100 81. 2014-wdh 4 (3b) 80 ·_81 80. 2015-end 9 (c) Was ist 32¹⁰⁵ in ℤ*_107? Sonstige Aufgaben 2001-end 2 (a) Untergruppen von ℤ*_12? 2001-wdh 2 (c) ord(9⁻¹) in ℤ*_11? 2003-mid-2 10 (b) Ordnung aller Elemente in ℤ*_15 2007-end 4 (2) z.z.: ℤ*_10 ist zyklisch. 2007-wdh 2 (4) ord(4) in ℤ*_9? 2012-mid 1 (3) Ist (ℤ*_4,·) Unteralgebra von (ℤ,·)? 2015-end 9 (b) Sind 3 und 5 Erzeuger von ℤ*_107? 5.2.4. Symmetrische Gruppe 2000-mid 8 (a-d) Was sind π⁻¹, σ⁻¹, (π∘σ)⁻¹ und ord(σ)? 2000-end 3 Radrennfahrer. 2000-wdh M4 ges.: Anzahl Zyklen von π. 2001-mid 1 Was sind ord(π), π² und π⁵⁹⁹? 2001-wdh 2 (a) ges.: Anzahl zweielementiger Untergruppen von S_3. 2002-end 5 16 Karten werden gemischt. 2003-wdh 6 (c) σ in Zyklendarstellung? 2005-mid 1 (4) Ordnung von π in Matrixschreibweise? 2005-mid 5 p = q∘r∘s in beiden Schreibweisen? 2007-end 1 (4) ges.: Unteralgebra von ([4]^[4],∘), die eine Gruppe ist. Info: Jede Untergruppe von S_4 wäre hier richtig. 2007-wdh 1 (5) Ist (S_3,∘) kommutativ? 2007-wdh 9 p = p_1∘p_2∘p_3∘p_4 2008-wdh 1 (10) Ist (S_n,∘) zyklisch? 2008-wdh 7 Rotation und Spiegelung von Fünfecken. 2009-end 6 (1-4) 4-elementige Untergruppe von S_4 2009-wdh 5 (1,2) ges.: p∊S_9 mit ord(p) = 9 und p,q∊S_4 mit p∘q ≠ q∘p. 2010-mid 1 (4) Was ist ord(p) in S_6? 2011-end-1 1 (2) Gibt es ein p∊S_5 mit ord(p) = 25? 2012-mid 5 Symmetrische Gruppe S_8. 2012-end 1 (2) Gibt es eine Untergruppe, die p∊S_8 enthält und 4 Elemente besitzt? 2012-wdh 1 (3) Ist die kleinste Gruppe, die p,q∊S_4 enthält, kommutativ? 2014-end 3 (1) 3- und 6-elementige Untergruppen von (S_4,∘). 2014-end 5 (1,2) Zyklendarstellung und Ordnung von p? 2014-wdh 6 (1) Gruppe Q = {p ∊ S_4|p∘p = id} 5.2.5. Inneres Produkt 2008-end 7 (1,2) Neutrales Element, inverse Elemente und Ordnungen in (ℤ_m x ℤ_n, +_m x +_n). 5.2.6. Gruppenhomomorphismen und -isomorphismen 2000-mid 10 (a) Gibt es ein Isomorphismus zwischen (ℤ_5,+_5) und (ℤ_25,+_25)? 2000-mid 10 (b) Gibt es ein Isomorphismus zwischen (ℤ,+) und (5ℤ,+)? 2002-wdh 7 (a) Wie viele nicht-isomorphe Gruppen mit drei Elementen gibt es? 2006-end 1 (h) Ist jeder Homomorphismus bijektiv? 2006-end 6 (a) Definition Homomorphismus. 2006-end 6 (b) z.z.: h(x) = x mod 5 ist kein Homomorphismus von ℤ_9 nach ℤ_5. 2006-end 6 (c) z.z.: h(x) = x mod 3 ist ein Homomorphismus von ℤ_9 nach ℤ_3. 2008-end 7 (3) Sind ℤ_2 x ℤ_3 und ℤ_6 isomorph? Sind es ℤ_2 x ℤ_2 und ℤ_4? 2009-end 6 (5) Ist (ℤ_4,+_4) isomorph zu ({id,p,q,r,},∘) mit p = (1,2)(3)(4), q = (1)(2)(3,4) und r = (1,2)(3,4)? 2009-wdh 5 (3) Welcher Zusammenhang besteht zwischen S_2 und ℤ*_4? 2011-end-2 1 (2) Gibt es unendlich viele paarweise nicht-isomorphe 2-elementige Gruppen? ------------------------------------------------------------------------------------------------------------------------------------------------- 5.3. Endliche Körper ------------------------------------------------------------------------------------------------------------------------------------------------- 5.3.1. Wichtige Begriffe zu Ringen und Körpern 1998-end 9 Ist (ℤ*_n,+_n,·_n) ein Körper? 2002-end 2 (c) Verknüpfungstafeln eines 3-elementigen Körpers ausfüllen. 2004-wdh 2 (f) Ist die Summe (mit ⊕) aller Elemente eines endlichen Körpers (K,⊕,⊙) das additive neutrale Element 0? 2007-wdh 1 (8) Ist (ℤ_9,+_9,·_9) ein Körper? 2005-mid 4 (1) z.z.: Es gibt ein Ring und kein Körper mit 3 Elementen 0, 1 und a. 2006-wdh-2 1 (g) Ist jeder Ring ein Körper? 2006-wdh-2 1 (h) Gilt in jedem Ring (M,⊕,⊙) a ⊕ (b ⊙ c) = (a ⊕ b) ⊙ (a ⊕ c) für beliebige a,b,c∊M? 2006-wdh-2 1 (i) Sind in einem Körper beide Operatoren abelsch (kommutativ)? 2012-mid 1 (1) Gilt [0]_1 = {0} in (ℤ,+,·)? Info: [k]_n = {x|x ≡_n k} ist die Menge aller zu k kongruenten Zahlen modulo n. 5.3.2. Polynomringe Rechnen mit Polynomen 2001-wdh 1 (a) Ist 3x³+3x²+4 kongruent zu 4x³+3x modulo x+2 in ℤ_5[x]? 2001-wdh 1 (b) Ist die Kongruenz modulo g für ein Polynom g eine Äquivalenzrelation? 2004-end 2 (c) Gilt x²-5x+4 mod x-2 = 2 in ℤ[x]? 2009-end 7 (2) Polynomdivision von x⁴+x³+3 durch 3x²+4 über ℤ_5[x]. 2009-wdh 8 (1) z.z.: In ℤ_3[x] gilt (x³+2)³ = x⁹+2. 2009-wdh 8 (2) z.z.: In ℤ_3[x] gilt x⁸ ≡_π x² für π = x³+2 2011-end-2 4 (1) Polynomdivision von x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1 durch x²+1 über ℤ_11[x]. 2011-wdh 8 (1) Polynomdivision von x⁶+x⁴+1 durch x²+x+1 über ℤ_2[x]. 2012-wdh 5 (3) Was ist (x³)² mod x⁶+2x³+1 in ℤ_5[x]? Der Restklassenring (ℤ_n[x]_q,+_q,·_q) 2005-wdh 6 Ordnung, Multiplikationstafel und Nullteiler von ℤ_2[x]_(x³+1). 2006-end 3 Repräsentantenmenge und Verknüpfungstafeln von ℤ_3[x]_(2x²+1). 2006-wdh-2 4 Was ist (2x²+x+2) ·_π (x²+2x+1) und x² ·_π x² in ℤ_3[x]_π für π = 2x³+x²+2? 2009-end 7 (1) Was ist |ℤ_5[x]_(3x²+4)|? 2010-end 2 (2) Was sind x³ ·_p x², x³ ·_p x²+1, x³ ·_p x³+x und x³ ·_p x²+x+1 in (ℤ_3[x]_4,+_p,·_p) für p = x⁴+1? 2010-wdh 5 Induktion, Polynomaddition und Polynommultiplikation in ℤ_2[x]_(x¹⁵+x¹⁴). 2011-wdh 8 (3) Was ist |ℤ_2[x]_(x⁶+x⁴+1)|? 2012-end 5 (2a) Was ist (x²+x²+1)² in ℤ_2[x]_(x⁴+x+1)? 2012-wdh 5 (1) Was ist |ℤ_5[x]_(x⁶+2x³+1)|? 2015-wdh 6 (a) Was ist (x+x⁷)(1+x³+x⁴) in ℤ_2[x]_(1+x+x³+x⁴+x⁸)? Euklidischer Algorithmus 2001-mid 2 (b) Was ist das multiplikative Inverse von x²+x in ℤ_2[x]_(x³+x+1)? 2003-mid-1 7 Was ist der größte gemeinsame Teiler von x⁴+x³-3x²+7x-6 und x³-4x²+5x-6 in ℚ[x]? 2005-mid 3 (1) Was ist der größte gemeinsame Teiler von x⁵-3x⁴+3x³-9x²+2x-6 und x³+3x²+x+3 in ℤ[x]? 2005-wdh 5 (1) Was ist der größte gemeinsame Teiler von 3x³-52x+16 und x⁴-x³-8x²-4x-48 in ℂ[x]? 2007-end 6 Euklid mit x⁵+x⁴-2x³-2x²+1 und x³+2x²-1 über ℚ[x]. 2007-wdh 8 Euklid mit x⁶+2x⁴+2x³+x²+1 und x³+x²+1 über ℤ_3[x] und multiplikatives Inverses. 2010-end 2 (3) Was ist das multiplikative Inverse von x in ℤ_3[x]_(x⁴+1)? 2011-end-1 5 Was ist der größte gemeinsame Teiler von x⁶-1 und x³+x+3 in ℤ_5[x]? 2011-end-2 4 (4) Was ist das multiplikative Inverse von ax+b in ℤ_11[x]_(x²+1) für alle a,b∊ℤ_11? 2012-mid 7 Was ist der größte gemeinsame Teiler von x⁴+2x³-x²+2x-1 und 2x³-x²-1 in ℤ_3[x]? 2012-end 5 (2b) Was ist das multiplikative Inverse von x²+x²+1 in ℤ_2[x]_(x⁴+x+1)? 2012-wdh 5 (4) Was ist das multiplikative Inverse von x³ in ℤ_5[x]_(x⁶+2x³+1)? 2015-wdh 6 (b) Was ist das multiplikative Inverse von 1+x³+x⁴ in ℤ_2[x]_(1+x+x³+x⁴+x⁸)? Irreduzibilität und Faktorisierung von Polynomen 2003-mid-1 10 (a) Ist x²+x+1 irreduzibel in ℤ_3[x]? 2003-mid-2 10 (a) Ist x⁴+x³+1 irreduzibel in ℤ_2[x]? 2004-end 2 (h) Ist x²+2 reduzibel in ℤ_3[x]? 2005-mid 3 (2) Was ist die Faktorisierung von x⁵+x⁴+x³+x² in ℤ_2[x]? 2005-end 1 (4) Wie viele irreduzible Polynome der Form x³+ax²+b gibt es in ℤ_3[x]? 2006-wdh-2 1 (c) Ist (ℤ_2[x]_π,+_π,·_π) für ein irreduzibles Polynom π∊ℤ_2[x] ein Körper? 2006-wdh-2 1 (d) Ist (x+1)² irreduzibel über ℤ_3? 2011-wdh 8 (2) z.z.: x⁶+x⁴+1 ist reduzibel in ℤ_2[x]. 2012-end 5 (1) Welche Polynome aus ℤ_2[x] mit Grad 2 sind irreduzibel? Galois-Körper 2001-mid 2 (a) Ist ℤ_2[x]_(x³+x+1) ein Körper? 2001-end 3 Gibt es einen Körper K und ein Polynom p, so dass K[x]_p ein Körper mit genau 27 Elementen ist? 2004-end 2 (e) Ist GF(6) ein Körper mit 6 Elementen? 2004-end 2 (f) Ist (ℤ_4,+_4,·_4) isomorph zu GF(4)? 2004-end 2 (g) Gilt char(GF(8)) = 2? 2006-end 1 (g) Ist (ℤ_3[x]_x,+_x,·_x) kein Körper? 2006-end 1 (i) Gilt für zwei Polynome a und b über einem Körper (ℤ_n,+_n,·_n) die Gleichung grad(a·b) = grad(a) + grad(b)? 2007-end 1 (6) Welchen Grad besitzt π, falls (ℤ_5[x]_π,+_π,·_π) ein Körper mi 25 Elementen ist? 2009-wdh 8 (3) z.z.: (ℤ_3[x]_π,+_π,·_π) ist für π = x³+2 kein Körper. 2010-end 1 (1) Ist (ℤ_9,+_9,·_9) isomorph zu GF(9)? 2010-end 2 (1) Was ist |ℤ_2[x]_4|? z.z.: (ℤ_3[x]_4,+_p,·_p) ist für p = x⁴+1 kein Körper. 2010-wdh 1 (7) Gilt in GF(8) (1+1)⁷ = 0? 2011-end-2 4 (2) z.z.: ℤ_11[x]_(x¹⁰+x⁹+x⁸+x⁷+x⁶+x⁵+x⁴+x³+x²+x+1) ist kein Körper. 2011-end-2 4 (3) z.z.: ℤ_11[x]_(x²+1) ist ein Körper. 2012-end 5 (2c) Für welches n ist ℤ_2[x]_(x⁴+x+1) isomorph zum Galois-Körper GF(n)? 2012-wdh 5 (2) Ist ℤ_5[x]_(x⁶+2x³+1) ein Körper? ------------------------------------------------------------------------------------------------------------------------------------------------- 5.4. RSA-Verfahren ------------------------------------------------------------------------------------------------------------------------------------------------- 2013-wdh 9 Verschlüsseln und entschlüsseln mit p = 7 und q = 11.