%
% algo-2014-03.tex college Algoritmiek 2014
% ook beschikbaar als pdf via
%   http://www.liacs.nl/home/graaf/algo/
%
% latex algo-2014-03.tex
% dvips -t landscape -Ppdf algo-2014-03.dvi
% ps2pdf algo-2014-03.ps
% latex algo-2014-03.tex; dvips -t landscape -Ppdf algo-2014-03.dvi; ps2pdf algo-2014-03.ps; 
% acroread algo-2009-02.pdf &
%
% acroread algo-2014-03.pdf &
% gebruik CTRL-L
%
% psnup -8 -r -m20 controle.ps > small.ps
%
% Jeannette de Graaf, j.m.de.graaf@liacs.leidenuniv.nl
%
% november 2006/februari 2009/2009/2010/2011/2013/2014
%cp

\documentclass{slides}

\usepackage{portland}

\usepackage[english,dutch]{babel}

\selectlanguage{dutch}

\usepackage[dvips]{graphicx}

%\usepackage{eurosym}

\usepackage{color}

\definecolor{mygreen}{rgb}{0,0.6,0}

\newcommand{\cpp}{C$\stackrel{\scriptscriptstyle{++}}{}$}
% kijk: dit is een macro.
% je kunt beginnen met \kopje{College 3}
\newcommand{\kopje}[1]{\vspace{1mm}Algoritmiek 2014/03\hfill{\bf \textcolor{blue}{#1}}
     \vspace{3mm}\hrule}

\frenchspacing

\begin{document}

\landscape


\begin{slide}

%\kopje{College 3}
\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{College 3}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\vspace{1.5cm}

\begin{LARGE}
\begin{center}
Derde college algoritmiek\\

\vspace{2cm}

21 februari 2014\\

\vspace{2cm}


\textcolor{mygreen}{Toestand-actie-ruimte}
% en complexiteit}

\end{center}
\end{LARGE}

 \vfill
\end{slide}


\begin{slide}
\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Binaire zoekbomen}}
\vspace{3mm}
\hrule
%eerste college
\bigskip

\begin{itemize}
\item
Een \textcolor{red}{binaire zoekboom}\footnote{{\tiny zie ook werkgroep 2 en Levitin, p.60/189/190}} is een binaire boom waarbij voor elke knoop geldt dat de waarde
in die knoop groter is dan alle waarden in zijn linkersubboom, en kleiner dan alle waarden in zijn
rechtersubboom.
\end{itemize}

\vspace{5mm}
\begin{center}
{\setlength{\unitlength}{0.15cm}
\begin{picture}(110,35)

\put(80,35){\makebox(0,0){\small 5}}

\put(78,34){\line(-2,-1){12}}
\put(82,34){\line(2,-1){12}}

\put(65,25){\makebox(0,0){\small 1}}
\put(67,23){\line(1,-1){7}}

\put(95,25){\makebox(0,0){\small 7}}
\put(93,23){\line(-1,-1){7}}
\put(97,23){\line(1,-1){7}}

\put(75,14){\makebox(0,0){\small 3}}
\put(73,12){\line(-1,-2){3.5}}
\put(69,2){\makebox(0,0){\small 2}}
\put(77,12){\line(1,-2){3.5}}
\put(81,2){\makebox(0,0){\small 4}}

\put(85,14){\makebox(0,0){\small 6}}
\put(105,14){\makebox(0,0){\small 9}}
\put(104,12){\line(-1,-2){3.5}}
\put(100,2){\makebox(0,0){\small 8}}

\put(15,25){\bf LWR}
\put(0,15){$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9$}

\end{picture}
}
\end{center}

%\vspace{1.5cm}

\vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{BZboom: verwijderen}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\vspace{5mm}
{\tiny Eerst de weg te gooien waarde/knoop zoeken en deze vervolgens netjes verwijderen. Hierbij is de ouder van de te verwijderen knoop nodig. We onderscheiden drie gevallen: de knoop is een blad of heeft \'e\'en kind of heeft twee kinderen.}

\vspace{-5mm}
\begin{center}
\setlength{\unitlength}{0.15cm}
\begin{picture}(155,55)(5,0)
%\put(5,0){\framebox(155,50){}}
\put(-10,0){
\input{AVLboom.68_1}
}
% gemaakt met `texgraaf.c'
% voor invoer: zie `AVLboom.68_1info.dat'
% andere instantie dan in Algoritmiek dictaat/practicumopgave
%
% ietsje aangepast ten opzichte van Datastructuren dictaat
% vervolgens handmatig aangepast door Jeannette de Graaf
\end{picture}
\end{center}

\vspace{0.5cm}
\begin{center}
\textcolor{red}{verwijderen van een blad}
\end{center}

  \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{BZboom: verwijderen}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\begin{center}
\setlength{\unitlength}{0.15cm}
\begin{picture}(160,55)(5,0)
%\put(5,0){\framebox(160,50){}}
\put(-10,0){
\input{AVLboom.68_1_2}
}
% gemaakt met `texgraaf.c'
% voor invoer: zie `AVLboom.68_1_2info.dat'
% stond nog niet in Datastructuren dictaat
% vervolgens handmatig aangepast door Jeannette de Graaf
\end{picture}
\end{center}

\vspace{1cm}
\begin{center}
\textcolor{red}{verwijderen van een knoop met 1 kind}
\end{center}
  \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{BZboom: verwijderen}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\begin{center}
\setlength{\unitlength}{0.15cm}
\begin{picture}(160,55)(5,0)
%\put(5,0){\framebox(160,50){}}
\put(-10,0){
\input{AVLboom.68_1_3}
}
% gemaakt met `texgraaf.c'
% voor invoer: zie `AVLboom.68_1_3info.dat'
% stond nog niet in Datastructuren dictaat
% vervolgens handmatig aangepast door Jeannette de Graaf
\end{picture}
\end{center}

\vspace{1cm}
\begin{center}
\textcolor{red}{verwijderen van een knoop met 2 kinderen}\\
verwissel met de grootste kleinere {\small of kleinste grotere}
\end{center}

  \vfill
\end{slide}




\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Toestand-actie-ruimte}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

{\bf Probleem $\longrightarrow$ Toestand-actie-ruimte}\\

Een \textcolor{red}{toestand-actie-ruimte}
(toestand-actie-diagram, state transition diagram, toestandsruimte, state space)

\begin{itemize}
\item
\emph{Bestaat uit} alle mogelijke \textcolor{red}{toestanden en acties}
\vspace{-0.5cm}
\item
Begintoestand, eindtoestand(en)
\vspace{-0.5cm}
\item
Een actie veroorzaakt een overgang van de ene (toegelaten) toestand naar een
andere
\vspace{-0.5cm}
\item
\emph{Oplossing} van het probleem: een opeenvolging van acties die van de
begintoestand naar een eindtoestand leiden
\end{itemize}

  \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Nim}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

{\bf Voorbeeld 1: NIM}

\begin{itemize}
\item
We beginnen met \'e\'en stapel van $n$ lucifers (begintoestand)
\vspace{-0.5cm}
\item
Er zijn twee spelers: \textcolor{red}{A} en \textcolor{mygreen}{B}
\vspace{-0.5cm}
\item
De spelers pakken om de beurt 1 of 2 lucifers (acties)
\vspace{-0.5cm}
\item
Het spel is afgelopen als er geen lucifers meer op de stapel liggen (eindtoestand)
\vspace{-0.5cm}
\item
De speler die de laatste lucifer(s) pakt heeft gewonnen
\end{itemize}

{\bf Gevraagd: } is het spel winnend voor degene die begint?
  \vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Nim $n=5$}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{center}
{\bf toestand-actie-ruimte \textcolor{red}{(spelboom)} $n=5$}
\end{center}

\begin{center}
{\setlength{\unitlength}{0.15cm}
\begin{picture}(115,80)

\put(64,65){\makebox(0,0){5}}
\put(62,63){\line(-2,-1){20}}
\put(66,63){\line(2,-1){20}}
\put(0,65){\makebox(0,0){\textcolor{red}{A}}}

\put(41,50){\makebox(0,0){4}}
\put(87,50){\makebox(0,0){3}}
\put(0,50){\makebox(0,0){\textcolor{mygreen}{B}}}
\put(39,48){\line(-1,-1){10}}
\put(43,48){\line(1,-1){10}}
\put(85,48){\line(-1,-1){10}}
\put(89,48){\line(1,-1){10}}

\put(28,35){\makebox(0,0){3}}
\put(54,35){\makebox(0,0){2}}
\put(0,35){\makebox(0,0){\textcolor{red}{A}}}
\put(74,35){\makebox(0,0){2}}
\put(100,35){\makebox(0,0){1}}

\put(26,33){\line(-1,-2){5}}
\put(30,33){\line(1,-2){5}}
\put(20,20){\makebox(0,0){2}}
\put(36,20){\makebox(0,0){1}}
\put(0,20){\makebox(0,0){\textcolor{mygreen}{B}}}

\put(50,28){\tiny{\textcolor{red}{A wint}}}
\put(70,28){\tiny{\textcolor{red}{A wint}}}
\put(96,28){\tiny{\textcolor{red}{A wint}}}

\put(15,13){\tiny{\textcolor{mygreen}{B wint}}}
\put(32,13){\tiny{\textcolor{mygreen}{B wint}}}

\end{picture}
}
\end{center}

  \vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Nim $n=5$}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{center}
{\bf Winnend voor A}. \\
Winnende zet: 2 lucifers wegnemen
\end{center}

\vspace{1cm}

\begin{center}
{\setlength{\unitlength}{0.15cm}
\begin{picture}(115,70)

\put(64,60){\makebox(0,0){{\bf \textcolor{red}{5}}}}
\put(62,58){\line(-2,-1){20}}
\put(66,58){\line(2,-1){20}}
\put(0,60){\makebox(0,0){\textcolor{red}{A}}}

\put(41,45){\makebox(0,0){{\bf \textcolor{mygreen}{4}}}}
\put(87,45){\makebox(0,0){{\bf \textcolor{red}{3}}}}
\put(0,45){\makebox(0,0){\textcolor{mygreen}{B}}}
\put(39,43){\line(-1,-1){10}}
\put(43,43){\line(1,-1){10}}
\put(85,43){\line(-1,-1){10}}
\put(89,43){\line(1,-1){10}}

\put(28,30){\makebox(0,0){{\bf \textcolor{mygreen}{3}}}}
\put(54,30){\makebox(0,0){{\bf \textcolor{red}{2}}}}
\put(0,30){\makebox(0,0){\textcolor{red}{A}}}
\put(74,30){\makebox(0,0){{\bf \textcolor{red}{2}}}}
\put(100,30){\makebox(0,0){{\bf \textcolor{red}{1}}}}

\put(26,28){\line(-1,-2){5}}
\put(30,28){\line(1,-2){5}}
\put(20,15){\makebox(0,0){{\bf \textcolor{mygreen}{2}}}}
\put(36,15){\makebox(0,0){{\bf \textcolor{mygreen}{1}}}}
\put(0,15){\makebox(0,0){\textcolor{mygreen}{B}}}


\end{picture}
}
\end{center}

%  \vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Nim $n=6$}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{center}
{\bf toestand-actie-ruimte (spelboom) $n=6$}
\end{center}

\begin{center}
{\setlength{\unitlength}{0.12cm}
\begin{picture}(170,100)

\put(95,90){\makebox(0,0){6}}
\put(92,87){\line(-2,-1){25}}
\put(98,87){\line(3,-1){37}}
\put(0,90){\makebox(0,0){\textcolor{red}{A}}}

\put(65,70){\makebox(0,0){5}}
\put(137,70){\makebox(0,0){4}}
\put(0,70){\makebox(0,0){\textcolor{mygreen}{B}}}
\put(0,50){\makebox(0,0){\textcolor{red}{A}}}
\put(0,30){\makebox(0,0){\textcolor{mygreen}{B}}}
\put(0,10){\makebox(0,0){\textcolor{red}{A}}}


\put(62,67){\line(-1,-1){13}}
\put(68,67){\line(1,-1){13}}
\put(134,67){\line(-1,-1){13}}
\put(140,67){\line(1,-1){13}}
\put(47,50){\makebox(0,0){4}}
\put(83,50){\makebox(0,0){3}}
\put(119,50){\makebox(0,0){3}}
\put(155,50){\makebox(0,0){2}}
\put(150,42){\tiny{\textcolor{red}{A wint}}}

\put(44,47){\line(-1,-2){6}}
\put(50,47){\line(1,-2){6}}
\put(37,30){\makebox(0,0){3}}
\put(57,30){\makebox(0,0){2}}
\put(50,22){\tiny{\textcolor{mygreen}{B wint}}}

\put(80,47){\line(-1,-2){6}}
\put(86,47){\line(1,-2){6}}
\put(73,30){\makebox(0,0){2}}
\put(93,30){\makebox(0,0){1}}
\put(67,22){\tiny{\textcolor{mygreen}{B wint}}}
\put(86,22){\tiny{\textcolor{mygreen}{B wint}}}

\put(116,47){\line(-1,-2){6}}
\put(122,47){\line(1,-2){6}}
\put(109,30){\makebox(0,0){2}}
\put(129,30){\makebox(0,0){1}}
\put(103,22){\tiny{\textcolor{mygreen}{B wint}}}
\put(122,22){\tiny{\textcolor{mygreen}{B wint}}}

\put(34,27){\line(-1,-3){4}}
\put(40,27){\line(1,-3){4}}
\put(29,10){\makebox(0,0){2}}
\put(45,10){\makebox(0,0){1}}
\put(22,2){\tiny{\textcolor{red}{A wint}}}
\put(40,2){\tiny{\textcolor{red}{A wint}}}



%\put(50,28){\tiny{\textcolor{red}{A wint}}}
%\put(70,28){\tiny{\textcolor{red}{A wint}}}
%\put(96,28){\tiny{\textcolor{red}{A wint}}}

%\put(15,13){\tiny{\textcolor{mygreen}{B wint}}}
%\put(32,13){\tiny{\textcolor{mygreen}{B wint}}}

\end{picture}
}
\end{center}

  \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Nim $n=6$}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{center}
{\bf A kan niet winnen} (bij perfect spel van B) \\
\end{center}

\begin{center}
{\setlength{\unitlength}{0.12cm}
\begin{picture}(170,100)

\put(95,90){\makebox(0,0){{\bf \textcolor{mygreen}{6}}}}
\put(92,87){\line(-2,-1){25}}
\put(98,87){\line(3,-1){37}}
\put(0,90){\makebox(0,0){\textcolor{red}{A}}}

\put(65,70){\makebox(0,0){{\bf \textcolor{mygreen}{5}}}}
\put(137,70){\makebox(0,0){{\bf \textcolor{mygreen}{4}}}}
\put(0,70){\makebox(0,0){\textcolor{mygreen}{B}}}
\put(0,50){\makebox(0,0){\textcolor{red}{A}}}
\put(0,30){\makebox(0,0){\textcolor{mygreen}{B}}}
\put(0,10){\makebox(0,0){\textcolor{red}{A}}}


\put(62,67){\line(-1,-1){13}}
\put(68,67){\line(1,-1){13}}
\put(134,67){\line(-1,-1){13}}
\put(140,67){\line(1,-1){13}}
\put(47,50){\makebox(0,0){{\bf \textcolor{red}{4}}}}
\put(83,50){\makebox(0,0){{\bf \textcolor{mygreen}{3}}}}
\put(119,50){\makebox(0,0){{\bf \textcolor{mygreen}{3}}}}
\put(155,50){\makebox(0,0){{\bf \textcolor{red}{2}}}}

\put(44,47){\line(-1,-2){6}}
\put(50,47){\line(1,-2){6}}
\put(37,30){\makebox(0,0){{\bf \textcolor{red}{3}}}}
\put(57,30){\makebox(0,0){{\bf \textcolor{mygreen}{2}}}}

\put(80,47){\line(-1,-2){6}}
\put(86,47){\line(1,-2){6}}
\put(73,30){\makebox(0,0){{\bf \textcolor{mygreen}{2}}}}
\put(93,30){\makebox(0,0){{\bf \textcolor{mygreen}{1}}}}

\put(116,47){\line(-1,-2){6}}
\put(122,47){\line(1,-2){6}}
\put(109,30){\makebox(0,0){{\bf \textcolor{mygreen}{2}}}}
\put(129,30){\makebox(0,0){{\bf \textcolor{mygreen}{1}}}}

\put(34,27){\line(-1,-3){4}}
\put(40,27){\line(1,-3){4}}
\put(29,10){\makebox(0,0){{\bf \textcolor{red}{2}}}}
\put(45,10){\makebox(0,0){{\bf \textcolor{red}{1}}}}

\end{picture}
}
\end{center}

  \vfill
\end{slide}

\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{2persoonsspelen en recursie}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

Een stand is \textcolor{red}{winnend} voor degene die aan de beurt is als een
der directe (= in 1 zet te bereiken) vervolgstanden NIET \textcolor{red}{winnend} is voor de
tegenstander.

\begin{center}
{\setlength{\unitlength}{0.11cm}
\begin{picture}(170,40)

\put(95,30){\makebox(0,0){{\bf \textcolor{red}{5}}}}
\put(92,27){\line(-2,-1){25}}
\put(98,27){\line(3,-1){37}}
\put(0,30){\makebox(0,0){\textcolor{red}{A}}}

\put(65,10){\makebox(0,0){{\bf \textcolor{mygreen}{4}}}}
\put(137,10){\makebox(0,0){{\bf \textcolor{red}{3}}}}
\put(0,10){\makebox(0,0){\textcolor{mygreen}{B}}}
\end{picture}
}
\end{center}

Speler \textcolor{red}{A} is aan zet en een van de directe vervolgstanden (namelijk de rechter zet, neem 2 lucifers) is niet winnend voor de tegenstander.


 \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{2persoonsspelen en recursie}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

Een stand is \textcolor{red}{verliezend} voor degene die aan de beurt is als ALLE
directe (= in 1 zet te bereiken) vervolgstanden \textcolor{red}{winnend} zijn voor de
tegenstander.

\begin{center}
{\setlength{\unitlength}{0.11cm}
\begin{picture}(170,40)

\put(95,30){\makebox(0,0){{\bf \textcolor{mygreen}{6}}}}
\put(92,27){\line(-2,-1){25}}
\put(98,27){\line(3,-1){37}}
\put(0,30){\makebox(0,0){\textcolor{red}{A}}}

\put(65,10){\makebox(0,0){{\bf \textcolor{mygreen}{5}}}}
\put(137,10){\makebox(0,0){{\bf \textcolor{mygreen}{4}}}}
\put(0,10){\makebox(0,0){\textcolor{mygreen}{B}}}
\end{picture}
}
\end{center}

Speler \textcolor{red}{A} is aan zet en alle directe vervolgstanden
(zowel de linker als de rechter zet) zijn winnend voor de tegenstander.


 \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{2persoonsspelen en recursie}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

%Een stand is \textcolor{red}{winnend} voor degene die aan de beurt is als een
%der directe (= in 1 zet te bereiken) vervolgstanden NIET \textcolor{red}{winnend} is voor de
%tegenstander.

Een algoritme dat bepaalt of een stand \textcolor{red}{winnend} is, ziet er dus ruwweg zo uit:

Loop alle mogelijke directe vervolgstanden af:

\vspace{-8mm}

\hspace{1cm}kijk of je er een tegenkomt die not \textcolor{red}{winnend} is voor de
tegenstander: \textcolor{mygreen}{recursie}

\vspace{-8mm}
\hspace{1cm}zo ja, dan is de oorspronkelijke stand winnend (en heb je meteen een
winnende zet) en hoef je niet verder te kijken

\vspace{-8mm}
\hspace{1cm}zo nee, dan de volgende vervolgstand proberen

\vspace{-5mm}
Als alle vervolgstanden zijn geweest {\small (en ook de laatste vervolgstand was winnend voor de
tegenstander)} is de oorspronkelijke stand niet winnend.
  \vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Structuur algoritme -1-}}
\vspace{3mm}
\hrule
%tweede college
\bigskip
\begin{verbatim}
winnend(stand)::

   if eindstand(stand) then
      //  makkelijk; bijv return false;
   else
      for alle mogelijke zetten i do
          kopie := stand;  // maak een kopie
          doezet(kopie,i);  // en doe de zet daarin
          if not winnend(kopie) then
              return true;
          fi
      od
      return false;
   fi
\end{verbatim}

Zie ook Programmeermethoden (college over recursie)\\
  \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Structuur algoritme -2-}}
\vspace{3mm}
\hrule
%tweede college
\bigskip
\begin{verbatim}
winnend(stand)::

   if eindstand(stand) then
      //  makkelijk; bijv return false;
   else
      for alle mogelijke zetten i do
      // nu met terugzetten !
          doezet(stand,i);
          if not winnend(stand) then
              neemzetterug(stand,i);
              return true;
          fi
          neemzetterug(stand,i);
      od
      return false;
   fi
\end{verbatim}

  \vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Voorbeeld: nim}}
\vspace{3mm}
\hrule
%derde college
\bigskip


Gebruik een kopie en doe daarin de zetten:

\vspace{0.5cm}

\begin{small}
\begin{verbatim}
bool nimwinst (int stand) {
    int lucifer, kopie;
    if ( stand == 0 )
        return false;
        // tegenstander heeft zojuist de laatste lucifers gepakt
    else {
        // directe vervolgstanden aflopen
        for ( lucifer = 1; lucifer <= 2; lucifer++ ) {
             kopie = stand;  // maak een kopie
             kopie -= lucifer; // doe een zet in de kopie
             if ( !nimwinst (kopie) ) {
                 return true;
             }
        }
        return false;
    }  // else
}
\end{verbatim}
\end{small}

\vfill
\end{slide}




\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Nogmaals: nim}}
\vspace{3mm}
\hrule
%derde college
\bigskip


Met terugzetten:

\vspace{0.5cm}

\begin{small}
\begin{verbatim}
bool nimwinst (int stand) {
    int lucifer;
    if ( stand == 0 )
        return false;
        // tegenstander heeft zojuist de laatste lucifers gepakt
    else {
        // directe vervolgstanden aflopen
        for ( lucifer = 1; lucifer <= 2; lucifer++ ) {
             stand -= lucifer; // doe een zet
             if ( !nimwinst (stand) ) {
                 stand += lucifer; // terugzetten
                 return true;
             }
             stand += lucifer; // terugzetten
        }
        return false;
    }  // else
}
\end{verbatim}
\end{small}

\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Boer, wolf, geit, kool}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

{\bf Voorbeeld 2: Old world puzzle} (Ex. 1.2.1.)

We hebben een kool, een geit, een wolf en een boer. Deze moeten met een
bootje van de ene kant van de rivier naar de andere. In het bootje kan
alleen de boer met \'e\'en ander iets. Als de boer er niet bij is zal de
wolf de geit opeten en de geit de kool. De boer is de enige die de boot kan
``besturen''.

{\bf Vraag: } Hoe kan alles (liefst zo snel mogelijk) naar de andere oever verplaatst worden?

\begin{center}
\includegraphics[scale=1.0]{wolfboergeitkool.ps}
\end{center}


\end{slide}







\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Toestand-actie-ruimte}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{center}
{\setlength{\unitlength}{0.10cm}
\begin{picture}(200,50)


\put(85,40){\makebox(0,0){{\tiny K$\|$BGW}}}
\put(97,40){\line(1,0){7}}
%\put(96,44){\textcolor{mygreen}{{\tiny BG}}}
\put(115,40){\makebox(0,0){{\tiny KBG$\|$W}}}
\put(85,10){\makebox(0,0){{\tiny W$\|$BKG}}}
\put(97,10){\line(1,0){7}}
%\put(96,3){\textcolor{mygreen}{{\tiny BG}}}
\put(115,10){\makebox(0,0){{\tiny WBG$\|$K}}}

\put(67,25){\makebox(0,0){{\tiny KWB$\|$G}}}
\put(133,25){\makebox(0,0){{\tiny G$\|$KWB}}}
\put(75,37){\line(-1,-1){7}}
%\put(60,34){\textcolor{mygreen}{{\tiny BW}}}
\put(125,37){\line(1,-1){7}}
%\put(131,34){\textcolor{mygreen}{{\tiny BK}}}
\put(75,14){\line(-1,1){7}}
%\put(60,14){\textcolor{mygreen}{{\tiny BK}}}
\put(125,14){\line(1,1){7}}
%\put(131,14){\textcolor{mygreen}{{\tiny BW}}}

\put(36,25){\makebox(0,0){{\tiny KW$\|$BG}}}
\put(48,25){\line(1,0){7}}
%\put(48,29){\textcolor{mygreen}{{\tiny B}}}
\put(5,25){\makebox(0,0){{\tiny KGWB$\|$}}}
\put(17,25){\line(1,0){7}}
%\put(16,29){\textcolor{mygreen}{{\tiny BG}}}
\put(164,25){\makebox(0,0){{\tiny GB$\|$KW}}}
\put(145,25){\line(1,0){7}}
%\put(145,29){\textcolor{mygreen}{{\tiny B}}}
\put(195,25){\makebox(0,0){{\tiny $\|$BGKW}}}
\put(176,25){\line(1,0){7}}
%\put(175,29){\textcolor{mygreen}{{\tiny BG}}}

\end{picture}
}
\end{center}

Merk op: de boot ligt altijd aan de oever waar de boer zich bevindt.

De oplossing is een \textcolor{red}{kortste pad} van de begintoestand naar de eindtoestand: hier zijn er twee, bij
beide moet de boer 7 keer de rivier oversteken.

\vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Toestand-actie-ruimte}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{center}
{\setlength{\unitlength}{0.10cm}
\begin{picture}(200,50)


\put(85,40){\makebox(0,0){{\tiny K$\|$BGW}}}
\put(97,40){\line(1,0){7}}
\put(96,44){\textcolor{mygreen}{{\tiny BG}}}
\put(115,40){\makebox(0,0){{\tiny KBG$\|$W}}}
\put(85,10){\makebox(0,0){{\tiny W$\|$BKG}}}
\put(97,10){\line(1,0){7}}
\put(96,3){\textcolor{mygreen}{{\tiny BG}}}
\put(115,10){\makebox(0,0){{\tiny WBG$\|$K}}}

\put(67,25){\makebox(0,0){{\tiny KWB$\|$G}}}
\put(133,25){\makebox(0,0){{\tiny G$\|$KWB}}}
\put(75,37){\line(-1,-1){7}}
\put(60,34){\textcolor{mygreen}{{\tiny BW}}}
\put(125,37){\line(1,-1){7}}
\put(131,34){\textcolor{mygreen}{{\tiny BK}}}
\put(75,14){\line(-1,1){7}}
\put(60,14){\textcolor{mygreen}{{\tiny BK}}}
\put(125,14){\line(1,1){7}}
\put(131,14){\textcolor{mygreen}{{\tiny BW}}}

\put(36,25){\makebox(0,0){{\tiny KW$\|$BG}}}
\put(48,25){\line(1,0){7}}
\put(48,29){\textcolor{mygreen}{{\tiny B}}}
\put(5,25){\makebox(0,0){{\tiny KGWB$\|$}}}
\put(17,25){\line(1,0){7}}
\put(16,29){\textcolor{mygreen}{{\tiny BG}}}
\put(164,25){\makebox(0,0){{\tiny GB$\|$KW}}}
\put(145,25){\line(1,0){7}}
\put(145,29){\textcolor{mygreen}{{\tiny B}}}
\put(195,25){\makebox(0,0){{\tiny $\|$BGKW}}}
\put(176,25){\line(1,0){7}}
\put(175,29){\textcolor{mygreen}{{\tiny BG}}}

\end{picture}
}
\end{center}

Merk op: de boot ligt altijd aan de oever waar de boer zich bevindt.

De oplossing is een \textcolor{red}{kortste pad} van de begintoestand naar de eindtoestand: hier zijn er twee, bij
beide moet de boer 7 keer de rivier oversteken.

\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Studenten en professoren}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

Een leuke variant op dit probleem is het volgende:

We hebben drie professoren en drie studenten. Deze moeten allemaal met een
bootje van de ene kant van de rivier naar de andere. In het bootje kunnen hooguit twee
personen.
Aan beide oevers mogen de professoren niet in de meerderheid zijn, anders worden de
studenten nerveus.

{\bf Vraag: } Hoe kan iedereen naar de andere oever verplaatst worden?\\

\begin{small}
Merk op dat in tegenstelling tot het boer-wolf-geit-kool-probleem hier iedereen de boot kan
``besturen''. Er moet nu dus in een toestand worden aangegeven waar de boot ligt.

Er zijn 4 verschillende oplossingen, elk met 11 keer overvaren.
\end{small}


\vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Torens van Hanoi}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\begin{small}

{\bf Voorbeeld 3: Torens van Hanoi}

Gegeven $n$ ($n \geq 1$) schijven, alle verschillend in grootte, en 3 palen.
In de beginsituatie liggen alle schijven boven op elkaar om \'e\'en paal, waarbij er geen grotere schijf op een
kleinere ligt. De andere 2 palen zijn leeg.

{\bf Opdracht:} Breng de hele toren (zo snel mogelijk) naar een van de lege palen door het een voor een
verplaatsen van schijven van de ene paal naar de andere. Alleen de \emph{bovenste} schijf van een stapel
kan verzet worden,
en deze mag alleen \emph{bovenop} een andere stapel gelegd worden.
\emph{Restrictie}: er mag nooit een grotere schijf op een kleinere gelegd worden.

Een {\bf toestand} is in dit geval een verdeling van de schijven over de palen, waarbij (als gevolg van de
restrictie) geen grotere schijf op een kleinere ligt.
Een {\bf actie} is het verplaatsen van een schijf volgens de spelregels.

{\bf Vraag:} Hoeveel toestanden zijn er in dit geval eigenlijk?

\end{small}
\vfill
\end{slide}


\begin{slide}
\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Toestand-actie-ruimte $n=3$}}
%\vspace{3mm}
\hrule
%tweede college
%\bigskip
%{\bf toestand-actie-diagram} voor $n=3$.
\vspace{-0.2cm}
%\begin{center}
\includegraphics[scale=0.75]{hanoi_graph3.eps}
%\end{center}

\vfill
\end{slide}



\begin{slide}
\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Oplossing Hanoi $n=3$}}
\vspace{3mm}
\hrule
%derde college
\bigskip
{\bf Optimale oplossing voor $n=3$}.
\input{hanoi1.tex}
\input{hanoi2.tex}
\input{hanoi3.tex}

\vfill
\end{slide}


\begin{slide}
\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Oplossing Hanoi algemeen}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\vspace{-1cm}
\includegraphics[scale=0.7]{hanoiopl.eps}

\begin{center}
{\small \textcolor{red}{Recursieve} oplossing van de Torens van Hanoi}
\end{center}

{\tiny Zie verder: Programmeermethoden, college over recursie.}

\vfill
\end{slide}




\begin{slide}

{\bf \Huge Een Intermezzo}

\end{slide}




\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Kannen}}
\vspace{3mm}
\hrule
%derde college
\bigskip

{\bf Voorbeeld 4: Kannenprobleem}

We hebben twee kannen: een grote met een inhoud van 8 liter, en een kleine met
 een inhoud van 5 liter. Op de kannen
staat geen maatverdeling. Verder hebben we de beschikking over een waterkraan
 en een afvoer. Bij aanvang zijn beide kannen leeg.

{\bf Vraag: } Hoe krijgen we precies 4 liter water in  een van de twee kannen? En liefst zo snel mogelijk.\\

\begin{center}
\includegraphics[scale=0.2]{kan.ps}
\includegraphics[scale=0.15]{kan.ps}
\includegraphics[scale=0.2]{kan.ps}
\includegraphics[scale=0.15]{kan.ps}
\includegraphics[scale=0.2]{kan.ps}
\includegraphics[scale=0.15]{kan.ps}
\includegraphics[scale=0.2]{kan.ps}
\end{center}

\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Toestanden en acties}}
\vspace{3mm}
\hrule
%derde college
\bigskip

We onderscheiden toestanden en zinvolle (!) acties:

{\bf Toestand}: Een paar $(x, y)$ met $0 \leq x \leq 8$ en $0 \leq y \leq 5$. Hierin is $x$ de inhoud van de grote kan
en $y$ de inhoud van de kleine kan.\\
{\bf Begintoestand}: beide kannen leeg, dus (0,0)\\
{\bf Eindtoestanden}: alle toestanden met 4 liter in een van beide kannen, dus (4, y) en (x, 4)

{\bf Acties}: vullen, legen en overgieten
\begin{enumerate}
\vspace{-1cm}
\item[-]
een kan geheel (aan)vullen
\vspace{-1cm}
\item[-]
een kan geheel leeggooien
\vspace{-1cm}
\item[-]
de ene kan leeggooien in de andere
\vspace{-1cm}
\item[-]
van de ene kan in de andere gieten totdat deze vol is
\end{enumerate}
\vfill
\end{slide}

\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Toestandsruimte}}
\vspace{3mm}
\hrule
%derde college
%\bigskip
\vspace{-0.2cm}
\input{plaatje1.tex}
\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03 \hfill{\bf \textcolor{blue}{... met mogelijke
acties}} \vspace{3mm} \hrule
%derde college
%\bigskip
\vspace{-0.2cm}
\input{plaatje2.tex}
\vfill
\end{slide}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Oplossing}}
\vspace{3mm}
\hrule
%derde college
%\bigskip
\vspace{-0.2cm}
\input{plaatje3.tex}
\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03 \hfill{\bf \textcolor{blue}{Snelste
oplossing}}
\vspace{3mm}
\hrule
%derde college
\bigskip
De snelste oplossing gebruikt de volgende \textcolor{red}{strategie} en zorgt voor 4 liter in de kleine kan.
Er is overigens ook een (iets) langere oplossing, die 4 liter in de grote kan achterlaat.


\begin{tabbing}
XXXX\=XXX\=XXX\=XXX\=XXX\=XXX\kill
   \> Herhaal  \\
   \>   \> Herhaal\\
   \>   \>    \>  Vul de kleine kan;\\
   \>   \>    \>  Giet over in de grote kan;\\
   \>   \> totdat de grote kan vol is\\
   \>   \> Grote kan leeggooien;\\
   \>   \> Giet uit de kleine kan over in de grote kan; \\
   \> totdat oplossing gevonden
\end{tabbing}


Zie verder het college.
\vfill
\end{slide}




\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{(Werk)college}}
\vspace{3mm}
\hrule
%tweede college
\bigskip

\vspace{-5mm}

\begin{itemize}

\item
{\bf Lezen/leren bij dit college:}
\\
Paragraaf 6.6 {\tiny (subparagraaf `Reduction to Graph Problems')}

\vspace*{-0.8cm}
\item

\textcolor{red}{Programmeeropdracht: {\small functies zoals inlezen, afdrukken en eindstand moeten al geschreven zijn en werken !!!!}}

\vspace*{-0.8cm}
\item

{\bf Volgend werkcollege:}
\\
donderdag 27 februari 2014, 11:15--13:00, zaal 306/308, 303:
werken aan de eerste programmeeropdracht

\vspace*{-0.8cm}
\item

{\bf Uitwerking bomenpracticum:}
\\
binnenkort op http://www.liacs.nl/home/graaf/ALGO/

\vspace*{-0.8cm}
\item

{\bf Opgaven:}
\\
zie http://www.liacs.nl/home/graaf/ALGO/

\vspace*{-0.8cm}
\item

{\bf Volgend college:}
\\
vrijdag 28 februari 2014, 11:15--13:00, zaal B2

\end{itemize}
 \end{slide}

\end{document}



\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Raadsel}}
\vspace{3mm}
\hrule
%tweede college
\bigskip
Gegeven heel veel platte stenen, die aan de ene kant zwart zijn en aan de andere kant wit.
Iemand legt, zonder dat jij het ziet (je hebt een blinddoek voor je ogen), de stenen op de tafel
neer. Je krijgt van die persoon te horen dat er precies 50 stenen met de witte kant boven liggen;
de andere hebben de zwarte kant boven.

Jij moet er, geblinddoekt, voor zorgen dat er twee groepen stenen komen, met in 
beide groepen evenveel stenen die met de witte kant
boven liggen.\\
Vraag: hoe kun je dat voor elkaar krijgen?
\vfill
 \end{slide}





\end{document}






\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Tijdcomplexiteit}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\textcolor{red}{Complexiteit} (= tijdcomplexiteit) van een algoritme:
\begin{itemize}
\item
\vspace{-0.5cm}
= hoeveelheid werk verricht door het algoritme
\item
\vspace{-0.5cm}
hangt meestal af van de grootte van de invoer: hoe groter de invoer, hoe groter de complexiteit
\item
\vspace{-0.5cm}
wordt bepaald door het aantal keer dat de \textcolor{red}{basisoperatie} wordt uitgevoerd
\item
\vspace{-0.5cm}
het belangrijkste is de (asymptotische) groei
\item
\vspace{-0.5cm}
wordt vaak uitgedrukt in \textcolor{red}{O-notatie} (orde van grootte)
\item
\vspace{-0.5cm}
hangt vaak ook af van het soort invoer: \textcolor{red}{worst case, best case, average case}
\end{itemize}

  \vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Maximum}}
\vspace{3mm}
\hrule
%derde college
\bigskip
{\bf Voorbeeld 1}:

\vspace{-0.3cm}
\verb+// invoer: array +$a[0 \cdots n-1]$\verb+ bestaande uit +$n$\verb+ reals+\\
\verb+// uitvoer: de grootste waarde+

\vspace{-0.3cm}
\begin{tabbing}
XXXX\=XXX\=XXX\=XXX\=XXX\=XXX\kill
    \> {\tt max} $:= a[0]$;\\
    \> {\bf for} $i := 1$ {\bf to} $n-1$ {\bf do} \\
    \>   \> {\bf if} ( $ a[i] > $ {\tt max} ) {\bf then} $\longleftarrow$ \textcolor{red}{basisoperatie}\\
    \>   \>    \> {\tt max} $:= a[i]$;\\
    \>   \> {\bf fi}\\
    \> {\bf od}\\
    \> {\bf return} {\tt max};
\end{tabbing}

\textcolor{red}{Complexiteit}: $C(n) = n-1 \in \Theta(n)$
\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{Uniciteit}}
\vspace{3mm}
\hrule
%derde college
\bigskip
\vspace{-0.2cm}
{\bf Voorbeeld 2}:

\vspace{-0.4cm}
\verb+// invoer: array +$a[0 \cdots n-1]$\verb+ bestaande uit +$n$\verb+ reals+\\
\verb+// uitvoer: true als alle +$n$ \verb+waarden verschillen+

\vspace{-0.4cm}
%\begin{small}
\begin{tabbing}
XXXX\=XXX\=XXX\=XXX\=XXX\=XXX\kill
    \> {\bf for} $i := 0$ {\bf to} $n-2$ {\bf do} \\
    \>   \> {\bf for} $j:= i+1$ {\bf to} $n-1$ {\bf do}\\
    \>   \>    \> {\bf if} ( $a[i] = a[j]$ ) {\bf then} $\longleftarrow$
    \textcolor{red}{basisoperatie}\\
    \>   \>    \>   \> {\bf return} false; {\bf fi}\\
    \>   \> {\bf od}\\
    \> {\bf od}\\
    \> {\bf return} true;
\end{tabbing}
%\end{small}

\vspace{-0.2cm}
\textcolor{red}{Best case} complexiteit: $B(n) = 1 \in \Theta(1)$

\vspace{-0.5cm}
\textcolor{red}{Worst case} complexiteit: $$W(n) = \sum_{i=0}^{n-2}(n-1-i) = \frac{1}{2}n(n-1) \in
\Theta(n^2)$$

\vfill
\end{slide}






\begin{slide}
\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{O-notatie}}
\vspace{3mm}
\hrule
%derde college
\bigskip

O-notatie beschrijft het asymptotisch gedrag:

\textcolor{red}{$ f \in O(g)$} $\iff {}$
$\exists c > 0$ en $\exists n_0 \geq 0$
  zodat $\forall n > n_0$:

\vspace{-0.5cm}
\hspace{5.2cm} $f(n) \leq c \cdot g(n)$


$\textcolor{red}{ f \in \Omega(g)} \iff {}$
$\exists c' > 0$ en $\exists n_0 \geq 0$
  zodat $\forall n > n_0$:

\vspace{-0.5cm}
\hspace{5.2cm} $f(n) \geq c' \cdot g(n)$

$\textcolor{red}{ f \in \Theta(g)} \iff {}$
$\exists c_1,c_2 > 0$ en $\exists n_0 \geq 0$
  zodat $\forall n > n_0$:

\vspace{-0.5cm}
\hspace{5.2cm} $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$

  \smallskip
Aangezien zowel $f$ als $g$ in onze toepassingen de complexiteit van een
algoritme voorstelt is
hier steeds $f>0$ en $g>0$.

\vfill
\end{slide}


\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{O}}
\vspace{3mm}
\hrule
%derde college
\bigskip
%\begin{center}
\includegraphics[scale=0.75]{big-oh.eps}

\hspace{2cm} {$ t \in O(g)$}: $t(n)$ groeit niet sneller dan $g(n)$


%\end{center}

\vfill
\end{slide}

\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{$\Omega$}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\includegraphics[scale=0.75]{big-omega.eps}

{$ t \in \Omega(g)$}: $t(n)$ groeit minstens zo snel als $g(n)$

\vfill
\end{slide}

\begin{slide}

\vspace{1mm}
%algoritmiek
Algoritmiek 2014/03
\hfill{\bf \textcolor{blue}{$\Theta$}}
\vspace{3mm}
\hrule
%derde college
\bigskip

\vspace{-0.5cm}
\includegraphics[scale=0.75]{big-theta.eps}

\vspace{-0.6cm}
\hspace{1cm} {$ t \in \Theta(g)$}: $t(n)$ groeit even snel als $g(n)$

\vfill
\end{slide}


\end{document}
