dm.tex

%%
% Copyright (c) 2017 - 2021, Pascal Wagler;
% Copyright (c) 2014 - 2021, John MacFarlane
%
% All rights reserved.
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions
% are met:
%
% - Redistributions of source code must retain the above copyright
% notice, this list of conditions and the following disclaimer.
%
% - Redistributions in binary form must reproduce the above copyright
% notice, this list of conditions and the following disclaimer in the
% documentation and/or other materials provided with the distribution.
%
% - Neither the name of John MacFarlane nor the names of other
% contributors may be used to endorse or promote products derived
% from this software without specific prior written permission.
%
% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
% "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
% LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
% FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
% COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
% INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
% BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
% LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
% CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
% LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
% ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
% POSSIBILITY OF SUCH DAMAGE.
%%

%%
% This is the Eisvogel pandoc LaTeX template.
%
% For usage information and examples visit the official GitHub page:
% https://github.com/Wandmalfarbe/pandoc-latex-template
%%

% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
\PassOptionsToPackage{dvipsnames,svgnames*,x11names*,table}{xcolor}
%
\documentclass[
  paper=a4,
  ,captions=tableheading
]{scrartcl}
\usepackage{amsmath,amssymb}
\usepackage{lmodern}
\usepackage{setspace}
\setstretch{1.2}
\usepackage{ifxetex,ifluatex}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\definecolor{default-linkcolor}{HTML}{A50000}
\definecolor{default-filecolor}{HTML}{A50000}
\definecolor{default-citecolor}{HTML}{4077C0}
\definecolor{default-urlcolor}{HTML}{4077C0}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  pdftitle={Algorithmique et optimisation discrète},
  pdfauthor={Maxime NEMO},
  hidelinks,
  breaklinks=true,
  pdfcreator={LaTeX via pandoc with the Eisvogel template}}
\urlstyle{same} % disable monospaced font for URLs
\usepackage[margin=2.5cm,includehead=true,includefoot=true,centering,]{geometry}
% add backlinks to footnote references, cf. https://tex.stackexchange.com/questions/302266/make-footnote-clickable-both-ways
\usepackage{footnotebackref}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering

% Make use of float-package and set default placement for figures to H.
% The option H means 'PUT IT HERE' (as  opposed to the standard h option which means 'You may put it here if you like').
\usepackage{float}
\floatplacement{figure}{H}

\usepackage{algorithm,algpseudocode}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{listings}

\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\ifluatex
  \usepackage{selnolig}  % disable illegal ligatures
\fi

\title{Algorithmique et optimisation discrète}
\usepackage{etoolbox}
\makeatletter
\providecommand{\subtitle}[1]{% add subtitle to \maketitle
  \apptocmd{\@title}{\par {\large #1 \par}}{}{}
}
\makeatother
\subtitle{DM 4MMAOD6 2021-2022}
\author{Maxime NEMO}
\date{15 novembre 2021}



%%
%% added
%%

%
% language specification
%
% If no language is specified, use English as the default main document language.
%

\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[shorthands=off,main=english]{babel}
\else
    % Workaround for bug in Polyglossia that breaks `\familydefault` when `\setmainlanguage` is used.
  % See https://github.com/Wandmalfarbe/pandoc-latex-template/issues/8
  % See https://github.com/reutenauer/polyglossia/issues/186
  % See https://github.com/reutenauer/polyglossia/issues/127
  \renewcommand*\familydefault{\sfdefault}
    % load polyglossia as late as possible as it *could* call bidi if RTL lang (e.g. Hebrew or Arabic)
  \usepackage{polyglossia}
  \setmainlanguage[]{english}
\fi



%
% for the background color of the title page
%
\usepackage{pagecolor}
\usepackage{afterpage}
\usepackage[margin=2.5cm,includehead=true,includefoot=true,centering]{geometry}

%
% break urls
%
\PassOptionsToPackage{hyphens}{url}

%
% When using babel or polyglossia with biblatex, loading csquotes is recommended
% to ensure that quoted texts are typeset according to the rules of your main language.
%
\usepackage{csquotes}

%
% captions
%
\definecolor{caption-color}{HTML}{777777}
\usepackage[font={stretch=1.2}, textfont={color=caption-color}, position=top, skip=4mm, labelfont=bf, singlelinecheck=false, justification=raggedright]{caption}
\setcapindent{0em}

%
% blockquote
%
\definecolor{blockquote-border}{RGB}{221,221,221}
\definecolor{blockquote-text}{RGB}{119,119,119}
\usepackage{mdframed}
\newmdenv[rightline=false,bottomline=false,topline=false,linewidth=3pt,linecolor=blockquote-border,skipabove=\parskip]{customblockquote}
\renewenvironment{quote}{\begin{customblockquote}\list{}{\rightmargin=0em\leftmargin=0em}%
\item\relax\color{blockquote-text}\ignorespaces}{\unskip\unskip\endlist\end{customblockquote}}

%
% Source Sans Pro as the de­fault font fam­ily
% Source Code Pro for monospace text
%
% 'default' option sets the default
% font family to Source Sans Pro, not \sfdefault.
%
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
    \usepackage[default]{sourcesanspro}
  \usepackage{sourcecodepro}
  \else % if not pdftex
    \usepackage[default]{sourcesanspro}
  \usepackage{sourcecodepro}

  % XeLaTeX specific adjustments for straight quotes: https://tex.stackexchange.com/a/354887
  % This issue is already fixed (see https://github.com/silkeh/latex-sourcecodepro/pull/5) but the
  % fix is still unreleased.
  % TODO: Remove this workaround when the new version of sourcecodepro is released on CTAN.
  \ifxetex
    \makeatletter
    \defaultfontfeatures[\ttfamily]
      { Numbers   = \sourcecodepro@figurestyle,
        Scale     = \SourceCodePro@scale,
        Extension = .otf }
    \setmonofont
      [ UprightFont    = *-\sourcecodepro@regstyle,
        ItalicFont     = *-\sourcecodepro@regstyle It,
        BoldFont       = *-\sourcecodepro@boldstyle,
        BoldItalicFont = *-\sourcecodepro@boldstyle It ]
      {SourceCodePro}
    \makeatother
  \fi
  \fi

%
% heading color
%
\definecolor{heading-color}{RGB}{40,40,40}
\addtokomafont{section}{\color{heading-color}}
% When using the classes report, scrreprt, book,
% scrbook or memoir, uncomment the following line.
%\addtokomafont{chapter}{\color{heading-color}}

%
% variables for title, author and date
%
\usepackage{titling}
\title{Algorithmique et optimisation discrète}
\author{Maxime NEMO}
\date{15 novembre 2021}

%
% tables
%

%
% remove paragraph indention
%
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em}  % prevent overfull lines

%
%
% Listings
%
%


%
% header and footer
%
\usepackage[headsepline,footsepline]{scrlayer-scrpage}

\newpairofpagestyles{eisvogel-header-footer}{
  \clearpairofpagestyles
  \ihead[15 novembre 2021]{Algorithmique et optimisation discrète}
  \chead[]{}
  \ohead[Algorithmique et optimisation discrète]{15 novembre 2021}
  \ifoot[\thepage]{Maxime NEMO}
  \cfoot[]{}
  \ofoot[Maxime NEMO]{\thepage}
  \addtokomafont{pageheadfoot}{\upshape}
}
\pagestyle{eisvogel-header-footer}

%%
%% end added
%%

\begin{document}

%%
%% begin titlepage
%%
\begin{titlepage}
\newgeometry{left=6cm}
\newcommand{\colorRule}[3][black]{\textcolor[HTML]{#1}{\rule{#2}{#3}}}
\begin{flushleft}
\noindent
\\[-1em]
\color[HTML]{000000}
\makebox[0pt][l]{\colorRule[0039A6]{1.3\textwidth}{2pt}}
\par
\noindent

{
  \setstretch{1.4}
  \vfill
  \noindent {\huge \textbf{\textsf{Algorithmique et optimisation
discrète}}}
    \vskip 1em
  {\Large \textsf{DM 4MMAOD6 2021-2022}}
    \vskip 2em
  \noindent {\Large \textsf{Maxime NEMO}}
  \vfill
}


\textsf{15 novembre 2021}
\end{flushleft}
\end{titlepage}
\restoregeometry

%%
%% end titlepage
%%



{
\setcounter{tocdepth}{2}
\tableofcontents
\newpage
}
\hypertarget{pruxe9ambule}{%
\paragraph{Préambule}\label{pruxe9ambule}}

Je certifie que ce travail est le fruit de mon travail personnel
exclusivement

\hypertarget{analyse-des-duxe9fauts-de-cache}{%
\section{Analyse des défauts de
cache}\label{analyse-des-duxe9fauts-de-cache}}

Le comportement d'un algorithme dépend très fortement de son
implémentation. En effet, chaque choix d'implémentation fera que le
programme a un coût d'exécution différent. Le coût d'un programme peut
être mesuré grâce au nombre d'opérations (le travail), ou bien grâce à
l'espace mémoie qu'il utilise, ou bien encore par sa localité (le nombre
de défauts de cache). En effet, les données utiles pour son exécutions
sont rapide à accéder lorsqu'elles sont présentes dans le cache, mais
bien moins rapide lorsque celles-ci sont absentes.\\
Le modèle qu'on va retenir pour le cache est le modèle LRU (Least
Recently Used). Cette politique a au plus 2 fois plus de défauts de
cache qu'une politique optimale. On va utiliser le modèle CO pour
l'analyse des défauts de cache. Celui ci consiste à supposer qu'on a un
cache de taille Z, utilisant des blocs de taille L et avec une politique
LRU.\\
Le but sera alors de trouver le nombre de défauts de cache, de concevoir
un algorithme qui utilise les valeurs de Z et de L pour faire moins de
défauts, et puis enfin de construire un programme qui ne fait pas trop
de défauts, quelles que soient les valeurs Z et L, qui sera alors bon
sur toutes les machines.\\
\hspace*{0.333em}

\emph{Exemple 1:}\\
Prenons l'algorithme naïf suivant, que nous allons analyser et améliorer
petit à petit.

\begin{algorithm}[H]
\caption{Example 1}
\begin{algorithmic}[1]
\Require{$A$ and $B$ two matrix of size $n \times n$} 
\Ensure{$C$ a matrix of size $n \times n$}
\Statex
 
  \For{$i=0; i<n; i++$}
    \For{$j=0; j<n; j++$}
      \State $c_{i,j} \gets a_{i,j} \times b_{j,i}$
    \EndFor
  \EndFor
\end{algorithmic}
\end{algorithm}

Calculons le nombre de défauts de cache dans le cadre de notre modèle
CO.\\
Pour cela, on va faire plusieurs hypothèses :

\begin{itemize}
\item
  Si \(Z\) est très grand (\(Z = \infty\)) :\\
  Alors on va faire \(\frac{n \times n}{L}\) défauts sur A,
  \(\frac{n \times n}{L}\) défauts sur B, \(\frac{n \times n}{L}\)
  défauts sur C\\
  On fait alors \(\frac{3n^2}{L}\) défauts de cache
\item
  Si \(Z\) est très petit, alors, en notant \(Q\) le nombre de défauts
  de cache,\\
  \(Q(n, L, Z) = \underbrace{ \frac{n^2}{L}}_{Sur A} + \underbrace{\frac{n^2}{L}}_{Sur C} + \underbrace{n^2}_{sur B} \approx n^2\).
\end{itemize}

On remarque alors que sous les deux hypothèses précédentes, le résultat
n'est pas le même, cela signifie que notre algorithme n'est pas
optimisé.

~\\
L'organisation des données a un effet sur les performances. En effet,
l'algorithme précédent lit les éléments de \(A\) de manière contiguë et
écrit les éléments de \(C\) de manière contiguë, c'est-à-dire selon le
sens du stockage, mais ce n'est pas le cas pour la lecture des éléments
de \(B\). Il s'agit ici d'un problème de la localité spatiale. Celle-ci
n'étant pas bonne pour \(B\), il va falloir régler cela. Il existe aussi
des problèmes de localité temporelle, c'est-à-dire que l'on accède aux
données proches dans la mémoire de façon espacée dans le temps. La
solution est de faire un parcours selon le sens de stockage autant que
possible.\\
Une première optimisation serait de transformer notre algorithme naïf en
algorithme cache-aware. C'est-à-dire un programme qui est optimal en
terme de défauts de cache mais qui utilise les valeurs de Z et de L pour
cela.\\
On va utiliser des techniques de blocking. Cela consiste en
l'amélioration de la localité en effectuant un parcours des matrices par
blocs qui tiennent dans le cache.\\
On se limite volontairement au blocs rectangulaire. On pourrait très
bien immaginer des blocs de formes plus complexes.

On va alors travailler par bloc de taille \(\alpha \times \beta\)\\
\textbf{Méthode générale : cache-aware}\\
Supposons \(\alpha\) et \(\beta\) entiers tels que les calculs effectués
dans le bloc se fassent sans que le cache soit plein si il était
initialement vide.\\
Pour les calculs suivant, on suppose que le cache est toujours alligné
pour simplifier.\\
On va calculer le nombre de défaut de cache par bloc, puis le multiplié
par le nombre de bloc que l'on va devoir explorer. Si cette valeur est
assymptofiquement la même que l'optimal qu'on avait trouvé avec
l'algorithme naïf, alors on a produit un algorithme cache-aware.

\textbf{Application :} On a alors \#défaut de cache par bloc =
\(\underbrace{ \beta\lceil \frac{\alpha}{L}\rceil}_{sur A}+ \underbrace{\beta\lceil \frac{\alpha}{L}\rceil}_{sur C} + \underbrace{ \alpha\lceil \frac{\beta}{L}\rceil}_{sur B}\)\\
On a donc finalement :
\(Q(n,L,Z) \approx \frac{n}{\alpha} \times \frac{n}{\beta} \times \frac{3 \alpha\beta}{L} = \Theta(\frac{n^2}{L})\)
qui est bien l'optimal que l'on avait trouvé (quand \(Z = \infty\)) On
peut aussi en déduire que \(\alpha = \beta \approx \sqrt{\frac{Z}{3}}\),
avec \(\alpha = \beta \leq \sqrt{\frac{Z}{3}}\)\\
On peut alors construire un algorithme cache-aware qui va effectuer les
calculs par blocs (boucle \emph{for} sur les blocs). On peut alors créer
\protect\hyperlink{algorithm5}{\emph{Algorithm 5} en annexe}

~

On a trouvé un algorithme qui, asymptotiquement, est toujours optimal,
mais celui-ci dépend de Z et de L, et donc un seul et même algorithme ne
peux pas etre optimal sur toutes les machines puisque Z et L seront
différents. La prochaine étape est alors de créer un algorithme
cache-oblivious.\\
\textbf{Méthode générale : cache-oblivious}\\
On va effectuer du blocking récursif, c'est-à-dire découper
récursivement en blocs plus petits jusqu'à ce que la résolution d'un
sous-problème tient dans le cache.\\
\textbf{Application :} \protect\hyperlink{algorithm6}{\emph{Algorithm 6}
en annexe}

\hypertarget{cas-des-algorithmes-ruxe9cursifs}{%
\section{Cas des algorithmes
récursifs}\label{cas-des-algorithmes-ruxe9cursifs}}

La programmation récursive peut amener à des \textbf{calculs redondants}
qui les rendent très mauvais niveau performance. Il est alors possible
d'éliminer les redondances en suivant la méthode suivante:

\begin{itemize}
\tightlist
\item
  Trouver les calculs redondants en analysant les dépendances entre
  instructions avec un graphe d'appel par exemple.\\
\item
  Éliminer ces calculs grâce à :

  \begin{itemize}
  \tightlist
  \item
    Soit de la mémoïsation, c'est-à-dire mémoriser le résultat d'un
    appel pour pouvoir s'en servir plus tard si on a encore besoin du
    résultat. Pour cela, on utilise généralement des tables de hash ou
    des tableaux.
  \item
    Soit passer à de la programmation itérative avec ordonnancement
    topologique, c'est-à-dire effectuer les calculs nécéssaires dans un
    sens tel que l'on ait déjà effectué (et mémorisé) les valeurs
    intermédiaires nécéssaires à chaque calcul avant de le faire.
  \end{itemize}
\end{itemize}

\emph{Exemple 2 :} Soit la fonction \(f\) définie ci-dessous

\begin{algorithm}[H]
\caption{Example 2}
\begin{algorithmic}[4]
\Require{int $x$} 
\Ensure{$res$ the result}
\Function{$f$}{$x$}
    \If{ $x = 0$}
      \State Return 1
    \EndIf
    \State $res = 0$
    \For{$i=0; i<x; i++$}
      \State $res = res + f(i)$
    \EndFor
  \State Return $res$
\EndFunction
\end{algorithmic}
\end{algorithm}

On remarque qu'il y a beaucoup de calculs redondants (tous les \(f(i)\)
avec \(i<x\)).\\
La première amélioration est d'utiliser de la mémoïsation. On applique
la méthode générale de mémoïsation, c'est-à-dire de regarder si le
calcul n'aurait pas déjà été fait précédement.

\begin{algorithm}[H]
\caption{Example 2 - memorization}
\begin{algorithmic}[5]
\Require{int $x$} 
\Ensure{$res$ the result}
\Statex
\State $T$ = [] a hashmap
  \Function{$f$}{$x$}
    \If{ $x = 0$}
      \State Return 1
    \EndIf
    \State $res = 0$
    \For{$i=0; i<x; i++$}
      \If key $i$ in $T$
        \State $val = T[i]$
      \Else
        \State $val = f(i)$
      \EndIf
      \State $res = res + val$
    \EndFor
  \State Return $res$
  \EndFunction
\end{algorithmic}
\end{algorithm}

~

En faisant une analyse des dépendances entre instructions avec un graphe
d'appels de \(f\), on se rend compte que \(f(x)\) dépends seulement de
\(f(i), i<x\). On peut alors créer une version itérative de notre
algorithme en calculant les instructions qui ne dépendent en premier de
rien, puis les instructions qui dépendent de rien des des instructions
qu'on vient de calculer etc\ldots{}

On obtient alors l'algorithme suivant :

\begin{algorithm}[H]
\caption{Example 2 - iterative}
\begin{algorithmic}[6]
\Require{int $x$} 
\Ensure{$res$ the result}
\Statex
  \Function{$f$}{$x$}
    \State $T$ = [x]
    \State $T[0] = 1$
    \For{$i=1; i<=x; i++$}
      \State $s=0$
      \For{$j = 0; j<i; j++$}
        \State $s = s + T[j]$
      \EndFor
      \State $T[i] = s$
    \EndFor
  \EndFunction
\end{algorithmic}
\end{algorithm}

On a appliqué simplement la méthode, il est évident que dans notre cas,
l'algorithme peut encore être simplifié, mais pas au niveau de la
redondance des calculs de \(f(i)\) puisque, chaque \(f(i)\) n'est
calculé qu'une et une seule fois.

~\\
\hspace*{0.333em}

\hypertarget{programmation-dynamique}{%
\section{Programmation dynamique}\label{programmation-dynamique}}

Pour résoudre des problèmes plus complexes, il est parfois pratique
d'utiliser de la programmation dynamique. On peut modéliser un problème
par une équation de Bellman lorsque :

\begin{itemize}
\tightlist
\item
  Une solution optimale peut s'exprimer de façon récursive\\
\item
  Et la formule récursive réduit le problème général en sous-problèmes
  dont on va chercher la solution optimale.
\end{itemize}

Une fois l'équation de Bellman trouvée, on peut créer un programme
récursif utilisant cette équation. On peut alors ensuite utiliser les
méthodes d'optimisation des programmes récursifs évoqués précédemment.

~\\
\hspace*{0.333em}

\emph{Exemple 3: (inspiré d'un énoncé de l'ENS Lyon)}\\
On veut construire une tour la plus haute possible à partir de
différentes briques. On dispose de n types de briques et d'un nombre
illimité de briques de chaque type. Chaque brique de type \(i\) a une
longueur \(x_i\) une largeur \(y_i\) et une hauteur \(z_i\). Chaque
brique doit être posée sur la base \(x,y\) Dans la construction de la
tour, une brique ne peut être placée au dessus d'une autre que si les
deux dimensions de la base de la brique du dessus sont strictement
inférieures aux dimensions de la rangée de briques du dessous

\emph{Solution :}\\
Entrées :\\
\(L_{base}\) la longueur de la base ; \(l_{base}\) la largeur de la base
; les types de briques\\
Equation de Bellman :

Si il existe une brique compatible :\\
\(h_{max}(L_{base}, l_{base}) = \underset{\textrm{type } i ; y_i < l_{base} ; x_i < L_{base}} {\max}( z_i + h_{max}( (L_{base}//x_i ) \times x_i, y_i)\)\\
\(h_{max}(L_{base}, l_{base}) = 0\) si aucune brique ne respecte les
conditions du max

On peut alors créer le \protect\hyperlink{exemple3}{\emph{code fournis
en annexe}}.

~

Une autre méthode pour gérer les probèmes d'optimisation est de faire du
\textbf{Branch \& Bound}, qui est utilie lorsqu'on a un problème de
minimisation ou de maximisation. Cette technique est divisée en 2
parties.

\begin{itemize}
\tightlist
\item
  La \emph{séparation}, qui conciste à diviser le problème initial en
  sous problèmes. L'ensemble des potientielles solutions des sous
  problèmes doit recouvir l'ensemble des potentielles solutions du
  problème initial. On va résoudre ces sous problèmes grâce à
  l'évalutation. On pourra, si besoin, séparer encore les sous problèmes
  en sous sous problèmes etc\ldots{}
\item
  L'\emph{évaluation} conciste à résoudre un des problèmes. On peut le
  résoudre de deux façons. Soit on trouve une solution optimale au
  problème considéré en regardant les solutions du problème ou en
  utilisant les sous solutions des sous problèmes. Soit on prouve qu'il
  n'existe pas de solution optimale (meilleure que celle qu'on pourrait
  déjà avoir éventuellement trouvé précédement), et donc il est inutile
  d'explorer ce problème et ses sous problèmes.
\end{itemize}

Je comprends la notion de Branch \& Bound mais je ne la maitrise pas
assez pour pouvoir créer un exemple et l'appliquer correctement dessus.

\hypertarget{annexes}{%
\section{Annexes}\label{annexes}}

\hypertarget{algorithm5}{%
\paragraph{}\label{algorithm5}}

\begin{algorithm}[H]
\caption{Example 1 - Cache-Aware}
\begin{algorithmic}[2]
\Require{$A$ and $B$ two matrix of size $n \times n$} 
\Ensure{$C$ a matrix of size $n \times n$}
\Statex
 
  \For{$I=0; I<n; I+=\alpha$}
    \State int $i_{max} \gets \min(I+\alpha, m)$
    \For{$J=0; J<n; J+=\alpha$}
      \State int $j_{max} \gets \min(J+\alpha, m)$
      \For{$i=I; i<i_{max}; i++$}
        \For{$j=J; j<j_{max}; j++$}
        \State $c_{i,j} \gets a_{i,j} \times b_{j,i}$
        \EndFor
      \EndFor
    \EndFor
  \EndFor
\end{algorithmic}
\end{algorithm}

\hypertarget{algorithm6}{%
\paragraph{}\label{algorithm6}}

\begin{algorithm}[H]
\caption{Example 1 - Cache-Oblivious}
\begin{algorithmic}[3]
\Require{$A$ and $B$ two matrix of size $n \times n$, $T$ a threshold, $a$, $b$ two indexes initially = 0, $c$, $d$ two indexes initially = $n$} 
\Ensure{$C$ a matrix of size $n \times n$}
\Statex
\Function{$f_{rec}$}{$a,b,c,d$}
  \State $NbLine \gets b-a$
  \State $NbCol \gets d-c$
  \If {$NbLine < T$ and $NbCol < T$}
    \For{$i=a; i<b; i++$}
      \For{$j=c; j<d; j++$}
        \State $c_{i,j} \gets a_{i,j} \times b_{j,i}$
      \EndFor
    \EndFor
  \Else
    \If { $NbLine > NbCol$}
      \State $f_{rec}(a+NbLine/2, b, c, d)$
      \State $f_{rec}(a, b+NbLine/2, c, d)$
    \Else
      \State $f_{rec}(a, b, c+NbCol/2, d)$
      \State $f_{rec}(a, b, c, d+NbCol/2)$
    \EndIf
  \EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\hypertarget{exemple-3-algorithme}{%
\paragraph{Exemple 3 : Algorithme}\label{exemple-3-algorithme}}

\hypertarget{exemple3}{%
\paragraph{}\label{exemple3}}

\lstinputlisting[language=Python]{exemple3.py}

\end{document}