LDAP: couldn't connect to LDAP server
Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | |||
restricted:tc-a:tp2:travaux_pratiques_deuxieme_seance_2017 [2017/11/27 17:19] – pprea | restricted:tc-a:tp2:travaux_pratiques_deuxieme_seance_2017 [2017/11/27 17:21] (Version actuelle) – pprea | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ====== TP2 ====== | ||
+ | |||
+ | S' | ||
+ | |||
+ | {{restricted: | ||
+ | |||
+ | Le but de ce TP est de résoudre ce problème en proposant un ordre d' | ||
+ | |||
+ | ===== Préparatifs ===== | ||
+ | |||
+ | ==== Un début ==== | ||
+ | |||
+ | - Ajoutez au graphe un sommet de départ, voisin de tout les sommets du graphe sur lesquels aucun autre sommet ne pointe | ||
+ | - Associez un nombre à chaque sommet du graphe (consécutifs et partant de 0) | ||
+ | - Déduisez-en la [[https:// | ||
+ | |||
+ | ==== Implémentation d'une structure de graphe ==== | ||
+ | |||
+ | Ecrivez la liste d' | ||
+ | |||
+ | Ainsi, on pourra tester que si **g** est le graphe : | ||
+ | * **g[0]** correspond à la liste de tous les voisins de " | ||
+ | * Si le numéro associé à " | ||
+ | * testez deux autres conditions que votre graphe doit avoir. | ||
+ | |||
+ | |||
+ | ===== L' | ||
+ | |||
+ | L' | ||
+ | |||
+ | ==== Pseudo-code ==== | ||
+ | |||
+ | L' | ||
+ | |||
+ | < | ||
+ | tri_topologique_recursif(s, | ||
+ | placer s dans la liste des sommets marqués | ||
+ | pour chaque voisin x de s: | ||
+ | si x n’a pas été marqué: | ||
+ | tri_topologique(x, | ||
+ | placer s au début de la_liste_des_sommets_ordonnées | ||
+ | </ | ||
+ | |||
+ | |||
+ | Ses paramètres de départ sont : | ||
+ | * **s** : le sommet de départ, | ||
+ | * **le_graphe** : le graphe à parcourir, | ||
+ | * **la_liste_des_sommets_ordonnées** : la liste initialement vide qui contiendra l' | ||
+ | * ** la_liste_des_sommets_marqués** : liste initialement vide qui contient les sommet vus pendant l' | ||
+ | |||
+ | ==== Implémentation ==== | ||
+ | |||
+ | L' | ||
+ | |||
+ | Pour utiliser l' | ||
+ | |||
+ | <code python> | ||
+ | la_liste_des_sommets_ordonnées = [] | ||
+ | tri_topologique_recursif(0, | ||
+ | print(la_liste_des_sommets_ordonnées) | ||
+ | </ | ||
+ | |||
+ | < | ||
+ | Vous pourrez noter que le paramètre **la_liste_des_sommets_marqués** fonctionne de la même manière que le paramètre **la_liste_des_sommets_ordonnées**, | ||
+ | </ | ||
+ | |||
+ | ==== On peaufine ==== | ||
+ | |||
+ | L' | ||
+ | |||
+ | La fonction **tri_topologique** doit: | ||
+ | * avoir 2 paramètres : le sommet de départ et le graphe, | ||
+ | * rendre la liste des sommets triés. | ||
+ | |||
+ | Si le sommet de départ est de numéro 0 et que le graphe est codé dans la variable **graphe**, le code suivant doit fonctionner : | ||
+ | |||
+ | <code python> | ||
+ | liste_ordonnee = tri_topologique(0, | ||
+ | print(liste_ordonnee) | ||
+ | </ | ||
+ | |||
+ | ===== On peaufine ===== | ||
+ | |||
+ | ==== Première solution ==== | ||
+ | |||
+ | Manipuler des nombres peut être pénible pour un être humain. La liste des sommets ordonnés pourrait être mieux décrite par des noms. Pour cela, utilisez une liste dont la valeur à l' | ||
+ | |||
+ | |||
+ | ==== Un fichier par type d' | ||
+ | |||
+ | Placer votre graphe et la correspondance nombre, nom dans un fichier à part. | ||
+ | |||
+ | Vous devez avoir cinq fichiers : | ||
+ | * le fichier contenant le graphe, | ||
+ | * le test du graphe, | ||
+ | * le fichier contenant l' | ||
+ | * le fichier de test de l' | ||
+ | * le fichier contenant l' | ||
+ | |||
+ | |||
+ | |||
+ | ===== Pour continuer sur les parcours ===== | ||
+ | |||
+ | Programmez une machine à calculer (simple : uniquement les 4 opérations de base), d' | ||