J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Mines Informatique 1 MPI 2024

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo mines
🔗 Explorer
Banque
Mines
Année
2024
Filière
MPI
Matière
Info
Mines MPIMines 2024MPI InfoInfo 2024
2025_08_29_c0b7bce4bb61bd481e81g

É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 : 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 ou ) 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 ( ) où est un ensemble fini, appelé ensemble de sommets, est une partie de , appelée ensemble d'arcs, et 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 , 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 tel que
  • est un ensemble fini, appelé ensemble de sommets,
  • est un sous-ensemble de couples de , appelé ensemble d'arcs,
  • est une application , l'entier naturel étant appelé la multiplicité de l'arc ,
  • est un sommet particulier de , appelé la source,
  • est un sommet particulier de , appelé le puits.
Indication C : Par convention, nous numérotons les sommets d'un réseau par les entiers entre 0 et , où est le cardinal de . La source porte le numéro 0 ; le puits porte le numéro .
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 , le champ de la variable gobale vaut 0 si n'est pas un arc du réseau et vaut si 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 est strictement inférieur à la constante globale .
Effet : La précondition est vérifiée par une assertion.
Postcondition : La variable globale contient le réseau vide avec sommets et aucun arc.
4 - Écrire une fonction C void nw_add (int u, int v) qui ajoute une occurence de l'arc ( ) au réseau ( ) stocké dans la variable globale , autrement dit, qui incrémente la multiplicité d'une unité.
5 - Écrire une fonction void nw_remove(int u, int v) qui retire une occurence de l'arc ( ) dans le réseau stocké dans la variable globale 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 désigne un tableau d'entiers formé de cases, où est le nombre de sommets du réseau stocké dans la variable globale .
Postcondition: Toutes les cases du tableau désigné par le pointeur valent -1 .
Nous utilisons le terme chemin pour signifier systématiquement un chemin simple dans le graphe orienté ( ), c'est-à-dire une suite d'arcs ( ) de 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 contient un réseau ( ) à sommets.
Effet : La fonction calcule une arborescence de plus courts chemins selon un parcours en largeur dans le graphe ( ) et l'écrit dans la variable globale .
Postcondition : On a et, pour tout autre sommet accessible depuis , la case contient le prédécesseur du sommet dans l'arborescence . Enfin, toute autre case de vaut -1 .
Valeur de retour : Booléen true si le puits est accessible depuis la source dans l'arborescence . Booléen false sinon.

1.2 Déconnexion de la source et du puits

Définition : Nous disons qu'un ensemble de chemins de source commune et de puits commun est réalisable dans le réseau si, pour tout arc , les chemins de utilisent moins de fois l'arc , autrement dit
Définition : Étant donné un ensemble réalisable de chemins de source commune et puits commun dans un réseau , nous appelons réseau résiduel de par rapport à , et nous notons , le réseau obtenu à partir de en effectuant, pour tout indice compris entre 1 et et pour tout arc , la suppression d'une occurence de l'arc et l'ajout d'une occurence de l'arc opposé .
- Écrire une fonction C void _residue(void) ainsi spécifiée :
Précondition : La variable globale contient un réseau ( ). L'ensemble des arcs avec tiré de la variable globale forme une arborescence de racine atteignant le puits dans le graphe ( ).
Postcondition : La variable contient le réseau résiduel où est l'unique chemin de source et de puits dans l'arborescence .
- Nous appliquons fois la fonction _residue à un réseau en mettant à jour la variable globale et notons les chemins utilisés entre la source et le puits . Montrer qu'il est toujours possible de trouver un ensemble réalisable de chemins dans 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
- Écrire une fonction C void nw_disconnect(void) ainsi spécifiée : Précondition : La variable globale contient un réseau ( ).
Effet : Tant qu'il existe un chemin de source et de puits , le réseau est transformé en le réseau résiduel , où est un plus court chemin de vers .
Postcondition : Si la fonction se termine, il n'existe pas de chemin de la source vers le puits dans le réseau . De plus, l'ensemble des arcs avec tiré de la variable globale forme une arborescence dans le réseau résiduel dans laquelle la racine est et le sommet n'est pas accessible.
- 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 un réseau et un sous-ensemble de sommets de . Nous appelons bordure, et notons , l'ensemble d'arcs allant de vers son complémentaire :
Nous étendons la notion de multiplicité à des ensembles d'arcs en posant :
Définition : Nous appelons entourage dans le réseau tout sous-ensemble de sommets contenant la source mais pas le puits .
- Soient un ensemble réalisable de chemins dans un réseau et un entourage dans . Établir la relation
Nous fixons pour les quatre prochaines questions un ensemble réalisable de chemins dans un réseau tel que, dans le réseau résiduel , il n'existe plus aucun chemin entre la source et le puits . Nous notons l'entourage dans composé des sommets accessibles dans depuis la source .
- Montrer que, pour tout arc tel que et , toutes les occurrences de l'arc sont utilisées par un chemin de l'ensemble .
- Montrer qu'aucune occurence d'un arc tel que et n'est utilisée par un chemin de l'ensemble .
- Démontrer l'égalité
Définition : Nous disons qu'un entourage est de plus petite bordure s'il minimise la multiplicité . Nous notons la multiplicité de la bordure d'un tel entourage.
- Démontrer la relation
et en déduire que, si la variable globale contient un réseau, après exécution de la fonction nw_disconnect, l'ensemble est un entourage de plus petite bordure de , à savoir un entourage de multiplicité .

2 Algorithme de Goldberg

2.1 Densité d'un graphe

Pour tout ensemble fini , la notation désigne l'ensemble des paires (non ordonnées) à valeur dans , c'est-à-dire l'ensemble
Définition : Un graphe non orienté est un couple où est un ensemble fini, appelé ensemble de sommets, et est un ensemble de paires, appelé ensemble d'arêtes. Pour tout ensemble de sommets , nous notons le graphe , appelé graphe induit par sur .
Indication C : Par convention, nous numérotons les sommets de tout graphe non orienté par les entiers entre 1 et , où est le cardinal de . 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 et dont la première case n'est pas utilisée. Chaque arête est stockée sous forme de deux arcs.
- Écrire une fonction C graph *gr_create(unsigned int n) dont la valeur de retour est un graphe non orienté vide à sommets.
18 - Écrire une fonction C void gr_add (graph , int , int v) ayant pour effet d'insérer une arête dans le graphe non orienté .
Définition : Nous notons le degré d'un sommet dans le graphe non orienté :
19 - Écrire une fonction C int degree (graph *G, int v) dont la valeur de retour est le degré du sommet dans le graphe non orienté .
- Écrire une fonction int edges (graph *G) dont la valeur de retour est le nombre d'arêtes dans le graphe non orienté .
Définition : Nous appelons densité du graphe le rapport
où est le cardinal de et est le cardinal de .
21 - Écrire une fonction C double density (graph *G) dont la valeur de retour est la densité du graphe non orienté .
Définition : Le problème d'optimisation du sous-graphe le plus dense d'un graphe non orienté consiste à trouver un ensemble de sommets non vide tels que la densité du sous-graphe induit est maximale et calculer cette densité maximale

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é à sommets et un entier naturel , existe-t-il un sous-graphe induit de densité strictement supérieure au seuil ? Autrement dit, a-t-on ?
Définition : Étant donnés un graphe non orienté avec sommets et arêtes ainsi qu'un entier naturel , nous appelons réseau associé au graphe et au seuil le réseau où
(a) L'ensemble est la réunion , les sommets source et puits étant de nouveaux sommets n'appartenant pas à .
L'ensemble d'arcs comprend:
  • pour tout sommet , un arc , de multiplicité .
  • pour toute arête , un et un , de multiplicité .
  • pour tout sommet , un arc , de multiplicité .
22 - Écrire une fonction C void reduce (graph , int ) ayant pour effet d'initialiser la constante globale , de type network, par le réseau associé au graphe et au seuil .
23 - Soient un graphe non orienté et une partie non vide des sommets. Montrer que la densité du graphe induit satisfait la relation
૯
24 - Soient un graphe non orienté avec sommets et arêtes, une partie non vide des sommets, le réseau associé au graphe et à un seuil et l'entourage dans . Montrer que la multiplicité de la bordure de satisfait l'égalité
et que
25 - Soit le réseau associé au graphe et au seuil et soit la multiplicité de la bordure d'un entourage de plus petite bordure. Montrer les équivalences suivantes :
- Écrire une fonction C bool oracle (graph , int r) dont la valeur de retour est le booléen true si et false si . En justifier le principe. On pourra s'intéresser au contenu du tableau global après exécution de la fonction nw_disconnect.

2.3 Recherche dichotomique

Nous considérons l'ensemble de couples d'entiers
27 - Soient deux couples ( ) et ( ) appartenant à . Montrer que,
28 - Soient un graphe non orienté à sommets et une partie non vide de . Montrer que s'il n'existe aucun sous-graphe induit de densité supérieure ou égale à , alors le sous-graphe induit est un sous-graphe de densité maximale .
29 - Écrire une fonction C efficace void binary_search (graph *G) qui, pour tout graphe , modifie le tableau global de sorte que l'ensemble de sommets vérifie
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é tout graphe orienté tel qu'il existe une bijection avec pour tout . Le degré entrant d'un sommet dans un graphe orienté est
- Établir la majoration suivante entre la densité d'un graphe non orienté quelconque et le degré entrant maximum d'une orientation quelconque de G
Nous exécutons l'algorithme 1 sur un certain graphe non orienté . Dans les questions qui suivent, nous numérotons les sommets de selon la même numérotation que celle de l'algorithme. Nous notons la bijection qui oriente l'arête dans le sens ( ) et 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.
- Établir, pour tout compris entre 1 et , l'inégalité
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

- Détailler une structure de données qui permette d'exécuter l'algorithme 1 en temps où et . Il est suggéré de nantir la structure de données graph d'une table qui maintient, pour tout entier compris entre 0 et , la collection des sommets de degré 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

  1. 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.
Mines Informatique 1 MPI 2024 - Version Web LaTeX | WikiPrépa | WikiPrépa