Travail pour lundi

Pour lundi prochain 6 avril 2020

Je vous mets à disposition un fichier csv, téléchargeable ici (bouton droit, enregistrer sous, dessin.csv).

L’enregistrer dans un dossier. Le script ci-dessous est à enregistrer puis lancer dans le même dossier !

Compléter la fonction ci-dessous lecture qui va lire ce fichier et renvoyer une liste constituée de dictionnaires comme

{ 'espece' : 'noir', 'abscisse' : 1, 'ordonnee' : 2}

Attention les deux dernières valeurs sont à convertir en entier !

Pour que ce script fonctionne il faudra installer matplotlib avec l’une de ces commandes (selon votre version de python) en invite de commandes (touche windows, taper cmd)

  • py -3.8 -m pip install matplotlib
  • py -3.7 -m pip install matplotlib
  • py -3.6 -m pip install matplotlib
  • py -3.5 -m pip install matplotlib
  • etc.

Le code à compléter :

def lecture(nom_du_fichier) :
    # initialisation : liste vide
    liste = ...

    # ouverture du fichier en lecture -> 'r'
    with open(... , ...) as fichier:

        # on récupère le contenu
        texte = fichier.read()

        # on le separe en lignes
        lignes = texte.split(sep = '\n')

        # on parcourt les lignes
        for phrase in lignes:

            # on découpe la phrase en trois morceaux dans une liste
            # attention dans ce csv le séparateur
            # est un virgule , et pas un ;
            liste_de_trois = ...

            if len(liste_de_trois) == 3:
                # un nouveau dico vide appelé new
                new = ...

                new['espece'] = liste_de_trois[2]

                # attention : à convertir en entiers
                # le premier élément de la liste
                new['abscisse'] = ...

                # le deuxième élément de la liste
                new['ordonnee'] = ...

                # on rajoute new à la liste
                ...

        # on ferme le fichier ouvert
        ...

    # on renvoie la liste remplie
    return ...

liste = lecture("dessin.csv")

###########################################
# Le code ci-dessous n'est pas à modifier #
###########################################

import matplotlib.pyplot as plt 

tuning = [('noir', 'black'),
          ('jaune', 'yellow'),
          ('bleu', 'b'),
          ('truc','white')]

for spec, couleur in tuning:
    # données
    x=[]
    y=[]
    for f in liste :
        if f['espece'] == spec:
            x.append(f['abscisse'])
            y.append(f['ordonnee'])
    plt.scatter(x, y, color = couleur, label = spec, marker = 's')

# graphique
plt.legend()
plt.show()

Créer du html !

Munissez-vous de notepad++ sous windows pour encoder votre texte ou un autre bon éditeur… PAS DE WORD OU DE BLOC-NOTES OU WORDPAD ici !!!

On ouvre un nouveau thème, le sixième sur sept en tout, appelé « Interactions entre l’homme et la machine sur le Web »

Les plus curieux parmi vous peuvent voir ce qu’on est censé faire en cliquant ici, mais ça peut faire peur… pour rien !

On a déjà fait ceci :

<!doctype html>
<html lang="fr">
<head>
  <meta charset="utf-8">
  <title>Ma page de NSI</title>
</head>
<body>
  <p>J'adore mes élèves de 
  <a href="https://mathonomie.com/2019/03/01/premiere-page-en-html/">NSI</a>.</p>
  <p>Ils sont <em>top.</em><br />
  <strong>Surtout les girls ;-)</strong></p>
  <pre>print("Je kiffe grave")
  >>> Je kiffe grave</pre>
  <a href="https://fr.wikipedia.org/wiki/Le_Monde_de_Dory">
      <img src="https://mcusercontent.com/7cc10f722af6d9eca85880602/images/0daa521c-5302-4e23-9e6d-6675db85bd3b.gif" width=100px></a>
</body>
</html>

Qui a donné ceci :

cm 2020-04-01 une première page

Il y a beaucoup de choses sur ce site et nous allons visiter ensemble

Les veinards qui ont suivi l’ICN l’an dernier ont déjà de belles notions…

 

D’ici mercredi prochain, il faut avoir attentivement lu les pages ci-dessous sur la chaîne lumni :

Vrai ou Faux ?

Questions « flash » du 1er avril

not True ?
False
On vous demande le contraire « logique ».
Par exemple si « x == 2 » est vrai, alors « x == 2 » vaut True.
On va donc statuer que x vaut 2.
Alors « not (x == 2) » est pareil que « x != 2 » et ça c’est faux, puisque x vaut 2.
True
Ben non, c’est not True, alors c’est pas True 😀
I don’t know 😦
C’est mal.
I know but I won’t tell 😉
Chenapan.
True or False ?
True
On vous demande si c’est vrai, ou si le contraire est vrai.
Par exemple est-ce que « x == 2 » ou « x != 2 » ?
Et ça, peu importe ce que vaut x, c’est l’un OU l’autre.
Donc si l’un est vrai OU l’autre est vrai c’est vrai.
Donc si x vaut 2 c’est vrai, et si x ne vaut pas 2, c’est encore vrai.
C’est toujours vrai.
Wrong
On dit pas wrong, on dit False, et c’est False de dire False, parce que c’est True 😀
I still don’t know 😦
C’est vraiment mal.
I know but I won’t tell 😉
Décidément, frippon canaillou, va..

TP – afficheurs d’octets UTF8

Prérequis :

Se souvenir du cours sur l’utf8, comme ici.

NSI première : C’était pour mercredi 1er avril

ISN terminale : c’est le TP du jeudi 2 avril

Réaliser une fonction affiche_octets_utf8 qui … affiche les octets (en binaire) d’un caractère (encodé en utf8) envoyé en paramètre d’entrée (ou en argument si vous préférez).

Le découpage fonctionnel est le suivant :

def un_octet(chaine_de_bits):
    # renvoie par exemple pour l'espace :
    # 00100000
    # pour le A (code 65) :
    # 01000001
def deux_octets(c):
    # renvoie par exemple pour é :
    # 11000011 10101001
def trois_octets(c):
    # renvoie par exemple pour €  :
    # 11100010 10000010 10101100

def quatre_octets(c):
    # attention deux cas ici

def affiche_octets_utf8(caractere):
    # utilise une fonction native de python
    # pour avoir les bits de l'écriture binaire
    # et suivant la longueur ce cette chaîne binaire appelle
    # l'une des quatre fonctions ci-dessus
    # en leur envoyant la chaîne binaire pour qu'elles
    # renvoie les octets

print(affiche_octets_utf8(' '))
print(affiche_octets_utf8('A'))
print(affiche_octets_utf8('é'))
print(affiche_octets_utf8('€'))
print(affiche_octets_utf8(chr(2 ** 15)))
print("C'est le glyphe ou caractère pour un code de 2 ** 15")
print("D'après google translate, voudrait dire 'Yào' soit briller en chinois !")
print("L'afficheur quatre octets est un peu virtuel :")
print("Pas de code unicode à quatre octets à ce jour ...")
print("... compatibles avec Python 3.")
print("Mais, avec la fonction quatre_octets, un code de")

for k in range(17, 21):
    print("2 **", k, "doit afficher", quatre_octets(bin(2 ** k)[2:]))
    print("(" + str(k + 1) + " bits)")

Et ce code doit afficher :

  est codé sur 1 octet (ASCII) : 00100000
A est codé sur 1 octet (ASCII) : 01000001
é est codé sur 2 octets : 11000011 10101001
€ est codé sur 3 octets : 11100010 10000010 10101100
耀 est codé sur 3 octets : 11101000 10000000 10000000
C'est le glyphe ou caractère pour un code de 2 ** 15
D'après google translate, voudrait dire 'Yào' soit briller en chinois !
L'afficheur quatre octets est un peu virtuel :
Pas de code unicode à quatre octets à ce jour ...
... compatibles avec Python 3.
Mais, avec la fonction quatre_octets, un code de
2 ** 17 doit afficher 11110000 10100000 10000000 10000000
(18 bits)
2 ** 18 doit afficher 11110001 10000000 10000000 10000000
(19 bits)
2 ** 19 doit afficher 11110010 10000000 10000000 10000000
(20 bits)
2 ** 20 doit afficher 11110100 10000000 10000000 10000000
(21 bits)
>>>

A finir pour les courageux !

 

J’ai donné ce début de code sur discord

def un_octet(chaine_de_bits):
    '''renvoie par exemple pour l'espace : 00100000
    pour le A (code 65) : 01000001'''
    longueur = len(chaine_de_bits)
    nb_zeros = 8 - longueur
    return nb_zeros * '0' + chaine_de_bits #'00' + '100000'

def deux_octets(c):
    '''renvoie par exemple pour é : 11000011 10101001'''
    deuxieme_octet = '10' + c[-6:]
    premier_octet = '110' + '0' * (5 - len(c[:-6])) + c[:-6]
    return premier_octet + ' ' + deuxieme_octet

def affiche_octets_utf8(caractere):
    # utilise une fonction native de python
    # pour avoir les bits de l'écriture binaire
    code = ord(caractere)
    chaine = bin(code)
    chaine = chaine[2:]
    log2 = len(chaine)

    if log2 > 8:
        return un_octet(chaine)
    elif log2 > 12:
        return deux_octets(chaine)

    # et suivant la longueur ce cette chaîne binaire appelle
    # l'une des quatre fonctions ci-dessus
    # en leur envoyant la chaîne binaire pour qu'elles
    # renvoie les octets

print(affiche_octets_utf8(' ')) # 32 -> 00 100000
print(affiche_octets_utf8('A')) # 65 -> 0 1000001
print(affiche_octets_utf8('é'))

Et ces explications dans le shell

>>> 'é'
'é'
>>> chr(65)
'A'
>>> ord('é')
233
>>> bin(ord('é'))
'0b11101001'
>>> bin(233)
'0b11101001'
>>> hex(233)
'0xe9'
>>> bin(233)
'0b11101001'
>>> bin(ord('é'))
'0b11101001'
>>> bin(ord('é'))[0]
'0'
>>> bin(ord('é'))[1]
'b'
>>> bin(ord('é'))[0:2]
'0b'
>>> bin(ord('é'))[2:]
'11101001'
>>> bin(ord('A'))[2:]
'1000001'
>>> bin(ord(' '))[2:]
'100000'
>>> '0' * 2 + bin(ord(' '))[2:]
'00100000'
>>> 2 ** 15
32768
>>> 2 ** 17
131072
>>> 2 ** 16
65536
>>> print(chr(2 ** 15))
耀
>>> chr(108)
'l'
>>> bin(ord('€'))[2:]
'10000010101100'
>>> len(bin(ord('€'))[2:])
14
>>>

Prouver un algorithme

On devait pour aujourd’hui implémenter l’algorithme de recherche dichotomique sur un tableau trié :

def recherche_dichotomique(tab, val):
    """ Recherche val dans un tableau tab
        tab est supposé trié """

    # initialisation
    gauche = 0
    droite = len(tab) - 1
    
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == val:
            # on a trouvé val dans le tableau,
            # à la position milieu
            return milieu
        elif tab[milieu] > val:
            # on cherche entre gauche et milieu - 1
            droite = milieu - 1
        else:             # on a tab[milieu] < val
            # on cherche entre milieu + 1 et droite
            gauche = milieu + 1

    # on est sorti de la boucle sans trouver val
    return -1


#tests

liste = [1, 3, 5, 7, 9]
print(liste)
for truc in [0, 42, 5 , 3, 7, 2, 8, 9, 1, -52]:
    print("Pour", truc, "on obtient",
          recherche_dichotomique(liste, truc))
[1, 3, 5, 7, 9]
Pour 0 on obtient -1
Pour 42 on obtient -1
Pour 5 on obtient 2
Pour 3 on obtient 1
Pour 7 on obtient 3
Pour 2 on obtient -1
Pour 8 on obtient -1
Pour 9 on obtient 4
Pour 1 on obtient 0
Pour -52 on obtient -1
>>>

C’est sans difficulté, puisqu’on vous avait donné ce document institutionnel (à comprendre jusqu’au milieu de la troisième page) et que ce code figurait au milieu de la deuxième page.


Prouver un algorithme – en deux temps (à savoir) :

  • Il faut prouver qu’il se termine : On parle de terminaison.

    On utilise ici un variant de boucle, en général

    • soit une variable qui augmente et ne peut pas dépasser un « plafond »
    • soit une variable qui diminue et ne peut pas passer sous un « plancher »
  • Il faut prouver qu’il fait bien ce que l’on attend de lui : On parle de correction.

    Pour cela, on va chercher un un invariant de boucle.

    C’est quoi un « invariant de boucle ? »

    C’est une propriété qui est vérifiée avant l’entrée dans la boucle,
    qui est vérifiée à chaque itération de la boucle et qui amène au résultat escompté à la sortie de la boucle.


Exemple facile pour commencer

Soit l’algorithme

def deux_puissance(n):

    assert n >=0

    #initialisation
    i = 0
    reponse = 1
    
    # traitement :
    while i < n : 
        i += 1
        reponse *= 2

    # terminé :
    return reponse

# tests
assert deux_puissance(0) == 1
assert deux_puissance(1) == 2
assert deux_puissance(2) == 4
assert deux_puissance(8) == 256

Cette fonction passe sans encombres les tests caractérisés par

  • les quatre assert en fin de code qui testent quatre valeurs de retour,
  • le assert en début de fonction qui teste les préconditions « n positif ou nul ».

Mais nous voulons prouver cet algorithme !

  • Terminaison :

    Le variant de boucle est clairement ici i qui augmente forcément avec l’incrémentation i += 1 dans la boucle while. Quand i atteint n, qui est forcément positif ou nul, l’algorithme termine. La terminaison est donc assurée.

  • Correction :

    On veut que le programme renvoie 2 ** n quel que soit n positif ou nul.
    L’invariant de boucle est par exemple ici la propriété

    « reponse vaut 2 ** i »

    • Avant la boucle, i vaut zéro et reponse vaut 1 soit 2 ** 0. OK
    • Si l’invariant « reponse vaut 2 ** i » est vraie à la fin d’un passage de la boucle, au passage suivant
      • i passera à i + 1
      • reponse vaudra reponse * 2 soit 2 ** i * 2 soit 2 ** (i +1). OK
    • Au sortir de la boucle, l’invariant est donc encore respecté et la dernière valeur de i est n donc « reponse vaut 2 ** n » et c’est bien la bonne valeur qu’on renvoie.
    • La correction est donc assurée.

Prouver notre algorithme de dichotomie

On s’appuie sur ce document institutionnel où il est prouvé.

Commentaires.


Et nos tris ?

Et bien pour les deux tris par sélection ou par insertion étudiés :

  • Un variant de boucle est rang initialisée à zéro puis incrémentée et qui ne dépassera pas len(tab). Ceci prouve la terminaison.
  • Un invariant de boucle est

    « les éléments sont triés jusqu’à rang »

    Souvenons-nous que nous l’avions bien souligné (et même encadré en vert). Ceci permet de prouver la correction.

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) :