Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Cours : algorithmes et récursivité


Sujet :

Algorithmes et structures de données

  1. #1
    Community Manager

    Cours : algorithmes et récursivité
    Pour tous ceux qui s'intéressent aux algorithmes dont notamment la récursivité, je signale un lien exceptionnel à lire absolument :
    http://recursivite.developpez.com

    On peut y télécharger au format PDF un livre complet (145 pages!) d'Axel Chambily-Casadesus et Petrut Constantine sur le sujet :
    http://recursivite.developpez.com/recursivite.pdf

    Ce manuel traite un nombre impressionnant d'algorithmes (anagrammes, fractales, tris, arbres et graphes, dictionnaire, parcours du fou sur un échiquier, problème des tours de Hanoi, jeu du compte est bon, dérécursificaton etc..), itérativement puis grâce à la récursivité.

    A titre de complément au livre, voici ci-dessous deux algorithmes récursifs "génériques".
    Pour les appliquer, il suffit de bien visualiser l'enchaînement des cas possibles et de bien définir la condition d'arrêt et le vecteur d'état. Les exemples du livre ont pour objectif de préciser ces données en fonction de leur contexte afin d'optimiser le traitement...


    1- Algorithme de recherche à essais successifs (backtracking) : modélisation de la recherche par arbre ; arrêt à la première solution trouvée.
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    Essai (Etape)
    -------------
      Repeter ...
       {
        Selection etape racine du sous-arbre suivant
        Si étape acceptable alors ..
         {
          Sauvegarde du vecteur d'état
          Enregistrement étape
          Si Non_Succès (vecteur d'état) alors ..
           {
             Essai(racine_sous_arbre)
             Si Non_Succès (vecteur d'état) alors .. 
              {
                Annulation de l'enregistrement de l'étape
                Restauration du vecteur d'état
              }
           }
         }
       }
      Jusqu'à Succès (vecteur d'état) OU (plus de sous-arbres) 
    Fin.


    2- Algorithme de recherche à essais successifs de toutes les solutions.
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
     
    Essai (Etape)
    -------------
      Pour tous les sous-arbres ..
       {
        Selection etape racine du sous-arbre suivant
        Si étape acceptable alors ..
         {
           Sauvegarde du vecteur d'état
           Enregistrement étape
           Si Non_Succès (vecteur d'état) alors ..
            {
              Essai(racine_sous_arbre)
                sinon enregistrer la solution 
             }
           Annulation de l'enregistrement de l'étape
           Restauration du vecteur d'état
         }
       }
    Fin.


    Voilà : en espérant que cela vous éclairera autant que moi
    Pour contacter les différents services du club (publications, partenariats, publicité, ...) : Contacts

  2. #2
    Membre averti
    ftp://ftp-developpez.com/recursivite/recursivite.pdf: Lien mort

  3. #3
    Responsable Qt & Livres

    Le bon lien est : http://recursivite.developpez.com/recursivite.pdf. C'est corrigé dans le message ci-dessus, !
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Candidat au Club
    Merci beaucoup...