Étude de trafic routier

Quelques remaques

• L'égalité se teste avec == pas =.
• Une liste Python ni ne renvoie, ni ne retourne des éléments (c'est les fonctions qui retournent...). Une liste contient des éléments.
• Si on veut tester un seul élément d'une liste, il ne faut pas utiliser de boucle (question 3).
• Les complexités temporelles affirmées doivent être justifiées. Effectuer n itération sur un boucle ne suffit pas à avoir un complexité en \(\mathcal{O}(n)\), il faut en plus que chaque itération se fasse en \(\mathcal{O}(1)\) (c'est à dire un nombre fixe d'instructions élémentaires).
• Éviter les pop() au sein d'une boucle for sur les indices de l'itérable. En le pop va décaler les éléments suivants et il est possible d'avoir des erreurs out of range. Si besoin, on peut s'en sortir en itérant avec des indices décroissants (range(len(l) - 1, - 1, 0)).
• Les tranches (slice) de listes (ex. l[a:b], l[:b], l[a:], l[b:a:-1], l[:], l[::-1]) sont à connaitre. Elles peuvent être très utiles dans ce sujet pour copier une tranche de liste.

Partie I. Préliminaires

Q1 – Expliquer comment représenter une file de voitures à l’aide d’une liste de booléens.

Une liste Python permet de rerpésenter une file de voiture, modélisées par des cases.

Une liste de booléens indique si une voiture est présente ou non dans chaque case.

Q2 – Donner une ou plusieurs instructions Python permettant de définir une liste A représentant la file de voitures illustrée par la Figure 1(a).

A = [True,False] + [True] * 2 + [False] * 6 + [True]

Q3 – Soit L une liste représentant une file de longueur n et i un entier tel que \(0 \le i \le n\). Définir en Python la fonction occupe(L, i) qui renvoie True lorsque la case d’indice i de la file est occupée par une voiture et False sinon.

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

Q4 – Combien existe-t-il de files différentes de longueur n ? Justifier votre réponse.

Chaque case est occupée de façon indépendante des autres, il y a deux choix par case et donc \(2^n\) files différentes de longueur \(n\).

Q5 – Écrire une fonction egal(L1, L2) retournant un booléen permettant de savoir si deux listes L1 et L2 sont égales.

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

Ou en utilisant l'égalité sur les listes

def egal(L1, L2):
    return L1 == L2

Q6 – Que peut-on dire de la complexité de cette fonction ?

Avec le premier code, on constate la compléxité linéaire de l'algorihtme. En effet, le nombre d'itérations de la boucle est égal à la longueur des listes et pour chaque itératione une compraraison en \(\mathcal{O}(1)\) est effectuée.

remarque non attendue dans les copies de concours si la comparaison n'est pas d'une complexité de \(\mathcal{O}(1)\), comme c'est le cas quand L1 et L2 sont des structures imbriquées par exemple liste de listes, la complexité globale est alors égale à \(n\cdot\mathcal{O}(c(n))\) où \(c(n)\) est une fonction qui indique la complexité des comparaisons en fonction de la taille \(n\) des entrées.

Q7 – Préciser le type de retour de cette fonction.

Elle retourne un booléen.

Partie II. Déplacement de voitures dans la file

Q8 – Étant donnée A la liste définie à la question 2, que renvoie `avancer(avancer(A, False),True)̀

avancer(A, False) retourne [False, True, False, True, True, False, False, False, False, False, False]. Et cette liste est utilisée en premier argument de avancer avec Trueen deuxième argument.

avancer(avancer(A, False),True) retourne donc [True, False, True, False, True, True, False, False, False, False, False].

Q9 – On considère L une liste et m l’indice d’une case de cette liste (\(0 \le m < len(L)\)). On s'intéresse à une étape partielle où seules les voitures situées sur la case d’indice m 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(L, m) qui réalise cette étape partielle de déplacement et renvoie le résultat dans une nouvelle liste sans modifier L.

def avancer_fin(L, m):
    return L[:m] + [False] + L[m:-1] # le [False] occupera la case d'indice m libérée par les voitures de droite ayant avancé

Q10 – Soient L une liste, b un booléen et m 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 m se déplacent, les autres voitures ne se déplacent pas. Le booléen b indique si une nouvelle voiture est introduite sur la case la plus à gauche.

Définir en Python la fonction avancer_debut(L, b, m) qui réalise cette étape partielle de déplacement et renvoie le résultat dans une nouvelle liste sans modifier L.

def avancer_debut(L, b, m):
    return [b] + L[:m] + L[m + 1:] # La case m de L est donc supprimée, elle était vide

Q11 – On considère une liste L dont la case d’indice \(m > 0\) est temporairement inaccessible et bloque l’avancée des voitures. Une voiture située immédiatement à gauche de la case d’indice m 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 b indique si une nouvelle voiture est introduite lorsque cela est possible.

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

def avancer_debut_bloque(L, b, m):
    copie = L.copy() # nouvelle liste
    for i in range(m - 1,0,-1):
        if not copie[i]: # la case est vide
            copie[i] = copie[i - 1] # si une voiture sur la case immédiatement à gauche, elle avance
            copie[i - 1] = False # en libérant la case d'avant
    copie[0] = b # possible introduction d'une nouvelle voiture
    return copie

Partie III. Une étape de simulation à deux files

Q12 – En utilisant le langage Python, définir la fonction avancer_files(L1, b1, L2, b2) qui renvoie le résultat d’une étape de simulation sous la forme d’une liste de deux éléments notée [R1, R2] sans changer les listes L1 et L2. Les booléens b1 et b2 indiquent respectivement si une nouvelle voiture est introduite dans les files L1 et L2. Les listes R1 et R2 correspondent aux listes après déplacement.

def avancer_files(L1, b1, L2, b2):
    m = len(L1) // 2
    L1C = avancer_fin(L1, m)
    L2C = avancer_fin(L2, m)
    # le début de L1 avance, le croisement est libre
    L1C = avancer_debut(L1C, b1, m)

    # le début de l2 avance en second pour respecter la priorité
    if L1C[m]: # une voiture de L1 bloque l'intersection
        L2C = avancer_debut_bloque(L2C, b2, m)
    else:
        L2C = avancer_debut(L2C, b2, m)
    return  [L1C, L2C]

Q13 – On considère les listes D = [ False, True, False, True, False], E = [False, True, True, False, False]

Que renvoie l’appel avancer_files(D, False, E, False) ?

La valeur retournée est : [[False, False, True, False, True], [False, True, False, True, False]]

Partie IV. Transitions

Q14 – En considérant que de nouvelles voitures peuvent être introduites sur les premières cases des files lors d’une étape de simulation, décrire une situation où une voiture de la file L2 serait indéfiniment bloquée.

La file L1 étant prioritaire, il est possible de créer une file L discontinue si à chaque itération, une voiture est ajoutée sur la première case de L1.

Cette file discontinue de L1 empeche les voitures de L2 de passer le croisement.

Q15 – Étant données les configurations illustrées par la Figure 4, combien d’étapes sont nécessaires (on demande le nombre minimum) pour passer de la configuration 4(a) à la configuration 4(b) ? Justifier votre réponse.

Il faut 4 étapes pour que les pour que la dernière voiture de L1 arrive sur le croisement (si aucune voiture est ajoutée).

Il faut une étape supplémentaire pour libérer le croisement. Lors de cette étape, les voitures de L2 peuvent avancer d'une case.

Il faut ensuite 4 étapes supplémentaires pour que les voitures de L2 avancent dans la configuration 4(b).

Durant les 4 dernières étapes, il est possible d'ajouter une voiture à la file L1 pour arriver dans la configuration 4(b).

Il faut donc au minumum 10 étapes pour passer de la configuration 4(a) à la configuration 4(b).

Q16 – Peut-on passer de la configuration 4(a) à la configuration 4(c) ? Justifier votre réponse.

Si la configuration 4(c) était possible, à l'étape précédente une voiture de L1 occuperait le croisement. Cette dernière voiture empeche la présence d'une voiture de L2 sur le croisement, il est donc impossible qu'une voiture de L2 soit sur la case qui suit le croisement.

La configuration 4(c) est donc impossible.

Q17 – Écrire en langage Python une fonction elim_double(L) non récursive, de complexité linéaire en la taille de ̀ L, qui élimine les éléments apparaissant plusieurs fois dans une liste triée ̀ L et renvoie la liste triée obtenue. Par exemple elim_double([1, 1, 3, 3, 3, 7]) doit renvoyer la liste ̀ [1, 3, 7]`.

def elim_double(L):
    sans_double = [L[0]]
    for i in range(1, len(L)):
        if L[i] != sans_double[-1]:
            sans_double.append(L[i])
    return sans_double

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

Q18 – Que retourne l’appel suivant ? doublons([1, 1, 2, 2, 3, 3, 3, 5])

doublons est une fonction récursive qui donne le même résultat que elim_double. l'appel retourne [1, 2, 3, 5]

Q19 – Cette fonction est-elle utilisable pour éliminer les éléments apparaissant plusieurs fois dans une liste non triée ? Justifier.

Cette fonction ne compare que deux cases consécutives elle est donc inutilisable pour une liste non triée où deux éléments identiques peuvent ne pas être contigus.

Q20 – La fonction recherche donnée en annexe permet d’établir si la configuration correspondant à but est atteignable en partant de l’état init. Préciser le type de retour de la fonction recherche, le type des variables but et espace, ainsi que le type de retour de la fonction successeurs.

La fonction recherche retourne un booléen.

but correspond à la modélisation d'une configuration, c'est une liste de deux listes de booléens.

espace est une liste de configurations, c'est une liste de listes de deux listes de booléens : [[[bool],[bool]]]

successeurs retourne une liste de configurations (une liste de listes de deux listes de booléens) c'est cohérent avec l'utilisation du + à la ligne 6 de recherche.

Q21 - Afin d’améliorer l’efficacité du test if but in espace, ligne 10 de l’annexe, on propose de le remplacer par if in1̀(but, espace) ou bien par if in2(but, espace), avec in1 et ̀ in2` deux fonctions définies ci-dessous. On considère que le paramètre liste est une liste triée par ordre croissant.

Quel est le meilleur choix ? Justifier.

in1 effectue une recherche itérative qui est linéaire dans le pire des cas.

in2 effectue une recherche dichotomique qui est en \(\mathcal{O}(log(n))\).

in2 est donc plus efficace.

Q22 – Afin de comparer plus efficacement les files représentées par des listes de booléens on remarque que ces listes représentent un codage binaire où ̀ Truecorrespond à 1 etFalseà 0. Écrire la fonction ̀ versEntier(L)̀ prenant une liste de booléens en paramètre et renvoyant l’entier correspondant. Par exemple, l’appelversEntier([True, False, False])renverra4`.

def versEntier(L):
    entier = 0
    for chiffre in L:
        entier = entier * 2 + int(chiffre)
    return entier

Q23 – On veut écrire la fonction inverse de versEntier, transformant un entier en une liste de booléens. Que doit être au minimum la valeur de taille pour que le codage obtenu soit satisfaisant ? On suppose que la valeur de taille est suffisante. Quelle condition booléenne faut-il écrire en ligne 4 du code ci-dessous ?

Une liste de booléens de taille taille code au maximum le nombre entier \(2^{taille} -1\). Donc taille doit être supérieur à \(log_2(entier + 1)\).

la boucle while sert à affecter les valeurs de la liste, c'est donc

while i >= 0.

Q24 – Montrer qu’un appel à la fonction recherche de l’annexe se termine toujours.

D'après la question Q4, le nombre de configuration d'une liste de taille \(n\) est \(2^n\).

Pour deux listes, \(2 * 2^n\) est donc un majorant d'une nombre de configurations (en effet, la case de l'intersection ne permet pas les cas où elle est occupée simultanément par une voiture de ̀ L1̀ et une voiture de `L2̀ ).

Le nombre de configuration est donc fini.

recherche s'arrête quand il n'y a plus de configuration à découvrable. Cela sera au plus tard le cas quand on les a toutes découvertes.

Si la fonction recherche ne retourne pas de successeurs, recherche s'arrête.

Si la fonction recherche retourne au moins un successeur, le nombre de configuration diminue stritement et finira donc par valoir 0 si successeur en retourne à chaque itération.

recherche se termine donc toujours.

Q25 – Compléter la fonction recherche pour qu’elle indique le nombre minimum d’étapes à faire pour passer de init à but lorsque cela est possible. Justifier la réponse.

def recherche(but, init):
    espace = [init]
    stop = False
    nb_coup = 0
    while not stop:
        ancien = espace
        ajout =  successeurs(espace)
        nb_coup += 1
        if but in ajout:
            return nb_coup
        espace.sort() # permet de trier espace par ordre croissant
        espace = elim_double(espace)
        stop = egal(ancien,espace) # fonction définie à la question 5
    return -1 # pour inateignable 

Q26 – Écrire la requête SQL qui renvoie les identifiants des croisements atteignables en utilisant une seule voie à partir du croisement ayant l’identifiant c.

SELECT id_croisement_fin
FROM Voie
WHERE id_croisement_debut = c;

Q27 – Écrire la requête SQL qui renvoie les longitudes et latitudes des croisements atteignables en utilisant une seule voie, à partir du croisement c.

SELECT C.longitude, C.latitude
FROM Voie V
JOIN Croisement C ON C.id = V.id_croisement_fin
WHERE V.id_croisement_debut = c;

Q28 – Que renvoie la requête SQL suivante ?

Elle renvoie tous les ìd des croisements situés à distance 2 (en nombre d'arêtes) du croisement c, dans un graphe orienté du réseau routier.