Zusammenfassung Mathematik für Informatiker I PDF

Preview

Summary

Warning: TT: undefined function: 32Zusammenfassung Mathematik für Informatiker IModulo mit dem Taschenrechner Division ganzzahligen Rest abziehen mit Nenner multiplizieren euklidischer AlgorithmusggT(s, t) - q = s div t - r = s mod tsolange t ungleich 0: - r und q berechnen - sneu = talt - tneu = rn...

Description

Zusammenfassung Mathematik für Informatiker I Modulo mit dem Taschenrechner • • •

Division ganzzahligen Rest abziehen mit Nenner multiplizieren

euklidischer Algorithmus ggT(s, t) • q = s div t • r = s mod t solange t ungleich 0: • r und q berechnen • sneu = talt • tneu = rneu Beispiel (nicht-tabellarisch): 798 = 294 * 2 + 210 294 = 210 * 1 + 84 210 = 84 * 2 + 42 ß 42 ist der ggT 84 = 42 * 2 Beispiel (tabellarisch): s t 798 294 294 210 210 84 84 42 0 40

q 2 1 2 2

r 210 84 42 0

erweiterter euklidischer Algorithmus • • • •

q = s div t r = s mod t x, y, u, v vordefiniert durch 1, 0, 0, 1 x und y ergeben dabei die Vielfachsummendarstellung

Update-Formeln:

• • •

uneu = xalt – qneu*ualt xneu = ualt sneu = talt

Beispiel: s 798 294 210 84 40

t 294 210 84 42 0

• • • q 2 1 2 2

42 = ggT(798, 294) = 3*798 – 8*294

r 210 84 42 0

vneu = yalt – qneu*valt yneu = valt tneu = rneu

x 1 0 1 -1 3

y 0 1 -2 3 -8

u 0 1 -1 3 -7

v 1 -2 3 -8 19

Nachweis Restklassenring „Beschreiben Sie, wie man mit dem erweiterten Euklidischen Algorithmus nachweisen kann, dass a mod n eine Einheit im Restklassenring ℤ" ist und wie man ggf. das Inverse von a mod n berechnen kann.“ • a mod n ist Einheit modulo n ggT(a, n) = 1 • der liefert der erw. Euklidische Algorithmus den ggT von a und n, sowie die Vielfachsummendarstellung davon, d.h. ggT(a, n) = a*a + b*n für a , b$ ∈ ℤ

Induktion •

•

•

Induktionsanfang (IA): o ist bei Summenzeichen der untere Wert (meist 0 oder 1) o wird in der Form n = 1 angegeben o dann berechnet man unabhängig voneinander die linke und rechte Seite mit dem n o dabei muss links und rechts das gleiche herauskommen Induktionsschritt (IS): o man iteriert n zu n -> n+1 o dann setzt man n+1 in die Gleichung ein o im Fall vom Summenzeichen, werden die n in der Klammer nicht durch n+1 ersetzt, sondern erst dahinter in einem weiteren Summanden Induktionsvorraussetzung (IV): o wird über dem Gleichheitszeichen in der nächsten Zeile geschrieben, um die Gültigkeit zu signalisieren (nur die rechte Seite wird ausgerechnet) o nun wird solange umgeformt, bis alle n in der Form (n+1) auftauchen

IV: Gleichung aufstellen, linke Seite übernehmen, rechte Seite aus Angabe herleiten Behauptung: alle n durch (n+1) ersetzen Beweis: Ausmultiplizieren, Ausdruck aus Voraussetzung finden und ersetzen à Gültigkeit durch (n+1) zeigen

Widerspruchsbeweis zu &𝑝 ist irrational )

Annahme, &𝑝 sei rational: Sei & 𝑝 = $ * für 𝑎, 𝑏 ∈ ℕ und a, b teilerfremd. ).

Quadrieren liefert 𝑝 = $ *. $ ⇔ 𝑝 ∗ 𝑏1 = 𝑎 1 , d.h. 𝑝|𝑎 1 Da p Primzahl, folgt 𝑝|𝑎, d.h. 𝑎 = 𝑝 ∗ 𝑘 für 𝑘 ∈ ℕ ⇒ 𝑝 ∗ 𝑏1 = $ 𝑝 1 ∗ $ 𝑘1 ⇒ $ 𝑏 1 = 𝑝 ∗$ 𝑘1, d.h. 𝑝|𝑏1 bzw. 𝑝|𝑏 Also ist p gemeinsamer Teiler von a und b, ein Widerspruch zu teilerfremd.

Abbildungsbegriff • • •

injektiv: 𝑓( 𝑎) = 𝑓 (𝑏) ⇒ 𝑎 = 𝑏 o zu jedem y-Wert gibt es höchstens einen x-Wert (Funktion) surjektiv: 𝑓 89 (𝑦) ist nicht leer für jedes𝑦 ∈ 𝑁 o zu jedem y-Wert gibt es mindestens einen x-Wert bijkeitv: 𝑓 ist sowohl injektiv, als auch surjektiv

Gauß-Algorithmus Treppen-Normalform: • unten links muss sich eine „Treppe“ aus ausschließlich Nullen befinden • dies erreicht man durch Umformung Umformungen: • Zeilentausch: Man kann Zeilen beliebig tauschen. Bietet sich an, wenn es eine Zeile mit einer 1 an der ersten Stelle gibt, diese aber (noch) nicht die erste ist.

Multiplikation/Subtraktion mit anderer Zeile: Man nimmt beispielsweise Zeile II und schaut, wie man durch Multiplikation/Subtraktion mit der ersten Zeile Nullen an die erste(n) Stelle(n) bekommt. Beispielsweise: II-5*I Unter der Diagonalen dürfen nur Nullen stehen bleiben. •

Der Rang Γ gibt an, in wie vielen Spalten auf eine einzelne 1 und sonst nur Nullen normiert sind (Bsp.: Γ = 3). In χ führt man dann die charakteristischen Spalten auf. Bsp.: χ = {1, 3, 5} Als χ c werden dann die nicht-charakteristischen Spalten aufgeführt. Bsp: χc = {2, 4} Die Standardlösung ergibt sich durch untereinander schreiben der charakteristischen und nichtcharakteristischen Spalten. • Für charakteristische Spalten gibt man die Zahl auf der rechten Seite an. • Für nicht-charakteristische Spalten gibt man eine Null an. Basis des homogenen Lösungsraums: • Der homogene Lösungsraum betitelt die nicht-charakteristischen Spalten. • Wird als ℎ" für jedes n = einer nicht-charakteristischen Spalte angegeben.

Monoide, Gruppen und Körper • •

es kann ein Neutralelement geben wenn dann gibt es zu jedem Element ein Inverses

• •

Nachweis NE: x=0, y=e und ausrechnen; das Ergebnis noch allgemein durch Einsetzen beweisen Nachweis IE: Gleichung gleich dem NE setzen und nach y auflösen

Halbgruppe Monoid Gruppe abelsche Gruppe Ring Körper

es gibt ein e mit x*e = x es gibt zu jedem x ein y mit x*y = e

Abg. + AG Abg. + AG + NE Abg. + AG + NE + IE Abg. + AG + NE + IE + KG (R, + , N) ist komm. Gruppe + (R, ·, E) ist Halbgruppe + DG (K, +, 0) ist abel. Gruppe + (K\{0}, ·, 1) ist abel. Gruppe + DG

• •

(N, +, ·, 0, 1) ist kein Ring. Kommutative Ringe sind: (Z, +, ·, 0, 1), (Q, +, ·, 0, 1) und (R, +, ·, 0, 1) (Z, +, ·, 0, 1) ist kein Körper, aber (Q, +, ·, 0, 1) und (R, +, ·, 0, 1) sind Körper.

•

Restklasse von a modulo m ist die Menge aller Zahlen, die bei Division durch m denselben Rest lassen, wie a

Lösen quadratischer Gleichungen • •

Diskriminante berechnen: ∆ := b2 − 4ac Fälle: o ist ∆ kein Quadrat im Körper, so gibt es keine Lösung o ist ∆ = 0, so gibt es eine Lösung o ansonsten gibt es zwei Lösungen

•

restliche Berechnung, wie bei der Mitternachtsformel:

Kongruenz modulo n a ≡n b :⇔ n teilt a – b Kurzschreibweise der Kongruenz: [a]n

8*± √∆ 1)

Matrizen •

•

Darstellungsmatrix bestimmen: o erste Spalte x1, zweite Spalte x2, dritte Spalte x3 o Beispiele für Modulo angeben: gilt mod 3 à 3=0, 4=1 o dann alle x modulo nehmen: bei modulo 3 wird 3x1 zu 0 o die Darstellungsmatrix D ergibt sich aus den Resten aller x Basis des Kerns: o Gauß-Algorithmus auf Darstellungsmatrix anwenden o „leere“ (also nur Nullen) Zeilen ergeben die Basis (z.B. h2) o das Bild lässt sich aus der ersten Spalte der Darstellungsmatrix ablesen

•

Determinante einer Matrix bestimmen: o i2 = -1 o muss eine quadratische Matrix sein o 2x2-Matrix: ad – bc

•

kanonische Basis/Basen: jedes a zu einer 1, alles andere zu einer 0

•

Basis des Eigenraums: o ist der Eigenwert beispielsweise 3, so lautet die Formel: A – 3*E o diagonal den angegebenen Eigenwert abziehen o mit Gauß-Verfahren normieren

Horner-Schema •

Teiler angeben: Nullstellenform aufstellen und ausmultiplizieren: z.B. (x-2)(x+1) = x2-x-2

•

um die Nullstellen zu bestimmen, das Ergebnis in die Mitternachtsformel setzen und die Ergebnisse in geschweifter Klammer angeben...