Diskrete Strukturen

All + All -

Diskrete Strukturen

+ - Vorlesung im Sommersemester 2009
- + - Org
  - + - Vorlesungen
    - ~ Dietmar Lammers
    - Fast immer nur Dienstags
  - + - Übungsbetrieb
    - ~ Phillipp Kegel
    - 5 Übungsgruppen, 4x Donnerstags, 1x Freitag 10-12 im M3
    - Freitags ggf. auch mal Vorlesung!
    - ~ Anmeldung erforderlich
  - + - Sprechstunde
    - Raum 612, Einsteinstr 62
    - Speziell für DS: Di 12.00h-13.00h
    - eigentlich fast immer ...
  - + - Homepage
    - Script, MindMap, Unterlagen, Literatur, Aktuelles
    - ~ http://cs.uni-muenster.de/u/lammers/EDU/ss09/DiskreteStrukturen/
  - Klausur, Termine
  - + - Script / Unterlagen?
    - diese Mindmap (freemind), ggf. auch als html-Version
    - Guter Foliensatz von den letzten Veranstaltungen durch Xiaoyi Jiang
  - Fragen?
+ - Themen der Diskreten Strukturen
- formalisieren, abstrahieren, strukturieren
- Grundbegriffe und Grundstrukturen der Informatik
- Ganze Zahlen
- Endliche Mengen
- Unstetige Zusammenhänge
- Einfache Strukturen
- ~ Informatik-Spektrum 32/1, pp 4-32
+ - Logik
- + - Ringelnatz: Logik
  - Die Nacht war kalt und sternenklar,
    Da trieb im Meer bei Norderney
    Ein Suahelischnurrbarthaar. -
    Die nächste Schiffsuhr wies auf drei.
    
    Mir scheint da mancherlei nicht klar,
    Man fragt doch, wenn man Logik hat,
    Was sucht ein Suahelihaar
    Denn nachts um drei am Kattegatt?
- + - die denkende Kunst
  - gehört zur Philosophie, Mathematik und Informatik
    wikipedia.de, 23.2.2009:
    Seit dem 20. Jahrhundert versteht man unter Logik überwiegend symbolische Logik. Diese baut auf einer künstlichen Sprache auf und verwendet streng definierte Schlussregeln. Ein einfaches Beispiel für ein solches formales System ist die Aussagenlogik. Die symbolische Logik nennt man auch mathematische Logik oder formale Logik im engeren Sinn. Die Logik hatte nicht immer eine in diesem Sinn formale Struktur, sondern befasste sich in der Antike und im Mittelalter überwiegend mit natürlichsprachlichen Argumenten.
- + - Eindeutige Sprache
  - Eindeutige Schlüsse
  - Argumentation wird nachvollziehbar
  - Eine Formale Sprache mit formalen Schlussregeln
    erlaubt formales (=automatisches) Beweisen
- + - Klassische (=zweiwertige) Logik
  - Eine Aussage ist entweder wahr oder falsch
  - "ein drittes gibt es nicht" (tertium non datur)
  - Der Wert einer zusammengesetzten Aussage ist eindeutig
    durch die Teilaussagen bestimmt
  - + - Prädikatenlogik
    - Erweiterung der Aussagenlogik
    - Prädikat = Aussage(funktion)
    - + - Junktoren
      - + - und: ∧
        wfwf
        
        p q p∧q
        
        w w
        
        w f
        
        f f
        
        f f
      - + - oder : ∨
        p   q    p∨q
        -----------
        w   w     w
        w   f      w
        f    w     w
        f    f      f
      - + - nicht: ¬
        p    ¬p
        -------
        w    f
        f     w
      - + - Wenn A gilt, dann gilt auch B: A⇒B
        auch: A→B, A⊃B
      - A gilt genau dann, wenn B gilt: A⇔B
      - + - ...wie viele 2stellige Junktoren kann es geben?
        16: Ich kann das Probem als Verteilproblem
        der w auf vier Positionen betrachten:
        1. - kein w - 1 Möglichkeit
        2. - ein w - 4 Möglichkeiten
        3. - zwei w - 6 Möglichkeiten
        4. - drei w (= ein f) - 4 Möglcihkeiten
        5. - vier w - 1 Möglichkeit
        zusammen 16 (=2^4 - warum wohl?)
    - + - Quantoren
      - + - es gibt: ∃x P(x)
        Es gibt schwarze Schafe
        
        Es gibt ein t, für das gilt: t ist ein schwarzes Schaf
      - + - für alle: ∀x P(x)
        Alle Vögel können fliegen
        
        Für alle x aus der Menge der Vögel gilt: x kann fliegen
  - + - Andere Systeme
    - fuzzy logik
    - intuitionistische Logik
  - + - Wissenschaftstheorie
    - Karl Popper, Falsifizierbarkeit
    - Spektrum der Wissenschfaft 3/2009 pp 72.
- + - Definitionen
  - Eine Definition ist i.a ein Vereinbarung über eine abkürzende Schreibweise für eine Reihe von Eigenschaften. Wichtig ist die Überprüfbarkeit, d.h. das ich beweisen kann, das ein Objekt tatsächlich diese Definition erfüllt, oder eben nicht.
    Sinnvoll ist eine Definition natürlich nur dann, wenn ich den definierten Begiff häufiger verwende, die Benutzung Zeit und Arbeit spart, und eventuell weitere Aussagen auch übersichtlicher macht.
    Wohldefiniert ist ein Begriff dann, wenn das Definierte existiert und durch die Definition eindeutig beschreiben ist. Bei expliziten Definitionen ist das klar, bei impliziten Definitionen muss man das ggf. nachweisen.
    Bsp: Annäherung an die Quadratwurzel
    + - Interessant sind induktive Definitionen:
    Man gibt einzelne (initiale) Elemente an, und Konstruktionsregeln,
    wie man aus diesen zu neuen Elementen kommt.
    Oft kommt dann noch eine Eindeutigkeitsregel dazu,
    z.B. "kleinste Menge mit dieser Eingenschaft".
    - Def. Ein Binärbaum über einer Menge M ist ein Ausdruck B,
      der folgende Bedingungen erfüllt:
      
      1. Für alle Elemente m aus M ist m ein Binärbaum.
      2. Wenn a und b Binärbäume sind, so ist auch (a.b) ein Binärbaum.
      
      BSP:
      Sei M = {1,2,3}, dann ist z.B. (1.((2.1).3)) ein Binärbaumüber M
- + - Beweise
  - + - Hopcroft/Motwani/Ullman, Introduction to Automat Theory, Languages, and Computation:
    
    "In the USA of the 1990's it became popular to teach proof as a matter of personal taste about the statement"
    - (Kein Wunder, das sich Creationsten dort ausbreiten)
    Ein Beweis ist ein Nachweis der Korrektheit einer Aussage in kleinen, nachvollziehbaren Schritten.
    Ein Beweis einer Aussage ist die Herleitung der Korrektheit einer Aussage aus den Voraussetzungen in Schritten, deren Korrektheit bereits nachgewiesen ist.
    U.a. deswegen ist eine exakte Sprache hier notwendig:
    Ungenaue Aussagen kann man nicht beweisen, eine ungenauer Beweis beweist nichts.
    
    + - Ein formaler Beweis in der klassischen Logik ist die Umformung einer Zeichenreihe nach definierten Regeln (eines Kalküls).
    - Das macht automatisches Beweisen möglich: Wie Routenplaner Wege zum Ziel finden, finden automatische Beweiser die richtigen Umformungen von den Voraussetzungen zur Behauptung
      Hier trennt sich Syntax und Semantik: Ich kann einfach nach den Regeln umformen, ohen über die Bedeutung nachzudenken. Die Semantik, also die Bedeutung folgt aus dem Modell, das ich der Syntax zuordne
    Beispiele, in denen eine Aussage stimmt, oder Tests, sind keine hinreichenden Beweise.
    + - Meist sind die Aussagen, die zu beweisen sind, von der Form:
    Wenn A1 und A2 und A3 und ... und An, dann gilt B
    - Oft sind nicht alle Annahmen angegeben, Axiome werden gern ohne weitere Erwähnung angenommen
      Zu Nutze machen kann man sich beim Beweis einer solchen Aussage folgende Sätze:
      + - Satz: Die Aussage "Wenn A dann B" ist genau dann wahr, wenn auch die Aussage "Nicht B oder A" wahr ist,
      - Beweis: Hier kann man einen direkten Beweis mit einer Wahrheitstafel verwenden,
        in der alle möglichen Fälle aufgeführt werden:
        
        A B A → B ¬A ∨ B
        
        w w w w
        
        w f f f
        
        f w w w
        
        f f w w
      Satz (de Morgan 1): nicht (A und B) = nicht(A) oder nicht(B)
      Satz (de Morgan 2): nicht (A oder B) = nicht(A) und nicht(B)
      ... u.a. diverse Distibutiv- und Assoziativregeln
    Bei Aequivalenzaussagen "A genau dann, wenn B" beweist man meist hintereinander "Wenn A, dann B" und "Wenn B dann A".
    + - Beweistechniken
    - + - Direkter (deduktiver) Beweis
      - Man schliesst von den Voraussetzungen Schritt für Schritt auf den Schluss
      - Satz: Ist eine Zahl n ungerade, so ist auch n² ungerade
    - + - Indirekter Beweis
      - Man zeigt (direkt) "Aus nicht (B) folgt nicht (A)"
      - + - Es gilt nämlich:
        + - Satz: (A→B) = (¬B → ¬A)
        Beweis: Man kann das wieder über eine Wahrheitstafel beweisen,
        Man kann aber auch die nützlichen Gesetze
        nicht (A und B) = nicht(A) oder nicht(B)" und
        nicht (nicht(A)) = A"
        durch Wahrheitstafeln aus den Axiomen beweisen, und dann zusammen mit dem vorigen Satz zum Beweis benutzen:
        Beweis:
        nicht(B) folgt nicht(A) = nicht(nicht(A)) oder nicht(B)
        = A oder nicht(B) = A folgt B
      - Das ist wie bei Labyrinth-Rätseln - oft ist es einfacher, vom Ausgang zum Startpunkt zu gehen
    - + - Beweise durch Widerspruch
      - Man nimmt an "A und nicht(B)",
        und zeigt, das das immer falsch ist,
        indem man einen Widerspruch findet,
        also eine Aussage P und nicht(P) herleitet.
        + - Im Prinzip ist das ein Spezialfall des indirekten Beweises:
        A ∧ ¬ B → f
        = ¬(f) → ¬( A ∧ ¬ B)
        = w → ¬(A) ∨ B
        = w → ( A → B)
        
        Bsp/Satz: √3 ist irrational
        Bsp / Satz: Es gibt keine bijektive Abbildung zwischen einer Menge und ihrer Potzenzmenge
        Bsp / Satz: In einem unendlichen Universum ist das Komplement einer endlichen Menge unendlich.
    - + - Induktive Beweise
      - Viele Strukturen, mit denen sich Informatik, Logik und Mathematik beschäftigen,
        sind induktiv aufgebaut. Die Idee ist dabei, das ich
        
        1. eine kleine Zahl der Elemente der Struktur exakt benenne, und
        2. Regeln angebe, wie ich aus (bekannten) Elementen der Stuktur weitere Elemente
          der Struktur erzeugen kann.
        
        Die Gesamstruktur besteht dann nur aus den so erzeugten Elementen.
        Der Beweis von Eigenschaften aller Elemente der Struktur geht dann folgendermassen:
        
        1. Ich weise die Eigenschaft für die kleine Menge der benannten Elemente nach
        2. Ich weise für alle Konstruktionsregeln nach, das die Eigenschaft für das konstruierte
           Element gilt, wenn sie bereits für die zur Konstruktion verwendeten Elemente galt.
        
        Da alle Elemente so erzeugt werden, ist damit die Eigenschaft für alle Elemente der
        Struktur beweisen.
        + - Bsp: die natürlichen Zahlen
        "Die natürlichen Zahlen hat der liebe Gott gemacht, alles anderer ist Menschenwerk"
        Peano (1858-1932) kommt in seinen Axiomen mit weniger aus:
        Def:
          1. 0 ist eine natürliche Zahl.
          2. Zu jeder natürlichen Zahl n gibt es genau einen Nachfolger n', der ebenfalls eine natürliche Zahl ist.
          3. Es gibt keine natürliche Zahl, deren Nachfolger 0 ist.
          4. Jede natürliche Zahl ist Nachfolger höchstens einer natürlichen Zahl.
          5. Von allen Mengen X, welche die Zahl 0 und
              mit jeder natürlichen Zahl n auch stets deren Nachfolger n'
              enthalten, ist die Menge der natürlichen Zahlen die kleinste.
        
        (Quelle: wikipedia, 3/2009)
        + - Der Nachfolger n' von n ist natürlich n+1. Damit hat man folgendes Induktionsschema
        für die natürlichen Zahlen:
        1. Man zeigt eine Eingenschaft für eine natürliche Zahl m
        2. Unter der Annahme, das die Eigenschaft für eine beliebige natürliche
           Zahl n gilt, zeigt man das sie dann auch für den Nachfolger, die Zahl n'=(n+1) gilt.
        Damit hat man bewiesen, das die nachzuweisende Eigenschaft für alle natürlichen
        Zahlen >= m gilt. Falls m=0, gilt sie also universell für alle natürlichen Zahlen.
        Satz: Die Summe natürlichen Zahlen
        von 0 bis zu einer natürlichen Zahl m > 0 ist
        gleich (m+1)m/2, also
        ∀ m ∈ Ν : ∑_i=0,...,mi = (m+1)m/2
        Beweis:
        
        Für m=1 ist die Aussage korrekt, denn 0+1 = (1+1)/2 = 2/2 = 1.
        
        Sei die Aussage nun für die Zahl k korrekt. Es ist ∑_{i=0,...,(k+1)}i
        = (k+1) + ∑_i=0,...,ki
        =_IV (k+1) + (k+1)k/2
        = (2(k+1) + (k+1)k)/2 = (k+2)(k+1)/2,
        Die Aussage gilt also auch für (k+1)
        
        Also gilt sie für alle m>0 - q.e.d
        
        Bsp/Aufgabe: Die Summe der ungeraden Zahlen von 1 bis 2n-1 ist n².
        
        + - Bsp: Reguläre Ausdrücke über einem Alphabet
        Def: Sei Σ eine endliche Menge von Symbolen, dann sind
        die Menge RE(Σ) der regulären Ausdrücke und
        die zugehörigen Mengen RM defniert durch
        
        ε ∈ RE(Σ), RM(ε) := ∅
        
        ∀ a ∈ Σ : a ∈ RE(Σ), RM(a) := {a}
        
        ∀ a,b ∈ RE(Σ) : (a+b) ∈ RE(Σ), RM((a+b)) := RM(a)∪RM(b)
        
        ∀ a,b ∈ RE(Σ) : (ab) ∈ RE(Σ), RM((ab)) := RM (a)RM(b)
        
        ∀ a ∈ RE(Σ) : (a)^* ∈ RE(Σ), RM((a)^*) := RM(a)^*
        
        keine weiteren Elemente sind in RE(Σ)
        
        Die Klammern sind dabei wesentlich, und zu schreiben!
        Aufgabe: Zeigen Sie:
        Für das Alphabet Σ={a,b,c} ist a∪bc^* nicht in RE(Σ)
        BSP: Geben Sie einen regulären Ausdruck an, der die Natürlichen Zahlen in der üblichen Dezimaldarstellung beschreibt
        Man kann beweisen, das die durch reguläre Ausdrücke darstellbaren Mengen genau die von endlichen Automaten akzeptierten Sprachen sind. Der Beweis muss natürlich induktiv über den Aufbau geführt werden.
    - ~ Weitere Beispiele etc.
- + - Literatur
  - Ebbinghaus / Flum / Thomas: Einführung in die mathematische Logik, Spektrum akad. Verlag
+ - Mengen
- + - Was ist eine Menge?
  - ~ Georg Cantor: Eine Menge ist eine Zusammenfassung bestimmter, wohlunterschiedlicher Dinge unserer Anschauung oder unseres Denkens, welche Elemente der Menge genannt werden, zu einem Ganzen.
    Hier sind wir formaler, eine Menge ist definiert durch ihre Elemente, und man kann exact sagen, wann ein Element dazu gehört und wann nicht.
    Damit ist z.B. die Menge der besten Putenrezepte keine Menge im mathematischen Sinn.
- + - Mögliche Angaben einer Menge:
  - + - Die leere Menge
    - ∅= {}
  - + - Durch Aufzählen der Elemente
    - {a, b, c}
    - {4,5,7}
    - {rot, grün, blau}
  - + - Durch Angabe einer Impliziten Bildungsregel, sofern diese wirklich eindeutig ist
    - {3,6,9,12,...}
    - {1,1/2,1/3,1/4,...}
  - + - Durch die Angabe der Eigenschaften der Elemente: {x | P(x)}
    - { n | n>3}
    - { n ∈ N | n>5 }
- + - Beziehungen zwischen Mengen und Elementen
  - Def.
    x∈A    :<=> x ist Element der Menge A
    x∉A    :<=> x ist nicht Element der Menge A
    Def.
    A⊆B    A ist Teilmenge von B :<=>(x ∈ A ⇒ x ∈ B)
    A⊂B    A ist echte Teilmenge von B :<=> (A ⊆ B ∧ A ≠ B)
    A=B   :<=> (x ∈ A ⇔ x ∈ B)
    Def. |A| heisst Anzahl der Elemente der Menge bzw. Kardinalität von A
    + - A ∪ B := {x | x ∈ A ∨ x ∈ B} - die Vereinigung von A und B, "A vereinigt B"
    A ∩ B := {x | x ∈ A ∧ x ∈ B} - die Schnittmenge von A und B, "A geschnitten B"
    A-B := A\B = {x | x ∈ A ∧ x ∉ B} - die Differenz von A und B, "A ohne B"
    A∆B := (A\B) ∪ (B\A) - die symmetrische Differenz von A und B
    A x B := {(a,b) | a∈A und b∈B} - das Kreuzprodukt von A und B
    A^c := c(A) := {x | x ∈ U ∧ x ∉ A} - Das Komplement von (bzgl. des Unversums U)
    2^A := ℘(A) := Pot(A) = {S | S ist Teilmenge von A} - Potenzmenge von A
    - Teilmengen sind interessant, die Logik, genauer das
      Zermelo-Fraenkel-Choice (ZFC)-Axiomenschemata der Mengenlehre,
      baut z.B. die natürlichen Zahlen IN aus der Leeren Menge und Teilmengen auf
      (kleinste Menge mit der Eigenschaften des Unendlichkeitsaxiomes)
      0 - ∅
      1 - {∅} = Pot(0)
      2 - {∅,{∅}} = Pot(1)
      3 - {∅,{∅},{∅,{∅}}} = Pot(2)
      ...
      Potenzmengen sind auch interessant, u.a. weil die Kardinalität einer Menge immer ungleich der Kardinalität ihrer Potenzmenge ist.
      + - BSP für Potzenmengen
      - M:={1,2,3}
        Pot(M) = {{}, {1},{2},{3}, {1,2},{1,3},{2,3}, {1,2,3}}
      Bem: A-B = A ∩ c(B)
    Die (aktuelle) Bezeichnung 2^A für die Potenzmenge beruht wohl aus folgendem Satz:
    + - Satz: Für endliche Mengen A gilt |2^A| = 2^|A|
    - Bew: Sei OBdA A = {a_1,...a_n}, habe also n Elemente
      Für jede Teilmenge von A hat man für jedes Element a_i die Wahl,
      es hinzuzunehmen oder nicht.
      Die leere Menge ergibt sich dann z.B, wenn man kein Element hinzunimmt,
      für A selbst nimmt man jedes Element dazu, für die einelementigen Teilmengen
      nimmt man jeweils das eine Element, etc.
      Insgesamt ergeben sich so 2ⁿ Möglichkeiten für die Teilmengen - q.e.d.
- + - Mengenalgebra
  - + - Es gelten folgende Zusammenhänge
    1. c(c(A))=A - Doppletes Koplement
    2. c(A ∪ B) = c(A) ∩ c(B), c(A ∩ B) = c(A) ∪ c(B) - DeMorgan’sche Regeln
    3. A ∪ B = B ∪ A, A ∩ B = B ∩ A - Kommutativgesetze
    4. A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C - Assoziativgesetzt
    5. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) , A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) - Distriutivgesetze
    6. A ∪ A = A, A ∩ A = A - Idempotenzgesetze
    7. A ∪ ∅ = A, A ∪ U = U - Identitäsgesetze
    8. A ∪ c(A) = U, A ∩ c(A) = ∅ - Inversionsgesetzt
    9. A ∪ U = U, A ∩ ∅ = ∅ - Dominanzgesetzt
    10. A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A - Absorptionsgesetzt
    - Alle diese Gesetze kann (und sollte) man natürlich beweisen. Gleichheit bei Mengen zeigt man
      meist am einfachsten elementweise für beide Richtungen, d..h:
      
      Um die Behauptung A=B zu zeigen, zeige ich
      1. für alle Elemente x aus A gilt: x ist ein Element von B
      2. für alle Elemente x aus B gilt: x ist ein Element von A
      
      Gern wird eine Richtung vergessen.
      BSP: Beweis des ersten Identitiäsgesetzes (7):
      zu zeigen: A ∪ ∅ = A,
      1) x∈(A ∪ ∅) -> x ∈{e| e∈A oder e∈∅} -> (da ∅ keine Elemente ethält) x∈A
      2) x∈A -> x∈{e|e∈A oder e∈∅ } -> x∈(A ∪ ∅)
      - q.e.d.
      Man kann diese Gesetzt auch über Zugehörigkeitstabellen (vgl.. Wahrheitstabellen) beweisen.
      Die ZUgehörigkeit ist der Wert der charakteristischen Funktion, 0 bzw. 1.
      BSP: Gesetz 9:
      Unterschiedlikche Möglichkeiten für die Zugehörigkeit
      gibt es hier nur bei A:
      
      A    U     ∅        A ∪ U     A ∩ ∅
      ---------------------------
      1    1     0            1            0
      0    1     0            1            0
      ---------------------------
    Man kann damit viele Zusammenhänge einfach nachrechnen
    BSP: c(A-B)=c(A) ∪ B
- + - Relationen und Funktionen
  - Teilmengen des Kreuzproduktes drücken Beziehungen zwischen den Elementen aus, und
    können nach diversen Eigenschaften klassifiziert werden. Spezielle (linkseindeutige) Beziehungen dieser Form sind die Funktionen, einer der zentralen Begriffe der Mathematik.
    + - Def.: Seien A und B, und für n ∈ IN seien
          A_1, A_2, ... A_n Mengen
    1)   Eine Teilmenge R ⊆ A x B heißt (binäre) Relation
          von A und B.
          Für zwei Elemente a aus A, b aus B schreibt man
          statt (a,b) ∈ R meist kurz: aRb
          Ist A=B, spricht man auch von einer Relation auf A.
    2) Eine Teilmenge R ⊆ A_1 x A_2 x ... A_n heißt
         (n-Stellige) Relation über A_1, ... und A_n.
    - Beispiele
      Für geordnete Zahlenmengen sind =, <, <=, ... beliebte
      Beispiele von Relationen - so geläufig, das man sie meist
      gar nicht als Teilmengen sieht:
      3 < 4 wird meist nicht interpretiert als (3,4) ∈<, < ⊆ (NxN)
      Für Wörter über einem Alphabet kann man z.B. die nützliche Relation "ist Anfangswort von" definieren.
      Verwandschaftsbeziehungen bei Menschen sind Relationen - "ist Tante von", "ist Elternteil von", "Ist Kind von", ...
      Relationale Datenbanken bestehen im wesentlichen aus
      mehrstelligen Relationen, die den Zusammenhang der Daten herstellen.
      Sie sind in Tabellen geordnert, die wesentlichen Operationen sind
      - project = Wähle Teilspalten einer Tabelle
      - select   = Wähle aus einer Tabelle die Einträge,
                      die angegebenen Bedingungen genügen, und
      - join      = verknüpft Werte anhand von korrespondierenden Werten
    + - Eigenschaften von Relationen
    - + - Def (transitv, reflexiv, symmetrisch, ...): Eine Relation R über MxM heißt genau dann
      1. symmetrisch, wenn aRb → bRa
      2. antisymmetrisch, wenn (aRb ∧ bRa) → a=b
      3. transitiv, wenn (aRb ∧ bRc) → aRc
      4. reflexiv, wenn ∀ a∈M aRa
      5. Aequivalenzrelation, wenn sie symmetrisch, reflexiv und transitiv ist.
      - BSP: Die Relation "ist Nachkomme von" ist
        - nicht symmetrisch
        - nicht antisymmetrisch
        - transitiv,
        - nicht reflexiv
        auf einer Menge von Personen.
        BSP: Die Relation "ist Teiler von" auf den natürlichen Zahlen ist
        - nicht symmetrisch
        - antisymmetrisch
        - transitiv
        - reflexiv
        
        BSP: = ⊆ NxN
        ist das bekannteste Beispiel für eine Aequivalenzrelation.
        
        Interessanter sind z.B. die
        Aequivalenzklassen der modulo-Division (mit einer festen Zahl,)
        z.B. sind z.B. 2,5,8,11, ... aequivalent modulo 3,
        gehören also zur geichen Aequivalenzklasse.
        BSP: <, <=, ^2, ...
        Def. Für eine Menge M und eine Aequivalenzrelation A
        ist für jedes Element x aus M die
        Aequivalenzklasse Equiv(x,A) definiert als
        die Menge der zu x aequivalenten Elemente, also
        Equiv(x,A) := {y ∈M| xAy }
        Satz: Aequivalenzklassen sind gleich oder haben einen leeren Schnitt
        Bew: Sei X:=Equiv(x,A) und Y:=Equiv(y,A).
        1) Wenn der Schnitt von X und Y leer ist, ist der Satz erfüllt.
        2) Es gebe also nun ein w ∈ (X∩Y).
        
        Sei nun z∈X beliebig.Dann gilt
        (a) xAz → zAx und xAw → zAw. Weiter gilt
        (b) yAw → wAy
        Mit (a) und (b) zusammen folgt
        zAy → yAz → z∈Y, also zusammen X⊆Y.
        Analog zeigt man Y⊆X - q.e.d.
        Für jede Aequivalenzrelation bilden die (diskunkten) Aequivalenzkalssen eine Partition der Ausgangsmenge, d.h. die Vereinigung aller Aequivalenzlklassen einer Aequivlanezrelation ergibt die Gesamtmenge.
      Def. Relationen, die reflexiv und transitiv sind, nennt man auch Quasiordnungen
      + - Def. Eine Relation R über einer Menge M,
      die reflexiv, transitiv und antisymmetrisch ist,
      heißt (partielle) Ordnung oder
      Halbordnung über M.
      
      In einer Halbordnung R heisst ein Element x
      mit xRy Vorgänger von y.
      Gibt es kein z mit xRz und zRy, so heißt
      x direkter Vorgänger von y,
      - BSP:
        Sei M:={a,b,c,d,e}, dann ist
        R:={(a,a),(b,b),(c,c),(d,d),(e,e),
            (a,d), (b,a),(c,d), (d,e)
            (a,e), (c,e)}
        ist eine Halbordnung auf M.
        Halbordnungen kann man in "Hasse-Diagrammen" aufzeichnen.
        Knoten sind dabei die Elemente der Menge,
        ein direkter Vorgänger wird unter seien Nachfolger geschrieben, und
        beide mit einer Kante verbunden
        
        BSP
        
               e
               |
               d
               /\
              / \
             a   c
             |
             b
        BSP: "⊆" ist eine Halbordnung auf beliebigen Mengen
      Def. Eine Halbordnung R auf M heißt totale Ordnung auf M, wenn für alle x,y aus M xRy oder yRx gilt
      + - Def. (trans.-ref. Hülle) Sei R eine Relation auf einer Menge M.
      Dann ist die transitiv-reflexive Hülle R^* von R definiert als die
      kleinste Menge mit folgenden Eigenschaften:
      1. ∀a∈M: (a,a)∈R^*
      2. R⊆R^*
      3. Falls (a,b) und (b,c) in R^* liegen, so liegt (a,c) in R^*
      Statt von trans.-ref. Hülle spricht man auch von
      transitiv-reflexiver Fortsetzung
      - Es gilt:
        (a,b)∈R^* genau dann, wenn
        
        a=b, oder
        
        Es gibt ein n∈N₀ und x₁,...x_n mit a=x₁ R x₂ R ... R x_n=b.
        
        Obige Eigenschaft wird auch oft zur Definition herangezogen
        BSP: In der Informatik wird das recht oft "mechanisch" interpretiert,
        als beliebig häufige Anwendung eines Prozesses hintereinander.
        Sei z.B. "--" der Prozess "liefere den alphabetisch nächsten Buchstaben",
        alsp a--b--c ...
        dann schreibt man z.B. a --^* u
      Def (total, eindeutig): Eine Relation R über AxB heißt
      linkstotal, wenn gilt: ∀a∈A ∃b∈B (a,b)∈R
      rechtstotal, wenn gilt: ∀b∈B ∃a∈A (a,b)∈R
      linkseindeutig, wenn gilt: ∀a,c∈A und b∈B mit aRb und cRb gilt a=c
      rechtseindeutig, wenn gilt: ∀a∈A und b,c∈B mit aRb und aRc gilt b=c
    + - Eigenschaften von Funktionen
    - + - Def. (Funktion)
      1. Eine rechtseindeutige Relation f über AxB heißt
        (partielle) Funktion oder Abbildung (von A nach B)
      2. Eine linkstotale Funktion f über AxB heißt
        totale Funktion oder einfach Funktion von A nach B
      3. Statt (a,b) ∈ f ⊆ MxN schreibt man bei Funktionen üblicherweise f: M→N, b=f(a) oder a→f(a)
      - BSP:
        "quadriert ist" - in Zeichen: f(x)=x² - auf den reellen Zahlen ist eine Funktion, also linkstotal und rechtseindeutig.
        
        BSP:
        Die Relation "ist Quadrat von" - in Zeichen: f(x)=sqrt(x)
        auf den reellen Zahlen ist keine Funktion, da sie nicht linkstotal ist.
        Beschränkt am Definitions- und Wertebereich auf die
        positiven reellen Zahlen, ist sie sogar eine bijektive Funktion.
      Def. Eine rechtstotale Funktion heißt surjektiv
      + - Def. Eine linkseindeutige Funktion heißt injektiv
      - BSP: die Fakultätsfunktion ! auf den natürlichen Zahlen,
        die induktiv definniert ist durch:
        
        1) 0! := 1
        2) für n>0 ist n! := n * (n-1)!
        
        ist injektiv, aber nicht surjektiv.
        z:B. haben alle ungeraden Zahlen >2 kein Urbild.
      + - Def. Eine injektive und surjektive Funktion heißt bijektiv
      - BSP:
        f: Z→ N₀ mit
        
        f(0) := 0
        
        f(n) := (-1)*2n, falls n<0
        
        f(n) := 2n+1, falls n>0
        
        ist eine bijektive Funktion der ganzen in die natürlichen Zahlen.
      Def. (Urbild) Zu einer Funktion f: N→M ist das Urbild eines Elementes b∈M definiert durch
      f^-1(b):={a∈N | f(a)=b}
      Für injektive Funktionen ist das Urbild eindeutig, man redet dann auch von Umkehrfunktion.
    + - Darstellung
    - Endliche binäre Relationen kann man natürlich
      auf mehrer Arten darstellen, z.B
      - durch Aufzählung der Paare
      - grafisch durch verbindende Linien, oder besser Pfeile
        (eine Relation ist ja i.A. gerichtet)
      + - Interessant ist auch eine Darstellung als Matrix mit Werten 0 und 1:
      Wenn A = {a_1, ... a_n} und B={b_1,...b_m}, kann man
      tabellarisch aufschreiben
      
             | b_1    b_2    b_3 ... b_m
      ---------------------------
      a_1 | r_11 r_12   r_13 ... r_1m
      a_2 | r_21 ...
      ...    | ...
      a_n | r_n1 ...                    r_nm
      
      und R=(r_ij), r_ij=1 falls a_iRb_j, und r_ij=0 sonst.
      
      Relexivität und Symmetrie kann man dann direkt sehen.
      - BSP: Sei M:={a,b,c,d,e},
        R:={(a,a),(b,b),(c,c),(d,d),(e,e),
            (a,d), (c,d), (d,e)
            (a,e), (c,e)}
        
        Das kann man auch darstellen als
        
              a    b    c    d   e
        -------------------
        a | 1    0    0    1   1
        b | 0    1    0    0   0
        c | 0    0    1    1   1
        d | 0    0    0    1   1
        e | 0    0     0   0   1
    + - Charakteristische Funktion
    - Geht man von einem Universum U aus, kann man
      eine Menge M aus diesem Universum auch über eine
      Zugehörigkeitsfunktion, ihre charakteristische Funktion Χ_M, definieren.
      
      Es gilt Χ_M ⊂(Ux{0,1}) und Χ_M(m)=1 ↔ m∈M
- + - endliche und unendliche Mengen
  - Für endliche Mengen M ist die Kardinalität - |M| - einfach zu bestimmen,
    indem man die Elemente zählt,
    Für unendliche Mengen sollte man meinen, das die einfach immer
    die gleiche Kardinalität - eben ∞ - haben.
    Überlegt man aber, das Mengen A und B dann offenbar gleich gross sind,
    wenn ich eindeutig jedem Element der einen genau ein Element der anderen
    zuordnen kann, also ein bijektive Abbildung zwischen ihnen besteht,
    dann ergeben sich unterschiedliche Unendlchkeiten!
    + - Abzählbarkeit - Alef 0
    - Die "kleinste" Unendlichkeit ist die Kardinalität
      der natürlichen Zahlen - ℵ₀.
      Man nennt die Mengen mit Bijektionen in
      die natürlichen Zahlen abzählbar unendlich.
      + - Beliebte Beispiele sind
      - die Menge der Quadratzahlen {n²|n aus IN}, Bijektion n²->n
      - die Menge der ganzen Zahlen Z, Bijektion z.B.:
        f(0) = 0,
        f(z) = 2z     für z>0,
        f(z) = 2z-1 für z<0
      - die Menge der Primzahlen
      - die Menge der rationalen Zahlen Q
      (das ist ggf. überraschend, weil man dort "mehr" Elemente vermutet, und kann
        mit Cantors 1. Diagonalargument bewiesen werden.)
      - Theorem: Die Menge der rationalen Zahlen Q ist abzä̈hlbar unendlich
        Beweis: Cantors erstes Diagonalargument
        Es reicht zu zeigen, dass alle positiven rationalen Zahlen abzählbar unendlich sind.
        Ordne dazu die Brüche                           und durchlaufe sie
                                                                     im Diagonalen-Zickzack, Schema:
            1/1    1/2    1/3    1/4     1/5 ...             1     2     6     7    ...
            2/1    2/2    2/3    2/4     2/5 ...             3     5     8     ...
            3/1    3/2    3/3    3/4     3/5                  4     9 ...
            4/1    4/2    4/3    4/4     4/5                 10   ...
            ...                                                        ...
        Kürzbare Bruche werden übersprungen, man erhält eine Abzählung der
        positiven rationalen Zahlen: 1, 1/2, 2, 3, 1/3, 1/4, 2/3, 3/2, 4, 5, ....
        q.e.d.
        
        Auf einer 1999 veröffentlichten Liste der 100 wichtigsten mathematischen
        Sätze findet sich diese Aussage auf Platz 3.
        
        ~ http://personal.stevens.edu/~nkahl/Top100Theorems.html
    + - Überabzählbarkeiit- Alef
    - + - Eine weitere Unendlichkeit ist die Kardinalität
      der reellen Zahlen - ℵ.
      Weil man für jede Aufzählung immer noch ein Element "dazwischen"
      findet, nennt man sie auch überabzählbar unendlich.
      - Satz: Das offene Einheitsintervall der reellen Zahlen - [0,1( - ist überabzählbar
        Beweis: Cantors 2. Diagonalargument:
        Angenommen, das Intervall [0,1( sei abzählbar.
        Dann ich alle Elemete in einer Folge
        
        z_1 = 0, a_11 a_12 a_13 a_14 ...
        z_2 = 0, a_21 a_22 a_23 a_24 ...
        z_3 = 0, a_31 a_32 a_33 a_34 ...
        z_4 = 0, a_41 ...
        ...
        
        in der üblichen Dezimaldarstellung aufzählen. Wir konstruieren nun
        eine neue Zahl x = 0, x_1 x_2 x_3 ... aus den Diagonalelementen,
        und zwar so:
        Für i=1,2,... ist
        x_i := 4 falls a_ii = 5,
        x_i := 5 sonst
        
        Dann ist unsere konstruierte Zahl x offenbar im Intervall [0,1( enthalten,
        aber nicht in der Folge z_1, z_2, ..., denn sonst wäre ja
        für einen Index j der Wert x_j = a_jj, und das ist per Konstruktion
        ja nicht der Fall.
        Wir haben also einen Widerspruch zur Annahme erhalten,
        und bewiesen, das [0,1( überabzählbar ist.
        
        q.e.d.
    + - Die Kontinuumshypothese
    - Satz: Es gibt keine Menge, deren Mächtigkeit zwischen der
      Mächtigkeit der natürlichen Zahlen und
      der Mächtigkeit der reellen Zahlen liegt.
      
      Diese These stammt - etwas anders formuliert - von G. Cantor.
      Sie ist ist das 1. Problem auf David Hilberts Liste der 23 wichtigsten
      ungelösten Probleme.
      
      Inzwischen ist klar, das sie unter ZFC nicht beweisbar ist, d.h. sowohl die
      Annahme der Kontinuumshypothese wie auch deren Verneinung führen
      im üblichen Axiomensystem der Mathematik nicht zu Widersprüchen.
      ~ Wie real ist das Unendliche? (Spektrum der Wiss. 2/2009)
- + - Mengen als Sprachen; Wortproblem
  - In der Theorie der Berechenbarkeit geht es darum, zu entscheiden, welche Probleme
    überhaupt gelöst werden können. Das läßt sich so formalisieren , das die Probleme
    (universelle) Maschinen und die Lösungen als Eingaben dazu modelliert werden.
    Man redet dann statt von korrekten Lösungen auch von (Wörtern der) Sprache,
    die die Maschinen akzeptieren.
    Letztlich kann man die Lösungen L für jedes Problem P dann als Menge schreiben:
    
    L := { l | l löst das Problem P }.
    
    Wenn man eine effiziente Maschine angeben kann, die entscheiden kann, ob
    eine Lösung zu L gehört, ist das Problem entscheidbar.
    Stichworte: Churche These, kontextfreie Sprachen, endliche Automaten, Kenllerautomaten, Turing-berechenbar, Chomsky-Hierarchie

p	q	p∧q
w	w
w	f
f	f
f	f

+ - Kombinatorik

Wir haben nun die Werkzeuge für interessantere Anwendungen.
Eine davon ist die Kombinatorik: die Beschäftigung mit Kombinationen endlicher Teilmengen endlicher Mengen, und das Zähen der Kombinationsmöglichkeiten unter verschiedenen Voraussetzungen.

+ - Urnenmodelle

Viele Kombinatorische Probeme lassen sich als Ziehen von Elementen aus einer Urne modellieren.

Hier ergeben sich vier Varianten aus den beiden Optionen:

1. Man legt Elemente nach dem Ziehen in die Urne zurück, oder behält sie (Ziehen mit / ohne Zurücklegen)

2. Die Reihenfolge der gezogenen Elemente spielt eine Rolle, oder auch nicht.

Bezeichnungen (Wählen von k Objekten aus n):

geordnet ungeordnet

mit Zurücklegen: k-Stichprobe: n^k k-Auswahl: (n+k-1) über k

ohne Zurücklegen: k-Permutation: n!/(n-k)! k-Kombination: n über k

	geordnet	ungeordnet
mit Zurücklegen:	k-Stichprobe: n^k	k-Auswahl: (n+k-1) über k
ohne Zurücklegen:	k-Permutation: n!/(n-k)!	k-Kombination: n über k

+ - BSP:

- Ziehen von zwei Karten aus einem Kartenstapel von verschiedenen Karten
bei MauMau: Ziehen ohne Zurücklegen, Reihenfolge unwichtig
- Lotto 6 aus 49: Ziehen ohne Zurücklegen, Reihenfolge unwichtig
- Los mit 6-stelliger Losnummer: 6x Ziehen mit Zurücklegen aus 0-9, Reihenfolge wichtig
- Würfeln mit 2 Würfeln (z.B. Maier): 2x Ziehen mit Zürücklegen aus 1-6, Reihenfolge unwichtig
- Mögliche Wörter mit 6 verschiedenen Buchstaben: 6x Ziehen ohne Zurücklegen, Reihenfolge wichtig.

+ - k-Stichprobe (ZO)

Ziehen mit Zurücklegen, geordnet
Das Ergebnis ist ein k-Tupel. Für jede Position des k-Tupels habe ich
n Möglichkeiten, insgesamt k mal
n*n*...*n = n^k Möglichkeiten.
Für M={1,2,3} und k=2 ergeben sich die 9 Möglichkeiten

(1,1), (1,2), (1,3),
(2,1), (2,2), (2,3),
(3,1), (3,2), (3,3)
BSP: 6-stellige Zahlenlose habe natürlich wie erwartet 10⁶ = 1 000 000 Möglichkeiten.
6-stellige Wörter über {a,b,c} gibt es dagegen 3⁶ = 729 verschiedene.

+ - k-Permutation (zO)

Ziehen ohne Zurücklegen, geordnet
Das Ergebnis ist wieder ein k-Tupel. (,...,)
Für die 1. Position habe ich n Möglichkeiten.
Für die 2. Position habe ich nur noch (n-1) Möglichkeiten.
Für die 3. Position habe ich nur noch (n-2) Möglichkeiten
...
Für die k. Position habe ich nur noch (n-k+1) Möglichkeiten.

Zusammen: P(n,k) := n(n-1)(n-2)...(n-k+1) = n!/(n-k)! Möglichkeiten
Für M={1,2,3} und k=2 ergeben sich die 6 Möglichkeiten

(1,2), (1,3),
(2,1), (2,3),
(3,1), (3,2)
BSP: 5-stellige Wörter über {a,b,...,z}, in denen jeder Buchstabe nur ein mal vorkommt, gibt es P(26,5) = 26*25*24*23*22 = 7893600 verschiedene.

+ - k-Kombination (zo)

Ziehen ohne Zurücklegen, ungeordnet
Das Modell entspricht der Bildung von k-elementigen Teilmengen
einer n-elementigen Menge, da ja die Reihung keine Rolle spielt,
aber Elemente nur ein mal auftreten dürfen.

Als Grundlage können wir dann die k-Permutation annehmen, müssen aber die
doppelt gezählten Elemente wieder abziehen.

Eine Anordung einer k-elementigen Menge ist eine k-Permuation
der Menge, also gibt es dafür P(k,k) = k!/(k-k)! = k! Möglichkeiten der Anordnung

Das geht in die Formel zur k-Permutation als Produkt ein, wir müssen
es also für die k-Kombinaton herausdividieren, und kommen zu

C(n,k) := (1/k!)*P(n,k) = (1/k!)*(n!/n-k)!) = n! / ( k!(n-k)! ) =: (

n

k

)

Für M={1,2,3} und k=2 ergeben sich die 3 unterscheidbaren
Möglichkeiten

[1,2], [1,3], [2,3]

Hier soll [,] andeuten, das es anders als bei (,) nicht auf
die Reihung ankommt.

+ - Den Bruch

(

n

k

)
nennt man auch Binomialkoeffizient,
da er beim Ausmultiplizieren der binomischen Formel
als Koeffizient der Einzelprodukte auftritt:

(a+b)ⁿ =∑_k=0,...,n (

n

k

) a^kb^(n-k)
- Man beweise die Formel meist durch Induktion über n, man kann die Binominalkoeffizienten nun aber auch kombinatorisch herleiten:
  Es ist ja (a+b)ⁿ = (a+b)(a+b)....(a+b).
  Es ergeben sich Produkte der Form a^kb^n-k.
  
  Wie oft kann nun jedes Produkt auftreten?
  Nun, das ist aequivalent zu dem Probem, wie oft ich k a-s auf n Positionen
  verteilen kann, und das ist wiederum genau die Anzahl der k-elementigen
  Teilmengen einer k-elementigen Menge (der Positions-Indices),
  also n über k.
  
  Insgesamt ergibt sich die binomische Summmenformel.
BSP: Aus {a,...,z} kann ich auf C(26,5) = 26*25*24*23*22 / (5*4*3*2*1) = 7893600 / 120 = 65780 verschiedene Weisen 5 Buchstaben entnehmen.

Analog berechnet sich die Zahl der Möglichkeiten beim Zahlenlotto 6 aus 49: C(49,6) = 49*48*47*46*45*44 / (6*5*4*3*2) = 13.983.816

+ - k-Auswahl (Zo)

Ziehen mit Zurücklegen, ungeordnet
Zur Bestimmung der Möglichkeiten starten wir hier bei den Überlegungen zur der k-Stichprobe. Wir bekommen wieder k-Tupel, Da hier aber die Reihung egal ist, können wir z.B. die Tupel der Stichprobe der Grösse nach ordnen, und dann die doppelten nur einfach zählen.

Wie viele Tupel bleiben dann? Nun, jedes Tupel kann man eindeutig beschreiben
durch eine Folge von zwei unterschiedlichen Zeichen, z.B. '*' und '|'.

* bedeutet das Ziehen eines Elements der gleichen Größe,
| bedeutet den Wechsel zum nächstkleineren Element.

z.B: **|*||*| bedeutet ich habe 4 mal gezogen,. davon 2x das grösste Element, 1x das zweitgrösste, 0x das drittgrösste, 1x das viertgrössste, und 0x das kleinste.

Für jedes Element meines Ausgangsmenge bis au das kleinste bekomme ich also einen |, für jeden Zug einen *, insgesamt n-1+k Zeichen.

Alle möglichen Verteilungen der k *-Symbole auf
n+k-1 Positionen liefern mit also alle möglichen Ergebnisse
der Ziehung k-Auswahl. .
Das war ja gerade unserer k-Kombination aus (n+k-1)-Elementen,
wir bekommen also

(

n+k-1

k

) Möglichkeiten für die k-Auswahl aus n Elementen

Für M={1,2,3} und k=2 ergeben sich die 6
unterscheidbaren
Möglichkeiten

[1,1], [1,2], [1,3],
        [2,2], [2,3],
                [3,3]

Hier soll [,] andeuten, das es anders als bei (,) nicht auf
die Reihung ankommt.
BSP: Wenn man sich eine Getränkekiste mit 12 Flaschen aus 2 Geschmacksrichtungen zusammenstallt, hat man dafür (12+2-1)! / ( 2! 11! ) = 12*11/2 = 66 Möglichkeiten.

+ - Prinzipien

+ - Siebformel
- Satz: Sind A und B endliche Mengen, so gilt
  |A∪B| = |A| + |B| - |A∩B|
  Bew.: Seien A={a_1,...,a_n,s_1,...,s_k} und B={b_1,...,b_l,s_1,...,s_k}.
  Dann ist |A|=n+k, |B|=l+k, |A∪B| = n+k-l , |A∩B|=k,
  also |A| + |B| - |A∩B|= n+k + l+k - k = n+k+l - q.e.d.
  + - Summenregel
  - Für disjunkte Mengen A, B gilt dann natürlich
    |A∪B| = |A| + |B|
    
    + - BSP: Wenn in der Bücherei 10 Bücher über Logik und 5 über Kombinatorik
    verfügbar sind, habe ich 15 Möglichkeiten, zu jedem Thema je ein Buch
    auszuleihen.
    - Achtung: ich kann 50 verschiedene Kombinationen ausleihen, aber das war nicht die Anforderung
    + - BSP: Die Anzahl der 5-elementigen Teilmengen von {1,.2..,10}, die
    entweder 1 oder 2, aber nicht beide zusammen enthalten, ist 140.
    - Bew:
      Nun - die einen Teilmengen bestehen aus
      {1} vereinigt mit einer vierelementige
      Teilmenge von {3,..,10}.
      Davon gibt es (ungeordnetes Ziehen
      ohne Zurücklegen) 8!/(4!*4!).
      
      Analog geht es mir der 2. Wir haben also zusammen
      
      2*(8*7*6*5)/4*3*2 = 8*7*6*5 / 12 = 7*20=140
+ - verallg. Siebformel
- Die Siebformel lässt sich weiter verallgemeinern:
  Man muss immer wieder alternierend zuviel gezählte Elemente
  abziehen bzw. zuviel abgezogene Elemente dazuzählen:
  + - Satz: Für endliche Mengen A₁,...,A_n gilt:
  |∪_i=1,...,nA_i| = Σ_r=1,...,n(-1)^(r-1) Σ_{1≤i_1<...<i_r≤n}|∩_j=1,...,rA_{i_j}|
  - Bew: durch Induktion oder kombinatorisch, z.B.[Steger]
  - BSP r=3
  - + - BSP: Anzahl der durch 2,3, oder 5 teilbaren Zahlen < 100
    - Sei A_k := {n aus 1,...100: k teilt n}.
      Dann suchen wir |A_2 ∪ A_3 ∪ A_5|
      
      Es ist |A_k| = floor(100/k) (also die grösste ganze Zahl <= 100/k),
      denn jede k-te natürliche Zahl ist durch k teilbar.
      
      Es ist ausserdem
      A_2 ∩ A_3 = A_6,
      A_2 ∩ A_5 = A_10
      A_3 ∩ A_5 = A_15, und
      A_2 ∩ A_3 ∩ A_5 = A_30, mit der Siebformel
      
      |A_2 ∪ A_3 ∪ A_5| = |A_2|+|A_3|+|A_5| - |A_6|-|A_10|-|A_15| + |A_30|
      = 50 + 33 + 20 - 16 - 10 - 6 + 3 = 103 -32 + 3 = 74
  + - Ganz allgemein spricht man vom Prinzip der Inklusion und Exklusion: Man kann zunächst zu viel (oder zu wenig) summieren, muss dann aber das doppelt gezählte wieder abziehen bzw. das noch nicht gezählte dazu summieren.
  - BSP Platzierungen
    
    Wenn man 5 Personen A B C D und E um einen Tisch platzieren will, hat man 5! Möglichkeiten (Ziehen ohne Zurücklegen, geordnet)
    
    Was aber, wenn der Tisch rund ist? Dann ist die Ausrichtung der Positionierung egal, d.h. die obige Rechnung leifert uns für jede mögliche Tischordnung fünf gleiche Lösungen. Für den runden Tisch ergeben sich damit 5!/5 = 4! = 24 Lösungen.
    
    Man kann das auch anders modellieren: Für einen runden Tisch kann ich die erste Platzierung oBdA fest wählen, für die übrigen vier Plätze bleiben dann 4! Möglichkeiten.
    + - BSP: Was, wen man runden Tisch ein Paar dabei ist, das unbedingt zusammen sitzen muss?
    - Man modelliert dann mit 4 Personen
    Def: [n] := {1,2,...,n}
    + - BSP Derangement-Zahlen bzw. fixpunktfreie Permutationenen:
    - Nach einer Wohnheimparty legen sich die n Bewohner (allein!) ins nächstbeste Bett. Wie viele Möglichkeiten gibt es, das keiner in seinem Bett liegt?
      
      Den Einzelfall modelliert eine (bijektive) fixpunktfreie Permutation
      
      pi: [n] --> [n] mit pi(i) ≠ i;
      
      Uns interessiert die Anzahl solcher Permutationen. Direkt ist das schwer zu bestimmen,
      aber einfach zu bestimmen sind:
      
      1. die Anzahl der Bijektionen von {1,...,n} - das sind genau n! (zO)
      2. die Anzahl xi_n der Bijektionen mit mindestens einem Fixpunkt (s.u)
      
      Die Derangement-Zahlen ergeben sich dann aus n! - xi_n
      Sei A_i := { pi: [n]->[n] | pi(i) = i } Dann liefert uns die Siebformel das Ergebnis für
      
      xi_n = |∪_i=1,...,nA_i| = Σ_r=1,...,n(-1)^(r-1) Σ_{1≤i_1<...<i_r≤n}|∩_j=1,...,rA_{i_j}|
      
      In ∩_j=1,...,rA_{i_j} sind genau die
      Permuationen mit pi(i_J) = i_J für alle j=1,..,r. die leigen also fest, die
      übrigen sind nicht eingeschränkt. Damit gibt es dort (n-r)! Möglichkeiten.
      Davon gibt es C(n,r) Kombinationen.
      Mit der Überlegung erhalten wir:
      
      xi_n = Σ_r=1,...,n(-1)^(r-1) (n! / (r!(n-r)!) ) (n-r)! = Σ_r=1,...,n(-1)^(r-1) (n! / r!)
      
      Für die Derangement-Zahlen D_n ergibt sich zusammengefasst:
      
      D_n = n! ( 1 -1 + 1/2! - 1/3! + 1/4! -+ ... + (-1)ⁿ/n!
+ - Produktregel
- Wenn man eine Sache in zwei Schritten erledigen kann, und für den ersten Schritt gibt es n Möglichkeiten, und für jede dieser Schrittvarianten gibt es m Möglichkeiten für den zweiten Schritt, dann gibt es n*m Möglichkeiten, das Ganze auszuführen.
  BSP: Für eine Vorführung des Schauspiels Romeo und Julia kann der Regisseur
  aus 5 Frauen für die Rolle der Julia und 3 Männern für die Rolle des Romeo
  wählen. Er hat dann 5*3 = 15 verschiedene mögliche Paare.
  + - Satz: Für endliche Mengen A_i gilt:
  
  | A_1 x ... x A_n | = |A_1| * ... * |A_n|
  - Bew: z.B. durch Induktion über n
    BSP: Die Anzahl der vierstelligen Zahlen, deren i-te Ziffer eine durch i teilbare Zahl ist, ist 600
    BSP: Ein 32-bit Betriebssystem (bzw. eine 32-Bit Speicherzelle) kann maximal 4.294.967.296 Adressen ansprechen
+ - Doppeltes Abzählen
- Für eine Relation R aus XxY kann man die Kardinalität
  auf zwei Wege bestimmen:
  1. Man summiert über alle linken Seiten alle Auftreten der rechten Seiten ("Zeilensumme"):
    |R| = ∑_x∈X|{y : (x,y) ∈ R}|
  2. Man summiert über alle linken Seiten alle Auftreten der rechten Seiten ("Spaltensumme"):
    |R| = ∑_y∈Y|{x : (x,y) ∈ R}|
+ - Schubfachprinzip
- Satz: verteilt man n Objekte auf m Schubladen, und ist n>m, so landet in mindestens einer Lade mehr als ein Objekt
  Bew: Annahme, es landen max. 1 Objekt in jeder Lade -> Es gibt max. m Objekte -> Widerspruch
  Das Prinzip heisst englisch "pigeonhole principle"
  Bsp: von 13 Personen haben mindestens zwei im gleichen Monat Geburtstag.
  Def: Für reelle x ist ⌈x⌉ definiert als die kleinste
  ganze Zahl, die grösser oder gleich x ist:
  ceiling(x) ;= ⌈x⌉ := min {n∈Z| n ≥ x}
  Satz: verteilt man n Objekte auf m Schubladen, und ist n>m, so landen in mindestens einer Lade mindestens ceilng(n/m) Objekte.
  
  Satz (Verallgemeinertes Schubfachprinzip):
  Sei f: X->Y eine Funktion, so gibt es ein y aus Y mit
  |f^-1(y)| ≥ ceiling( |X|/|Y| )
  Bew:
  + - BSP: (Spezialfall des Satzes von Ramsey)
  In einer Gruppe von 6 Personen gibt es entweder drei, die sich kennen,
  oder drei, die sich alle nicht kennen. ("kennen" ist dabei symmetrisch)
  - Bew:
    Sei die Gruppe P={p1, p2, ... , p6}, und
    kenn1 : P-{p1} --> {0,1} die "kennen"-funktion für p1.
    Dann liegen im Urbild von 0 oder 1 mindestens ceiling(5/2) = 3 Elemente.
    Wir nehmen mal an, das das für 1 der Fall ist (im anderen Fall agrumentiert man
    analog mit "nicht kennen"), und numerieren mal so, das zumindest p2,p3,p4 darin liegen.
    
    Nun haben wir folgende Fälle:
    1. p2,p3, und p4 kennen sich alle nicht - dann haben wir drei Personen, die sich alle nicht kennen - fertig.
    2. OBdA p2, p3 kennen sich. Da sie aber auch beide p1 kennen, haben wir drei Personen, die sich kennen - auch fertig.
    - q.e.d.

+ - Permutationen

Permutationen, also bijektive Abbildungen endlicher Mengen auf sich selbst, waren uns ja schon in den vorigen Abschnitten nützlich. Hier beschreiben wir sie genauer, und untersuchen einige speziellen Eigenschaften.
Zunächst. nur der Vollständigkeit halber, die Definition:

Def: Eine bijektive Abbildung pi : M -> M
einer endlichen Menge M auf sich selbst heisst Permutation.
+ - Warum sind Permutationen, insbesondere Permutationen auf [n], interessant?
Die Elemente jeder endlichen Menge kann man numerieren,
d.h. man kann für jede endliche Menge M mit n Elementen
eine bijektive Funktion num : M --> [n] angeben.
- Genau genommen gibt es sogar n! solcher Abbildungen num
Deswegen gibt es für jede bijektive Funktion f einer
endlichen Menge M mit n Elementen eine
Permutation p auf [n] und eine Darstellung
f = num^-1 ⋅ p ⋅ num
+ - Mit dieser Identifkation reicht es, die Permutationen auf [n] zu untersuchen, um die Eigenschaften aller Bijektionen von n-elementigen Mengen herauszufinden.
- Solche Einbettungen sind ein wichtiges Hilfsmittel in vielen Bereichen, vor allem in der Algebra. Da interessiert dann auch der Strukturerhalt als zusätzliches Kriterium.
Bem: Für n aus N bilden die Permutationen auf [n] eine
symmetrische Gruppe, die mit S_n bezeichnet wird.
+ - Darstellung
- + - Matrixdarstellung
  - Man kann Argument und Wert in eine 2xn-Matrix unterienander schreiben:
    
    pi := (
    
    1 2 ... n
    
    pi(1) pi(2) ... pi(n)
    
    )
    
    Sofern wir Permutationen auf [n] betrachten, ist auch die Darstellung nur der unteren Zeile üblich. Das ist aber ggf. missdeutig:
    
    pi := (pi(1) pi(2) ... pi(n))
    BSP:
    
    pi := (
    
    1 2 3 4 5 6
    
    2 5 3 6 1 4
    
    )
- + - Zykeldarstellung
  - Wegen der Endlichkeit der Mengen landet man beim hintereinander ausführen von Permutationen eines Elements irgenwann wieder beim Startelement. Im obigen Beispiel:
    pi(1)=2, pi(2)=5, pi(5)=1 --- Zykel (1 2 5)
    pi(4) = 6, pi(6) = 4 --- Zykel (4 6)
    pi(3) = 3 --- Zykel (3)
    
    Def: Die Länge eines Zykels einer Permutation pi
    ist definiert als das kleinste n, für das
    piⁿ (i) = i für ein i aus dem Zykel gilt.
    Dabei bedeutet piⁿ die n-fache Hintereinanderausführung
    der Funktion pi, also n Auftreten von pi im Ausdruck pi(pi(...(pi(i)).
    Man kann jede Permutation also auch eindeutig durch Angabe der Zykel definieren. Die Darstellung ist dann( z_1 z_2 .... ), wobei jedes z_i ein Zykel ist.
    Für das Beispiel von oben: pi := ((1 2 5) (3) (4 6))
- + - Permutationsmatrix
  - Man kann eine Permutation von [n] auch als Abbildung ein einem n-Dimensionalen Vektorrraum sehen.
    Da nur Umsortierungen des Eingabevektors vorkommen, ist die Abbildung dann eine (n x n) - Matrix, die aus der Einheitsmatrix durch Vertauschen von Zeilen hervorgeht.
    Genauer: pi := (m_ij)_i,j=1,...,n, wobei
    m_ij = 1, falls pi(i) = j, und
    m_ij = 0 sonst
    Für das obige BSP ergibt sich folgende Matrix:
    
       0 1 0 0 0 0
       0 0 0 1 0 0
       0 0 1 0 0 0
       0 0 0 0 0 1
       1 0 0 0 0 0
       0 0 0 0 1 0
+ - Stirling-Dreieck 1. Art
- Übrigens kann (genau) eine Permutation n Zykel der Länge 1 haben,
  und relativ viele Zykel die Länge n. Genauer:
  + - Def. s_n,k bezeichnet die Anzahl
  der Permutationen über [n] mit genau k Zyklen.
  Man nennt s_n,k auch Stirling-Zahlen erster Art
  - ~ James Stirling (1692-1770)
  Da jede Permutation mindestens einen und maximal n Zykel hat, es andererseits genau n! Permutationen über [n] gibt, folgt direkt
  Satz: ∑_k=1,..,n s_n,k = n!
  Man kann auch einfach eine schöne Rekursionsformel für s_n,k herleiten,
  wenn man sich überlegt, das
  für n>0 folgt s_n,0=0 , und
  für k>n auch s_n,k=0 gilt:
  + - Satz (Stirling-Dreieck erster Art):
  Mit s_0,0:= 1 gilt
  ∀ n,k ∈ N mit n≥k ist s_n.k = s_n-1,k-1 + (n-1)s_n-1,k
  - Bew (kombinatorisch):
    Wie kann eine Permutation über [n] mit k Zyklen entstehen?
    
    Entweder entsteht sie durch Zufügen des Zyklus (n)
    zu den Permutationen mit k-1 Zyklen über [n-1].
    Das ergibt den 1. Summanden.
    
    Oder n wird in einen der k Zyklen über [n-1] hinzugefügt.
    Da die Reihenfolge bei Zykeln wichtig ist, hat man
    dafür (n-1) Möglichkeiten. Das ergibt den 2. Summanden.
    Bem: ((1 2 3 4)) = ((4 1 2 3)), aber ((1 2 3 4)) ≠ ((2 1 3 4))
    BSP für [4], und k=3
    Mir der Formel kann man ein Dreieck der Stirling-Zahlen erster Art aufbauen.
    Die Zeilennummer ist dabei das n , die Zahlposition in der Zeile das k,
    und die Zählung beginnt bei (0,0):
    
    1
    
    0 1
    
    0 1 1
    
    0 2 3 1
    
    0 6 11 6 1
    
    0 24 50 35 10 1
    
    0 120 ...
BSP: Zeichenhäufigkeiten, z.B. Variationen des Wortes COMPUTER oder KNALL

+ - Binominalkoeffizienten

Auch die Binominalkoeffizienen sind uns in diesem Kapitel schon begegnet. Sie treten bei Zählproblemen auf, und haben einige erwähnenswerte Eigenschaften
+ - Gleichungen
- Zunächst noch einmal die exakte Definition:
  + - Def: Für n,k aus N₀ und n≥k ist
  
  (
  n
  k
  ) :=
  n!
  k!(n-k)!
  - Man sieht leicht, da das grosse Werte annimmt, wenn k etwa n/2 beträgt, Für sehr kleine k oder k in der Größenordnung von n sind Nenner und Zähler nahezu gleich.
    Insbesondere gilt: (n über n) = (n über 0) = 1
  Aus der Definition und (n-(n-k)) = k folgt direkt
  Satz;
  
  (
  n
  k
  ) = (
  n
  (n-k)
  )
  
  + - Satz: Für n aus N₀ gilt:
  
  2ⁿ = ∑_k=0,...,n (
  n
  k
  )
  - Bew: Wie wir schon wissen, ist die Anzahl der
    k-elementigen Teilmengen einer n-elementigen Menge
    genau (n über k). Andererseits ist die Mächtigkeit der
    Potenzmenge, also die Anzahl aller Teilmengen einer Mengen,
    genau 2ⁿ - q.e.d.
    Bem: Der Satz lässt sich auch leicht aus der allgemeinen binomischen Formel ableiten, indem man a=b=1 setzt.
+ - Pascal'sches Dreieck
- ~ Nach dem französichen Mathematiker Blaise Pascal (1623-1662) ist die folgende Rekursionsformel für die Berechnung der Binominalkoeffizienten benannt:
  + - Satz (Pascal-Dreieck): Für n, k aus N mit n>k gilt:
  
  (
  n
  k
  ) = (
  n-1
  k-1
  ) + (
  n-1
  k
  )
  - Das kann man relativ leicht durch Nachrechnen beweisen. Interessant ist aber auch der folgende Beweis durch kombinatorische Betrachtungen:
    Bew (kombinatorisch): Die linke Seite der Gleichung entspricht der Anzahl der k-elementigen Teilmengen einer n-elementigen Menge. Wie setzen sich diese zusammen? Nun, man diese in zwei Gruppen zerlegen, indem man ein Element - sei dies mit e_n bezeichnet - auswählt.
    Die n-elementigen Teilmengen von M setzen sich dann zusammen aus den Teilmengen, die e_n enthalten, und denen, die e_n nicht enthalten,
    Das sind einerseits aus den (k-1)-elementigen Teilmengen von M-{e_n}, zu denen man das Element e_n hinzunimmt, und andererseits die k-elementigen Teilmengen von M-{e_n}.
    Deren Anzahlen stehen aber genau in der Summe auf der rechten Seite der Gleichung.
    Damit kann man das Werte rekursiv berechnen. Nimmt man n für die Zeile,
    und k für die Spalten, und startet bei n=1, k=1, ergibt sich
    
    1
    
    1 1
    
    1 2 1
    
    1 3 3 1
    
    1 4 6 4 1
    
    ...
+ - Vandermonde'sche Identität
- Ein weitere Überlegung zur Zerlegungen von Mengen führt zu
  + - Satz: Für alle k,m.n aus N₀ gilt:
  
  (
  n+m
  k
  ) = ∑_l=0,...,k (
  n
  l
  ) (
  m
  k-l
  )
  - Der Beweis ist klarer, wenn man die n und m nach Eigenschaften gruppiert, hier - oBdA - in männlich und weiblich.
    Bew/BSP: Seien die n und m unterscheidbare Untergruppe einer Menge, z.B. n Frauen und m Männer einer Personengruppe. Es gibt nun, wie bereits beweisen, ((n+m) über k) k-elementige Untergruppen davon. Andererseits hat jede k-elementige Untergruppe
    0≤l≤k Frauen, aus den n Frauen ausgewählt, und entsprechend (k-l) Männer. Es gibt also für jede k-elementige Untergruppe mit l Frauen genau (n über l)(m über (k-l)) Möglichkeiten.
    Nun müssen wir noch über alle möglichen l summieren, um alle möglichen k-elementigen Teilmengen der (n+m)-elementigen Menge zu bekommen. Das ist genau die rechte Seite der Gleichung - q.e.d.
+ - Bezierkurven
- Das Verfahren von Bezierkurven wurde in den 1960er Jahren bei Citroen und Renault unabhängig voneinander von Casteljau und Bezier für rundere Formen im Autobau entwicklelt, Heute werden sie allgemein in der Vektorgrafik und CAD, speziell z.B. bei frei skalierbaren Schriften (true type, PostScript) verwendet. Sie erlauben eine effiziente Berechnung der Rundungen bei abgerundeten Kanten.
  Def. Für t∈[0,1] ist eine Bézierkurve n-ten Gerades C(t)
  zu n+1-Stützpunkten (Kontrollpunkten, Bezierpunkten) P_0, ... , P_n definiert durch
  C(t) := ∑_i=0,...,nB_n,1(t) P_i
  Dabei ist das i-te Bernsteinpolynom n-ten Grades
  
  B_n,i(t) := (
  n
  i
  ) tⁱ(1-t)^(n-i)
  
  ~ BSP
  In der Praxis verwendet man meist Bezierkurven der Grade 2 und 3, und setzt größere Kurven aus mehren Stücken (Splines) zusammen. Neben einigen anderen schönen Eigenschaften ist die entstehende Kurve glatt an den Übergängen.
  Die Rekursionsformel des Pascal'schen Deiecks lässt sich auf die Bernsteinpolynome zu deren eeffizienter Berechnung übertragen, man erhält
  Satz: B_n,i(t) = t*B_n-1,i-1(t) + (1-t)*B_n-1,i(t)

+ - Mengenpartitionen

Kombnatorische Beweise beruhen ja gelegentlich auf der Zerlegung von Mengen.
Das macht die Frage interessant, wie man endliche Mengen zerlegen kann.
Def: Eine k-Partition eine n-elementigen Menge M ist eine Zerlegung der Menge in k nicht leere, diskunkte Teilmengen A_1, ..., A_k, also
M = A_1 ∪ A_2 ∪ ... ∪ A_k,
und für paarweise verschiedenen 0<i,j <=k: A_i ∩ A_j = ∅
Def. Die Anzahl der k-Partitionen einer n-elementigen Menge
wird mit S_n.k oder auch S(n,k) bezeichnet.
Diese Zahlen heissen auch Stirling-Zahlen 2. Art
Für n>0 ist das wohldefiniert, Zur Fortsetzung
definiert man S_0.0 := 1 Damit kann man
wieder eine Rekursionsgleichung für Stirlingzahlen 2. Art angeben:
+ - Satz: (Stirling-Dreieck 2. Art): Für alle Zahlen n,k aus N mit n>k gilt
S_n,k = S_n-1,k-1 + kS_n-1,k
- Bew (kombinatorisch):
  Links steht die Anzahl der k-Partitionen einer k-elementigen Menge. Wie entstehen diese?
  Wir wählen wieder ein festes Element e_n aus M, Man kann die k-Partitionen von M dann zusammensetzen aus den k-Partionen von M-{e_n}, indem man einer der k Teilmengen das Element e_n hinzufügt. Dafür hat man k Möglichkeiten - das ergibt den rechten Summanden, Oder man hat{e_n} als eigene Partitionsmenge, dort kommen dann die (k-1)-Partotionen von M-{e_n} hinzu - das ergibt den ersten Summanden,. q.e.d.
  
  Für k>n ist sicher S_n,k=0
  Für n>0 ist sicher S_n,0=0
  Aus der Rekursionsgleichung kann man wieder in der üblichen Weise die Werte berechnen, es ergibt sich das folgende bei (0,0) beginnende Dreieck:
  + -
  
  1
  
  0 1
  
  0 1 1
  
  0 1 3 1
  
  0 1 7 6 1
  
  0 1 15 25 10 1
  
  0 1 31 90 ...
  - 3=1+2*1, 15=1+2*7, ...
BSP
S(4,2)
  = S(3,1) + 2*S(3,2)
  = 1+2*(S(2,1)+2*S(2,2))
  = 1 + 2*(1 + 2*1) = 7

{1,2,3,4}
= {1} ∪ {2,3,4} = {2} ∪ {1,3,4} = {3} ∪ {2,1,4} = {4} ∪ {2,3,1}
= {1,2} ∪ {3,4} = {1,3} ∪ {2,4} = {1,4} ∪ {2,3}

+ - Zahlpartitionen

Man auch eine Zahl n in eine Summe k anderer Zahlen zerlegen:
n = n_1 + ... n_k,
und untersuchen, auf wie viele Weisen das geht.
Unterscheiden kann man dabei noch, ob die Reihenfolge der Summanden eine Rolle spielt, oder nicht.
BSP: 4 = 1+1+1+1 = 2+1+1 = 2+2 = 3+1 ( = 1+3 = 1+1+2 )
+ - Geordnete Zahlpartitionen
- + - Satz: Für alle k, n ∈ N mit n ≥ k gilt:
  
  Die Anzahl der geordneten k-Partitionen von n ist (
  n-1
  k-1
  )
  - Bew: Nun - man kann die Partionen als Summe von 1sen schreiben, die zu k Gruppen zusammengefasst werden. :
    
    n = (1+1+1) + (..) ... + (...) - k Klammerpaare.
    
    Das ist aequivalent zu der Bedingung, aus den n-1 +-Zeichen die k-1 für die Unterteilung
    in Klammerpaare heraus zu suchen, und das ist ungeordnetezs Ziehen ohne Zurücklegen - q.e.d.
    
    Def: Eine diophantische Gleichung ist ein Polynom p(x_1, ... , x_n) in n Unbekannten mit ganzzahligen Koeffizienten, zu dem man eine ganzzahlige Nullstelle sucht.
    Diophantische Gleichungen sind i.a. unentscheidbar, d.h. es gibt keinen Algorithmus, der zu jeder Diophanitschen Gleichung feststellen kann, ob eine ganzzahlige Lösung existiert.
    Den Spezialfall x_1 + x_2 + ... + x_k - n = 0 löst für x_i >0 allerdings nebenstehender Satz.
    Auch für x_1 + ... + x_k - n = 0 für x_i >= 0 hilft uns der nebenstehende Satz.
    Es gilt ja
    x_1 + x_2 + ... x_k = n
    <=>
    (x_1 + 1)+(x_2 + 1) + ... (x_k + 1) = n+k.
    
    Also habe ich (
    n+k-1
    k-1
    ) ganzzahlige Lösungen dafür
+ - Ungeordnete Zahlpartitionen
- Def. Die Anzahl der Möglichkeiten, eine natürliche
  Zahl n als Summe von k Summanden zu schreiben,
  wird mit P_n,k bezeichnet.
  Man setzt P_0,0 := 1
  + - Satz: Für alle n, k aus N mit n ≥ k ≥ 1 gilt
  P_n,k = ∑_j=0,...,k P_n-k,j
  - Bew: Wir sortieren die möglichen Partitionen, so das die 1-sen vorn stehen.
    Es ist dann n= n_1 + ... + n_i + n_(i+1) + ... + n_k, wobei n_1=n_2=...=n_i=1 gilt.
    Also sind alle n_(i+1) bis n_k mindestens zwei. Zieht man von dem Teil
    bei jedem Summanden eine 1 ab, kommt man also auf eine Zahlpartionierung
    von (k-i)-Partitionierung von (n-k).
    Umgekehrt kann man jede k-Partitionierung von n mit i 1sen so erzeugen.
    Es gibt also genau P_n-k,k-i verschiedene Partitionen mit i 1sen.
    Summiert man über alle mögliche i, bekommt man mit
    ∑_i=0,...k P_n-k,k-i = ∑_j=0,...,k P_n-k,j
    die Behauptung - q.e.d.
+ - Catalanzahlen
- + - Def: Eine Triangualisierung ist eine Partition des konvexen n-Ecks in Dreiecke durch sich gegenseitig nicht schneidende Diagonalen.
  + - Def: Ein Binärbaum ist ein Baum mit einem eindeutigen Wurzelknoten, bei dem jeder Knoten maximal zwei Kindknoten hat.
  + - Def: Ein korrekter Klammerausdruck ist ein Wort über {(,)},
  das folgendermassen aufgebaut ist:
  
  1. Das leere Wort ist ein korrekter Klammerausdruck
  2. Sind U und V korrekte Klammerausdrücke,
    so sind auch
    2.1 UV     und
    2.2 (U)
    korrekte Klammerausdrücke
  - BSP:
    1 Paar: ()
    2 Paare: (()) und () ()
    3 Paare: ()()() und (())() und ()(()) und ((()))
    ...
  Def. Sei n aus N₀.
  C_n nennt man auch Catalan-Zahlen.
  + - Satz: Sei n aus N₀. Dann gilt mit C₀=1 für n>0:
  C_n = ∑_k=1,...,n C_k-1 C_n-k
  Bew: Wir zerlegen wieder die Menge der möglichen Klammerausdrücke:
  Für k<=n sei A_k die menge aller legalen Klammerausdrück, deren erste Klammer
  an der Position 2k geschlossen wird.
  Innerhalb der erste Klammer liegen dann k-1 Klammerpaare,
  ausserhalb gerade n-k.
  Für alle Möglichkeiten müssen wir nun wieder von k=1, ... , n summieren - q.e.d.
  
  + - Satz: Sei n aus N₀. Dann gilt mit B₀=1 für n>0:
  B_n = ∑_k=1,...,n B_k-1 B_n-k
  Bew: Ganz analog, wir teilen in Klassen A_k, bei denen am linken Teilknoten k Knoten hängen, am rechten folgerichtig n-k, und summieren über alle k.
  
  Satz: Sei n aus N₀. Dann gilt mit T₂=1 für n>2:
  T_n = ∑_k=3,...,n T_k-1 T_n-k+2
  Bem: Für n ≥ 0 gilt
  
  C_n= B_n= T_n+2=
  1
  n+1
  (
  2n
  n
  )

+ - Abschätzungen

+ - Landau-Symbole
Zur Beschreibung der Grössenordnung beim Wachstum der Werte einer Fuktion hat sich die Verwendung von Landau-Symbolen bewährt. Mit diesen kann man komplizieertere Funktionen in bekannte, einfache Wachstumsklassen zuordnen. Besonders in Numerik nd Informatik sind sie beliebt, um das Laufzeitverhallten von Algorithmen abzuschätzen.
Dabei ist dann n idR. die Grösse der Eingabe, und gefragt wird noch der Dauer oder dem Speicherplatzbedarf der Berechnung des Ergebnissens.

+ - Def.

o(g(n)):= { f(n) | ∀c>0, ∃n_0 ∈N so dass ∀n≥n_0 gilt |f(n)|<c*|g(n)|}

O(g(n)):= { f(n) | ∃C≥0, ∃n_0 ∈N so dass ∀n≥n_0 gilt |f(n)|≤C*|g(n)|}

Ω(g(n)):= { f(n) | ∃C>0, ∃n_0 ∈N so dass ∀n≥n_0 gilt |f(n)|≥C*|g(n)|}

ω(g(n)):= { f(n) | ∀c≥0, ∃n_0 ∈N so dass ∀n≥n_0 gilt |f(n)|>c*|g(n)|}

Θ(g(n)):= O(g(n)) ∩ Ω(g(n))

Meist wählt man als g(n) eine einfache Potenz
BSP: Der Test, ob eine Eingabe der Länge n zu einer gegebenen kontextfreien Grammatik gehört kann man in O(n³) Schritten lösen. Das beweist man, indem man einen Algorithmus angibt, der das macht, und dessen Schritte zählt.
Genauer kann man sogar sagen, das das Problem zu o(n³) gehört, denn die Potzen ist geringfügig kleiner.
Speziellere Grammatiken erlauben effizientere Tests, Grammatiken der LR(1)-Klasse z.B. erlauben es, das Wortproblem in O(n) Zeit zu lösen.
Immer wird das Wortproblem einer Grammatik aber von der Länge der Eingabe abhängen, deswegen ist es sicher in ω(1).

+ - Einige interessante Abschätzungen
Wie wir gesehen haben, geht es bei den Landau-Symbolen um Ungleichungen, also Abschätzung nach oben und unten gegenüber bekannten Funktionen, Wir sehen uns nun einige Abschätzungen für bislang aufgeretene Funktionen an,
+ - Satz: Für n≥15 gilt n^n/2 ≤ n! ≤ (n/2)ⁿ
Bew: Recht kanonisch (Steeger)

Satz (Stirlingformel): n! = sqrt(2 π n) (n/e)ⁿ * (1 + 1/(12n) + O(1/n²))
+ - Satz

(n/k)^k ≤ (
n
k
) ≤ (en/k)^k

Bew: (n über k) ausmultiplizieren und (n/k) gegen (n-i)/(k-i) abschätzen bzw.Reihenentwicklung der Exponentialfunktion ...

+ - Diskrete Stochastik

+ - Def. Eine abzählbare Menge heisst auch diskreter Ereignisraum,
ein Element der Menge elementares Ereignis
- BSP: Würgelwurf, Ziehung beim Lotto, Münzwurf
Def. Sei S ein Ereignisraum. Eine injektive Funktion P: S->[0,1] mit
∑_x∈S P(x) = 1
heisst Wahrscheinlichkeitsfunktion.
Für Ereignisse A aus mehreren Elementarereignissen, also A⊆S,
definiert man P(A) = ∑_x∈A P(x)
Im einfachsten Fall, der Gleichverteilung, bei der alle Elementarereignisse die gleiche Wahrscheinlichkeit haben, gilt P(x) = 1/|S| und P(A) = |A| / |S|.
Hier kommt es also im wesentlichen auf das Zählen von Mengen an, das wir hier schon ausführlich betrachtet haben.
BSP: Wie wahrscheinlich ist es, mit 2 Würfeln eine 7 als Augensumme zu erzielen?
+ - BSP: Wieviel Personen muss man zusammenrufen, damit wahrscheinlich zwei am gleichen Tag Geburtstag haben?
- Wir vereinfachen etwas; Jedes Jahr habe 365 Tage, und Geburtstage seinen gleichwahrscheinlich
  an allen Tagen im Jahr, Der Ereignisraum bei k geladenen Gästen
  ist dann [365]^k.
  "ist wahrscheinlich" heisst konkret, das die Wahrscheinlichkeit mindesten 0,5 beträgt.
  Wir betrachten nun das Anti-Ereignis B: Jeder der k Gäste hat an einem anderen Tag Geburtstag, Ist P(B)<0,5, so ist P(A) >= 0,5.
  B lässt sich leicht auf die Menge der k-Permutationen von [365] modellieren,
  ergibt also 365*364*...*(365-k+1)
  
  Nachrechnen |B| / |S| ergibt, das ab k=23 P(B) kleiner als 0,5 wird
  P(A) über 0,5 wächst:
  365*364* ... * 343 / 365²³ ≈ 0,49270276567601459277

+ - Urnenmodelle (2)

Neben der Modellierung von Problemen durch das Ziehen von Elementen aus einer Urne, das oben behandelt wurde, kann man Probleme oft auch durch das Verteilen von Bällen auf mehrere Urnen modellieren. Die meisten der sich ergebenden Möglichkeiten sind und in diesem Kapitel schon begegnet.
+ - Man kann prinzipiell wieder vier Fälle unterscheiden, und zwar
a) ob die Bälle unterscheidbar sind oder nicht, und
b) ob die Urnen unterscheidbar sind oder nicht.
- BSP: Wenn man zwei Bälle b auf zwei Urnen U verteilt, hat man zwei mögliche Ergebnisse:
  1) U=[], U=[b,b], oder
  2) U=[b], U=[b].
  BSP: Wenn man zwei Bälle b auf zwei Urnen U, V verteilt, hat man drei mögliche Ergebnisse:
  1) U=[], V=[b,b], oder
  2) U=[b], V=[b], oder
  3) U=[b,b], V=[]
  BSP: Wenn man zwei Bälle b1, b2 auf zwei Urnen U verteilt, hat man zwei mögliche Ergebnisse:
  1) U=[], U=[b1,b2], oder
  2) U=[b1], U=[b2]
  
  BSP: Wenn man zwei Bälle b1, b2 auf zwei Urnen U, V verteilt, hat man vier mögliche Ergebnisse:
  1) U=[], V=[b1,b2], oder
  2) U=[b1], V=[b2], oder
  3) U=[b2], V=[b1], oder
  4) U=[b1,b2], V=[]
(Def.) In diesem Unterbaum gilt im Folgenden:
B ist eine Menge von Bällen, |B|= n
U ist eine Menge von Urnen, |U|=m
Eine weitere interessante Unterscheidung ist die Forderung, ob eine Urne mindestens (surjektiv), höchstens (injektiv) oder genau einen (bijektiv) Ball enthalten darf, ob also die Abbildung f: Bälle -> Urnen die in Kammern erwähnte Eigenschaft hat.
Hier muss natürlich:
- für surjektiv n >= m,
- für injektiv m >= n, und
- für bijektiv n=n gelten.
+ - Fälle:
- + - 1. Bälle und Urnen unterscheidbar
  + - f beliebig
  Jeder der n Bälle kann auf jede der m Urnen entfallen.
  Wir zeihen also n mal eine Urne, mit Zurücklegen -
  macht mⁿ Möglichkeiten für ein Abbildung f.
  
  + - f surjektiv
  Für jede Urne u aus U muss das Urbild f^-1(u) mindestens
  ein Element aus B umfassen.
  Die Urbilder bilden eine m-Partitionierung von B. Genauso beschreibt
  jede m-Partitionierung von B eine Klasse von surjektiven Abbildungen nach U.
  Jeder dieser S_n,m Partitionierungen kann ich
  auf m! Weisen die Urnen zuordnen, und erhalten
  zusammen m!S_n,m surjektive Abbildungen.
  
  + - f injektiv
  Das entspricht dem Ziehen der Urne ohne Zurücklegen : m!/n!
  
  + - f bijektiv
  Es gibt n! (=m!) bijektive Abbildungen.

+ - Zusammenfassung

Wir haben eine ganze Reihe von Zählproblemen untersucht, die man so auf Probleme übertragen kann. Dabei kamen häufig verwendete Beweisprinzipien vor, u.a. das Zerlegen eines Problems in zwei oder mehr nicht überlappende Gruppen, die dann einfacher zu behandeln waren, als Grundidee.
Die wichtigsten Häufigkeiten (=Wahrscheinlichkeiten) der disketen Wahrscheinlichkeitstheorie wurden zusammen mit ihren Modellen behandelt, und zur Abschätzung der Komplexität von Problemen wichtige Bezeichnungen eingeführt.

+ - Graphentheorie
+ - Wir haben schon gesehen, das (endliche) Mengen dann interessanter werden, wenn man die Elemente - über Funktionen oder Relationen - miteinander in Beziehung setzt.
Graphen erlauben nun die Formulierung komplerer Beziehungen auf einer Menge von Knoten.
Unabhängig davon ob man sie aufmalt ("Ein Bild sagt mehr als tausend Worte"), oder nur abstrakt als Modellierungshilfe einsetzt - Graphen sind ausdrucksstark, und haben viele untersuchenswerte Eigenschaften.
+ - BSP
Relationen

+ - Endliche Automaten

Abstammungsbaum / Genealogie

Strassenkarte / S-Bahn- oder Bus-Netzplan

Toplogische Probleme / Knoten

+ - Petri-Netz (UML)

~ Flussdiagrammen, Ablaufdiagramme, Organisationsdiagramme

~ Klassendiagramme

Dateisysteme

Syntaxbäume

~ (Entscheidungs-)Bäume

+ - n-Ecken

Schalt- oder Lötpläne

Mindmaps

...

+ - Grundlagen
Def. Ein (ungerichteter) Graph G ist ein Tupel (V, E ), wobei V eine endliche nichtleere Menge von Knoten ist, und die Menge E = {{x, y} | x, y ∈ V } die Kanten zwischen Knoten spezifiziert..

Def. Ein gerichteter Graph ist ein Graph, bei dem die Kanten eine
Orientierung haben. Dann ist E ⊆ VxV
Um nicht in der Schreibweise für gerichtetet und ungerichtete Graphen unterscheiden zu müssen, vereinbaren wir, das bei Verwendung der Tupelschreibweise für ungerichtete Graphen (x, y) := (y, x) gilt.
Das ist ein Unterschied dazu, die Symmetrie von E zu verlangen - dann hätte man zwei unterscheidbare Kanten (x,y),(y,x).
Darstellung: Man kann kleine Graphen gut graphisch (!) darstellen, indem man die Knoten als Punkte malt, und für die verbindenenden Kanten Linien zischen die verbundenen Knoten zeichnet.
Bei gerichteten Graphen malt man die Kanten als Pfeile.
Die genaue Lage der Knoten ist dabei gleichgültig, man sollte also etwas aufpassen, wenn man Graphen aufgrund dieser Darstellung vergleicht.
+ - Isomorphe Graphen
Wir präzisieren diesen etwas schwammigen Gleichheitsbegriff:
+ - Def. Zwei Graphen G=(V,K) und H=(U,L) heissen isomorph,
wenn es eine bijektive Abbildung f: V->U der Knotenmengen
gibt mit der Eigenschaft, das für alle Knotenpaare
{v,k} aus K eine Kante {f(v),f(k)} in L existiert, und L auch keine
weiteren Kanten enthält.
f heisst dann auch Graphisomorphismus.
BSP

Def: Ein Konten a und eine Kante k heissen inzident, wenn a einer der Endknoten der Kante ist.
Def. Sei G=(V,E) ein Graph. Ein Subgraph S=(V_1,E_1) von G
ist ein Graph, für den gilt V_1 ⊆ V und E_1 = {{x,y}∈E | x,y∈V_1}
+ - Def. Für eine Graph (V,E) und einen Knoten v aus V heisst
deg(v):=|{ {v,x}|{v,x}∈E }| der Grad von v .
Die Menge {x | {v,x}∈E } heisst auch Nachbarschaft des Knotens v.

deg(v1) = deg(v2) = deg(v5) = deg(v7) = deg(v9) = 1
deg(v3) = deg(v6) = deg(v8) = 2
deg(v4) = 3

+ - Satz: Für jeden Graphen (V,E) gilt:
∑_v∈V deg(v) = 2*|E|
Bew: Auf der linken Seite der Gleichung wird jede Kante {a,b} des Graphen zwei mal gezählt: einmal beim Knoten a, einmal beim Knoten b. Auf der rechten Seite zählen wir direkt jede Kante doppelt - q.e.d.

+ - Korollar: Für jeden Graphen gilt: Die Anzahl der Knoten mit ungeradem Grad ist gerade.
Bew: Teilen wir V diskunkt in die Knoten mit geraden Grad VG
und die mit ungeradem Grad VU, gilt nach dem letzten Satz
∑_v∈VG deg(v) + ∑_v∈VU deg(v) = 2*|E|.
Da die Sume über gerade Werte wieder gerade ist,
muss auch die linke Teilsumme gerade sein.
Da alle Summanden ungerade sind, muss die Anzahl der Summanden
gearde sein. Die Anzahl der Summanden sind aber die
Anzahl der Knoten mit ungeradem Grad - q.e.d.

+ - Einige spezielle Graphen
+ - Def. Ein Kreis C(n) ist ein Graph aus n verschiedenen Knoten, die zyklisch miteinander verbunden sind.
+ - BSP

Ein Kreis kann natürlich auch ein Subgraph eines anderen Graphen sein.

+ - Def. Ein Graph (V,E) heisst vollständig, wenn
alle Knoten miteinander verbunden sind, wenn also gilt E = VV
Vollständige Graphen mit n Knoten bezeichnen wir mit K_n oder Kn.
+ - BSP:
K4 ≅ ({1,2,3,4},{{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}})

+ - K4, K5, K6

Für vollständige Graphen haben alle Knoten den Grad |V|-1

Ein vollständiger Graph mit n Knoten hat n(n-1)/2 Kanten.

+ - Def. Ein vollständig bipartiter Graph K(n,m) ist ein Graph über zwei disjunkten Knotenmengen V und W mit den Mächtigkeiten |V|=n und |W|=m, bei dem jeder Knoten aus V zu jedem Knoten aus W direkt benachbart ist, und seinerseits keien Nachbarn in V hat, und umgekehrt jeder Knoten in W zu jedem in V direkt benachbart ist, aber keine Nachbarn in V hat.

+ - Def. Ein d-dimensionalen (Hyper-)Würfel Q_d ist
isomorph zu dem Graph (V,E) mit
1. V = {0,1}^d, und
2. {v,k}∈E <=> v und k unterscheiden sich an genau einer Stelle.
~ Konstruktion
Hyperwürfel haben also d-Tupel aus 0 und 1 als Kanten
+ - Eine d+1-dimensionalen Hyperwürfel kann man aus einem d-dimensionalen gewinnen, indem man letzteren verdoppelt, und dann die passenden Kantenknoten verbindet.
BSP

+ - Q0-Q4

+ - Q0-Q4 abstrakter:
Q0=({0},[})
Q1=({0,1},{{0,1}})
Q2=({00,01,10,11},{{00,01},{10,11}{11,10}{01,11}})
Q3=({000,001,010,011,   100,101,110,111 },
   {
     {000,001},{010,011},{011,010},{001,011},
     {100,101},{110,111},{111,110},{101,111},
     {000,100},{010,110},{011,111},{001,101}
   })

+ - Bem: ein Würfel der Dimension d hat

Grad d (für alle Knoten)

2^d Knoten

d * 2^d-1 Kanten

2d Seiten

Zur Zahl der Kanten: Jeder der 2^d Knoten hat Grad d,
es gehen also d Kanten von ihm weg. Wenn ich über alle Knoten
zähle, zähle ich aber jede Kante doppelt, also d*2^d-1
Zun Begriff "Seiten": Seiten sind (d-1)-dimensionale Hyperwürfel, die Subgraphen sind.
Behauptung: Allgemein gibt es für k=0,...,d-1
genau (d!/(d-k)!) * 2^d-k k-dimensionale Grenzelemente
eines Hyperwürfels.

+ - Wege, Pfade, Zykel
+ - Def. ein Graph (V,E) heisst zusammenhängend,
wenn jeder Knoten mit jedem anderen durch eine
Kette von Kanten verbungen ist. Genauer: Wenn gilt:
Für alle v,w aus V gibt es ein n>= 0 und v=x_1, ..., x_n=w aus V
und für i=1, ..., n-1 ist {x_i,x_(i+1))} eine Kante in E.

Das Knoten-Tupel (x_1,..., x_n) heisst Weg (walk) von v nach w.
Von Pfad (path) spricht man, wenn bei einem Weg alle Knoten
paarweise verschieden sind, d.h. der Weg keine Kreise enthält.
+ - BSP Weg und Pfad

Def: Eine Teilmenge U von V heisst Zusammenhangskomponete
(oder einfach Komponente) des Graphen,
wenn für alle u,v aus U ein Pfad von u nach v existiert.
Die Zusammenhangskomponenten bilden natürlich eine Partition der Menge der Knoten: Jeder Knoten liegt in einer Komponente, und die Komponenten sind disjunkt.
+ - Satz: Für jeden Graphen G=(V,E) gilt, das G mindesten |V| -|E| Komonenten enthält.
Bew. (Induktion nach m=|E|)
IA: m=0. Dann ist jeder Knoten eine Komponente, es gibt |V|-0 Komponenten.
IS: Sei nun G=(V,E) mit |E|=m+1. OBdA wählt man ein e aus E aus.
Der Graph G'=(V,E-{e}) enthält nun nach IV mindestens |V|-m Komponenten, und G entsteht aus G' durch Hinzunahme von e. Was kann dabei passieren?
1) e verbindet Knoten, die schon in einer Komponente lagen. Dann bleibt die Komponentenzahl |V|-m > |V|-(m+1).
2) e verbindet zwei Komponenten zu einer, dann sinkt die Kompinentenzahl um eins: |V|-m-1 = |V|-(m+1)
In beiden Fällen bleibt die Induktionsaussage erhalten - q.e.d.

Bem. Ein zusammenhängender Graph besteht aus nur aus einer Zusammenhangskomponente.
Mit dem Satz von oben liefert das direkt, das für jeden zusammenhängenden Graphen (V,E) gilt:
|E| ≥ |V|-1
Kreise haben also die minimale Kantenzahl für zusammenhängende Graphen.
+ - Aber: Nicht jeder Graph mit |E|>|V|-2 ist zusammenhängend!
BSP: K6 und ein einzelner Punkt

+ - Bäume

Bäume bilden eine oft genutzte spezielle Klasse von Graphen. Aus der alltäglichen Praxis sind im wesentlichen solche mit einer ausgezeichneten Wurzel bekannt, man kann aber Bäume auch allgemeiner als kreisfreie Graphen definieren. Wir geben hier direkt beide Definitionen:
+ - Def (Baum): Ein Baum T=(V,E) ist ein zusammenhängender, kreisfreier Graph. Ein Knoten v im Baum mit deg(v)=1 heisst Blatt.

Es gibt also für jedes Knotenpaar im Baum eine Pfad zwischen den Knoten, aber keinen geschlosssenen Pfad.
Bei mehreren Bäumen spricht man auch wie üblich von Wald.
Wenn man einen Baum an einer Stelle trennt, erhält man einen Wald mit zwei Bäumen.

+ - Def (Wurzelbaum) Ein Wurzelbaum ist ein Tupel (T,r), wobei T=(V,E) ein Baum ist, und r ein (ausgezeichnetes) Element aus V, das Wurzel genannt wird.
Wurzelbäume werden meist mit der Wurzel nach oben gezeichnet. Wer schon mal eine n Baum entworfen und gezeichnet hat, weiss, warum.

+ - Neben den schon bei den allgemeine Graphen genannten Beispiele sind ggf. AVL-Bäume als Vetreter der ausgewogenen Suchbäume und Listen als spezielle Binärbäume z.B. als Grundlegende Datenstruktur der Programmiersprachen LISP/Scheme als prominente Beispiele zu nennen.
+ - BSP Listen

Je mehr ein Baum spezialisiert wird, um so mehr Aussagen kann man natürlich darüber machen. Hier sind im Folgenden nur ein paar sehr allgemeine Aussagen zu Bäumen aufgeführt.
Wenn man versucht, die Kanten in einen Baum zu schätzen, kommt man leicht zu der Vermutung, das sie mit der Blattanzahl zusammenhängt. Das sitmmt aber nicht.
+ - Satz: Für einen Baum T=(V,E) gilt |E| = |V| - 1
Für einen nicht-rekusiven Beweis benötigen wir noch zwei Hilfsaussagen, und eine Hilfsdefinition:
Def. Sei G=(V,E) ein Graph, und v ein Knoten aus V. Dann ist G-[v] der Graph, der aus G durch Entfernen des Knotens v und aller mit ihm verbundenen Kanten entsteht, also
G-[v] := (V-{v},{ {x,y}∈E | x≠v und y≠v }).
+ - Lemma 1: Ein Baum mit mindestens zwei Knoten hat mindestens zwei Blätter.
Bew: Man wählt eine beliebige Kante, und läuft in beide Richtungen bis es nciht mehr weiter geht. Da der Baum zykelfrei ist, habn wir dann zwei verschiedenen Blätter gefunden.

+ - Lemma 2: Ist T=(V,E) ein Baum mit mindestens zwei Knoten, und b ein Blatt,
so ist T-[b] auch ein Baum.
Bew: Sei T':=T-[b].
T' ist sicher kreisfrei, da T kreisfrei war, und wir nur etwas weggenommen haben. T' ist aber auch immer noch zusammenhängend, denn für alle Konoten x,y aus T' gibt es einen Pfad in T, da T ein Baum ist. Alle innerern Knoten dieses Pfades haben einen Grad >1, also kann g nicht zu dem Pfad beigetragen haben, und der Pfad ist auch ein Pfad in T'.

Bew. des Satzes (durch Widerspruch):
Für |V|=1 ist die Aussage richtig. Wenn wir annehmen, die Aussage ist falsch, muss es also in der Knotenzahl ein "kleinstes" Gegenbeispiel T'=(V',E') geben, mit |V'|>1 und |E'|≠|V'|-1, und der Eigenschaft, das alle Bäume mit weniger als |V'| Knoten die Aussage erfüllen.
Entfernen wir nun aus T' ein Blatt, von dem es ja nach Lemma 1 mindestens zwei geben muss, bleibt nach Lemma 2 immer noch ein Baum übrig, mit n:=¦V'¦-1 Knoten und m:=|E'|-1 Kanten, da wir genau eine Kante entfernt haben. Für diesen Baum muss, da T' ja kleinstes Gegenbeispiel war, die Aussage des Satzes zutreffen, also m=n-1. Mithin git auch |E'|=m+1=n=|V'|-1 - wwas oben gerade ausgeschlossen war. Widerspruch! - q.e.d.
Mit einer induktiven Definition von Bäumen kann man das sehr viel einfacher induktiv beweisen. Aber hier reicht für einen alternativen Beweis auch die Beobachtung, das durch das Entfernen einer Kante genau zwei Bäume U1, U2 entstehen. Habe U1 m Knoten und (nach Induktionsvoraussetzung) m-1 Kanten. so hat U2 |V|-m Knoten, und damit (|V|-m)-1 Kanten.
Eine Kante kommt beim zusammensetzen zu G hinzu , zusammen haben wir
m-1+|V|-m-1 + 1 = |V|-1 Kanten - q.e.d.

Def: Sei ein Graph G=(V,K) gegeben. Ein Baum T=(V,F) heisst Spannbaum von G, falls F⊆E.
+ - Satz: Jeder zusammenhängende Graph enthält einen Spannbaum.

Der Beweis erfordert wieder eine Hilfsaussage:
+ - Lemma: Sei G=(V,E) ein zusammenhängender Graph, und C ein Kreis in G.
Dann gilt für alle Kanten e im Kreis, das (V,E-{e}) ein zusammenhängender Graph ist.
Intuitiv ist das klar: Entfernt man in einem Kreis eine Verbindung zwischen zwei Knoten, können sich beide Knoten ja noch über den (langen) anderen Weg erreichen. hängen also noch zusammen. Den formalen Beweis überlasse ich gern dem interessierten Leser.

Bew. (des Satzes): Für |V|=1 ist die Aussage richtig.
Sei nun |V|>1. Wir geben eine Algorithmus zur Konstruktion eines Spannbaumes an:
Input: G=(V,E)
Output: T=(V,F)

F:=E
while T:=(V,F) ist kein Baum // d.h. T enthält einen Kreis
do
  wähle eine beliebige Kante e aus einem beliebigen Kreis von T
  F := F-{e}
done
Da lt. Lemma (V,F) immer ein zusammenhängender Graph bleibt, funktioniert der Algorithmus,. also - q.e.d.
Bemerkenswert an dem Beweis ist. das es ein konstruktiver Beweis ist, der einen Algorithmus verwenden. Das ist oft eine sehr gute Methode, weil man zum formalen Beweis gleich eine Konstruktionsmethode gewinnt.
+ - BSP: Spannbäume (rot)

+ - Markierte Bäume
+ - Wenn man fragt, ob zwei Bäume gleich sind, ist entscheidend, ob man damit "bis auf Isomorphie" meint, also einne bijektive Abbildung zwischen den Knoten erlaubt, oder nicht. Im letzteren Fall muss man die Knoten unterscheiden können, sie sind also markiert. Man spricht dann von markierten Bäumen.
+ - BSP gleich vs. isomorphe Graphen

Beide Zählweisen leifern schon für kleine n sehr unterschiedliche Werte:

n 2 3 4 5 6 7

labeled 1 3 16 125 1296 16807

nicht isomorph 1 1 2 3 6 11

Für markierte Bäume findet man relativ leicht eine Gesetzmäßigkeit:
+ - Satz (Cayley):
Fün n>1 gilt: Es gibt n^(n-2) markierte Bäume mit n Knoten.
Bew-Skizze: auch das kann man algorithmisch beweisen.
Man konstruiert eine Algorithmus, der vom kleinsten
markierten Blatt aus beginnend jedem markierten Baum
mit n Knoten bijektiv ein (n-2)-Tupel über [n] zuordnet.
Davon gibt es, wie wir in der Kombinatorik schon gesehen
haben, genau n^(n-2) verschiedene.

Wie viele isomorphe Bäume es gibt ist schwieriger zu entscheiden.
Hier sei nur erwähnt, dass für allgemeine Graphen das
Subgraphenisomorphismusproblem (Ist G isomorph
zu einem Subgraphen von G'?) NP-vollständig ist, und das
Graphenisomorphismusproblem (Ist G isomorph zu G'?)
vermutlich nicht NP-vollstängig ist., aber zur Zeit kein
Algorithmus mit polynomineller Laufzeit dafür bekannt ist.

+ - Eulertouren
Angeblich geht die Einführung der Graphentheorie durch Leonhard Euler auf folgendes Königsberger-Brückenproblem zurück.
Das Problem ist eher ein topologischsches, die Lösung verwendet aber Graphentheoretische Aussagen.
+ - ~ Gibt es in der Stadt Königsberg einen Rundweg, bei dem man alle sieben Brücken der Stadt über den Pregel genau einmal überquert und wieder zum Ausgangspunkt gelangt?

Def (Eulertour): Eine Eulertour oder Eulerkreis ist
ein Kreis in einem Graphen, der jede Kante genau einmal enthält.
Enthält ein Graph G einen Eulerkreis, nennt man ihn eulersch.
+ - Satz: Ein zusammenhängender Graph G=(V,E) ist genau dann eulersch, wenn der Grad aller Knoten gerade ist.
Bew (=>): Enhält G eine Eulertour, geht diese in jeden Knoten genau so oft "hinein" wie "hinaus" - deswegen ist der Knotengrad gerade.
Bew (<=): Sei also der Knotengrad gerade für alle Knoten. Wir wählen nun einen beliebigen Knoten v1, und gehen von dort zu einem Knoten v2, und markieren dabei die Kante {v1,v2} als benutzt. Von v2 gehen wir über eine noch nicht markierte Kante (mindestens eine muss es ja geben) weiter zu v3, und markieren wieder. Das Verfahren setzen wir fort. Da es immer eine unbenutze Kante finden, müssen wir irgendwann wieder in in v1 ankommen.
Dann haben wir zwei Situationen:

a) Es gibt noch mindestens einen Knoten w mit unmarkierten Kanten. Da G zusammenhängend ist, muss es dann eine nicht markierte Kante geben. die von w ausgeht. Wir können dann das Verfahren (rekursiv) in w wieder starten, und nacher die beiden Wege zu einem verbinden.

b) Alle Kanten sind markiert - dann haben wir einen Eulerkreis gefunden.
+ - BSP

+ - BSP: Eulertour für K(5)

E1+E2 = (1,4,5,1,3,2,1)
E1+E2+E3=(1,4,5,1,3,2,4,3,5,2,1)

+ - Mit diesem Satz ist klar, das es für das Königsberger Brückenproblen keinen Weg gibt, da die Knotengrade ungerade sind (die Knoten entsprechen den abstrahierten Landflächen):

Def. Eine offene Eulertour ist eine Eulertour, bei der Anfangs- und Endknoten nicht übereinstimmen.

Es gilt dann der modifizierte Satz, den man mit der Wahl der beiden Ausnahmen als Start und Zielknoten leicht beweist:
+ - Satz: Ein zusammenhängender Graph G=(V,E) enthält genau dann eine offene Eulertour, wenn der Grad aller Knoten bis auf zwei gerade ist.
Bew: Wenn man die beiden Knoten mit zwei zusätzlichen Kanten und einem zusätzlichen Knoten verbindet, hat man einen Eulerkreis.

+ - Ein recht bekanntes für eine offene Eulertour (wo Anfangs- und Endknoten nicht übereinstimmen) ist das Malspiel "Das ist das Haus vom Nikolaus".

~ de.wikipedia.org > Wiki > Leonhard Euler

+ - Hamiltonkreise
Neben den Wegen, die alle Kanten erfassen, ist natürlich auch die Frage nach den Wegen interessant. die alle Knoten erfassen.
+ - Def (Hamiltonkreis): In einem Graph G=(V,E) nennt man einen Kreis, der
alle Knoten aus V genau einmal durchläuft, einen Hamiltonkreis.
Enthält ein Graph eine Hamiltonkreis, nennt man ihn hamiltonsch.
BSP

~ en.wikipedia.org > Wiki > William Rowan Hamilton
Eines der berühmten Beispiele für die Suche nach einem Hamiltonkreis (mit Randbedingungen) ist das "Travelling Salesman"-Problem: Ein Handlungsreisender möchte n Städte besuchen, und sucht einen optimalen Weg zwischen ihnen.
+ - Das Entscheidungsproblem, ob ein gegebenener Graph G einen Hamiltonkreis enthält ist NP-vollständig (Karp, 1992).
Das heisst, das man sehr wahrscheinlich keinen Algorithmus finden kann, der die Frage für beliebige Graphen G=(V,E) beantwortet, und dessen Laufzeit polynomiell in |V| und |E| ist.
~ de.wikipedia.org > Wiki > NP-Vollst%C3%A4ndigkeit
Klasse P: Es gibt ein k aus N, so das Problem
im O(Eingabelänge)^k Schritten lösbar ist.
+ - Offene Frage: P = NP ?
Lösung bringt 1 Mio US-$ als Preisgeld

~ spektrum.de > Artikel > 968743& z=798888

NP-vollständig: Wenn ein NP-vollständiges Probleme in P liegt, dann NP=P

Bislang spielten Schleifen keine Rolle, das sie für die betrachteten Eigenschaften quasi zusammenschnurrten. Für folgende Aussagen sind sie wichtig.
Def: In einem Graphen heisst eine zum Kante mit gleichen Start- und Zielknoten,
also {v,v} für ein v aus V, eine Schleife.
Ein Graph ohne Schleifen heisst schleifenfrei.
Die vollständigen Graphen sind natürlich hamiltonsch. Es leuchtet auch ein, das man eher einen Hamiltonkreis findet, wenn die Knotengrade hoch sind. Genauer gilt:
+ - Satz: Gilt in einem schleifenfreien Graphen G=(V,E), das
für alle Paare x,y aus V mit x≠y und {x,y}∉E
folgt deg(x) + deg(y) ≥ |V|,
so gibt es in dem Graphen einen Hamiltonkreis.

Bew: durch Widerspruch, etwas komplexer (z.B. Steger S. 78)

Und als Spezialfall davon:
Korollar: Hat jeder Knoten in einem schleifenfreien Graphen G=(V,E) einen Grad von mindestens |V|/2, ist der Graph hamiltonsch.
Viel bekannte Graphen enhalten Hamiltonkreise, u.a. die vollständigen Graphen K(n), wie der obige Satz beweist. Auch fast alle Hyperwürfel, wie man durch die folgende Konstruktion zeigen kann:
+ - Satz: Jeder Hyperwürfel der Dimension d>=2 ist hamiltonsch.
Bew: (Induktion nach d):
IA: Für d=2 ist der Hamiltonkreis genau der ganze Graph.
IS: Q_(d+1) entsteht ja aus Q_d, indem man Q_d verdoppelt,
wobei man an den Knoten der Kopie eine 1,, an denen des Originals eine 0 ergänzt, und dann jeweils die ehemals gleichen Knoten, die sich nun um genau die erste (bzw. letzte, hängt man hinten an) Stelle unterscheiden, miteinander verbindet.
In den Q_d gibt es nach Voraussetzung Hamiltonkreise. Wir entnehmen diesen Kreisen nun eine Kante an einer beliebigen Stelle, aber in Original und Kopie gleich, und verbinden die beiden nun offenen Kreise an den Bruchstellen über die Verbindungen von Kopie und Original. Das liefert einen Hamiltonkreis in Q_(d+1).
- q.e.d.
BSP

+ - Die o.g. Konstruktion liefert nebenher einen binären Code, bei dem sich die einzelnen Codewörter nur um ein Bit unterscheiden - den Gray-Code.

Dezimalwerte, Gray- und Standard-Binärcode für 4 Bits:

dez. 0 1 2 3 4 5 6 7

std. 0000 0001 0010 0011 0100 0101 0110 0111

Gray 0000 0001 0011 0010 0110 0111 0101 0100

dez. 8 9 10 11 12 13 14 15

std. 1000 1001 1010 1011 1100 1101 1110 1111

Gray 1100 1101 1111 1110 1010 1011 1001 1000

Man kann für den Gray-Code die Konstruktion auch noch "algorithmischer" angeben:
Für n=1 Bit ist der Gray-code G(0)=0 und G(1)=1.
Für n>1 Bit ist der Gray-Code
G(k) = 0G(k) für k < 2^(n-1)
G(k) = 1G(2^n-k-1) sonst.
Der Gray-Code liefert also einen (speziellen) Hamiltonkreis im Hyperwürfel.
Er spielt z.B. in der Computergraphik eine Rolle, weil er höherer Kompressionen erlaubt.
+ - Suchen auf Graphen
+ - Wir haben ja schon gesehen, das Algorithmen auf Graphen praktisch sein können. Oft steht man vor dem Problem, jeden Knoten eines Graphen "anfassen" zu müssen, oder einen Graphen vollständig durchsuchen zu müssen. Dafür bieten sich zwei Wege an ("breadth first" vs. "depth first"), und ihre Effizienz hängt auch mit der Speicherung des Graphen zusammen.
BSP: Minimales Knotenlabel finden, Werte in den Knoten aufsummieren, ...

Natürlich werden Sie i.A. bei der Programmierung in einer höheren Programmiersprache einfach den entsprechenden Datentyp (e.g. "btree") wählen, aber der ist ja auch einmal programmiert worden, und ggf. ihr eine eigenen Implementation ja auch für ein spezielles Problem effizienter.
Da Knotenmegen ja endlich sind, kann man immer eine Bijektion V->[|V|] angeben. Wir identifizieren deswegen hier eine Knotenmenge V mit |V|=n immer mit [n] = {1,2, ..., n}.
Manche Probleme lassen sich sehr schnell lösen, wenn der Graph als Adjazenzmatrix vorliegt, d.h. für n Knoten haben wir eine n x n -Matrix, die genau dann eine 1 im Feld (l,k) hat, wenn Knoten l mit Knoten k verbunden ist, und sonst 0.
+ - Eine andere Form der Speicherung ist die mit Adjazenzlisten. Hier speichert man zu jedem Knoten eine Liste mit seinen direkten Nachbarn.
+ -
+ -

BSP, Frage: Gibt es eine Kante von 3 nach 2? Welche Nachbarn hat 3?

Wenn man einen (Wurzel-)Baum als Graphen hat, ist das Probem überschaubar: Man wählt einen Knoten (im Idealfall die Wurzel), und löst das Problem dann rekursiv für alle Nachbarn (bzw. Kinder). Je nachdem ob die anstehende Berechung erst für den Knoten oder erst für die Nachbarn entschieden wird, kann man die Algorithmen klassifizieren.
Für allgemeine Graphen ist viel schwieriger zu entscheiden, ob man alle Knoten abgearbeitet hat, und man muss sich auch merken, welche Knoten bearbeitet wurden, weil Kreise ja vorkommen können.
Da Suchen auf Graphen im Bereich "Algorithmen und Datenstrukturen" der Vorlesungen Informatik I+II ausführlich behandelt wird, möchte ich hier nicht intensiver in das Thema einsteigen.

+ - Planare Graphen
~ Dieser Abschnitt berührt wieder Probleme der Topologie. Insofern werden wir nur recht oberflächlich darauf eingehen.
+ - Def. Ein Graph heisst planar oder eben wenn man ihn
kreuzungsfrei n die Ebene einbetten kann.
Man kann das auch - aber mit erheblichem Aufwand - formal definieren. Hier soll die Anschauung reichen.
+ - BSP:

+ - BSP: geht nicht: K5, K(3,3)

+ - Def. Für einen planaren Graphen G heissen die Bereiche der
Ebene, die man erhält, wenn man den Graphen
an den Kanten zerschneidet, Gebiet.
Die Anzahl der sich so ergebenden Gebiete wird mit faces(G)
bezeichnet. Das äussere Gebiet zählt dabei mit.
BSP: Der K4 hat vier Gebiete, K3 nur zwei.

+ - Satz (Eulersche Polyederformel):
Sei G=(V,E) ein zusammenhängender ebener Graph. Dann gilt
  faces(G) = |E| - |V| + 2
Bew: Durch Induktion nach |E|. Der IA sind Bäume, das IS-Argument Kreise!
IA: Sei T ein Baum. Bäume sind planar und enthalten keine Kreise, es ergibt sich
also faces(T)=1. Ausserdem gilt für Bäume |E|=|V|-1, also |E|-|V|+2 = 1.
IS: Sei nun ein Graph G=(V,E) gegeben, der kein Baum ist. G enhält mindstens
einen Kreis, und dieser Kreis umschliesst ein Gebiet. Entfernt man eine Kante e aus dem Kreis, hat der Graph genau ein Gebiet weniger, und damit nach IV

  (|E|-1) - |V| + 2 Gebiete.

G hat nun ein Gebiet mehr, also |E|-|V|+2 Gebiete - q.e.d.

+ - Satz: Für jeden planaren Graphen G=(V,E) mit |V|>2 gilt
|E| ≤ 3*|V| - 6
Bew: Eine Einbettung in die Ebene liefert g Gebiete. Jedes Gebiet wird durch mindestens drei Kanten begrenzt, jede Kante begrenzt maximal zwei Gebiete, also: 3*g ≤ 2*|E|.
Also 2/3|E| ≥ g = |E|-|V|+2 => (1/3)|E| ≤ |V|-2 - q.e.d.
Deswegen kann es z.B. keine planare Darstellung für den K5 geben.
Bei Triangularisierungen wird jedes Gebiet von genau drei Kanten begrenzt, für diese gilt daher im Satz die Gleicheit: |E|=3|V|-6

+ - Satz (Kuratowski): Ein Graph ist genau dann planar wenn er weder eine Unterteilung des K(5) noch des K(3,3) als Teilgraphen enthält.
Unterteilungen eiens Graphen sind Graphen., bei denen einzelnen Kanten durch Pfade ersetzt werden, Intuitiv setzt man einfach mehr neue Knoten auf Kanten.
+ - BSP Unterteilungen

~ de.wikipedia.org > Wiki > Kazimierz Kuratowski
Bew: ... entfällt hier. Nachzulesen in
Casimir Kuratowski: Sur le problème des courbes gauches en topologie. In: Fund. Math. 15. 1930, 271-283.
K(5) und K(3,3) sind also gewissermassen die einzigen echten Bausteine für mehrdimensionale Graphen
+ - BSP: Petersen-Graph

Es gibt in der Computergraphik bekannte Verfahren, die in O(|V|+|E|) Zeit testen, ob ein Graph G=(V,E) planar ist, und ihn ggf. auch konstruieren.
+ - Planare Graphen sind ein aktives Forschungsgebiet ...
~ www2.informatik.hu-berlin.de > Alkox > Forschung > Planar

+ - Graphenfärbung
+ - Viele Probleme können mit Hilfe von Graphenfärbung modelliert werden: (politische) Karten, Verteilung von Sendefrequenzen bei Mobilfunk oder WLAN, die Registerbelegung durch gleichzeitg benutzte Variablen im Compilerbau, ... fast alles, was mit Überlappungsproblemem zu tun hat.
BSP: Im WLAN gibt es 6 Frequenzen, und die AccessPoints müssen so verteilt sein, dass sich in ihrem Sendebereich keine gleichen Frequenzbereiche überlappen, da es sonst zu Störungen kommt. Das kann man durch 6 Farben modellieren.
+ -

Def: Sei G=(V,E) ein Graph.
Eine Knotenfärbung mit k Farben von G ist eine Abbildung
c: V -> [k] mit der Eigenschaft, das
für alle Kanten {v,w}∈ E gilt c(v)≠c(w).
+ - Def: Zu einem Graphen G ist die chromatische Zahl (χ(G))
das minimale k, für das eine Knotenfärbung für G existiert.
BSP: Vollständige Graphen K(n) haben die chromatische Zahl n
BSP: Kreise mit gerader Knotenzahl kann man abwechselnd färben, also gilt für alle n>1: χ(C(2n)) = 2
+ - BSP: Für Kreise mit ungerader Knotenzahl muss man für den "letzten" Knoten eine neue Farbe wählen, also gilt hier für alle n>1: χ(C(2n+1)) = 3
BSP

Für bipartite Graphen G ist natürlich χ(G) = 2, da die Knoten in einer der Partitonsmengen immer die gleiche Farbe haben können. Das motiviert folgenden Zusamenhang:
+ - Satz: Ein Graph G=(V,E) ist genau dann bipartit, wenn er keinen Kreis ungerader Knotenzahl als Teilgraphen enthält.
Bew. "=>": Angenommen, G sei bipartit und beinhalte einen Kreis ungerader Ordnung.
Dann gäbe es eine Knotenfärbung mit zwei Farben auch für den Kreis - Widerspruch!
Bew "<=": Man beginnt bei einem Knoten, färbt ihn rot, und färbt in Breitensuche immer nach dem Abstand (also der Zahl der Knoten dazwischen), bei geradem Abstand rot, ungeradem Abstand blau. Da es keinen Kreis ungerader Knotenzahl als Untergraphen gibt, kann man so alle Knoten färben, und die Knoten gleicher Farbe bilden eine Partition des bipartiten Graphen,

Aus dem Problem der Kartenfärbung enstand der folgende Satz:
+ - Satz (Vierfarbensatz): Für jeden planaren Graphen ist χ(G) ≤ 4
Zum Beweis:
Als Vermutung ist diese Aussage schon recht alt, konnte aber erst 1977 durch Appel und Haken gelöst werden. Er wurde von Mathematikern zunächst (und ggf.immer noch) nur ungern gesehen, da er das Problem in mehere Mengen von Problemfällen teilt. Der Beweis für die unendliche Menge war dann formal, aber für den Nachweis der Aussage für 1963 problematische Fälle wurde ein Computer(programm) bemüht.
Erheblich einfacher zu beweisen ist die gleiche Aussage für 5 Farben

+ - Im allgemeinen ist das Problem, χ(G) für einen gegebenenen Graphen G bestimmen. recht aufwändig. Schon die Frage: "Ist für gegebenen Graphen χ(G) höchstens 3?" ist NP-vollständig. In der Praxis verwendet man daher Näherungslösungen, die idR auf lokalen Informationen beruhen.
BSP Greedy-Algorithmus:
Wir besuchen die Knoten des Graphen in einer beliebigen Reihenfolge v1 , v2 , . . . , vn und ordnen dem aktuellen Knoten jeweils die kleinste Farbe zu, die noch nicht fur einen benachbarten, bereits besuchten Knoten verwendet wird.
Def. Für einen Graphen G=(V,E) ist
maxdeg(G) := max {deg(v) | v∈V } der maximale Knotengrad von G.
(Man verwendet oft auch die Bezeichnung Δ(G).)
Der Greedy-Algorithmus benötigt im worst case maxdeg(G) Farben.

Wie bei Euler- und Hamiltongraphen kann man auch für Färbungen wie oben die Knoten oder eben die Kanten färben, Wir diskutieren das kurz:
+ - Def: Sei G=(V,E) ein Graph.
Eine Kantenfärbung mit k Farben von G ist eine Abbildung
c: E -> [k] mit der Eigenschaft, das
für alle Kanten e, f ∈ E mit e ∩ f ≠ ∅ gilt c(e)≠c(f).
e und f haben also mindestens einen gemeinsamen Knoten

Def: Zu einem Graphen G ist der chromatische Index (χ'(G))
das minimale k, für das eine Kantenfärbung für G existiert.
Da alle Kanten, die von einem Knoten ausgehen, unterschiedliche Farben haben müssen, muss χ′(G) ≥ maxdeg(G) gelten. Andererseits gilt.
+ - Satz (Vizing, 1964): χ′(G) ≤ maxdeg(G) + 1
Zum Beweis gab Vizing einen Algorithmus an, der in O(|V|*|E|) eine Kantenfärbung liefert.

+ - BSP Petersen-Graph: χ=3, χ'=4
+ -

~ en.wikipedia.org > Wiki > Chromatic index

Das Problem zu entscheiden, ob für einen gegebenenen Graphen G   χ′(G) = maxdeg(G) oder χ′(G) = maxdeg(G) + 1 gilt. ist aber wieder NP-vollständig (Holyer, 1981). Dabei gilt:
+ - Satz (Erdős & Wilson 1977): χ′(G) = maxdeg(G) für fast alle Graphen
+ - Paul Erdös,
~ de.wikipedia.org > Wiki > Paul Erd%C5%91s

+ - Erdös-Zahl
~ de.wikipedia.org > Wiki > Erd%C5%91s-Zahl

+ - Matching
+ - Es sind oft Elemente einer Menge einer anderern paarweise zuzuordnen, z.B. Stellen zu Arbeitssuchenden. Zeitungsartikel den Plätzen auf einer Seite, Vorlesungen zu Räumen, etc. Das kann man mit Matchings modellieren.
BSP: Fünf Vorlesungen V25M, V40B, V45, V60B und V200M suchen entsprechend grosse Räume, die mit Beamer und/oder Musikanlagen ausgestattet sind.
Dazu gibt es folgende Hörsääle mit Platzzahlen und Ausstattung: H200BM, H150B, H100B, H120M, H50BM.
Gibt es ein sinnvolle Verteilung der Vorlesungen auf die Hörsääle?

Def: Sei ein Graph G=(V,E) gegeben.
Eine Teilmenge M von E heisst Matching oder Paarung,
wenn die Kanten von M paarweise keine gemeinsamen Knoten haben, d.h.
für alle e, f aus M gilt e∩ f = ∅.
Def: Ein Knoten k heisst (von einem Matching) überdeckt,
wenn er in einer Kante des Matchings enthalten ist.
Def. Ein Matching M eines Graphen G=(V,E) heisst maximal,
wenn für alle Kanten e aus E-M gilt M∪{e} ist kein Matching mehr.
+ - Def. Ein Matching M eines Graphen G=(V,E) heisst perfekt,
wenn für alle Knoten überdeckt sind.
BSP: links einfache, rechts perfekte Paarung

+ - Nicht für alle Graphen kann man ein perfektes Matching finden. Z.B. bei Sterngraphen besteht jede Matching nur aus einer Kante.
BSP: Sterngraphen S(4), S(6)

+ - Satz (Heiratssatz, Hall 1935): In bipartiten Graphen G mit Bipartition {A,B} existiert genau dann eine Paarung, die jeden Knoten aus A überdeckt, falls für jede Teilmenge S von A gilt, dass ihre Nachbarschaft mindestens so groß ist wie S selbst.
Die Nachbarschaft einer Knotenmenge sind die Nachbarn all ihrer Knoten.

Korollar: Erfüllt ein bipartiter Graph G = (V, E ) die Bedingungen des Satzes von Hall, so kann man ein Matching M der Kardinalität |M | = |A| in Zeit O(|V |*|E |) bestimmen.

+ - Zahlentheorie und Arithmetik
Die hier vorgestellten Zusammenhänge werden in der Mathematk idR unter dem Oberbegriff "Zahlentheorie" oder "Grundlagen der Algebra" gelehrt. Es geht um (ganze) Zahlen und eigentlich einfache Eigenschaften derselben.
Damit ist die Formulierung einfacher Hypothesen möglich, deren Beweise (oder Widerlegungen) aber teilweise noch ausstehen und sich als erstaunlich hartnäckig erweisen.
+ - Zahlentheorie
Die Menge der ganzen Zahlen ist bezüglich der Division nicht abgeschlossen. Deswegen ist interessant zu untersuchen, wann Divisionsergebnisse wieder in den ganzen Zahlen liegen.
Def. Seien n und m ganze Zahlen, Man sagt m teilt n (m|n),
wenn es eine ganze Zahl k gibt, für die gilt: k*m = n
Def: Für natürliche Zahlen n und m bezeichnet
ggT(n,m) := max {d : d|m und d|n}
den grössten gemeinsamen Teiler von n und m
Def: Für natürliche Zahlen n und m bezeichnet
kgV(n,m) := min {v : m|v und n|v}
das kleinste gemeinsame Vielfache von n und m
+ - Def (eulersche Phi-Funktion):
Die eulersche Phi-Funktion φ ordnet natürlichen Zahlen > 1 die
Anzahl der teilerfremden Zahlen zu, die kleiner als n sind:
φ(n) := | { m∈N : m<n und ggT(m,n)=1 } |
BSP: φ(5)=4, φ(6)=2, φ(7)=6, φ(12)=4, ...

+ - Modulo-Arithmetik
+ - Def: Sei m eine ganze Zahl und m>2.
Zwei ganze Zahlen a, b heissen genau dann kongruent modulo m,
wenn gilt m|(a-b).
Man schreibt dann a ≅ b (mod m), auch a ≡ b (mod m) oder a = b (mod m)
Diese Definition ist aequivalent mit der Fomulierung:
Es gibt ein k aus Z, so dass gilt a = b + km
Für jedes m definiert "= (mod m)" eine Aequvalenzrelation (transitiv, refleyxiv, symmetrisch)
mit m Aequvalenzklassen auf Z , und
Z_m = {0,1,...,m-1} ist ein Repräsentantensystem.
Mit obiger Überlegung schreibt man auch (a mod m) für den
Repräsentaten der r, für den gilt a = floor(a/m) * m + r
(r ist also der Rest bei ganzzahliger Division durch m)
Es gilt dann:
a ≅ b (mod m)    genau dann, wenn   (a mod m) = (b mod m)

+ - Satz: Für a,b, m aus Z und m > 1 gilt:

(a+b) mod m = ((a mod m) + (b mod m)) mod m

(a*b) mod m = ((a mod m) * (b mod m)) mod m

Bew: Nun. es gibt ja ganze Zahlen A und B mit
a = A*m + (a mod m) und b = B*m + (b mod m).
Also (a+b) = (A+B)*m + (a mod m) + (b mod m), nd m´damit (1).
Teil (2) folgt dann mit (1) und der Beobachtung. das A*m mod m = 0 ist.

+ - Der Satz erspart uns (und unseren Rechnern) ggf. das Rechnen mit sehr grossen Zahlen, wenn uns nur das Ergebnis modulo m interessiert. Und das tut es oft, u.a. bei der Verschlüsselung.
Oft wird modulo-Arithmetik auch bei Bestimmung von Checksummen verwendet

+ - BSP: Für die RSA-Codierung, die auf dem Chinesischen Restsatz beruht, ist
e der Verschlüsselungs-Exponent,.
N = RSA-Modul, Produkt zweier Primzahlen,
K der Klartext, und C der Code.
Für d gilt e*d ≅ 1 (mod φ(N))
Verschlüsseln: C ≅ K^e mod N
Entschlüsseln: K ≅ C^d mod N
~ de.wikipedia.org > Wiki > RSA-Kryptosystem
BSP: e=23, N = 143, d= 47. Kodiert werden soll 5
Zu berechnen sind dann:
C=5²³ mod 143
= (((5²)²*5)²*5)²*5 mod 143
= ((53 *5)²*5)²*5 mod 143
= (122²*5)²*5 mod 143
= (12*5)²*5 mod 143
= 125
und 125⁴⁷ mod 143
= ((((125²)²*125)²*125)²*125)²*125 mod 143
= ((((38)²*125)²*125)²*125)²*125 mod 143
= (((14*125)²*125)²*125)²*125 mod 143
= ((34*125)²*125)²*125 mod 143
= (27*125)²*125 mod 143
= 5

+ - BSP: die letzte Stelle der ISBN-Nummer (ISBN-10, bis 2006) ist die nach Position gewichtete Summe der Ziffern davor mod 11. Einfache (Tipp-)fehler sind dann leicht zu erkennen.
ISBN 3-540-46660-6
1*3 + 2*5 + 3*4 + 4*0 + 5*4 + 6*6 + 7*6 + 8*6 + 9*0 = 171
171 mod 11 = 6
Die Prüfziffer bei ISBN-13 berechnet sich übrigens so:
z_13 = (10 - (( z_1 + z_3 + z_5 + z_7 + z_9 + z_11 + 3*(z_2 + z_4 + z_6 + z_8 + z_10 + z_12)) mod 10)) mod 10

+ - BSP: Ein vergleichbares Verfahren verwendet das EAN-Barcode,
~ de.wikipedia.org > Wiki > European Article Number

BSP (Teilbarkeitskriterien): Eine Zahl ist durch 3 teilbar, wenn ihre Quersumme durch drei teilbar ist. - mit Teil (2) des Satzes einfach beweisbar.

+ - Satz: Für a,b,c,d,m aus Z und m > 1 mit
a ≅ b mod m und c ≅ d mot m gilt:

(a+c) mod m = (b+d) mod m

(a*c) mod m = (b*d) mod m

Bew.: Es gibt A, C mit a-b=A*m, c-d=C*m, mithin (a+c)-(b+d) = (A+C)*m.
Teil (2) entsprechend.
Achtung - die Umkehrung gilt i.A,. nicht. Insondere folgt aus (a*c) ≅ (b*c) mod m nur. wenn m und c teilerfremd sind auch a ≅ b mod m.

+ - ggT: Der Algorithmus von Euklid
+ - Satz: Für natürliche Zahlen mn, mit m<n, wobei m n nicht teilt, gilt
ggT(m.n) = ggT(n mod m, m)
Bew:
1) Es gibt ein k mit (n mod m) = n - k*m.
  Wenn gilt d|m und d|m, dann gilt also auch d|(n mod m)
2) Gilt d|(n mod m) und d|m, dann gilt wegen
  n = k*m + (n mod m) auch d|n.

Dieser Satz liefert einen effizenten Algorithmus zur Berechnung des ggT zweier Zahlen:
+ - Der euklidische Algorithmus:
function euklid(m,n) { if (m teilt n) return m else return euklid(n mod m, m); }

+ - Der euklidische Algorithmus, Variante1:
function euklid(m,n) { if (m=0) return n else return euklid(n mod m, m); }

BSP: euklid(15,10) -> euklid(10,15) -> euklid(5,10) -> euklid(0,5) -> 5

BSP: euklid(8,12) -> euklid(4,8) -> euklid(0,4) -> 4

+ - Der Chinesische Restsatz:
I.A. sind in der Modularithmetik Lösungen linearer Gleichungen nicht mehr so eindeutig.
Gibt es eine Lösung x für die Gleichung a*x = b mod m, so ist auch auch x+k*m für alle ganzen Zahlen k eine Lösung.
Schränkt man den Lösungsbereich auf das Repräsentantensystem ein, kann es eine oder mehrere Lösungen geben. z.B:
2*x = 4 mod 6 hat die Lösungen x=2 und x=5.

+ - Satz: Für natürliche Zahlen a_1,..., a_k, m_1, ..., m_k, wobei die m_i
paarweise teilerfremd sind, und m:=m_1*...*m_k, gibt es
genau ein x aus Z_mmit:
x = a_1 mod m_1,
x = a_2 mod m_2,
...
x = a_k mod m_k.
Man kann den Satz recht einfach mit unseren bekannten Methoden beweisen, indem man die Bijektivität der Abbildung x -> (x mod m_1, ... , x mod m_k) nachweist.
Meist wird er allerding mit dem etwas kompexerern Vokabular und den Methoden der Algebra beweisen, z.B. bei Wikipedia:
~ de.wikibooks.org > Wiki > Beweisarchiv: Algebra: Ringe: Chinesischer Restsatz

+ - Primzahlen
Natürlich teilt 1 alle ganzen Zahlen, und jede Zahl teilt sich selbst.. Primzahlen sind nun die positiven Zahlen, die nur diese beiden (trivialen) Teiler haben:
+ - Def: Eine natürliche Zahl p>1 heisst Primzahl oder prim,
wenn nur p selbst und 1 p teilen.
Don Zagier, Max-Planck-Institut für Mathematik in Bonn: "... gehören sie trotz ihrer einfachen Definition zu den willkürlichsten, widerspenstigsten Objekten, die der Mathematiker studiert. Sie wachsen wie Unkraut unter den natürlichen Zahlen, scheinen keinem anderen Gesetz als dem Zufall unterworfen". Zugleich zeigten sie aber "die ungeheuerlichste Regelmäßigkeit auf und sind durchaus Gesetzen unterworfen, denen sie mit fast peinlicher Genauigkeit gehorchen".
Aus:
~ spektrum.de > Artikel > 972374& z=798888
Beachte: 1 ist keine Primzahl

+ - Satz (Euklid): Es gibt unendlich viele Primzahlen
Bew: Angenommen, es gäbe nur endlich viele - p_1 bis p_n.
Es ist aber dann q := (p_1 * p_2 * .... * p_n) + 1 eine Zahl, die nicht durch p1_1, ... p_n teilbar ist. Es muss aber eine Darstellung von n als Produkt von primzahlpotenzen geben - Widerspruch! - q.e.d.

+ - Def: π(n) := |{p≤n : p ist prim}| bezeichnet die Anzahl der Primzahlen kleiner oder gleich n.
BSP: π(10) = 4, π(100) = 25, π(1000) = 168.

+ - Satz: Für alle natürlichen Zahlen n gilt:
π(n) = (1 + o(1)) * n / ln(n)
In der Praxis ignoriert man den o(1)-Term meist, und schätzt π(n) direkt mit n/ln(n) ab.
BSP: Es ist exp(10) ≈ 22062, ln (exp(10)) = 10, also gibt es etwa 2206 Primzahlen die kleiner als 22062 sind.

Ungelöst ist die Frage nach der Anzahl der Primzahlzwillige, also der Zahlen. bie denen p und p+2 Primzahlen sind.
+ - Vermutung (Goldbach): Jede gerade Zahl >3 lässt sich als Summe zweier Primzahlen ausdrücken.
4=2+2, 6=3+3, 8=5+3, 10=5+5, 12=7+5, 14=7+7. 16=11+5, 18=11+7, 20=13+7, ...

+ - Vermutung: Es gibt unendlich viele Primzahlzwillinge
3,5 - 5,7 - 11-13 - 17,19, ...

~ spektrum.de > Artikel > 972374& z=798888
Primzahlzwillinge müssen die Form 6n-1, 6n+1 haben. Sie werden inzwischen auch per Compouter gejagt, Anfang 2009 sind zwei Zahlen mit fast 59000 Dezimalstellen das grösste bekannte Zwillingspaar.

+ - Satz (Fundamentalsatz der Arithmetik)
Sei n eine natürliche Zahl, n>1. Dann lässt sich n (bis auf die Reihenfolge)
eindeutig als ein Produkt von Primzahlpotenzen darstellen:
n = p_1^i_1*p_2^i_2*...*p_k^i_k, p_1,...p_k prim, i_1,...,i_k∈N
Bew (Existenz) - .B. durch Induktion nach n:
IA: n=2 - 2 ist prim.
IS: n
Fall 1: n ist prim - fertig.
Fall 2: Es gibt Zahlen m und k mit n=m*k.
dann greift die Induktionsvoraussetzung für m und k, udn wir haben ein Produkt von (Produkten von) Primzahlpotenzen.
- q.e.d.
Bew. (Eindeutigkeit)
Angenommen, es gebe für eine Zahl zwei verschiedene Zerlegungen D1=D2 in Prinzahlpotenzen.
Dann kann man die gleichen Primzahlen auf beiden Seiten der Gleichung kürzen
und kommt zu einer Gleichung mit ungleichen Primzahlen:
p_1^i_1*p_2^i_2*...*p_k^i_k = p_k+1^i_k+1*p_k+2^i_k+2*...*p_l^i_l , p_1,...p_l prim, i_1,...,i_l∈N
Rechte und linke Seite müssend dann gemeinsame Teiler haben, und
insbesondere teilt dann p_1 die rechte Seite, also eine der Primzahlen dort.
Dann ist das aber keine Primzahl mehr - Widerspruch! - q.e.d.

Viele aktuelle Kryptographieverfahren beruhen darauf, das es schwer ist, grosse Zahlen in Faktoren zu zerlegen, insbesondere wenn die grosse Zahl aus zwei auch grossen Primzahlen besteht - siehe Hinweise zum RSA-Verfahren bei der Modulo-Arithmetik
+ - Fermatsche Primzahlen
Fermat vermutete, er habe eine gute Methode gefunden, grosse Primzahlen zu finden:
+ - Def: Eine Primzahl p = 2ⁿ+1 heisst Fermatsche Primzahl
Natürlich sind nicht alle Zahlen der Form Primzahlen!

BSP: 3, 5, 17 sind prim, 9 nicht.

Def: Eine Zahl F(n) = 2^m+1 mit m=2ⁿ, m.n∈N,
heisst n-te Fermatsche Zahl
+ - Satz: Eine Fermatsche Primzahl ist eine Fermatsche Zahl
Bew: Annahme, eine Fermatsche Primzahl enthalte im Exponenten
einen ungeraden Faktor u: p=2^u*v+1 = (2^v)^u+1 = a^u+1,
mit a=2^v. Für ungerade Exponenten (und nur für solche) kann man aber a^u+1
zerlegen: a^u+1 = (a+1)*(a_u-1-a_u-2+ ...+a²-a+1)
Also ist p nicht prim - Widerspruch! - q.e.d.

F(0) = 3, F(1) = 5, F(2) = 17, F(3) = 257, F(4) = 65537 sind prim.

F(5) = 4294967297 = 641*· 6700417 ist nicht prim (Euler, 1732)
F(6) = 274177 * 67280421310721 ist nicht prim (Landry, 1880)
F(7) = 59649589127497217 * 5704689200685129054721 (Morrison/Brillhart, 1970)

Auch für einige grösserer Fermatsche Zahlen sind Zerlegungen bekannt.
Man vermutet inzwischen, das nur F(0), ..., F(4) Primzahlen sind.

+ - Mersenne-Primzahlen
+ - Def: Eine Primzahl p = 2ⁿ-1 heisst Mersenne-Primzahl
Natürlich sind nicht alle Zahlen der Form Primzahlen!
BSP: 3, 7, 63 sind prim, 15 nicht.
Für Mersenne-Zahlen lässt ist ein relativ einfacher, effizienter Primzahltest, der Lucas-Lehmer-Test, anwenden. Deswegen sind die grössten bekannten Primzahlen sind meistens Mersenne-Primzahlen.
Gemeldet wurden 2008 zwei neue grösste bekannte Primzahlen:
2^37156667-1 mit 11185272 Stellen, und
2^43112609-1 mit 12978189 Stellen.
Bei der Suche nach grossen Primzahlen werden seit 1951 Computer eingesetzt.
Bis 1996 waren das idR einzelne (Super-)Computer, danach ein per Internet verteilt rechnendes System GIMPS (engl.: Great Internet Mersenne Prime Search), das die Leerlaufzeiten von Rechnern ausnutzt.

+ - Primzahltests
Dividieren bis zum Wert der Wurzel

~ de.wikipedia.org > Wiki > Sieb des Eratosthenes

Lukas-Lehmer-Test: Nur für Mersenne-Zahlen

+ - Wahrscheinlichkeitstests
Fermatscher Primzahltest, Basis: kleiner Fermatscher Satz
Solovay-Strassen-Test,
Basis: Satz nach Euler und Jacobi-Symbol,
liefert: Eulersche Pseudoprimzahlen
Miller-Rabin-Test
Basis: Satz nach Miller
liefert: starke Pseudoprimzahlen

+ - Der kleine Fermat
+ - Satz: Sei n ein natürliche Zahl, n>1 mit folgender Primzahlzerlegung:
n = (p_1)^m_1*(p_2)^m_2* ... *(p_k)^m_k
Dann ist φ(n) = (p_1-1)(p_1)^m_1-1* ... * (p_k-1)(p_k)^m_k-1
Beim Beweis hilft folgendes Lemma:

+ - Lemma: Sei p ein Primzahl, k∈N, dann ist
φ(p^k) = p^k(1 - 1/p)
Bew: Es gibt p^k Zahlen, die kleiner oder gleich p^k sind.
Darunter teilen genau die Vielfachen von p p^k. Wie viele
gibt es da? Nun - genau p^k-1. Also sind die teilerfremden Zahlen die Differenz:
φ(p^k) = p^k - p^k-1 = p^k(1 - 1/p) - q.e.d.

+ - Satz (Euler): Für alle natürlichen Zahlen n > 1 gilt
für alle a mit ggT(n,a)=1, n>a>0:
a^φ(n) ≅ 1 (mod n)
Bem. Für Primzahlen p gilt natürlich φ(p) = p-1

+ - Satz ("kleiner Fermat"): Für alle natürlichen Zahlen p>1 gilt:
p ist genau dann eine Primzahl, wenn
für alle m aus Z_p-{0} gilt: m^p-1 ≅ 1 (mod p)
Bew: "=>" liefert die o.g. Bemerkung und der Satz von Euler
Bew "<=": Sei q ein beliebiger Teiler von p, dann gibt es k und l mit
q^p-1 = 1 + k*p, und l*q=p, also
q^p-1 - 1 = k*l*q
Das kann nur für q=1 allgemein gelten, also ist p prim.
+ - BSP:
p=4, Z_p={0,1,2,3},
1*1*1 = 1 ≅ 1 (mod 4)
2*2*2 = 8 ≅ 0 (mod 4)
3*3*3 = 27 ≅ 3 (mod 4)
p=5, Z_p={0,1,2,3,4},
1*1*1*1 = 1 ≅ 1 (mod 5)
2*2*2*2 = 16 ≅ 1 (mod 5)
3*3*3*3 = 81 ≅ 1 (mod 5)
4*4*4*4 = 256 ≅ 1 (mod 5)

+ - Arithmetik
+ - Polynome
Polynome sind einfache - insbesondere einfach zu differenzierende - Funktionen, mit
denen sich fast alle komplizierteren Funktionen gut annnähern lassen. Ihre Werte sind
dabei in akzeptabler Zeit zu berechnen.
In der Algebra betrachtet man Polynome "über" (d.h. mit Koeffizienten aus) beliebigen
(Zahl)Körpern, hier werden wir nur Polynome über den rellen Zahlen (R) oder
den komplexen Zahlen (C) behandeln.
+ - Def. Seien a₀, ... , a_n Zahlen aus einem Körper K, dann ist
p(x) := a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀
ein Polynom über K. Dabei grad(p) oder deg(p) := n ist der Grad des Polynoms
p ist also eine Funktion. Definitions- und Wertebereich kann dabei mit dem Körper K übereinstimmen,. muss es aber nicht.
+ - BSP: p(x) = 10
ein konstantes Polynom

+ - BSP: p(x) = 2,3 x + 4
ein lineares Polynom. Es definiert eine Gerade in der Ebene.

+ - BSP: p(x) = x²-4x +3
ein quadratisches Polynom. Eine etwas gestörte Parabel

Entscheidend für das Wachtumsverhalten der Polynome ist die grösste Potenz. Ist sie gerade, ist das Wachstumsverhalten für + und - unendlich gleich, ist sie ungerade, genau entgegengesetzt
+ - BSP:
+ - p(x) = x

+ - p(x) = x²

+ - p(x) = x²+x

+ - p(x) = x³

+ - p(x) = x³+x²

Für gegebenen x kann man die Werte von Polynomen mit einem Schema effizient ausrechenen: Statt alle Potenzen zu bilden und zusätzlich die Koeffizienten zu multiplizieren, rechnet man mit folgender Klammerung:
+ - Def. Sei p(x) = a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀
Dann ist p(x) = (((...(a_n*x+a_n-1)*x+a_n-2)*x+a_n-3)...+a₁)x+a₀,
und diese Darstellung nennt man Horner-Schema
Das Horner-Schema ist mit folgendem Algorithmus zu berechnen:

INPUT: x enthalten den Argumentwert, das Array a[] die Koeffizienten. OUTPUT: Der Wert p(x) in der Variable p p = a[n]; for (i=n; i>0 ; i = i-1) { p = p*x + a[i-1] }

Man kann den Wert eines Polynoms für einen Wert also in O(n) Schritten (Multiplikationen und Additionen) berechnen.

BSP

Das Wachumsverhalten ist für betragsmässig grosse Werte also festgelegt. Interessanter sind oft die kleineren Werte. Uns interessieren vor allem Werte, bei denen die Kurve einen Nulldurchgang hat. Dazu:
+ - Rechnen mit Polynomen
+ - Def. Für zwei Polynome
p(x) = a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀ und
q(x) = b_mx^m+b_m-1x^m-1+...+b₁x+b₀ ist
(p+q)(x) := p(x)+q(x), und
(p-q)(x) := p(x)-q(x)
(pq)(x) := p(x)*q(x)
Ergänzt man ggf. fehlende Potenzen mit dem Koeffizienten 0,
also z.B 4*x⁵+3*x²+1
zu 4*x⁵+0*x⁴+0*x³+3*x²+0*x+1, kann man auch gleich Formeln angeben:
+ - Mit k:=max(n,m) ist
(p+q)(x) = (a_k+b_k)x^k+(a_k-1+b_k-1) x^k-1+...+(a₁+b₁)x+(a₀+b₀)
(p-q)(x) = (a_k-b_k)x^k+(a_k-1-b_k-1) x^k-1+...+(a₁-b₁)x+(a₀-b₀)
(pq)(x) = c_n+mx^n+m+c_n+m-1x^n+m-1+...+c₁x+c₀,
wobei für i=0,..., n+m: c_i := ∑_j=0,...,ia_jb_j-i
BSP p(x) = 2x²-3x+5, q(x)=4x²+2x-12
pq(x) = (2*4)x⁴ + (2*2+(-3)*4)x³ + (2*(-12)+(-3)*2+5*4)x² + ((-3)*(-12)+5*2)x + 5*(-12)
Die neuen Koeffizienten ergeben sich also als Summen von Produkten von Koeffizienten, deren Indices in der Summe den aktuellen Exponenten ergeben - z.B c3 = a3*b0+a2*b1+a1*b2+b3*a0

Für die Division finden wir eine Division mit Rest:
+ - Satz: Seien a(x), b(x) zwei Polynome, und b(x) nicht Null.
Dann gibt es eindeutig bestimmte Poynome q(x) und r(x) mit
1. a(x) = q(x)b(x) + r(x)
2. r(x) = 0 oder deg(r)<deg(b)

+ - BSP
a(x) = x³+3x²-2x-5
b(x) = x+6

  x³+3x² -2x -5 : x+6 = x²-3x+16
- (x³+6x²)
-----------
      -3x² -2x -5
  -   (-3x²-18x)
      -------------
             16x-5
          - (16x+96)
            -----------
                   -101   = r(x)

q(x) = x²-3x+16
Probe:
(x²-3x+16)(x+6) -101
= x³-3x²+16x + 6x²-18x+96 -101
= x³ +3x² -2x -5 - stimmt.

Bew: 1. Existenz: Für den Fall, das deg(b)>deg(a) ist, ist offenbar mit r:=a a = 0*q + a der Satz erfüllt.
Wir betrachten also nur noch den Fall deg(a)>=deg(b),
und führen eine Induktion nach deg(a) aus.
IA: deg(a)=0=deg(b) => a und b sind konstant. a(x)=a_0, und b(x)=b_0.
Damit erfüllt t(x) = a_0/b_0 und r(x)=0 die Erwartungen

IS: Sei nun also deg(a)>0, und deg(b)≤deg(a), und sei
a(x) = a_nxⁿ+a_n-1x^n-1+...+a₁x+a₀, und
b(x) = b_mx^m+b_m-1x^m-1+...+b₁x+b₀.
Sei s(x) := a(x)-(a_n/b_m)x^n-mb(x)
Das ist ein Polynom mit kleinerem Grad als a(x), und damit gibt es nach IV eine Darstellung
s(x) = t(x)b(x) +r(x).
Es ist dann also a(x)=s(x)+(a_n/b_m)x^n-mb(x) = t(x)b(x)+(a_n/b_m)x^n-mb(x)+r(x)
= (t(x)+(a_n/b_m)x^n-m) b(x) + r(x),
wir haben also eine Darstellung für a(x) als Produkt mit Rest wie im Satz gefunden.
Bew. 2. Eindeutigkeit
Angenommen. es gäbe zwei Darstellungen der o.g. Form, also
a(x) = q1(x)b(x) +r1(x) = q2(x)b(x) +r2(x)
Dann gilt auch (q1-q2)b = r2-r1
Wenn q1-q2 nicht Null ist, ist deg((q1-q2)b) >= deg(b).
Es ist aber deg(r2-r1) < deg(b) -- Widerspruch!

Die Polynome q und r aus dem obigen Satz lassen sich - bei Vorgehen wie im Beispiel - in O(n²) schritten bestimmen.
Man kann die Begriffe teilt und Teiler ganz kanonisch
auf Polynome erweitern, damit auch die gesamte Modulo-Rechung,
und auch den ggT zweier Polynome mit dem Euklidischen Algorithmus bestimmen.

+ - Def: Für ein Polynom p(x) heisst ein Wert x₀
mit p(x₀) = 0 Nullstelle von p.
Für lineare Polynome ist das einfach: x-a = 0 genau dann, wenn x=a.
+ - Für quadratische Polynome kann man eine Formel herleiten:
ax²+bx+c = 0 , also x² + (b/a)x +c/a = 0, mit Umbenennung:
ist die normierte Form x² + px     +q   = 0

Lösung durch quadrat. Ergänzung. Mit
(x+s)² = x² +2sx + s² -- identifiziere p=2s --> s² = (p/2)²

x² + px + q = 0
x² + px = -q     ergänze (p/2)²
(x+p/2)² = +(p/2)² -q
x+p/2 = +/- sqrt((p/2)² -q)
x1 = -p/2 + sqrt((p/2)² -q)
x2 = -p/2 - sqrt((p/2)² -q)

+ - Für (reduzierte) kubische Polynome gibt es auch - kompliziertere - Formeln, die cardanischen Formeln. Auch für Polynome vierten Grades gibt es noch Formeln, für allgemeinere Polynome höheren Grades sind nur noch für Spezialformen Formeln bekannt.
~ de.wikipedia.org > Wiki > Cardanische Formeln

Man kann aber die Schwierigkeit reduzieren, wenn man schon eine Nullstelle kennt, denn, wenn x1 eine Nullstelle von p(x) ist, dann gibt es ein Polynom q(x) mit grad(q) = grad(p)-1, und p(x)=(x-x1)q(x), und die weiteren Nullstellen von p und q stimmen überein.
+ - Satz: Ein Polynom p≠0 über den reellen Zahlen hat höchstens deg(p) Nullstellen.
Anschaulich ist das recht klar.
Bew: (Induktion über deg(p))
IA: deg(p)=0, also p(x) konstant ungleich 0 - ok.
IS: Sei deg(p)=n>0. Hat p keine Nullstelle, ist der Satz erfüllt.
Hat p eine Nullstelle p0, so gibt es Polynome q, r mit
p = q(x-p0)+r, deg(r)<deg(x-p1)=1, also deg(r)=0.
r ist also konstant, und für x=p0 liefert die Gleichung dann 0=0+r,
also ist r=0.
Damit ist p = q(x-p0)., und deg(q) = deg(p)-1,
q hat also nach IV maximal n-1 Nullstellen - q.e.d.

+ - Fundamentalsatz der Algebra
(Prosavariante) Über den komplexen Zahlen
zerfällt jedes Polynom vollständig in lineare Faktoren.
+ - (formalere Variante) Ein Polynom p vom Grad n über
den kompleyen Zahlen C hat genau n komplexe Nullstellen.
Die Nullstellen müssen dabei nicht unbedingt verschieden sein, sie können mit einer gewissen Häufigkeit auftreten

+ - Sind die Nullstellen p_1, ... p_n, und ist p normiert, so ist
p(x) = (x-p_1)(x-p_2)...(x-p_n).

Ist p nicht normiert, kommt noch der höchste Koeffizient als konstanter Faktor im Produkt dazu.

BSP: x³-7x²+15x-9 = (x-1)(x²-6x+9) = (x-1)(x-3)(x-3)

BSP: x²+1 = (x+i)(x-i)               = x²-i²

Das leuchtet dann ein, wenn man bedenkt, das über den reellen Zahlen allein die Existenz der Quadratwurzel problematisch ist. Im Komplexen existiert die Wurzel auch auch von negativen Zahlen (i=√-1). Formal zu beweisen ist das in der Algebra recht schwer, mit Mitteln der Funktionentheorie recht leicht.

+ - Einheitswurzeln
Def: Im Körper der kompexen Zahlen zerfallen für alle n=0,1,2,...
die Polynome (xⁿ-1) in n verschiedene Nullstellen,
1, ω, ω², ω³, ..., ω^n-1.
ω heisst dann n-te Einheitswurzel
+ - Satz: Im Körper C ist für jedes n=0,1,2,...
ω=exp(2πi / n) eine n-te Einheitswurzel.
Bew: exp(2πi/n)ⁿ = exp(2πi)= 1

+ - Partialbruchzerlegung
Weil der Begriff häufiger auftaucht, möchte ich ihn hier auch kurz einführen, ohne mehr damit zu machen:
Def.: Für zwei Polynome p, q ist eine Partialbruchzerlegung
eine Darstellung des Quotienten p/q als Summe von
Brüchen, bei denen die Nenner Potenzen von linearen Funktionen sind.
Im Komplexen gilt genauer:
Ist für geeignete k, m_1, ... m_k, a_1, ...a_k
q(x) = (1-a₁x)^m_1(1-a₂x)^m_2...(1-a_kx)^m_k
so gibt es Polynome r₁, ... r_k mit
p(x) / q(x) = r₁(x)/(1-a₁x)^m_1 + ... + r_k(x)/(1-a_kx)^m_k

+ - Funktionsapproximation
Satz (Approximationssatz von Weierstraß): Jede stetige Funktion läßt sich auf einem kompakten Intervall gleichmäßig durch Polynome approximieren.
+ - BSP: Taylorpolynome

~ de.wikipedia.org > Wiki > Taylorreihe

~ Karl Weierstraß
Da Polynome stark oszillieren, nimmt man auch gern zur Polynomstückchen zur Funktionsinterpolation:
+ - ~ Ein Spline n-ten Grades ist eine stückweise aus
Polynomen mit maximalem Grad n zusammengesetzte Funktion.
An die Stellen, an denen zwei Polynomstücke zusammenstoßen werden dabei noch bestimmte Bedingungen z.B. bezüglich der Differenzierbarkeit gestellt.

+ - Was macht Funktionsapproximationen eigentlich interessant?
Manchmal hat man gar keine Funktionen, sonder nur Messwerte

Manchmal sind die Approximationen gutmütiger, und hinreichend für die Modellierung.

+ - CRC
+ - Eine Korrektheitsprüfung durch (binäre) Polynomdivision mit einem Generatorpoynoms ist das Verfahren hinter dem Begriff zyklischen Redundanzprüfung (Cyclic Redundancy Check).
Effizient muss das deswegen sein, damit es eine Datenübertragung nicht verlangsamt, sondern parallel dazu ohne wesentliche Mehrlast berechnet werden kann.
Effizient ist das, weil die Polynomdivision binar eine einfache xor-operation ist. Das ist eine Eigenschaft den zugrunde liegenden Zahlkörpers:
+ - Zahlkörper F₂:
+ -

+ 0 1

0 0 1

1 1 0

* 0 1

0 0 0

1 0 1

Dazu kommt, das die Subtraktion gleich der Addition ist, da in diesem etwas seltsamen Körper -1 = 1, also 1 das Inverse Element zu 1 ist, Zusammen mit dem sich ergebenden Übertrag wandelt sich die auszuführende Operation in ein bitweises entweder-oder (xor).

Bei der Polynomdivision kommt nun zum tragen, das im Ergebnis eine 1 den Divisor kopiert, eine 0 nur (eine 2er-Potzenz) shiftet.
Dieses Verfahren lässt sich effizient mit Schieberegistern realisieren, die auch in Hardware realisiert werden können. Das ist - schnell!
+ - Die Qualität der Prüfung hängt vom gewählten CRC-Polynom ab. Ethernet, FDDI, ZIP und PNG benutzen z.B das Polynom
CRC-32 = 0x04C11DB7 = 0000 0100 1100 0001 0001 1101 1011 0111
(Die führende 1 an der 33. Bitposition wird nicht gespeichert.)
CRC-32 = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1
(V.42, MPEG-2, PNG [14], POSIX cksum)
CRC-1 = x + 1 (Parity Bit)
CRC-5-USB = x⁵ + x² + 1 (USB token packets)
CRC-24-Radix-64 = x²⁴ + x²³ + x¹⁸ + x¹⁷ + x¹⁴ + x¹¹ + x¹⁰ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x + 1
(OpenPGP)
~ en.wikipedia.org > Wiki > Cyclic redundancy check#Commonly used and standardised CRCs

+ - BSP
Nachricht= 1101011011, Generatorpolynom = 10011
11010110110000 Nachricht wird um (Länge des G-Polynoms)-1 Nullen aufgestockt 10011 ----- 10011 und somit geringerwertig wäre als das Generatorpolynom) 10011 ----- 000010110 10011 ----- 010100 10011 ----- 1110 (Rest)
Übertragen wird nun die Nachricht+Rest: 11010110111110
Beim Empfang wird nun wieder durch das CRC-Polynom dividiert:
11010110111110 10011 ----- 10011 10011 ----- 000010111 10011 ----- 010011 10011 ----- 00000
Geht das ohne Rest auf, ist die Übertragung mit hoher Wahrscheinlichkeit korrekt

+ - Rechnen mit grossen Zahlen
Unter grossen Zahlen verstehen wir Zahlen, die - dargestellt zur Basis 2 - nicht mehr in die Register der verfügbarene Rechner passen.
Aktuell haben Rechner Register mit 32 oder 64 bits, wir meinen also Zahlen, die grösser als 4294967296 bzw. 18446744073709551616 sind.
Additionen von Zahlen in dieser Grössenordnung ergeben wieder diese Grössenordnung, lassen sich also mit einem Maschinenbefehl erledigen.
Mutliplikationen können ja leicht die Stellenzahl verdoppeln, für ein korrektes Ergebnis in einem Maschinenbefehl dürfen also die beteiligten Zahlen sogar nur halb so viele Stellen haben.

Wie wir bei den Primzahlen gesehen haben, kommen grössere Zahlen durchaus vor, und es ist durchaus ein Problem, für sie die Basisoperationen '+', '*' und '/' effizient zu berechnen.
+ - Zahldarstellung
+ - Man kann jede Zahl zu einer geeigneten Basis (üblicherweise mit p bezeichnet)
darstellen. Unsere übliches System ist die Darstellung zur
Basis 10, die dezimale Darstellung:
a = Σ_{k=0,1,...,∞} a_k 10^k.
Für irgendeine natürliche Zahl n sind die a_k mit k>n natürlich alle Null.
Dann nennt man n+1 die Stelligkeit von a.
Wir schreiben a dann statt als Summe als Reihe der Koeffizienten,
beginnend mit dem höchsten Index:
a = a_na_n-1a_n-2... a₀
BSP: 123 = 1*10² + 2*10¹ + 3*10⁰
a₂=1, a₁=2, a₀=3
a = 123
BSP: 123 = 1*2⁶ + 1*2⁵ +1*2⁴ +1*2³ +0*2² +1*2¹ +1*2⁰
a = (1111011)₂
BSP: 123 = 1*8² + 7*8¹ +3*8⁰
a = (173)₈

Die verwendete Basis notieren wir, falls es nicht eindeutig ist in Form einer
Klammer mit Index: (...)_Basis
+ - Für die Berechnung grosser Zahlen wählen wir eine Darstellung zu einer Basis, die der noch handhabbaren Registergrösse (als 2er-Potenz) entspricht, also für 32 Bits die Basis b=2³², etc.
BSP: Wenn wir also von einem (hypothetischen) 3-Bit-Rechner ausgehen, wäre die Basis 2³=8 angemessen. Jedes der Produkte in der Summendarstellung im letzen Beispiel wäre also auf der Maschine in einer Operation berechenbar, die Gesamtsumme aber nicht mehr.

+ - Addition
In dieser Darstellung können wir zwei grosse Zahlen natürlich addieren (und subtrahieren), indem wir jeweils die jeweils gleichen Koeffizienten summieren.
Fehlende Koeffizienten werden auf 0 gesetzt, und Überträge, also das verlassen des
Zahlbereichs, müssen wir berücksichtigen:
+ - Sei x = (x_n...x₀)_b, und y = (y_m...y₀)_b, und sei k:=max(n,m).
Dann ist z = (x+y) = (z_k...z₀)_b mit
z₀ := (x₀ + y₀) mod b,
r₀ := (x₀ + y₀) - ((x₀ + y₀) mod b) mod 2
z₁ := (x₁ + y₁+ r₀) mod b,
r₁ := (x₁ + y₁+ r₀) - ((x₁ + y₁+ r₀) mod b) mod 2
...
z_l := (x_l + y_l+ r_l-1) mod b,
l ist dabei k oder k+1, je nach Übertrag der höchsten Stelle.
BSP:
x = 123 = (173)₈, y = 87 =(127)₈, z=x+y
z0 = (7+3) mod 8 = 2, r0 = 1
z1 = (7+2+1) mod 8 = 2, r1 = 1
z2 = (1+1+1) mod 8 = 3, r2 = 0
x+y = (322)₈ = 3*64 + 2*8 +2 = 210

Die Subtraktion behandelt man analog. Hier fällt sogar der Übertrag weg.
Insgesamt reichen für Addition und Subtraktion O(max(n,m)) Standardoperationen aus.

+ - Multiplikation
Die Muliplikation ist komplizierter.
Kanonisch würde man die Darstellung von oben verwenden,
Faktor für Faktor ausmultipizieren und wieder summieren:

Sei x = (x_n...x₀)_b, und y = (y_m...y₀)_b,
Dann ist x*y = x*Σ_k=0,1,...,m y_k b^k = Σ_k=0,1,...,m (x*y_k*b^k).
Jedes der Produkte x*y_k ist wieder eine Summe
y_k * x = y_k*Σ_j=0,1,...,n x_j b^j = Σ_j=0,1,...,n (y_k*x_j*b^j).
Der bei der einfachen Multiplikation entstehende Übertrag von
r_j = floor(y_k*x_j/b) ist natürlich auch noch geeignet in die Summation aufzunehmen.
+ - Das istl. etwas kompliziert formuliert, das Schema des schriftlichen Multiplizierens:
BSP:
x = 123 = (173)₈, y = 87 =(127)₈, z=x*y
173 * 127 ------------ 173 366 14=1*8+6 1535 21=2*8+5, 49+2=6*8+3, 7+6=1*8+5 ------------ 24715
(24715)8 = 5+7*8+6*8^2+4*8^3+2*8^4 = 10701 = 123*87

Insgesamt erfordert also auf diesem Wege die Multiplikation zweier (zur Basis b) n-stelliger Zahlen O(n^2) Operationen
+ - Mit geschickterer Zusammenstellung kann man bessere werte erreichen.
Das Verfahren von Schönhage und Strassen (1971) benötigt O(n log n log log n) Schritte.

~ de.wikipedia.org > Wiki > Sch%C3%B6nhage-Strassen-Algorithmus

Die Division lässt sich auf die Multiplikation zurückführen, der Berechnungsaufwand liegt also auch in dieser Grössenordnung.

+ - FFT
Der Algorithmus von Strassen und Schönhage macht sich eine Umwandlung des Problems in einen andere Struktur zunutze, er benutzt die schnelle diskrete Fourier-Transormation.
Die prinzipielle Idee dabei ist folgende: Man kann eine Funktion, z.B. ein Polynom, durch eine Funktionalgleichung angeben. Viele Funktionen kann man aber auch eindeutig dadurch bestimmen, das man geeignete Paare von Werten und Funktionswerten ("Stützstellen") angibt.
Insbesondere Polynome vom Grad n sind eindeutig bestimmt, wenn man n solcher Paare angibt.
Bei der FFT sind die Stützstellen idR Einheitswurzeln.
Die Eindeutigkeit erlaubt auch eine Rücktransformation der Darstellung in die ursprüngliche Form.
Nützlich ist das dann, wenn man zu einer schwierigen Operation o auf der Originaldarstellung eine aequivalente. effiziente Operation o' auf der Transformierten findet. Dann kann man
statt

Aufgabe ------ o ------- > Lösung

folgenden Weg realisieren:

Aufgabe --transf.-> DFT(Aufgabe) --o'-> DFT(Lösung) --rücktransf.-> Lösung

Die FFT wird auch sehr erfolgreich in der Signalverarbeitung verwendet.

+ - Kryptographie
~ gnupg.org > Gph > De > Manual

~ openssh.com > Manual

~ RivestShamirAdleman-Kryptosystem

~ matheprisma.uni-wuppertal.de > Module > RSA > Index

~ de.wikipedia.org > Wiki > Digital Signature Algorithm

+ - Rekursionsgleichungen
+ - In den vergangenen Kapiteln sind uns ja wiederholt induktiive Definitionen begegnet, bei denen die Begriffe ausgehend von Anfangswerten dann durch eine Rekursionsgleichung definiert wurden.
Für viele Zwecke ist das auch sehr praktisch, etwa bei der algorithmischen Behandlung von Graphen (insbes. Bäumen), bei denen jeder Knoten besuicht werden muss.
Bei Funktionen dagegen, wo uns eigentlich nur der Funktionswert interessiert, ist es wesentlich effizienter die Rekursionsgleichung aufzulösen und durch eine Funktion zu ersetzen, deren Wert nicht mehr auf den Vorgängerwerten basiert, sondern nur noch vom Index n und den Anfangswerten abhängt, und natürlich auch keine von n abhängigen Summen oder Produkte (∑., Π) enthält.
+ - BSP
Def: Die Folge fib(n), die definiert ist durch

fib(0) := 0, fib(1) := 1

fib(n) := fib(n-1) + fib(n-2) für alle n>1

heisst Fibonacci-Folge
Wenn man die Folge ganz einfach rekursiv nach der Definitionsgleichung programmiert, wächst der Berechungsaufwand enorm nA = n Additionen:
fib(2) = 1A
fib(3) = 1A         + 1A = 2A
fib(4) = 2A + 1A + 1A = 4A
fib(5) = 4A + 2A + 1A = 7A
fib(6) = (7+4+1)A = 12A
fib(7) = 20A, fib(8) = 33A, fib(9)=54A
fib(10) = 88A, ...

Genauer betrachtet ist das auch eine Rekursionsgleichung:
Additionen(fib(0)) = Additionen(fib(1) =0
Additionen(fib(n)) = Additionen(fib(n-1)) + Additionen(fib(n-2)) + 1
Berechnet man fib(n) schlauer, indem man die Zwischenergebnisse speichert und nicht immer neu berechnet, benötigt man immer noch (n-1) Additionen für die Berechnung von fib(n), und natürlich mehr, genauer O(n) Zellen Speicherplatz.

Hat man solch eine nicht-rekursive Definitionsgleichung gefunden,
spricht man auch von einem geschlossenem Ausdruck und
von einer Lösung der Rekursionsgleichung.
Um uns dem Problem, eine Lösung der Rekursionsgleichung zu finden, verallgemeinern und formalisieren wir zunächst, um dann über Spezialfälle ggf. zum Einzelproblem zu finden.
Def: Eine Rekursionsgleichung ist eine Gleichung der Form
f(n) := g(n,f(n-1),f(n-2),...,f(n-k))
mit Funktionen f: N -> W und g:NxW^k->W für eine Wertemenge W.
+ - Damit die Rekursionsgleichung eindeutig bestimmt ist, werden k Anfangswerte benötigt.
BSP: Bei fib ist k=2, W=N₀, und
f≡fib, und
g(n,a,b) = a+b für n>1,
g(1,a,b) = 1 und g(0,a,b) = 0

+ - Lineare Rekursionsgleichungen
Lineare Rekursionsgleichungen stellen eine wichtigen Spezialfall dar, für den in einigen Fällen allgemeine Lösungen angegeben werden können.
+ - Def: Eine Rekusionsgleichung der o.a. Form, bei der g eine lineare Funktion in f ist,
heisst lineare Rekursionsgleichung k-ter Ordnung.
Es ist dann
f(n) = a₁f(n-1)+a₂f(n-2)+...+ a_kf(n-k) + b₀ für n>k-1,
mit den Anfangsbedingungen f(i) = b_i für i=1,...,k-1.
Ist b₀=0, so heisst die Rekursionsgleichung homogen
Die Unterscheidung zwischen homogener und inhomogener Form ist für den Fall nicht eindeutiger Lösungen spannend. dann kann man aus Lösungen der homogenen Form weitere Lösungen zusammensetzen, etc.
~ de.wikipedia.org > Wiki > Lineare Differenzengleichung#Rechenregeln

+ - Lineare Rekursionsgleichungen 1, Ordnung sind einfach zu lösen
+ - Homogenen Fall: Ist f(n)=af(n-1), und f(0) gegeben, dann ist
f(1)=af(0), f(2)=aaf(0), f(3)=aaaf(0), insgesamt f(n) = aⁿf(0)
Bew: Induktion.
BSP: Wenn sich Bakterienkulturen in Nährlösung jede Minute teilen,
bedeutet das für ihre Anzahl nach n Minuten:
Anzahl(n) = 2*Anzahl(n-1). Fangen wir mit einem Bakterum an, also f(0) = 1,
ist Anzahl(n) = 2ⁿ.
Nach 60 Minuten also 1.152.921.504.606.846.976 Stück.
Und wenn sie sich nur alle 5 Minuten teilen?

Inhomogener Fall: Ist f(n)=af(n-1)+b, und f(0) gegeben, dann ist
f(1)=af(0)+b, f(2)=aaf(0)+ab +b, f(3)=aaaf(0)+aab+ab+b=a³+b(a²+a+1)
insgesamt:
+ - Satz: Für die inhomogen lineare Rekursionsgleichung
f(n) = af(n-1)+b mit Anfangswert f(0) ist die geschlossene Form
für a=1: f(n) = b+nf(0), und
sonst: f(n) = aⁿf(0) + b(aⁿ-1)/(a-1)
Bew: Induktion.
BSP: Wenn eine Bank für 4% Zinsen Geld verleiht, und man immer 6%
zurückzahlt, ergibt das bei 100 EUR
Restbetrag(n) = 1,04*Restbetrag(n-1) - 6.
Mit f(0) = 100 ist Restbetrag(n) = 1,04ⁿ*100-6*(1,04ⁿ-1)/0,04.
Restbetrag=0 ergibt sich dann für
1,04ⁿ*100 = 6*(1,04ⁿ-1)/0,04.
Umformen ergibt 3=1,04ⁿ, mithin n=log(3)/log(1,04).
Das ergibt 28,011022757 Rückzahlungen, ehe die Summe abgetragen ist.

+ - Auch für homogene lineare Rekursionsgleichungen 2. Ordnung finden sich noch eine bekannte geschlossene Form.
+ - Satz: Seien f(0), f(1), a₁ und a₂ Konstanten, a₁ und a₂ nicht beide Null,
und f(n) = a₁f(n-1)+a₂f(n-2) für n>1
Seien weiter
b₁ und b₂ reelle Lösungen der Gleichung x²-a₁x-a₂=0.

Dann gilt für den Fall b₁=b₂:
f(n) = (nA+B)b₁ⁿ, mit
A=(f(1)-b1*f(0))/b₁, und B=f(0)

und für den Fall b1≠b2:
f(n)=b₁ⁿA-b₂ⁿB mit
A=(f(1)-f(0)b₂) / (b₁-b₂) und B=(f(1)-f(0)b₁) / (b₁-b₂)
Bew: Induktion nach n
+ - BSP: Für die Fibonacci-Rekursion ist der Satz anwendbar.
Wir erhalten f(0)=0, f(1)=1, a₁=a₂=1.
Lösungen für x²-x-1=0 sind 1/2 ± √(1/4+1) = (1±√5)/2, also
A=B=2/((1+√5)-(1-√5))=1/√5, und
fib(n) = ((1+√5)/2)ⁿ* 1/√5 - ((1-√5)/2)ⁿ* 1/√5
Interessant, wie sich die Wurzeln wieder aufheben ...

+ - (1+√5)/2 ist übrigens der "Goldene Schnitt"
~ de.wikipedia.org > Wiki > Goldener Schnitt

+ - Rekursive Algorithmen (merge-sort, Baumsuche, ...) teilen ja in der Regel ein Problem in zwei oder mehr gleich grosse Teile. Die Laufzeitanalyse führt dann nicht zu einer linearen Rekursionsgleichung, sondern zu einer Rekursionsgleichung der Form
Aufwand(n) = 2*Aufwand(n/2)+f(n)
Über die Größenordnung der Laufzeit dieser Klasse von Funktionen macht der unter dem Namen "Master-Theorem" bekannte Satz Aussagen.
Die rekursive Gleichung hat dabei die Form (T steht für den Aufwand, von "Time"):

T(n) = aT(n/b) + f(n).

a,b sind Konstanten. Bei jedem Rekursionsschritt wird das Problem in b Teile geteilt,
und f(n) beschreibt den Aufwand für die Kombination des Teilproblems.
Die Entwicklung der Kosten hängt dann ganz grundlegend von f(n) ab,
Das Theorem behandelt drei Fälle je nach Wachtumsverhalten von f(n),
und in anderen Fällen ist es nicht anwendbar.
~ de.wikipedia.org > Wiki > Master-Theorem
Zur Erinnerung:
O(g): f wächst höchsten so schnell wie g
Θ(g): f wächst ähnlich wie g
Ω(g): f wächst mindestsen so schnell wie g

+ - Erzeugende Funktionen
Bislang haben wir Lösungen von Rekursionsgleichungen mehr oder minder geraten, und dann unsere Vermutung bewiesen. Man kann aber auch versuchen, Lösungen von Rekursionsgleichungen konstruktiv zu finden. ein Hilfsmittel dazu sind formale Potzenzreihen und ihre erzeugende Funktionen.
Zur Schreibweise: Bei Folgen und Reihen wird statt a(n) auch oft a_n geschrieben.
Gemeint ist dasselbe:
Der Wert von a(n) hängt von n ab, a ist also eine Funktion von n.
Ich habe mich wegen der Lesbarkeit hier für die Funktionsschreibweise entschieden.
Def. Ein Ausdruck
A(x) := ∑_n≥0a(n)xⁿ
heisst formale Potenzreihe.
Die formale Potenzreihe ist die erzeugende Funktion
zur unendlichen Folge (a(n))_n≥0.
Formal deshalb, weil die Reihen nicht unbedingt überall konvergieren müssen.
Für formale Potzenzreihen in diesem Zusammenhang reicht die Konvergenz für sehr kleine Werte von x, weil wir im wesentlichen an den Koeffizienten interessiert sind, und die Werte der Reihen keine grosse Rolle spielt.
+ - Die Idee ist nun. zu einer Rekursionsgleichung eine passende erzeugende Funktion zu finden, diese in die Gleichung einzusetzen und danach aufzulösen, um dann letzlich über einen Koeffizientenvergleich eine nichtrekursive Darstellung der a(n) zu bekommen.
Das geht allgemein in 6 Schritten.
1. Aufstellen der erzeugenden Funktion A(x) := ∑_n≥0a(n)xⁿ
2. Umformen der rechten Seite, so dass Anfangswerte und Rekursionsgleichung eingesetzt werden können.
3. Unendliche Summen (meist über Index-shifts) so weiter umformen, dass sie durch A(x) ersetzt werden können.
4. Auflösen nach A(x). Man erhält A(x) = f(x) mit einer - hoffentlich einfachen - Funktion f.
5. Umschreiben von f(x) als formale Potenzreihe. Das kann durch Partialbruchzerlegung und Zurückgreifen auf bekannte Potenzreihen geschehen.
6. Der Koeffizientenvergleich liefert dann eine explizite Darstellung für a(n).

+ - Wir machen das für das sehr einfache BSP a(n) = 2a(n-1), a(0)=1.
1. Aufstellen der erzeugenden Funktion A(x) := ∑_n≥0a(n)xⁿ
2. Umformen der rechten Seite, so dass Anfangswerte
und Rekursionsgleichung eingesetzt werden können.
Hier kann man direkt a(n) ersetzen:
∑_n≥0a(n)xⁿ = a(0) + ∑_n≥12a(n-1)xⁿ
3. Unendliche Summen (meist über Index-shifts) so weiter umformen,
das sie durch A(x) ersetzt werden können:
A(x) = 1 + ∑_n≥02a(n)xⁿ⁺¹
= 1 + 2∑_n≥0a(n)xⁿ⁺¹
= 1 + 2x∑_n≥0a(n)xⁿ
= 1 + 2x∑_n≥0a(n)xⁿ
= 1 + 2xA(x)
4. Auflösen nach A(x):

A(x) = 1 + 2xA(x)
A(x)-2xA(x) = 1
A(x) (1-2x) = 1
A(x) = 1 / (1-2x)
5. Umschreiben von f(x) als formale Potenzreihe.
Bei den bekannten Funktionen mit Potenzreihenentwicklung findet man
1 / (1-ax) = ∑_n≥0aⁿxⁿ für ein festes a, hier a=2:
A(x) = 1 / (1-2x) = ∑_n≥02ⁿxⁿ
6. Koeffizientenvergleich liefert dann eine explizite Darstellung für a(n):
A(x) = ∑_n≥0a(n)xⁿ = ∑_n≥02ⁿxⁿ
also a(n) = 2ⁿ.

+ - Bekannte Potenzreihen findet man viele

~ Potenzreihen bei wikipedia

+ - Um "passende" Potenzreihen zu finden, kann man zunächst von bekannten Potenzreihen ausgehen, diese verknüpfen und umformen.
Addition und Subtraktion erfolgen wie gewohnt Komponentenweise.
A(x)*B(x) = ∑_n≥0a(n)xⁿ * ∑_n≥0b(n)xⁿ = ∑_n≥0c(n)xⁿ , mit
c(n) = ∑_K=0,...,na(k)b(n-k)
Die Folge (c(n))_n≥0 nennt man auch
Faltung oder Konvolution der Folgen (a(n))_n≥0 und (b(n))_n≥0.
Zu einer Potenzreihe A(x) ist die inverse Potenzreihe B(x) die Reihe, für die
A(x)*B(X) = 1+0x +0x²+... ergibt, also In der o.g. Produktdarstellung c(0)=1 ist, und c(k)=0 für alle k>1.
Die Inverse existiert genau dann, wenn a(0)≠0.
Eine Potenzreihe A(X) = ∑_n≥0a(n)xⁿ kann man auch
formal nach x gliedweise ableiten, er ergibt sich
A'(X) = ∑_n≥1na(n)x^n-1 = ∑_n≥0(n+1)a(n+1)xⁿ
Die Ableitung ist also die zugehörige Potenzreihe zur
Folge a(1), 2a(2), 3a(3), ... , ka(k), ....
Interessant ist auch eine Verschiebung um m Stellen (nach rechts),
was bei geeigneter Benennung nur der Multiplikation mit x^m entspricht
a(0)x^m+a(1)x^m+1+a(2)x^m+2+... = x^m∑_n≥0a(n)xⁿ

+ - Viele der bekannten erzeugenden Funkionen entstammen der Funktion der geometrischen Reihe. Deren erzeugende Funktion kann man finden, indem man, ausgehend von der Potzenzreihe, die inverse Potenzreihe sucht:
A(x) := ∑_n≥0xⁿ.
Suche B(x) := ∑_n≥0b(n)xⁿ mit A(x)B(x) = 1.
Das liefert b(0)=1, b(1)=-1, und b(k)=0 für k>1, also B(x) = 1-x.
Damit ergibt sich für A(x) = 1/B(x) = 1 / (1-x)
die bekannte Funktion der geometrischen Reihe.
Wählt man hier x=ay, so findet man die Funktion für
∑_n≥0(ay)ⁿ = ∑_n≥0aⁿyⁿ = 1 / (1-ay)
Auch die (formale) Ableitung bringt weitere erzeugende Funktionen:
A'(x) := ∑_n≥1nx^n-1 = ∑_n≥0(n+1)xⁿ
= (1 / (1-x))' = 1 / (1-x)²

+ - BSP a(n) = 3a(n-1) + n, a(0) = 1
Schritt 1-3 liefert:
A(x) = 1 + 3x∑_n≥0a(n)xⁿ + ∑_n≥0nxⁿ
= 1 + 3xA(x) + 1/(1-x)²
Auflösen:
A(x) = 1 + 3x∑_n≥0a(n)xⁿ + ∑_n≥0nxⁿ
= 1 + 3xA(x) + 1/(1-x)²
liefert
A(x) = (x²-x+1) / ( (1-3x)(1-x)² )
also ein Bruch von zwei Polynamen, der Nenner vom Grad 3.
Direkt Potenzreihen dafür zu finden ist schwierig. Wir machen zunächst eine Partialbruchzerlegung mit folgendem Ansatz:
A(x) = (x²-x+1) / ( (1-3x)(1-x)² )
= A / (1-3x) + B / (1-x) + C / (1-x)²
Auflösen, einsetzen etc. liefert daraus die drei Gleichungen
A+B+C = 1 (aus x=0)
C = - 1/2 (aus *(1-x)², x=1)
A = 7/4 (aus *(1-3x), x=1/3)
B = -1/4 (aus A+B+C=1)
Also A(x) = (7/4) / (1-3x) - (1/4) / (1-x) - (1/2) / (1-x)²
mit den entsprechenden bekannten Potenzreihen
A(X) = (7/4) ∑_n≥03ⁿxⁿ - (1/4) ∑_n≥0xⁿ - (1/2) ∑_n≥0(n+1)xⁿ
= ∑_n≥0 ( (7/4)3ⁿ - 1/4 - (n+1)/2 ) xⁿ
= ∑_n≥0 ( (7/4)3ⁿ - n/2 - 3/4 ) xⁿ
Koeffizientenvergleich: a(n) = (7/4)3ⁿ - n/2 - 3/4

+ - BSP Fibonacci-Folge
Das ist nun etwas aufwändiger.
fib(n) = fib(n-1)+fib(n-2), fib(0)=0, fib(1)=1
A(x) = ∑_n≥0fib(n)xⁿ
= 0 + x + ∑_n≥2(fib(n-1)+fib(n-2))xⁿ
= 0 + x + x∑_n≥2fib(n-1)x^n-1 + x²∑_n≥2fib(n-2)x^n-2
= 0 + x + x∑_n≥1fib(n)xⁿ + x²∑_n≥0fib(n)xⁿ
= 0 + x + x(A(x)-fib(0)) + x²A(x)
= 0 + x + xA(x) + x²A(x)
Auflösen: A(x) = x / (-x²-x+1)
Zerlegen in Partialbruch mit Ansatz:
A(x) = x / (-x²-x+1) = A/(1-ax) + B/(1-bx) liefert
A+B=0 (aus x=0)
(1-ax)(1-bx) = 1-x-x² (Hauptnenner, umformen, Koeffizientenvergleich)
Ab+Ba = -1 (..., Koeffizientenvergleich)
Lösen ergibt: A=1/√5, B=-1/√5, a=(1+√5)/2, b=(1-√5)/2
Wir erhalten A(x) = (1/√5)(1/(1-ax)) - (1/√5)/(1/(1-bx))
= 1/√5 ∑_n≥0aⁿxⁿ - 1/√5 ∑_n≥0bⁿxⁿ
= ∑_n≥0(1/√5)(aⁿ-bⁿ)xⁿ
Koeffizientenvergleich liefert
fib(n) = (1/√5)(aⁿ-bⁿ) = (1/√5)((1+√5)/2)ⁿ-(1/√5)((1-√5)/2)ⁿ

Den Spezialfall fib hatten wir ja schon bewiesen. Hier sieht man auch. wie man auf die allgemeine Lösung für eine lineare Rekursionsgleichung 2. Ordnung kommt - per Erzeugende Funktion und Ansatz über die Partialbruchzerlegung. Dieser Ansatz funktioniert übrigens auch bei wechselseitiger Rekursion ...

+ - Algebren
+ - Algebra: Etwas, worin man rechnen kann
+ - Wir haben schon viele Algebren benutzt,. ohne uns weiter Gedanken darüber zu machen.
Der Begriff bezieht sich auf eine grundlegende Formalisierung, die es erst erlaubt, formale Strukturen zu verwenden und nachzuweisen.
~ de.wikipedia.org > Wiki > Algebra#Wortgeschichte

+ - Def: Eine (universelle) Algebra ist ein Tupel (S,f_1,...,f_n) aus einer
nicht leeren Trägermenge S und n Operationen f_1, ... f_n, n>0.
Eine Operation f ist dabei ein Funktion f: S^m → S.
und m≥0 die Stelligkeit der Operation f.
Wichtig ist die Abgeschlossenheit der Operationen:
Der Wertebereich ist wieder S
Nullstellige Operationen sind Konstanten.
BSP: (N, max) - Die natürlichen Zahlen mit der zweistelligen Operation
max(a,b) := ( a falls a>b, b sonst)
(R,+,*) - die reellen Zahlen mit den binären Operationen
+ und * ist eine Algebra, sogar eine recht spezielle Algebra: ein Körper
Mit einer Grundmenge U ist (Pot(U),∩,∪,c) eine Algebra auf der
Potenzmenge von U und den Operationen Vereinigung, Schnitt
und der unären Operation Komplement
Die Menge B = {t,f} mit dem logischen und- und oder-Operationen
und der Verneinung bildet die boolesche Algebra (B,∧,∨,¬).
Die Wörter über einem endlichen Alphabet Σ bilden
zusammen mit der Konkatenation • , also dem Aneinanderfügen von Wörtern,
eine Algebra (Σ^*,•)
+ - Eine Menge von Begriffen zusammen mit mindestens den Operationen Projektion, Selektion, Kreuzprodukt , Vereinigung, Differenz und Umbenennung bildet eine relationale Algebra, die Grundlage der relationalen Datenbanken.
~ de.wikipedia.org > Wiki > Relationale Algebra

+ - Einstellige Operationen nennt man auch unäre, zweistellige binäre und dreistellige ternäre Operationen. Zweistellige Operationen werden oft "infix", also wie bei zweistelligen Relationen zsichen die beiden Operanden notiert.
Beispiele:

x → x² unär

(x,y) → ggT(x,y) binär

(x,y,z) → if x then y else z   ternär

+ - Def. Sei (S,f_1,...f_k) eine Algebra, und S' ⊆ S nicht leer.
sind die Operationen f_1, ... , f_k abgeschlossen auf S', so heisst
S' Unteralgebra von (S,f_1,...,f_k)
BSP: (N₀,+) ist eine Unteralgebra von (Z,+)
({0,1},*) ist eine Unteralgebra von (Z,*)
({0,1},+) ist keine Unteralgebra von (Z,+)

+ - Bei binären Operationen ist eine interessante Frage, ob gewisse Elemente
sich neutral verhalten, also quasi keine Auswirkungen haben.
+ - Def: Gilt für ein Element e in einer Algebra (S,◊) mit einer binären Operation ◊
e ◊ x = x für alle x∈S, dann heisst e linksneutrales Element.
BSP:
1 auf (N,max),
∅ auf (Pot(U),∪)

Def: Gilt für ein Element e in einer Algebra (S,◊) mit einer binären Operation ◊
x ◊ e = x für alle x∈S, dann heisst e rechtsneutrales Element.
+ - Satz: Hat in eine Algebra (S, ◊) die Operation ◊
ein rechtsneutrales Element r und ein linksneutrales Element l,
so gilt l=r
Bew: l = l ◊ r = r

+ - Def: In Fall des Satzes spricht man auch von dem neutralen Element.
BSP: Für (Pot(U),∩) ist U ein neutrales Element.

Man spricht in Analogie zur vertrauten Multiplikation
statt vom neutralen Element auch von
Einselement, und schreibt es folgerichtig oft 1 statt e.
+ - Lemma: In einer Algebra (S,◊) hat ◊ höchstens ein neutrales Element
Bew: Gäbe es zwei, könnte man eines als rechts. eines als linksneutrales ansehen .... - q.e.d.

+ - Def. Sei (S,◊) eine Algebra mit einen neutralen Element e zu ◊
Gibt es zu einem Element a aus S
1. ein b aus S mit b ◊ a = e, so nennt man b Linksinverses zu a
2. ein b aus S mit a ◊ b = e, so nennt man b Rechtsinverses zu a.
Gilt sogar a◊b = b◊a = e, heisst b einfach Inverses zu a.
Nicht jedes Element muss ein Inverses haben.
BSP: (N₀,+) hat das Neutrale Element 0,
und nur 0 hat ein Inverses, nämlich wieder 0.

+ - Def: Ein Element 0 mit der Eigenschaft
0 ◊ a = 0 für alle a aus S heisst linkes Nullelement
(rechtes Nullelement und Nullelement entsprechend)
BSP: Für (Pot(U),∩) ist ∅ ein Nullelement.

+ - Morphismen
Morph kommt aus dem Griechischen und bedeutet Gestalt oder Form. Unter Morphismen versteht man in der Mathematik dann eine Abbildung, die gewisse Strukturen erhält. Dafür müssen die zugrunde gelegten Algebren natürlich einigermassen kompatibel sein.
Def: Die Signatur eine Algebra (S,f_1,...,f_n) ist die Liste
der Stelligkeiten der Operationen,
also für f_1: S^m_1→S, f_2: S^m_2→S, ... , f_n: S^m_n→S
das Tupel (m_1, m_2, ..., m_n)
Def: Für zwei Algebren (S,f_1,...,f_k) und (M,g_1,...,g_k) mit gleicher Signatur
heisst eine Abbildung h: S→M (Algebra-)Homomorphismus, wenn
folgende Abbildung für alle i kommutiert, d.h. für i=1,...k gilt
h ⋅ f_i = g_i ⋅ h :
+ -
BSP Bezeichnet |w| die Anzahl der Zeichen eines Wortes,
so ist für ein Alphabet Σ
h: Σ^* → N₀, h(w):=|w|
ein Homomorphismus von (Σ^*,•) nach (N₀,+)
Die Signatur der Algebren ist jeweils (2).
Die Länge eines zusammengesetzten Wortes ist die Summe der Teilwörter.
Solche kommutierenden Abbildungen spielen (u.a. in der mathematischen Algebra) eine wichtige Rolle, Wir hatten das Prinzip der Einbettung ja auch schon so ähnlich aaO benutzt

+ - Satz: Mit den Voraussetzungen der vorigen Definition ist
(h(S),g_1,...,g_k) eine Unteralgebra von (M,g_1,...,g_k)
Bew: Das folgt sofort aus der Abschliessungs-Eigenschaft von h

+ - Def. Ist mit den Benennungen der letzen Definition h bijektiv, so nennt man
h einen Algebra-Isomorphismus und die beiden Algebren isomorph.
(vgl. FFT-Einbettung.)

BSP: Die boolesche Algebra ({t,f},∧,∨,¬) ist isomorph zur Algebra
({1,0},min,max,1-) mit der Operation 1-(x) = 1-x.
h(t)=1, h(f)=0.
BSP: Die boolesche Algebra ({t,f},∧,∨,¬) ist auch isomorph zur Algebra
({U,∅},∩,∪,c)   (c = Komplement) für eine Universums-Menge U,
h(t)=U, h(f)=∅.

+ - Monoide und Gruppen
Speziellere Strukturen bekommt man, indem man Axiome - Anforderungen an die Operationen - hinzunimmt.
Def: Eine binäre Verknüpfung ◊ in der Algebra (S,◊) heisst assoziativ,
wenn für alle a,b,c aus S gilt ( a ◊ b) ◊ c = a ◊ (b ◊ c)
+ - Satz: Gibt es in einer Algebra (S,◊) mit einer assoziativen Operation ◊
zu einem Element a ein Linksinverses l und ein Rechtsinverses r,
so gilt l=r.
Insbesondere ist das Inverse, sofern es existiert, dann eindeutig bestimmt.
Bew: l = l ◊ e = l ◊ (a ◊ r) = (l ◊ a) ◊ r = e ◊ r = r

Def: Eine Algebra (S,◊) mit einem assoziativen binären
Operator ◊ heisst Halbgruppe.
Def: Eine Halbgruppe (S,◊) mit einem neutralen Element e
heisst Monoid.
Def: Ein Monoid (S,◊), für den für jedes a aus S ein Inverses existiert,
heisst Gruppe.
+ - Eine weitere Operation und ein zusätzliche Forderungen führen zu den Begriffen
Ring und Körper.
Def. (Ring): Ein Ring ist eine Algebra mit zwei binären Verknüfungen (R,+,*), wobei
(R,+) eine abelschen Gruppe mit neutralem Element 0 ist,
* assoziativ ist, und
für alle a,b,c, aus R gilt: a*(b+c) = a*b + a*c und (a+b)*c = a*c + b*c
Def. (Körper): Ein nicht leerer, kommutativer Ring (R,+,*) mit
neutralem Element bzg. * (Ring mit 1) ist ein Körper,
wenn es zu jedem a≠0 ein Inverses bzgl. * gibt.

+ - Def. Eine Halbgruppe (ein Monoid, eine Gruppe) (S,◊) heisst abelsch,
wenn für alle a,b aus S gilt a ◊ b = b ◊ a
~ de.wikipedia.org > Wiki > Niels Henrik Abel

+ - Gruppen.
Wir schreiben in diesem Abschnitt fast immer
'*' für die Operation, 1 für das neutrale Element, a^-1 für das Inverse von a,
und identifizieren die Menge G mit der Gruppe (G,*)
Für Gruppen lassen sich leicht die üblichen Rechenregeln (z.B. Kürzungsregeln) herleiten, insbesondere ist die binäre Operation der Algebra bei Gruppen bijektiv
Man kann natürlich ein Elemen aus der Gruppe auch mit sich selbst verknüpfen. Das führt zu
+ - Def (Potenz): Sei G eine Gruppe, und a aus G. Für eine ganze Zahl n≥0
definieren wir induktiv die n-te Potenz von a mit
1) a⁰ = 1
2) a¹ = a
3) aⁿ = a*a^n-1 für n>1
Die üblichen Potenz-Rechenregeln folgen direkt aus der Definition.

+ - Def (Ordnung): Sei g ein Gruppe und a aus G.
Es ist die Ordnung von a
ord(a) := min{n∈N: aⁿ = 1}, falls so ein n existiert.
sonst vereinbart man ord(a) := ∞.
BSP: G=({0,1,2,3,4,5}, +(mod 6)):
ord(0) = 1, ord(1) = 6, ord(2) = 3, ord(3)=2, ord(4)= 3, ord(5)=6

+ - Satz: In einer endlichen Gruppe hat jedes Element eine endliche Ordnung
Bew: G ist abgeschlossen, also sind die |G|+1 Elemente
a⁰, a¹, a², ... a^|G| alle in G.
Mindesten zwei davon müssen also gleich sein, seien das
oBdA die Potenzen k und l (k-l ist natürlich nicht 0).
Es ist also a^k=a^l, folgt
a^k-l=a^k*a^-l=a^l*a^-l=a^l-l=a⁰=1,
also a^k-l=1, also ord(a)≤(k-l)

+ - Satz: Sei G eine endliche Gruppe, und a aus G. Für ein k>0 gilt
a^k=1 genau dann. wenn ord(a)|k
Bew: einfach nachrechnen

+ - Def. Sei (G,*) eine Gruppe, und H⊆G.
Ist auch (H.*) eine Gruppe, nennt man H Untergruppe von G
BSP: Für eine ganze Zahl n ist
nZ := {nz | z∈Z}
(nZ,+) ist eine Untergruppe von (Z,+)

+ - Satz: S(a) := {1,a,a²,...,a^ord(a)-1} ist die kleinste Untergruppe, die a enthält.
Bew: S(a) ist abgeschlossen, und in einer Untergruppe H müssen
mit a auch alle Potenzen von a sein.
Jedes Element a^k von S(a) hat ein Inverses a^ord(a)-k

Gruppe und Untergruppe müssen das gleiche neutrale Element haben.
+ - Satz: Sind H und I Untergruppen einer Gruppe G, so ist auch H∩I eine Untergruppe.
Bew (knapp): z.zg. ist im wesentlichen die Abgeschlossenheit, Das ist aber klar, da h*i wegen der Abgeschlossenheit von H und I wieder in H und in I liegen muss.
Bem: Die Vereinigung von Untergruppe ist i.A. keine Gruppe:
2Z ∪ 3Z ist bzgl '+' nicht mal abgeschlossen.

Def: Sei a aus G, und H eine Untergruppe. Dann heisst
a*H :={ a*h | h∈H } eine linke Nebenklasse von H , und entsprechend
H*a :={ h*a | h∈H } eine rechte Nebenklasse von H
Bem: Zwei Nebenklassen sind endweder identisch oder diskunkt
+ - Bem: Die Menge aller Nebenklassen zu einer Untergruppe H bildet eine Partition von G
BSP: Für die Gruppe (Z,+) ist (6Z,+) eine Untergruppe,
mit den Nebenklassen
0+6Z, 1+6Z, 2+6Z, 3+6Z, 4+6Z, 5+6Z
Im Fall der ganzen Zahlen bezeichnet man die Nebenklassen
der o.a. Form auch als Restklassen. Es ist ja für i=0,...,5
i+6Z = {z∈Z| z = i mod 6 }

Def: Die Anzahl der verschiedenen Nebenklassen von H in G wird mit
Index von H bzw. ind(H) bezeichnet..
Satz (Lagrange) Für endliche Gruppen G und Untergruppen H gilt:
|G| = |H|*ind((H)
Insbesondere ist also die Mächtigkeit der Untergruppe ein Teiler der Mächtigkeit der Gruppe.
+ - Korollar: Sei a aus G und G eine endliche Gruppe.
Dann teilt ord(a) |G|
Bew: S(a) ist eine Untergruppe der Kardinaliät ord(a).

+ - Als Anregung:
~ de.wikipedia.org > Wiki > Lineare Algebra

Endliche Körper

+ - Spezialisierte Körper
Man kann z.B. zu Ringen nur einzelne Elemente ergänzen (adjungieren), und dann zum Körper vervollständigen, z.B. √5
~ de.wikipedia.org > Wiki > Goldener Schnitt#Der Goldene Schnitt als irrationalste und nobelste aller Zahlen

dez.	0	1	2	3	4	5	6	7
std.	0000	0001	0010	0011	0100	0101	0110	0111
Gray	0000	0001	0011	0010	0110	0111	0101	0100

dez.	8	9	10	11	12	13	14	15
std.	1000	1001	1010	1011	1100	1101	1110	1111
Gray	1100	1101	1111	1110	1010	1011	1001	1000

A	B	A → B	¬A ∨ B
w	w	w	w
w	f	f	f
f	w	w	w
f	f	w	w

1
0	1
0	1	1
0	2	3	1
0	6	11	6	1
0	24	50	35	10	1
0	120	...