Hej krigare,
Detta kommer att bli det sista seminariet som kommer hållas i Juli innan det drar igång igen i början av Augusti (mer precist den \(8/8\)). Med det sagt ska jag se till att ni får några roliga uppgifter att jobba på inför fredagen nästa vecka! Tanken är att det skall vara ett problem från varje kapitel :D.
Uppgift \(1\) (Kombinatorik + lite grafteori):
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ett flygplan flyger mellan n städer och har dessutom möjligheten att flyga fram och tillbaka mellan vilka två städer som helst. På hur många sätt kan flygplanet starta vid en stad, flyga till alla andra städer exakt en gång och sedan återvända?
Uppgift \(2\) (Algebra):
- - - - - - - - - - - - - - - - - - -
Antag att triangelolikheten är uppfylld för de reella talen \(x,y,z \in R\). Visa att \(x,y,z \geq 0\).
Uppgift \(3\) (Rekursion) - "Maximum Subarray":
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ni är givna en lista \(M\) med \(n\) heltal (kan vara positiva, negativa eller \(0\)). Antag att indexen \(i\) (med andra ord "positionerna") i listan satisfierar \(0 \leq i \leq n-1\) så att \(M[i]\) svarar mot heltalet på plats \(i\). T.ex. om \(M = [1,4, -3]\) så skulle \(M[0] = 1 , M[1] = 4 , M[2] =-3\). Vi betecknar \(M[i:j]\) som den del-lista vars element löper från index \(i\) till index \(j\) där \(j \geq i\). Låt nu \(DP[i]\) svara mot den maximala summan (summan av elementen i del-listan) som kan fås från någon del-lista som startar i index \(i\). T.ex. om vi återgår till exemplet med \(M =[1,4,-3]\) så skulle \(DP[0] = 5\). Därför att del-listan som startar i index \(0\) och slutar i index \(1\) ger den maximala summan utav alla del-listor som startar i index \(0\), och i detta fall blir summan \(1+4 = 5\). Låt till sist \(S\) motsvara den maximala del-listans (del-listan vars summa av element är maximal) summa. Visa att
a) \(DP[n-1] = M[n-1]\)
och annars (d.v.s. för \(i = n-2 , ..., 0\))
\(DP[i] = max(M[i] ,M[i]+DP[i+1])\)
b) \(S = max(DP[0], ..., DP[n-1])\)
För er som är förvirrade över vad \(S\) betyder, ger jag några exempel nedan
Ex1. \(M = [- 5, 10 ,15 ,20] \Rightarrow S = 45\) då del-listan \(M[1:3]\) ger en maximal summa av element.
Ex2. \(M = [-4 , 0, -1 ,-2 ,-3] \Rightarrow S = 0\) då del-listan \(M[1:1]\) ger en maximal summa av element.
Ex3. \(M = [-4 , 20 ,23, 175 , -40 , 400] \Rightarrow S = 578\) då del-listan \(M[1:5]\) ger en maximal summa av element.
OBS! Detta är ett klassiskt problem inom dynamisk programmering där man tar fram rekursiva formler för att lösa delproblem och sedan kombinerar lösningen till dessa för att ta fram lösningen till det ursprungliga problemet. I detta fall motsvarar deluppgift \(B\) huvudproblemet ("Given an array of "n" integers, find the sum of elements in the max subarray") och uppgift \(A\) motsvarar delproblemen ("Find the sum of elements in the max subarray that starts from index "i"").
Uppgift \(4\) (Geometri):
- - - - - - - - - - - - - - - - - - - - - -
Betrakta en triangel med hörn \(A,B,C\). Från \(A\) drar vi en bisektris till sidan \(BC\) så att den skär denna sida i punkten \(D\). Visa att
\(\frac{|AB|}{|BD|} = \frac{|AC|}{|CD|}\).
D.v.s. bevisa bisektrissatsen.
Zoom-länk (Vi startar som vanligt 13:00): https://stockholmuniversity.zoom.us/j/64826157501
Som vanligt är det bara att höra av er till oss om ni skulle ha några frågor eller funderingar. Fortsatt trevlig sommar på er!
Med vänliga hälsningar,
Emil Eriksson