[l2h] latex2html long standing bug, rawhtml stuff destroyed by math
Helge Hafting
helgehaf@aitel.hist.no
Tue, 17 Sep 2002 14:57:17 +0200
This is a multi-part message in MIME format.
--------------FA3B80111AFE787C5DE9FAF4
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I have a problem with latex2html.
I use rawhtml for putting some php includes into the generated
html. That works fine with when the file is mostly text.
If there's lots of math too, then the math comes out fine
as a bunch of pictures, but my rawhtml is replaced
by fragments of latex math. (i.e. something is
being overwritten - possibly a variable name clash
or filename clash between math code and rawhtml code?)
A file "leksjon_03.tex" with this problem is attached.
The attached file "buggy" is the generated index.html
file, in case there's problems reproducing it.
Here's the command used:
latex2html -split 0 $1 -no_navigation -info 0 -iso_language NO
Versions:
$ latex2html --version
This is LaTeX2HTML Version 2002-2 (1.70)
by Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The computer is running linux, the Debian unstable distribution.
latex2html is the latest version downloaded from your site.
Helge Hafting
--------------FA3B80111AFE787C5DE9FAF4
Content-Type: application/x-tex;
name="leksjon_03.tex"
Content-Transfer-Encoding: 8bit
Content-Disposition: inline;
filename="leksjon_03.tex"
%% LyX 1.2 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[a4paper,twoside,norsk]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\medskipamount}
\setlength\parindent{0pt}
\usepackage{amsmath}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}
\usepackage{babel}
\makeatother
\begin{document}
\begin{rawhtml}
<?php include("../../lek_header.php") ?>
\end{rawhtml}
\section{Master-metoden. Kap. 4.3}
\begin{rawhtml}
<?php include("../../lek_copyright.php") ?>
\end{rawhtml}
Da vi analyserte mergesort, kom vi fram til at kjøretiden kan uttrykkes
med følgende ligning: $T(n)=2T\left(\frac{n}{2}\right)+\theta (n)$.
Nå skal vi se på en oppskrift for å løse slike ligninger.
Master-metoden er en oppskrift på å løse rekurrens-ligninger på formen
$T(n)=aT(n/b)+f(n)$, hvor $a\geq 1$ og $b\geq 1$ og $f(n)$ er
en asymptotisk positiv funksjon. Ligningen beskriver en algoritme
som deler et problem med størelse \emph{n} inn i \emph{a} delproblemer,
hver med størelse \emph{n}/\emph{b}. (\emph{a} og \emph{b} er som
regel samme tall, men ikke nødvendigvis.) De \emph{a} delproblemene
løses rekursivt, hver på tiden $T(n/b)$. Tiden for å dele opp problemet
og kombinere resultater fra delproblemer inngår i $f(n)$. For merge-sort
får vi $a=2,\, b=2,$ og $f(n)=\Theta (n)$.
\subsubsection*{Kalkulatortips:}
Hvordan beregnes $\log _{b}a$ ? Vanlige kalkulatorer har tier-logaritmer,
$\log _{10}$, så hvordan beregnes f. eks. $\lg 1024=\log _{2}1024$
? For å få til dette utnytter vi at $\log _{x}y=\frac{\log _{10}x}{\log _{10}y}$.
Dermed får vi $\log _{2}1024=\frac{\log 1024}{\log 2}=10$
\subsection*{Master-teoremet}
Avhengig av hva $f(n)$ egentlig er finnes følgende tre løsninger
på rekurrens-ligningen:
\begin{enumerate}
\item Hvis $f(n)=O\left(n^{\log _{b}a-\epsilon }\right)$, $\epsilon >0$,
så er $T(n)=\Theta \left(n^{\log _{b}a}\right)$
\item Hvis $f(n)=\Theta \left(n^{\log _{b}a}\right)$, så er $T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)$
\item Hvis $f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right),$ $\epsilon >0$,
og hvis $af\left(\frac{n}{b}\right)\leq cf(n)$ for en $c<1$ og alle
tilstrekkelig store \emph{n}, så er $T(n)=\Theta \left(f\left(n\right)\right)$
\end{enumerate}
Hva sier egentlig dette? I hvert tilfelle sammenlignes $f(n)$ med
$n^{\log _{b}a}$, og løsningen avhenger av hvem som har høyest orden.
NB! Ikke bare størst, men \emph{polynomisk} størst. $n^{\log _{b}a-\epsilon }=\frac{n^{\log _{b}a}}{n^{\epsilon }}$
så i det første tilfellet må altså $f(n)$ være mindre enn $n^{\log _{b}a}$
med en faktor på $n^{\epsilon }$ for en eller annen $\epsilon >0$.
I det tredje tilfellet må $f(n)$ være \emph{polynomisk} større, og
dessuten tilfredsstille $af\left(\frac{n}{b}\right)\leq cf(n)$. De
fleste polynomisk begrensede funksjoner oppfyller dette.
Vær oppmerksom på at de tre tilfellene ikke dekker alle mulighetene
for $f(n)$. Det er et gap mellom tilfelle 1 og 2 hvor $f(n)$ har
lavere orden enn $n^{\log _{b}a}$ men uten å være \emph{polynomisk}
mindre. Det er et tilsvarende gap mellom tilfelle 2 og 3, og tilfelle
3 har dessuten muligheten for at den ekstra betingelsen ikke holder.
Master-metoden dekker mange tilfeller, men kan ikke brukes for disse
unntakene.
\subsection*{Bruk av master-metoden}
Master-metoden brukes altså til å løse kjøretidsligninger. Sørg først
for at ligningen som skal løses er på formen $T(n)=aT(n/b)+f(n)$.
Dermed kan man finne \emph{a}, \emph{b}, \emph{}og \emph{f}(\emph{n}).
Deretter sammenligner du $f(n)$ og $n^{\log _{b}a}$ . Hvis $f(n)$
har lavest orden gjelder tilfelle 1. NB! sjekk at $f(n)$ ikke bare
har lavere orden, men \emph{polynomisk} lavere. Hvis de to uttrykkene
har samme orden, gjelder tilfelle 2. Hvis $f(n)$ har høyest orden
gjelder det tredje tilfellet. Her må man sjekke at $f(n)$ er \emph{polynomisk}
størst, og dessuten sjekke tilleggsbetingelsen $af\left(\frac{n}{b}\right)\leq cf(n)$
for en \emph{c}<1. Når man har funnet ut om det er tilfelle 1,2, eller
3 (og at evt. ekstra betingelser holder) er det bare å skrive opp
løsningen for det tilfellet det var.
\subsection*{Eksempler:}
Rekurrens-ligningen for quicksort/mergesort:
$T(n)=2T(n/2)+\Theta (n)$ Her har vi $a=2,\, b=2$, og $f(n)=n.$
Videre er $n^{\log _{b}a}=n^{\log _{2}2}=n^{1}=n$. Her er $f(n)$
og $n^{\log _{b}a}$ begge lik \emph{n.} De har altså samme orden,
så dette er tilfelle 2 som gjelder. Løsningen for tilfelle 2 er \[
T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)=\Theta \left(n^{\log _{2}2}\lg n\right)=\underline{\Theta (n\lg n)}\]
Dermed vet vi at $T(n)=\theta (n\lg n)$ for mergesort.
Nok et eksempel: $T(n)=4T(n/2)+n^{3}$. Her har vi $a=4,\, b=2,$
og $f(n)=n^{3}$. Når vi setter inn \emph{a} og \emph{b} i $n^{\log _{b}a}$
får vi $n^{\log _{2}4}$, som er det samme som $n^{2}$. ($\log _{2}4$
er det tallet vi må opphøye 2 i for å få 4, og det er som kjent 2.
$2^{2}=4$) I dette tilfellet har $f(n)$ som er $n^{3}$ høyest orden,
så vi får det tredje tilfellet. Men er \emph{f}(\emph{n}) \emph{polynomisk}
størst? Ja, $n^{3}=\Omega \left(n^{2+\epsilon }\right)$ hvis $\epsilon \leq 1$.
Og det er greit nok, vi har lov til å velge et hvilket som helst positivt
tall for $\epsilon $. Når vi har det tredje tilfellet, må vi dessuten
sjekke at $af\left(\frac{n}{b}\right)\leq cf(n)$ for en $c<1$. Vi
setter inn \emph{a}, \emph{b}, og \emph{f}(\emph{n}), og får $4\left(\frac{n}{2}\right)^{3}\leq c(n)^{3}\Rightarrow \frac{4}{8}n^{3}\leq cn^{3}\Rightarrow \frac{1}{2}\leq c$.
\emph{c} større enn en halv er ikke noe problem, ettersom master-metoden
bare krever at \emph{c} må være mindre enn 1. Dermed kan vi bruke
løsningen for tilfelle 3, $T(n)=\theta \left(f(n)\right)=\underline{\theta \left(n^{3}\right)}$.
\section*{Oppgaver for leksjon 3:}
I oppgavene forrige gang tok vi en titt på binærsøk. Sett opp rekurrensligningen
for tidsforbruket for binærsøk, og løs den ved hjelp av master-metoden.
\subsection*{Gjør dessuten følgende oppgaver i læreboka:}
\begin{tabular}{|c|c|}
\hline
Oppgave&
side\\
\hline
\hline
4.3-3&
75\\
\hline
4.1 a,b,c,d,e og f&
85\\
\hline
\end{tabular}
\subsection*{Alternative oppgaver for de med {}``first edition'' av læreboka:}
\begin{tabular}{|c|c|}
\hline
Oppgave&
side\\
\hline
\hline
4.3-3&
64\\
\hline
4-1 a,b,c,d,e og f&
72\\
\hline
\end{tabular}
\begin{rawhtml}
<?php include("../../lek_footer.php") ?>
\end{rawhtml}
\end{document}
--------------FA3B80111AFE787C5DE9FAF4
Content-Type: text/html; charset=us-ascii;
name="buggy"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="buggy"
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//NO">
<!--Converted with LaTeX2HTML 2002-2 (1.70)
original version by: Nikos Drakos, CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>leksjon_03</TITLE>
<META NAME="description" CONTENT="leksjon_03">
<META NAME="keywords" CONTENT="leksjon_03">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="LaTeX2HTML v2002-2">
<META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css">
<LINK REL="STYLESHEET" HREF="leksjon_03.css">
</HEAD>
<BODY >
$f(n)=\Theta (n)$
<P>
<H1><A NAME="SECTION00010000000000000000">
Master-metoden. Kap. 4.3</A>
</H1>
<P>
$\log _{b}a$
<P>
Da vi analyserte mergesort, kom vi fram til at kjøretiden kan uttrykkes
med følgende ligning: <!-- MATH
$T(n)=2T\left(\frac{n}{2}\right)+\theta (n)$
-->
<IMG
WIDTH="155" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img1.png"
ALT="$ T(n)=2T\left(\frac{n}{2}\right)+\theta (n)$">.
Nå skal vi se på en oppskrift for å løse slike ligninger.
<P>
Master-metoden er en oppskrift på å løse rekurrens-ligninger på formen
<!-- MATH
$T(n)=aT(n/b)+f(n)$
-->
<IMG
WIDTH="166" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img2.png"
ALT="$ T(n)=aT(n/b)+f(n)$">, hvor <IMG
WIDTH="41" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img3.png"
ALT="$ a\geq 1$"> og <IMG
WIDTH="40" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img4.png"
ALT="$ b\geq 1$"> og <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> er
en asymptotisk positiv funksjon. Ligningen beskriver en algoritme
som deler et problem med størelse <I>n</I> inn i <I>a</I> delproblemer,
hver med størelse <I>n</I>/<I>b</I>. (<I>a</I> og <I>b</I> er som
regel samme tall, men ikke nødvendigvis.) De <I>a</I> delproblemene
løses rekursivt, hver på tiden <IMG
WIDTH="52" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img6.png"
ALT="$ T(n/b)$">. Tiden for å dele opp problemet
og kombinere resultater fra delproblemer inngår i <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$">. For merge-sort
får vi <!-- MATH
$a=2,\, b=2,$
-->
<IMG
WIDTH="91" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img7.png"
ALT="$ a=2,\, b=2,$"> og <!-- MATH
$f(n)=\Theta (n)$
-->
<IMG
WIDTH="91" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img8.png"
ALT="$ f(n)=\Theta (n)$">.
<P>
<H3><A NAME="SECTION00010100000000000000">
Kalkulatortips:</A>
</H3>
<P>
Hvordan beregnes <!-- MATH
$\log _{b}a$
-->
<IMG
WIDTH="41" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img9.png"
ALT="$ \log _{b}a$"> ? Vanlige kalkulatorer har tier-logaritmer,
<!-- MATH
$\log _{10}$
-->
<IMG
WIDTH="38" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img10.png"
ALT="$ \log _{10}$">, så hvordan beregnes f. eks. <!-- MATH
$\lg 1024=\log _{2}1024$
-->
<IMG
WIDTH="133" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img11.png"
ALT="$ \lg 1024=\log _{2}1024$">
? For å få til dette utnytter vi at <!-- MATH
$\log _{x}y=\frac{\log _{10}x}{\log _{10}y}$
-->
<IMG
WIDTH="106" HEIGHT="40" ALIGN="MIDDLE" BORDER="0"
SRC="img12.png"
ALT="$ \log _{x}y=\frac{\log _{10}x}{\log _{10}y}$">.
Dermed får vi <!-- MATH
$\log _{2}1024=\frac{\log 1024}{\log 2}=10$
-->
<IMG
WIDTH="171" HEIGHT="38" ALIGN="MIDDLE" BORDER="0"
SRC="img13.png"
ALT="$ \log _{2}1024=\frac{\log 1024}{\log 2}=10$">
<P>
<H2><A NAME="SECTION00011000000000000000">
Master-teoremet</A>
</H2>
<P>
Avhengig av hva <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> egentlig er finnes følgende tre løsninger
på rekurrens-ligningen:
<P>
<OL>
<LI>Hvis <!-- MATH
$f(n)=O\left(n^{\log _{b}a-\epsilon }\right)$
-->
<IMG
WIDTH="143" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img14.png"
ALT="$ f(n)=O\left(n^{\log _{b}a-\epsilon }\right)$">, <!-- MATH
$\epsilon >0$
-->
<IMG
WIDTH="39" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img15.png"
ALT="$ \epsilon >0$">,
så er <!-- MATH
$T(n)=\Theta \left(n^{\log _{b}a}\right)$
-->
<IMG
WIDTH="130" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$ T(n)=\Theta \left(n^{\log _{b}a}\right)$">
</LI>
<LI>Hvis <!-- MATH
$f(n)=\Theta \left(n^{\log _{b}a}\right)$
-->
<IMG
WIDTH="127" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$ f(n)=\Theta \left(n^{\log _{b}a}\right)$">, så er <!-- MATH
$T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)$
-->
<IMG
WIDTH="157" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img18.png"
ALT="$ T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)$">
</LI>
<LI>Hvis <!-- MATH
$f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right),$
-->
<IMG
WIDTH="148" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img19.png"
ALT="$ f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right),$"> <!-- MATH
$\epsilon >0$
-->
<IMG
WIDTH="39" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img15.png"
ALT="$ \epsilon >0$">,
og hvis <!-- MATH
$af\left(\frac{n}{b}\right)\leq cf(n)$
-->
<IMG
WIDTH="110" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img20.png"
ALT="$ af\left(\frac{n}{b}\right)\leq cf(n)$"> for en <IMG
WIDTH="39" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img21.png"
ALT="$ c<1$"> og alle
tilstrekkelig store <I>n</I>, så er <!-- MATH
$T(n)=\Theta \left(f\left(n\right)\right)$
-->
<IMG
WIDTH="120" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img22.png"
ALT="$ T(n)=\Theta \left(f\left(n\right)\right)$">
</LI>
</OL>
Hva sier egentlig dette? I hvert tilfelle sammenlignes <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> med
<!-- MATH
$n^{\log _{b}a}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img23.png"
ALT="$ n^{\log _{b}a}$">, og løsningen avhenger av hvem som har høyest orden.
NB! Ikke bare størst, men <I>polynomisk</I> størst. <!-- MATH
$n^{\log _{b}a-\epsilon }=\frac{n^{\log _{b}a}}{n^{\epsilon }}$
-->
<IMG
WIDTH="123" HEIGHT="41" ALIGN="MIDDLE" BORDER="0"
SRC="img24.png"
ALT="$ n^{\log _{b}a-\epsilon }=\frac{n^{\log _{b}a}}{n^{\epsilon }}$">
så i det første tilfellet må altså <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> være mindre enn <!-- MATH
$n^{\log _{b}a}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img23.png"
ALT="$ n^{\log _{b}a}$">
med en faktor på <!-- MATH
$n^{\epsilon }$
-->
<IMG
WIDTH="19" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
SRC="img25.png"
ALT="$ n^{\epsilon }$"> for en eller annen <!-- MATH
$\epsilon >0$
-->
<IMG
WIDTH="39" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img15.png"
ALT="$ \epsilon >0$">.
I det tredje tilfellet må <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> være <I>polynomisk</I> større, og
dessuten tilfredsstille <!-- MATH
$af\left(\frac{n}{b}\right)\leq cf(n)$
-->
<IMG
WIDTH="110" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img20.png"
ALT="$ af\left(\frac{n}{b}\right)\leq cf(n)$">. De
fleste polynomisk begrensede funksjoner oppfyller dette.
<P>
Vær oppmerksom på at de tre tilfellene ikke dekker alle mulighetene
for <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$">. Det er et gap mellom tilfelle 1 og 2 hvor <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> har
lavere orden enn <!-- MATH
$n^{\log _{b}a}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img23.png"
ALT="$ n^{\log _{b}a}$"> men uten å være <I>polynomisk</I>
mindre. Det er et tilsvarende gap mellom tilfelle 2 og 3, og tilfelle
3 har dessuten muligheten for at den ekstra betingelsen ikke holder.
Master-metoden dekker mange tilfeller, men kan ikke brukes for disse
unntakene.
<P>
<H2><A NAME="SECTION00012000000000000000">
Bruk av master-metoden</A>
</H2>
<P>
Master-metoden brukes altså til å løse kjøretidsligninger. Sørg først
for at ligningen som skal løses er på formen <!-- MATH
$T(n)=aT(n/b)+f(n)$
-->
<IMG
WIDTH="166" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img2.png"
ALT="$ T(n)=aT(n/b)+f(n)$">.
Dermed kan man finne <I>a</I>, <I>b</I>, og <I>f</I>(<I>n</I>).
Deretter sammenligner du <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> og <!-- MATH
$n^{\log _{b}a}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img23.png"
ALT="$ n^{\log _{b}a}$"> . Hvis <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$">
har lavest orden gjelder tilfelle 1. NB! sjekk at <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> ikke bare
har lavere orden, men <I>polynomisk</I> lavere. Hvis de to uttrykkene
har samme orden, gjelder tilfelle 2. Hvis <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> har høyest orden
gjelder det tredje tilfellet. Her må man sjekke at <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> er <I>polynomisk</I>
størst, og dessuten sjekke tilleggsbetingelsen <!-- MATH
$af\left(\frac{n}{b}\right)\leq cf(n)$
-->
<IMG
WIDTH="110" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img20.png"
ALT="$ af\left(\frac{n}{b}\right)\leq cf(n)$">
for en <I>c</I><1. Når man har funnet ut om det er tilfelle 1,2, eller
3 (og at evt. ekstra betingelser holder) er det bare å skrive opp
løsningen for det tilfellet det var.
<P>
<H2><A NAME="SECTION00013000000000000000">
Eksempler:</A>
</H2>
<P>
Rekurrens-ligningen for quicksort/mergesort:
<P>
<!-- MATH
$T(n)=2T(n/2)+\Theta (n)$
-->
<IMG
WIDTH="170" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img26.png"
ALT="$ T(n)=2T(n/2)+\Theta (n)$"> Her har vi <!-- MATH
$a=2,\, b=2$
-->
<IMG
WIDTH="86" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img27.png"
ALT="$ a=2,\, b=2$">, og <IMG
WIDTH="71" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img28.png"
ALT="$ f(n)=n.$">
Videre er <!-- MATH
$n^{\log _{b}a}=n^{\log _{2}2}=n^{1}=n$
-->
<IMG
WIDTH="176" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img29.png"
ALT="$ n^{\log _{b}a}=n^{\log _{2}2}=n^{1}=n$">. Her er <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$">
og <!-- MATH
$n^{\log _{b}a}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img23.png"
ALT="$ n^{\log _{b}a}$"> begge lik <I>n.</I> De har altså samme orden,
så dette er tilfelle 2 som gjelder. Løsningen for tilfelle 2 er <!-- MATH
\begin{displaymath}
T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)=\Theta \left(n^{\log _{2}2}\lg n\right)=\underline{\Theta (n\lg n)}
\end{displaymath}
-->
<P></P>
<DIV ALIGN="CENTER">
<IMG
WIDTH="360" HEIGHT="37" ALIGN="MIDDLE" BORDER="0"
SRC="img30.png"
ALT="$\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)=\Theta \left(n^{\log _{2}2}\lg n\right)=\underline{\Theta (n\lg n)}$">
</DIV><P></P>
Dermed vet vi at <!-- MATH
$T(n)=\theta (n\lg n)$
-->
<IMG
WIDTH="115" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img31.png"
ALT="$ T(n)=\theta (n\lg n)$"> for mergesort.
<P>
Nok et eksempel: <!-- MATH
$T(n)=4T(n/2)+n^{3}$
-->
<IMG
WIDTH="152" HEIGHT="34" ALIGN="MIDDLE" BORDER="0"
SRC="img32.png"
ALT="$ T(n)=4T(n/2)+n^{3}$">. Her har vi <!-- MATH
$a=4,\, b=2,$
-->
<IMG
WIDTH="91" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img33.png"
ALT="$ a=4,\, b=2,$">
og <!-- MATH
$f(n)=n^{3}$
-->
<IMG
WIDTH="73" HEIGHT="34" ALIGN="MIDDLE" BORDER="0"
SRC="img34.png"
ALT="$ f(n)=n^{3}$">. Når vi setter inn <I>a</I> og <I>b</I> i <!-- MATH
$n^{\log _{b}a}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img23.png"
ALT="$ n^{\log _{b}a}$">
får vi <!-- MATH
$n^{\log _{2}4}$
-->
<IMG
WIDTH="45" HEIGHT="17" ALIGN="BOTTOM" BORDER="0"
SRC="img35.png"
ALT="$ n^{\log _{2}4}$">, som er det samme som <IMG
WIDTH="21" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
SRC="img36.png"
ALT="$ n^{2}$">. (<!-- MATH
$\log _{2}4$
-->
<IMG
WIDTH="41" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img37.png"
ALT="$ \log _{2}4$">
er det tallet vi må opphøye 2 i for å få 4, og det er som kjent 2.
<IMG
WIDTH="48" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
SRC="img38.png"
ALT="$ 2^{2}=4$">) I dette tilfellet har <IMG
WIDTH="34" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img5.png"
ALT="$ f(n)$"> som er <IMG
WIDTH="20" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
SRC="img39.png"
ALT="$ n^{3}$"> høyest orden,
så vi får det tredje tilfellet. Men er <I>f</I>(<I>n</I>) <I>polynomisk</I>
størst? Ja, <!-- MATH
$n^{3}=\Omega \left(n^{2+\epsilon }\right)$
-->
<IMG
WIDTH="102" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img40.png"
ALT="$ n^{3}=\Omega \left(n^{2+\epsilon }\right)$"> hvis <!-- MATH
$\epsilon \leq 1$
-->
<IMG
WIDTH="39" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img41.png"
ALT="$ \epsilon \leq 1$">.
Og det er greit nok, vi har lov til å velge et hvilket som helst positivt
tall for <IMG
WIDTH="10" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
SRC="img42.png"
ALT="$ \epsilon $">. Når vi har det tredje tilfellet, må vi dessuten
sjekke at <!-- MATH
$af\left(\frac{n}{b}\right)\leq cf(n)$
-->
<IMG
WIDTH="110" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img20.png"
ALT="$ af\left(\frac{n}{b}\right)\leq cf(n)$"> for en <IMG
WIDTH="39" HEIGHT="29" ALIGN="MIDDLE" BORDER="0"
SRC="img21.png"
ALT="$ c<1$">. Vi
setter inn <I>a</I>, <I>b</I>, og <I>f</I>(<I>n</I>), og får <!-- MATH
$4\left(\frac{n}{2}\right)^{3}\leq c(n)^{3}\Rightarrow \frac{4}{8}n^{3}\leq cn^{3}\Rightarrow \frac{1}{2}\leq c$
-->
<IMG
WIDTH="264" HEIGHT="42" ALIGN="MIDDLE" BORDER="0"
SRC="img43.png"
ALT="$ 4\left(\frac{n}{2}\right)^{3}\leq c(n)^{3}\Rightarrow \frac{4}{8}n^{3}\leq cn^{3}\Rightarrow \frac{1}{2}\leq c$">.
<I>c</I> større enn en halv er ikke noe problem, ettersom master-metoden
bare krever at <I>c</I> må være mindre enn 1. Dermed kan vi bruke
løsningen for tilfelle 3, <!-- MATH
$T(n)=\theta \left(f(n)\right)=\underline{\theta \left(n^{3}\right)}$
-->
<IMG
WIDTH="176" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
SRC="img44.png"
ALT="$ T(n)=\theta \left(f(n)\right)=\underline{\theta \left(n^{3}\right)}$">.
<P>
<H1><A NAME="SECTION00020000000000000000">
Oppgaver for leksjon 3:</A>
</H1>
<P>
I oppgavene forrige gang tok vi en titt på binærsøk. Sett opp rekurrensligningen
for tidsforbruket for binærsøk, og løs den ved hjelp av master-metoden.
<P>
<H2><A NAME="SECTION00021000000000000000">
Gjør dessuten følgende oppgaver i læreboka:</A>
</H2>
<P>
<TABLE CELLPADDING=3 BORDER="1">
<TR><TD ALIGN="CENTER">Oppgave</TD>
<TD ALIGN="CENTER">side</TD>
</TR>
<TR><TD ALIGN="CENTER">4.3-3</TD>
<TD ALIGN="CENTER">75</TD>
</TR>
<TR><TD ALIGN="CENTER">4.1 a,b,c,d,e og f</TD>
<TD ALIGN="CENTER">85</TD>
</TR>
</TABLE>
<P>
<H2><A NAME="SECTION00022000000000000000">
Alternative oppgaver for de med ``first edition'' av læreboka:</A>
</H2>
<P>
<TABLE CELLPADDING=3 BORDER="1">
<TR><TD ALIGN="CENTER">Oppgave</TD>
<TD ALIGN="CENTER">side</TD>
</TR>
<TR><TD ALIGN="CENTER">4.3-3</TD>
<TD ALIGN="CENTER">64</TD>
</TR>
<TR><TD ALIGN="CENTER">4-1 a,b,c,d,e og f</TD>
<TD ALIGN="CENTER">72</TD>
</TR>
</TABLE>
<P>
$\log _{10}$
<BR><HR>
<ADDRESS>
Helge Hafting
2002-09-17
</ADDRESS>
</BODY>
</HTML>
--------------FA3B80111AFE787C5DE9FAF4--