[PDF] Examen - 26 juin 2019 26 juin 2019 L'examen

View - Download Examen - 26 juin 2019

Previous PDF

Next PDF

Licence Informatique, semestre 5 2019{20

Elements de logique pour l'informatique (Info 315) 10 juin 2020 http://www.lri.fr/ ~paulin/Logique

Examen - 26 juin 2019

L'examen dure 2 heures. L'enonce est compose de 2 pages. Toutes les reponses devront ^etre clairement

justiees. Le seul document autorise est une page A4 manuscripte recto-verso. Inscrivez votre nom sur chaque copie et numerotez-les. Cacheter toutes les copies. Re- copier le numero d'anonymat sur les intercalaires et sur le QCM.

Exercice 1QCM (6 points)

Lenumero d'anonymatde la copie principale (pas le numero d'etudiant) doit ^etre reporte sur

l'enonce du QCM (noircir les cases prevues a cet eet et reporter le numero en clair). Utiliser un stylo

bleu ou noir pour cocher les cases.

Des points negatifs sont attribues en cas de reponse fausse aux questions 1 a 3 (retrait de la moitie

des points attribes a une reponse correcte : une reponse juste et deux reponses fausses valent 0).

N'oubliez pas de rendre le QCM avec vos copies.

Exercice 2Questions de cours (3 points)

1. On s edonne trois form ulesA,BetCdu calcul propositionnel et on veut savoir siCest consequence logique ou non des formulesAetB. En vous appuyant sur les techniques vues en cours et en TD, proposer deux methodes dierentes pour repondre a cette question. Vous detaillerez les grandes etapes mais sans entrer dans le detail des regles logiques. Typiquement votre reponse sera organisee de la maniere suivante : (a) On applique les transformations suiv antesaux form ulesA;B;C: \......" (b) A l'aide des r egles\. ....."vues en cour sappliqu ees al'ob jet\. .....",on construit \. ....." (c) Suiv antla forme de l'ob jetconstruit, on en d eduit\. ....." 2. P eut-onf airela m ^emec hosesi A,BetCsont des formules du calcul des predicats? Exercice 3Modelisation, modeles et preuves (12 points).

On s'interesse au probleme de coloriage d'un graphe. Il s'agit d'attribuer une couleur a chaque sommet

du graphe de maniere a ce que deux sommets qui sont relies par une ar^ete n'aient pas la m^eme couleur.

Dans la premiere partie de l'exercice, on utilise la logique du premier ordre. Dans la seconde partie,

le probleme est modelise en utilisant le calcul propositionnel. Cette seconde partie est completement

independante de la premiere. Partie I : Modelisation en calcul des predicats (8 points). On se donne un langage dans lequel il y a deux predicats binairesEetcolet un predicat unaireV tels que |V(x) est vrai exactement lorsquexest unsommet du graphe |E(x;y) est vrai exactement lorsquexetysont deux sommetsrelies par une ar^etedu graphe. |col(x;c) est vrai exactement lorsque le sommetxestassocie a la couleurc.

D'un point de vue logique, n'importe quel element de l'univers peut representer une couleur, y compris

les sommets du graphe. Attention, il n'y a pas de predicat pour l'egalite dans le langage, les formules

ne devront donc pas utiliser l'egalite. I-1 F ormaliserles enoncessuiv antsqui seron tpar la suite n otesPetQ: P :

A tout sommet est asso cie(au moins) une couleur

Q : Deux sommets reli esp arune ar ^etene son tpas asso cies ala m ^emecouleur I-2

Soit la form ule8x;V(x)):E(x;x) noteeR.

1 (a)A quelle propr ietedu graphe de sommets Vet d'ar^etesEcorrespond la formuleR? (b) En utilisan tla m ethodede r esolution(don ton d etaillerales etapes),mon trerque Rest consequence logique dePet deQ. I-3 Soien tun domaine Det des interpretations deEet deVquelconques qui satisfont la proprieteR. (a) Mon trerqu'il e xistetoujours une in terpretationd ecoltelle que les formulesPetQsont vraies dans cette interpretation. (b) P eut-onen d eduireque P^Qest consequence logique deR? pourquoi? I-4 On mo diele probl emeen in troduisantdan sle langage deux constan tesbleuetrouge. On rem- place la formulePqui dit qu'a tout sommet est associe une couleur, par la formuleP0qui dit qu'a tout sommet est associe une des deux couleursbleuourouge. (a)

Donner la f ormuleP0.

(b) On se p lacesur le domaine Ddes entiers naturels, et dans une interpretation dans laquelle le predicatVest toujours vrai et la relationE(n;m) est vraie si et seulement sin+mest impair. La couleurbleuest interpretee 0 et la couleurrougepar 1. i. La form uleRest-elle vraie dans cette interpretation? ii. T rouverune in terpretationde colqui rend vraies les formulesP0etQ. (c) Dans un domain eDet une interpretation deEet deVquelconque qui rend vraie la formule R, existe-t-il toujours une interpretation decolqui rend vraies les formulesP0etQ? Justier votre reponse. Partie II : Modelisation en calcul propositionnel (4 points). On s'interesse maintenant au m^eme probleme mais dans le cadre du calcul propositionnel. On a donc un graphe qui est deni par un ensemble niSde sommets et une relationAentre ces sommets correspondant aux ar^etes. On cherche a colorier ce graphe avec plusieurs couleurs. Pour cela on va introduire des variables propositionnelles qui modelisent la couleur des sommets. On denit un ensemble de formules correspon-

dant aux contraintes du coloriage (deux sommets relies par une ar^ete n'ont pas la m^eme couleur). On

cherche ensuite des solutions en utilisant la logique dont on pourra deduire les proprietes de coloriage

de notre graphe initial. Par exemple, si on a deux sommetsxety, on pourra introduire deux variables propositionnelles XetYtelles queXest vraie si et seulement si le sommetxest colorie en bleu etYest vrai si et seulement si le sommetyest colorie en bleu. S'il existe une ar^ete entrexetydans le graphe, alors on introduira une formuleX):Yqui dit que sixest bleu alorsyne peut pas ^etre bleu. Et ceci pour

toutes les ar^etes et toutes les couleurs. Si l'ensemble des formules ainsi obtenu est satisable alors un

modele de cet ensemble correspond a une solution du probleme de coloriage. II-1 On supp oseque l' onv eutcolorier le graphe a vecseulemen tdeux couleurs bleuetrouge. (a) Mon trerqu'il sut d 'utiliserun ev ariableprop ositionnellepar sommet que l'on notera Cx. Expliquer comment la valeur de verite deCxest reliee a la couleur du sommetx. (b) Donner un ensem blede clauses propositionnellesqu'il faut satisfaire pour trouver un colo- riage du graphe en utilisant les variables propositionnellesCx, on pourra utiliser les ensembles

SetApour caracteriser les formules.

(c) Expliciter ces clauses dans le cas p articuliero uSest un ensemble de trois sommetsa,betc tous relies entre eux. Montrer que l'ensemble de clauses ainsi obtenu est insatisable. Qu'en deduisez-vous concernant la possibilite de colorier ce graphe avec 2 couleurs? II-2 On s'in teressemain tenant aun coloriage a vecplus d edeux couleurs. (a) S'il y a trois couleurs bleu,rougeetvert, combien faut-il de variables propositionnelles pour modeliser le probleme en fonction du nombre de sommets du graphe? Combien faut-il de clauses en fonction du nombre d'ar^etes et du nombre de couleurs? (b) A-t-on b esoinde plus de v ariablesprop ositionnellesp ourm odeliserle prob lemea vec4 cou- leurs? de maniere generale combien de variables propositionnelles sont necessaires pour modeliser le probleme en fonction du nombre de couleurs? 2quotesdbs_dbs29.pdfusesText_35

[PDF] PLANNING DES EXAMENS DE RATTRAPAGE DE S2 FILIERE

[PDF] Examen Matière : Marketing International - L 'ENT de IGA Rabat

[PDF] Première LMD ST (S1) ~ Faculté des Sciences (Univ Tlemcen)

[PDF] Université des Sciences et de la Technologie Houari - usthb

[PDF] Épreuves uniques - Enseignement secondaire, 2e cycle

[PDF] IMM 5753F : Demande d 'examen médical - Citoyenneté et

[PDF] Les métiers des Sciences

[PDF] Microscopie en bacteriologie - Direction des laboratoires

[PDF] Calendrier Primaire 2017-2018

[PDF] Épreuve unique - Enseignement secondaire, 2e cycle - Histoire et

[PDF] Épreuves uniques - Enseignement secondaire, 2e cycle - Science et

[PDF] coproculture - XLABS laboratoire

[PDF] Nederlands - vwo: vakspecifieke informatie centraal examen 2016

[PDF] Examen normalisé

[PDF] Examen normalisé