Mines Informatique 1 MPI 2024Sujet et rapport du jury

5,0(2 votes)

Structures de graphes (listes d'adjacence, allocation dynamique en C)
Parcours de graphes en largeur (BFS)
Algorithmes sur les flots et chemins augmentants
Démonstrations par récurrence et par l'absurde
Complexité algorithmique

Explorer les annales

BanqueMines Année2024 FilièreMPI MatièreInformatique

Annales Mines MPI Informatique Mines MPI 2024 MPI Informatique Informatique 2024

Téléchargements

Télécharger le sujet (PDF)

Rapport du jury Lire en ligne LaTeX Word

Corrigé : pas encore disponible

Présentation du sujet

Difficile

Extraction d'un sous-graphe le plus dense d'un graphe non orienté

La première épreuve d'informatique MPI des Mines 2024 (3 heures) est un problème unique de 33 questions consacré à l'extraction d'un sous-graphe le plus dense d'un graphe non orienté quelconque. Il combine démonstrations mathématiques et programmation en langage C, en trois sections : minimisation de bordure par chemins augmentants, réduction au problème de densité, puis algorithme d'approximation plus rapide.

1Section 1 : entourage de plus petite bordureRésolution d'un problème de minimisation de bordure dans un multigraphe orienté à l'aide d'une technique de chemins augmentants, avec des questions de programmation en C (Q1 à Q19 environ).
2Section 2 : algorithme de GoldbergÉtude d'une technique de réduction du problème de construction d'un sous-graphe le plus dense au problème de la première section, avec oracle et recherche dichotomique.
3Section 3 : algorithme de CharikarÉtude d'un algorithme d'approximation plus rapide, avec analyse d'un facteur d'approximation et implémentation optimale (questions les plus rarement traitées).

Difficile. Le jury qualifie le sujet d'assez long et note que les questions des sections 2 et 3 ont été rarement traitées, notamment par manque de temps pour les dernières questions.

L'épreuve en chiffres

Moyenne 11,02 / 20 · écart-type 4,35 · 839 présents · où vous situez-vous ?

Moyenne: 11,02/ 20
Écart-type: 4,35
Présents: 839
Coefficient: 3
Durée: 3 h

Deux tiers des copies environ (moyenne ± écart-type)

Où je me situe ?

Votre note sur 20 à ce sujet, en conditions de concours.

Source : document officiel du concours, épreuve du 15 mai 2024. Notes publiées par le concours (après harmonisation le cas échéant). Courbe : estimation par une loi normale.

Ce qu'a observé le jury

6 erreurs relevées

Utilisation de constructions hors langage C · Parcours en largeur mal implémenté · Transformation de chemin non comprise

Le sujet comporte 33 questions mêlant démonstrations et programmation en C. La plupart des candidats ont abordé de façon équilibrée les deux types de questions, mais le jury rappelle que les programmes attendus sont le plus souvent courts et que des codes longs et complexes contiennent presque toujours des erreurs. Une attention particulière a été portée à la validité stricte du code C, cette épreuve pratique n'admettant aucune indulgence pour du code non valide.

Les erreurs les plus sanctionnées

1
Utilisation de constructions hors langage Cépreuve entière
Le jury n'a eu aucune indulgence pour du code non valide en C, comme l'usage de parenthèses à la place de crochets pour un tableau, de l'opérateur « <- » à la place de l'affectation, ou de constructions d'autres langages.
« aucune indulgence si le code n'était pas du code C valide »
2
Parcours en largeur mal implémentéQ7
Certains candidats écrivent un parcours en profondeur (DFS) au lieu d'un parcours en largeur (BFS), ou des parcours avec boucles infinies ou fuites mémoire.
« l'écriture d'un parcours en DFS plutôt qu'en BFS »
3
Transformation de chemin non compriseQ9
Il fallait saisir que la suppression d'un arc crée par définition un arc inverse, ce qui permet de transformer deux chemins ; c'est l'une des questions les plus mal traitées du sujet.
« l'une des questions les plus mal traitées du sujet »
4
Allocation statique au lieu d'allocation dynamiqueQ17, Q18
Le graphe est souvent alloué statiquement en variable locale au lieu d'être alloué dynamiquement, et l'initialisation du tableau de voisins pose de nombreux problèmes.
« Question finalement peu traitée »
5
Itération sur les indices au lieu du parcours de la liste chaînéeQ19
L'erreur la plus fréquente consiste à itérer sur les indices d'un tableau de voisins au lieu d'utiliser le champ suivant de la structure de liste chaînée.
« montrant ainsi une incompréhension totale de la structure de liste chaînée »
6
Division entière au lieu de division flottanteQ21
La difficulté est de forcer une division en nombres flottants en C ; mettre le résultat dans une variable de type float après une division entière ne fonctionne pas.
« Mettre le résultat après la division dans une variable de type float ou double ne fonctionne pas »

Ce qui a été bien réussi

La question 4 sur l'incrémentation est très bien traitée dans l'ensemble.
La question 5 est très bien traitée.
La question 6 est très majoritairement bien traitée.
Les questions 13 à 15 sont globalement bien traitées.

Conseils du jury

Privilégier la correction et la simplicité des codes plutôt que des programmes longs et complexes.
Ne pas imbriquer des fonctions les unes dans les autres en C.
Allouer dans le tas avec malloc une structure qu'une fonction doit retourner par référence, et non dans une variable locale.
Numéroter les questions de façon claire ; la numérotation des sections n'est pas nécessaire.
Utiliser des noms de variables intelligibles et structurer les codes longs avec des fonctions auxiliaires commentées.

Synthèse rédigée par WikiPrépa à partir du rapport officiel du jury (à télécharger en PDF). Les citations sont extraites du rapport.

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARIS, TÉLÉCOM PARIS, MINES PARIS, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.

Concours Mines-Télécom, Concours Centrale-Supélec (Cycle International).

CONCOURS 2024

PREMIÈRE ÉPREUVE D'INFORMATIQUE

Durée de l'épreuve : $3$ heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

Cette épreuve concerne uniquement las candidats de la filière MPI.

L'énoncé de cette épreuve comporte 9 pages de texte.

Abstract

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant les raisons des initiatives qu'il est amené à prendre.

Préliminaires

Présentation du sujet

L'épreuve est composée d'un problème unique comportant 33 questions divisées en trois sections. L'objectif du problème est d'extraire un sous-graphe le plus dense d'un graphe non orienté quelconque, c'est-à-dire repérer un sous-ensemble de sommets riche en arêtes. Le calcul d'un sous-graphe dense possède des applications considérables dans le domaine de la fouille des données : qu'il s'agisse de détection de communautés dans des réseaux sociaux, de repérage d'attaques par pollupostage (ou spamming) ou d'identification de complexes protéiques au sein de données biologiques massives pour ne citer que quelques exemples.

Dans la première section (page 1), nous résolvons un problème de minimisation de bordure dans un multigraphe orienté à l'aide d'une technique de chemins augmentants. Dans la deuxième section (page 5), nous étudions une technique de réduction du problème de construction d'un sous-graphe le plus dense au problème de la première section. Dans la troisième section (page 8), nous étudions un algorithme d'approximation plus rapide.

Dans tout l'énoncé, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité, mais du point de vue mathématique avec la police en italique (par exemple

n, n_(max)

n_1

) et du point de vue informatique avec celle en romain avec espacement fixe (par exemple n, NMAX ou n1).

Travail attendu

Pour répondre à une question, il est permis de réutiliser le résultat d'une question antérieure, même sans avoir réussi à établir ce résultat.

Selon les consignes, il faudra coder des fonctions à l'aide du langage de programmation C exclusivement, en reprenant le prototype de fonction fourni par le sujet, ou en pseudo-code (c-à-d. dans une syntaxe souple mais conforme aux possibilités offertes par le langage C). Inclure les entêtes tels que <assert.h>, <stdbool.h>, etc. n'est pas demandé.

Quand l'énoncé demande de coder une fonction, sauf indication explicite de l'énoncé, il n'est pas nécessaire de justifier que celle-ci est correcte ou de tester que des préconditions sont satisfaites.

Le barème tient compte de la clarté et de la concision des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle. Lorsqu'une réponse en pseudo-code est permise, seule la logique de programmation est évaluée, même dans le cas où un code en C a été fourni en guise de réponse.

1 Entourage de plus petite bordure

Dans cette section, nous travaillons dans un multigraphe orienté, c'est-à-dire un couple (

W, F, μ

) où

W

est un ensemble fini, appelé ensemble de sommets,

F

est une partie de

W \times W

, appelée ensemble d'arcs, et

μ : F \to ℕ^*

est une application, appelée multiplicité des arcs.

Les démonstrations ou justifications pourront utiliser la notion de multi-ensemble sans formalité excessive. L'intersection, notée

\cap

, se calcule en considérant le minimum des multiplicités des éléments; l'union disjointe, notée

⊔

, se calcule en considérant la somme des multiplicités des éléments; le cardinal se calcule en sommant toutes les multiplicités.

1.1 Réseaux

Définitions: Nous appelons réseau tout quintuplet

H = (W, F, μ, s, t)

tel que

$W$ est un ensemble fini, appelé ensemble de sommets,
$F$ est un sous-ensemble de couples de $W \times W$ , appelé ensemble d'arcs,
$μ$ est une application $F \to ℕ^*$ , l'entier naturel $μ(e)$ étant appelé la multiplicité de l'arc $e$ ,
$s$ est un sommet particulier de $W$ , appelé la source,
$t$ est un sommet particulier de $W$ , appelé le puits.

Indication C : Par convention, nous numérotons les sommets d'un réseau

H = (W, F, μ, s, t)

par les entiers entre 0 et

n + 1

, où

n + 2

est le cardinal de

W

. La source

s

porte le numéro 0 ; le puits

t

porte le numéro

n + 1

Nous préparons deux fichiers, network.h et network.c. Le premier fichier contient les déclarations suivantes.

/* Debut du fichier network.h */
#ifndef NETWORK_H
#define NETWORK_H
const unsigned int NMAX = 102;
struct network_s {
    unsigned int n;
    unsigned mu [NMAX] [NMAX];
};
typedef struct network_s network;
void nw_init(unsigned int n);
void nw_add(int u, int v);
void nw_remove(int u, int v);
void nw_disconnect(void);
void _arr_init(int *T);
bool _bfs_tree(void);
void _residue(void);
#endif
/* Fin du fichier network.h */

1 - Expliquer le rôle des lignes 3, 4 et 23 dans le fichier network.h.
Le second fichier contient initialement les définitions suivantes et sera complété par les fonctions de la section 1 .

/* Debut du fichier network.c */
network H;
int A[NMAX];
/* Fin du fichier network.c */

Pour tout couple

(u, v) \in W \times W

, le champ

mu[u][v]

de la variable gobale

H

vaut 0 si

(u, v)

n'est pas un arc du réseau et vaut

μ((u, v))

(u, v)

est un arc.
2 - Expliquer comment faire interagir les fichiers network.h et network.c.
3 - Écrire une fonction C void nw_init(unsigned int n) ainsi spécifiée :
Précondition : L'entier naturel

n

est strictement inférieur à la constante globale

n_(max)

.
Effet : La précondition est vérifiée par une assertion.
Postcondition : La variable globale

H

contient le réseau vide avec

n + 2

sommets et aucun arc.
4 - Écrire une fonction C void nw_add (int u, int v) qui ajoute une occurence de l'arc (

u, v

) au réseau (

W, F, μ, s, t

) stocké dans la variable globale

H

, autrement dit, qui incrémente la multiplicité

μ[u][v]

d'une unité.
5 - Écrire une fonction

C

void nw_remove(int u, int v) qui retire une occurence de l'arc (

u, v

) dans le réseau stocké dans la variable globale

H

et qui se défend, par le truchement d'une assertion, du cas où l'arc à supprimer n'existe pas.
6 - Écrire une fonction C void _arr_init(int *T) ainsi spécifiée:
Précondition : Le pointeur

T

désigne un tableau d'entiers formé de

n + 2

cases, où

n + 2

est le nombre de sommets du réseau stocké dans la variable globale

H

.
Postcondition: Toutes les cases du tableau désigné par le pointeur

T

valent -1 .
Nous utilisons le terme chemin pour signifier systématiquement un chemin simple dans le graphe orienté (

W, F

), c'est-à-dire une suite d'arcs (

e_1, \dots, e_t

) de

F

distincts qui se succèdent. Le sommet initial d'un chemin s'appelle la source, le sommet final s'appelle le puits.
7 - Écrire une fonction C bool _bfs_tree(void) ainsi spécifiée :
Précondition : La variable globale

H

contient un réseau (

W, F, μ, s, t

) à

n + 2

sommets.
Effet : La fonction calcule une arborescence

A

de plus courts chemins selon un parcours en largeur dans le graphe (

W, F

) et l'écrit dans la variable globale

A

.
Postcondition : On a

A[s] = s

et, pour tout autre sommet

v \in W

accessible depuis

s

, la case

A[v]

contient le prédécesseur du sommet

v

dans l'arborescence

A

. Enfin, toute autre case de

A

vaut -1 .
Valeur de retour : Booléen true si le puits

t

est accessible depuis la source

s

dans l'arborescence

A

. Booléen false sinon.

1.2 Déconnexion de la source et du puits

Définition : Nous disons qu'un ensemble de chemins

Π = {π_1, …, π_k}

de source commune

s

et de puits commun

t

est réalisable dans le réseau

H = (W, F, μ, s, t)

si, pour tout arc

e \in F

, les chemins de

Π

utilisent moins de

μ(e)

fois l'arc

e

, autrement dit

∀e ∈ F, Card({j ∈ [ [1, k] ] tel que e ∈ π_j}) ⩽ μ(e).

Définition : Étant donné un ensemble réalisable de chemins

Π = {π_1, …, π_k}

de source commune

s

et puits commun

t

dans un réseau

H = (W, F, μ, s, t)

, nous appelons réseau résiduel de

H

par rapport à

Π

, et nous notons

Res(H, Π)

, le réseau obtenu à partir de

H

en effectuant, pour tout indice

j

compris entre 1 et

k

et pour tout arc

e = (u, v) \in π_j

, la suppression d'une occurence de l'arc

e

et l'ajout d'une occurence de l'arc opposé

e¯ = (v, u)

◻8

- Écrire une fonction C void _residue(void) ainsi spécifiée :
Précondition : La variable globale

H

contient un réseau (

W, F, μ, s, t

). L'ensemble des arcs

{(A[v], v); 0 < v ⩽ n + 1

avec

A[v] > 0}

tiré de la variable globale

A

forme une arborescence

A

de racine

s = 0

atteignant le puits

t

dans le graphe (

W, F

).
Postcondition : La variable

H

contient le réseau résiduel

Res((W, F, μ, s, t), {α})

où

α

est l'unique chemin de source

s

et de puits

t

dans l'arborescence

A

◻9

- Nous appliquons

k

fois la fonction _residue à un réseau

H

en mettant à jour la variable globale

A

et notons

α_1, \dots, α_k

les chemins utilisés entre la source

s

et le puits

t

. Montrer qu'il est toujours possible de trouver un ensemble réalisable

Π

k

chemins dans

H

tels que le réseau obtenu des applications de _residue coïncide avec le réseau résiduel par rapport à

Π

, autrement dit tel que l'on a

Res(…Res(Res(H, {α_1}), {α_2}), …, {α_k}) = Res(H, Π)

◻10

- Écrire une fonction C void nw_disconnect(void) ainsi spécifiée : Précondition : La variable globale

H

contient un réseau (

W, F, μ, s, t

).
Effet : Tant qu'il existe un chemin de source

s

et de puits

t

, le réseau

H

est transformé en le réseau résiduel

Res((W, F, μ, s, t), {α})

, où

α

est un plus court chemin de

s

vers

t

.
Postcondition : Si la fonction se termine, il n'existe pas de chemin de la source vers le puits dans le réseau

H

. De plus, l'ensemble des arcs

{(A[v], v); 0 ⩽ v ⩽ n + 1

avec

A[v] > 0}

tiré de la variable globale

A

forme une arborescence

A

dans le réseau résiduel dans laquelle la racine est

s

et le sommet

t

n'est pas accessible.

◻11

- Démontrer que la fonction nw_disconnect se termine en introduisant un variant de boucle inspiré par la question 9 .

1.3 Optimalité

Définition : Soit

H = (W, F, μ, s, t)

un réseau et

S

un sous-ensemble de sommets de

W

. Nous appelons bordure, et notons

\partialS

, l'ensemble d'arcs allant de

S

vers son complémentaire :

\partialS = {(u, v) \in F avec u \in S et v \notin S}

Nous étendons la notion de multiplicité à des ensembles d'arcs en posant :

μ(\partialS) = \sum_(e \in \partialS)μ(e)

Définition : Nous appelons entourage dans le réseau

H = (W, F, μ, s, t)

tout sous-ensemble de sommets

S \subseteq W

contenant la source

s

mais pas le puits

t

◻12

- Soient

Π

un ensemble réalisable de

k

chemins dans un réseau

H = (W, F, μ, s, t)

S \subseteq W

un entourage dans

H

. Établir la relation

k ⩽ μ(\partialS)

Nous fixons pour les quatre prochaines questions un ensemble réalisable

Π_0

k_0

chemins dans un réseau

H

tel que, dans le réseau résiduel

Res(H, Π_0)

, il n'existe plus aucun chemin entre la source

s

et le puits

t

. Nous notons

S_0

l'entourage dans

H

composé des sommets accessibles dans

Res(H, Π_0)

depuis la source

s

◻13

- Montrer que, pour tout arc

e = (u, v) \in F

tel que

u \in S_0

v \notin S_0

, toutes les

μ(e)

occurrences de l'arc

e

sont utilisées par un chemin de l'ensemble

Π_0

◻14

- Montrer qu'aucune occurence d'un arc

(v, u) \in F

tel que

v \notin S_0

u \in S_0

n'est utilisée par un chemin de l'ensemble

Π_0

◻15

- Démontrer l'égalité

k_0 = μ(\partialS_0)

Définition : Nous disons qu'un entourage

S

est de plus petite bordure s'il minimise la multiplicité

μ(\partialS)

. Nous notons

σ(H)

la multiplicité de la bordure d'un tel entourage.

◻16

- Démontrer la relation

k_0 = σ(H)

et en déduire que, si la variable globale

H

contient un réseau, après exécution de la fonction nw_disconnect, l'ensemble

{v \in W; A[v] ⩾ 0}

est un entourage de plus petite bordure de

H

, à savoir un entourage de multiplicité

σ(H)

2 Algorithme de Goldberg

2.1 Densité d'un graphe

Pour tout ensemble fini

X

, la notation

(X/2)

désigne l'ensemble des paires (non ordonnées) à valeur dans

X

, c'est-à-dire l'ensemble

(X/2) = {{u, v} avec (u, v) ∈ X^2 tel que u ≠ v}

Définition : Un graphe non orienté est un couple

G = (V, E)

où

V

est un ensemble fini, appelé ensemble de sommets, et

E \subseteq (V/2)

est un ensemble de paires, appelé ensemble d'arêtes. Pour tout ensemble de sommets

X \subseteq V

, nous notons

G_X = (X, E_X)

le graphe

G_X = (X, E \cap (X/2))

, appelé graphe induit par

X

sur

G

Indication C : Par convention, nous numérotons les sommets de tout graphe non orienté

G = (V, E)

par les entiers entre 1 et

n

, où

n

est le cardinal de

V

. Nous représentons un graphe par un tableau de listes d'adjacence doublement chaînées en adoptant les déclarations de type suivantes.

struct link_s {
    int node;
    struct link_s *prev;
    struct link_s *next;
};
typedef struct link_s link;
struct graph_s {
    unsigned int n;
    link **neighbours;
};
typedef struct graph_s graph;

Le champ neighbours est un tableau alloué dynamiquement de longueur

n + 1

et dont la première case n'est pas utilisée. Chaque arête est stockée sous forme de deux arcs.

◻17

- Écrire une fonction C graph *gr_create(unsigned int n) dont la valeur de retour est un graphe non orienté vide à

n

sommets.
18 - Écrire une fonction C void gr_add (graph

*G

, int

u

, int v) ayant pour effet d'insérer une arête

{u, v}

dans le graphe non orienté

G

Définition : Nous notons

deg_G(v)

le degré d'un sommet

v

dans le graphe non orienté

G = (V, E)

deg_G(v)=|{u ∈ V tel que {u, v} ∈ E}|=∑_(u ∈ V t.q.; {v, u} ∈ E)1.

19 - Écrire une fonction C int degree (graph *G, int v) dont la valeur de retour est le degré

deg_G(v)

du sommet

v

dans le graphe non orienté

G

◻20

- Écrire une fonction

C

int edges (graph *G) dont la valeur de retour est le nombre d'arêtes dans le graphe non orienté

G

Définition : Nous appelons densité du graphe

G = (V, E)

le rapport

δ(G) = m/n

où

n

est le cardinal de

V

m

est le cardinal de

E

.
21 - Écrire une fonction C double density (graph *G) dont la valeur de retour est la densité

δ(G)

du graphe non orienté

G

Définition : Le problème d'optimisation du sous-graphe le plus dense d'un graphe non orienté

G

consiste à trouver un ensemble de sommets non vide

X

tels que la densité

δ(G_X)

du sous-graphe induit

G_X = (X, E_X)

est maximale et calculer cette densité maximale

ρ(G) = max_(X \subseteq V;; X \neq \emptyset)δ(G_X)

2.2 Oracle pour le problème de décision

Nous nous intéressons au problème de décision suivant :
Étant donnés un graphe non orienté

G

n

sommets et un entier naturel

r

, existe-t-il un sous-graphe induit

G_X = (X, E_X)

de densité

δ(G_X)

strictement supérieure au seuil

r/(n^2)

? Autrement dit, a-t-on

ρ(G) > r/(n^2)

Définition : Étant donnés un graphe non orienté

G = (V, E)

avec

n

sommets et

m

arêtes ainsi qu'un entier naturel

r

, nous appelons réseau associé au graphe

G

et au seuil

r

le réseau

H = (W, E, μ, s, t)

où
(a) L'ensemble

W

est la réunion

W = V \cup {s, t}

, les sommets source

s

et puits

t

étant de nouveaux sommets n'appartenant pas à

V

(β)

L'ensemble d'arcs

F

comprend:

pour tout sommet $v \in V$ , un arc $(s, v)$ , de multiplicité $mn^2$ .
pour toute arête ${u, v} \in E$ , un $arc(u, v)$ et un $arc(v, u)$ , de multiplicité $n^2$ .
pour tout sommet $u \in V$ , un arc $(u, t)$ , de multiplicité $mn^2 - n^2 deg_G(u) + 2r$ .

22 - Écrire une fonction C void reduce (graph

*G

, int

r

) ayant pour effet d'initialiser la constante globale

H

, de type network, par le réseau associé au graphe

G

et au seuil

r

23 - Soient

G = (V, E)

un graphe non orienté et

X \subseteq V

une partie non vide des sommets. Montrer que la densité du graphe induit

G_X = (X, E_X)

satisfait la relation

૯δ(G_X) = (∑_(v ∈ X)deg_G(v) − ∑_(u ∈ X, v ∈ V∖X; t.q.{u,v}૯E)1)/(2|X|)

24 - Soient

G = (V, E)

un graphe non orienté avec

n

sommets et

m

arêtes,

X \subseteq V

une partie non vide des sommets,

H

le réseau associé au graphe

G

et à un seuil

r

S

l'entourage

S = {s} \cup X

dans

H

. Montrer que la multiplicité de la bordure de

S

satisfait l'égalité

μ(\partialS) = mn^3 + 2|X|(r - n^2 δ(G_X))

et que

μ(∂{s}) = mn^3

25 - Soit

H

le réseau associé au graphe

G

et au seuil

r

et soit

σ(H)

la multiplicité de la bordure d'un entourage de plus petite bordure. Montrer les équivalences suivantes :

{σ(H) = mn^3 ⇔ ρ(G) ⩽ r/(n^2); σ(H) < mn^3 ⇔ ρ(G) > r/(n^2)

◻26

- Écrire une fonction C bool oracle (graph

*G

, int r) dont la valeur de retour est le booléen true si

ρ(G) > r/(n^2)

et false si

ρ(G) ⩽ r/(n^2)

. En justifier le principe. On pourra s'intéresser au contenu du tableau global

A

après exécution de la fonction nw_disconnect.

2.3 Recherche dichotomique

Nous considérons l'ensemble de couples d'entiers

Δ = {(m^′, n^′) ∈ ℕ^2 avec 0 ⩽ m^′ ⩽ m et 1 ⩽ n^′ ⩽ n}.

27 - Soient deux couples (

m_1, n_1

) et (

m_2, n_2

) appartenant à

Δ

. Montrer que,

si (m_1)/(n_1) \neq (m_2)/(n_2), alors |(m_1)/(n_1) - (m_2)/(n_2)| ⩾ 1/(n^2).

28 - Soient

G = (V, E)

un graphe non orienté à

n

sommets et

X

une partie non vide de

V

. Montrer que s'il n'existe aucun sous-graphe induit de densité supérieure ou égale à

δ(G_X) + 1/(n^2)

, alors le sous-graphe induit

G_X

est un sous-graphe de densité maximale

ρ(G)

.
29 - Écrire une fonction C efficace void binary_search (graph *G) qui, pour tout graphe

G = (V, E)

, modifie le tableau global

A

de sorte que l'ensemble de sommets

X = {v \in V; A[v] ⩾ 0}

vérifie

δ(G_X) = ρ(G).

Justifier brièvement le principe de fonctionnement de la fonction.
30 - Nous supposons avoir écrit l'ensemble des fonctions de la section 2 dans un fichier densest_subgraph.c. Expliquer comment faire interagir le fichier densest_subgraph.c avec les fichiers network.h et network.c de la section 1.

3 Algorithme de Charikar

Dans le cadre d'un compromis entre temps d'exécution et justesse du calcul d'optimisation, nous nous intéressons à l'algorithme suivant.

Algorithme 1 : Recherche gloutonne d'une densité élevée
    Entrées : Graphe $G=(V, E)$.
    Sorties : Sous-graphe induit à grande densité
    $\Gamma \leftarrow G$; /* Plus dense graphe rencontré */
    $G_{n} \leftarrow G$ où $n=|V|$
    pour $i$ de $n$ à 2 (cas inclus) faire
        si $\delta\left(G_{i}\right)>\delta(\Gamma)$ alors
            $\Gamma \leftarrow G_{i}$
        Identifier le sommet $v_{i}$ qui minimise le degré $\operatorname{deg}_{G_{i}}$.
        Former le graphe $G_{i-1}$ en supprimant de $G_{i}$ le sommet $v_{i}$ et les
        arêtes incidentes à $v_{i}$.
    retourner $\Gamma$

3.1 Analyse d'un facteur d'approximation

Définition : Nous appelons orientation d'un graphe non orienté

G = (V, E)

tout graphe orienté

Gˆ = (V, Eˆ)

tel qu'il existe une bijection

ω : E \to Eˆ

avec

ω({u, v}) = (u, v)

pour tout

arc(u, v) \in Eˆ

. Le degré entrant d'un sommet

v

dans un graphe orienté

Gˆ = (V, Eˆ)

est

deg_(Gˆ)^−(v) = Card({u ∈ V tel que (u, v) ∈ Eˆ}) = ∑_(u ∈ V t.q.; (u, v) ∈ Eˆ)1.

◻31

- Établir la majoration suivante entre la densité d'un graphe non orienté quelconque

G

et le degré entrant maximum d'une orientation quelconque

Gˆ

de G

δ(G) ⩽ max_(v \in V)deg_(Gˆ)^-(v)

Nous exécutons l'algorithme 1 sur un certain graphe non orienté

G

. Dans les questions qui suivent, nous numérotons les sommets de

G

selon la même numérotation que celle de l'algorithme. Nous notons

ω_0

la bijection qui oriente l'arête

{v_i, v_(i^′)}

dans le sens (

v_(min(i, i^')), v_(max(i, i^'))

) et

Gˆ_0

l'orientation associée. Autrement dit, nous orientons toute arête, au moment de sa suppression, vers le sommet incident qui a conduit à sa suppression.

◻32

- Établir, pour tout

i

compris entre 1 et

n

, l'inégalité

deg_(Gˆ_0)^-(v_i) ⩽ 2δ(G_i)

et en déduire que l'algorithme 1 est un algorithme d'approximation dont on précisera le facteur d'approximation.

3.2 Implémentation optimale

◻33

- Détailler une structure de données qui permette d'exécuter l'algorithme 1 en temps

O(n + m)

où

n = |V|

m = |E|

. Il est suggéré de nantir la structure de données graph d'une table qui maintient, pour tout entier

d

compris entre 0 et

n

, la collection des sommets de degré

d

ainsi que d'autres éléments que l'on jugera opportuns.
Une réponse décrite en pseudo-code ou en langage naturel est admise mais doit être suffisamment précise pour s'assurer que la complexité est belle et bien linéaire.

Fin de l'épreuve

Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de la licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de Modification 3.0 France.

Tout autre usage est soumis à une autorisation préalable du Concours commun Mines Ponts.

Questions fréquentes

4 questions

Sur quoi porte le sujet d'informatique 1 MPI des Mines 2024 ?

Sur l'extraction d'un sous-graphe le plus dense d'un graphe non orienté, avec un algorithme de chemins augmentants, l'algorithme de Goldberg puis celui de Charikar.

Le sujet d'informatique 1 MPI Mines 2024 est-il long ?

Oui, le jury le qualifie d'assez long avec 33 questions ; les questions des dernières sections ont été rarement traitées, souvent par manque de temps.

Quelles erreurs le jury a-t-il le plus relevées en informatique 1 MPI Mines 2024 ?

L'usage de constructions non valides en C, un parcours en profondeur écrit à la place d'un parcours en largeur, une allocation statique au lieu de dynamique, et une itération sur les indices au lieu du parcours de la liste chaînée.

Ce sujet d'informatique MPI Mines 2024 demande-t-il de coder en C ?

Oui, les réponses de programmation doivent être écrites en langage C, avec une tolérance uniquement pour un point-virgule ou une accolade manquante, mais aucune indulgence pour du code non valide.

Pas de description pour le moment

Commentaires• Mines Informatique 1 MPI 2024

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...

Explorer les annales

Téléchargements

Présentation du sujet

L'épreuve en chiffres

Ce qu'a observé le jury

Les erreurs les plus sanctionnées

Ce qui a été bien réussi

Conseils du jury

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARIS, TÉLÉCOM PARIS, MINES PARIS, MINES SAINT-ÉTIENNE, MINES NANCY, IMT ATLANTIQUE, ENSAE PARIS, CHIMIE PARISTECH - PSL.

CONCOURS 2024

PREMIÈRE ÉPREUVE D'INFORMATIQUE

Durée de l'épreuve : 3 heures

Abstract

Préliminaires

Présentation du sujet

Travail attendu

1 Entourage de plus petite bordure

1.1 Réseaux

1.2 Déconnexion de la source et du puits

1.3 Optimalité

2 Algorithme de Goldberg

2.1 Densité d'un graphe

2.2 Oracle pour le problème de décision

2.3 Recherche dichotomique

3 Algorithme de Charikar

3.1 Analyse d'un facteur d'approximation

3.2 Implémentation optimale

Fin de l'épreuve

Questions fréquentes

Sur quoi porte le sujet d'informatique 1 MPI des Mines 2024 ?

Le sujet d'informatique 1 MPI Mines 2024 est-il long ?

Quelles erreurs le jury a-t-il le plus relevées en informatique 1 MPI Mines 2024 ?

Ce sujet d'informatique MPI Mines 2024 demande-t-il de coder en C ?

Commentaires• Mines Informatique 1 MPI 2024

Commentaires• Mines Informatique 1 MPI 2024

Durée de l'épreuve : $3$ heures