ÉCOLE DES PONTS PARISTECH, ISAE-SUPAERO, ENSTA PARISTECH, TELECOM PARISTECH, MINES PARISTECH, MINES SAINT-ÉTIENNE, MINES NANCY, IMT Atlantique (ex Télécom Bretagne), ENSAE PARISTECH.

CONCOURS 2017

ÉPREUVE D'INFORMATIQUE COMMUNE

Durée de l'épreuve : 1 heure 30 minutes

INFORMATIQUE COMMUNE

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

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.

Étude de trafic routier

Notations

• on note len sa longueur;
• pour entier, , l'élément de la liste d'indice est noté ;
• pour et entiers, est la sous-liste composée des éléments , ..., ;
• , avec entier, est la liste obtenue en concaténant copies de . Par exemple, est la liste .

(a) Représentation d'une file de longueur onze comprenant quatre voitures, situées respectivement sur les cases d'indices et 10 .}

\end{figure}

Partie I. Préliminaires

Partie II. Déplacement de voitures dans la file

• une voiture se trouvant sur la case la plus à droite de la file sort de la file;
• une voiture peut avancer d'une case vers la droite si elle arrive sur une case inoccupée;
• une case libérée par une voiture devient inoccupée;
• la case la plus à gauche peut devenir occupée ou non, selon le cas considéré.

(a) Liste initiale

Figure 2 - Étape de simulation

Q8 - Étant donnée la liste définie à la question 2, que renvoie avancer(avancer( , False), True) ?
Q9 - On considère une liste et l'indice d'une case de cette liste ( ). On s'intéresse à une étape partielle où seules les voitures situées sur la case d'indice ou à droite de cette case peuvent avancer normalement, les autres voitures ne se déplaçant pas.

Définir en Python la fonction avancer_fin qui réalise cette étape partielle de déplacement et renvoie le résultat dans une nouvelle liste sans modifier .
Q10 - Soient une liste, un booléen et l'indice d'une case inoccupée de cette liste. On considère une étape partielle où seules les voitures situées à gauche de la case d'indice se déplacent, les autres voitures ne se déplacent pas. Le booléen indique si une nouvelle voiture est introduite sur la case la plus à gauche.
nouvelle voiture n'est introduite.
Définir en Python la fonction avancer_debut qui réalise cette étape partielle de déplacement et renvoie le résultat dans une nouvelle liste sans modifier .
Q11 - On considère une liste dont la case d'indice est temporairement inaccessible et bloque l'avancée des voitures. Une voiture située immédiatement à gauche de la case d'indice ne peut pas avancer. Les voitures situées sur les cases plus à gauche peuvent avancer, à moins d'être bloquées par une case occupée, les autres voitures ne se déplacent pas. Un booléen indique si une nouvelle voiture est introduite lorsque cela est possible.
Par exemple, la file | | | | | | | | | | devient | | | | | | | | | nouvelle voiture n'est introduite.

Définir en Python la fonction avancer_debut_bloque qui réalise cette étape partielle de déplacement et renvoie le résultat dans une nouvelle liste.

Figure 3 - Étapes de simulation à deux files

Partie III. Une étape de simulation à deux files

Partie IV. Transitions

Figure 4 - Étude de configurations

Partie V. Atteignabilité

def doublons(liste):
    if len(liste)>1:
        if liste[0] != liste[1]:
            return [liste[0]] + doublons(liste[1:])
        del liste[1]
        return doublons(liste)
    else:
        return liste

doublons([1, 1, 2, 2, 3, 3, 3, 5])

def in1(element,liste):
    a = 0
    b = len(liste)-1
    while a <= b and element >= liste[a]:
        if element == liste[a]:
            return True
        else:
            a = a + 1
    return False
def in2(element,liste):
    a = 0
    b = len(liste)-1
    while a < b:
        pivot = (a+b) // 2 # l'opérateur // est la division entière
        if liste[pivot] < element:
            a = pivot + 1
        else:
            b = pivot
    if element == liste[a]:
        return True
    else:
        return False

def versFile(n, taille):
    res = taille * [False]
    i = taille - 1
    while ...:
        if (n % 2) != 0: # % est le reste de la division entière
            res[i] = True
        n = n // 2 # // est la division entière
        i = i - 1
    return res

Partie VI. Base de données

• Croisement(id, longitude, latitude)
• Voie(id, longueur, id_croisement_debut, id_croisement_fin)

SELECT V2.id_croisement_fin
FROM Voie as V1
JOIN Voie as V2
ON V1.id_croisement_fin = V2.id_croisement_debut
WHERE V1.id_croisement_debut = c

Annexe

def recherche(but, init):
    espace = [init]
    stop = False
    while not stop:
        ancien = espace
        espace = espace + successeurs(espace)
        espace.sort() # permet de trier espace par ordre croissant
        espace = elim_double(espace)
        stop = egal(ancien,espace) # fonction définie à la question 5
        if but in espace:
            return True
    return False
def successeurs(L):
    res = []
    for x in L:
        L1 = x[0]
        L2 = x[1]
        res.append( avancer_files(L1, False, L2, False) )
        res.append( avancer_files(L1, False, L2, True) )
        res.append( avancer_files(L1, True, L2, False) )
        res.append( avancer_files(L1, True, L2, True) )
    return res
# dans une liste triée, elim_double enlève les éléments apparaissant plus d'une fois
# exemple : elim_double([1, 1, 2, 3, 3]) renvoie [1, 2, 3]
def elim_double(L):
    # code à compléter
# exemple d'utilisation
# debut et fin sont des listes composées de deux files de même longueur impaire,
# la première étant prioritaire par rapport à la seconde
debut = [5*[False], 5*[False]]
fin = [3*[False]+2*[True], 3*[False]+2*[True]]
print(recherche(fin,debut))

Fin de l'épreuve.