SUJET + CORRIGE - Université de Bordeaux
que si les k premières lettres du motif forment un suffixe des q premières lettres de ce même motif, alorssoitk = 0,soitk = q Donnezlaparticularitédel’automated’unmotifnonrecouvrable Solution: Touteslesarcsretour reviennentàl’étatinitial
Matrices et Suites Bac ES 2019, Amérique du Nord
Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet que le technicien doit suivre pour aller de B à A, tout en minimisant la distance parcourue: le trajet B – L – E – P – A Et ce trajet aura pour longueur: 80 km + 70 km + 80 km + 180 km = 410 kilomètres En effet, l’algorithme de Dijkstra est le suivant:
Sujet et corrigé du bac en mathématiques, série ES
En utilisant l’algorithme de Dijkstra, déterminons le trajet le moins cher pour aller de A à G: Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet le moins cher pour aller de l’aéroport A à l’aéroport G: le trajet A - E - D - C - G Et ce dernier coûtera: 45 + 40 + 60 + 50 = 195 €
Optimisation - Institut de Mathématiques de Toulouse
Exercice 4 (Algorithme de Bellman-Ford) Appliquer l’algorithme de Bellman-Ford pour calculer les distances minimale depuis le sommet A aux autres sommets Dans chaque cas, quel autre algorithme aurait on pu utili-
IT3004 Graphes et algorithmes Notes de cours et exercices
De la première forme de la définition, on déduit l’algorithme suivant : Algorithme 1 : SuccPartie_1 Données : X ⊂E,~Γ Résultat :Y ⊂E 1 Y =0/ ; 2 pour chaque (x,y)∈~Γ faire 3 si x ∈X alors 4 Y =Y ∪{y}; Selon le choix du type de données pour X et Y, la complexité de l’algorithme précédent peut varier
1 Notes de cours - unistrafr
Implémentez les primitives de base des sémaphores définies p ar Dijkstra (voir notes de cours, section 1 1), Init, Vet Pà l’aide des primitives standard Unix 3 Entraînement : exercice corrigé 3 1 Énoncé : interblocage Un étudiant qui se spécialise en anthropologie et accessoirement en informatique s’est embar-
Compilation réalisée à partir d’exercices de BAC TES
GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir d’exercices de BAC TES Exercice n° 1 Un groupe d’amis organise une randonnée dans les Alpes On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer Une arête entre deux sommets coïncide avec l’existence d’un
Chapitre 2 Corrigé des exercices - info-llgfr
Corrigé des exercices Combinatoire des graphes Exercice 1 a) Soit G = (V;E) un graphe non orienté simple Notons V1 l’ensemble des sommets de degré pair et V2 l’ensemble des sommets de degré impair Nous savons que X v2V deg(v) = 2jEj, donc : X v2V2 deg(v) = 2jEj X v2V1 deg(v): De cette égalité il résulte que X v2V2
Complexité Corrigé
1 à tab length-2, bornes incluses On a donc tab length-2 exécutions du corps de la boucle, soitunnombretotald’opérationsen(tab length-2) (1) ,c’est-à-dire( tab length) 3 Correction de l’exercice 1 3 Cet exercice ressemble beaucoup à l’exercice 1 2, avec une différence fondamentale dans la boucle interne
Théorie des Graphes Exercices de Travaux Dirigés
Exercices de Théorie des Graphes 1 page EFREI - Année 2010/11 Théorie des Graphes Exercices de Travaux Dirigés I – MODELISATION DE PROBLEME A L’AIDE DE GRAPHE I 1 - Conseil d'administration Le Conseil d'Administration de l'institut X est composé de 7 personnes : D, P, G, H, K, S et V
[PDF] Algorithme de héron Terminale Mathématiques
[PDF] Algorithme de loi continue / densite Terminale Mathématiques
[PDF] Algorithme de mathématiques 2nde Mathématiques
[PDF] Algorithme de maths 1ère Mathématiques
[PDF] Algorithme de maths 2nde Mathématiques
[PDF] Algorithme de mesure d'angle 1ère Mathématiques
[PDF] Algorithme de niveau Seconde 2nde Mathématiques
[PDF] algorithme de parcours en largeur PDF Cours,Exercices ,Examens
[PDF] algorithme de parcours en profondeur en c PDF Cours,Exercices ,Examens
[PDF] Algorithme de Pythagore 2nde Mathématiques
[PDF] ALGORITHME DE PYTHAGORE ( TI-84 plus ) 2nde Mathématiques
[PDF] algorithme de recherche dans un tableau PDF Cours,Exercices ,Examens
[PDF] algorithme de recherche dichotomique PDF Cours,Exercices ,Examens
[PDF] algorithme de recherche intelligence artificielle PDF Cours,Exercices ,Examens
Exercice 3Corrigé
BACCALAURÉAT GÉNÉRAL
Session 2016
MATHÉMATIQUES
- Série ES -ENSEIGNEMENT DE SPÉCIALITÉ
Durée de l'épreuve : 3 heures
Coefficient : 7
Les calculatrices électroniques de poche sont autorisées, conformément à la réglementation en vigueur. Le sujet est composé de 4 exercices indépendants. Le candidat doit traiter tous les exercices. Dans chaque exercice, le candidat peut admettre un résultat précédemment donné dans le texte pour aborder les questions suivantes, à condition de l'indiquer clairem ent sur la copie. ou non fructueuse, qu'il aura développée.Il est rappelé que la qualité de la rédaction, la clarté et la précision des raisonnements
entreront pour une part importante dans l'appréciation des copies. Avant de composer, le candidat s'assurera que le sujet comporte bien 5 pages numéro tées de 1 à 5.EXERCICE35 points
Candidatsde la série ES ayantsuivi l"enseignementde spécialitéUne compagnie aérienne utilise huit aéro-
ports que l"on nomme A, B, C, D, E, F, G et H.Entre certains de ces aéroports, la compagnie
propose des vols dans les deux sens. Cette situation est représentée par le grapheΓ ci-contre, dans lequel : les sommets représentent les aéro-ports, les arêtes représentent les liaisons as- surées dans les deux sens par la com- pagnie.AB C D EF G HPartie A
1. a .Déterminer, en justifiant, si le grapheΓest complet. b.Déterminer, en justifiant, si le grapheΓest connexe.2.Déterminer, en justifiant, si le grapheΓadmet une chaîne eulérienne. Si oui, donner
une telle chaîne.3.Donner la matrice d"adjacenceMdu grapheΓen respectant l"ordre alphabétique des
sommets du graphe.4.Pour la suite de l"exercice, on donne les matrices suivantes :
M 2=( ((((((((((3 1 2 2 1 1 0 11 4 1 2 2 0 2 0
2 1 3 1 1 2 0 1
2 2 1 4 1 1 1 1
1 2 1 1 3 0 1 0
1 0 2 1 0 2 0 1
0 2 0 1 1 0 3 0
1 0 1 1 0 1 0 2)
))))))))))etM3=( ((((((((((4 8 3 7 6 1 4 18 4 8 8 3 6 1 4
3 8 2 7 4 1 6 1
7 8 7 6 7 3 3 2
6 3 4 7 2 3 1 4
1 6 1 3 3 0 5 0
4 1 6 3 1 5 0 4
1 4 1 2 4 0 4 0)
Un voyageur souhaite aller de l"aéroport B à l"aéroport H. a.Déterminer le nombre minimal de vols qu"il doit prendre, Justifier les réponses à l"aide des matrices données ci-dessus. b.Donner tous les trajets possibles empruntant trois vols successifs.Partie B
Les arêtes sont maintenant pondérées par le coût de chaque vol, exprimé en euros.Un voyageur partant de l"aéroport A doit se
rendre à l"aéroport G. En utilisant l"algorithme de Dijkstra, détermi- ner le trajet le moins cher.AB C D EF G H 40100
45
110
50
120
60
50
40
55
80
90
1 alainpiller. frfreemaths . fr 1. a. Déterminons, en justifiant, si le graphe est complet: