Theorie hoofdstuk 2

Matrices

• Een matrix $A$ van grootte $m \times n$ is een tabel met getallen met $m$ rijen en $n$ kolommen.
• De elementen van de matrix worden aangeduid met $a_{ij}$, waarbij $i$ de rij-index en $j$ de kolom-index is.
• Een vierkante matrix heeft hetzelfde aantal rijen en kolommen ($m = n$).
• Een kolommatrix heeft één kolom ($n = 1$).
• Een rijmatrix heeft één rij ($m = 1$).

Matrixbewerkingen

• Optellen en aftrekken: Matrices van dezelfde grootte kunnen worden opgeteld of afgetrokken door de overeenkomstige elementen op te tellen of af te trekken.
• Vermenigvuldiging met een scalaire waarde: Een matrix vermenigvuldigen met een scalaire waarde betekent elk element van de matrix met deze scalaire waarde vermenigvuldigen.
• Matrixvermenigvuldiging: Het product van twee matrices $A$ ($m \times n$) en $B$ ($n \times p$) is een matrix $C$ ($m \times p$) waarvan de elementen zijn gedefinieerd door: $c_{ij} = \sum_{k=1}^{n} a_{ik}b_{kj}$
• Transponeren: De getransponeerde $A^T$ van een matrix $A$ wordt verkregen door de rijen en kolommen van $A$ te verwisselen.

Speciale Matrices

• Identiteitsmatrix: Een vierkante matrix met 1-en op de hoofddiagonaal en 0-en elders, aangeduid met $I$.
• Nulmatrix: Een matrix waarvan alle elementen nul zijn.
• Diagonaalmatrix: Een vierkante matrix waarvan alle elementen buiten de hoofddiagonaal nul zijn.
• Bovendriehoeksmatrix: Een vierkante matrix waarvan alle elementen onder de hoofddiagonaal nul zijn.
• Onderdriehoeksmatrix: Een vierkante matrix waarvan alle elementen boven de hoofddiagonaal nul zijn.
• Symmetrische matrix: Een vierkante matrix zodanig dat $A = A^T$.
• Antisymmetrische matrix: Een vierkante matrix zodanig dat $A = -A^T$.

Stelsels Lineaire Vergelijkingen

• Een stelsel lineaire vergelijkingen is een verzameling lineaire vergelijkingen met dezelfde variabelen.
• Een stelsel lineaire vergelijkingen kan worden geschreven in matrixvorm als $Ax = b$, waarbij $A$ de coëfficiëntenmatrix is, $x$ de vector van variabelen is en $b$ de vector van constanten is.
• Een stelsel lineaire vergelijkingen kan een unieke oplossing, een oneindig aantal oplossingen of geen oplossing hebben.

Oplossingsmethoden

• Gauss-eliminatie: Een methode om stelsels lineaire vergelijkingen op te lossen door de uitgebreide matrix $[A | b]$ om te zetten in een gereduceerde echelonmatrix.
• Substitutie: Een methode om stelsels lineaire vergelijkingen op te lossen door bepaalde variabelen uit te drukken in termen van de andere variabelen.
• Regel van Cramer: Een methode om stelsels lineaire vergelijkingen op te lossen met behulp van determinanten.
• Matrixinversie: Als de matrix $A$ inverteerbaar is, wordt de oplossing van het stelsel $Ax = b$ gegeven door $x = A^{-1}b$.

Determinanten

• De determinant van een vierkante matrix $A$, aangeduid als $\det(A)$ of $|A|$, is een scalaire waarde die kan worden berekend op basis van de elementen van de matrix.
• De determinant van een $2 \times 2$ matrix wordt gegeven door: $\det \begin{pmatrix} a &b \ c & d \end{pmatrix} = ad - bc$
• De determinant van een $3 \times 3$ matrix kan worden berekend met behulp van de regel van Sarrus of de ontwikkeling van Laplace.

Eigenschappen van Determinanten

• Als een matrix een rij of kolom met nullen heeft, is de determinant ervan nul.
• Als twee rijen of twee kolommen van een matrix identiek zijn, is de determinant ervan nul.
• Als een rij of een kolom van een matrix wordt vermenigvuldigd met een scalaire waarde, wordt de determinant ervan vermenigvuldigd met die scalaire waarde.
• Als twee rijen of twee kolommen van een matrix worden omgewisseld, verandert de determinant ervan van teken.
• De determinant van het product van twee matrices is gelijk aan het product van hun determinanten: $\det(AB) = \det(A) \det(B)$.
• De determinant van de getransponeerde van een matrix is gelijk aan de determinant van de matrix: $\det(A^T) = \det(A)$.

Vectorruimten

• Een vectorruimte is een verzameling objecten, vectoren genoemd, waarop twee bewerkingen zijn gedefinieerd: vectoroptelling en vermenigvuldiging met een scalaire waarde.
• Een deelruimte is een deelverzameling van een vectorruimte die zelf een vectorruimte is.
• Een lineaire combinatie van vectoren is een uitdrukking van de vorm $c_1v_1 + c_2v_2 +... + c_nv_n$, waarbij $c_1, c_2,..., c_n$ scalaire waarden zijn en $v_1, v_2,..., v_n$ vectoren zijn.
• De lineaire omhulling van een verzameling vectoren is de verzameling van alle mogelijke lineaire combinaties van deze vectoren.
• Een verzameling vectoren is lineair onafhankelijk als geen niet-triviale lineaire combinatie van deze vectoren gelijk is aan de nulvector.
• Een basis van een vectorruimte is een verzameling lineair onafhankelijke vectoren die de vectorruimte opspannen.
• De dimensie van een vectorruimte is het aantal vectoren in een basis van deze vectorruimte.

Lineaire Afbeeldingen

• Een lineaire afbeelding is een functie tussen twee vectorruimten die de optelling en scalaire vermenigvuldiging bewerkingen behoudt.

Eigenwaarden en Eigenvectoren

• Een eigenvector van een vierkante matrix $A$ is een niet-nul vector $v$ zodat $Av = \lambda v$, waarbij $\lambda$ een scalaire waarde is die eigenwaarde wordt genoemd.
• De karakteristieke vergelijking van een matrix $A$ wordt gegeven door $\det(A - \lambda I) = 0$, waarbij $I$ de identiteitsmatrix is.
• De eigenwaarden van een matrix zijn de wortels van zijn karakteristieke vergelijking.
• De eigenruimte geassocieerd met een eigenwaarde $\lambda$ is de verzameling van alle eigenvectoren geassocieerd met $\lambda$, samen met de nulvector.

Eigenschappen van Eigenwaarden en Eigenvectoren

• Eigenvectoren die geassocieerd zijn met verschillende eigenwaarden zijn lineair onafhankelijk.
• Een matrix is diagonaliseerbaar als deze een basis van eigenvectoren heeft.

Matrices

• Een matrix is een rechthoekige tabel met getallen of symbolen.
• Bijvoorbeeld: $A = \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \end{bmatrix}$, $B = \begin{bmatrix} 1 & 2 \ 3 & 4 \ 5 & 6 \end{bmatrix}$, $C = \begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix}$

Matrix Bewerkingen

• Optellen: Als A en B $m \times n$ matrices zijn, dan is $A + B$ ook een $m \times n$ matrix waarbij overeenkomstige elementen worden opgeteld: $(A + B){ij} = A{ij} + B_{ij}$
• Vermenigvuldigen: Als A een $m \times n$ matrix is en B een $n \times p$ matrix, dan is AB een $m \times p$ matrix waarbij: $(AB){ij} = \sum{k=1}^{n} A_{ik} B_{kj}$
• Transponeren: Als A een $m \times n$ matrix is, dan is de getransponeerde van A, aangeduid als $A^T$, een $n \times m$ matrix waarbij rijen kolommen worden en kolommen rijen: $(A^T){ij} = A{ji}$
• Identiteitsmatrix: Een identiteitsmatrix, aangeduid als I, is een vierkante matrix met 1-en op de hoofddiagonaal en 0-en elders. Een voorbeeld van een $3 \times 3$ identiteitsmatrix: $I = \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \end{bmatrix}$
• Inverse: De inverse van een vierkante matrix A, aangeduid als $A^{-1}$, is een matrix zodanig dat: $AA^{-1} = A^{-1}A = I$, waarbij I de identiteitsmatrix is. Bijvoorbeeld: $A = \begin{bmatrix} a & b \ c & d \end{bmatrix}$, $A^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \ -c & a \end{bmatrix}$
• Determinant: De determinant van een vierkante matrix A, aangeduid als $|A|$ of det(A), is een scalaire waarde die kan worden berekend op basis van de elementen van een vierkante matrix. Voor een $2 \times 2$ matrix: $A = \begin{bmatrix} a & b \ c & d \end{bmatrix}$, $|A| = ad - bc$

Cosinusregel

• Voor elke $\triangle ABC$:
• $a^2 = b^2 + c^2 - 2bc\ cosA$
• $b^2 = a^2 + c^2 - 2ac\ cosB$
• $c^2 = a^2 + b^2 - 2ab\ cosC$
• Rekenmachine moet in gradenmodus staan.
• Bijvoorbeeld: Bij $a = 5,\ b = 8,\ \angle C = 77^\circ$ is $c = \sqrt{89 - 80\ cos(77^\circ)}$ en $c \approx 8.58$

Algoritmische Efficiëntie

• Bij het vergelijken van algoritmen wordt voornamelijk gefocust op twee belangrijke middelen: tijd en ruimte.
• Tijd is hoe lang het algoritme duurt om te draaien.
• Ruimte is hoeveel geheugen het algoritme gebruikt.
• Efficiëntie wordt meestal uitgedrukt als een functie van de invoergrootte (aangeduid met 'n').
• Big-O-notatie wordt gebruikt om de asymptotische bovengrens van de groeisnelheid van een algoritme te beschrijven.
• Big-O-notatie biedt een bovengrens voor de groeisnelheid van een algoritme, waarbij constante factoren en termen van lagere orde worden genegeerd.
• Het richt zich op de groei van de uitvoeringstijd of het ruimtegebruik als de invoergrootte toeneemt.

Algemene Groeisnelheden (van beste naar slechtste)

Belangrijke Punten Over Big-O

• Negeert Constanten: O(2n) is hetzelfde als O(n).
• Dominante Term: O(n^2 + n) wordt vereenvoudigd tot O(n^2).
• Slechtst Denkbare Scenario: Big-O staat typisch voor het slechtst mogelijke geval.

Voorbeelden

• O(1) Constante Tijd: Deze functie kost dezelfde hoeveelheid tijd, ongeacht de arraygrootte.

  int getFirstElement(int[] array) {
      return array;
  }
  

• O(n) Lineaire Tijd: De uitvoeringstijd groeit lineair met de grootte van de array.

  int findElement(int[] array, int target) {
      for (int i = 0; i < array.length; i++) {
          if (array[i] == target) {
              return i; // index van het element
          }
      }
      return -1; // niet gevonden
  }
  

• O(n^2) Kwadratische Tijd: Geneste lussen zorgen ervoor dat de uitvoeringstijd kwadratisch groeit met de grootte van de array.

  void printPairs(int[] array) {
      for (int i = 0; i < array.length; i++) {
          for (int j = 0; j < array.length; j++) {
              System.out.println(array[i] + "," + array[j]);
          }
      }
  }
  

Ruimtelijke Complexiteit

• Ruimtelijke complexiteit verwijst naar de hoeveelheid geheugen die een algoritme gebruikt in verhouding tot de invoergrootte.
• Het wordt ook uitgedrukt met behulp van Big-O-notatie.
• O(1): Een algoritme gebruikt een constante hoeveelheid geheugen, ongeacht de invoergrootte.
• O(n): Het geheugengebruik van een algoritme groeit lineair met de invoergrootte.
• O(n^2): Het geheugengebruik van een algoritme groeit kwadratisch met de invoergrootte.

Praktische Implicaties

• Het begrijpen van algoritmische efficiëntie is essentieel voor het kiezen van het juiste algoritme, het optimaliseren van code en het voorspellen van prestaties.
• Het selecteren van een efficiënt algoritme kan de prestaties aanzienlijk beïnvloeden, vooral bij grote datasets.
• Het identificeren en elimineren van inefficiënties kan leiden tot snellere en energie-efficiëntere programma's.
• Met Big-O-notatie kunt u schatten hoe een algoritme presteert naarmate de invoergrootte groeit.