[PDF] LI0467_Annexe04pdf - Lettres dInformation - Ucanss
DE LA CONVENTION DE FORMATION PROFESSIONNELLE CONTINUE réalisera PASS PREM'SS et l'option en cochant l'option concernée
[PDF] Contexte enjeux et modalités de mise en œuvre du CQP
de législation et validé par un contrôle continu Architecture Prem'ss cours de formation les notes des contrôles continus de l'option pourront
[PDF] Contrôle Continu Architecture des Ordinateurs 1h30
Une bonne réponse rapporte 05 point et une mauvaise réponse ne vous rapporte aucun point Page 2 NOM : Prénom : 1) Le terme SIMD
[PDF] La loi cadre n° 34-09 relative au système de santé et à loffre de soins
Le droit à la protection de la santé est une responsabilité de l'Etat et de la société TITRE PREMIER DU SYSTEME DE SANTE Chapitre premier Responsabilité de
[PDF] Techniques Algorithmiques et Programmation Test de contrôle continu
Nom prénom: Techniques Algorithmiques et Programmation Test de contrôle continu s s Question 2 Appliquer deux fois l'opération de dépilement (pop) au
[PDF] Modalités de mise en œuvre des CQP GCA et CSU de la Branche
Les CQP GCA et CSU sont composés de 3 éléments : PASS PREM'SS et l'option de branche Les nom et prénom des stagiaires Contrôle continu par I4 10
[PDF] MODALITES DE CONTRÔLE DES CONNAISSANCES ET DES
15 oct 2019 · a) Inscription en régime de Contrôle continu (CC) Tout·e·s s les étudiant·e·s de la composante et extérieur·e·s à la composante
[PDF] Brochure DM - Faculté de Pharmacie -UM6SS-
L'Université Mohammed VI des Sciences de la Santé (UM6SS) lance le premier CONTRÔLE CONTINUE ET TRAVAIL DE MÉMOIRE DE FIN D'ETUDE OBJECTIF
[PDF] ROYAUME DU MAROC Ministère de lEducation Nationale de l
majeur : le premier rapport national sur l'état de l'Ecole et ses perspectives Le Programme NAJAH présenté ici s'organise autour des espaces
Groupe: Année 2018-2019
Nom prénom:
Techniques Algorithmiques et Programmation
Test de contrôle continu
1h - aucun document autoriséTas minimum de lettres
Question 1.Donnez le tas résultant de l"insertion dans un tas minimum supposé vide au départ des
10 lettres du motvoyageusesajoutées une par une en le lisant de gauche à droite. On trie les lettres
selon l"ordre alphabétique. Par exemple :gSolution.[4 pts]
a e e g o y u v s sQuestion 2.Appliquer deux fois l"opération de dépilement (pop) au tas de la question précédente.
Donner les tas obtenus après l"exécution de chacune des deux opérations.Solution.[3 pts (avec question suivante)]
e e e g e ou e s g s s o y u g o y u s o y u v s v s v Question 3.Quelles sont dans l"ordre les deux lettres ainsi supprimées?Solution.apuise.
Algorithme A*
On considère le graphe valué suivant, ainsi que les deux heuristiquesh1eth2estimant la distance
entre un sommet donné ett: 341 2 18 3 21b
c a st d(s;t)(a;t)(b;t)(c;t)(d;t)(t;t)h
1311220
h2521160
Question 4.Démontrez que si une heuristiquehvérifie l"inégalité triangulaire et sous-estime la
distance, alorshest monotone.Solution.[4 pts]Il faut montrer que inégalité triangulaire + sous-estimation implique monotonie.
On a :
h(x;t)6h(x;y) +h(y;t)(inégalité triangulaire)6dist(x;y) +h(x;t)(h()sous-estimedist())
6!(x;y) +h(x;t)(w(x;y) =coût d"un chemin dexày)
Ce qui est la définition de la monotonicité. Question 5.Appliquez l"algorithme A* sur le graphe ci-dessus entresetten utilisant l"heuristique h1. Indiquez dans la table ci-dessous dans quel ordre les sommets sont ajoutés àPen donnant à
chaque foisparent[u],co^ut[u]etscore[u]au moment de l"ajout deudansP.Ps parent? co^ut0 score3 Donnez le chemin desàtainsi construit et son coût.Solution.[3 pts]Psdacbt
parent?sdsab co^ut013345 score334555 Note : En fait, lecest facultatif, puisque il a le même score quebett. Mais si on fait le tas normalement, c"est bien lui qui sera au sommet.Avech1:s!d!a!b!t, etco^ut[t] = 5.
Question 6.Mêmes questions en utilisant l"heuristiqueh2.Ps parent? co^ut0 score5 Donnez le chemin desàtainsi construit et son coût.Solution.[3 pts]Pscbt
parent?scb co^ut0356 score5466Avech2:s!c!b!t, etco^ut[t] = 6.
Question 7.Comparez le coût des deux chemins, expliquez. Solution.[2 pts]Le chemin obtenu avech2n"est pas optimal, carh2n"est pas monotone :h2(d;t) =6alors quew(d;a) +h2(a;t) = 4. Alternativement,h2ne sous-estime pas les distances non plus :
distG(d;t) = 4.
Voyageur de commerce
On considère le problème du voyageur de commerce sur un ensemble de4pointsV=fs;u;v;wg dont la distanced(;)est donnée par la table et le graphe ci-dessous :21 3 9 65uvs wdsuvw s0529 u5013 v2106 w9360 Dans la suite on noteraV=Vn fsg=fu;v;wg. L"algorithme de programmation dynamique vu en cours repose sur la fonctionD(t;S), définie pour tout sous-ensemble de pointsSVet tout pointt2S, comme étant la longueur minimum d"un chemin allant desàtet qui visite tous (et
seulement) les points deS. On rappelle que cette fonction vérifie la formule de récurrence suivante :
D(t;S) =d(s;t)sijSj= 1
min x2SnftgfD(x;Sn ftg) +d(x;t)gsijSj>1La table ci-dessous doit acceuillir toutes les valeurs deD(t;S). Les lignes de la table représentent
les points (t) et les colonnes les sous-ensembles (S). La première colonne est déjà remplies, en notant
que certaines cases n"ont pas à être remplies.Sfugfvgfwgfu;vgfu;wgfv;wgfu;v;wgt
u5 vX wX Question 8.Indiquez par une croix les cases qui ne doivent pas être remplies. Question 9.Complétez les autres cases de la table. Solution.[1+4 pts (avec la question précédente)]Sfugfvgfwgfu;vgfu;wgfv;wgfu;v;wgt
u5XX312X11 vX2X6X1513 wXX9X886Question 10.Expliquez comment on calcule à l"aide de cette table la longueur de la tournée optimale.
Donnez cette longueur.
Solution.[2 pts]On calcule la longueur grâce à la dernière colonne, celle correspondant àS=
V =fu;v;wg. Il faut ajouter le retourd(t;s)avect=u,v, ouw.OPT(V;d) = mint2fu;v;wgfD(t;V) +d(t;s)g:
D(u;V) +d(u;s) = 11 + 5 = 16.
D(v;V) +d(v;s) = 13 + 2 = 15.
D(w;V) +d(w;s) = 6 + 9 = 15.
La longueur minimale est donc 15.
quotesdbs_dbs50.pdfusesText_50[PDF] controle corrigé sur les angles 5ème
[PDF] controle corrigé svt seconde biodiversité
[PDF] controle corrigé trigonométrie seconde
[PDF] contrôle d'accès biométrique pdf
[PDF] controle de connaissance amp
[PDF] controle de francais 4eme sur le fantastique
[PDF] controle de géographie 5ème l'accès ? l'eau
[PDF] contrôle de gestion dans le secteur public
[PDF] controle de gestion dunod pdf
[PDF] contrôle de gestion et gestion budgétaire charles horngren pdf
[PDF] contrôle de gestion et performance de l'entreprise pdf
[PDF] contrôle de gestion et système d'information mémoire
[PDF] controle de gestion exercices corrigés
[PDF] controle de gestion exercices corrigés maroc
