📚 الرئيسية
دخول

مسابقة دكتوراه 2014 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 07

مسابقة تخصص · Recherche Opérationnelle · المدة: 2سا

⬇️ تحميل☆ حفظ✓ تم الحل

Concours d’accès au Doctorat LMD en Recherche Opérationnelle et Management, épreuve écrite Réseaux et Optimisation, USTHB, Faculté des Mathématiques, Département de Recherche Opérationnelle, année universitaire 2013-2014, durée 2h.

التمرين 1

Exercice 1 — Forêts maximales et arbres couvrants

#minimum-spanning-tree#integer-programming#complexity

Soit R=(X,E,p)R=(X,E,p) un réseau connexe, où p:E→Zp:E\to\mathbb{Z}.

  1. Décrire un algorithme de forêt de poids maximum et donner sa complexité.
  2. Donner une formulation binaire du problème.
  3. Montrer que le problème est polynomial.
  4. Montrer que, si tous les poids sont positifs, la forêt optimale est un arbre.
  5. Adapter l’algorithme à l’arbre de poids maximum.
  6. Pour des distances positives, formuler et résoudre le problème de l’arbre de poids minimum.
  7. Montrer que la contrainte d(v)≤2d(v)\le2 rend le problème NP-complet.
◀الحل

1.

Kruskal en ordre décroissant résout le problème en O(mlog⁡m)O(m\log m).

max⁡∑e∈Epexe\max\sum_{e\in E}p_ex_e

sous

∑e∈E(S)xe≤∣S∣−1,xe∈{0,1}.\sum_{e\in E(S)}x_e\le|S|-1, \qquad x_e\in\{0,1\}.

2.

Avec des poids positifs, toute forêt non connexe peut être augmentée.

3.

La contrainte de degré 22 transforme l’arbre couvrant en chemin hamiltonien.

Le probleˋme est NP-complet.\boxed{\text{Le problème est NP-complet.}}

التمرين 2

Exercice 2 — Hypercube et codes binaires

#hypercube#hamiltonian-cycles#coding-theory
  1. Montrer que QnQ_n est hamiltonien pour n≥2n\ge2.
  2. Pour un sommet xx de QnQ_n : a. compter les sommets à distance ii de xx ; b. compter les sommets de poids pair ; c. compter les sommets de poids impair.
  3. Montrer l’équivalence entre un code dans QnQ_n de distance minimale 2p2p et un code de même cardinal dans Qn−1Q_{n-1} de distance minimale 2p−12p-1.
◀الحل

1.

Un code de Gray cyclique fournit un cycle hamiltonien.

2.

Ni(x)=(ni)\boxed{N_i(x)=\binom ni} Npair=Nimpair=2n−1\boxed{N_{\mathrm{pair}}=N_{\mathrm{impair}}=2^{n-1}}

3.

Le poinçonnage diminue la distance d’au plus 11, et l’ajout d’un bit de parité rend les distances paires.

A(n,2p)=A(n−1,2p−1)\boxed{A(n,2p)=A(n-1,2p-1)}
→السابقConcours Doctorat 2014 — Université Mohamed Khider - Biskra — Épreuve N°06التاليConcours Doctorat 2014 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°08←