Ruimtelijke Vectoren: Definities

Ruimtelijke Vectoren

Definitites

Definitie 1.1: Veld

• Een veld is een set $\mathbb{K}$ met twee interne operaties: optellen ($+$) en vermenigvuldigen ($\cdot$).
• $(\mathbb{K},+)$ is een Abeliaanse groep:
  • Associativiteit: $(a+b)+c = a+(b+c)$ voor alle $a,b,c \in \mathbb{K}$
  • Commutativiteit: $a+b = b+a$ voor alle $a,b \in \mathbb{K}$
  • Neutraal element: Er bestaat een $0 \in \mathbb{K}$ zodat $a+0 = a$ voor alle $a \in \mathbb{K}$
  • Inverse element: Voor elke $a \in \mathbb{K}$ bestaat er een $-a \in \mathbb{K}$ zodat $a+(-a) = 0$
• $(\mathbb{K}\setminus{0},\cdot)$ is een Abeliaanse groep:
  • Associativiteit: $(a\cdot b)\cdot c = a\cdot (b\cdot c)$ voor alle $a,b,c \in \mathbb{K}$
  • Commutativiteit: $a\cdot b = b\cdot a$ voor alle $a,b \in \mathbb{K}$
  • Neutraal element: Er bestaat een $1 \in \mathbb{K}$ zodat $a\cdot 1 = a$ voor alle $a \in \mathbb{K}$
  • Inverse element: Voor elke $a \in \mathbb{K}\setminus{0}$ bestaat er een $a^{-1} \in \mathbb{K}$ zodat $a\cdot a^{-1} = 1$
• Distributiviteit:
  • $a\cdot (b+c) = a\cdot b + a\cdot c$ voor alle $a,b,c \in \mathbb{K}$

Voorbeelden

• Voorbeelden van velden zijn: $\mathbb{Q, R, C}$.
• Voorbeelden van sets die geen velden zijn: $\mathbb{Z, N}$.

Definitie 1.2: Vectorenruimte

• Een vectorenruimte over een veld $\mathbb{K}$ is een set $E$ met twee operaties:
• Optellen: $+: E \times E \rightarrow E$.
  • Associativiteit: $(u+v)+w = u+(v+w)$ voor alle $u,v,w \in E$
  • Commutativiteit: $u+v = v+u$ voor alle $u,v \in E$
  • Neutraal element: Er bestaat een $0 \in E$ zodat $u+0 = u$ voor alle $u \in E$
  • Inverse element: Voor elke $u \in E$ bestaat er een $-u \in E$ zodat $u+(-u) = 0$
• Vermenigvuldigen met een scalair: $\cdot : \mathbb{K} \times E \rightarrow E$.
  • Gemengde associativiteit: $a\cdot (b\cdot u) = (a\cdot b)\cdot u$ voor alle $a,b \in \mathbb{K}$ en $u \in E$
  • Distributiviteit t.o.v. optellen van scalairen: $(a+b)\cdot u = a\cdot u + b\cdot u$ voor alle $a,b \in \mathbb{K}$ en $u \in E$
  • Distributiviteit t.o.v. optellen van vectoren: $a\cdot (u+v) = a\cdot u + a\cdot v$ voor alle $a \in \mathbb{K}$ en $u,v \in E$
  • Neutraal element: Er bestaat een $1 \in \mathbb{K}$ zodat $1\cdot u = u$ voor alle $u \in E$
• Elementen van $E$ heten vectoren.

De Vectorenruimte $F^n$

Definitie

• Zij $F$ een veld en $n$ een positief geheel getal. Een vector in $F^n$ is een geordende n-tupel $(a_1, a_2,..., a_n)$.
• Elke $a_i \in F$.

Definitie

• Laat $u = (a_1, a_2,..., a_n) \in F^n$ en $v = (b_1, b_2,..., b_n) \in F^n$.
• De som van u en v wordt gedefinieerd als: $u + v = (a_1 + b_1, a_2 + b_2,..., a_n + b_n)$.

Definitie

• Laat $u = (a_1, a_2,..., a_n) \in F^n$ en $c \in F$.
• De scalaire vermenigvuldiging cu wordt gedefinieerd als: $cu = (ca_1, ca_2,..., ca_n)$.

Stelling

• Zij $F$ een veld en n een positief geheel getal. Dan is $(F^n, +, \cdot)$ een vectorenruimte over $F$.
• Dit wordt bewezen door de axioma's van een vectorenruimte stap voor stap te controleren.

Voorbeelden

• Rekenvoorbeelden in $\mathbb{R}^3$, $\mathbb{C}^2$ en $\mathbb{Z}_2^3$ illusteren optellen en scalaire vermenigvuldiging.

De Vectorenruimte $M_{m \times n}(F)$

Definitie

• Laat $F$ een veld zijn en $m$ en $n$ positieve gehele getallen. Een $m \times n$ matrix is een rechthoekige array:
  • $\begin{bmatrix} a_{11} & a_{12} &... & a_{1n}\ a_{21} & a_{22} &... & a_{2n}\ \vdots & \vdots & \ddots & \vdots\ a_{m1} & a_{m2} &... & a_{mn} \end{bmatrix}$
• Elke $a_{ij} \in F$.

Definitie

• Laat $A = [a_{ij}]$ en $B = [b_{ij}]$ matrices in $M_{m \times n}(F)$ zijn.
• De som van A en B wordt gedefinieerd als: $A + B = [a_{ij} + b_{ij}]$.

Definitie

• Laat $A = [a_{ij}] \in M_{m \times n}(F)$ en $c \in F$.
• De scalaire vermenigvuldiging $cA$ wordt gedefinieerd als: $cA = [ca_{ij}]$.

Stelling

• Laat $F$ een veld zijn en $m$ en $n$ positieve gehele getallen. Dan is $(M_{m \times n}(F), +, \cdot)$ een vectorenruimte over $F$.

De Vectorenruimte $P(F)$

Definitie

• Laat $F$ een veld zijn.
• Een polynoom in $x$ met coëfficiënten uit $F$ is: $f(x) = a_n x^n + a_{n-1}x^{n-1} +... + a_1x + a_0$.
• Elke $a_i \in F$ en $n$ is een niet-negatief geheel getal.
• Als $f(x) = 0$, dan is $f(x)$ het nulpolynoom.

Definitie

• Laat $f(x) = a_n x^n + a_{n-1}x^{n-1} +... + a_1x + a_0$ en $g(x) = b_m x^m + b_{m-1}x^{m-1} +... + b_1x + b_0$ polynomen in $F[x]$ zijn.
• De som van $f(x)$ en $g(x)$ wordt gedefinieerd als: $f(x) + g(x) = (a_k + b_k)x^k + (a_{k-1} + b_{k-1})x^{k-1} +... + (a_1 + b_1)x + (a_0 + b_0)$.
• $k = max(m, n)$, en $a_i = 0$ voor $i > n$ en $b_i = 0$ voor $i > m$.

Definitie

• Laat $f(x) = a_n x^n + a_{n-1}x^{n-1} +... + a_1x + a_0$ een polynoom in $F[x]$ zijn en $c \in F$.
• De scalaire vermenigvuldiging $cf(x)$ wordt gedefinieerd als: $cf(x) = ca_n x^n + ca_{n-1}x^{n-1} +... + ca_1x + ca_0$.

Definitie

• Laat $P(F)$ de verzameling van alle polynomen in $x$ met coëfficiënten uit $F$ zijn.

Stelling

• Laat $F$ een veld zijn. Dan is $(P(F), +, \cdot)$ een vectorenruimte over $F$.

De Vectorenruimte $F^S$

Definitie

• Laat $F$ een veld zijn en $S$ een niet-lege verzameling. De set van alle functies van $S$ naar $F$ wordt aangeduid met $F^S$.

Definitie

• Laat $f, g \in F^S$.
• De som van $f$ en $g$ wordt gedefinieerd als: $(f + g)(s) = f(s) + g(s)$ voor alle $s \in S$.

Definitie

• Laat $f \in F^S$ en $c \in F$.
• De scalaire vermenigvuldiging $cf$ wordt gedefinieerd als: $(cf)(s) = cf(s)$ voor alle $s \in S$.

Stelling

• Laat $F$ een veld zijn en $S$ een niet-lege verzameling. Dan is $(F^S, +, \cdot)$ een vectorenruimte over $F$.

Voorbeeld 4

• Voorbeeld met $S = {1, 2}$ and $F = \mathbb{R}$ illustreert $f, g \in \mathbb{R}^S$ door $f(1) = 1, f(2) = -2, g(1) = 2$, en $g(2) = 3$.

Subruimtes

Definitie

• Laat $V$ een vectorenruimte over $F$ zijn. Een deelverzameling $W$ van $V$ heet een subruimte van $V$ als $W$ een vectorenruimte over $F$ is met de bewerkingen van optelling en scalaire vermenigvuldiging gedefinieerd op $V$.

Stelling

• Laat $V$ een vectorenruimte over $F$ zijn en $W$ een niet-lege deelverzameling van $V$. Dan is $W$ een subruimte van $V$ als en alleen als de volgende twee voorwaarden gelden:
  1. $x + y \in W$ voor alle $x, y \in W$.
  2. $cx \in W$ voor alle $c \in F$ en $x \in W$.
• Het bewijs toont de subruimte-eigenschappen aan.

Gevolgtrekking

• Laat $V$ een vectorenruimte over $F$ zijn en $W$ een niet-lege deelverzameling van $V$. Dan is $W$ een subruimte van $V$ als en alleen als $ax + y \in W$ voor alle $a \in F$ en $x, y \in W$.
• Het bewijs laat zien dat de voorwaarde equivalent is aan de 2 vereiste eigenschappen.

Voorbeeld 5

• Laat $V$ een vectorenruimte over $F$ zijn. Dan zijn ${0}$ en $V$ subruimtes van $V$.

Voorbeeld 6

• Laat $F$ een veld zijn en n een positief geheel getal. Definieer $W = {(a_1, a_2,..., a_n) \in F^n: a_1 + a_2 +... + a_n = 0}$. Dan is $W$ een subruimte van $F^n$.
• Het bewijs verifieert de subruimte-eigenschappen.

Voorbeeld 7

• Laat $F$ een veld zijn en $n$ een positief geheel getal. Definieer $W = {(a_1, a_2,..., a_n) \in F^n: a_1 = 1}$. Dan is $W$ geen subruimte van $F^n$.
• Het bewijs laat zien dat de verzameling de nulvector niet bevat.

Voorbeeld 8

• Laat $F$ een veld en $V$ een vectorenruimte over $F$ zijn. Laat $x \in V$. Definieer $W = {ax: a \in F}$. Dan is $W$ een subruimte van $V$.
• Het bewijs laat zien dat de verzameling non-leeg is en voldoet aan de subruimte-eis.

Definitie

• Laat $V$ een vectorenruimte over $F$ en $S$ een deelverzameling van $V$ zijn. De span van $S$, aangeduid met span($S$), is de verzameling van alle lineaire combinaties van vectoren in $S$.
  • $span(S) = {a_1x_1 + a_2x_2 +... + a_nx_n: a_i \in F, x_i \in S, n \in \mathbb{N}}$.
• In andere woorden, de span van $S$ is de verzameling van alle vectoren die geschreven kunnen worden als een lineaire combinatie van vectoren in $S$.
• Als $S = \emptyset$, definiëren we span($S$) = {0}.

Stelling

• Laat $V$ een vectorenruimte over $F$ en $S$ een deelverzameling van $V$ zijn. Dan is span($S$) een subruimte van $V$.
• Het bewijs laat zien dat span($S$) non-leeg is en voldoet aan de subruimte-eis.

Stelling

• Laat $V$ een vectorenruimte over $F$ en $S$ een deelverzameling van $V$ zijn. Dan is span($S$) de kleinste subruimte van $V$ die $S$ bevat.
• Dat wil zeggen, als $W$ een subruimte van $V$ is die $S$ bevat, dan span($S$) $\subseteq W$.
• Het bewijs laat zien dat lineaire combinaties van $S$ altijd in W zitten.

Definitie

• Laat $V$ een vectorenruimte over $F$ en $S$ een deelverzameling van $V$ zijn. We zeggen dat $S$, $V$ spant als span($S$) = $V$.

Voorbeld 9

• Laat $F$ een veld zijn. Dan wordt $F^n$ gespannen door ${(1, 0,..., 0), (0, 1,..., 0),..., (0, 0,..., 1)}$.
• Bewijs dat lineaire combinaties de hele ruimte dekken.

Voorbeld 10

• Laat $P(F)$ de vectorenruimte van alle polynomen in $x$ met coëfficiënten uit $F$ zijn. Dan wordt $P(F)$ gespannen door ${1, x, x^2,...}$.
• Bewijs dat lineaire combinaties de hele ruimte dekken.

Algoritmische Complexiteit en Speltheorie

Wat is Algoritmische Complexiteit?

• Algoritmes zijn tijd- en ruimte- complex.
• De mate van tijds- en geheugengebruik (time complexity) en de mate van aanwendde geheug (space complexity) groeien als het formaat van de invoer van een algoritme groeit.
• Efficiëntie van een algoritme.
• Big-O notatie.

Waarom is het belangrijk?

• De efficiëntie van een algoritme is te herleiden uit de efficiëntie.
• Het vergelijken van algoritmen voor een taak.
• Bespreken van de prestatiekenmerken van code.

Vastellen complexiteit

• Bepaal wat "één stap" is voor het algoritme.
• Druk het aantal stappen uit als functie van het format van de invoer.
• Vereenvoudig de functie.
  • $12n \rightarrow n$
  • $n^2 + n \rightarrow n^2$
  • $2^n + n^5 \rightarrow 2^n$

Gemeenschappelijke complexiteiten

• Constante, Logaritmisch, Lineair, Lineairithmisch, kwadratisch, exponentieel, factorieel.

Voorbeelden

• Voorbeelden van verschillende tijdcomplexiteiten met bijbehorende python code.
• Constante tijdscomplexiteit - $O(1)$
• Lineaire tijdscomplexiteit - $O(n)$
• Kwadratische tijdscomplexiteit - $O(n^2)$

Algoritmische Speltheorie

Game Theory (Speltheorie)

• Een manier om instellingen te bestuderen waar meerdere deelnemers elk verschillende voorkeuren / doelen hebben
• Een "spel" heeft een specifieke definitie:
  • Regels van ontmoeting
  • Specificatie van uitbetalingen
  • Spelers handelen strategisch

Voorbeelden

• Veilingen, netwerkroutings, gesponsorde zoekopdrachten

Zelfzuchtige Routing

• Grafiek $G = (V, E)$
• $r$-spelers
• Elke speler wil van s_i naar t_i
• $x_e$-spelers kiezen edge $e$
• $l_e(x_e)$-latentie op edge $e$
• Kosten voor speler i is de som van de latentiev op het pad

Nash-Equilibrium

• De flow in Nash-Equilibrium is als geen speler zijn kosten kan verbeteren door zijn pad te veranderen.
• Price of Anarchy
  • $\text{PoA} = \frac{\text{Cost of worst-case Nash Equilibrium}}{\text{Cost of optimal flow}}$
  • Het idee is om te begrijpen hoe "slecht" een Nash-Equilibrium kan zijn in vergelijking met een optimale flow.

Braess's Paradox

• Een manier voor extra middelen om de performance te verlagen.

Integralen

Symbolische Integratie

• Met het gebruik van verschillende programma's kan aan de hand van de formule en de grenzen bepaald worden wat de exacte waarde is.
  • Benader de oplossing
  • Zoek de goede substitutie
  • Evalueer aan de hand van de definitieve integraal
  • Check de waarde.

Expectation Maximization Algoritme

EM Algoritme voor GMMs

E-step evalueren