QCM qui était à préparer

Thème A : types de base

Parmi les noms suivants, lequel n’est pas celui d’une méthode d’encodage des caractères ?
Arial
This is the correct answer 🙂
Il s’agit d’une police de caractères, pas d’une méthode d’encodage.
UTF-16
C’est une méthode d’encodage de caractères que nous n’avons pas étudiée où chaque caractère est codé sur une suite de un ou deux mots de 16 bits.
ASCII
La méthode d’encodage de caractères sur laquelle sont basées les autres. Les nouvelles normes comme l’Unicode ou UTF-8 son rétro-compatibles avec l’ASCII.
Unicode
C’est la méthode d’encodage de caractères qui s’est imposée.
Quel est le plus grand entier positif (non signé) représentable en binaire sur 2 octets (c’est-à-dire 16 bits) ?
Le plus grand est
This is the correct answer 🙂
Le bit de poids fort vaut alors , le bit de poids faibles et avec des « 1 » partout, on a . Attention l’énoncé dit « non signé » donc pas de négatifs !
Le plus grand est
C’est le piège dans lequel je suis moi-même tombé : ce serait la bonne réponse pour des entiers signés donc avec des négatifs : de à
Le plus grand est
On sort des 16 bits
Le plus grand est
Quel est le nombre minimum de bits qui permet de représenter les 7 couleurs de l’arc-en-ciel ?
Il faut au moins 3 bits.
This is the correct answer 🙂
Oui avec trois bits, on peut coder :
000 -> 0
001 -> 1
010 -> 2
011 -> 3
100 -> 4
101 -> 5
110 -> 6
111 -> 7
Il faut au moins 2 bits.
Trop peu : avec deux bits, 4 possibilités de zéro à trois.
Il faut au moins 4 bits.
C’est trop !
Il faut au moins 5 bits.
C’est trop !
Quelle est l’écriture en hexadécimal (base 16) du nombre entier positif qui s’écrit 1110 1101 en base 2 ?
ED
This is the correct answer 🙂
1110 donne 14 donc E
1101 donne 13 donc D
DE
Il faudrait 1101 1110 dans cet ordre !
EDF
Il faudrait 1110 1101 1111
FEFD
Non… il faudrait 1111 1110 1111 1101…

Thème B : types construits

Quelle est la valeur de l’expression
[ 2*k + 1 for k in range(4) ]
[1, 3, 5, 7]
This is the correct answer 🙂
C’est une liste en compréhension avec k allant de 0 à 3, donc 2*k allant de 0 à 6 de deux en deux… et on ajoute 1 donc 1, 3, 5, 7
[0, 1, 2, 3]
Non, ce serait par exemple
[ k for k in range(4) ]
[3, 5, 7, 9]
Non, ce serait par exemple
[ 2 * k + 3 for k in range(4) ]
[1, 2, 3, 4]
Non, ce serait par exemple
[ k + 1 for k in range(4) ]
De quelle expression la liste suivante est-elle la valeur ?
[[0,0,0,0], [1,1,1,1], [2,2,2,2]]
[[i] * 4 for i in range(3)]
This is the correct answer 🙂
En effet [0] * 4 donne la liste [0, 0, 0, 0] par exemple… et on s’arrête à 2 puisque c’est range(3).
[[i] * 4 for i in range(4)]
Donnerait
[[0,0,0,0], [1,1,1,1], [2,2,2,2], [3,3,3,3]]
[[i] * 3 for i in range(4)]
Donnerait
[[0,0,0], [1,1,1], [2,2,2], [3,3,3]]
[[i] * 3 for i in range(3)]
Donnerait
[[0,0,0], [1,1,1], [2,2,2]]
On exécute le script suivant :
inventaire = {'pommes': 430, 'bananes': 312,
                    'oranges' : 274, 'poires' : 137}
stock = 0
for fruit in inventaire.keys():
    if fruit != 'bananes':
        stock = stock + inventaire[fruit]
Que contient la variable stock à la fin de cette exécution ?
Elle contient 841.
This is the correct answer 🙂
En effet inventaire est un dictionnaire que l’on parcourt avec ses clés et stock une variable initialisée à zéro. On lui ajoute la valeur correspondant à chaque clé « fruit » qui n’est pas ‘bananes’.
Elle contient 312.
Non, car c’est différent « != » de ‘bananes’.
Elle contient {430, 274, 137}.
Ce sont bien les nombres qu’on ajoute mais cette expression n’a pas de sens en python. On ajoute dans un entier ici.
Elle contient {‘pommes’, ‘oranges’, ‘poires’}.
Non, on ajoute les valeurs. Cette juxtaposition de « clés » n’a pas de sens en python.
On considère le code suivant :
t = [0, 3, 5, 7, 9]
t[9] = 3 + t[5]
Que vaut t à la fin de son exécution ?
L’exécution déclenche une erreur
This is the correct answer 🙂
On veut accéder à t[5] (ou après t[9]) et t contient cinq valeurs indexées de 0 à 4.
t vaut
[0, 3, 5, 7, 9]
t vaut
[0, 3, 5, 7, 9, 3]
t vaut
[0, 3, 5, 7, 9, 8]
On définit la variable suivante :
citation = "Les nombres gouvernent le monde".
Quelle est la valeur de l’expression citation[5:10] ?
citation[5:10] vaut « ombre »
This is the correct answer 🙂
Les lettres de 5 à 10 exclus, donc de la sixième à la dixième.
citation[5:10] vaut « ombres »
Non, citation[5:11] vaut « ombres ».
citation[5:10] vaut « nombre »
Non, citation[4:10] vaut « nombre ».
citation[5:10] vaut « nombres »
Non, citation[4:11] vaut « nombres ».

Thème C : traitement de données en tables

Qu’est-ce qu’un fichier CSV ?
Un format de données
This is the correct answer 🙂
« CSV : Comma Separated Values » : des données séparées par des virgules, par exemple.
une librairie Python permettant l’affichage des images
Non, PIL ou pillow est une libraireie de travail sur les images en python
un format d’image
N’importe quoi : JPG, PNG en sont par contre.
Un utilitaire de traitement d’image
Non, ça c’est Paint, Photofiltre, le GIMP…
Laquelle de ces affirmations est vraie ?
on peut ouvrir un fichier CSV à l’aide d’un tableur
This is the correct answer 🙂
Oui, les valeurs séparées par des virgules seront alors case par case, et ce pour chaque ligne en gros…
un fichier CSV permet de gérer l’apparence du code dans l’éditeur
N’importe quoi 😉
un fichier CSV permet de gérer l’apparence d’une page HTML
Un fichier CSS fait ça, pas un CSV
un fichier CSV contient un programme à compiler
Non, un fichier C peut-être…
On exécute le script suivant :
notes = {"Paul": 12, "Jean": 16, "Clara": 14, "Aïssa": 18}
t = list(notes.keys())
Quelle est la valeur de t à la fin de cette exécution ?
C’est
["Paul", '"Jean", "Clara", "'Aïssa']
This is the correct answer 🙂
Oui, on transfrome en liste avec list les clés du dictionnaire notes.
C’est
Paul
Non, il en manque et c’est dans une liste.
C’est
[12, 16, 14, 18]
Non, ça c’est si on convertit en liste les valeurs notes.values()
C’est
[ "Paul": 12, "Jean": 16, "Clara": 14, "Aïssa": 18 ]
Non ça c’est n’importe quoi.
On a défini deux tables de données :
data1 = [(‘Bruce’, ’Wayne’), (‘Chuck’, ‘Norris’), (‘Bruce’, ‘Lee’), (‘Clark’, ‘Kent’)]
data2 = [(‘Diana’, ’Prince’), (‘Chuck’, ‘Norris’), (‘Peter’, ‘Parker’)]
Quelle instruction permet de construire une table data regroupant l’ensemble des informations de data1 et data2 ?
C’est
data = data1 + data2
This is the correct answer 🙂
Cette question m’a aussi « embrouillé ».
On a bien l’ensemble des informations, même si, grosse vanne… on a deux fois (‘Chuck’, ‘Norris’)
C’est
data == data1 + data2
Non, ça c’est un booléen qui vaut False car on teste si c’est égal.
C’est
data = [element for element in data1 or data2]
Gros piège ! Celle-ci empêcherait-elle les doublons ? Presque… Mais elle plante : le « or » n’a pas de sens.
C’est
data = [data1] + [data2]
Non, puisque data1 et data2 sont déjà des listes.
Qu’est-ce que le format de fichier CSV ?
un format de fichier où les données sont séparées par un caractère tel qu’une virgule
un format de fichier pour décrire une base de données
Non, on en reparlera 😉
un format de fichier mis au point par Microsoft pour Excel
Non, c’est par exemple XLS
un format de fichier décrivant une page Web
Non, pour les pages web, on utilise de fichiers HTML ou CSS
On a extrait les deux premières lignes de différents fichiers.
Déterminer celui qui est un authentique fichier CSV :
Nom,Pays,Temps
Camille Muffat,France,241.45
This is the correct answer 🙂
Trois valeurs séparées par des virgules et la première ligne contient le nom des « champs ».
Nom Pays Temps
Camille Muffat France 241.45
Manquent les virgules ou les points-virgules !
{ « Nom »: « Camille Muffat », « Pays »: « France », « Temps »: 241.45}
Ici un dictionnaire avec des clés.
{ Nom: « Camille Muffat », Pays: « France », Temps: 241.45}
N’importe quoi

Thème F : langages et programmation

étant un entier strictement positif, la fonction suivante calcule sa factorielle, c’est-à-dire le produit
Comment faut-il écrire la ligne en pointillée ci-dessous pour ce faire ?
def factorielle(n):
    f = 1
    .........
        f = f * i
    return f
Il faut écrire dans les pointillés
for i in range(1, n+1):
This is the correct answer 🙂
On multiplie bien f par tous les entiers de 1 à n. ON peut même faire mieux avec
for i in range(2, n+1):
Il faut écrire dans les pointillés
for i in range(1, n):
On n’aura pas multiplié par , le range s’arrêterait juste avant
Il faut écrire dans les pointillés
for i in range(0, n):
Là on va multiplier par zéro et le résultat fera zéro.
Il faut écrire dans les pointillés
for i in range(n+1):
Là on va multiplier par zéro et le résultat fera zéro.
On exécute le script suivant :
a = 4
b = 4
c = 4
while a < 5:
    a = a - 1
    b = b + 1
    c = c * b
Que peut-on dire ?
ce programme ne termine pas
This is the correct answer 🙂
En effet la terminaison est assurée quand a dépasse ou atteint 5, mais a est initialisé à 4 et décroît. On « boucle » indéfiniment.
à la fin de l’exécution, la variable a vaut 5
Non 4, 3, 2, 1, 0, -1 … et pas de fin !
à la fin de l’exécution, la variable b vaut 34
à la fin de l’exécution, la variable c vaut 42
Non, même si on kiffe le 42 😉
On souhaite écrire une fonction qui renvoie le maximum d’une liste d’entiers :
def maximum(L):
    m = L[0]
    for i in range(1,len(L)):
        if .........:
            m = L[i]
    return m
Par quoi faut-il remplacer les pointillés pour que cette fonction produise bien le résultat attendu ?
Par L[i] > m
This is the correct answer 🙂
Si ce test est réalisé, on doit changer le maximum m.
Par L[i] > L[i-1]
Non, rien à voir avec l’indice avant.
Par L[i] > L[i+1]
Non, rien à voir avec l’indice après. En plus ça plante à la fin.
Par i > m
Non, ici i est l’indice et c’est la valeur L[i] qui nous intéresse.
Quel est le seul langage de programmation parmi les propositions suivantes ?
C++
This is the correct answer 🙂
Oui, même si on ne l’a pas étudié !
CSS
Langage de style de pages web.
HTML
Langage de contenu de pages web.
WEB
Pas un langage à ma connaissance.
La fonction suivante calcule la racine carrée du double d’un nombre flottant.
from math import sqrt

def racine_du_double(x):
    return sqrt(2*x)
Quelle est la précondition sur l’argument de cette fonction ?
C’est x >= 0.
This is the correct answer 🙂
Il faut un positif (ou nul) pour une racine carrée.
C’est x < 0
Non, le contraire.
C’est 2 * x > 0.
On peut aussi avoir x == 0 qui ne serait pas accepté.
C’est sqrt(x) >= 0
Non, la condition est sur x et pas sur la racine de x.
La fonction maxi ci-dessous a pour but de renvoyer la valeur maximale présente dans la liste qui lui est passée en argument.
def maxi(L):
    dernier_indice = len(L) - 1
    valeur_max = L[0]
    for i in range(1,dernier_indice):
        if L[i] > valeur_max:
            valeur_max = L[i]
    return valeur_max
Cette fonction a été mal programmée. On souhaite réaliser un test pour le démontrer.
Parmi les propositions suivantes, laquelle mettra la fonction maxi en défaut ?
C’est
maxi([1, 2, 3, 4])
This is the correct answer 🙂
En effet le maximum est au dernier indice et on ne teste pas cette valeur avec le range là-haut
C’est
maxi([4, 3, 2, 1])
On aura l’impression que c’est correct car le maximum n’est pas au dernier indice.
C’est
maxi([1, 3, 3, 2])
On aura l’impression que c’est correct car le maximum n’est pas au dernier indice.
C’est
maxi([1, 1, 1, 1])
On aura l’impression que c’est correct car le maximum n’est pas forcément au dernier indice, on le rencontre avant.

Thème G : algorithmique

Quelle est la valeur de c à la fin de l’exécution du code suivant :
L = [1,2,3,4,1,2,3,4,0,2]
c = 0
for k in L:
    if k == L[1]:
        c = c+1
3
This is the correct answer 🙂
C’est le nombre de fois où l’on rencontre 2 en parcourant la liste puisque L[1] vaut 2.
0
2
10
Que renvoie la fonction suivante quand on l’appelle avec un nombre entier et une liste d’entiers ?
def mystere(n,L):
    for x in L:
        if n == x:
            return True
    return False
une valeur booléenne indiquant si le nombre n est présent au moins une fois dans la liste L
une valeur booléenne indiquant si le nombre n est présent plusieurs fois dans la liste L
une valeur booléenne indiquant si le nombre n est le plus grand de la liste L
une valeur booléenne indiquant si le nombre n est le plus petit de la liste L
La fonction mystere suivante prend en argument un tableau d’entiers.
def mystere(t):
    for i in range(len(t) - 1):
        if t[i] + 1 != t[i+1]:
            return False
    return True
si le tableau passé en argument est une suite d’entiers consécutifs
si le tableau passé en argument est trié en ordre croissant
si le tableau passé en argument est trié en ordre décroissant
si le tableau passé en argument contient des entiers tous identiques
On exécute le script suivant :
liste=[48, 17, 25 , 9, 34, 12, -5, 89, 54, 12, 78, 8, 155, -85]

def recherche(liste):
    valeur_1 = valeur_2 = liste[0]
    for item in liste:
        if item < valeur_1:
            valeur_1 = item
        elif item > valeur_2:
            valeur_2 = item
        else:
            pass
    return (valeur_1, valeur_2)
Que va renvoyer l’appel
recherche(liste) ?
C’est (-85, 155).
This is the correct answer 🙂
C’est un couple composé du minimum et du maximum.
C’est (155, -85).
C’est [-85, 155].
C’est [155, -85].
Un algorithme de recherche dichotomique dans une liste triée de taille nécessite, dans le pire des cas, exactement comparaisons.
Combien cet algorithme va-t-il utiliser, dans le pire des cas, de comparaisons sur une liste de taille ?
comparaisons au pire des cas.
This is the correct answer 🙂
Ben oui, après un coup, on se retrouve avec une moitié de éléments et donc au pire encore comparaisons, donc au pire en tout.
comparaisons au pire des cas.
comparaisons au pire des cas.
comparaisons au pire des cas.
On considère la fonction suivante :
def f(x,L):
    i = 0
    j = len(L)-1
    while i<j:
        k = (i+j)//2
            if x <= L[k]:
                j = k
            else:
                i = k + 1
    return i
Cette fonction implémente :
la recherche dichotomique
This is the correct answer 🙂
Oui, à une petite différence de celui vu en cours :
ici i est la variable de gauche,
j celle de droite,
k le milieu,
si le nombre est à gauche, j devient k (contre k-1 dans notre cours),
si le nombre est à droite, i devient k + 1 (comme dans notre cours). Par ailleurs, ce code renvoit toujours un indice du tableau, donc on présuppose certainement que la valeur est dans le tableau !
le tri par insertion
le tri par sélection
la recherche du plus proche voisin

Dichotomie

Questions « flash »

Envoyées par votre boomer adoré rencontré le 10 mars, exemples de ce qu’il y aurait en fin d’année pour celles et ceux qui arrêteraient…

Correction des codes proposés pour aujourd’hui

Question sur le cours de lundi ?

Une synthèse des éléments essentiels est dans les deux dernières questions du quizz recopiées ci-dessous, avec commentaires audio extraits du salon de discussion discord.

On considère la fonction Python suivante, qui prend en argument une liste L et renvoie le maximum des éléments de la liste :
def rechercheMaximum(L):
    max = L[0]
    for i in range(len(L)):
        if L[i] > max:
            max = L[i]
    return max
On note la taille de la liste. Quelle est la complexité en nombre d’opérations de l’algorithme ?
linéaire, c’est-à-dire de l’ordre de
constante, c’est-à-dire ne dépend pas de
quadratique, c’est-à-dire de l’ordre de
cubique, c’est-à-dire de l’ordre de
Pour trier par sélection une liste de 2500 entiers, le nombre de comparaisons nécessaires à l’algorithme est
de l’ordre de
de l’ordre de
de l’ordre de
de l’ordre de

Dichotomie – le sujet du jour

  • Un petit jeu par oral sur discord « trouve le nombre »
  • Une animation : ici. (Celle qui a permis la vidéo ci-dessus, merci !)
  • Un document institutionnel.
  • Des prises de notes d’élèves (merci) :
    • Pour appliquer la dichotomie la liste doit être triée
    • À chaque puissance de 2 supplémentaire il y a un coup supplémentaire (ex 15 cartes : 4 coups au max, 16 cartes : 5 au max)
    • Le nombre de possibilités correspond (à un près) au nombre de bits nécessaires en binaire.
    • Cela s’appelle en gros le logarithme en base 2 : \log_2(n)
    • Exemple \log_2(4) c’est 2, mais avec 4 valeurs on a \log_2(4) + 1 soit 3 coups max
    • \log_2(n) en gros c’est le nombre de bits qu’il faut pour écrire n en binaire … moins un (correctif depuis le cours) si on l’arrondit par défaut … embrouille mais voir table ci-dessous.
    • L’algorithme de dichotomie a une complexité au pire de l’ordre de O\left(\log_2(n)\right)
    • O(\cdots) est la complexité au pire
    • L’algorithme naïf est de complexité de O(n) car on prend nombre par nombre.
    • Un algorithme de dichotomie s’arrête de deux manières :
      • soit si on trouve le bon nombre et on renvoie l’indice (donc milieu),
      • soit on s’arrête car droite<gauche ou gauche>droite (c’est pareil) et on renvoie -1.
    • On code ça avec while droite >= gauche

Pourquoi ce décalage de 1 entre le log en base 2 et le nombre max de coups dont on n’a pas vraiment parlé pendant le cours ?

cm 2020-03-25 log_2 et dichotomie

Travail d’ici lundi (rien à rendre) :

  • Travailler et comprendre le document institutionnel jusqu’au mileu de la troisième page.
  • Programmer la dichotomie en commençant par compléter le pseudo-code ci-dessous (le code étant déjà dans le document en lien) :
    • en entrée une liste t et une valeur à chercher val
    • on initialise
      • gauche à …
      • droite à …
    • tant que gauche … droite :
      • milieu =
      • si t[milieu] … val
        • alors renvoyer …
      • sinon si t[milieu] … val
        • alors droite = milieu … 1
      • sinon :
        • alors gauche = milieu … 1
    • renvoyer …
  • QCM (27 questions = une bonne heure max) :

Correction des exercices pour le 25 mars

Premier exercice

Votre algorithme doit afficher toutes les couleurs (codes à six chiffres hexadécimaux) possibles … en théorie !
Il y en a beaucoup trop… combien ? -> 16 777 216

def gere_hexa(chiffre):
    """
    attend un chiffre entre 0 et 15
    renvoie un caractère 0 ... 9 A ... F
    """
    if chiffre > 9:
        return chr(55 + chiffre)
    return str(chiffre)

def hexadecimal(nombre):
    """
    attend un nombre entre 0 et 255 (un octet)
    renvoie une chaine de deux caratères correspondant au nombre
    (la fonction hex de python le gère aussi)
    """

    # c'est sur un octet
    assert 0 <= nombre < 256

    quotient = nombre // 16
    reste = nombre % 16

    return gere_hexa(quotient) + gere_hexa(reste)

def couleurs(max_r, max_v, max_b):
    """
    Affiche tous les 256 * 256 * 256 = 16 777 216 codes couleurs
    si max_r = max_b = max_v
    """
    for r in range(max_r):
        for v in range(max_v):
            for b in range(max_b):
                print("#" + hexadecimal(r) + hexadecimal(v) + hexadecimal(b))

# couleurs(256, 256, 256)

Il faudrait plus de onze heures chez moi pour le tester avec

couleurs(256, 256, 256)

Sérieux ?

Je ne l’ai pas fait, j’ai rajouté en dessous

from time import time

debut = time() # temps en secondes depuis le 01/01/1970

# On lance un programme réduit divisé par 64 et par 16
couleurs(4, 16, 256)

fin = time() # temps en secondes depuis le 01/01/1970

print(fin - debut) # c'est le temps en seconde écoulé

print("Pour toutes les couleurs, il faudrait :")
print("Plus de", int(((fin - debut) * 64 * 16 // 60) //60), "heures.")

Et ça donne

#000000
#000001
#000002
#000003
#000004
#000005
#000006
#000007
#000008
#000009
#00000A
#00000B
#00000C
#00000D
#00000E
#00000F
#000010
#000011
#000012
#000013
#000014
#000015
#000016
#000017
#000018
#000019
#00001A
#00001B
#00001C
#00001D
#00001E
#00001F
#000020
#000021
#000022
#000023
#000024
#000025
#000026
#000027
#000028
#000029
#00002A
#00002B
#00002C
#00002D
#00002E
#00002F
...
#030FFC
#030FFD
#030FFE
#030FFF
40.56948494911194
Pour toutes les couleurs, il faudrait :
Plus de 11 heures.
>>>

Plus d’infos sur la bibliothèque time et sa fonction time() .

 

Deuxième exercice

Combien de triangles de côtés (a, b, c) rectangles, c’est-à-dire tels que a^2 + b^2 = c^2a, b, c sont des entiers non nuls, chacun au maximum égal à 100?
Avec un algorithme bien entendu…

def egalite_de_pythagore(a, b, c):
    return a ** 2 + b ** 2 == c ** 2

def triplets():
    liste = []
    for a in range(1, 101): # de 1 à 100 svp !
        for b in range(1, 101):
            for c in range(1, 101):
                if egalite_de_pythagore(a, b, c) and (b, a, c) not in liste :
                    liste.append((a, b, c))
    return liste

def affichage():
    tous = triplets()
    print("Il y a", len(tous), "possibilités")
    for a, b, c in tous:
        print(str(a) + "^2 +" + str(b) + "^2 =" + str(c) + "^2")
    print("Tous ces triangles sont constructibles.")

affichage()

N.B. : On vous laisse le commenter celui-là 😉

Il y a 52 possibilités
3^2 +4^2 =5^2
5^2 +12^2 =13^2
6^2 +8^2 =10^2
7^2 +24^2 =25^2
8^2 +15^2 =17^2
9^2 +12^2 =15^2
9^2 +40^2 =41^2
10^2 +24^2 =26^2
11^2 +60^2 =61^2
12^2 +16^2 =20^2
12^2 +35^2 =37^2
13^2 +84^2 =85^2
14^2 +48^2 =50^2
15^2 +20^2 =25^2
15^2 +36^2 =39^2
16^2 +30^2 =34^2
16^2 +63^2 =65^2
18^2 +24^2 =30^2
18^2 +80^2 =82^2
20^2 +21^2 =29^2
20^2 +48^2 =52^2
21^2 +28^2 =35^2
21^2 +72^2 =75^2
24^2 +32^2 =40^2
24^2 +45^2 =51^2
24^2 +70^2 =74^2
25^2 +60^2 =65^2
27^2 +36^2 =45^2
28^2 +45^2 =53^2
28^2 +96^2 =100^2
30^2 +40^2 =50^2
30^2 +72^2 =78^2
32^2 +60^2 =68^2
33^2 +44^2 =55^2
33^2 +56^2 =65^2
35^2 +84^2 =91^2
36^2 +48^2 =60^2
36^2 +77^2 =85^2
39^2 +52^2 =65^2
39^2 +80^2 =89^2
40^2 +42^2 =58^2
40^2 +75^2 =85^2
42^2 +56^2 =70^2
45^2 +60^2 =75^2
48^2 +55^2 =73^2
48^2 +64^2 =80^2
51^2 +68^2 =85^2
54^2 +72^2 =90^2
57^2 +76^2 =95^2
60^2 +63^2 =87^2
60^2 +80^2 =100^2
65^2 +72^2 =97^2
Tous ces triangles sont constructibles.
>>>

 

Parmi ceux -ci, combien forment des triangles rectangles (c’est-à-dire : peut-on tous les construire) ?

Tous !

Si a^2 + b^2 = c^2 avec a \geqslant 1, b \geqslant 1 et c \geqslant 1,
alors a^2 + 2 \times a \times b + b^2 \geqslant c^2 puisque 2 \times a \times b \geqslant 2 \times 1 \times 1 = 2 > 0
soit (a +b)^2 \geqslant c^2
et donc a +b \geqslant c puisque x \mapsto \sqrt{x} croissante sur \mathbb{R}^{+}.

Donc l’inégalité triangulaire est forcément vérifiée, ils sont tous constructibles !

Un petit QCM / Quizz ?

Thème A : types de base

Quel est un avantage du codage UTF8 par rapport au codage ASCII ?
il permet de coder tous les caractères
il permet de coder un caractère sur un octet au lieu de deux
il permet de coder les majuscules
il permet de coder différentes polices de caractères
Dans quel système de numération 3F5 représente-t-il un nombre entier ?
hexadécimal (base 16)
binaire (base 2)
octal (base 8)
décimal (base 10)

Thème B : types construits

On définit :
T = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Laquelle des expressions suivantes a pour valeur 7 ?
T[2][0]
T[3][1]
T[3, 1]
T[2, 0]
Quelle est la valeur de l’expression
[(i,i+1) for i in range(2)]
[(0, 1), (1, 2)]
[0, 1, 1, 2]
[(1, 2), (2, 3)]
[[0, 1], [1, 2]]
Quelle est l’expression qui a pour valeur la liste
[1, 4, 9, 16, 25, 36]
[n * n for n in range(1, 7)]
[n * n for n in range(6)]
[n * n for n in range(7)]
[n * n for n in range(1, 6)]
Si la variable note est définie par
note = ["do", "ré", "mi", "fa", "sol", "la", "si"]
alors :
l’index de « mi » est 2
l’index de note est 0
l’index de « si » est 7
l’index de « sol » est 5

Thème C : traitement de données en tables

T = [ {'fruit': 'banane', 'nombre': 25},
      {'fruit': 'orange', 'nombre': 124},
      {'fruit': 'pomme', 'nombre': 75},
      {'fruit': 'kiwi', 'nombre': 51} ]
Quelle expression a-t-elle pour valeur le nombre de pommes ?
T[2]['nombre']
T[2, 'nombre']
T[3]['nombre']
T[3, 'nombre']
Que réalise l’instruction suivante :
mon_fichier = open("exemple.txt", "r")
Elle permet d’ouvrir le fichier « exemple.txt » en mode lecture si le fichier est dans le même dossier que le fichier du programme Python comportant cette instruction.
Elle permet d’ouvrir le fichier « exemple.txt » en mode lecture même si le fichier n’est pas dans le même dossier que le fichier du programme Python comportant cette instruction.
Elle permet d’ouvrir le fichier « exemple.txt » en mode écriture si le fichier est dans le même dossier que le fichier du programme Python comportant cette instruction.
Elle permet d’ouvrir le fichier « exemple.txt » en mode écriture même si le fichier n’est pas dans le même dossier que le fichier du programme Python comportant cette instruction.

Thème F : langages et programmation

En Python, quelle est la méthode pour charger la fonction sqrt du module math ?
from math import sqrt
using math.sqrt
#include math.sqrt
from math include sqrt
On définit deux fonctions :
def f(x):
    y = 2 * x + 1
    return y
def calcul(x):
    y = x - 1
    return f(y)
Quelle est la valeur renvoyée par l’appel
calcul(5)
9
4
11
19

Thème G : algorithmique

On considère la fonction Python suivante, qui prend en argument une liste L et renvoie le maximum des éléments de la liste :
def rechercheMaximum(L):
    max = L[0]
    for i in range(len(L)):
        if L[i] > max:
            max = L[i]
    return max
On note la taille de la liste. Quelle est la complexité en nombre d’opérations de l’algorithme ?
linéaire, c’est-à-dire de l’ordre de
constante, c’est-à-dire ne dépend pas de
quadratique, c’est-à-dire de l’ordre de
cubique, c’est-à-dire de l’ordre de
Pour trier par sélection une liste de 2500 entiers, le nombre de comparaisons nécessaires à l’algorithme est
de l’ordre de
de l’ordre de
de l’ordre de
de l’ordre de

Tris : complexité

Des séances difficiles aujourd’hui et mercredi, peut-être conceptuellement les plus difficiles de l’année.


Plan (début du cours à 10h) :

  • Question flash
  • Correction algorithmes
  • Complexité (temporelle)
  • Salon de discussion de 11h à 12h
    • Attentes et habitudes de travail pour cette période de confinement
    • Complexité
  • Preuves (pas abordé aujourd’hui)
  • Exercices donnés pour mercredi

Question flash :

  • Compléter le corps de la boucle « intérieure » en une instruction d’une ligne pour que ce programme affiche tous les nombres de 00 à 99
    for d in range(10):
        for u in range(10):
            ...

Plusieurs réponses proposées :

  • Attendue avec d comme chiffre des dizaines et u comme chiffre des unités
    for d in range(10):
        for u in range(10):
            print(d * 10 + u)
  • En concaténation pour l’affichage avec d comme chiffre des dizaines et u comme chiffre des unités
    for d in range(10):
        for u in range(10):
            print(str(d) + str(u))
  • En changeant les range 😉 pas imposés à l’origine avec d comme chiffre des dizaines et u comme chiffre des unités
    for d in range(0, 100, 10):
        for u in range(10):
            print(d + u)
  • D’autres…

Correction de l’implémentation des algorithmes demandée

Allez prendre connaissance des corrections des algorithmes pour aujourd’hui :

Préparez vos questions pour le salon de discussion à 11H.

Peu de questions. Il y avait ceux qui avaient bossé, et les autres !

Mais aussi des problèmes MBN. On a statué sur le fait qu’on pouvait m’envoyer des codes de plein de manières, discord, mail, etc.

ET aussi TAKE IT EASY 😉 IT’S GONNA BE ALRIGHT ! BUT WORK !


Complexité (temporelle)

a) Une intuition ?

J’ai fait quelques animations pour illustrer mon propos.

Une liste aléatoire de 16 chiffres et les deux tris en action :

0_animation_les_deux_en_meme_temps

  • En vert les cases déjà triées,
  • la flèche rouge pour le rang,
  • la case rouge pour la « boucle intérieure »,
  • les cases en bleu encore à trier,
  • en jaune la valeur correspondant temporairement à « i_min » pour le tri par sélection.

On compte le nombre de comparaisons en haut à droite.
Ce sera notre indicateur de complexité temporelle. Une intuition ?

-> Notre intuition c’est que le tri par insertion semble a priori plus rapide… c’est-à-dire moins de comparaisons et donc une plus faible complexité temporelle .

b) Plus dans le détail – tri par sélection

Avec nos cartes comme dans la vidéo de l’autre jour

cm 2020-03-23 cartes dessinees

Qu’est-ce que ça donne :

  • Combien de comparaisons ? -> 20
  • Ce nombre change-t-il suivant la valeur des six cartes ? -> non, on fait toujours les mêmes comparaisons :
(Notes de notre salon de discussion discord)
(Complexité temporelle : nombre de comparaisons)
Tri sélection pour 6 valeurs :
    Premier passage 
       -> 5 comparaisons (boucle intérieure) 
       -> + 1 comparaison de i_min et rand donc 
    Donc :
        1er passage 5 + 1 = 6 comparaisons
	2e passage  4 + 1 = 5 comparaisons
	3e passage  3 + 1 = 4 comparaisons
	4e passage  2 + 1 = 3 comparaisons
	5e passage  1 + 1 = 2 comparaisons
    Fin du programme :
        6 + 5 + 4 + 3 + 2 = 20 comparaisons

c) Plus dans le détail – tri par insertion

Toujours avec nos cartes, comme dans l’autre vidéo de l’autre … autre jour

cm 2020-03-23 cartes dessinees

Qu’est-ce que ça donne :

  • Combien de comparaisons ? -> 14
  • Ce nombre change-t-il suivant la valeur des six cartes ? -> Oui, on n’insère pas un 2 comme on insère un 8 par exemple !

c) Plus dans le détail – comparaison des tris par sélection et par insertion

Toujours avec nos cartes des autres jours :

Qu’est-ce que ça donne :

  • Qui est le plus rapide (moins de comparaisons) ?
    -> le tri par insertion
  • Est-ce toujours le cas ?
    -> On dirait ! (?)

On veut en avoir le cœur net :

d) Un exemple, le « pire des cas » pour le tri par insertion

Questions :

On cherche une conclusion : complexité temporelle de ces deux tris

  • Combien de comparaisons pour le tri par sélection de 6 valeurs ? -> 20
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 6 valeurs ? -> 20 aussi (au pire)
  • Combien de comparaisons pour le tri par sélection de 10 valeurs ? -> 54
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 10 valeurs ? -> 54 aussi (au pire)
  • Combien de comparaisons pour le tri par sélection de 7 valeurs ? -> 27
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 7 valeurs ? -> 27 aussi (au pire)
  • Combien de comparaisons pour le tri par sélection de 16 valeurs (premier gif animé) ? -> 135
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de 16 valeurs ? -> 135 aussi (au pire)
  • On considère maintenant n un entier positif non nul.
  • Combien de comparaisons pour le tri par sélection de n valeurs ?
    De l'ordre du carré de n.
    On parle de complexité quadratique, voir ci-dessous.
  • Combien de comparaisons au maximum (dans le pire des cas) pour le tri par insertion de n valeurs ?
    Et bien la même chose : 
    si la liste est triée par valeurs décroissantes !

La partie théorique abordée aujourd’hui

Complexité du tri par sélection

(Notes de notre salon de discussion discord)
(Complexité temporelle : nombre de comparaisons)
Tri sélection pour n valeurs :
    Premier passage 
       -> (n - 1) comparaisons (boucle intérieure) 
       -> + 1 comparaison de i_min et rand donc 
    Donc :
        1er passage    n    comparaisons
	2e passage  (n - 1) comparaisons
	3e passage  (n - 2) comparaisons
                      ...
avant-dernier passage  3    comparaisons
      dernier passage  2    comparaisons
Fin du programme :
   n + (n - 1) + (n - 2) + ... + 3 + 2 comparaisons

Combien ça fait n +(n - 1) + (n - 2) + ... + 3 + 2 ?

Écrivons le deux fois, l’un au-dessous de l’autre :

cm 2020-03-23 calcul somme complexité

Les deux lignes font donc (n+2) \times (n -1)=n^2+2n-n-2=n^2+n-2.

Une seule ligne fait donc \boxed{n +(n - 1) + (n - 2) + ... + 3 + 2 = \dfrac{n^2+n-2}{2}}.

Les informaticiens estiment que, quand n devient grand, il devient négligeable devant le n^2, tout comme le -2. Ils estiment même que la division par deux n’est pas le cœur du problème.

En effet, pour n = 1 000 000, n^2 fait mille milliards, et même n = 1 000 000 est négligeable…

Pour simplifier, avec une notation de Landau utilisées en informatique, on retiendra que :

La complexité du tri par sélection est de l’ordre du carré de n : on parle de complexité quadratique, et on la note O(n^2) : « de l’ordre de n^2 au pire »

A titre de comparaison, la recherche du maximum ou du minimum dans une liste nécessite autant de comparaisons que le nombre d’éléments n de cette liste, on dit qu’elle est linéaire, et  on la note O(n).

Complexité du tri par insertion

Il nous semble meilleur, donc plus rapide, donc avec une complexité plus faible. EN MOYENNE, c’est certainement vrai.

Mais AU PIRE, quand la liste est à l’origine classée par valeurs décroissantes, la complexité est la même :

(Notes de notre salon de discussion discord)
(Complexité temporelle : nombre de comparaisons)
Tri insertion pour n valeurs triées dans l'ordre décroissant 
(comme 8 7 6 5 4 3 2) :
    Premier passage 
       -> 1 comparaisons (boucle intérieure) 
       -> + 1 comparaison de i avec zéro 
    Donc :
        1er passage      2    comparaisons
	2e passage       3    comparaisons
	3e passage       4    comparaisons
                        ...
avant-dernier passage (n - 1) comparaisons
      dernier passage    n    comparaisons
Fin du programme :
   2 + 3 + ...  + (n - 2) + (n - 1) + n comparaisons

Donc n +(n - 1) + (n - 2) + ... + 3 + 2 = 2 + 3 + ... + (n-2)+(n-1)+n

On a donc aussi, dans le pire des cas : \boxed{n +(n - 1) + (n - 2) + ... + 3 + 2 = \dfrac{n^2+n-2}{2}}.

La complexité AU PIRE du tri par insertion est aussi de l’ordre du carré de n : une complexité quadratique, notée aussi O(n^2) : « de l’ordre de n^2 au pire »

Conclusion à retenir :

  • Le tri par sélection est de complexité quadratique.
  • Le tri par insertion est de complexité quadratique, au pire.

Sinon, on abordera mercredi cette question :

  • Ces tris sont-ils toujours corrects ? Peut-on les PROUVER ?

Mercredi salon de discussion 13h27 – 15h17 😉

Pour mercredi 25 mars -> à rendre au plus tard dans la nuit de mardi à mercredi par le canal que vous voulez (discord, mail, MBN, etc.):

  1. Premier exercice : refaire la question flash pour que votre algorithme affiche toutes les couleurs (codes à six chiffres hexadécimaux) possibles … en théorie !
    Il y en a beaucoup trop… combien ?
  2. Deuxième exercice : combien de triplets (a, b, c) tels que a^2 + b^2 = c^2a, b, c sont des entiers non nuls, chacun au maximum égal à 100?
    Avec un algorithme bien entendu…
    Parmi ceux -ci, combien forment des triangles rectangles (c’est-à-dire : peut-on tous les construire) ?
  3. Retravailler sérieusement le cours d’aujourd’hui.

Tri par insertion

C’est le tri naturel du joueur de cartes qui ramasse celles qui lui sont distribuées et les insère dans son jeu.

Programmer pour lundi un code qui produit ceci, à l’aide de deux boucles imbriquées :

La liste initiale
[8, 6, 2, 9, 3, 4]
On insère le 6
[6, 8, 2, 9, 3, 4]
On insère le 2
[2, 6, 8, 9, 3, 4]
On insère le 9
[2, 6, 8, 9, 3, 4]
On insère le 3
[2, 3, 6, 8, 9, 4]
On insère le 4
[2, 3, 4, 6, 8, 9]
>>> 

Le pseudo-code depuis la page wikipedia :

  procédure tri_insertion(liste t)
       pour rang de 1 à len(t) - 1 # donc for rang in range(len(t)) ;-)

            # mémoriser t[rang] dans carte
            carte ← t[rang]                            

            # décaler vers la droite les éléments de t[0]..t[rang-1] qui sont plus grands que carte en partant de t[rang-1]
            i ← rang                               
            tant que i > 0 et t[i - 1] > carte
                     t[i] ← t[i - 1]
                     i ← i - 1

            # placer carte dans le "trou" laissé par le décalage
            t[i] ← carte

CORRIGÉ :

Déception : peu de codes rendus, mais aussi des satisfactions !
J’ai commenté individuellement sur MBN.

Version 1 – deux boucles imbriquées :

def tri_insertion(t):
    # il faut une liste non vide
    assert len(t) > 0
    print("La liste initiale")
    print(t)
    # parcours de la liste jusqu'à la dernière valeur
    for rang in range(1, len(t)):
        # On veut insérer cette 'carte', on la 'descend' vers la gauche
        # on stocke sa valeur. Le rang est gardé puisque c'est i qui 'descend'
        carte = t[rang]
        print("On insère le", carte)

        # i va décroître donc, en partant de rang
        i = rang
        
        # tant que celle de gauche est plus GRANDE
        # attention à ne pas aller en dessous de zéro !!
        
        while i > 0 and t[i - 1] > carte:
            t[i] = t[i - 1] # on décale vers la droite
            i -= 1          # on descend à gauche

        # on est sorti du while : soit on est à zéro soit c'est
        # en i qu'il faut mettre la carte
        t[i] = carte
        # affichage
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_insertion(t)

Version 2 – en utilisant une fonction insere intercalée :

def insere(t, rang):
    # On veut insérer cette 'carte', on la 'descend' vers la gauche
    # on stocke sa valeur. Le rang est gardé puisque c'est i qui 'descend'
    carte = t[rang]
    print("On insère le", carte)

    # i va décroître donc, en partant de rang
    i = rang
    
    # tant que celle de gauche est plus GRANDE
    # attention à ne pas aller en dessous de zéro !!
    
    while i > 0 and t[i - 1] > carte:
        t[i] = t[i - 1] # on décale vers la droite
        i -= 1          # on descend à gauche

    # on est sorti du while : soit on est à zéro soit c'est
    # en i qu'il faut mettre la carte
    t[i] = carte
    return t

def tri_insertion(t):
    # il faut une liste non vide
    assert len(t) > 0
    print("La liste initiale")
    print(t)
    # parcours de la liste jusqu'à la dernière valeur
    for rang in range(1, len(t)):
        

        # insertion
        t = insere(t, rang)
        
        # affichage
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_insertion(t)

Besoin d’un autre regard ?

Suite de notre progression en NSI ?

Prochain cours lundi 10h sur ce site.

Chat audio lundi à 11h sur discord.

Tri par sélection

On veut donc trier un tableau ou pour nous une liste qu’on nomme ici t.

t = [8, 6, 2, 9, 3, 4]

Questions 1 :

  • Que vaut len(t) ?
  • Que vaut t[0] ? t[1] ?
  • Que vaut t[5] ? t[6] ?
  • Que vaut t[-1] ?

Réponses 1 :

Question 2 :

  • Comment trouver l’indice du minimum de cette liste ?
t = [8, 6, 2, 9, 3, 4]

Réponse 2 :

En code, qu’est-ce que ça donne ?

def indice_minimum(liste):
    assert len(liste) > 0
    i_min = ...
    for i in range(..., ......):
        if liste[...] < liste[...]:
            i_min = ...
    return ...

Question 3 :

  • Compléter le code ci-dessus.
    Pour le tester :

    >>> t = [8, 6, 2, 9, 3, 4]
    >>> indice_minimum(t)
    2
    >>>

Réponse 3 :

Question 4 :

  • Comment intervertir les valeurs de deux variables a et b en python ?

Réponse 4 :

  • En python, c’est plus facile que dans d’autres languages :
    >>> a = 42
    >>> b = 21
    >>> a, b
    (42, 21)
    >>> a, b = b, a # interversion
    >>> a, b
    (21, 42)
    >>> a
    21
    >>> b
    42
    >>>  # c'est gagné 🙂

Le tri en lui même

Reprenons maintenant notre tri, comme sur la vidéo. Les étapes sont :

[8, 6, 2, 9, 3, 4]
indice du minimum : 2
On intervertit les valeurs des rangs 0 et 2
[2, 6, 8, 9, 3, 4]
indice du minimum : 4
On intervertit les valeurs des rangs 1 et 4
[2, 3, 8, 9, 6, 4]
indice du minimum : 5
On intervertit les valeurs des rangs 2 et 5
[2, 3, 4, 9, 6, 8]
indice du minimum : 4
On intervertit les valeurs des rangs 3 et 4
[2, 3, 4, 6, 9, 8]
indice du minimum : 5
On intervertit les valeurs des rangs 4 et 5
[2, 3, 4, 6, 8, 9]
>>> 

On a donc deux boucles imbriquées (je proposerai un corrigé avec deux fonctions pour éviter cette lourdeur) :

  • une boucle « extérieure » avec une indice rang qui parcourt la liste t an allant des rangs 0 à 4 ici, donc de 0 à len(t) - 2 en règle générale,
    • une boucle « intérieure » avec un indice i qui cherche l’indice du minimum i_min,
    • on intervertit alors t[rang] et t[i_min] après cette boucle « intérieure ».

En pseudo-code, l’algorithme du tri par sélection est (source Wikipedia) :

  procédure tri_selection(liste t)
      pour rang de 0 à len(t) - 2
          i_min ← rang       
          pour i de rang + 1 à len(t) - 1
              si t[i] < t[i_min], alors i_min ← i
          fin pour
          si i_min ≠ rang, alors échanger t[rang] et t[i_min]
      fin pour
  fin procédure

Mieux comprendre le rôle des indices ? Une nouvelle vidéo :

Question 5 pour vendredi :

  • programmer une fonction tri_selection(t) qui effectue ce tri.
  • déposer ce code dans la collecte prévue à cet effet sur mon bureau numérique.

Réponse 5, finalement samedi – CORRIGÉ :

Déception : seulement huit neuf codes rendus, mais aussi des satisfactions !
J’ai commenté individuellement sur MBN.

Version 1 – deux boucles imbriquées :

def tri_selection(t):
    # il faut une liste non vide
    assert len(t) > 0
    print(t)
    # parcours de la liste jusqu'à l'avant dernier
    for rang in range(len(t) - 1):
        # recherche de l'indice du minimum
        # on initialise
        i_min = rang
        # on parcourt le reste de la liste
        for i in range(rang + 1, len(t)):
            # si on trouve plus petit ...
            if t[i] < t[i_min]:
                # ... alors l'indice change !
                i_min = i
        print("indice du minimum :", i_min)

        if i_min != rang :
            # interversion : le minimum passe devant
            print("On intervertit les valeurs des rangs", rang, "et", i_min)
            t[rang], t[i_min] = t[i_min], t[rang]
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_selection(t)

Version 2 – en utilisant la fonction indice_minimum :

def indice_minimum(liste, rang):
    # il faut une liste non vide
    assert len(liste) > 0
    # on initialise
    i_min = rang
    # on parcourt le reste de la liste
    for i in range(rang + 1, len(liste)):
        # si on trouve plus petit ...
        if liste[i] < liste[i_min]:
            # ... alors l'indice change !
            i_min = i
    # On renvoie l'indice du minimum
    return i_min

def tri_selection(t):
    print(t)
    # parcours de la liste jusqu'à l'avant dernier
    for rang in range(len(t) - 1):
        # recherche de l'indice du minimum
        ind_min = indice_minimum(t, rang)
        print("indice du minimum :", ind_min)
        if ind_min != rang :
            # interversion : le minimum passe devant
            print("On intervertit les valeurs des rangs", rang, "et", ind_min)
            t[rang], t[ind_min] = t[ind_min], t[rang]
        print(t)

t = [8, 6, 2, 9, 3, 4]
tri_selection(t)

Besoin d’un autre regard ?

Suite de notre progression en NSI ?

  • Corrigé et autre algorithme de tri vendredi.
  • Salon de discussion discord lundi prochain le 23 mars à 11h00.

Bon courage !