IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
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

    Inscrit en
    avril 2014
    Messages
    670
    Détails du profil
    Informations forums :
    Inscription : avril 2014
    Messages : 670
    Points : 9 496
    Points
    9 496
    Par défaut 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

    Homme Profil pro
    Développeur informatique
    Inscrit en
    novembre 2013
    Messages
    177
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Administration - Collectivité locale

    Informations forums :
    Inscription : novembre 2013
    Messages : 177
    Points : 348
    Points
    348
    Billets dans le blog
    2
    Par défaut ftp://ftp-developpez.com/recursivite/recursivite.pdf: Lien mort

  3. #3
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 857
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 857
    Points : 181 642
    Points
    181 642
    Par défaut
    Le bon lien est : http://recursivite.developpez.com/recursivite.pdf. C'est corrigé dans le message ci-dessus, !
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou 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
    Homme Profil pro
    Médecin Spécialiste HGE
    Inscrit en
    novembre 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Médecin Spécialiste HGE
    Secteur : Santé

    Informations forums :
    Inscription : novembre 2012
    Messages : 2
    Points : 4
    Points
    4
    Par défaut
    Merci beaucoup...

Discussions similaires

  1. Récursivité et algorithme
    Par zerakain dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 02/01/2007, 17h55
  2. Cours sur algorithmes et mathématique
    Par legend666 dans le forum Algorithmes et structures de données
    Réponses: 20
    Dernier message: 01/10/2006, 06h47
  3. cours d'algorithmes en java :?:
    Par imane1 dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 18/09/2005, 10h18
  4. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 23h18

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo