Dijkstran Algoritmi lyhyin polku

Dijkstran Algoritmi

Ongelmanasettelu

• Olkoon painotettu graafi $G = (V, E, w)$, jossa $w: E \rightarrow \mathbb{R}_{\geq 0}$ ja alkusolmu $s \in V$.
• Tavoitteena on löytää lyhyimmät polut solmusta $s$ kaikkiin muihin solmuihin $V$.
• Kaikkien kaarten painojen oletetaan olevan ei-negatiivisia.

Algoritmi

1. Alustus:
   • Asetetaan $\text{dist}[s] = 0$ ja $\text{dist}[v] = \infty$ kaikille $v \in V \setminus {s}$.
   • Asetetaan $Q = V$, eli kaikki solmut ovat aluksi prioriteettijonossa.
2. Iterointi:
   • Niin kauan kuin $Q \neq \emptyset$:
     • Etsitään $u \in Q$, jolla on pienin $\text{dist}[u]$.
     • Poistetaan $u$ joukosta $Q$.
     • Kaikille solmun $u$ naapureille $v$:
       • Jos $\text{dist}[v] > \text{dist}[u] + w(u, v)$:
         • Asetetaan $\text{dist}[v] = \text{dist}[u] + w(u, v)$.
         • Asetetaan $\text{prev}[v] = u$ (valinnainen, polun rekonstruointia varten).

Esimerkki

• Graafi sisältää solmut A, B, C, D, E ja F.

• Kaarten painot ovat seuraavat:

  • A-B: 4
  • A-C: 2
  • B-C: 1
  • B-D: 5
  • C-E: 8
  • C-F: 10
  • D-E: 2
  • D-F: 2
  • E-F: 3

• Alkusolmu on A.

• Taulukko esittää etäisyyksien kehittymistä A:sta muihin solmuihin algoritmin edetessä:

Selitys

• Alustus: Etäisyys A:han on 0, kaikki muut etäisyydet ovat äärettömiä.
• A: Etäisyydet B:hen ja C:hen päivitetään (4 ja 2).
• C: Etäisyydet E:hen ja F:ään päivitetään C:n kautta (10 ja 12). Etäisyys B:hen tarkistetaan, mutta se ei ole lyhyempi kuin nykyinen etäisyys.
• B: Etäisyys D:hen päivitetään (5).
• D: Etäisyydet E:hen ja F:ään päivitetään (7 ja 7).
• E: Etäisyys F:ään tarkistetaan ja tarvittaessa päivitetään (10, ei muutosta).
• F: Lisäpäivitykset eivät ole mahdollisia, koska kaikki solmut on jo käyty läpi.

Tulos

• Lyhyimmät etäisyydet A:sta muihin solmuihin ovat:
  • A: 0
  • B: 4
  • C: 2
  • D: 5
  • E: 7
  • F: 7

Luento 24: Hypoteesien Testaus

Tilastollinen Hypoteesi

• Tilastollinen hypoteesi on oletus populaation parametrista.
• Esimerkkejä ovat $\mu = 100$, $\sigma^2 = 15$, ja $p = 0.4$.

Hypoteesien Testaus

• Hypoteesien testauksessa lähdetään olettamasta, että hypoteesi on tosi.
• Selvitetään, kuinka todennäköistä on, että otostunnusluku poikkeaisi hypoteesista, jos oletus olisi tosi.

Nollahypoteesi

• Merkitään $H_0$.
• Testattava hypoteesi.
• Testataan nollahypoteesia yrittämällä löytää todisteita sen hylkäämiseksi.
• Aloitetaan olettamalla, että nollahypoteesi on tosi.
• $H_0$ sisältää aina yhtäläisyysmerkin.
  • Esimerkkejä: $H_0: \mu = 100$, $H_0: \mu \leq 100$, $H_0: \mu \geq 100$.

Vaihtoehtoinen Hypoteesi

• Merkitään $H_1$.
• Hypoteesi, joka on ristiriidassa nollahypoteesin kanssa.
• $H_1$ ei koskaan sisällä yhtäläisyysmerkkiä.
  • Esimerkkejä: $H_1: \mu \neq 100$, $H_1: \mu > 100$, $H_1: \mu < 100$.
• $H_0$ ja $H_1$ ovat toisensa poissulkevia ja yhdessä kattavia.

Menetelmä

1. Ilmoitetaan nollahypoteesi $H_0$.
2. Ilmoitetaan vaihtoehtoinen hypoteesi $H_1$.
3. Valitaan merkitsevyystaso $\alpha$.
4. Valitaan otos ja kerätään todisteita (otostunnuslukuja).
5. Etsitään kriittiset arvot (arvot, jotka määrittävät hylkäysalueen).
6. Etsitään testitunnusluku.
7. Tehdään tilastollinen päätös.
8. Tehdään johtopäätös.

Tyypin I Virhe

• Nollahypoteesin $H_0$ hylkääminen, kun se on tosi.
  • Tyypin I virheen todennäköisyyttä kutsutaan merkitsevyystasoksi, ja sitä merkitään $\alpha$.
  • $P(\text{Tyypin I virhe}) = P(\text{Hylätään } H_0 | H_0 \text{ on tosi}) = \alpha$.

Tyypin II Virhe

• Nollahypoteesin $H_0$ hyväksyminen, kun se on väärä.
  • Tyypin II virheen todennäköisyyttä merkitään $\beta$.
  • $P(\text{Tyypin II virhe}) = P(\text{Hyväksytään } H_0 | H_0 \text{ on väärä}) = \beta$.

Testin Voima

• Todennäköisyys hylätä nollahypoteesi $H_0$, kun se on väärä.
• Testin voimaa merkitään $1 - \beta$.
• $P(\text{Hylätään } H_0 | H_0 \text{ on väärä}) = 1 - \beta$.

Yhteenveto

• Päätöksen ja todellisen tilanteen välinen suhde:

P-Arvo

• Todennäköisyys havaita otostunnusluku, joka on yhtä äärimmäinen tai äärimmäisempi kuin otoksesta saatu tunnusluku, jos nollahypoteesi on tosi.

Lineaarialgebra

Perusmääritelmät

Vektoriavaruus

• Vektoriavaruus kunnan $\mathbb{K}$ yli (usein $\mathbb{R}$ tai $\mathbb{C}$) on joukko $E$, jossa on määritelty kaksi operaatiota:
  • Yhteenlasku: $E \times E \rightarrow E$, $(u, v) \mapsto u + v$
  • Skalaarikertolasku: $\mathbb{K} \times E \rightarrow E$, $(\lambda, u) \mapsto \lambda u$
• Noudatettavat aksioomat:
  • $(E, +)$ on Abelin ryhmä (kommutatiivinen).
  • $\forall \lambda, \mu \in \mathbb{K}, \forall u \in E$:
    • $\lambda(\mu u) = (\lambda \mu)u$
    • $(\lambda + \mu)u = \lambda u + \mu u$
    • $\lambda(u + v) = \lambda u + \lambda v$
    • $1u = u$

Aliavaruus

• Joukon $F$, joka on vektoriavaruuden $E$ osajoukko, on aliavaruus, jos:
  • $F$ ei ole tyhjä.
  • $\forall u, v \in F, u + v \in F$
  • $\forall \lambda \in \mathbb{K}, \forall u \in F, \lambda u \in F$

Virittävä Joukko

• Vektoreiden joukko $(v_1,..., v_n)$ virittää $E$:n, jos jokainen vektori $E$:ssä voidaan kirjoittaa lineaarisena kombinaationa näistä vektoreista.

Vapaa Joukko

• Vektoreiden joukko $(v_1,..., v_n)$ on vapaa (tai lineaarisesti riippumaton) $E$:ssä, jos ainoa lineaarinen kombinaatio näistä vektoreista, joka antaa nollavektorin, on sellainen, jossa kaikki kertoimet ovat nollia.

Kanta

• $E$:n kanta on vektoreiden joukko, joka on sekä vapaa että virittävä.
• Jokainen vektori $E$:ssä voidaan kirjoittaa yksiselitteisesti kertoimien lineaarisena kombinaationa kannan vektoreista.

Ulottuvuus

• Vektoriavaruuden $E$ ulottuvuus, merkitään $\dim(E)$, on vektoreiden lukumäärä $E$:n kannassa.
• Jos $E$:llä on äärellinen kanta, sanotaan, että $E$ on äärellisulotteinen.

Lineaarikuvaukset

Määritelmä

• Kuvaus $f : E \rightarrow F$ kahden vektoriavaruuden $E$ ja $F$ välillä samalla kunnalla $\mathbb{K}$ on lineaarinen, jos:
  • $\forall u, v \in E, f(u + v) = f(u) + f(v)$
  • $\forall \lambda \in \mathbb{K}, \forall u \in E, f(\lambda u) = \lambda f(u)$

Ydin ja Kuva

• $f$:n ydin, merkitään $\ker(f)$, on kaikkien $E$:n vektoreiden joukko, jotka kuvataan $F$:n nollavektoriksi:

  $\ker(f) = {u \in E \mid f(u) = 0_F}$

• $f$:n kuva, merkitään $\text{Im}(f)$, on kaikkien $F$:n vektoreiden joukko, jotka ovat vähintään yhden $E$:n vektorin kuvia:

  $\text{Im}(f) = {v \in F \mid \exists u \in E, f(u) = v}$

Dimensiolause

• Jos $E$ on äärellisulotteinen ja $f : E \rightarrow F$ on lineaarikuvaus, niin:

  $\dim(E) = \dim(\ker(f)) + \dim(\text{Im}(f))$

Isomorfismi

• Bijektiivinen lineaarikuvaus on isomorfismi.
• Jos $f : E \rightarrow F$ on isomorfismi, niin $E$ ja $F$ ovat isomorfisia, mikä tarkoittaa, että niillä on sama vektorirakenne.

Matriisit

Määritelmä

• Matriisi on lukutaulukko. $m \times n$-matriisissa on $m$ riviä, $n$ saraketta.
• Matriisin alkioita merkitään usein $a_{ij}$, jossa $i$ on rivin indeksi ja $j$ on sarakkeen indeksi.

Matriiseihin Kohdistuvat Operaatiot

• Yhteenlasku: Jos $A$ ja $B$ ovat samankokoisia $m \times n$-matriiseja, niiden summa $A + B$ on matriisi, jonka alkiot ovat $(A + B){ij} = A{ij} + B_{ij}$.
• Skalaarikertolasku: Jos $A$ on $m \times n$-matriisi ja $\lambda$ on skalaari, niin $\lambda A$ on matriisi, jonka alkiot ovat $(\lambda A){ij} = \lambda A{ij}$.
• Matriisikertolasku: Jos $A$ on $m \times n$-matriisi ja $B$ on $n \times p$-matriisi, tulo $AB$ on $m \times p$-matriisi, jonka alkiot ovat $(AB){ij} = \sum{k=1}^{n} A_{ik} B_{kj}$.

Käänteismatriisi

• Neliömatriisi $A$ on kääntyvä, jos on olemassa sellainen matriisi $B$, että $AB = BA = I$, jossa $I$ on identiteettimatriisi. Matriisia $B$ kutsutaan $A$:n käänteismatriisiksi ja merkitään $A^{-1}$.

Determinantti

• Determinantti on funktio, joka liittää skalaarin neliömatriisiin. Sitä merkitään $\det(A)$ tai $|A|$. Determinanttia käytetään sen määrittämiseen, onko matriisi kääntyvä ($\det(A) \neq 0$) ja matriisin käänteismatriisin laskemiseen.

Ominaisarvot ja Ominaisvektorit

• Neliömatriisin $A$ ominaisvektori on nollasta poikkeava vektori $v$ siten, että $Av = \lambda v$, jossa $\lambda$ on skalaari, jota kutsutaan ominaisarvoksi. Ominaisarvot ovat polynomin karakteristiset juuret, jotka määritellään $\det(A - \lambda I) = 0$.

Pistetulo ja Ortogonaalisuus

Pistetulo

• Pistetulo vektoriavaruudessa $E$ on kuvaus $\langle \cdot, \cdot \rangle : E \times E \rightarrow \mathbb{K}$, joka täyttää seuraavat ehdot:
  • $\langle u, v \rangle = \overline{\langle v, u \rangle}$ (konjugaattisymmetrinen)
  • $\langle u + v, w \rangle = \langle u, w \rangle + \langle v, w \rangle$ (lineaarisuus vasemmalla)
  • $\langle \lambda u, v \rangle = \lambda \langle u, v \rangle$
  • $\langle u, u \rangle \geq 0$, ja $\langle u, u \rangle = 0$ jos ja vain jos $u = 0$ (positiivisuus)

Ortogonaalisuus

• Kaksi vektoria $u$ ja $v$ ovat ortogonaalisia, jos $\langle u, v \rangle = 0$. Vektoreiden joukko on ortogonaalinen, jos kaikki joukon erilliset vektoriparit ovat ortogonaalisia. Ortogonaalinen nollasta poikkeavien vektoreiden joukko on lineaarisesti riippumaton.

Ortonormaalit Kannat

• Ortonormaali kanta on kanta, joka koostuu yksikkövektoreista (normi 1) ja jotka ovat ortogonaaliset toisiinsa. Ortonormaalit kannat yksinkertaistavat monia laskutoimituksia ja niitä käytetään monissa sovelluksissa.

Ortogonaalinen Projektio

• Vektorin $v$ ortogonaalinen projektio aliavaruuteen $F$ on vektori $w \in F$ siten, että $v - w$ on ortogonaalinen arvoon $F$. Jos $(e_1,..., e_n)$ on $F$:n ortonormaali kanta, niin $v$:n ortogonaalisen projektio arvoon $F$ on:

  $\text{proj}F(v) = \sum{i=1}^{n} \langle v, e_i \rangle e_i$

Bernoullin Periaate

• Bernoullin periaate toteaa, että nesteen nopeuden kasvu tapahtuu samanaikaisesti paineen alenemisen tai nesteen potentiaalienergian alenemisen kanssa.
• $\bf{P + \frac{1}{2} \rho V^2 + \rho gh = vakio}$

jossa:

$P$ = nesteen staattinen paine $\rho$ = nesteen tiheys $V$ = nesteen nopeus $h$ = nesteen korkeus

Venturi-Mittari

• Venturi-mittari on laite, jota käytetään putken läpi virtaavan nesteen nopeuden mittaamiseen.
• Paine-erojen mittaamisen avulla voidaan laskea nesteen nopeus sen liikkuessa putken läpi.
  • $A_1V_1 = A_2V_2$
  • $P_1 + \frac{1}{2} \rho V_1^2 = P_2 + \frac{1}{2} \rho V_2^2$
• Ratkaistaan $V_1$:n suhteen:

$V_1 = \sqrt{\frac{2(P_1 - P_2)}{\rho (\frac{A_1^2}{A_2^2} - 1)}}$

Nostovoima Siivellä

• Siipi on rakenne, jossa on kaarevat pinnat, jotka on suunniteltu saamaan reaktio ilmasta, jonka läpi se liikkuu.
• Koska siiven yläosan etäisyys on pidempi kuin siiven alaosan etäisyys, yläosan ilman on liikuttava nopeammin.
• Bernoullin periaatteen mukaan siiven yläosan paineen on oltava pienempi kuin siiven alaosan paine, mikä luo nostovoimaa.

Nostovoiman Yhtälö

$L = \frac{1}{2} \rho V^2 A C_L$

jossa:

$\rho$ = ilman tiheys $V$ = nopeus $A$ = siiven pinta-ala $C_L$ = nostovoimakerroin