Notebook zu: Mathematik für Informatiker
Band 1

©2001-2007 Gerald Teschl (http://www.mat.univie.ac.at/~gerald/) und Susanne Teschl  (http://staff.technikum-wien.at/~teschl/)

Dieses Notebook ist als Ergänzung zu unserem Buch Mathematik für Informatiker, Band 1, Springer 2007, gedacht. Dort finden Sie auch weitere Erklärungen.

Logik und Mengen

Mengen

A = {a, b, c};  B = {c, d, e};

Vereinigung

Union[A, B]

Durchschnitt

Intersection[A, B]

Vereinfachung (Sortieren und Entfernen von Mehrfachelementen)

Union[{a, c, b, c}]

A = {a, c, b, c};  B = {c, b, a};

Achtung:

{A == B, Union[A] == Union[B]}

Schaltalgebra

Ein kleines Programm zur Darstellung von Logiktafeln

LogicTable[f_, v_List] := 
      Module[{n = Length[v], tabl, values, 
          rules}, 
tabl = {Flatten[{v, 
                f}]}; 
Do[
values =  
            IntegerDigits[i, 2, n]  /.  {0 -> False, 
                1 -> True}; 
rules = 
            Table[Rule[v[[i]], values[[i]] ], {i, 
                n}]; 
tabl = 
            Append[tabl, 
              Flatten[{values, f  /.  rules}]];
, {i, 0, 
            (2^n) - 1}]; 
TableForm[
          tabl]
]

LogicTable[{! a, ! (a || b), ! a && ! b}, {a, 
        b}]

LogicalExpand[! a && ! b || ! a && b || a && b]

LogicalExpand[Implies[a, b]]

Zahlenmengen und Zahlensysteme

Approximation von (Sqrt[2])

d[q_] := 
      Module[{p = q}, 
While[((((p/q)))^2) < 2, 
          p = p + 1]; 
{((p - 1)/q), (p/q)}]

d[100]

Clear[d]

Ungleichungen

Simplify[(x/((x^2) + (y^2))) < (1/y), x > 0 && y > 0]

<< Algebra`InequalitySolve`

InequalitySolve[1 - (x^2) > 0, x]

Komplexe Zahlen

z1 = 1 + 2  I; z2 = 3 -  I; (z1/z2)

{Re[z1], Im[z1], Conjugate[z1], Abs[z1]}

(Sqrt[1 + I (Sqrt[3])])

ComplexExpand[%]

Simplify[((Sqrt[a b])/(Sqrt[a]))]

Simplify[((Sqrt[a b])/(Sqrt[a])),  a > 0]

Sqrt[-I] Sqrt[-I] == Sqrt[(-I) (-I)]

Clear[z1, z2]

Summen- und Produktzeichen

(∑_(k = 1)^n) k

(∏_(k = 1)^n) k

Umwandlung zwischen Zahlensystemen

BaseForm[0.1, 2]

16^^FAD

8^^67

Teilbarkeit und Primzahlen

PrimeQ[4]

Do[
If[PrimeQ[n], 
          Print[n]], 
{n, 1, 5}];

FactorInteger[180]

GCD[75, 38]

Mod[22, 5]

Quotient[22, 5]

Elementare Begriffe der Zahlentheorie

Rest modulo m

Mod[17, 5]

Multiplikatives Inverses

PowerMod[4, -1, 9]

Euklidscher Algorithmus

Euklid[a_Integer, b_Integer] :=  
        Module[{r = a, rr = b}, 
While[ 
            rr !=  0,  {r, rr} = {rr, 
                Mod[r, rr]}]; 
r];

Euklid[75, 38]

GCD[75, 38]

Rekursive Alternative

Euklid[a_Integer, 0] = a; 
    Euklid[a_Integer, b_Integer] := Euklid[b, Mod[a, b]];

Euklid[75, 38]

Erweiterter Eukild

ExtendedEuklid[a_Integer, b_Integer] :=  
        Module[{r = a, rr = b, x = 1, xx = 0, y = 0, yy = 1,  
            Q}, 
While[ 
            rr  !=  0,  
Q = 
              Quotient[r, rr]; 
{r, rr, x, xx, y, 
                yy} = {rr, Mod[r, rr], xx, x - Q xx, yy, 
                y - Q yy}
]; 
{r, x, 
            y}];

ExtendedEuklid[3489, 3827]

ExtendedGCD[3489, 3827]

RSA

ToCharacterCode["KLEOPATRA"]

x = % - 65

n =  1147;  e = 29;

y = PowerMod[x, e, n]

d = PowerMod[e, -1, EulerPhi[n]]

Mod[y^d, n]

FactorInteger[n]

m = (31 - 1) (37 - 1)

EulerPhi[n]

PowerMod[e, -1, m]

Clear[x, y, n, e, d, m]

Chinesischer Restsatz

Needs["NumberTheory`NumberTheoryFunctions`"]

ChineseRemainder[{2, 3, 2}, {3,  5,  7}]

Polynomringe und endliche Körper

Faktorisierung

Factor[x^3 - 1]

Expand[%]

Polynomdivision

PolynomialQuotient[3  x^4 + x^3 - 2 x, x^2 + 1, x]

PolynomialRemainder[3  x^4 + x^3 - 2 x, x^2 + 1, x]

Euklid'scher Algorithmus

PolynomialEuklid[p_, q_] :=  
        Module[{r = p, rr = q}, 
While[ 
            rr =!=  0,  {r, rr} = {rr, 
                PolynomialRemainder[r, rr, 
                  x]}]; 
(r/(CoefficientList[r, x]))[[-1]]];

PolynomialEuklid[(x^3) - 2  x + 1, (x^2) - 1]

PolynomialExtendedEuklid[p_, q_] :=  
        Module[{r = p, rr = q, s = 1, ss = 0, t = 0, tt = 1, 
            Q}, 
While[ 
            rr  =!=  0,  
Q = 
              PolynomialQuotient[r, rr, x]; 
{r, rr, s, ss, 
                t, tt} = {rr, PolynomialRemainder[r, rr, x], ss, s - Q ss, 
                tt, t - 
                  Q tt}
]; 
{r, s, t}/(CoefficientList[r, x])[[-1]]];

PolynomialExtendedEuklid[(x^3) - 2  x + 1, (x^2) - 1]

Interne Befehle

PolynomialGCD[(x^3) - 2  x + 1, (x^2) - 1]

Needs["Algebra`PolynomialExtendedGCD`"]; 
    PolynomialExtendedGCD[(x^3) - 2  x + 1, (x^2) - 1]

Multiplikatives Inverses

Needs["Algebra`PolynomialPowerMod`"];
PolynomialPowerMod[x + 1, -1,  {(x^2) + x + 1, 2}]

Faktorisierung

Factor[(x^8) + (x^4) + (x^3) + x + 1,  Modulus -> 2]

Factor[(x^8) + (x^4) + (x^3) + x + 1,  Modulus -> 3]

Folgen und Reihen

Folgen

a[n_] := (1/(2^n))

{a[0], a[1], a[2], a[3], a[4]}

a[1] = 2. ; a[n_] := (1/2) (a[n - 1] + (2/a)[n - 1])

Table[a[n], {n, 1, 5}]

a[n_] := (((1 + (1/n)))^n)

N[{a[2], a[3], a[10], a[100], a[1000], a[10000]}]

Limit[a[n], n -> ∞]

N[E, 30]

Clear[a]

Heron'sche Folge

MySqrt[x_] := 
      Module[{h = N[x], hh = N[x] + 1}, 
While[hh - h > 0, 
          hh = h; h = (1/2) (h + 
                  (x/h))]; 
hh]

MySqrt[2]

Reihen

(∑_(k = 0)^∞) (1/(2^k))

Sum[1/2^k, {k, 1, Infinity}]

s[n_] = (∑_(k = 1)^n) (1. /(k^2));

{s[1], s[3], s[10],  s[100],  s[1000],  s[10000]}

(∑_(k = 1)^∞) (1/(k^2))

N[%]

Kombinatorik

Fakultät und Bimomialkoeffizient

6!

Binomial[45, 6]

Rekursionen und Wachstum von Algorithmen

Iteration und Chaos

f[μ_, x_] := 
        x + μ (1 - x) x;
F[x_, μ_, n_] := 
        Module[{xx = x}, Do[xx = f[μ, xx], {n}]; xx];

f[μ_, x_] := 
        x + μ (1 - x) x;
F[x_, μ_, n_] := Nest[f[μ, #1] &, x, n];

Table[F[0.1, 2.2, n],  {n, 1, 10}]

ShowWeb[F_, xstart_, nmax_, opts___] := 
      Module[{x, xmin, xmax, delta, graph, web, 
            lines}, 
lines = 
            Type  /.  {opts, Type -> Line}; 
x[0] := 
            xstart; 
x[n_] := x[n] = 
              f[x[n - 1]]; 
If[x[0] == x[1], 
            Return[Print[Fixed Point!]]]; 
web = 
            Flatten[Table[{{x[n], x[n]}, {x[n], x[n + 1]}}, {n, 0, nmax}], 
              1]; 
xmax = Max[web]; xmin = Min[web]; 
          delta = 0.1 (xmax - xmin); 
graph = 
            Plot[{f[x], x}, {x, xmin - delta, xmax + delta}, 
              DisplayFunction -> Identity]; 
Show[
            graph, Graphics[lines[web]], 
            DisplayFunction -> $DisplayFunction]
]  /; (IntegerQ[nmax] && Positive[nmax])

Needs["Graphics`Arrow`"];
Arrows[l_List] := 
        Table[Arrow[l[[i]], l[[i + 1]], 
            HeadLength -> 0.025], {i, Length[l] - 1}];

f[x_] := x + μ x (1 - x);

μ = 1; ShowWeb[f, 0.1, 6, Type -> Arrows];

μ = 2.2; ShowWeb[f, 0.7, 6, Type -> Arrows];

μ = 3; ShowWeb[f, 0.7, 50];

Clear[f, F]

Lösung einer Rekursion

Needs["DiscreteMath`RSolve`"];

RSolve[{a[n] == 3  a[n - 1] - 4, a[0] == 5}, a[n], 
      n]

RSolve[{a[n] == a[n - 1] + 6  a[n - 2],  a[0] == 1,  
        a[1] == 8}, a[n], n]

Landausymbol

LandauO[f_ + g_] := 
        LandauO[If[tmp == 0, g, f] ] /;  
          FreeQ[tmp = Limit[Abs[(f/g)], n -> ∞], 
            n];
LandauO[c_  f_] :=  LandauO[f]  /; FreeQ[c, n];

LandauExpand[expr_] :=  
        LandauO[Expand[expr]] /. 
          Log[x_] /;  PolynomialQ[x, n] -> Log[n];

LandauExpand[((n + 1)/((n^2) + 1)) + Exp[-n + 3] + 
        11 n Log[3 n + 1]]

Vektorräume

Vektoren

a = {1, 2, 0, -1};  b = {3, 0, 1, 2};

3  a - b

Norm[a]

(Sqrt[a . a])

Clear[a, b]

Matrizen und Lineare Abbildungen

Folgender Befehl wendet MatrixForm automatisch vor der Ausgabe an:

$PrePrint = MatrixForm;

Matrizen

A = {{1, 3, 2}, {-1, 4, 5}};  
    B = {{-2, 4, 0}, {6, 2, -8}};

2 (A + B)

MatrixForm[%]

Dimensions[A]

Transpose[(({{3, 2}, {5, -1}, {0, 7}}))]//MatrixForm

IdentityMatrix[2] // MatrixForm

DiagonalMatrix[{1, 2, 3}]  // MatrixForm

KroneckerDelta[1, 2]

Multiplikation von Matrizen

A=(({{4, 2, 0}, {-1, 3, 5}}));B=(({{2, 1}, {3, 7}, {1, 0}}));  A . B // MatrixForm

M = (({{7, 1}, {2, 5}}));M . M // MatrixForm

M^2 // MatrixForm

Eingabe von Gleichungen mit Matrizen

A = {{5, 3}, {2, -1}}; x = {x1, x2}; 
    b = {2, 3};
A . x == b

Solve[%, {x1, x2}]

Clear[A, B, b, x]

Inverse Matrix

A = {{2, 4}, {-1, 3}}; Inverse[A]  // MatrixForm

Inverse[(({{0.30, 0.59, 0.11}, {0.60, -0.28, -0.32}, {0.21, -0.52, 0.31}}))]//MatrixForm

Clear[A]

Lineare Gleichungen

Gauß-Algorithmus

A = (({{1, -1, -1, 0}, {-1, 0, -3, -11}, {4, -1, 2, 15}}));

RowReduce[A] // MatrixForm

RowReduce[(({{1, -1, 7, 6}, {-1, 4, -13, 3}, {2, 1, 8, 17}}))]//MatrixForm

RowReduce[(({{0, 1, 3, 2}, {1, 2, 5, 0}, {2, 5, 13, 2}}))]//MatrixForm

RowReduce[(({{1, 2, -1, 3}, {2, 4, -2, 6}, {3, 6, -3, 9}}))]//MatrixForm

Solve[{y  + 3  z ==  2,  x   + 2  y + 5  z == 0,  
        2  x  + 5  y  +  13  z  ==  2},  {x,  y,  
        z}]

Solve[{y  + 3  z ==  2,  x   + 2  y + 5  z == 0,  
        2  x  + 5  y  +  13  z  ==  2},  {x,  z, y}]

Clear[A]

Rang, Kern und Bild

A =  {{1, 1, 2},  {0, 1, 1},  {1, 0, 1}}; NullSpace[A]

Transpose[RowReduce[Transpose[A]]] // MatrixForm

MatrixRank[A]

Determinante

A = (({{1, -1, -1}, {-1, 0, -3}, {4, -1, 2}}));Det[A]

A = (({{0, 1, 3}, {1, 2, 5}, {2, 5, 13}}));Det[A]

Clear[A]

Lineare Optimierung

Lineare Ungleichungen

Needs["Graphics`InequalityGraphics`"]

InequalityPlot[ 
        x ≥ 0 && y ≥ 0 && x + y ≤ 20 && 
          x + y ≥ 10 && y ≤ 2  x,  {x,  0,  
          20},  {y, 0,  20} ];

Lineare Optimierung

LinearProgramming[{4, 3},(({{-1, -1}, {1, 1}, {2, -1}})),{-20, 10, 0}]

LinearProgramming[{-3, -4},(({{-1, -2}, {-2, -1}})),{-20, -28}]

\(Maximize[1.8 - 0.04\ x1 - 0.03\ x2, 
      x1 ≥ 0 && x2 ≥ 0 && 
        20 - x1 - x2 ≥ \ 0 && 

        x1 + x2 ≥ \ 10 && \ x2 ≤ \ 2  x1, {x1, 
        x2}]\)

Skalarprodukt und Orthogonalität

Skalarprodukt

a = {1, 2, 3}; b = {2, -4, 1}; a . b

(Sqrt[a . a])

Kreuzprodukt

Cross[{1, 2, 0},  {3, 4, 5}]

Ray Tracing

solr = 
      Solve[(((e . n  +  kr ))^2) == (((e  . n))^2) (1 + 
                2  kr (e . n) + kr^2), kr]

1 + 2  kr (e . n) + kr^2 /. solr // Simplify

er = Simplify[e  +  kr n  /.  solr[[2]] ]

%  /.  {n -> {0, 0, 1},  e -> {1, 0, -1}/(Sqrt[2])}  // 
      Simplify

solb = 
      Solve[1  -  (((e . n + kb )/
                      Sqrt[(1 + 2 (e . n) kb   + 
                            kb ^2)]))^2 == 
            nb^2 (1 - (e . n)^2), kb] // Simplify

kb  = kb/.solb[[1]]

1 + 2  kb (e . n) + kb^2  // Simplify

Clear[solr, solb, er, kb]

Gram-Schmidt-Verfahren

<< LinearAlgebra`Orthogonalization`

GramSchmidt[{{1, 0, 1}, {0, 1, 1}, {1, 2, 4}}]

Diskrete Kosinustransformation

DCT[n_] := 
      Table[(Sqrt[((2 - If[k == 1, 1, 0])/n)]) 
          Cos[(((2  j - 1) (k - 1) π)/(2  n))], {j, n}, {k, 
          n}]

DCT[2] // MatrixForm  // Simplify

DCT[3] // MatrixForm  // Simplify

Eigenwerte und Eigenvektoren

Koordinatentransformationen

U[ϕ_]=(({{Cos[ϕ], -Sin[ϕ], 0}, {Sin[ϕ], Cos[ϕ], 0}, {0, 0, 1}}));

U[π/4]  // MatrixForm

U[((-π)/4)] . {1, 3, 4}  // Simplify // MatrixForm

A=(({{0, 1, 0}, {1, 0, 0}, {0, 0, 1}}));

Inverse[U[(π/4)]] . A . U[(π/4)] // MatrixForm

Clear[A, U]

Eigenwerte und Eigenvektoren

A=(({{0, -1}, {1, 0}}));Eigenvalues[A]

Eigenvectors[A]

Clear[A]

Implizite Kurven

Needs["Graphics`ImplicitPlot`"];
ImplicitPlot[{x == y, x == -y, 
          3 x^2 - 2 x y  + 3 y^2 == 4}, {x, -1.5, 
          1.5}];

Grundlagen der Graphentheorie

Needs["DiscreteMath`Combinatorica`"]

Darstellung von Graphen

gr = 
        FromAdjacencyMatrix[{{0, 1, 0, 1, 1},  {1, 0, 1, 1, 0},  {0, 1, 0, 
              1, 0},  {1, 1, 1, 0, 0}, {1, 0, 0, 0, 0}}, {{0, 1},  {1, 
              1},  {2, 1},  {1, 0}, {0, 0}}];

ShowGraph[gr];

ShowLabeledGraph[gr];

Zusammenhang

ConnectedQ[gr]

EulerZug

gr = 
        FromAdjacencyMatrix[{ {0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 1, 
              0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1}, {0, 
              0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 
              0}, {0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 1, 
              0, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 0, 
              0, 1, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1}, {1, 0, 1, 0, 
              0, 0, 0, 1, 0, 1, 0}},  { {0, 2}, {0, 1}, {1, 1}, {1.5, 
              0}, {2, 1}, {3, 1}, {3, 2}, {2, 2}, {2, 3}, {1, 3}, {1, 
              2}}];

ShowLabeledGraph[gr];

EulerianCycle[gr]

Hamilton Kreis

hc = HamiltonianCycle[gr]

Bäume und kürzeste Wege

Needs["DiscreteMath`Combinatorica`"]

Gewichtete Graphen

gr = 
        FromAdjacencyMatrix[{{∞, 
              6, ∞, ∞, ∞, 10, 
              1}, {6, ∞, 5, ∞, ∞, ∞, 
              7}, {∞, 5, ∞, 6, ∞, ∞, 
              9}, {∞, ∞, 6, ∞, 3, ∞, 
              4}, {∞, ∞, ∞, 3, ∞, 3, 
              2}, {10, ∞, ∞, ∞, 3, ∞, 
              10}, {1, 7, 9, 4, 2, 10, ∞}}, {{-0.5, 
              0.86}, {-1, 
              0}, {-0.5, -0.86}, {0.5, -0.86}, {1, 0}, {0.5, 
              0.86}, {0, 0}}, EdgeWeight];

Travelling Salesman Problem

ts = TravelingSalesman[gr]

ShowCycle[G_Graph, c_List] := 
        ShowGraph[
          SetGraphOptions[
            G, {Append[Partition[c, 2, 1], 
                EdgeColor -> Green]}]];

ShowCycle[gr, ts];

ShowGraph[Highlight[gr, {Partition[ts, 2, 1]}]];

ShowGraph[CompleteGraph[6]];

Minimal aufspannende Bäume

ShowGraph[MinimumSpanningTree[gr]];

Kürzeste Wege

gr = 
        FromAdjacencyMatrix[{{∞, 4, 6, 
              7},  {4, ∞, ∞, 
              1},  {6, ∞, ∞, 2},  {7, 1, 
              2, ∞}}, {{0, 1},  {0, 0},  {1, 0},  {1, 1}}, 
          EdgeWeight];
sp = ShortestPath[gr, 1, 4]

ShowGraph[gr];

ShowCycle[gr, sp];

Flüsse in Netzwerken und Matchings

Needs["DiscreteMath`Combinatorica`"]

Netzwerke

A = {{∞, 10, ∞, 
          12, ∞, ∞}, {∞, ∞, 
          9, ∞, ∞, ∞}, {∞, ∞, ∞, 4, ∞, 
          8}, {∞, ∞, ∞, ∞, 
          12, ∞}, {∞, ∞, 
          6, ∞, ∞, 
          14}, {∞, ∞, ∞, ∞, ∞, ∞}}; 
    v = {{-1, 0}, {-0.5, 0.86}, {0.5, 
          0.86}, {-0.5, -0.86}, {0.5, -0.86}, {1, 
          0}};
gr = 
        FromAdjacencyMatrix[A, v, EdgeWeight, 
          Type -> Directed];

ShowLabeledGraph[gr, 
        EdgeLabel -> {10, 12, 9, 4, 8, 12, 6, 14}];

NetworkFlow[gr, 1, 6]

NetworkFlow[gr, 1, 6, All]

ShowNetworkFlow[A_, v_] := 
      Module[{gr, nf, el = {}, vl, vv, ww}, 
gr = 
          FromAdjacencyMatrix[A, v, EdgeWeight, 
            Type -> Directed]; 
nf = 
          NetworkFlow[gr, 1, Length[v], 
            All]; 
Do[
vl = 
            nf[[i]]; 
Do[
{vv, ww} = 
              vl[[j]]; 
el = 
              Append[el, 
                StringJoin[ToString[A[[i]][[vv]]], ",", 
                  ToString[ww]]];
, {j, 1, 
              Length[vl]}], 
{i, 1, 
            Length[nf]}]; 
ShowLabeledGraph[gr, 
          EdgeLabel -> el]
]

ShowNetworkFlow[A, v];

Clear[A, v, gr];

Matchings

gr = 
        FromUnorderedPairs[{{1, 5}, {1, 6}, {2, 6}, {2, 7}, {2, 8}, {3, 
              7}, {4, 6}}, {{0, 3}, {0, 2}, {0, 1}, {0, 0}, {1.5, 3}, {1.5, 
              2}, {1.5, 1}, {1.5, 0}}];

ShowLabeledGraph[gr];

BipartiteMatching[gr]

ShowGraph[Highlight[gr, {%}]];