[l2h] latex2html long standing bug, rawhtml stuff destroyed by math

Thu, 19 Sep 2002 17:56:52 -0700 

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

Attachment: leksjon_03.tex
Description: TeX document

Title: leksjon_03
$f(n)=\Theta (n)$

Master-metoden. Kap. 4.3

$\log _{b}a$

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 n inn i a delproblemer, hver med størelse n/b. (a og b er som regel samme tall, men ikke nødvendigvis.) De 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)$.

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$

Master-teoremet

Avhengig av hva $ f(n)$ egentlig er finnes følgende tre løsninger på rekurrens-ligningen:

  1. Hvis $ f(n)=O\left(n^{\log _{b}a-\epsilon }\right)$, $ \epsilon >0$, så er $ T(n)=\Theta \left(n^{\log _{b}a}\right)$
  2. Hvis $ f(n)=\Theta \left(n^{\log _{b}a}\right)$, så er $ T(n)=\Theta \left(n^{\log _{b}a}\lg n\right)$
  3. 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 n, så er $ T(n)=\Theta \left(f\left(n\right)\right)$
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 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 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 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.

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 a, b, og f(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 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 polynomisk størst, og dessuten sjekke tilleggsbetingelsen $ af\left(\frac{n}{b}\right)\leq cf(n)$ for en 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.

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 n. De har altså samme orden, så dette er tilfelle 2 som gjelder. Løsningen for tilfelle 2 er

$\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)}$

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 a og 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 f(n) 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 a, b, og f(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$. c større enn en halv er ikke noe problem, ettersom master-metoden bare krever at 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)}$.

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.

Gjør dessuten følgende oppgaver i læreboka:

Oppgave side
4.3-3 75
4.1 a,b,c,d,e og f 85

Alternative oppgaver for de med ``first edition'' av læreboka:

Oppgave side
4.3-3 64
4-1 a,b,c,d,e og f 72

$\log _{10}$

Helge Hafting 2002-09-17

Reply via email to