Fiche de révision : Graphes, dictionnaires et hachage

📋 Plan du Cours

1. Listes Python et opérations essentielles
2. Piles, files et dictionnaires
3. Modélisation algorithmique de l’awalé
4. Graphes, chemins et arbres
5. Matrices et listes d’adjacence
6. Parcours de graphes
7. Algorithme de Dijkstra
8. Fonctions de hachage et collisions
9. Hachage Python et recherche dichotomique

📖 1. Listes Python et opérations essentielles

🔑 Notions clés & Définitions

• Liste : N-uplet numérique ordonné dont les indices vont de 0 à n − 1 et dont la longueur vaut n.

★ À maîtriser

• Une tranche L[i:j] extrait les éléments d’indices i inclus à j exclu.

Compléments

• La concaténation de deux listes s’effectue avec l’opérateur +, tandis que la répétition d’une liste s’effectue avec un entier multiplicateur.

• Les opérations courantes sur une liste comprennent:

  • len
  • del
  • in
  • sort
  • reverse
  • min
  • max
  • insert
  • remove
  • count

📖 2. Piles, files et dictionnaires

🔑 Notions clés & Définitions

• Pile : Liste dans laquelle pop retire et retourne le dernier élément, tandis qu’append ajoute un élément à la fin.
• Dictionnaire : Structure associant des valeurs à des clés, qui peuvent être des chaînes ou des tuples mais pas des listes.

📝 Points essentiels

• Les méthodes d’extraction renvoient respectivement:

  • les clés avec keys()
  • les valeurs avec values()
  • les couples clé-valeur avec items()

• Une deque permet d’ajouter et de retirer des éléments à gauche avec appendleft et popleft, après import depuis collections.

💡 Astuce mémo

Pile : dernier entré, premier sorti ; file : premier entré, premier sorti.

📖 3. Modélisation algorithmique de l’awalé

📝 Points essentiels

• Au départ, le plateau d’awalé comporte 2 rangées de 6 trous contenant chacune 4 graines, soit 48 graines en jeu.

📌 La partie s’arrête lorsqu’un joueur possède au moins 25 graines dans sa réserve ou lorsqu’une situation empêche tout nouveau gain.

• 🔄 Un coup d’awalé suit les étapes suivantes: choisir une case non vide de son camp, prendre toutes ses graines, les semer une par une dans le sens direct, récolter éventuellement les graines admissibles

📌 Une case est ramassable si elle appartient au camp adverse et contient exactement 2 ou 3 graines.

📌 Une case jouable doit appartenir au camp actif, être non vide et ne pas vider complètement le camp adverse à la fin du tour.

💡 Astuce mémo

Initialiser → jouer → semer → récolter → vérifier la famine.

📖 4. Graphes, chemins et arbres

🔑 Notions clés & Définitions

• Graphe non orienté : Couple (S,A), où S est l’ensemble des sommets et A l’ensemble des paires de sommets appelées arêtes.
• Degré d’un sommet : Le degré d’un sommet est le nombre d’arêtes qui contiennent ce sommet.
• Arbre : Graphe connexe sans cycle, éventuellement organisé autour d’une racine et muni d’étiquettes aux nœuds.

📝 Points essentiels

• Un graphe d’ordre n possède n sommets et admet au plus le nombre d’arêtes correspondant à choisir deux sommets parmi n.

💡 Astuce mémo

Un graphe peut contenir des cycles ; un arbre est connexe et sans cycle.

📖 5. Matrices et listes d’adjacence

🔑 Notions clés & Définitions

• Matrice d’adjacence : Matrice carrée dont le coefficient aij indique le nombre d’arêtes reliant le sommet i au sommet j.
• Liste d’adjacence : Structure qui associe à chaque sommet la liste des sommets qui lui sont adjacents.

★ À maîtriser

• Pour un graphe fini non pondéré, le coefficient de la matrice $A^k$ situé à la ligne i et à la colonne j indique le nombre de chemins de longueur k reliant i à j.

Compléments

• Dans un graphe pondéré, le coefficient de la matrice d’adjacence contient la pondération de l’arête entre les deux sommets.

💡 Astuce mémo

Matrice : représentation dense avec des zéros ; liste : représentation économique des voisins.

📖 6. Parcours de graphes

★ À maîtriser

• Le parcours en profondeur explore un voisin puis poursuit aussi loin que possible avant de revenir au sommet précédent.

• Le parcours en largeur explore d’abord tous les voisins du sommet initial, puis les voisins de ces voisins, en évitant les sommets déjà rencontrés.

Compléments

• Les parcours de graphe utilisent un dictionnaire ou une structure de marquage pour éviter de visiter plusieurs fois un même sommet.

💡 Astuce mémo

Profondeur : on descend avant de revenir ; largeur : on explore niveau par niveau.

📖 7. Algorithme de Dijkstra

★ À maîtriser

• L’algorithme de Dijkstra cherche les plus courts chemins depuis le sommet 0 dans un graphe pondéré orienté ou non orienté.

• Dijkstra initialise la distance du sommet de départ à 0 et celles des autres sommets à l’infini, puis sélectionne à chaque étape le sommet non exploité de distance minimale.

• Pour chaque voisin X de distance connue, Dijkstra compare la distance actuelle de Y avec la somme de la distance de X et du poids de l’arête X-Y, puis conserve la plus petite.

Compléments

• Dans l’exemple fourni, le plus court chemin de A vers E est ABE et sa longueur est 5.

💡 Astuce mémo

Choisir le minimum → relaxer les voisins → recommencer → reconstruire le chemin.

📖 8. Fonctions de hachage et collisions

🔑 Notions clés & Définitions

• Fonction de hachage : Application d’un ensemble E de clés vers l’ensemble des entiers {0,…,n − 1}.

★ À maîtriser

📌 Une collision se produit lorsque deux clés distinctes possèdent la même valeur de hachage.

📐 Formule — Pour une clé entière x, un exemple de hachage est $h(x)=x\bmod n$.

• Le chaînage gère les collisions en stockant plusieurs valeurs dans une même case, généralement sous forme de liste.

Compléments

• Le hachage d’un dictionnaire de clés entières place chaque valeur dans une liste de n cases à l’indice donné par la fonction de hachage.

💡 Astuce mémo

Clés nombreuses pour peu d’adresses → collisions → chaînage.

📖 9. Hachage Python et recherche dichotomique

★ À maîtriser

• En Python, hash() renvoie pour un objet un entier signé sur 64 bits compris entre −2^63 et 2^63 − 1.

• Une recherche dichotomique dans une liste de clés triées compare la clé recherchée à l’élément central et élimine la moitié incompatible à chaque étape.

• La recherche d’une clé dans une liste triée par dichotomie a une complexité en O(log n), en supposant que le calcul de la fonction d’ordre est en O(1).

Compléments

• Pour utiliser un hachage Python dans une table de taille n, on calcule l’indice de la clé avec sa valeur de hachage puis on regroupe les valeurs partageant cet indice.

📌 Le tri facilite la recherche d’une clé, mais l’insertion d’un couple dans une liste triée peut rester coûteuse à cause du déplacement des éléments.

💡 Astuce mémo

Hachage : accès par adresse calculée ; recherche dichotomique : division répétée d’une liste triée.

📊 Tableaux de synthèse

Représentations d’un graphe