1
Vorkurs Mathematik für Informatiker
-- 1 Potenzen und Polynome --
Thomas Huckle
Stefan Zimmer (Stuttgart)
4.10.2018
2
3
Vorwort
• Es sollen Arbeitstechniken vermittelt werden für das
Informatikstudium
• Der wesentliche Teil ist das Bearbeiten der Übungsaufgaben
• Aufgaben, die man nicht lösen konnte, kann man vergessen,
daher gibt es keine „Musterlösungen“: „learning by doing“
• Stoffauswahl:
- Wiederholung von Schulstoff
- Informatik-relevante Mathematik
- insgesamt relativ willkürlich, aber interessant!
Vorlesung, Zentralübung, Tutorü., Seminar, Prakt., Lab …
4
Vorgehensweise
Mathematik: Definition von Objekten und Operationen.
Frage nach Eigenschaften der definierten Strukturen!
Vorlesung verstehen? Mitschreiben! Nacharbeiten!
Typischer Lösungsweg für Übungsaufgaben:
Aus aktuellem Teil des Skripts/der Vorlesung die Definitionen
anschauen, umformulieren, zusammenfügen Lösung
Jeder Zeit Fragen stellen! Anwesenheit!
Verschiedene Schwierigkeitsstufen.
Serlo: https://de.serlo.org/mathe/universitaet/tu-muenchen/vorkurs-mathematik-informatiker/44328
5
„Potenzen“ bzgl. Addition
Einführung der Zahloperationen, basierend auf 0 und 1:
„Potenzen“ bezgl. „+“:
n 11...11
n-mal
Mächtigkeit einer Menge mit
n Elementen (Äpfeln)
Addition: n+1 = (1+1+..+1+1) + 1 als Nachfolger von n
Multiplikation: nnnnmn ...
m-mal
als wiederholte Addition in Paketen oder
Mächtigkeit von m Mengen der Mächtigkeit n
6
Potenzen bzgl. Multiplikation
Potenz als wiederholte Multiplikation:
nxxxxx :
n-mal
als abkürzende Definition/Schreibweise „:=„
mnnm xxxxxxxxxxxxxxx
m-mal n-mal m+n-mal
mmm xyxyxyyyxxyx
m-mal m-mal m-mal
mnmmnm xxxxxxxx
n-mal m-mal m-mal
n-mal
7
Rekursive Definition
0
0:1
nfürxx
nfürxx
n
n
Präzise mathematische Definition:
Als Computer-Programm:
function Potenz( x: Real; n: Integer): Real;
begin
if n=1 then Potenz := x
else Potenz := x ∙ Potenz(x, n-1)
end;
Rekursives Programm (Ausführung von oben her)
8
Loop programm
Induktives Programm (Ausführung von unten her)
function Potenz ( x: Real; n: Integer ) : Real ;
var
p: Real ;
i : Integer ;
begin
p := 1.0 ;
for i := 1 to n do p := p ∙ x ;
Potenz := p ;
end ;
9
Brüche als Exponent
Definition:
Für eine positive Zahl x ϵ IR und n ϵ IN ist x1/n diejenige
positive Zahl y, für die gilt yn = x .
Für n=2 bekommen wir die üblichen Wurzeln √¯¯
Entsprechend ist die n-te Wurzel definiert durch
nnn xxx1
1
:
Damit diese Definition vernünftig ist, sollte es nur eine
solche Zahl y geben!
xyxy nn 1
10
Rechenregeln
Die Definition von x1/n wurde genau so gewählt, dass die
alte Regel (xm)n = xm∙n weiter gilt:
?1 nnx
xxxxn
nnn
1
1
1
Somit hebt der Exponent 1/n die Wirkung des Exponenten n
auf, bzw. Exponent n hebt 1/n auf.
Daher ist xn die Umkehrfunktion von y1/n (und umgekehrt).
qp
p
qp
qqp
xxxx11
1
:
11
Ziel: Erweiterung des
Potenzierens auf reelle ZahlenBrüche (positive rationale Zahlen), schon geschafft.
Erweiterung jeweils so, dass die alten Regeln weiter gelten.
Negative Exponenten:
nmnm xxx für m = 0:nnn xxxx 00
Daher muss x0 = 1 sein.
0xxxx nnnn nmnm xxx für m = − n:
Daher muss sein wegen n
n
xx
1:
1 nn xx
Später soll natürlich auch xy für definiert sein.,0,, xRyx
12
Polynome - Definitionen
Ein Term der Form xn heißt Monom (in x);
x є ǀR: Unbekannte; n є ǀN: Potenz
Die ai , i=0,1,…,n, heißen Koeffizienten des Polynoms.
Entsprechend heißt ein Term
ein Polynom (in x). Index i. Summenzeichen.
0
1
1
0
axaxaxa n
n
n
i
i
i
Das Summenzeichen Σ dient der einfacheren Notation
nn
n
i
i aaaaaa
1210
0
13
Polynom als Code
program Polynom;
const
n = 3;
var
a: array [0 . . n] of Real = (4.0 , 0.0 , 7.0 , 15.0 );
x: Real = 2.0;
sum: Real;
i: Integer;
begin
sum := 0.0;
for i := 0 to n do
sum := sum + a[i] * (x ** i);
WriteLn (sum);
end;
14
Diskussion
Das Programm wertet das Polynom aus.
Man gibt also eine Stelle x ein und erhält dafür
den Wert des Polynoms sum an dieser Stelle x.
Das Programm ist eigentlich ein schwerer Kunstfehler.
Aufwändig und teuer! Es geht wesentlich geschickter!
Beispiele für Polynome:
1 (nach 0 das einfachste)
7 x + 3
15 x3 + 7 x2 + 4 ( ein „innerer“ Koeffizient ist 0)
15
Grad eines Polynoms
Der Grad eines Polynoms ist „das größte i“ mit ai ≠ 0
Notation: nxn :)deg(
Allgemein: nxan
i
i
i
0
deg (= n, falls an ≠ 0).
Aufgabe: deg(1)=?, deg(7x+3)=?, deg(15x3+7x2+4)=?
deg(1)=0; deg(7x+3)=1; deg(15x3+7x2+4)=3;
deg(0)=?
16
deg(0)?
Rechenregeln für deg: Sei pn Polynom vom Grad n.
deg(pn ∙ pm) = n + m = deg(pn) + deg(pm)
deg(pn+pm) <= max{n,m} = max{deg(pn),deg(pm)}
Speziell für pn=0 soll daher auch gelten:
deg(0∙pm) = deg(0) + m = deg(0)
deg(0+pm) = max{deg(0),m} = m
→ deg(0) = ̶ ∞
Manchmal auch deg(0) = -1 in der Computeralgebra.
Also deg(0)<m, so dass deg(0)+1=deg(0)
17
?312 22 xxxx
Addieren und Multiplizieren
von PolynomenFunktioniert mit den üblichen Rechenregeln.
42312 222 xxxxxx
Multiplizieren:
?312 22 xxxx
352
363
2
2
312
234
2
23
234
22
xxxx
xx
xxx
xxx
xxxx
18
Polynomdivision (mit Rest)
Naheliegend: (x+1) : (x+1) = 1 (Vorsicht mit x=-1)
oder p(x) = 2x+2 = 2(x+1) = 2q(x) p:q=2
Ähnlich: (x2-1) : (x+1) = (x-1)
oder x2 - 1 = (x-1) (x+1)
13312
)13(352422
22
234234
xxxxx
xxxxxxxxx
sieht man
Aus dem vorigen Beispiel
312352 22234 xxxxxxxx
Formale Definition? Berechnung?
19
Division mit Rest für lN
Zu n,m ϵ lN gibt es eindeutig bestimmte q,r ϵ lN mit r<m, so dass
n = q∙m + r
gilt. Dabei ist q das Ergebnis und r der Rest der ganzzahligen
Division von n durch m: n/m = q Rest r
Übertragung auf Polynome:
Zu zwei Polynomen N und M mit Koeffizienten aus lR gibt es
eindeutig bestimmte Polynome Q, R mit Koeffizienten aus lR mit
deg(R) < deg(M), so dass N = Q∙M + R.
Dabei ist Q das Ergebnis und R der Rest der Polynomdivision
von N durch M, N : M = Q Rest R
20
Beispiel
3x x 1 )1/(121: 2 xxxx
)( 23 xx 2x
)( 2 xx
x2)22( x
1 (-1 ist der Rest)
( ) ( )
21
Lineare Polynome
Wichtige Spezialfälle: Polynome von kleinem Grad
Im Fall deg(P) ≤ 1 heißt P linear und ist eine Gerade.
P von der Form
bxaxPP )(
z.B. in linearen Gleichungen: a∙x + b = 0
Ist leicht zu lösen, so lange a ≠ 0 ist.
22
Quadratische Polynome
Im Fall deg(P) ≤ 2 heißt P quadratisch, ist also von der Form
P = P(x) = a∙x2 + b∙x + c (eine Parabel)
Dazu gehören die quadratischen Gleichungen (oBdA a=1):
02 qpxx
mit den Lösungen
qpp
x 42
2
21
so lange p2 ≥ 4q ist (andernfalls komplexe Lösungen!)
Aufgabe: 2x2 – 14x + 24 = 0. Lösungen? x=3, x=4.
23
Nullstellensuche
Die Nullstellen x1 , x2 eines quadratischen Polynomes liefern
eine Zerlegung in Linearfaktoren:
).)(( 21
2 xxxxqpxx
Sei P ein beliebiges Polynom vom Grad n mit Nullstelle x1.
Dann kann man den Linearfaktor x – x1 abspalten durch
Polynomdivision:
)()()( 1xxxQxP
mit einem Polynom Q vom Grad n-1.
Die Nullstellen von P sind nun x1 und die Nullstellen von Q.
Hauptsatz der Algebra: Polynom zerfällt in n Linearfaktoren.
24
Beispiele
Polynome P und rationale Funktionen P/Q sind wichtige
Klassen von Beispielfunktionen und dienen als Baukasten,
um kompliziertere Funktionen anzunähern
(Potenzreihe, Computergraphik, Bildverarbeitung)
Annäherung der
Exponentialfunktion
bei x=0 durch
Polynome wach-
senden Grads.