\documentclass[11pt,norsk]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage[colorlinks]{hyperref}
\usepackage{fouriernc,bm}

% Makroer for oppgaver
\newcounter{probnum}[section]
\newcounter{subprobnum}[probnum]

\newenvironment{oppgaver}{\vspace{12pt}\goodbreak \subsection*{Oppgaver}
\begin{list}{\bf Oppgave \arabic{probnum}.\ }
{\usecounter{probnum}\setlength{\itemsep}{6pt}}}{\end{list}\vfill\eject}

\newcommand{\oppgave}{\item}

\newenvironment{deloppgaver}{\begin{list}{\alph{subprobnum})}
{\usecounter{subprobnum}\setlength{\topsep}{3pt}
\setlength{\itemsep}{1.5pt}}}{\end{list}}

\newcommand{\deloppgave}{\item}


\begin{document}
\begin{flushright}
\small 13.~september, 2018
\end{flushright}
\vspace{7mm}

\begin{center}
\huge MAT-INF 1100: Obligatorisk oppgave 1\\
\vspace{5mm}
\Large  Innleveringsfrist: 27/9-2018, kl. 14:30 i Devilry
\end{center}

\section*{}
Obligatoriske oppgaver («obliger») er en sentral del av MAT-INF1100 og er utmerket trening i å besvare en matematisk oppgave.
Denne veiledningen er ment for å klargjøre noen krav vi som retter obligene stiller, både for å forenkle vår jobb i retteprosessen og for at dere skal slippe å måtte levere på nytt på grunn av formaliteter.

For å få godkjent en oblig bør man ha fått til om lag 2/3 av oppgavesettet og gitt alle deloppgavene et seriøst forsøk. 
Dersom det allikevel skulle være en oppgave du overhodet ikke får til, prøv å sette ord på hva du har tenkt og hvor det ikke lot seg løse.
Dersom man får «ikke godkjent» på en oblig og får et nytt forsøk vil det ha innleveringsfrist to uker etter første innlevering.  

\section{Krav til innlevering}

\begin{itemize}
	\item Besvarelsen skal leveres elektronisk via Devilry (\url{https://devilry.ifi.uio.no/}). Du velger selv om du skriver besvarelsen for hånd (og scanner besvarelsen) eller om du skriver løsningen direkte inn på datamaskin (f.eks. ved bruk av \LaTeX). Skannede ark må være godt lesbare. Godkjente filtyper: PDF

	\item Hoveddelen av besvarelsen skal leveres som én fil og i PDF-format. Det er lov å skanne inn håndskrevne ark så lenge disse er godt lesbare. 

	\item Besvarelsen skal inneholde navn, emne og oblignummer.

	\item Husk at andre skal lese og forstå din besvarelse! Besvarelsene bør derfor føres på en oversiktlig måte i den rekkefølgen de står oppgitt i.

	\item Alle plott og figurer som er med på å besvare oppgaven må inkluderes (husk også riktige akser og enheter). Du bør også skrive kort hva hver figur viser, for eksempel:
	\textit{Figur 2: Plott av funksjonen $f(x) = x^2 -3$.}

	\item Kode skrives i Python og leveres ved siden av besvarelsen, men \textbf{all diskusjon} og \textbf{all besvarelse} av oppgaven skal inn i hovedfila. 
	Det vil f.eks. si at du ikke kan levere et python-skript som besvarelse på en oppgave hvor du blir bedt om å lage en algoritme. Det er viktig at programkoden du leverer inneholder et kjøreksempel, slik at det er lett å se hvilket resultat programmet gir. 
	\item Det oppmuntres til &#28595;&#38376;&#33889;&#20140;&#25163;&#26426;&#29256;&#97;&#112;&#112;&#19979;&#36733; om oppgavene, men du skal selv ha formulert og skrevet den besvarelsen som leveres inn, og den skal gjenspeile din forståelse av stoffet. Du kan bli bedt om å redegjøre muntlig for innholdet i din besvarelse.

	\item Besvarelsen bør inneholde diskusjon om resultatene dere kommer fram til. Eksempler på spørsmål man kan stille seg for å vite hva man skal kommentere er: \textit{Gir dette plottet noen mening?} \textit{Ser virkelig grafen til $f(x)$ slik ut?} \textit{Var dette resultatet som forventet?} \textit{Kan dette skyldes numeriske feil?} 
\end{itemize}

\noindent
Husk at de to obligatoriske oppgavene i MAT-INF 1100 begge må bestås for å kunne gå opp til endelig eksamen i emnet.

\paragraph{Søknad om utsettelse av innleveringsfrist}Hvis man blir syk eller av andre grunner trenger å søke om utsettelse av innleveringsfristen må du ta kontakt med studieadministrasjonen ved Matematisk institutt (7. et. Niels Henrik Abels hus, e-post: studieinfo@math.uio.no) i god tid før innleveringsfristen. 
For fullstendige retningslinjer for innlevering av obligatoriske oppgaver se
\begin{center}
uio.no/studier/admin/obligatoriske-aktiviteter/mn-math-oblig.html
\end{center}

\section{\LaTeX}

Vi oppmuntrer til bruk av \LaTeX. Dette er et slags programmeringsspråk for å skrive naturfaglige dokumenter som det kan være greit å lære seg først som sist.
Hjelp til \LaTeX{} kan du få omtrent overalt, fra utallige forum på verdensveven til gruppelærere over hele MatNat-fakultetet. 
Dersom du trenger hjelp til å komme i gang vil du finne \LaTeX-versjonen av denne teksten samme sted som du finner PDF-filen. Vi vil også legge ut en \LaTeX-mal med eksempler på hvordan inkludere kode og figurer som du kan bruke til å gjøre obligene i MAT-INF1100 om du vil. 

\newpage


\begin{oppgaver}

\oppgave
Vi skal se på differensligningen
\begin{equation}\label{eq:diff}
x_{n+2} - 2 x_{n+1} - x_{n} = 0,  \quad\text{med  $x_0 = 1$ og $x_1 = 2$.}
\end{equation}
\begin{deloppgaver}

\deloppgave Lag et dataprogram som simulerer denne ligningen og skriver ut følgen $x_2$, $x_3$, \dots, $x_{100}$. 

\deloppgave Simuler  ligningen og skriv ut følgen $x_2$, $x_3$, \dots, $x_{100}$ når startverdien $x_1$ endres til $x_{1} = 1-\sqrt{2}$

\deloppgave Vis at den generelle løsningen av ligningen $x_{n+2} - 2 x_{n+1} -  x_{n} = 0$ er på formen
$$
x_n = C(1-\sqrt 2)^n + D(1+\sqrt 2)^n
$$
og at initialverdiene $x_0=1$ og $x_1 = 1-\sqrt 2$ bestemmer den endelige løsningen til å være $x_n = (1-\sqrt{2})^n$.

\deloppgave Sjekk om den analytiske løsningen i (c) stemmer med dine beregninger i (b) og forklar eventuelle avvik.

\deloppgave (Om du har lyst og tid). Bruk simuleringene i (b) til å estimere avrundingsenheten (the round-off unit) på maskinen din.
\end{deloppgaver}

\oppgave
Binomialkoeffisienten $\binom{n}{i}$ er definert som
\begin{equation}\label{eq:binomdef}
\binom{n}{i}=\frac{n!}{i!\,(n-i)!}
\end{equation}
der $n\ge 0$ er et ikke-negativt heltall og $i$ er et heltall i intervallet $0\le i \le n$.

Binomialkoeffisientene dukker opp i mange ulike sammenhenger og må ofte beregnes på datamaskin. Siden alle binomialkoeffisientene er heltall (divisjonen i  \eqref{eq:binomdef} gir aldri noen rest) så er det rimelig å bruke heltallige variable i slike beregninger. For små verdier av $n$ og $i$ går det bra, men for større verdier får vi fort problemer fordi både teller og nevner i \eqref{eq:binomdef} lett blir større enn det største heltallet som kan representeres med 32- eller 64-bits heltall selv om binomialkoeffisienten i seg selv ikke er så stor. I mange språk vil dette føre til en form for «overflow», men selv i et språk som Python som unngår dette ved at innebygget programvare kommer til unnsetning, vil beregningene gå langt saktere enn ellers. Vi kan bruke flyttall i stedet, men selv da vil vi lett få «overflow» underveis i beregningene. I denne oppgaven skal vi se hvordan vi kan unngå slike problemer.

Hvis vi ser nærmere på definisjonen \eqref{eq:binomdef} legger vi merke til at vi kan forkorte i stor skala,
$$
\binom{n}{i}=\frac{1\cdot 2 \cdots i \cdot (i+1) \cdots n}
{1\cdot 2 \cdots i \cdot 1 \cdot 2 \cdots (n-i)}
=\frac{i+1}{1}\cdot\frac{i+2}{2}\cdots \frac{n}{n-i}.
$$
Ved hjelp av produktnotasjon kan vi derfor skrive $\binom{n}{i}$ som
\begin{equation}\label{eq:altdef}
\binom{n}{i}=\prod_{j=1}^{n-i} \frac{i+j}{j}.
\end{equation}

\begin{deloppgaver}
\deloppgave
Skriv et program som beregner binomialkoeffisienter ved hjelp av formelen \eqref{eq:altdef}. Test metoden på eksemplene
\begin{align*}
\binom{5000}{4} &= 26010428123750,\\[3pt]
\binom{100000}{60} &= 1.18069197996257 \cdot 10^{218},\\[3pt]
\binom{1000}{500} &=  2.702882409454366 \cdot 10^{299}.
\end{align*}\nobreak
Hvorfor må du bruke flyttall og hvilke resultater får du?
\deloppgave
Er det nå mulig at du underveis får «overflow» om binomialkoeffisienten du skal beregne er mindre enn det største flyttallet som kan representeres på maskinen din?

\deloppgave
I vår utledning av \eqref{eq:altdef} forkortet vi $i!$ mot $n!$ i
\eqref{eq:binomdef}. En alternativ metode kan utledes ved å forkorte 
$(n-i)!$ mot $n!$ isteden. Utled denne alternative metoden på samme måte som over og diskuter når de to metodene bør brukes (du trenger ikke programmere denne metoden, det holder å argumentere matematisk). 
\end{deloppgaver}

\oppgave
Følgende Python-program er gitt:

\begin{verbatim}
from random import random

antfeil = 0; N = 100000

for i in range(N):
    x = random(); y = random(); z = random()
    res1 = (x*y)*z
    res2 = x*(y*z)
    
    if res1 != res2:
        antfeil += 1
        x0 = x; y0 = y; z0 = z
        ikkeass1 = res1
        ikkeass2 = res2

print (100. * antfeil/N)
print (x0, y0, z0, ikkeass1 - ikkeass2)

\end{verbatim}

En kjøring av programmet ga utskriften

{\small\begin{verbatim}
35.056
0.012421854744752325 0.1751776618141262 0.6421241188091763 -2.168404344971009e-19
\end{verbatim}
}

\begin{deloppgaver}
\oppgave Forklar hva programmet gjør og hva utskriften forteller oss.
\oppgave Endre programmet slik at det i stedet sammenligner de to størrelsene \verb\x*(y+z)\ og \verb\x*y+x*z\, og kjør det på nytt. Du skal nå se at det første tallet som blir skrevet ut blir
ulikt det  første tallet som ble skrevet ut over (d.v.s. {\tt 35.056}). Kan du tenke deg en mulig forklaring på dette?
\end{deloppgaver}

\vspace{1cm}
\centerline{\em Lykke til!}

\end{oppgaver}




\end{document}




