[PDF] Examen d’algorithmique et programmation - IMJ-PRG

View - Download Examen d’algorithmique et programmation - IMJ-PRG

Previous PDF

Next PDF

Algorithmique et Programmation 3 Examen L2 Maths-MIASH - automne 2020

Examen d'algorithmique et programmation

Duree : 2 heures.

La clarte et la precision de la redaction auront une part importante dans le bareme. Sauf precision contraire, les reponses devront ^etre justiees. Tous documents interdits. Les 4 exercices sont independants.

Exercice 1. Tri de notes.

On considere deux listeetudiantsetnotesde longueurn2Ntelles que pour tout entieri < n, notes i ]est la note de l'etudiant·e dont le numero etudiant estetudiants[i]. 1. Ecrire une fonctionnote_etu(etudiants,notes,numeroetudiant)qui renvoie la note de l'etu- diant·e dont le numero etudiant estnumeroetudiant. 2. Q uellees tl ac omplexitede l 'algorithmeq uev ousa vezp ropose? 3. D anscet teq uestion,on su pposeq uela l isteetudiantsest triee par ordre croissant de numero etudiant.Ecrire une nouvelle fonctionnote_etu_trie(etudiants,notes,numeroetudiant) qui comme a la question 1 renvoie la note de l'etudiant·e de numeronumeroetudiant, mais dont la complexite est enO(logn). On ne prouvera pas la complexite, mais on donnera le nom de l'algorithme utilise.

Solution de l'exercice 1.

1.

O ni mplementeun er echerched ansun el isteen l apar courantd ud ebut ala n.1d efn ote_etu(etudiants, notes, numeroetudiant):

2 n l en (etudiants) 3 f or i i n r ange (n) 4 i f e tudiants i n umeroetudiant 5 r eturn n otes i 2. La c omplexiteest en O (n)c aron a un es euleb ouclefordont le contenu est eectue au plusn fois, et chaque etape de boucle prend un temps en O(1). 3. O nv au tiliserla r echerched ichotomique.1d efn ote_etu_trie(etudiants, notes, numeroetudiant):

2 imin

0

3 imax

l en (etudiants) 1 4 w hile i min i max 5 i ( imin i max) 2 6 i f e tudiants i n umeroetudiant

7 imax

i 1 8 e lif e tudiants i n umeroetudiant

9 imin

i 1 10 e lse 11 r eturn i 12 r eturn

Erreur

n umero e tudiant i ntrouvable

Exercice 2. Somme des chires.

1. Ecrire une fonction recursive qui calcule la somme des chires de l'ecriture decimale d'un entier n>0, en appliquant l'idee suivante : si n<10, on renvoien;

si non,on cal culel asom mesdes chires den/ /1 0, et on renvoies+ n % 1 0.Universite de Paris 1 UFR de mathematiques

Algorithmique et Programmation 3 Examen L2 Maths-MIASH - automne 2020 2. D onnerun eb orneaus sipr eciseq uep ossibleen O(f(n)) sur la complexite de la fonction obtenue en fonction denen justiant. On suppose que les operations arithmetiques prennent un temps constant.

Solution de l'exercice 2.

1. O ns uitl 'algorithmep roposep arl 'enonce: 1d efs ommechiffres(n): 2 i f n 1 0 3 r eturn n 4 e lse 5 r eturn n 10 s ommechiffres(n 10) 2. Il y a u ne etaped ecal culp arc hired en, et sikest le nombre de chires den >0 en ecriture decimale on a 10 k1< ndonck <1 + log10n, d'ou on deduit une borne enO(logn).

Exercice 3. Coloration de graphe.

SoitG= (S;A) un graphe non oriente, soitk>1. UncoloriagedeGakcouleurs est une application c:S! f0;:::;k1gtelle que pour tout (s1;s2)2A,c(s1)6=c(s2) (on dit quec(s) est la couleur du sommets). SiGadmet un coloriage akcouleurs, on dit queGestk-coloriable. 1. M ontrerq uesi Gestk-coloriable pour un certaink>1, alorsGn'admet pas de boucle, c'est-a-dire d'ar^ete de la forme (s;s) pour un certains2S. 2. P ourc haquek>1, donner un exemple de graphe ak+ 1 sommets sans boucle qui n'est pas k-coloriable. On pourra commencer park= 1;2;3. 3. O ns 'interessed esormais al a2-c oloriabilite.O nsu pposeq uel egr aphees tcon nexe,c' est-a-dire que pour tous sommetss1ets2, il existe un chemin des1as2. a) M ontrerq uesi c1etc2sont deux coloriages a 2 couleurs deG, si (s1;s2)2Aet si c

1(s1) =c2(s1), alorsc1(s2) =c2(s2).

b) En d eduireq ues ic1etc2sont deux 2-coloriages deGtels qu'il existes2Savecc1(s) = c

2(s), alorsc1=c2.

c) M ontrerq ues icest un 2-coloriage deG, alors 1cest aussi un 2-coloriage deG. d) En d eduireq uesi Gest 2-coloriable, alors il admet un 2-coloriage tel quec(0) = 0. 4. O np roposel 'algorithmes uivantp ourv erierl a2- coloriabilite,o ul egr aphe( toujourssu ppose

connexe) est donne sous forme d'une matrice d'adjacence surnsommets de la forme 0;:::;n1.1d efe st_2_coloriable(M):

2 n l en ( M) 3 c 1 n 4 c 0 0

5 avisiter

0 6 w hile a visiter 7 x a visiter.pop() 8 f or y i n r ange (n) 9 i f c y 1 a nd M x y 1 10 c y 1 c x

11 avisiter.

append (y) 12 f or x i n r ange (n) 13 f or y i n r ange (n) 14 i f M x y 1 a nd c x c y 15 r eturn

F alse

16 r eturn T rue a) Enoncer sans justier l'algorithme de parcours de graphe sur lequel cet algorithme est base. b) Qu ellee stla c omplexitede l 'algorithmep roposeci -dessusen fon ctiond un ombrende sommets?Universite de Paris 2 UFR de mathematiques Algorithmique et Programmation 3 Examen L2 Maths-MIASH - automne 2020 c) M ontrerq uesi Gn'est pas 2-coloriable et siMest sa matrice d'adjacence, alors la fonction est_2_coloriable(M)retourneFalse. d) Su pposonsq ueGsoit 2-coloriable, soitc1un 2-coloriage deGtel quec1(0) = 0 (existe d'apres la question 3). Montrer qu'apres la derniere execution de la bouclewhile, on a quec[i]=c1(i) pour touti2 f0;:::;n1g. On introduira un invariant de boucle, et on pourra utiliser directement le fait vu en cours que tout sommet appartiendra a la liste avisitera un moment. e) C onclureq uel 'algorithmer envoiebi enTruessi le graphe est 2-coloriable.

Solution de l'exercice 3.

1. Si Gadmettait une boucle, on aurait uns2Stel que (s;s)2A, mais alorsc(s)6=c(s) carc est un coloriage, ce qui est manifestement contradictoire. 2. O np eutp rendrel egr aphecom pletsu rk+ 1 sommets (on relie tous les sommets entre eux, sauf s'ils sont identiques ). En eet sicest un coloriage akcouleurs, d'apres le principe des tiroirs deux sommets distincts auront la m^eme couleur, mais comme ils sont relies on aboutit encore a une contradiction. 3. a) Not onsqu ecom mel 'ensembled escou leursest f0;1g, sis1ets2sont relies etcest un coloriage alorsc(s1) = 1c(s2) car siaetbsont deux elements distincts def0;1gon a necessairementa= 1b, or ici on ac(s1)6=c(s2). En particulier, sic1(s1) =c2(s1) etc1;c2 sont deux 2-coloriages, et si (s1;s2)2A, alorsc1(s2) = 1c(s1) = 1c2(s2) =c2(s2). b) Soi ts0tel quec1(s0) =c2(s0), et soits2S. Par hypothese, il existe un chemin (s0;:::;sn) avecsn=s. En utilisant la question precedente, on montre par recurrence quec1(si) = c

2(si) pour touti= 0;:::;n, d'ouc1(s) =c2(s). Ainsi8s2S,c1(s) =c2(s) dontc1=c2.

c) S i( s1;s2)2A, on a 1c(s1)6= 1c(s2) carc(s1)6=c(s2), et 1cest a valeurs dans f0;1gcar c'est le cas dec, donc 1cest bien un coloriage a 2 couleurs deG. d) Su pposonsqu eGsoit 2-coloriable, soitcun 2-coloriage deG. Sic(0) = 0, alorsGadmet bien un 2-coloriage tel quec(0) = 0, et sinon on ac(0) = 1. On considere alorsc0= 1c, qui est aussi un 2-coloriage deGd'apres la question precedente, et qui satisfaitc0(0) = 11 = 0. 4. a)

Il es tbas es url ep arcoursen pr ofondeur.

b) La b ouclewhilecorrespond a un parcours en profondeur, qui d'apres le cours a une com- plexite enO(n2). On a en suite deux bouclesforimbriquees qui sont executees chacunen fois, donc leur contenu est execute au plusn2fois, et dont le contenu est enO(1). Donc la complexite de notre algorithme est enO(n2) +O(n2) =O(n2). c) La b ouclewhileproduit une fonctionc:V! f0;1gqui, siGn'est pas 2-coloriable, n'est pas un coloriage, donc on trouve deux sommetsxetytels que (x;y)2Aetc(x) =c(y), mais alors la conditionM[x][ y ]= =1 a ndc [x]= =c [y]de la ligne 15 sera satisfaite a un moment, donc le programme retourneraFalse. d) L'i nvariantde b ouclees t: si c[x]6=1 alorsc[x] =c1(x). On verie par recurrence sur le nombre d'executions de la boucle qu'il est toujours verie, en utilisant la question 2.a) et le fait que sis1ets2sont relies, alorsc1(s2) = 1c1(s2). Comme la bouclewhileeectue un parcours en profondeur et le graphe est connexe, a un moment chaque sommetyva satisfaire la conditionc[y]= =- 1 a ndM [x][ y ]= =1 , et a ce moment la on aura bienc[y]6=1, doncc[y] =c1(y) d'apres l'invariant de boucle, ce qui conclut la preuve. e) Il es tc lairq uel 'algorithmer envoiesoi tTruesoitFalse. Par contrapposee, il sut donc de montrer : si Gest 2-coloriable, l'algorithme renvoieTrue, et si Gn'est pas 2-coloriable, l'algorithme renvoieFalse. Or le deuxieme point a ete verie dans la question c, tandis que le premier decoule de la

question precedente : siGest 2-coloriable, on a d'apres la question 3 un 2-coloriagec1telUniversite de Paris 3 UFR de mathematiques

Algorithmique et Programmation 3 Examen L2 Maths-MIASH - automne 2020 quec1(0) = 0, et d'apres la question 4.d) a la n de la bouclewhile,cconcide avecc1. Ainsi commecest un 2-coloriage, la condition de la ligne 14 ne sera jamais satisfaite, et donc l'algorithme renvoieTrue.

Exercice 4. Train de marchandises.

On suppose qu'on anvilles numerotees de 0 an1. Un train veut faire le plus de prot possible en

partant de la ville 0 et en nissant a la villen1, en parcourant les villes dans l'ordre, et en choisissant

dans quelle ville il s'arr^ete. On a une matrice carree de taillen, noteeM, telle que pour toutes villes

i < j,M[i][j]>0 est le prix de revente des denrees produites par la villeidans la villej. Chaque fois

que le train s'arr^ete dans une ville, il revend la totalite de son contenu, puis est rempli de la denree

que produit la ville. Notonsw[i] le prot maximum que peut faire le train en partant de la villei. On posew[n1] = 0. 1. M ontrerq uep ourt outi < n1 on aw[i] = maxj2fi+1;:::;n1gM[i][j] +w[j]. 2. En d eduireu nal gorithmeq uip ermettede cal culerle pr otmax imumqu ep eutf airel etr ain en partant de la ville 0. 3. Comm ents' appellel at echniqueut iliseei cip ourr esoudrece pr obleme?Q uelss ont les sous-problemes consideres? 4. Pr ouverqu ev otreal gorithmer envoiebi enl ep rotmax imumq uep eutfai rel et rain. 5. D onneru neb orneen O(f(n)) aussi precise que possible sur la complexite de votre algorithme.

Solution de l'exercice 4.

1. Si l et rainp artd el av illei, les possibilites de prochain arr^et sont donne par lesj2 fi+1;:::;n

1g, et en arrivant a la villejle train fera un beneceM[i][j], et peut ensuite gagner au mieux

w[j] par denition, donc au total fera au maximum un beneceM[i][j]+w[j]. Donc le benece maximum en partant deisera bien maxj2fi+1;:::;n1gM[i][j] +w[j], d'ou la formule. 2. O nv acal culerwde gauche a droite, comme suggere par la question precedente.1d efm ax_profit(M): 2 n l en (M) 3 t 0 n 4 f or i i n r eversed range (n 1))

5 maxi_benef

0 6 f or j i n r ange (i,n)

7 benef

M i j t j 8 i f b enef m axi_benef

9 maxi_benef

b enef 10 t i m axi_benef 11 r eturn t 0 3. Il s 'agitd epr ogrammationdy namique,l ess ous-problemesson t: q uelest l eb enecemax imal en partant d'une villei2 f0;:::;n1g? 4. O nmon trep arr ecurrenced escendantesu ri2 f0;:::;n1gquet[i]=w[i] en utilisant la formule de la question question 1 et le fait que au debut,t[n-1]= 0 =w[n1]. Par denition w[0] est le prot maximum, or le programme renvoiet[0]=w[0] donc renvoie bien le prot maximum. 5. La c omplexitee ste nO(n2) car on a deux boucles imbriquees executees chacune au plusnfois, dont le contenu est enO(1).Universite de Paris 4 UFR de mathematiquesquotesdbs_dbs13.pdfusesText_19

[PDF] examen principe de gestion 1ére année

[PDF] examen principe de gestion ihec

[PDF] principe de gestion 2

[PDF] comptabilité générale exercices corrigés maroc

[PDF] examen comptabilité générale s1 corrigé pdf

[PDF] examen de comptabilité générale

[PDF] examen comptabilité générale s1 pdf maroc

[PDF] cours de comptabilité générale s1 pdf

[PDF] examen comptabilité générale corrigé

[PDF] examen de comptabilité générale s2 corrigé

[PDF] exercices corrigés sur le décodage d adresses

[PDF] examen algorithmique récursivité

[PDF] examen algorithmique avancée corrigé

[PDF] qcm biologie animale l1

[PDF] sujet dexamen de biologie animale