Aller au contenu

DS 2 — Correction : modélisation de la circulation

MP, année scolaire 2021-2022 — corrigé (informatique commune, Python et SQL).

Sujet

Seule la correction est disponible : l'énoncé n'est pas reproduit ici. Sujet d'après le concours Mines-Ponts 2016, informatique commune (modélisation de la circulation automobile : files de voitures, croisements, espace des configurations, base de données de croisements et de voies).

Partie I

Question 1.

Corrigé

On peut faire une liste [v0,...,vn-1] où vi vaut True quand une voiture est présente à l'indice \(i\) et False sinon.

Question 2.

Corrigé 
A = [ True, False, True, True, False,
    False, False, False, False, False, True ]

Question 3.

Corrigé 
def occupe(L, i):
    return L[i]

Question 4.

Corrigé

Chacune des \(n\) cases peut prendre deux valeurs, il y en a donc \(2^n\).

Question 5.

Corrigé

Question mal posée, on peut répondre légitimement avec ==…

def egal(L1, L2):
    if len(L1) != len(L2):
        return False
    for i in range(len(L1)):
        if L1[i] != L2[i]:
            return False
    return True

Question 6.

Corrigé

Complexité linéaire en temps en pire cas, ce qui correspond au fait d'avoir des listes égales.

Question 7.

Corrigé

Le type de retour est un booléen donc de type bool. Note : cette question est étrange…

Partie II

Question 8.

Corrigé

On a vu que avancer(A,False) renvoie

[False,True,False,True, True, False, False, False, False, False, False]

si on appelle sur ce résultat avancer avec True on obtient :

[True, False,True,False,True, True, False, False, False, False, False]

Question 9.

Corrigé

On a plusieurs choix ici, si on considère que la fonction avancer est définie, on peut l'utiliser directement. Sinon, on peut le faire à la main.

def avancer_fin(L, m):
    La = [ False ] * len(L)
    for i in range(m):
        La[i] = L[i]
    for i in range(m+1, len(L)):
        La[i] = L[i-1]
    return La

Question 10.

Corrigé 
def avancer_debut(L, b, m):
    La = [ False ] * len(L)
    for i in range(m+1, len(L)):
        La[i] = L[i]
    for i in range(1, m+1):
        La[i] = L[i-1]
    La[0] = b
    return La

Question 11.

Corrigé

Ici, il faut procéder en reculant à partir de la position m.

def avancer_debut_bloque(L, b, m):
    # on cherche la première case libre à gauche de m (strictement)
    i = m-1
    while i > 0 and L[i]:
        i = i-1
    return avancer_debut(L, b, i)

Partie III

Question 12.

Corrigé 
def avancer_files(L1, b1, L2, b2):
    p = len(L1)//2
    La1 = avancer_file(L1, b1)
    if La1[p]:
        La2 = avancer_fin(avancer_debut_bloque(L2, b2, p), p)
    else:
        La2 = avancer_file(L2, b2)
    return [La1, La2]

Question 13.

Corrigé

L'appel renvoie

[ [ False, False, True, False, True ], [ False, True, False, True, False ] ]

Partie IV

Question 14.

Corrigé

Il suffit que toutes les cases de L1 soient occupées.

Question 15.

Corrigé

On va y passer en deux temps, d'abord toutes les voitures de L1 passent à droite, ensuite les voitures de L2 peuvent descendre et au passage on rajoute des voitures à gauche de L1.

On a donc 5 étapes pour libérer le croisement puis comme sur la dernière étape on a commencé à faire descendre les voitures de L2 on a juste besoin de 4 étapes ensuite, donc 9 étapes en tout.

Question 16.

Corrigé

La configuration 4c n'a pas d'antécédent car il faudrait avoir une voiture de L1 et une voiture de L2 sur la position centrale.

Partie V

Question 17.

Corrigé 
def elim_double(L):
    Le = []
    for x in L:
        if Le == [] or x != Le[-1]:
            Le.append(x)
    return Le

Question 18.

Corrigé 
[ 1, 2, 3, 5 ]

Question 19.

Corrigé

Non car elle se contente de supprimer les doublons côte à côte.

Question 20.

Corrigé
  • recherche renvoie un bool ;
  • successeur renvoie une list de couples de configurations [L1,L2] ;
  • espace a le même type que le retour de successeur ;
  • but est une configuration, donc une liste [L1,L2] où les Li sont des list de bool de même longueur impaire.

Question 21.

Corrigé

La première recherche correspond à une recherche linéaire et la seconde à une recherche dichotomique, donc en temps logarithmique. La seconde est préférable.

Cependant, remarquons que dans la mesure où on effectue un tri à chaque étape en \(O(n \log_2 n)\), la question est peu pertinente…

Question 22.

Corrigé 
def versEntier(L):
    p = 1
    s = 0
    for b in reversed(L):
        if b:
            s = s + p
        p = p * 2
    return s

Question 23.

Corrigé

Il faut une taille correspondant au nombre de chiffres de \(n\) en binaire, soit \(\lfloor \log_2 n \rfloor + 1\).

La condition est \(n > 0\).

Question 24.

Corrigé

La fonction termine car elle continue tant qu'elle rajoute des configurations et que le nombre de configurations est borné par \(2^{2n-1}\).

Question 25.

Corrigé

On rajoute à chaque fois l'ensemble des successeurs aux précédents. Donc le test de présence du but ne va en fait porter que sur ces nouveaux successeurs. Il suffit de compter le nombre d'itérations dans la boucle while.

def recherche(but, init):
    espace = [ init ]
    stop = egal(but, init)
    if stop:
        return 0
    nb_etapes = 0
    while not stop:
        ancien = espace
        espace = espace + successeur(espace)
        espace.sort()
        espace = elim_double(espace)
        stop = egal(ancien, espace)
        nb_etapes += 1
        if but in espace:
            return nb_etapes
    return -1

Partie VI

Question 26.

Corrigé 
SELECT id_croisement_fin FROM voie
WHERE id_croisement_debut = c;

Question 27.

Corrigé 
SELECT longitude, latitude
FROM croisement JOIN voie ON croisement.id = id_croisement_fin
WHERE id_croisement_debut = c;

Question 28.

Corrigé

Cette requête renvoie les croisements accessibles en suivant deux voies à partir du croisement \(c\).