\documentclass{article}
\usepackage{amssymb, amsmath, geometry, multicol, stmaryrd}
\usepackage{listings, xcolor}
\usepackage[utf8]{inputenc}

\definecolor{red}{rgb}{0.8, 0.0, 0.0}
\definecolor{green}{rgb}{0.0, 0.8, 0.0}
\definecolor{blue}{rgb}{0.0, 0.0, 0.8}
\definecolor{orange}{rgb}{0.8, 0.5, 0.0}
\definecolor{lightgreen}{rgb}{0.6, 0.9, 0.6}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{white},
    commentstyle=\color{orange},
    keywordstyle=\color{blue},
    numberstyle=\tiny\color{blue},
    basicstyle=\footnotesize\ttfamily,             
    captionpos=b,
    numbers=none,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=4
}
\lstset{style=mystyle,
        mathescape=true,
        frameround=fttt,
        frame=trBL, 
        linewidth=15cm,
        aboveskip=5pt,
        belowskip=15pt,
        morecomment=[l][\color{orange}]{\#},
        keywords={, Si, Sinon, Tant, que, Retourner, alors, faire, Pour, tout, allant, de}
}

\geometry{tmargin=.7in, bmargin=.75in, lmargin=.75in, rmargin = .75in}

\begin{document}
\setlength{\parindent}{0mm}

\title{Algorithmes à connaître}
\author{Aubin SIONVILLE}
\date{MPI Clemenceau - 2021-2023}
\maketitle

\section*{Bases}

    \subsection*{Algorithme de recherche dichotomique}
    Entrées : un tableau T trié et un élément x\\
    Sortie : l'indice de l'élément x dans le tableau T ou -1 Si x n'est pas dans T \\
    Complexité : $\mathcal{O}(\log n)$
    \begin{lstlisting}
    $\underline{\mathrm{Dichotomie}}$ (T, x) :
        debut $\gets$ 1
        fin $\gets$ longueur(T)
        Tant que debut $\leq$ fin faire
            milieu $\gets$ (debut + fin) / 2
            Si T[milieu] = x alors
                Retourner milieu
            Sinon Si T[milieu] < x alors
                debut $\gets$ milieu + 1
            Sinon
                fin $\gets$ milieu - 1
        Retourner -1
    \end{lstlisting}

    \subsection*{Exponentiation rapide}
    Entrée : un entier n et un entier positif p\\
    Sortie : $\mathrm{n}^\mathrm{p}$ \\
    Complexité : $\mathcal{O}(\log p)$
    \begin{lstlisting}
    $\underline{\mathrm{ExpoRapide}}$ (n, p) :
        Si p = 0 alors
            Retourner 1
        Sinon Si p = 1 alors
            Retourner n
        Sinon Si p est pair alors
            Retourner $\mathrm{ExpoRapide}$ (n*n, p/2)
        Sinon
            Retourner $\mathrm{ExpoRapide}$ (n*n, (p-1)/2) * n
    \end{lstlisting}

    \subsection*{Algorithme d'Euclide}
    Entrées : deux entiers a et b\\
    Sortie : le PGCD de a et b \\
    Complexité : $\mathcal{O}(\log \min(a, b))$
    \begin{lstlisting}
    $\underline{\mathrm{PGCD}}$ (a, b) :
        Tant que b $\neq$ 0 faire
            t $\gets$ b
            b $\gets$ a $\mathrm{mod}$ b
            a $\gets$ t
        Retourner a
    \end{lstlisting}

\section*{Algos de tri}

    \subsection*{Tri par insertion}
    Entrée : un tableau T\\
    Sortie : le tableau T trié \\
    Complexité : $\mathcal{O}(n^2)$
    \begin{lstlisting}
    $\underline{\mathrm{TriInsertion}}$ (T) :
        n $\gets$ longueur(T)
        Pour i allant de 2 a n faire
            x $\gets$ T[i]
            j $\gets$ i - 1
            Tant que j $\geq$ 1 et T[j] > x faire
                T[j+1] $\gets$ T[j]
                j $\gets$ j - 1
            T[j+1] $\gets$ x
    \end{lstlisting}

    \subsection*{Tri par sélection}
    Entrée : un tableau T\\
    Sortie : le tableau T trié \\
    Complexité : $\mathcal{O}(n^2)$
    \begin{lstlisting}
    $\underline{\mathrm{TriSelection}}$ (T) :
        n $\gets$ longueur(T)
        Pour i allant de 0 a n-2 faire
            mini $\gets$ i
            Pour j allant de i+1 a n-1 faire
                Si T[j] < T[mini] alors
                    mini $\gets$ j
            Si mini $\neq$ i alors
                $\mathrm{Echanger}$ (T[mini], T[i])
    \end{lstlisting}

    \subsection*{Tri fusion}
    Entrée : un tableau T\\
    Sortie : le tableau T trié \\
    Complexité : $\mathcal{O}(n \log n)$
    \begin{lstlisting}
    $\underline{\mathrm{Fusion}}$ (T1, T2) :
        Si T1 est vide alors
            Retourner T2
        Si T2 est vide alors
            Retourner T1
        Si A[1] $\leq$ B[1] alors
            Retourner A[1] $\oplus$ $\mathrm{Fusion}$ (A[2..longueur(A)], B)
        Sinon
            Retourner B[1] $\oplus$ $\mathrm{Fusion}$ (A, B[2..longueur(B)])

    $\underline{\mathrm{TriFusion}}$ (T) :
        Si longueur(T) $\leq$ 1 alors
            Retourner T
        Sinon
            m $\gets$ longueur(T) / 2
            T1 $\gets$ $\mathrm{TriFusion}$ (T[1..m])
            T2 $\gets$ $\mathrm{TriFusion}$ (T[m+1..longueur(T)])
            Retourner $\mathrm{Fusion}$ (T1, T2)
    \end{lstlisting}

    \subsection*{Tri par tas}
    Entrée : un tableau T\\
    Sortie : le tableau T trié \\
    Complexité : $\mathcal{O}(n \log n)$
    \begin{lstlisting}
    $\underline{\mathrm{Entasser}}$ (T, i) :
        l $\gets$ $\mathrm{Gauche}$(i)
        r $\gets$ $\mathrm{Droite}$(i)
        maxi $\gets$ i
        Si l $\leq$ longueur(T) et T[l] > T[i] alors
            maxi $\gets$ l
        Si r $\leq$ longueur(T) et T[r] > T[i] alors
            maxi $\gets$ r
        Si maxi $\neq$ i alors
            $\mathrm{Echanger}$ (T[i], T[maxi])
            $\mathrm{Entasser}$ (T, maxi)

    $\underline{\mathrm{ConstruireTas}}$ (T) :
        Pour i allant de longueur(T)/2 a 1 faire
            $\mathrm{Entasser}$ (T, i)

    $\underline{\mathrm{TriTas}}$ (T) :
        $\mathrm{ConstruireTas}$ (T)
        Pour i allant de longueur(T) a 2 faire
            $\mathrm{Echanger}$ (T[1], T[i])
            longueur(T) $\gets$ longueur(T) - 1
            $\mathrm{Entasser}$ (T, i)
    \end{lstlisting}



\newpage



\section*{Algos des arbres}

    \subsection*{Parcours préfixe}
    Entrée : un arbre A\\
    Sortie : un tableau des sommets de A trié selon un parcours préfixe\\
    Complexité : $\mathcal{O}(|S|)$
    \begin{lstlisting}
    $\underline{\mathrm{ParcoursPrefixe}}$ (A) :
    visites $\gets$ []
    visites $\gets$ visites $\cup$ $\{A\}$
    Si filsGauche(A) $\neq$ $\varnothing$ alors
        visites $\gets$ visites $\cup$ $\mathrm{ParcoursPrefixe}$ (filsGauche(A))
    Si filsDroit(A) $\neq$ $\varnothing$ alors
        visites $\gets$ visites $\cup$ $\mathrm{ParcoursPrefixe}$ (filsDroit(A))
    Retourner visites
    \end{lstlisting}

    \subsection*{Parcours infixe}
    Entrée : un arbre A\\
    Sortie : un tableau des sommets de A trié selon un parcours infixe\\
    Complexité : $\mathcal{O}(|S|)$
    \begin{lstlisting}
    $\underline{\mathrm{ParcoursInfixe}}$ (A) :
        visites $\gets$ []
        Si filsGauche(A) $\neq$ $\varnothing$ alors
            visites $\gets$ visites $\cup$ $\mathrm{ParcoursInfixe}$ (filsGauche(A))
        visites $\gets$ visites $\cup$ $\{A\}$
        Si filsDroit(A) $\neq$ $\varnothing$ alors
            visites $\gets$ visites $\cup$ $\mathrm{ParcoursInfixe}$ (filsDroit(A))
        Retourner visites
    \end{lstlisting}

    \subsection*{Parcours suffixe}
    Entrée : un arbre A\\
    Sortie : un tableau des sommets de A trié selon un parcours suffixe\\
    Complexité : $\mathcal{O}(|S|)$
    \begin{lstlisting}
    $\underline{\mathrm{ParcoursSuffixe}}$ (A) :
    visites $\gets$ []
    Si filsGauche(A) $\neq$ $\varnothing$ alors
        visites $\gets$ visites $\cup$ $\mathrm{ParcoursSuffixe}$ (filsGauche(A))
    Si filsDroit(A) $\neq$ $\varnothing$ alors
        visites $\gets$ visites $\cup$ $\mathrm{ParcoursSuffixe}$ (filsDroit(A))
    visites $\gets$ visites $\cup$ $\{A\}$
    Retourner visites
    \end{lstlisting}

    \subsection*{Rotation gauche}
    Entrée : un arbre A\\
    Sortie : un arbre B tel que B est la rotation gauche de A\\
    Complexité : $\mathcal{O}(1)$
    \begin{lstlisting}
    $\underline{\mathrm{RotationGauche}}$ (A) :
        B $\gets$ filsDroit(A)
        filsDroit(A) $\gets$ filsGauche(B)
        filsGauche(B) $\gets$ A
        Retourner B
    \end{lstlisting}

    \subsection*{Rotation droite}
    Entrée : un arbre A\\
    Sortie : un arbre B tel que B est la rotation droite de A\\
    Complexité : $\mathcal{O}(1)$
    \begin{lstlisting}
    $\underline{\mathrm{RotationDroite}}$ (A) :
        B $\gets$ filsGauche(A)
        filsGauche(A) $\gets$ filsDroit(B)
        filsDroit(B) $\gets$ A
        Retourner B
    \end{lstlisting}


    
\newpage



\section*{Algos de graphes}

    \subsection*{Parcours en profondeur}
    Entrées : un graphe G=(S,A), un sommet s $\in$ S\\
    Sortie : un tableau des sommets de G trié selon un parcours en profondeur\\
    Complexité : $\mathcal{O}(|S| + |A|)$
    \begin{lstlisting}
    $\underline{\mathrm{ParcoursProfondeur}}$ (G, s) :
        visites $\gets$ []
        visites $\gets$ visites $\cup$ $\{s\}$
        Pour tout s' $\in$ voisins(s) faire
            $\mathrm{ParcoursProfondeur}$ (G, s')
    \end{lstlisting}

    \subsection*{Parcours en largeur}
    Entrées : un graphe G=(S,A), un sommet s $\in$ S\\
    Sortie : un tableau des sommets de G trié selon un parcours en largeur\\
    Complexité : $\mathcal{O}(|S| + |A|)$
    \begin{lstlisting}
    $\underline{\mathrm{ParcoursLargeur}}$ (G, s) :
        F $\gets$ FileVide
        visites $\gets$ []
        visites $\gets$ visites $\cup$ $\{s\}$
        $\mathrm{Enfiler}$(F, s)
        Tant que F est non vide faire
            s $\gets$ $\mathrm{Defiler}$(F)
            Pour tout s' $\in$ voisins(s) faire
                Si s' $\notin$ visites alors
                    visites $\gets$ visites $\cup$ $\{s'\}$
                    $\mathrm{Enfiler}$(F, s')
    \end{lstlisting}

    \subsection*{Tri préfixe}
    Entrées : un graphe G=(S,A), s $\in$ S, Res, Visites
    Sortie : Modifie Res et Visites pour que Res soit un parcours préfixe de Visites et des sommets accessibles depuis s\\
    Complexité : $\mathcal{O}(|S| + |A|)$
    \begin{lstlisting}
    $\underline{\mathrm{ExploreDescendant}}$ (G, s, Res, Visites) :
        todo $\gets$ PileVide
        $\mathrm{Empiler}$ (todo, (s, Succ(s)))
        Visites $\gets$ Visites $\cup$ $\{s\}$
        Tant que todo $\neq$ PileVide faire
            (x,l) $\gets$ $\mathrm{Depiler}$(todo)
            Si l = () alors
                Res $\gets$ x $\cdot$ Res
            Sinon
                t $\cdot$ l' $\gets$ l $\quad$#Separe la tete et le reste de la pile
                $\mathrm{Empiler}$ (todo, (x, l'))
                Si t $\notin$ Visites alors
                    Visites $\gets$ Visites $\cup$ $\{t\}$
                    $\mathrm{Empiler}$ (todo, (t, Succ(t)))

    $\underline{\mathrm{TriPrefixe}}$ (G, s) :
        Visites $\gets$ $\emptyset$
        Res $\gets$ $\emptyset$
        Tant que Visites$\setminus$S $\neq$ $\emptyset$ faire
            s $\gets$ un sommet de S$\setminus$Visites
            $\mathrm{ExploreDescendant}$ (G, s, Res, Visites)
        Retourner Res
    \end{lstlisting}

    \subsection*{Kosaraju}
    Entrées : un graphe G=(S,A)\\
    Sortie : les composantes fortement connexes de G\\
    Complexité : $\mathcal{O}(|S| + |A|)$
    \begin{lstlisting}
    $\underline{\mathrm{Kosaraju}}$ (G) :
        s $\gets$ un sommet de S
        T $\gets$ $\mathrm{TriPrefixe}$ (G, s)
        On parcoure G$^T$ en utilisant l'ordre de T comme points de regeneration.
        On retourne le plus petit partitionnement associe au parcours.
    \end{lstlisting}

    \subsection*{Kruskal}
    Entrées : un graphe G=(S,A) connexe\\
    Sortie : un arbre couvrant de poids minimal de G\\
    Complexité : $\mathcal{O}(|S| + |A|)$
    \begin{lstlisting}
    $\underline{\mathrm{Kruskal}}$ (G) :
        B $\gets$ $\emptyset$
        U $\gets$ $\emptyset$
        Tant que $\exists$ u,v tq u $\not\sim_B$ v faire
            $\{$x,y$\}$ $\in$ A$\setminus$U de poids minimal
            Si x $\sim_B$ y alors
                U $\gets$ U $\cup$ $\{\{$x,y$\}\}$
            Sinon
                U $\gets$ U $\cup$ $\{\{$x,y$\}\}$
                B $\gets$ B $\cup$ $\{\{$x,y$\}\}$
        Retourner T=(S, B)
    \end{lstlisting}

    \subsection*{Couplage biparti}
    Entrées : un graphe G=(S,A) biparti\\
    Sortie : un couplage maximal de G\\
    Complexité : $\mathcal{O}(|S| + |A|)$
    \begin{lstlisting}
        A faire
    \end{lstlisting}

    \subsection*{Dijkstra}
    Entrées : un graphe G=(S,A), un sommet s $\in$ S\\
    Sortie : Un tableau des distances minimales de s vers les autres sommets\\
    Complexité : $\mathcal{O}(|A| + |S| \log |S|)$
    \begin{lstlisting}
    $\underline{\mathrm{Djikstra}}$ (G, s) :
        distance $\gets$ [ $\infty$ pour tout s $\in$ S]
        file_priorite $\gets$ $\mathrm{FilePriorite}$()
        $\mathrm{Enfiler}$ (file_priorite, (0, s))

        Tant que file_priorite $\neq$ $\emptyset$ faire
            (d, u) $\gets$ $\mathrm{Defiler}$ (file_priorite)

            Pour tout v $\in$ Succ(u) faire
                Si distance[v] > distance[u] + $\mathrm{Poids}$(u,v) alors
                    distance[v] $\gets$ distance[u] + $\mathrm{Poids}$(u,v)
                    $\mathrm{Enfiler}$ (file_priorite, (distance[v], v))

        Retourner distance
    \end{lstlisting}


    \subsection*{Floyd Warshall}
    Entrées : un graphe G=(S,A)\\
    Sortie : Un tableau des distances minimales entre tous les sommets\\
    Complexité : $\mathcal{O}(|S|^3)$
    \begin{lstlisting}
    $\underline{\mathrm{FloydWarshall}}$ (G) :
        dist $\gets$ 0$_{M_{|S|,|S|}}$
        Pour tout a = (x,y) $\in$ A faire
            dist$_{x,y}$ $\gets$ $\mathrm{Poids}$(a)
        Pour tout x $\in$ S faire
            dist$_{x,x}$ $\gets$ 0
        Pour k allant de 1 a |S| faire
            Pour i allant de 1 a |S| faire
                Pour j allant de 1 a |S| faire
                    dist$_{i,j}$ $\gets$ min(dist$_{i,j}$, dist$_{i,k}$ + dist$_{k,j}$)
    \end{lstlisting}


\newpage


\section*{Algos de textes}

    \subsection*{Boyer-Moore}
    \begin{lstlisting}
        A faire
    \end{lstlisting}

    \subsection*{Rabin-Karp}
    Entrées : un texte T, un motif M\\
    Sortie : la liste des positions de M dans T\\
    Complexité : $\mathcal{O}(|T| + |M|)$ (max : $\mathcal{O}(|T| \times |M|)$)
    \begin{lstlisting}
    $\underline{\mathrm{RabinKarp}}$ (T, M) :
        L $\gets$ $\emptyset$
        n $\gets$ |T|
        m $\gets$ |M|
        hach$\_$n $\gets$ $\mathrm{Hachage}$(T[1..m])
        hach$\_$m $\gets$ $\mathrm{Hachage}$(M[1..m])
        Pour i allant de 0 a n-m+1 faire
            Si hach$\_$n = hach$\_$m alors
                Si T[i..i+m-1] = M alors
                    L $\gets$ L $\cup$ $\{i\}$
        Retourner L
    \end{lstlisting}
\newpage
    \subsection*{LZW}
    Entrées : un texte T\\
    Sortie : la liste des codes de T\\
    Complexité : $\mathcal{O}(|T|)$
    \begin{lstlisting}
    $\underline{\mathrm{LZWCompression}}$ (T) :
        L $\gets$ $\emptyset$
        dico $\gets$ $\emptyset$
        w $\gets$ ""
        Tant que il reste des caracteres a lire dans le texte, faire
            c $\gets$ prochain caractere
            p $\gets$ w $\cdot$ c
            Si p est dans le dico alors
                w $\gets$ p
            Sinon
                Ajouter p dans le dico
                L $\gets$ L $\cup$ dico(w)
                w $\gets$ c
        L $\gets$ L $\cup$ dico(w)
        Retourner L

    $\underline{\mathrm{LZWDecompression}}$ (Code, dico) :
        n $\gets$ |Code|
        L $\gets$ $\emptyset$
        v $\gets$ prochain(Code)
        L $\gets$ L $\cup$ v
        w $\gets$ char(v)

        Pour i allant de 2 a n faire
            k $\gets$ prochain(Code)
            Si k $\in$ dico alors
                input $\gets$ dico(k)
            Sinon
                input $\gets$ w $\cdot$ w[0]
            L $\gets$ L $\cup$ input
            dico $\gets$ dico $\cup$ w $\cdot$ input[0]
            w $\gets$ input
        Retourner L
    \end{lstlisting}


\newpage


\section*{Algos de logique}

    \subsection*{Algorithme de Quine}
    Entrées : $G$ une CNF, $p$ une variable propositionnelle et $b \in \mathbb{B}$\\
    Sortie : Une CNF équivalente à $G[p \mapsto b]$\\
    Complexité : $\mathcal{O}(|G|)$
    \begin{lstlisting}
    $\underline{\mathrm{Assume}}$ $(G, p, b)$ :
        Soit $\ell_V$ le litteral $p$ si $b=V$, $\neg p$ sinon
        Soit $\ell_F$ le litteral $\neg p$ si $b=V$, $p$ sinon
        Pour $C \in G$ faire
            Si $\ell_V \in C$ alors
                Supprimer $C$ de $G$
            Sinon 
                Si $\ell_F \in C$ alors
                Supprimer $\ell_F$ de $C$
        Retourner $G$
    \end{lstlisting}

    Entrée : $G$ une CNF\\
    Sortie : Oui si $G$ est satisfiable, Non sinon\\
    Complexité : $\mathcal{O}(|G|)$
    \begin{lstlisting}
    $\underline{\mathrm{Quine}}$ $(G)$ :
        Si $G=\emptyset$ alors
            Retourner Oui
        Sinon
            Si $\emptyset \in G$ alors
                Retourner Non
            Sinon Si $\exists \{\ell\} \in G$ alors
                Si $\ell = p$ avec $p \in \mathrm{vars}(G)$, alors
                    $\mathrm{Quine}(\mathrm{Assume}(G, p, V))$
                Sinon Si $\ell = \neg p$ avec $p \in \mathrm{vars}(G)$, alors
                    $\mathrm{Quine}(\mathrm{Assume}(G, p, F))$
            Sinon
                $p \gets h(G)$
                On essaie $\mathrm{Quine}(\mathrm{Assume}(G, p, V))$
                On essaie $\mathrm{Quine}(\mathrm{Assume}(G, p, F))$
    \end{lstlisting}

\newpage


\section*{Algos des languages/automates}

    \subsection*{Berry-Sethi}
    Entrée : Une expression régulière $e$\\
    Sortie : Un automate reconnaissant $\mathcal{L}(e)$\\
    Complexité : $\mathcal{O}(|e|)$
    \begin{lstlisting}
        On linearise $e$ en $f$ avec une fonction $\varphi$ telle que $f_\varphi = e$
        On calcule inductivement $\Lambda(f), S(f), P(f), F(f)$
        On fabrique $\mathcal{A} = (\Sigma, \mathcal{Q}, I, F, \delta)$ un automate reconnaissant $\mathcal{L}(f)$
        Retourner $\mathcal{A}_\varphi$
    \end{lstlisting}

\newpage


\section*{Algos d'apprentissage}

    \subsection*{K-moyennes}
    \begin{lstlisting}
        A faire
    \end{lstlisting}

    \subsection*{K plus proches voisins}
    Entrées : Un jeu de données classifiées $(S,c)$, un vecteur d'entrée $\overline{v}$\\
    Sortie : La classe de $\overline{v}$\\
    Complexité : $\mathcal{O}(|S|)$
    \begin{lstlisting}
    $\underline{\mathrm{kNN}}$ (S, c, $\overline{v}$) :
        On trie $S$ par distance croissante de $\overline{v}$ en $d_1, d_2, \dots, d_k, d_{k+1}, \dots$
        Soit $D$ un dictionnaire de classes de $\mathcal{C}$ vers $\mathbb{N}$ initialise a 0
        Pour i allant de 1 a k faire
            D[c(d_i)] $\gets$ D[c(d_i)] + 1
        Retourner la classe $c$ maximisant $D[c]$
    \end{lstlisting}

    \subsection*{Arbres K-dimensionnels}
    Entrées : Un jeu de données $\mathcal{V}$ et $i \in \llbracket 0, n-1 \rrbracket$ où $n$ est la dimension des données.\\
    Sortie : Un arbre k-dimensionnel $T$\\
    Complexité : $\mathcal{O}(|\mathcal{V}| \log |\mathcal{V}|)$
    \begin{lstlisting}
    $\underline{\mathrm{FabriqueArbreKD}}$ $(\mathcal{V}, i)$ :
        Si $\mathcal{V} = \emptyset$ alors
            Retourner $\mathrm{Vide}$
        Sinon
            On cherche $v \in \mathcal{V}$ tel que $v_i$ est la mediane de $\{u_i|u\in\mathcal{V}\}$
            Retourner $\mathrm{Noeud}\big( (v,i), \mathrm{FabriqueArbreKD}\big((\mathcal{V}\setminus\{v\})^{\geq_i v}, i + 1 \mod n\big)$,
                                $\mathrm{FabriqueArbreKD}\big((\mathcal{V}\setminus\{v\})^{\leq_i v}, i + 1 \mod n\big)\big)$
    \end{lstlisting}

    Entréés : Un arbre k-dimensionnel $T$, un vecteur ${v}$\\
    Sortie : La classe de $\overline{v}$\\
    Complexité : $\mathcal{O}(\log |\mathcal{V}|)$
    \begin{lstlisting}
    $\underline{\mathrm{RechercheKD}}$ ($T$, $\overline{v}$) :
        Si $T = \mathrm{Vide}$ alors
            Retourner $\mathrm{None}$
        Sinon
            $\mathrm{Noeud}\big((u,i),G,D\big)$ $\gets$ $T$
            Si $u_i \leq v_i$ alors
                $W \gets$ $\mathrm{RechercheKD}\big(D, {v}\big)$
                Si $W = \mathrm{None}$ alors
                    $W' \gets$ $\mathrm{RechercheKD}\big(G, {v}\big)$
                    Si $W' = \mathrm{None}$ alors
                        Retourner $\mathrm{Some}(u)$
                    Sinon
                        $\mathrm{Some}(z) \gets$ $W'$
                        Retourner le plus proche de $v$ entre $u$ et $z$
                Sinon
                    $\mathrm{Some}(w) \gets$ $W$
                    Si $v_i - u_i \leq d(v,w)$ alors
                        $W' \gets$ $\mathrm{RechercheKD}\big(G, {v}\big)$
                        Si $W' = \mathrm{None}$ alors
                            Retourner $\mathrm{Some}$(plus proche de $v$ entre $u$ et $w$)
                        Sinon
                            $\mathrm{Some}(z) \gets$ $W'$
                            Retourner $\mathrm{Some}$(plus proche de $v$ entre $u$, $w$ et $z$)
                    Sinon
                        Retourner $W$
            Sinon $Idem$
    \end{lstlisting}

    \subsection*{Algorithme HAC}
    Entrées : un ensemble de points $P$\\
    Sortie : un arbre de clustering\\
    Complexité : $\mathcal{O}(|P|^2)$
    \begin{lstlisting}
    $\underline{\mathrm{HAC}}$ (P) :
        $P \gets \{\{x\}|x \in \mathcal{D}\}$
        Tant que $|P| \geq 2$ et $Crit$, faire
            Soit $A,B \in P$ minimisant $D(A,B)$ avec $A \neq B$
            $P \gets (P \setminus \{A,B\}) \cup \{A \cup B\}$
        Retourner $P$
    \end{lstlisting}
    où $Crit$ est un critère sur le nombre de classes ou sur la valeur de la plus petite dissimilarité.

    \subsection*{Algorithme ID3}
    \begin{lstlisting}
        A faire
    \end{lstlisting}

\end{document}