Examen dalgorithmique géométrique PDF

Exercices avec Solutions

Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1. Ecrire un algorithme qui demande 1- Calcul de la somme des N premiers nombres entiers.

Exercices Corrigés Matrices Exercice 1 – Considérons les matrices

Puis calculer A-1. Exercice 8 – Appliquer avec précision aux matrices M et N suivantes l'algorithme du cours qui détermine si une matrice est inversible et

Langage C : énoncé et corrigé des exercices IUP GéniE

Exercice 1 1 Ecrire un progra mm e dans l e q ue l vous : 1. Déc l arere z un entier i et un pointeur vers un entier p

Exercices corrigés

Les scripts du cours. Cours no 1 : « Premiers pas en Python ». 1. Affectez les variables temps et distance par les valeurs 6.892 et 19.7.

ALGORITHME SECONDE Exercice 5.1 Ecrire un algorithme qui

Exercice 5.1. Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 jusqu'à ce que la réponse convienne. corrigé - retour au cours.

Algorithmique — M1 - Examen du 11/1/11 -corrigé

11 janv. 2011 Examen du 11/1/11 -corrigé. Université Paris Diderot. On applique un algorithme de cours. Exercice 1 – Routage.

Correction de lExamen Final

Complexité algorithmique 2010-2011. P. Baillot. B. Grenet. Correction de l'Examen Final. Exercice 1. Pour les définitions

Algorithmique — M1 - Examen du 11 janvier 2010

11 janv. 2010 Examen du 11 janvier 2010. Corrigé. On applique un algorithme de cours. Exercice 1 – Flux maximum. Pour le réseau ci-dessus on cherche à ...

Examen du 18 janvier 2008 - corrigé - version ?2

18 janv. 2008 Exercice 1 – Arbre couvrant minimum ... un algorithme de cours. 1. Choisissez un algorithme (écrivez juste son nom s'il s'agit d'un ...

Examen dalgorithmique géométrique

Examen. M1 Info M1 Math-Info. - Examen d'algorithmique géométrique -. - Corrigé rapide -. Barême : Exercice 1 sur 8 points : 1) 0.5pts - 2) 1pt - 3) 1pt

Geometrie Algorithmique, FMIN215Annee 2014-2015

Examen.

M1 Info, M1 Math-Info.- Examen d'algorithmique geometrique - - Corrige rapide -

Bar^eme :

Exercice 1 sur 8 points : 1) 0.5pts - 2) 1pt - 3) 1pt - 4) 1pt - 5) 0.5pts - 6) 1.5pts - 7) 2.5pts - Exercice 2 sur 4 points : 1) 0.5pts - 2) 1pt - 3) 0.5pts - 4) 0.5pts - 5) 1.5pts - Exercice 3 sur 8 points : 1) 1pt - 2) 1pt - 3) 1pt - 4) 1.5pts - 5) 2pts - 6) 1.5pts - - Exercice 1 - Test d'appartenance a un polygone convexe -

1. Voir cours, ou CC...

2. L'algo suivant marche :pour tous lesi= 1anfairesipest a droite de[pipi+1]oriente depiapi+1alorsretournerfaux;retournervrai;3. Non, ce test ne fonctionne plus siPn'est pas convexe. Par exemple, dans l'exemple

ci-dessous,pest dansPmais est a droite du segment [p2p3] oriente dep2versp3.4. On peut lancer un algorithme de calcul d'enveloppe convexe sur l'ensemble de points

fp1;:::;png.A partir du pointp1, on deroule l'enveloppe convexe a partir dep1.P est convexe si et seulement si on tombe sur la liste (p1;p2;:::;pn) (en supposant que tous lespisoient disjoints). Si on utilise l'algo de Graham, on obtient une complexite enO(nlogn).

5. Voir exemple ci-dessous.1

Geometrie Algorithmique, FMIN215Annee 2014-2015

Examen.

M1 Info, M1 Math-Info.6. Soitpest a droite du segment [pipk] oriente depiverspk, soit il est a droite de [pkpj]

oriente depkverspj, soit il est a gauche de ces deux segments et il est dans le triangle p ipjpket donc dans le polygoneP.

7. On peut alors construire un algo par dichotomie :sipest a gauche de[p1pn]oriente dep1apnalorsretournernon;i 1;

j n; tant queji >1fairek bi+j2 c; sipest a droite de[pipk]oriente depiapkalorsj k; sinonsipest a droite de[pkpj]oriente depkapjalorsi k; sinon retourneroui;//pest dans le trianglepipjpk, donc dansPretournernon; A chaque tour de boucle,jidiminue de moitie. On fait donc au plusO(logn) tours de boucle. Chaque autre operation elementaire s'eectue enO(1), donc globalement l'algo fonctionne enO(logn). - Exercice 2 --shape -

1. Voir cours...

2. Voir exemple ci-dessous.3. Si <12

minfpq:p2 P; q2 P; p6=qgalors un disque de rayonest trop petit et ne peut avoir deux points dePcomme diametre. Donc, l'-shape dePest vide.

4. Sipqest une ar^ete de l'-shape, alors par denition il existe un disque de rayon

contenantpetqsur son bord et aucun point dePdans son interieur. Par le Lemme 1, pqest une ar^ete de la triangulation de Delaunay.

5. Dans ce cas l'-shape est l'enveloppe convexe deP. En eet, supposons que ce ne soit

pas le cas, l'-shape contiendrait une ar^etepqbordee par deux trianglesT1etT2de la triangulation de Delaunay deP. Commepqest une ar^ete de l'-shape deP, il existe un disqueDde rayoncontenantpetqsur son bord et aucun point dePdans son interieur. CommeT1etT2sont de part et d'autre depq, un de ces triangles, disons T

1est du m^eme c^ote queDpar rapport apq. Par hypothese, le rayon deD() est

strictement plus grand que le rayon du cercle circonscrit aT1. DoncDdoit contenir 2

Geometrie Algorithmique, FMIN215Annee 2014-2015

Examen.

M1 Info, M1 Math-Info.le troisieme point (dierent depetq) du triangleT1, ce qui contredit la denition de

D. - Exercice 3 - Arbre euclidien minimum -

1. L'exemple suivant repond a la question :2. On constuit un graphe complet dont les sommets sont les points deP. Chaque ar^ete

pqest valuee par la distance depaq. On lance l'algorithme de Kruskal sur le graphe construit. L'arbre retourne est un ACEM deP. Le graphe constuit posseden(n1)=2 ar^etes. L'algo propose tourne donc en tempsO(n2logn).

3. On aACAO+OC(inegalite triangulaire, 'la ligne droite est le plus court che-

min...'). De plus, on aAO=r, ourdesigne le rayon deD, etOC < r. Finalement, on obtientAC <2r=AB.

4. Notonspetqles deux points les plus proches deP. SoitDle disque de rayon [pq]. Si

Dcontient dans son interieur un sommetrdeD, par la question precedente, on aurait pr < pq, ce qui contredit le choix depet deq. L'interieur deDne contient ainsi pas de points deP. Par le Lemme 1,pqest une ar^ete de la triangulation de Delaunay.

5. On generalise la reponse de la question precedente. Soitpqune ar^ete deT. Le graphe

Tpqcontient deux composantes connexes qui sont des arbres :Tpcontenantpet T qcontenantq. SoitDle disque de rayon [pq]. SiDcontient dans son interieur un sommetrdeD. Supposons quer2Tq. Par la question 3, on apr < pq. Mais alors, (Tpq) +prserait un arbre couvrant deP(carprest une ar^ete reliantTpetTq et de longueur total strictement inferieure a celle deT, ce qui contredit la denition deT. Sir2Tp, on raisonne de m^eme pour aboutir a une contradiction. AinsiDne contient pass de point dePdans son interieur etpqest une ar^ete de la triangulation de Delaunay deP.

6. On calcule la triangulation de Delaunay dePen tempsO(nlogn). Celle-ci contient

moins de 3nar^etes (3(n1) jEC(P)jpour ^etre precis...). On applique alors l'algo- rithme de Kruskal en tempsO(nlogn) sur ce graphe dont on value les ar^etes par les distances entre les points (comme a la question 1). Finalement, on obtient un ACEM dePen tempsO(nlogn). 3quotesdbs_dbs46.pdfusesText_46

[PDF] Examen dalgorithmique géométrique

Geometrie Algorithmique, FMIN215Annee 2014-2015

Examen.

Bar^eme :

1. Voir cours, ou CC...

2. L'algo suivant marche :pour tous lesi= 1anfairesipest a droite de[pipi+1]oriente depiapi+1alorsretournerfaux;retournervrai;3. Non, ce test ne fonctionne plus siPn'est pas convexe. Par exemple, dans l'exemple

5. Voir exemple ci-dessous.1

Geometrie Algorithmique, FMIN215Annee 2014-2015

Examen.

7. On peut alors construire un algo par dichotomie :sipest a gauche de[p1pn]oriente dep1apnalorsretournernon;i 1;

1. Voir cours...

2. Voir exemple ci-dessous.3. Si <12

4. Sipqest une ar^ete de l'-shape, alors par denition il existe un disque de rayon

5. Dans ce cas l'-shape est l'enveloppe convexe deP. En eet, supposons que ce ne soit

1est du m^eme c^ote queDpar rapport apq. Par hypothese, le rayon deD() est

Geometrie Algorithmique, FMIN215Annee 2014-2015

Examen.

1. L'exemple suivant repond a la question :2. On constuit un graphe complet dont les sommets sont les points deP. Chaque ar^ete

3. On aACAO+OC(inegalite triangulaire, 'la ligne droite est le plus court che-

4. Notonspetqles deux points les plus proches deP. SoitDle disque de rayon [pq]. Si

5. On generalise la reponse de la question precedente. Soitpqune ar^ete deT. Le graphe

6. On calcule la triangulation de Delaunay dePen tempsO(nlogn). Celle-ci contient