Piles, processus, SQL

Suite audioactive de Conway¶

On s'intéresse dans cet exercice à une suite définie par le mathématicien John Conway de la manière suivante :

\(u_0 = 1 \qquad u_1 = 11 \qquad u_2 = 21 \qquad u_3 = 1211 \qquad \ldots \)

Cette suite a été appelée suite "audioactive" par John Conway, mais la postérité la retiendra sous le nom de la suite "Look and Say" (regarde et dis). En effet, chaque terme de la suite se construit en lisant le terme précédent, à partir du terme \(u_0 = 1\) :

\(u_0\) c'est "un un", donc \(u_1 = 11\)
\(u_1\) c'est "deux un", donc \(u_2 = 21\)
\(u_2\) c'est "un deux un un", donc \(u_3 = 1211\)
\(\ldots\)

On cherche dans cet exercice à écrire une fonction python conway qui calcule le \(n\)-ième terme de la suite de Conway. On représente le terme \(u_n\) par une file, constitué des chiffres qui composent \(u_n\), le chiffre le plus à gauche étant en début de file, le chiffre le plus à droite en fin de file. On utilisera pour cela le type File définit par l'interface objet suivante :

Notation objet	Description
`File() -> File`	Créer une file vide
`f.est_vide() -> bool`	Détermine si la file `f` est vide.
`f.enfiler(c:int) -> None`	Ajoute l'entier `c` à la fin de la file `f`
`f.defiler() -> int`	Renvoie en le supprimant l'entier au début de la file `f`, lorsque cela est possible.
`f.examiner() -> int`	Renvoie sans le supprimer l'entier au début de la file `f`, lorsque cela est possible.
`f.__str__() -> str`	Renvoie une chaine de caractère représentant la file `f`.

Ainsi, \(u_2\) est représenté par la file dont l'affichage est :

print(u2)

[début] 2 1 [fin]

Donner les nombres \(u_4\), \(u_5\).

\(u_4 = 111221\) et \(u_5 = 312211\)

Donner le code python permettant d'instancier une variable u3 de type File représentant \(u_3\).

u3 = File()
u3.enfiler(1)          
u3.enfiler(2)          
u3.enfiler(1)          
u3.enfiler(1)          

Écrire une fonction scanne_debut, qui étant donné une file f supposée non vide compte en les supprimant de la file le nombre de chiffres identiques en début de la file f, et renvoie le nombre de chiffres identiques en début de la file f ainsi que le chiffre concerné.

def scanne_debut(f1):
    """ File -> (int, int) """
    e = f1.examiner()
    c = 0
    while not f1.est_vide() and f1.examiner() == e:
        c += 1
        f1.defiler()
    return c, e

e1 = File()
e2 = File()
e3 = File()
for e in [1, 1, 1, 3]:
    e1.enfiler(e)
for e in [1, 2, 3]:
    e2.enfiler(e)
for e in [3, 3]:
    e3.enfiler(e)

À titre d'exemple, si e1, e2, et e3 sont trois variables de type File (ils ne correspondent pas nécessairement à un terme particulier de la suite \((u_n)\)), on a :

print(e1)
print(e2)
print(e3)

[début] 1 1 1 3 [fin]
[début] 1 2 3 [fin]
[début] 3 3 [fin]

print(scanne_debut(e1))       
print(scanne_debut(e2))       
print(scanne_debut(e3))       

(3, 1)
(1, 1)
(2, 3)

À l'issue de l'exécution des codes précédents, on a de plus :

print(e1)
print(e2)
print(e3)

[début] 3 [fin]
[début] 2 3 [fin]
[début] [fin]

3. Écrire une fonction suivant qui étant donné une file f représentant un terme \(u_n\) de la suite de Conway renvoie la file fn représentant le terme \(u_{n + 1}\).

def suivant(f):
    """ File -> File """
    fn = File()
    while not f.est_vide():
        n, c = scanne_debut(f)
        fn.enfiler(n)
        fn.enfiler(c)
    return fn

u3 = File()
for e in [1, 2, 1, 1]:
    u3.enfiler(e)

print(u3)
u4 = suivant(u3)
print(u4)
u5 = suivant(u4)
print(u5)

[début] 1 2 1 1 [fin]
[début] 1 1 1 2 2 1 [fin]
[début] 3 1 2 2 1 1 [fin]

Déduire des fonction précédentes une fonction conway qui étant donné un entier n renvoie la file qui représente le terme \(u_n\) de la suite de Conway.

def conway(n):
    """ int -> File """
    pass

def conway(n):
    """ int -> File """
    u = File()
    u.enfiler(1)
    for _ in range(n):
        u = suivant(u)
    return u

print(conway(4))       
print(conway(10))       

[début] 1 1 1 2 2 1 [fin]
[début] 1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1 [fin]

SQL¶

On considère une gestion simplifiée des voyages dans l’espace. La base de données utilisée est constituée de quatre relations nommées Astronaute, Fusee, Equipe et Vol. Voici le contenu des tables Astronaute, Fusee, Equipe et Vol.

Les clés primaires sont soulignées et les clefs étrangères sont précédées d’un # :

On pourra utiliser les mots clés suivants : COUNT, FROM, INSERT INTO, JOIN ON, ORDER BY, SELECT, VALUES, WHERE.

Le mot clé COUNT permet de récupérer le nombre d’enregistrements issu de la requête. Par exemple, la requête suivante renvoie la valeur 4.
1
SELECT COUNT(*) FROM Astronaute ;
Le mot clé ORDER BY permet de trier les éléments par ordre alphabétique. Par exemple, la requête suivante :
1
SELECT modele FROM Fusee ORDER BY modele;
renvoie la table

'Falcon 9'

'SLS'

'Soyouz'

'Starship'

1. Donner la définition d'une clé primaire.
  
  Une clé primaire est un (ou plusieurs) attributs d'une table permettant d'identifier de manière unique les enregistrements de la table.
2. Dans la table Astronaute, la clé primaire est id_astronaute. Expliquer pourquoi cette requête SQL renvoie une erreur :
  1 2
  INSERT INTO Astronaute VALUES (3, 'HAIGNERE', 'Claudie', 'français', 3);
  L'attribut id_astronaute est une clé primaire de la relation Astronaute, et il y a déjà un astronaute dont l'identifiant est 3 : cette ordre viole donc une des contraintes d'intégrité de la base de donnée (unicité de la clé primaire).
3. Écrire le schéma relationnel de la table Fusee en précisant le domaine de chaque attribut.
On s'intéresse ici à la récupération d'informations issues de la base de données.
1. Écrire le résultat que la requête suivante renvoie :
  1 2 3
  SELECT COUNT(*) FROM Fusee WHERE constructeur = 'SpaceX';
  La requête renvoie 2 (SpaceX a construit deux fusées : Falcon 9 et Starship).
2. Écrire une requête SQL qui renvoie le modèle et le constructeur des fusées ayant au moins quatre places.
  1 2
  SELECT modele, constructeur FROM Fusee WHERE nb_places >= 4;
3. Écrire une requête SQL qui renvoie les noms et prénoms des astronautes français dans l’ordre alphabétique du nom.
  1 2 3
  SELECT nom, prenom FROM Astronaute WHERE nationalite = 'français' ORDER BY nom ;
1. Recopier et compléter les requêtes SQL suivantes permettant d’ajouter un cinquième vol avec la fusée 'Soyouz' le 12/04/2023 avec l'équipage composé de PESQUET Thomas et MCARTHUR Megan. On ne s’intéresse pas ici à la mise à jour qui suivra.
  1 2 3
  INSERT INTO Vol VALUES (5, 3, '12/04/2023'); INSERT INTO Equipe VALUES (5, 1); INSERT INTO Equipe VALUES (5, 4);
2. Écrire une requête SQL permettant d'obtenir la date des vols effectués par des fusées 'Falcon 9'.
  1 2 3 4
  -- la jointure est obligatoire SELECT Date FROM Vol JOIN Fusee ON Fusee.id_fusse = Vol.id_fusee WHERE nom = 'Falcon 9'
3. Écrire une requête SQL permettant d’obtenir le nom et le prénom des astronautes ayant décollé le '25/10/2022'.
  1 2 3 4
  SELECT nom, prenom FROM Astronaute JOIN Equipe ON Equipe.id_astronaute = Astronaute.id_astronaute JOIN Vol on Vol.id_vol = Equipe.id_vol WHERE Date = '25/10/2022'

Planification de tâches¶

On cherche a créer une application de type "To-do list" pour aider les utilisateurices à planifier leur journée. Pour cela les utilisateurices saisissent les informations concernant chacune des tâches qu'iels doivent effectuer : iel indiquent un nom pour la tâche, ainsi que la durée qu'iels estiment nécessaire afin de la réaliser. On représente une tâche saisie par l'utilisateurice à l'aide d'un objet de type Tache, muni de quatre attributs :

le numero de la tâche, saisi par l'utilisateurice
le nom de la tâche, saisi par l'utilisateurice ;
la duree nécessaire à la réalisation de la tâche saisie par l'utilisateurice (en minutes) ;
la duree_restante avant la fin de la tâche (en minutes). Cet attribut sera initialisé avec la durée totale nécessaire à la réalisation de la tâche.

Écrire le code d'une classe Tache de telle sorte que Tache(0, "Manger", 15) permette de représenter la tâche numéro 0, de nom "Manger" et de durée 15 minutes.

On ne se souciera pas d'écrire les docstrings.

class Tache:
    def __init__(self, n, nom, duree):
        self.numero = n
        self.nom = nom
        self.duree_initiale = duree
        self.duree_restante = duree

    def __repr__(self):
        return f'<t{self.numero}>'

Instancier deux variables t1 et t2 représentant les tâches :

Tâche numéro 1: Appeler maman. Durée estimée : 45 minutes.

Tâche numéro 2: Ranger sa chambre. Durée estimée : 60 minutes.

t1 = Tache(1, "Appeler maman.", 45)            
t2 = Tache(2, "Ranger sa chambre.", 60)            

t3 = Tache(3, "Réviser la NSI", 90)            
t4 = Tache(4, "S'entraîner aux échecs", 30)
t5 = Tache(5, "Apprendre son vocabulaire de chinois", 30)
t6 = Tache(6, "Lire Fondation", 60)
t7 = Tache(7, "Écrire la lettre au Père Noël", 20)

On supposera dans la suite que les variables t1, t2, \(\ldots\), t7 représentent les tâches suivantes :

Numéro	Nom	Durée
1	Appeler maman	45
2	Ranger sa chambre	60
3	Réviser la NSI	90
4	S'entraîner aux échecs	30
5	Apprendre son vocabulaire de chinois	30
6	Lire Fondation	60
7	Écrire sa lettre au Père Noël	20

On supposera également écrite une méthode __repr__ qui renvoie la chaîne de caractères <t1> lorsqu'elle est appliquée à la tâche numéro 1, <t2> lorsqu'elle est appliquée à la tâche numéro 2, etc.

Écrire le code de la méthode avancer de la classe Tache qui permet d'avancer la tâche self de duree minutes.
1 2
def avancer(self, duree): self.duree_restante -= duree
Écrire le code de la méthode est_terminee de la classe Tache qui renvoie True si et seulement si la tâche est terminée.
1 2
def est_terminee(self): return self.duree_restante <= 0

Afin d'aider l'utilisateurice à planifier sa journée, on lui propose d'associer à chacune des tâches une priorité. Les priorités sont représentées par un entier de la manière suivante : 1 est la priorité maximale, et plus le nombre est grand moins la tâche associée est prioritaire. On utilise pour cela une file, dans laquelle les éléments sont des tuples (tache, priorite). Les éléments sont rangés dans la file doivent respecter les deux conditions suivantes :

Condition 1 :: les éléments sont rangés par ordre croissant de priorité (l'élément de priorité maximale se trouve au début de la file, l'élément le moins prioritaire se trouve à la fin de la file)
Condition 2 :: parmi les éléments de même priorité, les éléments sont rangés dans l'ordre dans lequel ils ont été insérés dans la file (le premier élément de priorité \(p\) inséré se trouve devant les éléments de même priorité \(p\) insérés plus tard).

Par exemple, si la file de tâches f est la file :

f = File()       
f.enfiler((t3, 1))
f.enfiler((t1, 2))
f.enfiler((t2, 2))
f.enfiler((t4, 4))
f.enfiler((t5, 4))
print(f)

[début] (<t3>, 1) (<t1>, 2) (<t2>, 2) (<t4>, 4) (<t5>, 4) [fin]

Cela signifie que :

la tâche de priorité maximale est la tâche numéro 3 ;
les deux tâches à exécuter en priorité après la tâche numéro 3 sont les tâches numéro 1 et numéro 2. La tâche numéro 1 a été ajoutée à la file des tâches à traiter avant la tâche numéro 2.
il n'y a pas de tâche de priorité 3 ;
les tâches les moins prioritaires de la file sont les tâches 4 et 5. La tâche numéro 4 a été ajoutée avant la tâche numéro 5.

Représenter l'état de la file f lorsque l'on lui ajoute successivement la tâche numéro 6 avec la priorité 3, puis la tâche numéro 7 avec la priorité 1.

ajouter_file_prio(f, t6, 3)
ajouter_file_prio(f, t7, 1)
print(f)

[début] (<t3>, 1) (<t7>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]

On suppose déjà définies les fonctions suivantes :

creer_vide() -> File : créé et renvoie un objet de type File, vide.
enfiler(f: File, e: (Tache, int)) -> Nonetype : ajoute l'élément e à la fin de la file f.
defiler(f : File) -> (Tache, int) : renvoie en le supprimant de la file le premier élément de la file si cela est possible.
examiner(f: File) -> (Tache, int) : renvoie sans le supprimer de la file le premier élément de la file si cela est possible.
est_vide(f: File) -> bool : détermine si la file de priorié est vide ou non.

La file f est celle de la question 2, dans l'état indiqué dans la question 2a (après les ajouts).

Que renvoie defiler(f)[0] ? Représenter le contenu de la file f après l'exécution de cette instruction.
1 2
print(defiler(f)[0]) print(f)
```
<t3>
[début] (<t7>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
```

Que renvoie examiner(f)[1] ? Représenter le contenu de la file f après l'exécution de cette instruction.

print(examiner(f)[1])
print(f)

1
[début] (<t7>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]

Compléter le code de la fonction ajouter_file_prio qui étant donné une file f dont les éléments sont des tuples (tache, priorite) respectant les deux conditions de l'énoncé, une tache t et une priorité p, ajoute à la bonne position dans la file f le tuple (t, p).

On utilise une file auxiliaire f_aux que l'on remplit en défilant les éléments en début de file f tant que la priorité du premier élément de la file est inférieure ou égale à p. Puis on enfile l'élément (t, p) dans la file auxiliaire, et on reconstruit la file f de la manière adéquate en utilisant f_aux.

def ajouter_file_prio(f, t, p):
    """ File, Tache, int -> Nonetype"""
    f_aux = File()
    while not est_vide(f) and examiner(f)[1] <= p:
        enfiler(f_aux, defiler(f))
    enfiler(f_aux, (t, p))
    while not est_vide(f):
            enfiler(f_aux, defiler(f))
    while not est_vide(f_aux):
            enfiler(f, defiler(f_aux))

f = creer_vide()
for (t, p) in [(t1, 2), (t2, 2), (t3, 1), (t4, 4), (t5, 4), (t6, 3), (t7, 1)]:
    ajouter_file_prio(f, t, p)
print(f)

[début] (<t3>, 1) (<t7>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]

Une fois que l'utilisateurice a entré les tâches qu'iel doit effectuer, leur durée estimée, ainsi que la priorité à laquelle iel doit les effectuer, l'application lui propose un planning en utilisant la technique dite Pomodoro :

la tâche à effectuer est la tâche qui se trouve en tête de file ;
on défile cette tâche de la file des tâches à effectuer ;
on avance cette tâche de 25 minutes ;
si cette tâche n'est pas terminée, on (r)ajoute cette tâche dans la file des tâches à effectuer, avec la même priorité qu'initialement (en utilisant l'algorithme de la fonction ajouter_file_prio) ;
si cette tâche se termine au cours des 25 minutes, alors l'utilisateurice attend la fin des 25 minutes en se reposant ;
on continue ces étapes tant que la file des tâches à effectuer n'est pas vide.

On rappelle que les tâches à effectuer sont les suivantes (classées par ordre de priorité) :

Numéro	Nom	Durée	Priorité
3	Réviser la NSI	90	1
7	Écrire sa lettre au Père Noël	20	1
1	Appeler maman	45	2
2	Ranger sa chambre	60	2
6	Lire Fondation	60	3
4	S'entraîner aux échecs	30	4
5	Apprendre son vocabulaire de chinois	30	4

Compléter le tableau donné en annexe afin d'indiquer dans quel ordre les tâches seront réalisées, en suivant le modèle proposé. On indiquera pour chaque bloc de 25 minutes quelle est la tâche en cours d'exécution, ainsi que l'état de la file au début du bloc de 25 minutes (avant défilement). Ainsi, la tâche en cours d'exécution sera toujours la tâche au début de la file correspondante (dont le début se trouve tout en haut).

On fera particulièrement attention au cas où la tâche n'est pas terminée : celle-ci est rajoutée à la file des tâches à effectuer (dont elle avait été supprimée) avec la même priorité qu'initialement, en respectant les conditions 1 ET 2 de l'énoncé.

def planning(f):
    while not est_vide(f):
        print("État de la file", f)
        tache, prio = defiler(f)
        print("Tâche selectionnée", tache)
        tache.avancer(25)
        if not tache.est_terminee():
            ajouter_file_prio(f, tache, prio)
        print()

planning(f)

État de la file [début] (<t3>, 1) (<t7>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t3>

État de la file [début] (<t7>, 1) (<t3>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t7>

État de la file [début] (<t3>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t3>

État de la file [début] (<t3>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t3>

État de la file [début] (<t3>, 1) (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t3>

État de la file [début] (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t1>

État de la file [début] (<t2>, 2) (<t1>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t2>

État de la file [début] (<t1>, 2) (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t1>

État de la file [début] (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t2>

État de la file [début] (<t2>, 2) (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t2>

État de la file [début] (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t6>

État de la file [début] (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t6>

État de la file [début] (<t6>, 3) (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t6>

État de la file [début] (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t4>

État de la file [début] (<t5>, 4) (<t4>, 4) [fin]
Tâche selectionnée <t5>

État de la file [début] (<t4>, 4) (<t5>, 4) [fin]
Tâche selectionnée <t4>

État de la file [début] (<t5>, 4) [fin]
Tâche selectionnée <t5>

Combien de temps l'utilisateurice a-t-il passé à se reposer lors de la réalisation de son planning ?

def planning_temps_inactif(f):
    temps_repos = 0
    while not est_vide(f):
        tache, prio = defiler(f)
        tache.avancer(25)
        if tache.est_terminee():
            print(f"Tâche {tache} terminée. Repos avant la prochaine tâche : {-tache.duree_restante}")
            temps_repos += -tache.duree_restante
        else:
            ajouter_file_prio(f, tache, prio)
    return temps_repos

# les tâches et la file ont été modifiées par la
# l'exécution de la fonction  planning (question précédente)
# on réinitialise ces variables
f = creer_vide()
t1 = Tache(1, "Appeler maman.", 45)            
t2 = Tache(2, "Ranger sa chambre.", 60)            
t3 = Tache(3, "Réviser la NSI", 90)            
t4 = Tache(4, "S'entraîner aux échecs", 30)
t5 = Tache(5, "Apprendre son vocabulaire de chinois", 30)
t6 = Tache(6, "Lire Fondation", 60)
t7 = Tache(7, "Écrire la lettre au Père Noël", 20)
for (t, p) in [(t1, 2), (t2, 2), (t3, 1), (t4, 4), (t5, 4), (t6, 3), (t7, 1)]:
    ajouter_file_prio(f, t, p)
print(planning_temps_inactif(f))

Tâche <t7> terminée. Repos avant la prochaine tâche : 5
Tâche <t3> terminée. Repos avant la prochaine tâche : 10
Tâche <t1> terminée. Repos avant la prochaine tâche : 5
Tâche <t2> terminée. Repos avant la prochaine tâche : 15
Tâche <t6> terminée. Repos avant la prochaine tâche : 15
Tâche <t4> terminée. Repos avant la prochaine tâche : 20
Tâche <t5> terminée. Repos avant la prochaine tâche : 20
90

Remarque. La technique Pomodoro est une technique de gestion du temps développée par Francesco Cirillo à la fin des années 1980. Cette méthode se base sur l'usage d'un minuteur permettant de respecter des périodes de 25 minutes appelées pomodori.

Le nom vient d'un minuteur de cuisine en forme de tomate (en italien pomodoro, pluriel pomodori) qu'utilisa au début Francesco Cirillo, lorsqu'il était étudiant à l'université.

'Falcon 9'
'SLS'
'Soyouz'
'Starship'