Journal Informatique fondamentale : chemins dans un graphe

Posté par  (site web personnel) .
Étiquettes : aucune
8
17
juil.
2009
Bonjour,

Après trois années de prépa maths, j'ai passé quelques concours, dont celui d'informatique de l'ENS (ça s'est bien passé), pour lequel on a une épreuve d'informatique fondamentale.
Voici l'extrait de l'énoncé (la seule partie que j'ai traitée) :

« On définit un graphe orienté comme un ensemble de points (sommets) et un ensemble de couples de points (arêtes orientées). Un chemin est une suite d'arêtes telles que l'origine d'une arête soit toujours l'extrémité de la précédente. On suppose que les graphes considérés ici ont N sommets, et que l'on dispose d'une fonction f(X, Y) qui indique, pour X et Y deux sommets, s'il existe un chemin entre X et Y.
1. Écrire un algorithme qui, à partir de deux sommets S et T détermine s'il existe un chemin de S à T. La complexité temporelle doit être dominée par N^2.
2. Écrire un algorithme qui répond à cette même question, avec une complexité spatiale dominée par log(N)^2. (les indices des arêtes, étant des nombres entre 1 et N, occupent un espace dominé par log(N)) Peu importe la complexité temporelle. »

Je vous laisse chercher. La réponse à la seconde question (vers laquelle l'examinateur m'a laborieusement orienté) m'a paru très surprenante (et même, d'un point de vue esthétique, assez laide). J'indique la solution en commentaire, pour ceux qui veulent savoir sans avoir trop à chercher.

  • # Trop facile !

    Posté par  (site web personnel) . Évalué à 10.

    Pfffff trop facile il suffit de demander la solution à une SSII qui au choix nous la donnera via un superbe programme en java qui aura pris un an à être développé et nécessite l'achat d'un serveur à 8000€ pour faire tourner le code ou qui nous le rendra en l'espace de deux mois en aillant fait sous traiter en inde.

    Bref l'ENS ne forme sûrement pas de bon décideurs pressés !

    • [^] # Re: Trop facile !

      Posté par  (site web personnel) . Évalué à 1.

      C'est fou ce qu'elle t'as marqué cette histoire hein ? ;)
      Les cauchemars au beau milieu de la nuit se font plus rares ou seulement moins intenses ?

      • [^] # Re: Trop facile !

        Posté par  (site web personnel) . Évalué à 4.

        Les private joke c'est mieux quand on les comprend ... et pour le coup je ne vois pas de quelle histoire tu parles ...

        Je suis sûr que ça va finir par une histoire autour du nombre 42 de toute manière !

        • [^] # Re: Trop facile !

          Posté par  (site web personnel) . Évalué à 4.

          Après recherche, je me suis effectivement planté. Je faisais allusion à ce journal:
          https://linuxfr.org/~ploum/27723.html

          Ton commentaire y ressemblait tellement, que j'étais persuadé que tu étais l'auteur du journal à l'époque. J'aurais dû vérifier.

          • [^] # Re: Trop facile !

            Posté par  (site web personnel) . Évalué à 3.

            Ah mais la blague sur les décideurs pressés et leur amour pour le java parce que l'informaticien (le magazine des décideurs) leur a dit qu'il fallait faire du java pour être branché est plutôt vielle ...

            Bref Ploum n'a rien inventé mais il a su exploiter correctement un fait connu par tout ceux qui ont eut à faire à des SSII ou à des décideurs pressés.

  • # Spanning tree

    Posté par  . Évalué à 3.

    Pour le premier, faire un spanning tree et t'arrêter quand tu tombes sur T en partant de S ça joue non ? (Plus le nom exacte de l'algo)

    • [^] # Re: Spanning tree

      Posté par  . Évalué à 1.

      Ou un simple parcours en largeur et t'utilises la liste des sommets parcourus à partir de ton sommet de départ.

      Ca doit faire un truc genre O(N^2+A) à la très grosse louche (où A le nombre d'arêtes).

      • [^] # Re: Spanning tree

        Posté par  . Évalué à 2.

        Le n^2 comprends pas déja le A ? Dans le pire des cas, pour chaque sommets tu as au max N arêtes, et tu ne parcours chaque sommet qu'une fois, donc ça fait du N*N .

        • [^] # Re: Spanning tree

          Posté par  (Mastodon) . Évalué à 1.

          Oui : O(n²+a)=O(n²) pour n grand.
          Ce ne sont que des ordres de grandeur, la constante est négligeable.
          Et si je me souviens bien on doit même avoir O(a*n²)=O(n²).

          Yth.

          • [^] # Re: Spanning tree

            Posté par  . Évalué à 2.

            En fait ici on doit avoir a = n² au max :
            le nombre d'arête c'est au maximum le nombre de couple de sommets, t'as n sommets, donc le nombre de sommets = a = n² (tu fais le produit cartésien, il doit y en avoir moins mais on s'en fout ici, on fait du O(n²) )

            Donc on a pas du tout besoin de la constante "a" ici, c'est même incorrect d'en faire une constante puisqu'il varie potentiellement avec la taille du graphe, et qu'on sait le compter dans le pire des cas, si je me trompe pas.

            Donc du coup O(a+n²) = O( n² + n²) = O(n²)

    • [^] # Re: Spanning tree

      Posté par  . Évalué à 5.

      dijkstra

      • [^] # Re: Spanning tree

        Posté par  . Évalué à 3.

        Qui a la même complexité que ma proposition puisque de Dijkstra c'est une variante du parcours en largeur. Par contre avec Dijkstra tu calcules les distances alors que tu t'en fiches un petit peu quoi.

        • [^] # Re: Spanning tree

          Posté par  . Évalué à 6.

          Un parcours en profondeur c'est mieux qu'en largeur ici, ça bouffe moins de mémoire.

  • # Avec Twitter, c'est facile...

    Posté par  (site web personnel) . Évalué à 8.

    Tu proposes 100 euros à qui accepte de t'aider...

    ->[]

  • # Solution

    Posté par  (site web personnel) . Évalué à 8.

    La question 1 est relativement classique :

    On se base sur une tableau à N éléments indiquant si on a croisé tel sommet ou pas, et sur une liste de sommets pour lesquels on cherche à lister les sommets qui sont liés :

    Existe_chemin1 (T, croisés, liste) :
     Si liste est vide : renvoyer faux
     S «- tête (liste)
     Si S = T : renvoyer vrai
     Pour i de 1 à N
      Si f(S, i) = 1 et croisés[i] = faux :
       croisés[i] «- vrai
       liste «- empiler (i, liste)
      Finsi
     Fin pour
     Existe_chemin (T, croisés, liste)
    Fin

    Et on lance le programme avec un tableau 'croisés' rempli de valeur 'faux' (sauf pour S), et 'liste' qui vaut [S].

    Pour la seconde question, c'est plus compliqué.
    On remarque que, s'il existe un chemin de S à T, on peut choisir U à peu près au milieu du chemin, avant de vérifier qu'il existe un chemin entre S et U puis entre U et T. Pour éviter de faire des boucles, il va falloir retenir les sommets parcourus précédemment. C'est-à-dire qu'on invoquera les fonctions :
    Existe_chemin2 (S, U, empiler (U, liste)) et Existe_chemin2 (U, T, empiler (U, liste)).
    Par ce procédé, tant qu'on choisit U de manière optimale, la taille de la liste n'excédera jamais log(N).
    Pour éviter de faire exploser la complexité dans le cas où il n'existe pas de chemin entre S et T, il suffit de contrôler la taille de la liste : si elle dépasse log(N) (ou une limite arbitraire un peu au-dessus, comme 2*log(N)), on sait que le choix de U était incorrect, ou alors qu'il n'existe pas de chemin entre S et T.
    Ensuite, pour trouver le U correct, comme on a aucun indice nous permettant de le deviner, il suffit de tous les tester (on se fiche de la complexité temporelle). Ça donne :

    Existe_chemin2 (S, T, liste)
     Si S=T : renvoyer vrai
     Si taille(liste) > 2*log(N) : renvoyer faux
     U «- 1
     résultat «- faux
     Tant que U <= N et résultat = faux
      résultat «- Existe_chemin2 (S, U, empiler (U, liste)) et Existe_chemin2 (U, T, empiler (U, liste))
      U «- U+1
     Fin tant que
     Renvoyer résultat
    Fin

    Je n'ai jamais été habitué à faire un contrôle sur la taille d'une liste pour ne pas faire exploser la complexité (ça me parait 'sale'), ni à tester toutes les options pour en trouver une bonne au milieu (ça fait exploser la complexité). Ici, la complexité temporelle du seconde algorithme est au moins de N^log(N) !

    • [^] # Re: Solution

      Posté par  . Évalué à 5.

      Je n'ai jamais été habitué à faire un contrôle sur la taille d'une liste pour ne pas faire exploser la complexité (ça me parait 'sale')

      J'ai l'impression que c'est quelque chose de commun, par exemple en pathfinding.

      En A*, on sait dans quelle direction est la destination.
      Si les 2 points ne sont pas connectés, il va falloir tester tout le graphe pour s'en rendre compte, ce qui va être long quand on a un grand graphe. Ou bien on peut abandonner l'idée de trouver une solution au bout d'un certain nombre d'essais.
      Dans le cadre d'un jeu vidéo, ça peut être envisageable sachant que du coup c'est le joueur qui va choisir un autre point plus proche/accessible.

      (En réalité, pour un jeu, je trouve plus commode de faire un algo pour détecter les différents graphes déconnectés, puis de lancer l'algo si les 2 points sont connectés, ça évite de perdre du temps à tester une solution puisqu'on sait à l'avance que ça ne marchera pas, mais ça dépend un peu du contexte à chaque fois)
      (Et effectivement, ça fait gagner du temps mais ça fait utiliser plus de mémoire)

      Ici, la complexité temporelle du seconde algorithme est au moins de N^log(N) !
      Oui, je dirais que souvent, la complexité mémoire/spatiale évolue inversement par rapport à la complexité temporelle.

    • [^] # Commentaire supprimé

      Posté par  . Évalué à 2.

      Ce commentaire a été supprimé par l’équipe de modération.

      • [^] # Re: Solution

        Posté par  (site web personnel) . Évalué à 2.

        L'idée est bonne, mais si tu détruis le graphe, c'est que le graphe est une donnée de travail : il faut donc compter l'espace occupé en mémoire par le graphe, ce qui est alors très important (on dépasse le log(N)^2).

        Cependant, dans les faits, les données identifiant le graphe sont forcément présentes quelque part (puisqu'on peut accéder à toutes les arêtes).

    • [^] # Re: Solution

      Posté par  (site web personnel) . Évalué à 2.

      Dans l'algoritmes de la solution 2 tu oublies de vérifier si U est pas déjà dans la liste

      par ailleur, avec une pone implémentation de la liste, tu n'utilise que log(N) d'espace.

      • [^] # Re: Solution

        Posté par  (site web personnel) . Évalué à 5.

        En fait, l'algo de la solution 2 est faux. Il ne contient même pas d'appel à la fonction f

        il faut replacer la ligne

        Si S=T : renvoyer vrai
        par
        si f(S,T) OU S=T : renvoyer vrai

  • # Les graphs pour les ingénieurs ...

    Posté par  . Évalué à 3.

    Pour les ingés qui voudraient exploiter les belles théories/démonstations énoncées par nos amis chercheurs et qui ont besoin de la théorie des graphs et des algorithmes associés en particulier il existe un package python très sympa , networkx : [http://networkx.lanl.gov].

    Pour résoudre le problème énoncé on pourrait s'appuyer sur le DiGraph et la fonction shortest_path par exemple ...

  • # euh...

    Posté par  . Évalué à 10.

    pour la partie 1), il y a un piège ?
    Dans l'énoncé, on dit qu'on dispose d'une fonction f(X, Y) qui indique pour X et Y deux sommets, s'il existe un chemin entre X et Y.
    Et on demande d'écrire une fonction qui fait pareil.
    Je propose la fonction g(S, T) = f(S, T) j'ai bon ? Ou alors on me répond que je ne suis pas sûr que c'est dominé par N^2 ?

    Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

    • [^] # Re: euh...

      Posté par  . Évalué à 3.

      C'est probablement pour un chemin direct entre les deux ;)

    • [^] # Re: euh...

      Posté par  (site web personnel) . Évalué à 5.

      Oups ! La fonctions f(X, Y) indique s'il existe une arête qui va de X à Y. Au temps pour moi.

      • [^] # Re: euh...

        Posté par  . Évalué à 4.

        Et encore, on ne connais pas la complexité en temps et en espace de celle ci.

    • [^] # Re: euh...

      Posté par  (site web personnel) . Évalué à 3.

      C’est quoi cette mode d’écrire les pseudonymes à l’envers ? C’est pour montrer qu’on manipule bien l’UTF-8 ?

      • [^] # Re: euh...

        Posté par  . Évalué à 2.

        C'est encore mieux que le 1337…

        Puis pour se connecter sur un autre ordinateur que le sien, on y passe 10 minutes, c'est pratique.

        Envoyé depuis mon lapin.

        • [^] # Re: euh...

          Posté par  . Évalué à 2.

          Bof, je tape juste 2PetitsVerres comme login, et ça roule.

          Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

          • [^] # Re: euh...

            Posté par  (site web personnel) . Évalué à 1.

            Et ceux qui s’amusent à mettre des pseudo en japonais ou autre, ils font comment ? Sérieux, le souk que ça ferait, sur un channel IRC, si chacun y allait de sa police exotique. Et puis, pour que les autres puissent taper facilement les pseudo, ça serait d’un pratique, aussi…
            Ceci dit, c’est cool que ça puisse être fait et correctement affiché dans les navigateurs modernes, hein, je dis pas !

            • [^] # Re: euh...

              Posté par  . Évalué à 2.

              Il y a deux choses différentes. Le login, et le nom affiché. Ceux qui ont le nom à l'envers ou des caractères japonais, c'est dans le nom affiché, pas dans le login. Aucun problèmes pour se connecter de n'importe quel ordinateur, vu que c'est le login qui est demandé.

              Tous les nombres premiers sont impairs, sauf un. Tous les nombres premiers sont impairs, sauf deux.

  • # Analogique

    Posté par  . Évalué à 3.

    1 algorithme analogique par noeud.

    Avec des bouts de ficelle, en considérant les arc non orientés, réalisés un modèle en fil du noeud:

    Plus qu'à prendre les les noeuds S et T et à tirer. Si tu trouve un chemin c'est le plus court, plus qu'à vérifier l'orientation des arcs; tu coupes au ciseau si l'orientation ne donne pas un chemin de S à T et tu recommences.

  • # Et ?

    Posté par  . Évalué à 2.

    Le jury était hier non ?

    Du coup t'as été pris ?

    • [^] # Re: Et ?

      Posté par  (site web personnel) . Évalué à 2.

      Oui. Mais pas avec une note génialissime à cette épreuve (il y avait 6 ou 7 questions au total). Et avec de bonnes notes ailleurs.
      Mais je n'ai passé l'info que pour Lyon. Je vais plutôt aller à Ulm (concours MPI - physique), pour lequel je suis aussi sur liste principale.

      • [^] # Re: Et ?

        Posté par  (site web personnel) . Évalué à 2.

        c'est pas le pire non plus ;)

        • [^] # Re: Et ?

          Posté par  . Évalué à 1.

          Bah ça dépend si c'est pour faire des maths ou de l'info :)

          Sinon pour les gens qui sont recalés à Lyon, y'a plein de place pour les auditeurs (et si vous faites le master de Nice derrière, y'a un joli financement à la clé).

      • [^] # Re: Et ?

        Posté par  . Évalué à 0.

        Félicitations !
        M'étonnerais qu'on fasse mieux l'année prochaine ;)


        (futur MP* de ton (ex-)prépa)

  • # Ma réponse

    Posté par  . Évalué à 2.

    Question 1: Algorithme de Dijkstra ou DFS, en gros tu parcours ton graph et tu t'arrête dés que tu tombe sur T. On ne te demande même pas le plus courts chemin. Les deux sont en N^2 faut juste une mécanique d'arrêt si T est fermé transitivement.

    Question 2: Bon la ca devient plus complex, on a un graph orienté potentiellement cyclique et il s'agit de le parcourir avec une complexité spatial de log(n)^2. Déjà il n'y pas d'algo classique pour ce problème qui viennent a l'esprit immédiatement.
    On est pas limité en niveau temporelle donc on peut envisager des solution bien gruick, genre l'exploration aléatoire ( j'ai log(N)^2 explorateur qui parte de S et se balade aléatoirement sur le graph, ont ajout deux trois règles genre pas plus d'un explorateur par sommet, etc ), mais bon on est pas a l'abri d'une belle fermeture transitive qui enferme tous les explorateurs.
    Y a peut être des solutions basé sur les tri topologique mais vue que ton graph peut être cyclique ca ne marche pas non plus.
    On peut imaginer de tests tous les chemins de longueur log(N)^2 de manière itérative, mais si on a un graph peut dense ou cyclique ca ne marche pas non plus.

    La solution m'intéresse, parce qu'a part l'exploration aléatoire j'ai pas d'idée.

    • [^] # Re: Ma réponse

      Posté par  . Évalué à 1.

      moi ce qui me blo dans l'énnoncé, c'est complexité spatiale et complexité temporelle. Quelle est la différence entre les deux ?

      • [^] # Re: Ma réponse

        Posté par  . Évalué à 3.

        La complexité spatiale, représente l'ordre de grandeur de l'espace occupé pour ton calcul (par exemple, dans la mémoire vive), la complexité temporelle, c'est l'ordre de grandeur du nombre de calcul à effectuer (directement lié à la durée de ton calcul, donc).

  • # Félicitation!

    Posté par  . Évalué à 1.

    Bien joué pour Ulm, et l'X aussi! Même si tu vas apparemment préférer Ulm, on se croisera peut-être!

    Signé: l'autre Bizien

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.