# Memo de python >[!remarque] >Mémo de python qui sert à donner les spécifications qui diffèrent d'un langage à l'autre. Pas vraiment un cours de python mais pratique, pour skip une question à l'autre. ### Listes ```python # soit A une liste, la substitution retournes A[1:3] => [A[1],A[2]] A[::-1] => Inverse la liste set(A) => Éléments uniques de A ``` ### Copie / Move Python utilise la __référence__ par défaut. Càd: ```python def foo(l): l.append(1) a = [] c = a foo(a) # Ici on passes a qui serra modifié par foo print(a) # a = [1] print(c) # c = [1] ``` Cela ne s'appliques qu'aux liste (exp: les listes sont en réalité implémenté comme des pointeurs). Si on ne veux absolument pas que ça se produise (car ça peut introduire des bugs, par exemple: si on trie une liste temporairement pour un algorithme sans copie, on peut modifier la liste originale et faire n'importe quoi) on doit alors faire une copie: ```python c = a.copy() ``` # Graphes ### Degré C° >[!definition] >Degré(sommet): nombre de ses sommets adjacents >Degré(graphe): degré maximum de ses sommets >[!propriete] >$\sum d(v) = 2|E|$ >La somme de chaque degré de chaque nœud vaux 2 fois le nombre d’arêtes. ## Types de graphes >[!definition] >Un graphe complet est un graphe avec des arêtes entre chaque nœud. ### Chemin >[!definition] >__Chemin simple__: chemin où tout les sommets sont distincts (on ne repasse pas 2 fois sur le même truc) >[!definition] >On dit qu'un graphe est connexe si tout les point sont connectés entre eux (en gros ce que l'on définirais comme plusieurs graphes séparés). >[!definition] >On dit qu'un graphe sans cycle, donc __acyclique__ si il existe un unique chemin simple entre deux sommets connectés. Un __arbre__ est forcément __acyclique__. ## Trucs randoms >[!definition] >La profondeur c'est la profondeur depuis la racine. En sachant que la racine commence __à 0__. # Algorithmes ## BFS: parcours en largeur >[!definition] >L'algorithme de __BFS__ retournes une étape d'un parcours en largeur. Lors de ce parcours, les sommets sont explorés par [distance](https://fr.wikipedia.org/wiki/Lexique_de_la_th%C3%A9orie_des_graphes#D "Lexique de la théorie des graphes") croissante au sommet source. >Donc, on peut retourner les prédécesseur les plus proche de chaque noeud et reconstruire un chemin. ```python def bfs(o_graph, s_deb): """ retournes: dist : dict dictionnaire initialisé des distances entre un noeud de o_graph et s_deb. """ q = [s_deb] # noeuds à vister pred = {} # predecesseur visitee = [s_deb] # noeuds déjà visités while len(q) > 0: a_visiter = q.pop(0) if a_visiter in o_graph.keys(): for noeud in o_graph[a_visiter]: # o_graph est de la forme : {a:[b, c]} if not noeud in visitee: # on vérifie que le noeud n'a pas déjà été visté visitee.append(noeud) # on ajoute le noeud aux noeud déjà visités pred[noeud] = a_visiter q.append(noeud) return pred ``` Ensuite: ##### Reconstruction de chemin ```python def chemin(o_graph, s_deb, s_fin): l = bfs(o_graph, s_deb) if s_deb == s_fin: # cas spécial ou anyway on nous demandes un truc obscure return [s_deb] elif not s_fin in l.keys(): # cas où l'on ne trouves pas de chemin return [] else: p = chemin(o_graph, s_deb, l[s_fin]) # on fait un algorithme récursif qui construit le chemin depuis la fin return p + [s_fin] ``` ## Algorithme Prim: glouton L'algorithme de Prim permet d'avoir un parcours minimal entre plusieurs points (non orienté + potentiellement pondéré). Exemple: ![[Pasted image 20250125150652.png]] Ici, c'est le graphe recouvrant tout les points avec le chemin minimal. Fonctionne que sur les graphes connexes I think ```python def prim_couverture_mini(dico_adjacences, depart): triplets_retenus = [] # triplet d'aretes: (sommetA, sommetB, distance) sommets_pris_en_compte = [depart] while len(sommets_pris_en_compte) < len(dico_adjacences) : min_distance = float('inf') min_arete = None #triplet de départ initialisée à None # parmis tout les sommets déjà retenus, # parmis tout les sommets reliés à ces sommets déjà retenus, # on retient le sommet dont la distance est minimale for sommet1 in sommets_pris_en_compte: # on s'assure de partir d'un sommet déjà intégré, au départ la sommet 0 # dico_adjacences est sous la forme: # { sommet1: {sommet2: distance, sommet3: distance, ...}, sommet2: {sommet1: distance, sommet3: distance, ...}, ...} for sommet2, distance in dico_adjacences[sommet1].items(): # on parcourt pour chacun d'eux leurs sommets reliés et on retient la sommet dont la distance est minimale sur l'ensemble des sommets connectés aux lotissements déjà retenus if sommet2 not in sommets_pris_en_compte and distance < min_distance: min_distance = distance min_arete = (sommet1, sommet2, distance) if min_arete is not None: sommet1, sommet2, distance = min_arete triplets_retenus.append((sommet1, sommet2, distance)) sommets_pris_en_compte.append(sommet2) return triplets_retenus ``` ## Gale-shapeley >[!remarque] >Réécriture de l'algorithme Gale-Shapeley avec les attendus de l'INSA. C'est mieux de le représenter par un système d'école <-> étudiant que le système plutôt boomer de mariage et de score de préférence de couple. Sauf si l'IE c'est de recréer tinder, ce qui serrait plutôt funny. >[!definition] >L'algorithme de Gale-Shapeley, permet, selon deux liste de préférence (celle de l'école, et celle des étudiants) créer des liens optimaux (ex: parcoursup). ```python # On considère des listes de préférences des écoles et on fait une liste # selon chaque étudiant son rang (classement, puisque l'école donne les élèves par ordre croissant) def pref_to_rank(pref): res = {} for ecole, ecole_pref in pref.items(): ecole_pref_res = {} for rang, etudiant in enumerate(ecole_pref): ecole_pref_res[etudiant] = rang res[ecole] = ecole_pref_res return res def gale_shapley(etudiants, ecoles, etudiants_pref, ecoles_pref): """ etudiants -- set[str]. ecoles -- set[str]. etudiants_pref -- dict[str, list[str]]. (liste croissante) ecoles_pref -- dict[str, list[str]]. (liste croissante) Output: list of (a, b) pairs. """ classement_preference_ecole = pref_to_rank(ecoles_pref) liste_de_demande = etudiants_pref.copy() pair = {} etudiants_restants = set(etudiants) # on inverse pour pop plus rapidement la première (puisque c'est par ordre croissant mais pop la fin est plus rapide que le début) for etudiant in liste_de_demande.keys(): liste_de_demande[etudiant] = liste_de_demande[etudiant][::-1] while len(etudiants_restants) > 0: etudiant = etudiants_restants.pop() ecole_demande = liste_de_demande[etudiant].pop() if ecole_demande not in pair: pair[ecole_demande] = etudiant else: ancien_etudiant = pair[ecole_demande] ecole_prefere_nouvel_etudiant = classement_preference_ecole[ecole_demande][ancien_etudiant] < classement_preference_ecole[ecole_demande][etudiant] if ecole_prefere_nouvel_etudiant: etudiants_restants.add(etudiant) else: etudiants_restants.add(ancien_etudiant) pair[ecole_demande] = etudiant # pas obligatoire return [(ecole, elev) for elev, ecole in pair.items()] ``` Exemple d'utilisation: ```python print(gale_shapley( etudiants={"S.Samuel", "S.Bobby", "S.John"}, ecoles={"F.Smith", "F.Martinez", "F.Brown"}, etudiants_pref={ "S.Samuel": ["F.Smith", "F.Brown", "F.Martinez"], "S.Bobby": ["F.Martinez", "F.Brown", "F.Smith"], "S.John": ["F.Martinez", "F.Brown", "F.Smith"], }, ecoles_pref={ "F.Smith": ["S.Samuel", "S.John", "S.Bobby"], "F.Martinez": ["S.Samuel", "S.Bobby", "S.John"], "F.Brown": ["S.John", "S.Samuel", "S.Bobby"], }, ) ```