\documentclass[a4paper]{article}

\usepackage[latin2]{inputenc}
\usepackage{slovene}

\begin{document}

\title{Domača naloga}
\author{Mirnesa Klisura}
\date{18. 05. 1999}
\maketitle

\begin{abstract}
Podana imamo dva seznama, ki ju hočemo združiti v en seznam. Z 
indukcijo bomo dokazali veljavnost trditve, da oba seznama hkrati ne 
moreta biti prazna.
\end{abstract}

\section{Opis delovanja funkcije zlij}
Na vajah smo napisali funkcijo \verb+ zlij +, ki zlije dva seznama 
v en seznam. \\

PRIMER: \\
$ sez1 = 1\hspace{0.1 cm} 3\hspace{0.1 cm}
         6\hspace{0.1 cm} 8\hspace{0.1 cm} ; $ \\
$ sez2 = 2\hspace{0.1 cm} 4\hspace{0.1 cm} 5\hspace{0.1 cm} ; $ \\
$ \Longrightarrow nov\_seznam = 1\hspace{0.1 cm} 2\hspace{0.1 cm} 
                               3\hspace{0.1 cm} 4\hspace{0.1 cm} 
                               5\hspace{0.1 cm} 6\hspace{0.1 cm} 
                               8\hspace{0.1 cm} ; $ \\

Del kode funkcije \verb+ zlij +, izgleda takole:

\begin{verbatim}
tSeznam rezultat;
int glava;

if (sez1 == NULL) return sez2;
if (sez2 == NULL) return sez1;
rezultat = NULL;
do{
  if (vred_glave(sez1) > vred_glave(sez2))
    sez2 = izloci_glavo(&glava, sez2);
  else 
    sez1 = izloci_glavo(&glava, sez1);
  rezultat = Dodaj_na_koncu(glava, rezultat);
} while ((sez1 == NULL) || (sez2 == NULL));
\end{verbatim}

Funkcija zlij pa deluje na naslednji način:
\begin{itemize}
\item {Če je sez1 prazen, vrnemo sez2.}
\item {Če pa je sez2 prazen, potem vrnemo sez1.}
\item {Če pa seznama nista prazna, potem gremo preverjati:} 
       \begin{itemize}
       \item če je vrednost glave iz sez1 večja od vrednosti 
             glave iz sez2, potem iz sez2 izločimo glavo, 
       \item drugače pa izločimo glavo iz sez1 in glavo
             dodamo na konec seznama. 
       \end{itemize}
       To delamo dokler eden od seznamov ni prazen.
\end{itemize}

Ugotovili smo, da oba seznama hkrati ne moreta biti prazna. \\ 
To pa zaradi tega, ker: 
\begin{enumerate}
\item {na začetku zanke oba seznama nista prazna,}
\item {v zanki se vedno samo en seznam krajša.}
\end{enumerate}


\section{Naloga}

Dokazati moramo veljavnost trditve. Pravilnost trditve pa bomo 
dokazali z indukcijo. \\
Najprej bomo dokazali veljavnost trditve za bazo oz. osnovno
vrednost. Nato pa bomo, s pomočjo predpostavke, trditev dokazali 
še za korak.


\section{Dokaz}
{\bf TRDITEV:} {\it Oba seznama hkrati ne moreta biti prazna.} \\

{\bf BAZA}: {\sl Dokazati moramo, da je trditev veljavna za vsako dolžino 
               prvega niza, ki je večja od 0 in drugega, ki je 0, ter 
               obratno.}

\begin{enumerate}
\item {$ sez1 = NULL, sez2 {\neq} NULL; $} \\
       Ker je sez1 prazen seznam, vrnemo sez2. \\ 
       Iz tega sledi, da je trditev veljavna.

\item {$ sez1 {\neq} NULL, sez2 = NULL ; $} \\
      Ker je sez2 prazen sezanam, vrnemo sez1. \\
      Iz tega sledi, da je trditev veljavna. 
\end{enumerate}

{\bf PREDPOSTAVKA:} {\sl Predpostavljamo, da je trditev veljavna za 
                         vsako dolžino prvega seznama, ki je največ 
                         $ n_{1} $ in drugega, ki je največ $ n_{2} $.

$ |sez1| = n_{1} $ \\
$ |sez2| = n_{2} $ \\

{\bf KORAK:} {\sl Dokazati moramo, da je trditev veljavna:}
\begin{itemize}
\item {za vsako dolžino prvega niza, ki je največ $ n_{1} + 1 $ 
      in drugega, ki je največ $ n_{2} $}
\item {za vsako dolžino prvega niza, ki je največ $ n_{1} $ in
      drugega, ki je največ $ n_{2} + 1 $}
\item {za vsako dolžino prvega niza, ki je največ $ n_{1} + 1 $ 
      in drugega, ki je največ $ n_{2} + 1 $}
\end{itemize}

\begin{enumerate}
\item {$ |sez1| = n_{1} + 1 $ \\
       $ |sez2| = n_{2} $} \\
Ker noben od seznamov ni prazen, se sprehodimo po zanki do - while.
  \begin{itemize} 
  \item  Če je vred\_glave(sez1) $ > $ vred\_glave(sez2), se izloči glava iz 
         sez2, dolžina sez2 pa se zmanjša za 1. 
         Torej je $$ |sez2| = n_{2} - 1, 
                     |sez1| = n_{1} + 1 $$ 
         Dolžina sez2 se zmanjšuje za 1 toliko časa
           \begin{itemize}       
            \item {dokler sez2 ni prazen} \\
                   Za ta primer pa smo že dokazali veljavnost trditve (baza).
            \item {ali pa dokler vred\_glave(sez1) ni manjša od vred\_glave(sez2)} \\
                   V tem primeru se izloči glava iz sez1, dolžina sez1 pa se 
                   zmanjša za 1. Sledi, da je $$ |sez1| = n_{1}, \\
                                                  |sez2| = n_{2} - 1 $$
                   Ker pa je po predpostavki, trditev veljavna za vsako $ |sez1| = n_{1} $
                   in $ |sez2| = n_{2} $, potem velja tudi za ta primer, ko sta niza 
                   dolga $ n_{1} $ in $ n_{2} - 1. $
           \end{itemize}

  \item  Če pa je vred\_glave(sez1) $ < $ vred\_glave(sez2), potem se izloči 
         glava iz sez1, dolžina sez1 pa se zmanjša za 1.
         Torej je $$ |sez1| = n_{1}, 
                     |sez2| = n_{2} $$
         Po predpostavki, pa trditev velja za ta dva niza.
  \end{itemize}

\item {$ |sez1| = n_{1} $ \\ 
       $ |sez2| = n_{2} + 1 $} \\
Ker noben od seznamov ni prazen, se sprehodimo po zanki do - while.
  \begin{itemize}
  \item  Če je vred\_glave(sez1) $ > $ vred\_glave(sez2), se izloči glava iz 
         sez2, dolžina sez2 se zmanjša za 1.  
         Torej je $$|sez2| = n_{2}, 
                    |sez1| = n_{1} $$ 
         Po predpostavki pa trditev velja za ta dva niza.
  
  \item  Če pa je vred\_glave(sez1) $ < $ vred\_glave(sez2), potem se izloči 
         glava iz sez1, dolžina sez1 pa se zmanjša za 1.
         Torej je $$ |sez1| = n_{1} - 1,
                     |sez2| = n_{2} + 1 $$
         Dolžina sez1 se zmanjšuje za 1 toliko časa
         \begin{itemize}
         \item {dokler sez1 ni prazen} \\
                Za ta primer pa smo že dokazali,da trditev velja (baza).
         \item {ali pa dokler vred\_glave(sez1) ni večja od vred\_glave(sez2)} \\
                V tem primeru se izloči glava iz sez2, dolžina sez2 pa se 
                zmanjša za 1. Sledi, da je $$ |sez2| = n_{2}, 
                                               |sez1| = n_{1} - 1 $$ 
                Po predpostavki pa je trditev veljavna, za vsako dolžino sez1, 
                ki je največ $ n_{1} $ in dolžino sez2, ki je največ $ n_{2} $.
                Torej velja tudi za primer, ko je $$ |sez2| = n_{2}, \\
                                                     |sez1| = n_{1} - 1 $$
         \end{itemize}
  \end{itemize}

\item {$ |sez1| = n_{1} + 1 $ \\
       $ |sez2| = n_{2} + 1 $} \\
Ker noben od seznamov ni prazen se sprehodimo po zanki do - while.
  \begin{itemize}
  \item  Če je vred\_glave(sez1) $ > $ vred\_glave(sez2), se izloči glava iz 
         sez2, dolžina sez2 se zmanjša za 1. 
         Torej je $$ |sez2| = n_{2},
                     |sez1| = n_{1} + 1 $$
         Pravilnost trditve za ta primer pa smo že pokazali v točki 1.

  \item  drugače pa se izloči glava iz sez1, dolžina sez1 pa se zmanjša 
         za 1. Sledi, da je $$ |sez1| = n_{1},
                               |sez2| = n_{2} + 1 $$
         Za ta primer pa smo pokazali veljavnost trditve v točki 2.
  \end{itemize}
\end{enumerate} 

\section{Zaključek}
S pomočjo indukcije, smo dokazali pravilnost trditve.
Oba seznama hkrati torej ne moreta biti prazna.


\end{document}
