Implémentation Python de l’algorithme de Dijkstra

Cet article fait suite à l’article suivant sur l’algorithme de Dijkstra : http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Voici l’implémentation Python de l’algorithme

from collections import deque

def dijkstra(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    while queue:
        t = queue.popleft()
        print("On visite le sommet " + str(t))
        for voisin in graph[t]:
                queue.append(voisin)
                nouvelle_distance = distance[t] + graph[t][voisin]
                if(voisin not in distance or nouvelle_distance < distance[voisin]):
                    distance[voisin] = nouvelle_distance
                    print("Met à jour le sommet " + str(voisin) + " avec la distance : " + str(nouvelle_distance))
                    
    return distance



#Liste d'ajacence du graphe
graph = {'A':{'B':15,'C':4},'B':{'E':5},'C':{'E':11,'D':2},'D':{'E':3},'E':{}}
distance = dijkstra(graph,'A')
print("Distances" + str(distance))

Python les bases en plus de 128 mots [Partie 4]

Cet article fait suite aux trois premières parties qu’il est possible de consulter ici :

Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Exceptions :

Lorsqu’une erreur se produit, (une exceptions) elle peut être gérée à l’aide de l’instruction try:

try:
  print(r)
except NameError:
  print("variable r non définie")
except:
  print("Autre exception") 

Commentaires :

#Ceci est un commentaire
#sur
#plusieurs ligne
print("Bonjour Python")
"""
Ceci est un commentaire
sur
plusieurs ligne
"""
print("Bonjour Python")

Classes :

Les classes sont comme un constructeur d’objet, cela permet de modeler des concepts réels.

class Personne:
  def __init__(self, nom, age):
    self.nom = nom
    self.age = age

  def ma_fonction(self):
    print("Nom de la personne : " + self.name)

p1 = Personne("Sébastien", 36)
print(p1.nom)
print(p1.age) 
p1.ma_fonction()
p1.age = 40 #Modification des propriétés de l'objet
del p1.age #supprime la propriété de l'objet
del p1  #supprime l'objet

self est une référence à l’instance actuelle de la classe et est utilisé pour accéder aux variables qui appartiennent à la classe. Il peut être nommé autrement que self, mais ce doit être obligatoirement le premier paramètre de toute fonction de la classe.

Héritage :

L’héritage permet de définir une classe qui hérite de toutes les méthodes et propriétés d’une autre classe.

class Animal :
   def marcher():
       print('marche')

class Chien(Animal)
    pass

c1 = Chien()
c1.marcher()

Constructeur :

La fonction __init __ () est appelée automatiquement chaque fois qu’un nouvel objet est créé.

super () fera que la classe enfant héritera de toutes les méthodes et propriétés de son parent.

class Etudiant(Personne):
  def __init__(self, nom, prenom):
    super().__init__(nom, prenom) 

Python les bases en plus de 128 mots [Partie 3]

Cet article fait suite aux deux premières parties qu’il est possible de consulter ici :

Je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Tuples :

Un tuple est une collection ordonnée comme les listes et immuable (qui ne change pas).

exempleTuple = ("pomme", "poire", "fraise")
print(exempleTuple)
print(exempleTuple[1])
print(exempleTuple[-1]) #L'indexation négative signifie à partir de la fin, -1 se réfère au dernier élément, -2 se réfère à l'avant-dernier élément, etc.
print(exempleTuple[1:2]) #Vous pouvez spécifier une plage d'index en spécifiant par où commencer et où terminer la plage.
z = list(exempleTuple) #conversion tuple en liste
z[1] = "banane" 
x = tuple(z) #conversion liste en tuple

for x in exempleTuple: #Boucle sur un tuple
  print(x) 

if "poire" in exempleTuple: #test d'existence dans un tuple
  print("Oui") 

Unpacking :

coordonnees = (1,2,3)
x,y,z = coordonnees
print(x)

Dictionnaires :

Un dictionnaire est une collection non ordonnée, modifiable et indexée.

client = {
   "nom": "Elodie",
   "age": "45",
   "annee": 1980
 }

print(client["age"])
client["nouvelleCle"] = "nouvelleValeur" #ajoute une nouvelle clé et valeur
client.get("solde") #renvoi 'None' car la clé n'existe pas

Fonctions :

Les fonctions permettent d’organiser le code en morceau réutilisables. En Python, une fonction est définie à l’aide du mot clé def.

def exemple_fonction():
  print("TestFonction")

exemple_fonction()

Les données peuvent être passées aux fonctions en tant que paramètre. Vous pouvez ajouter autant de paramètres que vous le souhaitez, il suffit de les séparer par une virgule.

def exemple_fonction(prenom):
  print("Bonjour " + prenom)

exemple_fonction("John")
exemple_fonction("Pierre")

Python les bases en plus de 128 mots [Partie 2]

Cet article fait suite à la première partie qu’il est possible de consulter ici : http://128mots.com/index.php/2019/12/04/python-les-bases-capes-nsi-snt-en-plus-de-128-mots/

Comme pour le premier article, je traite ici des bases du langage Python pour l’apprendre rapidement. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Priorité des opérateurs :

Je récapitule la priorité des opérateurs en Python, de la priorité la plus haute à la priorité la plus basse

  • Parenthèses () : groupement d’opérations
  • Exposant : x ** y
  • Multiplication, multiplication de matrice, division, division entière, modulo : *, @, /, //, %
  • Addition, soustraction : +, –

Fonctions mathématiques :

import math
  • math.ceil(2.6) entier supérieur
  • math.floor(-5.3) partie entière, donne ici -8.0.
  • math.sqrt : racine carrée.
  • math.pow(5, 5) : 5 puissance 5.
  • math.exp(2) : fonction exponentielle.
  • math.log(2) : fonction logarithme
  • math.log(3, 2) : log en base 2.
  • math.factorial(4) : factorielle
  • math.fsum(L) : somme des éléments d’une liste
  • math.sin, math.cos, math.tan : fonctions trigonométriques
  • math.pi : pi
  • math.degrees(y) : conversion de radians en degrés
  • math.radians(y) : conversion de degrés en radians

Expressions conditionnelles :

Python s’appuie sur l’indentation pour définir la portée du code.

x = 100
y = 23
if x > y:
  print("x plus grand que y")
elif a == b:
  print("égalité")
else:
  print("y plus grand que x")

Chaines de caractères formatées (f-strings) :

import math
print(f'La valeur de pi est {math.pi:.3f}.')

Listes à deux dimensions (matrices) :

matrix = [[1, 2, 3], [4,5, 6], [7, 8, 9]]
print(matrix[0][1])

Méthodes sur les listes :

list.append('n') #Ajoute un élément en fin de liste
list.insert(0,'a') #Ajoute un élément à la position spécifiée
liste.pop(1) #Enleve l'élément de la liste à la position spécifiée
liste.sort() #Trie la liste
liste.reverse() #Retourne la liste
liste.copy()   #retourne une copie de la liste

Python les bases en plus de 128 mots [Partie 1]

Voici mes notes pour apprendre très rapidement le langage python. En France ces bases sont enseignées en lycée aux classes de seconde SNT, première et terminale NSI. Elles font également partie du programme de connaissance pour le CAPES NSI.

Opérateurs logiques :

  • and : retourne True si les deux déclarations sont vraies
  • or : Renvoie True si l’une des déclarations est true
  • not : Inverser le résultat, renvoie False si le résultat est vrai

Opérateurs de comparaison :

  • == Égalité
  • != Non égal
  • > < Supérieur / Inférieur
  • <= >= Inférieur égal / Supérieur égal
  • != Différent

Mot clé pass :

Lorsque l’instruction pass est exécutée, rien ne se produit, mais vous évitez une erreur lorsque du code vide n’est pas autorisé.

x = 22
y = 150

if x > y:
  pass

Entrée utilisateur :

Utilisation de l’instruction input :

nom = input("Nom utilisateur :")
print("Username is: " + nom)

Boucle While :

La boucle while exécute un ensemble d’instructions tant qu’une condition est vraie. L’instruction break, permet d’arrêter la boucle même si la condition while est vraie.

x = 1
while x < 11:
  if x == 5:
    break
  x += 1 

Boucle For :

Une boucle for effectue une itération sur une séquence (une liste, un tuple, un dictionnaire, un ensemble ou une chaîne de caractère).

Une liste :

for x in [1, 2, 3]:
  print(x)

Une chaine de caractère :

for x in "hello":
  print(x)

Un tuple :

tupleObjet = ('Citroen', 2019, 'C4', 23000)
 
for elements in tupleObj:
    print(elements)

Un dictionnaire :

dico = {'couleur': 'vert', 'animal': 'chien', 'legume': 'epinard'}
for cle in dico:
    print(cle)

Fonction Range :

Pour boucler un nombre de fois spécifique, utilisez la fonction range ().

for x in range(10):
  print(x)

Les Listes :

Une liste est une collection qui est ordonnée et modifiable et qui permet les doublons.

liste = ["pomme", "banane", "poire"]
print(liste[1])
print(liste[-1]) #Affiche le dernier élément de la liste
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[2:3])#Lorsque vous spécifiez une plage, la valeur de retour sera une nouvelle liste avec les éléments spécifiés.
print(liste[:3])#En omettant la valeur initiale, la plage commencera au premier élément:
print(liste[1:])#En omettant la valeur de fin, la plage ira à la fin de la liste:
print(liste[-2:-1])#des index négatifs pour lancer la recherche à partir de la fin de la liste: Cet exemple renvoie les éléments de l'index -2 (inclus) à l'index -1 (exclu).

Tri fusion Python – implémentation de l’algorithme

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présente une implémentation du tri fusion python.

Le tri fusion suit le paradigme diviser pour régner qui consiste à diviser la tâche initiale en deux tâches similaires plus petites. Cet article présent une implémentation du tri fusion python.

Introduction

L’algorithme est le suivant :
Diviser en deux moitiés la liste à trier.
On trie chacune d’entre elles.
Fusionner les deux moitiés obtenues pour reconstituer la liste triée.

On applique récursivement cet algorithme c’est à dire jusqu’à ce que la liste à trier soit constituée d’un seul élément.

tri fusion python
Tri fusion (source : wikipedia)
#Tri fusion fonction de division du tableau
def tri_fusion(tableau):
    if  len(tableau) <= 1: 
        return tableau
    pivot = len(tableau)//2
    tableau1 = tableau[:pivot]
    tableau2 = tableau[pivot:]
    gauche = tri_fusion(tableau1)
    droite = tri_fusion(tableau2)
    fusionne = fusion(gauche,droite)
    return fusionne


#Tri fusion fonction de fusion de 2 listes
def fusion(tableau1,tableau2):
    indice_tableau1 = 0
    indice_tableau2 = 0    
    taille_tableau1 = len(tableau1)
    taille_tableau2 = len(tableau2)
    tableau_fusionne = []
    while indice_tableau1<taille_tableau1 and indice_tableau2<taille_tableau2:
        if tableau1[indice_tableau1] < tableau2[indice_tableau2]:
            tableau_fusionne.append(tableau1[indice_tableau1])
            indice_tableau1 += 1
        else:
            tableau_fusionne.append(tableau2[indice_tableau2])
            indice_tableau2 += 1
    while indice_tableau1<taille_tableau1:
        tableau_fusionne.append(tableau1[indice_tableau1])
        indice_tableau1+=1
    while indice_tableau2<taille_tableau2:
        tableau_fusionne.append(tableau2[indice_tableau2])
        indice_tableau2+=1
    return tableau_fusionne

tableau = [11, 222, 3, 899, 24, 5, 46, 67]
print(tableau)
tableau_trie = tri_fusion(tableau)
print(tableau_trie)

A propos de tri fusion

Enfin, Le tri fusion fonctionne par comparaison. La complexité de l’algorithme pour n entrée est n log n, donc asymptotiquement optimal.

La technique est de diviser pour régner. Et l’algorithme fait principalement une opération de fusion (deux listes triées peuvent être fusionnées en temps linéaire).

Tri fusion python : liens externes

https://www.geeksforgeeks.org/merge-sort/

http://lwh.free.fr/pages/algo/tri/tri_fusion.html

https://pixees.fr/informatiquelycee/n_site/isn_algo_diviser_pour_regner.html

https://fr.wikipedia.org/wiki/Tri_fusion

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Liens internes sur les algorithmes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

http://128mots.com/index.php/2020/02/17/lalgorithme-de-dijkstra-dans-un-graphe-pondere-et-oriente-en-plus-de-128-mots/

Pour calculer la distance de Levenshtein avec un algorithme non récursif. On utilise une matrice qui contient les distances de Levenshtein. Alors Ce sont les distances entre tous les préfixes de la première chaîne et tous les préfixes de la seconde chaîne de caractères.

PageRank Python – Implémentation de l’algorithme en python

PageRank python est un algorithme utilisé par Google Search pour classer les sites Web dans les résultats de leurs moteurs de recherche. PageRank est un moyen de mesurer l’importance des pages de site Web.

pagerank python

Introduction :

Ce n’est pas le seul algorithme utilisé par Google pour ordonner les résultats des moteurs de recherche, mais c’est le premier algorithme utilisé par la société, il est le plus connu.

Le PageRank d’une page est calculé à partir de la somme du PageRank des pages avec un lien entrant à la page calculée que l’on divise par le nombre de pages sortantes de cette dernière, on applique un facteur d’atténuation pour symboliser la probabilité que l’utilisateur surfe sur une autre page.

Implémentation pagerank python :

J’installe networkx, c’est un package Python pour la création, la manipulation et l’étude de la structure, de la dynamique et des fonctions de réseaux complexes.

Networkx fournit des structures de données et des méthodes pour stocker des graphes que j’utilise pour l’algorithme pagerank.

import networkx as nx
import numpy as np

graphe=nx.DiGraph()

tableauPages = ["A","B","C"] #Exemple de page rank avec 3 pages
graphe.add_nodes_from(tableauPages) #Ajout des sommets du graphe

#on ajoute des arcs, on a :
#la page A a un lien vers B 
#la page B a un lien vers C
#la page C a un lien vers B
#la page C a un lien vers A
# la page B a 2 lien entrant
# la page C a un lien entrant 2 liens sortant
# la page A a un lien entrant un lien sortant
graphe.add_edges_from([('A','B'), ('C','A'),('B','C'), ('C','B')])
print("Sommets du graphe : ")
print(graphe.nodes())
print("Arrêtes du graphe : ")
print(graphe.edges())
#Si on considere un facteur d'attenuation de 0.85 = d
# la formule du page rank est :
#PR(p) = (1-d)/n + d * Somme de toutes les pages(PR(i) des lien entrants à p/nombre de lien sortant de la page qui reference p)
# PR(A) = (1-0,85)/3 + 0,85 * (PR(C)/2)
# PR(B) = (1-0,85)/3 + 0,85 * (PR(A)/1 + PR(C)/2)
# PR(C) = (1-0,85)/3 + 0,85 * (PR(B)/1)

pagerank = nx.pagerank(graphe)
print(pagerank)

Pagerank python liens externes :

https://fr.wikipedia.org/wiki/M%C3%A9thode_des_k_plus_proches_voisins

https://www.python.org/

https://www.educative.io/blog/python-algorithms-coding-interview

Liens internes :

http://128mots.com/?s=dijkstra

Tri par tas Python – implémentation de l’algorithme en Python

L’algorithme du tri par tas est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.

L'algorithme du tri par tas python est un algorithme de tri par comparaison. Cet article vous done le code du tri par tas python.

Le principe de l’algorithme du tri par tas python est le suivant :

  1. Alors on recherche le père du dernier nœud de l’arbre et on le tamise : le père d’un noeud dans un arbre binaire corresponds à l’arrondi inférieur de (i-1)/2 avec i la position du noeud dans le tableau qui stocke l’arbre.
  2. Le tamisage d’un noeud consiste à visiter son fils droit et son fils gauche et permuter la racine avec le plus grand des deux.
  3. Et il faut tamiser l’arbre jusqu’à arriver à la racine, le plus grand nombre de l’arbre se retrouve alors en position de racine au début du tableau.
  4. On permute la racine qui est le plus grand nombre avec la dernière feuille (soit la position n du tableau qui stocke l’arbre de taille n). On considère alors que ce nombre est bien ordonné (càd il est en dernière position et c’est le plus grand)
  5. Enfin, l’opération de tamisage et permutation est réitérée en considérant le sous arbre qui va de la racine à n-1 (pour ne pas déplacer le nombre qui a été correctement ordonné) jusqu’à ce qu’on arrive au fils gauche de la racine (l’indice 1)

Voir le lien wikipedia : https://fr.wikipedia.org/wiki/Tri_par_tas

from math import *
#128mots.com
def indice_fils_gauche(noeud_pere:int):
	return (noeud_pere * 2)+ 1

def indice_fils_droit(noeud_pere:int):
	return (noeud_pere * 2) + 2
#Retourne l'indice du noeud pere si il existe (noeud doit être > 0)
def indice_noeud_pere(noeud):
	#Si il existe il s'agit de l'arrondi inférieur de (noeud-1)/2
	return floor((noeud - 1)/2)

#permute 2 éléments d'un tableau et incrément la variable globale compteur_permutation à initialiser dans le main
def permute(tableau, indice1: int, indice2:int):
	print("Permutation de l'élément " + str(indice1) + " avec l'element " + str(indice2))
	print("**Avant permutation : " + str(tableau))
	global compteur_permutation
	if(indice1 != indice2):
	#on sauvegarde la valeur de l'indice 1 dans une variable temporaire
		tmp = tableau[indice1]
		tableau[indice1] = tableau[indice2]
		tableau[indice2] = tmp
		compteur_permutation += 1
	print("**Apres permutation : " + str(tableau))

#Tamise un arbre binaire à partir d'un noeud en parametre
#1. on compare le noeud avec le fils droit et le fils gauche (si ils existent)
#2. on permute avec la plus grande valeur
#128mots.com
def tamise(arbre,noeud,longueur):
	#On visite le fils droit et le fils gauche
	print("++Tamisage de " + str(noeud) + " arbre: " + str(arbre))	
	indiceFilsDroit   = indice_fils_droit(noeud)
	indiceFilsGauche  = indice_fils_gauche(noeud)
	print("indiceFilsDroit>>" + str(indiceFilsDroit))
	print("indiceFilsGauche>>" + str(indiceFilsGauche))


	if(indiceFilsDroit < longueur): # si le fils droit existe
		if(arbre[indiceFilsDroit] > arbre[indiceFilsGauche]): #Si le fils droit est plus grand que le fils gauche
			if(arbre[indiceFilsDroit] > arbre[noeud]): #Si le fils droit est plus grand que le noeud tamisé
				permute(arbre,indiceFilsDroit,noeud)
		elif(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
			permute(arbre,indiceFilsGauche,noeud)
	elif(indiceFilsGauche < longueur): #Si le fils gauche existe
		if(arbre[indiceFilsGauche] > arbre[noeud]): #Si le fils gauche est supérieur au noeud tamisé alors on permute
			permute(arbre,indiceFilsGauche,noeud)
	print("++Apres tamisage : " + str(arbre))			
#128mots.com

compteur_permutation = 0
arbre = [11, 222, 3, 24, 5, 46, 67, 899] #On écrit un arbre sous forme de tableau
print("démarrage arbre : " + str(arbre))

#128mots.com
#Tamisage initial
#on prend le dernier élément de l'arbe qui est une feuille et on recherche son père
indiceDuNoeudPere = indice_noeud_pere(len(arbre)-1) 
#on tamise càd on compare le noeud pere avec le fils droit et le fils gauche
#puis on permute avec la plus grande valeur
for i in range(indiceDuNoeudPere,-1,-1): #On tamise jusqu'à la racine
	tamise(arbre,i,len(arbre))

permute(arbre,len(arbre)-1,0) #on permute le premier element et le dernier 
#suite au tamisage c'est la plus grande valeur on la place donc à la fin du tableau

#on répete le tamisage
for i in range(len(arbre)-1,1,-1): 
	indiceDuNoeudPereDeI = indice_noeud_pere(i-1) #on prend l'élément i de l'arbe qui est une feuille et on recherche son père
	for j in range(indiceDuNoeudPereDeI,-1,-1): #On tamise jusqu'à la racine
		tamise(arbre,j,i)
	permute(arbre,i-1,0)

print("resultat final du tri : " + str(arbre))
print("nombre de permutation : " + str(compteur_permutation))

Conclusion

En conclusion, L’algorithme est utilisé pour trier sur place les éléments d’un tableau en un temps de l’ordre de n log ⁡ n.

Et l’étape qui coûte le plus dans cet algorithme est la seconde boucle (extraction des éléments du tas).

Enfin, et algorithme a l’avantage de consommer peu de mémoire par rapport à d’autres algorithme de tri.

Tri pas tas python : liens externes

https://fr.wikipedia.org/wiki/Tri_par_tas

https://fr.wikipedia.org/wiki/Smoothsort

https://wiki.inria.fr/sciencinfolycee/Le_tri_par_tas

http://perso.numericable.fr/jules.svartz/prepa/IPT_spe/TP_tris_efficaces_tas.pdf

https://www.prepabellevue.org/index.php?module=Site&voir=document&id_document=589

Liens internes sur les algorithmes

http://128mots.com/index.php/2021/01/13/algorithme-tri-quantique/

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/