% Section Partie 1 - SAE 2.02

\documentclass[class=article, crop=false]{standalone}


\begin{document}
  \section{Partie 1}


    \subsection{Question 1}
      \quad Pour représenter ce réseaux, je propose la structure de données suivante :
      \lstinputlisting[language=C,firstline=8,lastline=17]{code/p1e1.c}

      \par\quad La structure du point se compose de son nom et d'un tableau de pointeurs sur d'autre points. Le réseau est ainsi composé d'un tableau de pointeur sur des structures $pointsCaracteristique$, elles-même pointant sur un ou plusieurs point de la liste.

      \par\quad Le réseau est caractérisé par ses points caractéristiques. Chaque point connaît les points accessibles de manière direct. Cela permet de représenter les rues et leur sens. Prenons par exemple, une rue qui part du point A et qui a pour destination le point B. Elle sera caractérisée par la présence du point B dans la liste des points accessibles du point A. De cette manière on peut facilement dessiner le réseau et calculer les trajets à suivre. En somme, les pointeurs servent à caractériser les rues et leurs sens.


    \subsection{Question 2}
      \par\quad Le choix d'une telle structure est fait sur la base de la simplicité d'implémentation. En effet, cette structure est relativement simple. Elle ne travaille quasiment que sur de la manipulation de pointeurs. Le parcours des points caractéristiques est donc facile.

      \par\quad De plus, si on se penche sur la complexité de l'implémentation, le nombre d'opérations requise pour le parcours du réseau est proportionnel au nombre de points que l'on parcourt. Au pire, tout les points seront parcouru : c'est-à-dire que la complexité maximale s'élève au nombre de point qui compose le réseaux.


    \subsection{Question 3}
      \par\quad Pour savoir si A est accessible directement depuis le point B, il suffit juste de regarder si B se trouve dans le tableau des points caractéristiques accessibles directment.

      \par\quad Voici le code correspondant :
      \lstinputlisting[language=C,firstline=21,lastline=31]{code/p1e3.c}


    \subsection{Question 4}
      \par\quad Pour savoir si B est accessible depuis A, directement ou non (par une ou plusieurs rues), il est possible de répéter récursivement la fonction précédante. Ainsi, elle va tester chaque point independamment et si un chemin direct est trouvé, c'est que il y a forcément un chemain qui rend B accessible.

      \par\quad Voici le code correspondant :
      \lstinputlisting[language=C,firstline=36,lastline=51]{code/p1e4.c}

      \par\quad Voici maintenant une ébauche de travail qui visait à créé une version itérative de cette fonction :
      \lstinputlisting[language=C,firstline=53,lastline=89]{code/p1e4.c}

      \par\quad Je me suis rendu compte que je n'arrivait pas à penser l'algorithme autrement que récursivement, c'est pourquoi j'ai décidé de mettre cette ébauche de côté.
      
      \par\quad Néanmoin, il est quand même possible de réutiliser la partie de code qui teste si un point à déjà été testé. Ceci diviserait, par chaque points testé, la complexité de cette algorithme.

      \par\quad Voici ce que donne l'algorithme avec les modifications apportés :
      \lstinputlisting[language=C,firstline=91,lastline=122]{code/p1e4.c}


    \subsection{Question 5}

      \subsubsection{Analyse de l'algorithme de test de l'accès direct}

        \par\quad Analysons le premier algorithme, c'est-à-dire celui de la question n°3.

        \par\quad Cet algorithme se base sur un parcours de tableau grâce à une boucle $for$. Dans le principe de ce parcours, on commence du début du tableau, passe un par un les éléments et termine la boucle au moment où l'on trouve l'élèment que l'on cherche.

        \par\quad La boucle for est prévue pour boucler $N$ fois, $N$ étant le nombre d'élèments du tableau dans lequel on effectue la recherche. Cependant, cette boucle est capable de se terminer prématurément si la condition à l'intérieur se valide.

        \par\quad La complexité maximale de ce code est donc linéaire : $o(N)$, où $N$ est le nombre d'élèments maximums à parourir. Le nombre total d'opérations se calcul par la formule :
          \[3N+1\]
        \quad avec l'initialisation de la variable $i$, le test et l'incrémentation de la boucle $for$, et le test d'égalité de valeur dans la boucle.

      \newpage

      \subsubsection{Analyse de l'algorithme de test de l'accès indirect}

        \par\quad Analysons le second algorithme, c'est-à-dire celui de la question n°4.

        \par\quad Cet algorithme se base sur un parcours récursif sur l'ensemble des points accessibles depuis le point de départ, à la recherche du point d'arrivé. Nous allons étudier la version dite "améliorée" car elle se trouve être plus pertinente. En effet, elle propose de garder en mémoire les points sur lequels l'algorithme est déjà passé et donc déjà testé, de manière à omettre un ènième passage récursif sur ce point, et donc d'éviter une complexité exponentielle et potentiellement une boucle interminable.

        \par\quad Commençons par analyser la fonction $isInTab$, servant de fonction utilitaire afin de rechercher si un $PointCaracteristique$ se trouve dans le tableau des points déjà passé. Cette fonction, est en réalité identique à la fonction de l'exercice n°3, à la différance qu'elle ne recherche pas les valeurs au même endroit. Sa complexité est donc d'ordre linéaire($o(N)$), avec $3N+1$ instructions effectuées par appel.

        \par\quad Attaquons-nous maintenant au gros de l'algorithme. Comme expliqué plus haut, le principe est d'appliquer cet algorithme sur tout les points en accès direct d'un point. Alors on y retrouve une boucle $for$ qui boucle $N$ fois, $N$ étant ce nombre de points directement accessibles. Ensuite, on utilise la fonction $isInTab$ pour savoir si l'on doit lancer une recherche sur ce point où si cela a déjà été fait. On est donc à une complexité calculée par l'expression :
          \[N*3P+1\]
        \quad où $P$ est le nombre de point déjà testés, et $P$ tendant vers $N$. Sa complexité maximale est donc donnée par la formule :
          \[N\frac{1}{2}N(N+1)\]

        \par\quad Ensuite, après avoir rajouté le point courant à la liste des points déjà testés, on utilise la fonction $isAccessDirect$ afin de savoir si parmi la liste de point en accès direct on retrouve notre destination. On rajoute donc $3N+1$ à la complexité, ce qui nous donne l'expression :
          \[N*2(3P+1)\]
        \quad où $N$ est le nombre de points directement acessible et $P$ même variable que le pour le calcul précédant. Cela nous donne donc l'expression de complexité "au pire" :
          \[2N\frac{1}{2}N(N+1)\]
        
        \par\quad Enfin, et il s'agit ici de la partie la plus délicate de l'analyse, on étudie l'appel récursif de cette fonction. On doit donc imaginer combien de fois cette fonction sera appelée pour multiplier ce nombre par le reste de la complexité de ce code. Mais en réalité, comme on fait attention à ne pas revenir en arrière sur notre chemin, au plus nous parcourerons tout les points du plans. Appelons ce nombre $Q$. Dans ce cas la complexité maximale, dite "au pire" est donnée par la formule :
          \[2Q\frac{1}{2}Q(Q+1)\]
        \quad avec $Q$ le nombre total de points du plan de la ville. La compléxité maximal de cet algorithme est donc d'ordre quadratique ($o(N^{2})$).


\end{document}