931.tex

\documentclass{agregfiche}

\title{Leçon 931 - Schémas algorithmiques.  Exemples et applications.}

\begin{document}

\maketitle

\secrapports

\begin{rapport}{2018,2019}

Cette leçon permet au candidat de présenter différents schémas algorithmiques, en particulier « diviser
pour régner », programmation dynamique et approche gloutonne. Le candidat pourra choisir de se
concentrer plus particulièrement sur un ou deux de ces paradigmes. Le jury attend du candidat qu’il
illustre sa leçon par des exemples variés, touchant des domaines différents et qu’il puisse discuter les
intérêts et limites respectifs des méthodes. Le jury ne manquera pas d’interroger plus particulièrement le
candidat sur la question de la correction des algorithmes proposés et sur la question de leur complexité,
en temps comme en espace.

\end{rapport}

\begin{rapport}{2017 - rapport concernant la 902, diviser pour regner}
Cette leçon permet au candidat de proposer différents algorithmes utilisant le paradigme diviser pour
régner. Le jury attend du candidat que ces exemples soient variés et touchent des domaines différents.
Un calcul de complexité ne peut se limiter au cas où la taille du problème est une puissance exacte de
2, ni à une application directe d’un théorème très général recopié approximativement d’un ouvrage de
la bibliothèque de l’agrégation.
\end{rapport}

\begin{rapport}{2017 - rapport concernant la 907, programmation dynamique}
Même s’il s’agit d’une leçon d’exemples et d’applications, le jury attend des candidats qu’ils présentent
les idées générales de la programmation dynamique et en particulier qu’ils aient compris le caractère
générique de la technique de mémoïsation. Le jury appréciera que les exemples choisis par le candidat
couvrent des domaines variés, et ne se limitent pas au calcul de la longueur de la plus grande sous-
séquence commune à deux chaînes de caractères.
Le jury ne manquera pas d’interroger plus particulièrement le candidat sur la question de la correction
des algorithmes proposés et sur la question de leur complexité en espace.
\end{rapport}


\secindispensables
\begin{itemize}
    \item Approche gloutonne, diviser pour régner, programmation dynamique.
    \item Exemples (les plus classiques étant : algorithme de Dijkstra, tri fusion, plus longue sous-séquence commune).
\end{itemize}

\secasavoir

\begin{itemize}
    \item Des exemples moins classiques (Prim ou Kruskal, Hopcroft ou Karatsuba ou recherche de paires de points les plus proches ou FFT, multiplication de plusieurs matrices ou CYK,...  )
    \item Approche ascendante et descendante de la programmation dynamique.
    \item Calcul de complexité par formule de récurrence.
    \item Complexité en espace.
    \item Influence du schéma algorithmique sur les preuves de correction et de complexité.
\end{itemize}

\secidees

\begin{itemize}
    \item Des exemples de plus en plus compliqués.
    \item Problèmes d'optimisation et algorithmes approchés ?
\end{itemize}

\secpieges

\begin{itemize}
    \item Présenter les trois schémas et un unique exemple simple pour chacun risque de faire un plan peu intéressant, il faut probablement creuser l'un des schémas.
    \item On ne doit pas voir un catalogue de schémas et d'algorithme. Il faut absolument justifier les enchaînements, et les forces et faiblesses relative entre les différents paradigmes.
    \item Il faut maîtriser les ouvertures liés aux différents algorithmes présentés (prouver la correction, prouver la complexité, détails d'implémentation, est-ce le meilleur algorithme pour faire cela ?,\ldots).

\end{itemize}

\secquestionsclassiques

\begin{itemize}
    \item Donner un exemple d'algorithme glouton et d'entrée sur
    laquelle la solution optimale est atteinte ? Une sur laquelle
    elle n'est pas atteinte ?
%     rendu de monnaie sur pièce de  : 1, 2, 5, 10, 20, 50,  est
%optimale. rendu de monnaie sur 1,3,4 non optimal (6 = 4 + 1 + 1, vs
%6
%= 3+3
    \item Quelle est la différence entre diviser pour régner et la programmation dynamique ?
%    diviser pour régner = sous structure optimal
%   dynamique = sous structure optimal +  chevauchement des sous problèmes.
    \item Quelle est le lien entre la programmation dynamique et la mémoisation ? Quelles en sont les différences ?
      % mémoisation est un sous cas de la pro dynamique. En mémoïsant on a une approche top down alors qu'en programmation dynamique classique on a une approche bottom up.
    \item Avantages et désavantages de l'approche gloutonne ? De diviser pour régner, de la programmation dynamique ?
%    1) algorithme simple et efficace, mais ne retournant pas toujours une solution optimale
%   2) algorithme efficace, calcul simple de complexité, potentiellement parallélisable, mais stack overflow, et le choix du cas de base peux grandement changer la complexité. On résoud aussi potentiellement plusieurs fois le même problème.
%   3) la mémoïsation évite le problème précédent, mais induit un coup mémoire plus grand, limite la parallélisation et augmente les coup d'accès mémoire.
    \item Exemple de problème ne vérifiant pas la propriété de sous
    structure optimal ?
%  ceux où on ne peut pas faire de diviser pour régner. Cchemin le
%plus long dans un graphe, SAT
    \item Certaines structure de données sont-elles plus pertinentes
    que d'autres pour la mémoisation ?
%    table de hash et dictionnaire.
\end{itemize}

\secreferences

\begin{itemize}
    \item \input{refs/cormen}
    \item \input{refs/beauquier}
    \item \input{refs/kleinberg}
\end{itemize}

\secdev

\begin{itemize}
    \item[++] \input{dev/plsc}
    \item[++] \input{dev/tri_rapide}
    \item[+] \input{dev/primkruskal}
      \textit{\\Bien insister sur le caractère glouton dans cette
      leçon.}
\end{itemize}


\end{document}