Föreläsningsöversikt¶
- Fler sätt att representera grafer
- grannlista
- grannmatris
- Matriser, matrismultiplikation
- Räkna ut antalet vägar av en viss längd som finns mellan två noder
- Programmering
- dela upp i delproblem
- parprogrammering
Repetition, graf¶
- En graf består av hörn och kanter, $G = (V, E)$ där $V$ är mängden hörn/noder och $E$ är mängden kanter/bågar
- I en oriktad graf är varje kant en mängd.
- I riktad graf är varje kant en tupel.
- Exempel
- Oriktad graf: $G = (V, E)$, $V = \{a, b, c, d\}$, $E = \{\{a,b\}, \{b,c\}, \{a, c\}, \{c,d\}\}$
- Riktad graf: $G = (V, E)$, $V = \{a, b, c, d\}$, $E = \{(a,b), (b,c), (a, c), (c,d)\}$
Grannlista¶
- Ett annat sätt att representera en graf är att använda en grannlista (eng. adjacency list).
- En nod $x$ och de noder som kan nås via en båge från $x$.
- T.ex. för $G = (V, E)$, $V = \{a, b, c, d\}$, $E = \{(a,b), (b,c), (a, c), (c,d)\}$:
- a: b, c
- b: c
- c: d
- d:
Grannlista för oriktad graf¶
- Grannlistor är implicit riktade.
- För oriktade grafer beskriver man det som en båge i varje riktning
- T.ex. för $G = (V, E)$, $V = \{a, b, c, d\}$, $E = \{ \{a,b\}, \{a, c\}, \{a, d\}, \{a, e\}, \{b,c\}, \{b, d\}, \{c,d\}, \{c, e\}, \{d, e\}\}$
- a: b, c, d, e
- b: a, c, d
- c: a, b, d, e
- d: a, b, c, e
- e: a, c, e
Grannlista i Python¶
- I Python är datatypen
dictionary
ypperlig för att representera grannlistor. - $G = (V, E)$, $V = \{a, b, c, d\}$, $E = \{(a,b), (b,c), (a, c), (c,d)\}$
- T.ex. strängar med nodernas namn som nycklar och listor med deras grannars namn som värden.
- För grafen till höger:
my_graph = {'a': ['b', 'c'],
'b': ['c'],
'c': ['d'],
'd': []}
Grannlista i Python för viktad riktad graf¶
- Nästlade dictionaries.
- T.ex. strängar med nodernas namn som nycklar, värdena är dictionaries med grannoderna som nycklar och vikten av bågen till den noden som värde.
- För grafen till höger:
my_weighted_graph = {'a': {},
'b': {'a': 3, 'd': 7},
'c': {'a': 4},
'd': {'c': 2, 'e': 5},
'e': {'c': 3}}
Lite kontext¶
- I princip all matematik man stöter på i grundskolan och på gymnasiet behandlar "vanliga" tal, som t.ex. $3$, $42$, $\frac{22}{7}$, decimaltalet $639.95$, eller till och med irrationella tal som $\pi$.
- I den här kursen har vi också studerat matematiska objekt som mängder, tupler, och grafer, och vi har nämnt koncept som relationer och funktioner utan att närmare studera dem. Dessa koncept brukar betraktas som delar av den diskreta matematiken.
- En annan viktig gren av matematiken som man först brukar stöta på på universitetsnivå är den så kallade linjära algebran.
- (Idag är en kurs i linjär algebra obligatorisk för nästan alla (om inte alla) teknologer på LiU, ca 75 % läser den under första terminen.)
Linjär algebra (eng. linear algebra)¶
- Linjär algebra är den del av matematiken som studerar vektorer, matriser, linjära rum/vektorrum, linjära ekvationssystem och transformationer i linjära koordinatsystem.
- Den linjära algebran ligger till grund för den både den moderna naturvetenskapen och, genom statistiken, de kvantitativa humanvetenskaperna.
Skalärer¶
- En skalär är det ~nördiga~ formellt korrekta ordet för ett "vanligt" tal, som t.ex. $3$, $42$, $\frac{22}{7}$, decimaltalet $639.95$, eller till och med ett irrationellt tal som $\pi$, inom linjär algebra.
- Att dessa tal behöver ett separat begrepp säger något om att fokuset inom linjär algebra är något annat.
Matriser¶
- En matris är en matematisk konstruktion som har rader och kolumner och på vilken vi antar att vi kan utföra vissa matematiska operationer.
- Inom linjär algebra används traditionellt versaler för att referera till matriser.
- T.ex. matrisen $X$ nedan.
- Motsvarande gemener används för att referera till dess element.
- Element $x_{3,4}$ är alltså värdet på rad 3, kolumn 4, i matrixen $X$ nedan.
$$X = \begin{bmatrix} x_{1,1} & x_{1,2} & \ldots & x_{1,n} \\ x_{2,1} & x_{2,2} & \ldots & x_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m,1} & x_{m,2} & \ldots & x_{m,n} \\ \end{bmatrix} $$
Matriser, fortsättning¶
- Ibland ser man matriser skrivna med vanliga parenteser snarare än hakparenteser.
- Båda notationerna är vanliga och allmänt accepterade, så länge man är konsekvent.
$$X = \begin{pmatrix} x_{1,1} & x_{1,2} & \ldots & x_{1,n} \\ x_{2,1} & x_{2,2} & \ldots & x_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m,1} & x_{m,2} & \ldots & x_{m,n} \\ \end{pmatrix} $$
Vektorer i matriser¶
- Varje rad och varje kolumn i en matris kan betraktas som en vektor.
- Givet $m \times n$-matrisen $X$ nedan existerar det
- $m$ stycken radvektorer av längden $n$ och
- $n$ stycken kolumnvektorer av längden $m$.
$$X = \begin{bmatrix} x_{1,1} & x_{1,2} & \ldots & x_{1,n} \\ x_{2,1} & x_{2,2} & \ldots & x_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m,1} & x_{m,2} & \ldots & x_{m,n} \\ \end{bmatrix} $$
Vektorer i matriser¶
- Rad- och kolumnvektorer från en matris $E$ brukar betecknas med motsvarande gemen och index där en asterisk, $*$, representerar "alla":
- 3 stycken radvektorer: $e_{1,*}=(1, 1, 0, 2)$, $e_{2,*}=(0, 2, 1, 0)$, $e_{3,*}=(3, 0, 0, 1)$
- 4 stycken kolumnvektorer: $e_{*,1}=(1, 0, 3)$, $e_{*,2}=(1, 2, 0)$, $e_{*,3}=(0, 1, 0)$, $e_{*,4}=(2, 0, 1)$
$$ E = \begin{bmatrix} 1 & 1 & 0 & 2 \\ 0 & 2 & 1 & 0 \\ 3 & 0 & 0 & 1 \\ \end{bmatrix} $$
Vektorer i matriser¶
- För att tydliggöra att vissa vektorer utgör kolumner i en matris skriver man ibland:
- $e_{*,1}=\begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix}$, $e_{*,2}=\begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}$, $e_{*,3}=\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}$, $e_{*,4}=\begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix}$, eller
- $e_{*,1}=\begin{pmatrix} 1 \\ 0 \\ 3 \end{pmatrix}$, $e_{*,2}=\begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix}$, $e_{*,3}=\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}$, $e_{*,4}=\begin{pmatrix} 2 \\ 0 \\ 1 \end{pmatrix}$
- Detta har dock normalt sett ingen formell betydelse.
$$ E = \begin{bmatrix} 1 & 1 & 0 & 2 \\ 0 & 2 & 1 & 0 \\ 3 & 0 & 0 & 1 \\ \end{bmatrix} $$
Grannmatris (Adjacency Matrix)¶
- En graf består av noder och bågar, $G = (V, E)$
- En grannmatris $A$ är ett alternativt sätt att representera grafens bågar.
- Om noden $v_1$ har noden $v_2$ som granne, markerar vi detta med en $1$:a på rätt ställe i matrisen, eller med bågens vikt om grafen är viktad.
- En grannmatris är per definition kvadratisk, dvs den har lika många rader som kolumner.
Grannmatris¶
- Om vi har den riktade och oviktade grafen $G$ enligt figuren får vi följande grannmatris (bokstäverna i blått skrivs egentligen inte ut, men är med här av pedagogiska skäl)
- Oviktade bågar indikeras av ettor.
- Matrisen $A$ nedan utgör grannmatris för grafen $G$ i figuren:
$$ A = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right] \end{array} $$
Notation för grannmatriser¶
- Det förekommer flera olika formalismer för att uttrycka grannmatrisen till en graf $G$:
- $A_G$, "$A$ är $G$s grannmatris"
- $A(G)$, vi betraktar $A$ som en funktion som givet en graf ger dess grannmatris, "grannmatrisen till $G$"
- $G = (V, A)$, där $A$ används som alternativ till $E$, dvs en mängd av 2-tupler eller mängder för att indikera vilka bågar som existerar.
- $G = (V, E, W)$, som är vanligast för viktade grafer och där vi kallar grannmatrisen för $W$ (som i weight) istället för $A$.
Grannmatris, exempel¶
- Om vi har den riktade och oviktade grafen $G$ enligt figuren får vi följande grannmatris (bokstäverna i blått skrivs egentligen inte ut, men är med här av pedagogiska skäl)
- Oviktade bågar indikeras av ettor.
- Den riktade bågen från $d$ till $a$ motsvaras av siffran 1 på rad 4, kolumn 2 i matrisen:
$$ A = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \color{red}{\textbf{1}} & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right] \end{array} $$
Grannmatris, exempel¶
- Om vi har den riktade och oviktade grafen $G$ enligt figuren får vi följande grannmatris (bokstäverna i blått skrivs egentligen inte ut, men är med här av pedagogiska skäl)
- Oviktade bågar indikeras av ettor.
- Den riktade bågen från $c$ till $b$ motsvaras av siffran 1 på rad 3, kolumn 2 i matrisen:
$$ A = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & \color{red}{\textbf{1}} & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right] \end{array} $$
Grannmatris, exempel¶
- Om vi har den riktade och oviktade grafen $G$ enligt figuren får vi följande grannmatris (bokstäverna i blått skrivs egentligen inte ut, men är med här av pedagogiska skäl)
- Oviktade bågar indikeras av ettor.
- Den riktade bågen från $d$ till $c$ motsvaras av siffran 1 på rad 4, kolumn 3 i matrisen:
$$ A = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & \color{red}{\textbf{1}} & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{array} \right] \end{array} $$
Grannmatris, exempel¶
- Om vi har den riktade och oviktade grafen $G$ enligt figuren får vi följande grannmatris (bokstäverna i blått skrivs egentligen inte ut, men är med här av pedagogiska skäl)
- Oviktade bågar indikeras av ettor.
- Den riktade bågen från $e$ till $d$ motsvaras av siffran 1 på rad 5, kolumn 4 i matrisen:
$$ A = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & \color{red}{\textbf{1}} & 0 \end{array} \right] \end{array} $$
Grannmatris för en viktad graf¶
- Vi har ännu inte talat om hur viktade grafer representeras i matematisk notation.
- Ofta görs detta med just en grannmatris.
- Den viktade grafen $G = (V, E, W)$ där $W$ är en grannmatris, ibland kallad viktmatris (eng. weight matrix) i det här sammanhanget, där varje element $i, j$ uttrycker vikten för bågen från nod $i$ till nod $j$.
$$ W = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 7 & 0 \\ 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 5 \\ 0 & 0 & 3 & 0 & 0 \end{array} \right] \end{array} $$
Grannmatris för oriktad graf¶
- Grannmatrisen för en oriktad graf $G$ är symmetrisk.
- En symmetrisk matris $A$ har egenskapen att för alla element gäller att $a_{i,j} = a_{j, i}$.
- Behöver bara lagra halva matrisen vilket kan vara praktiskt för väldigt stora grafer.
$$ A = \require{enclose} \begin{array}{c c} & \begin{array}{c c c c c} \color{#00b9e7}{a} & \color{#00b9e7}{b} & \color{#00b9e7}{c} & \color{#00b9e7}{d} & \color{#00b9e7}{e} \\ \end{array} \\ \begin{array}{c c c c c} \color{#00b9e7}{a} \\ \color{#00b9e7}{b} \\ \color{#00b9e7}{c} \\ \color{#00b9e7}{d} \\ \color{#00b9e7}{e} \end{array} & \left[ \begin{array}{c c c c c} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \end{array} \right] \end{array} $$
Användning av grannmatriser för att räkna ut antal vägar mellan par av noder¶
Antal vägar av en viss längd¶
- Om $A$ är grannmatrisen för den oviktade grafen $G$, så kan vi få fram antal vägar mellan två noder $v_1$ och $v_2$ av längden 1 (eftersom de är grannar).
- Finurligt nog kan vi, genom att räkna ut $A^2$, få fram antalet vägar mellan noder av längden 2.
- Räknar vi ut $A^3$ kan vi få ut antalet vägar mellan två noder av längden 3.
- osv
- Om grafen $G$ är viktad så representerar $A^k$ summan av kostnaderna av alla vägar av längden $k$.
- Mindre direkt tillämpbart men inte meningslöst.
Antal vägar av längden 1¶
- Följande vägar av längden 1 finns i $G$
- 1 väg från $a$ till $b$
- 1 väg från $a$ till $c$
- 1 väg från $a$ till $d$
- 1 väg från $b$ till $c$
- 1 väg från $c$ till $d$
- 1 väg från $d$ till $c$
$$ A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$
Antal vägar av längden 2¶
- Följande vägar av längden 2 finns i $G$
- 2 vägar från $a$ till $c$
- 1 väg från $a$ till $d$
- 1 väg från $b$ till $d$
- 1 väg från $c$ till $c$
- 1 väg från $d$ till $d$
$$A^2 = A \times A = \begin{bmatrix} 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $$
Antal vägar av längden 3¶
- Följande vägar av längden 3 finns i $G$
- 1 väg från $a$ till $c$
- 2 vägar från $a$ till $d$
- 1 väg från $b$ till $c$
- 1 väg från $c$ till $d$
- 1 väg från $d$ till $c$
$$A^3 = A \times A \times A = \begin{bmatrix} 0 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$
Matrismultiplikation¶
- För att multiplicera två matriser, $A$ och $B$, måste antalet kolumner i $A$ vara samma som antalet rader i $B$.
- Produktmatrisen kommer ha lika många rader som $A$ och lika många kolumner som $B$.
- Element på plats $i,j$ i produktmatrisen är skalärprodukten av radvektor $i$ från $A$ och kolumnvektor $j$ från $B$.
Skalärprodukt¶
- Skalärprodukten är en operation mellan två vektorer av samma längd som resulterar i en skalär.
- Kallas ofta "dot product" på engelska.
- Givet vektorerna $a$ och $b$ av längden $i$ så är skalärprodukten:
$$a \cdot b = (a_1, a_2, \ldots, a_i) \cdot (b_1, b_2, \ldots, b_i) = a_1b_1 + a_2b_2 + \ldots + a_ib_i$$
Skalärprodukt, exempel¶
- $x = (1, 0, 4, 2)$
- $y = (3, 2, 6, 5)$
$$ \begin{align} \notag x \cdot y &= ({\color{Green}{\textbf{1}}}, 0, 4, 2) \cdot ({\color{DarkOrange}{\textbf{3}}}, 2, 6, 5) =\\ \notag&= {\color{Green}{\textbf{1}}} \cdot {\color{DarkOrange}{\textbf{3}}} + \phantom{0 \cdot 2 + 4 \cdot 6 + 2 \cdot 5 =}\\ \notag&\phantom{= 3 + 0 + 24 + 10 =}\\ \notag&\phantom{= 37} \end{align} $$
Skalärprodukt, exempel¶
- $x = (1, 0, 4, 2)$
- $y = (3, 2, 6, 5)$
$$ \begin{align} \notag x \cdot y &= (1, {\color{Green}{\textbf{0}}}, 4, 2) \cdot (3, {\color{DarkOrange}{\textbf{2}}}, 6, 5) =\\ \notag&= 1\cdot3 + {\color{Green}{\textbf{0}}}\cdot{\color{DarkOrange}{\textbf{2}}} + \phantom{4\cdot6 + 2\cdot5 =}\\ \notag&\phantom{= 3 + 0 + 24 + 10 =}\\ \notag&\phantom{= 37} \end{align} $$
Skalärprodukt, exempel¶
- $x = (1, 0, 4, 2)$
- $y = (3, 2, 6, 5)$
$$ \begin{align} \notag x \cdot y &= (1, 0, {\color{Green}{\textbf{4}}}, 2) \cdot (3, 2, {\color{DarkOrange}{\textbf{6}}}, 5) =\\ \notag&= 1\cdot3 + 0\cdot2 + {\color{Green}{\textbf{4}}}\cdot{\color{DarkOrange}{\textbf{6}}} + \phantom{2\cdot5 =}\\ \notag&\phantom{= 3 + 0 + 24 + 10 =}\\ \notag&\phantom{= 37} \end{align} $$
Skalärprodukt, exempel¶
- $x = (1, 0, 4, 2)$
- $y = (3, 2, 6, 5)$
$$ \begin{align} \notag x \cdot y &= (1, 0, 4, {\color{Green}{\textbf{2}}}) \cdot (3, 2, 6, {\color{DarkOrange}{\textbf{5}}}) =\\ \notag&= 1\cdot3 + 0\cdot2 + 4\cdot6 + {\color{Green}{\textbf{2}}}\cdot{\color{DarkOrange}{\textbf{5}}} =\\ \notag&\phantom{= 3 + 0 + 24 + 10 =}\\ \notag&\phantom{= 37} \end{align} $$
Skalärprodukt, exempel¶
- $x = (1, 0, 4, 2)$
- $y = (3, 2, 6, 5)$
$$ \begin{align} \notag x \cdot y &= (1, 0, 4, 2) \cdot (3, 2, 6, 5) =\\ \notag&= 1\cdot3 + 0\cdot2 + 4\cdot6 + 2\cdot5 =\\ \notag&= 3 + 0 + 24 + 10 =\\ \notag&\phantom{= 37} \end{align} $$
Skalärprodukt, exempel¶
- $x = (1, 0, 4, 2)$
- $y = (3, 2, 6, 5)$
$$ \begin{align} \notag x \cdot y &= (1, 0, 4, 2) \cdot (3, 2, 6, 5) =\\ \notag&= 1\cdot3 + 0\cdot2 + 4\cdot6 + 2\cdot5 =\\ \notag&= 3 + 0 + 24 + 10 =\\ \notag&= 37 \end{align} $$
Matrismultiplikation, repetition¶
- För att multiplicera två matriser, $A$ och $B$, måste antalet kolumner i $A$ vara samma som antalet rader i $B$.
- Produktmatrisen kommer ha lika många rader som $A$ och lika många kolumner som $B$.
- Element på plats $i,j$ i produktmatrisen är skalärprodukten av radvektor $i$ från $A$ och kolumnvektor $j$ från $B$.
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \phantom{\begin{bmatrix} A_{1,*}\cdot B_{*,1} & A_{1,*}\cdot B_{*,2} \\ A_{2,*}\cdot B_{*,1} & A_{2,*}\cdot B_{*,2} \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11 & 4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} {\color{DarkOrange}{\textbf{1}}} \cdot {\color{Green}{\textbf{7}}} + {\color{DarkOrange}{\textbf{2}}} \cdot {\color{Green}{\textbf{9}}} + {\color{DarkOrange}{\textbf{3}}} \cdot {\color{Green}{\textbf{11}}} & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11 & 4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ \require{color} A = \begin{bmatrix} {\color{DarkOrange}{\textbf{1}}} & {\color{DarkOrange}{\textbf{2}}} & {\color{DarkOrange}{\textbf{3}}} \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} {\color{Green}{\textbf{7}}} & 8 \\ {\color{Green}{\textbf{9}}} & 10 \\ {\color{Green}\textbf{11}} & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} {\color{DarkOrange}{\textbf{1}}} \cdot {\color{Green}{\textbf{7}}} + {\color{DarkOrange}{\textbf{2}}} \cdot {\color{Green}{\textbf{9}}} + {\color{DarkOrange}{\textbf{3}}} \cdot {\color{Green}\textbf{11}} & \phantom{1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12} \\ \phantom{4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11} & \phantom{4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12} \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} {\color{DarkOrange}{\textbf{1}}} & {\color{DarkOrange}{\textbf{2}}} & {\color{DarkOrange}{\textbf{3}}} \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & {\color{Green}{\textbf{8}}} \\ 9 & {\color{Green}\textbf{10}} \\ 11 & {\color{Green}\textbf{12}} \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & {\color{DarkOrange}{\textbf{1}}} \cdot {\color{Green}{\textbf{8}}} + {\color{DarkOrange}{\textbf{2}}} \cdot {\color{Green}\textbf{10}} + {\color{DarkOrange}{\textbf{3}}} \cdot {\color{Green}\textbf{12}} \\ \phantom{4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11} & \phantom{4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12} \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ {\color{DarkOrange}{\textbf{4}}} & {\color{DarkOrange}{\textbf{5}}} & {\color{DarkOrange}{\textbf{6}}} \end{bmatrix}$, $\qquad B = \begin{bmatrix} {\color{Green}{\textbf{7}}} & 8 \\ {\color{Green}{\textbf{9}}} & 10 \\ {\color{Green}\textbf{11}} & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ {\color{DarkOrange}{\textbf{4}}} \cdot {\color{Green}{\textbf{7}}} + {\color{DarkOrange}{\textbf{5}}} \cdot {\color{Green}{\textbf{9}}} + {\color{DarkOrange}{\textbf{6}}} \cdot {\color{Green}\textbf{11}} & \phantom{4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12} \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ {\color{DarkOrange}{\textbf{4}}} & {\color{DarkOrange}{\textbf{5}}} & {\color{DarkOrange}{\textbf{6}}} \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & {\color{Green}{\textbf{8}}} \\ 9 & {\color{Green}\textbf{10}} \\ 11 & {\color{Green}\textbf{12}} \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11 & {\color{DarkOrange}{\textbf{4}}} \cdot {\color{Green}{\textbf{8}}} + {\color{DarkOrange}{\textbf{5}}} \cdot {\color{Green}\textbf{10}} + {\color{DarkOrange}{\textbf{6}}} \cdot {\color{Green}\textbf{12}} \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11 & 4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12 \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =}\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11 & 4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12 \end{bmatrix} =\\ \notag&=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =\\ \notag&\phantom{=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix}} \end{align}$$
Matrismultiplikation, exempel¶
$ A = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}$, $\qquad B = \begin{bmatrix} 7 & 8 \\ 9 & 10 \\ 11 & 12 \end{bmatrix} \qquad $
$$\begin{align} \notag A \times B \notag&= \begin{bmatrix} a_{1,*}\cdot b_{*,1} & a_{1,*}\cdot b_{*,2} \\ a_{2,*}\cdot b_{*,1} & a_{2,*}\cdot b_{*,2} \end{bmatrix} =\\ \notag&=\begin{bmatrix} 1 \cdot 7 + 2 \cdot 9 + 3 \cdot 11 & 1 \cdot 8 + 2 \cdot 10 + 3 \cdot 12 \\ 4 \cdot 7 + 5 \cdot 9 + 6 \cdot 11 & 4 \cdot 8 + 5 \cdot 10 + 6 \cdot 12 \end{bmatrix} =\\ \notag&=\begin{bmatrix} 7 + 18 + 33 & 8 + 20 + 36 \\ 28 + 45 + 66 & 32 + 50 + 72 \end{bmatrix} =\\ \notag&=\begin{bmatrix} 58 & 64 \\ 139 & 154 \end{bmatrix} \end{align}$$
Antal vägar av längden 1¶
- Följande vägar av längden 1 finns i $G$
- 1 väg från $a$ till $b$
- 1 väg från $a$ till $c$
- 1 väg från $a$ till $d$
- 1 väg från $b$ till $c$
- 1 väg från $c$ till $d$
- 1 väg från $d$ till $c$
$$ A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$
Antal vägar av längden 2¶
- Följande vägar av längden 2 finns i $G$
- 2 vägar från $a$ till $c$
- 1 väg från $a$ till $d$
- 1 väg från $b$ till $d$
- 1 väg från $c$ till $c$
- 1 väg från $d$ till $d$
$$A^2 = A \times A = \begin{bmatrix} 0 & 0 & 2 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} $$
Antal vägar av längden 3¶
- Följande vägar av längden 3 finns i $G$
- 1 väg från $a$ till $c$
- 2 vägar från $a$ till $d$
- 1 väg från $b$ till $c$
- 1 väg från $c$ till $d$
- 1 väg från $d$ till $c$
$$A^3 = A \times A \times A = \begin{bmatrix} 0 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{bmatrix} $$
Andra tillämpningar av matriser¶
Matriser är ett effektivt sätt att lösa linjära ekvationssystem, det innebär att nästan allting inom naturvetenskapen och de kvantitativa delarna av humanvetenskaperna bygger på matrisalgebra, t.ex.
- Statistik, där de flesta metoder bygger just på att lösa linjära ekvationssystem.
- Kurserna 729G48 Forskningsmetodik och statistik och 729G88 Kvasiexperiment och statistisk analys brukar inte fokusera på den underliggande matematiken men ni kan lita på att det är matriser under ytan.
- Artificiell intelligens, speciellt maskininlärning, som ofta kan formuleras som tillämpad statistik.
- Se också: https://www.youtube.com/watch?v=rowWM-MijXU
Dela upp problem¶
Matrismultiplikation¶
- Multiplicera matriserna $A$ och $B$ med varandra (där $A$ har lika
många rader som $B$ har kolumner)
- För att räkna ut element på plats $i,j$ i produktmatrisen räknar vi skalärprodukten av rad $i$ från $A$ och kolumn $j$ från $B$.
- Delproblem 1: ta fram rad från en matris
- Delproblem 2: ta fram kolumn från en matris
- Delproblem 3: räkna ut skalärprodukt av två vektorer
Parprogrammering¶
- Programmeringsmetod där två programmerare programmerar tillsammans i samma stycke kod samtidigt.
- Populariserades genom utvecklingsmetodiken Extreme Programming (XP).
- Vanligt speciellt inom organisationer som jobbar med sk. agila utvecklingsmetodiker.
- XP, Scrum, Kanban, etc.
Varför parprogrammering?¶
- Fördelar:
- Enskilda uppgifter slutförs snabbare än av en enskild programmerare.
- Resulterar i mindre komplex kod som är enklare att underhålla.
- Speciellt svåra problem där lösningen inte är given från start löses bättre av par.
- Lagom jämna par lär sig av varandra och utvecklas snabbare.
- Nackdelar:
- Kostar fler programmerartimmar för att slutföra projekt.
- $\;\;\;\;\rightarrow$ Mindre tid över till testning och debuggning givet samma mängd utvecklare.
- Par av noviser skriver sällan produktionsvärdig kod.
Parprogrammering i undervisning¶
- Diskutera och bestäm er för vilket litet delproblem som ska göras
- Föraren jobbar på det lilla delproblemet och skriver koden
- Navigatörens jobb är att aktivt granska koden som skrivs
- Navigatörens jobb är inte att berätta för föraren exakt vad hen ska skriva, men kan komma med förslag
- Byt roller ofta! Minst en gång varje halvtimme men helst oftare, använd timer om ni tenderar att glömma.
- Ni behöver inte lösa delproblemet innan ni byter roller.
- Fira när ni löst delproblem.
Tre faser och mönster¶
- Planering: innan ni kör iväg
- Kodproduktion: när koden skrivs
- Omstart: när ni har kört fast
Planering¶
- Både förslag och genomgång av existerande kod / instruktioner
- Det är bra att säga "Jag förstår inte" eller "Jag vet inte"
- Tveka inte om att be varandra förtydliga (om ni är oeniga, fråga assistent)
- Uttryck med egna ord hur du uppfattar situationen
- Undvik fraser som "du får se om en stund", försök att förklara för din partner på en gång
- Anteckna så att ni kommer ihåg det ni kommer fram till
Kodproduktion¶
- Föraren
- berätta hur och vad du tänker
- du kan stanna upp och prata med/fråga navigatören
- undvik att bara sitta tyst och vara i din egna värld (soloprogrammering med åskådare)
- Navigatören läser koden som skrivs och säger till direkt när hen
- upptäcker enklare fel
- inte förstår vad föraren gör, namngivning, etc
Kodproduktion¶
- Navigatören antecknar och sparar större funderingar till senare, t.ex.
- potentiella buggar (t.ex. värden som kan resultera i en krasch)
- funderingar idéer på övergripande design
- saker som ni missat vid planeringen
- Det är OK att skicka tangentbordet mellan er
- vissa saker kan vara lättare för navigatören att uttrycka i kod
- byt roller om det känns bra att göra det men kom ihåg att balansera
Omstart¶
- Ni kan byta fokus och prata om annat en kort stund för att kunna tackla problemet med öppen inställning
- Gå igenom er kod se över det ni gjort
- Försök ha målet i sikte medan ni identifierar hur ni ska göra för att komma vidare
- Hitta lämpligt ställe att börja om på
- Om ni inte kommer överrens, kan det vara lämpligt att ta en kort paus, gå på toa/fika etc, lämna arbetsplatsen
- Ge varandra tid att tänka/gå igenom koden
Varning¶
- Få par är perfekt matchade.
- Om du är den, åtminstone just nu, svagare programmeraren, lämna inte över ansvaret på din partner
- Om du är den, åtminstone just nu, starkare programmeraren, kör inte över din partner
- Glöm inte att byta roller!
Vad gör vi om det inte fungerar att parprogrammera?¶
- Gör uppgifterna enskilt.
- När båda är klara: Byt kod med varandra och granska.
- Diskutera eventuella skillnader.
- Sätt ihop en gemensam slutgiltig version som båda förstår.
- Redovisa gemensam version.
- Skicka in gemensam version i Sendlab.
Parprogrammering¶
- Programmeringsmetod där två programmerare sitter vid samma dator och programmerar
- Extreme Programming (XP), Kent Beck sent 90-tal
- I industrin
- En person, föraren (driver) skriver kod för den valda uppgiften
- Den andra personen, observatören/navigatören (observer/navigator) granskar koden; funderar på övergripande design
- Byt roll ofta!
- Studier har visat att
- designbeslut från par blir bättre jämfört med ensamma programmerare
- kod från par blir enklare (mindre komplicerad) jämfört med ensamma programmerare
Parprogrammering i undervisning¶
Diskutera och bestäm er för vilket litet delproblem som ska göras
Föraren jobbar på det lilla delproblemet och skriver koden
Navigatörens jobb är att aktivt granska koden som skrivs
Navigatörens jobb är inte att berätta för föraren exakt vad hen ska skriva, men kan komma med förslag
Byt roller ofta! Minst en gång varje halvtimme.
Ni behöver inte lösa delproblemet innan ni byter roller
Fira när ni löst delproblem
Tre faser och mönster¶
- Planering: innan ni kör iväg
- Kodproduktion: när koden skrivs
- Omstart: när ni har kört fast
Planering¶
- Både förslag och genomgång av existerande kod / instruktioner
- Det är OK att säga "Jag förstår inte" eller "Jag vet inte"
- Tveka inte om att be varandra förtydliga
- Uttryck med egna ord hur du uppfattar situationen
- Undvik fraser som "du får se om en stund", försök att förklara för din partner på en gång
- Anteckna så att ni sparar det ni kommer fram till
Kodproduktion¶
- Föraren
- berätta hur och vad du tänker
- du kan stanna upp och prata med/fråga navigatören
- undviker att bara sitta tyst och vara i sin egen värld
- Navigatören läser koden som skrivs och säger till direkt när hen
- upptäcker enklare fel
- inte förstår vad föraren gör, namngivning etc
- Navigatören antecknar och sparar större funderingar till senare, t.ex.
- potentiella buggar (t.ex. värden som kan resultera i en krasch)
- funderingar idéer på övergripande design
- saker som ni missat vid planeringen
- Det är OK att skicka tangentbordet mellan er
- vissa saker kan vara lättare att uttrycka i kod för navigatören
- byt roller om det känns bra att göra det
Omstart¶
- Ni kan byta fokus och prata om annat en kort stund för att kunna tackla problemet med öppen inställning
- Gå igenom er kod se över det ni gjort
- Försök ha målet i sikte medan ni identifierar hur ni ska göra för att komma vidare
- Hitta lämpligt ställe att börja om på
- Om ni inte kommer överrens, kan det vara lämpligt att ta en kort paus, gå på toa/fika etc, lämna arbetsplatsen
- Ge varandra tid att tänka/gå igenom koden