\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 中国竞猜网_中国足彩网-足球推荐 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}




