https://www.loutrel.fr/wikinsi/ 2026-04-29T23:44:48+00:00 https://www.loutrel.fr/wikinsi/ https://www.loutrel.fr/wikinsi/lib/tpl/dokuwiki/images/favicon.ico text/html 2021-01-26T11:05:23+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:boyer_moore&rev=1611655523&do=diff Algorithme de recherche textuelle Boyer-Moore: ---------- Cet algorithme permet la recherche d'un motif dans un texte de manière plus efficace et plus rapide. motif : chaine de caractère que l'on souhaite rechercher dans un texte. Algorithme python et son fonctionnement: text/html 2021-01-14T11:03:32+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:chemin&rev=1610618612&do=diff Chercher une chaine dans un graphe Ici nous cherchons à connaitre le chemin entre deux noeuds :!: cet algorithme renvoie un chemin, ce n'est pas forcement le plus court L'algorithme va renvoyer une chaine de noeud entre le noeud de depart et le text/html 2022-04-29T11:57:05+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:cle_arbre&rev=1651226225&do=diff ====== Rechercher ou insérer une clé dans un arbre de recherche Rechercher une clé #---Classe permettant l'implémentation de l'arbre binaire--- class ArbreBinaire: def __init__(self, valeur): self.valeur = valeur self.enfant_gauche = None self.enfant_droit = None def insert_gauche(self, valeur): if self.enfant_gauche == None: self.enfant_gauche = ArbreBinaire(valeur) else: new_node = ArbreBinaire(valeur) new_node.enfant_gauche … text/html 2021-01-14T11:01:09+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:cycle&rev=1610618469&do=diff Cycle dans les graphes Qu'est qu'un cycle ? Un cycle est tout simplement une boucle dans un graphe, c'est utile pour savoir s'il est possible d'effectuer un parcours qui revient à son point de départ sans être obligé de faire demi-tour. L'algorithme ci dessous permet de text/html 2021-01-26T11:03:07+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:diviser_pour_regner_algo&rev=1611655387&do=diff Méthode "diviser pour régner": ---------- Cette méthode algorithmique permet de résoudre un problème. Tout d'abord, on divise ce problème en une multitude de petits problèmes, puis ces sous problèmes étant plus simples, sont ensuite résolus, et on recombine enfin les petits problèmes résolus afin d'obtenir la solution du problème de départ. (je vous invite à voir la text/html 2021-01-26T11:04:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:dynamique&rev=1611655485&do=diff Programmation dynamique: ---------- La programmation dynamique est une méthode de programmation qui permet d'éviter notamment deux problèmes de la récurrence. Elle permet la résolution de ces problèmes qui sont la répétitivité d'un programme (le temps d'exécution trop long) et l'empilage non infini de la récurrence, en mémorisant le résultat et en le réutilisant quand nécessaire. Ça reprend le principe de text/html 2022-05-13T11:18:58+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:parcours_arbre&rev=1652433538&do=diff Parcourir un arbre de différentes façons Parcours préfixe #---Classe permettant l'implémentation de l'arbre binaire--- class ArbreBinaire: def __init__(self, valeur): self.valeur = valeur self.enfant_gauche = None self.enfant_droit = None def insert_gauche(self, valeur): if self.enfant_gauche == None: self.enfant_gauche = ArbreBinaire(valeur) else: new_node = ArbreBinaire(valeur) new_node.enfant_gauche = self.enfant_gauche … text/html 2021-01-14T11:00:46+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:parcours_profondeur&rev=1610618446&do=diff Le parcours en profondeur Dans le cas du parcours en profondeur, on va chercher à aller “le plus loin possible”. La méthode de découverte est unidirectionnelle. VARIABLE G : un graphe u : noeud v : noeud //On part du principe que pour tout sommet u du graphe G, u.couleur = blanc à l'origine DEBUT PARCOURS-PROFONDEUR(G,u) : u.couleur ← noir pour chaque sommet v adjacent au sommet u : si v.couleur n'est pas noir : PARCOURS-PROFONDEUR(G,v) fin si fin pour FIN text/html 2023-01-04T11:44:45+00:00 Anonymous (anonymous@undisclosed.example.com) https://www.loutrel.fr/wikinsi/doku.php?id=les_programmes_a_connaitre:algorithmique_term:taille_arbre&rev=1672829085&do=diff ====== Calculer la hauteur et la taille d'un arbre ====== HK Hauteur d'un arbre : rappel : profondeur maximale d'un arbre. Programme permettant de calculer la hauteur d'un arbre : #---Classe permettant l'implémentation de l'arbre binaire--- class ArbreBinaire: def __init__(self, valeur): self.valeur = valeur self.enfant_gauche = None self.enfant_droit = None def insert_gauche(self, valeur): if self.enfant_gauche == None: self.enfant_gauche = ArbreBina…