Information, représentation des données

On y a parlé d’écriture

  • binaire des nombres entiers non signés,
  • hexadécimale de mêmes nombres entiers non signés,
  • fait un rappel sur les pixels et la notation html des couleurs :cm 2020-02-06 ISN code couleur d7d03d
  • abordé ensuite des algorithmes de conversion du décimal au binaire :
    • comme on le fait « à la main »,
    • par divisions successives par deux,
  • expliqué l’encodage des entiers signés.

Tout est dans les tableaux ci-dessous :

Coder le deuxième algorithme de conversion vers le binaire donné pendant ce cours, par divisions successives par deux, celui du cinquième tableau au début de la troisième page, pour la rentrée.

Bonnes vacances !

TP improvisé : pile ou file ?

Mini-projets et site web les présentant :

Une collecte a été mise en place pour les rendus sur l’espace numérique de travail (MBN) du lycée.

Exposé du jour :

Septième et dernier exposé de notre cycle par Alex & Tom :

Parcours des graphes et application aux labyrinthes, pile et file

TP improvisé – application de la pile

Il y a huit présents pour sept absents (JU…) ! Plutôt que de péter une pile, on en a utilisé une…

On s’appuie sur le TP des premières NSI de ce mercredi pour, en deux étapes :

  • implémenter les déplacements clavier, dans une boucle while continuer : « perpétuelle » où continuer est initialisée à True et on attend des événements (clavier, souris) pour des actions ou quitter la boucle en passant continuer à False.
  • tout changer, CHANGER DE PARADIGME : passer à un algorithme itératif en utilisant notre nouvelle structure de données, la pile :

cm 2020-01-30 ISN changement de paradigme pour parcous

À droite l’algorithme suivi, par exemple par Corentin « B. de B. », qui a obtenu ceci :

cm 2020-01-31 tp4_parcours profondeur B de B

C’est un parcours en profondeur, « à gauche d’abord » (du point de vue du personnage) ! On a utilisé une pile,

  • initialisé la pile avec pile = []
  • empilé avec pile.append((x, y))
  • dépilé avec x, y = pile.pop()

En changeant cette dernière commande en lui ajoutant un paramètre, on obtient une file,

  • initialisé la file avec file = []
  • emfilé avec file.append((x, y))
  • dépilé avec x, y = file.pop(0)

Et au niveau du parcours, ça change tout : on a un parcours en largeur :

cm 2020-01-31 tp4_parcours largeur B de B

« Serais-je capable de répondre à cette question lors de l’examen ? »

Je vous conseille la lecture ce cet article scientifique pour préparer vos épreuves à venir et autres examens :

Examens : pour bien réviser, testez-vous !

On y lit en particulier :

« Prenons l’exemple d’un cours ou d’une matière dont on sait qu’il ou elle fera l’objet d’un contrôle de connaissance en fin de semestre ou trimestre, comme c’est le cas lors des examens à l’université ou des épreuves du baccalauréat ou du brevet.

  1. Au fur et à mesure des séquences d’enseignement, nous vous conseillons de vous créer, non pas des fiches de révision, mais des fiches de questions ou « tests » que vous pourrez utiliser lors de votre prochaine séance d’apprentissage.
  2. Ensuite, nous vous conseillons de faire autre chose pendant un moment (pause, travail sur une autre matière…). En effet, le délai est nécessaire pour que l’information soit stockée en « mémoire à long terme ».
  3. Puis, vous allez reprendre les questions créées dans la phase 1 et tout simplement essayer d’y répondre en faisant un véritable effort de récupération en mémoire.
  4. Enfin, vous pourrez reprendre le cours et les réponses données aux questions afin d’en faire une correction. Cette ultime étape permet d’étendre encore le bénéfice du test sur l’apprentissage.

Ce même processus peut être répété pour chaque cours ou leçon. Se tester ne prend donc pas plus de temps que de faire des fiches ou relire son cours. Pourtant, c’est une stratégie beaucoup plus efficace ! »

Bonne semaine !

Trions pour l’avenir …

… ou pour une meilleure algorithmique !

Tout le monde doit avoir programmé les tris :

  • par sélection,
  • par insertion,
  • à bulles,

en se basant sur le canevas de la semaine dernière.

On commence par corriger ensemble le tri par sélection que beaucoup avaient fini la semaine dernière et dont on avait proposé un pseudo-code :

from random import randint
 
liste=[]
for i in range(8):
    liste.append(randint(1,101))
 
print(liste)

# tri par sélection du minimum

for i_depart in range(0,7):
    # initialisation
    i_min = i_depart

    # recherche du minimum
    for i in range(i_depart + 1, 8):
        if liste[i] < liste[i_min]:
            i_min = i

    # interversion
    liste[i_depart], liste[i_min] = liste[i_min], liste[i_depart]
    print(liste)

qui donne par exemple :

[62, 84, 15, 52, 58, 35, 56, 7]
[7, 84, 15, 52, 58, 35, 56, 62]
[7, 15, 84, 52, 58, 35, 56, 62]
[7, 15, 35, 52, 58, 84, 56, 62]
[7, 15, 35, 52, 58, 84, 56, 62]
[7, 15, 35, 52, 56, 84, 58, 62]
[7, 15, 35, 52, 56, 58, 84, 62]
[7, 15, 35, 52, 56, 58, 62, 84]
>>> 

Romain (bravo !) propose cette comparaison graphique du temps d’exécution des tris :

TR - 2020_01_15 - Temps de traitement, Algorithmique .jpg

L’image ci-dessus a été obtenue (par Romain) avec des listes de tailles n allant de 1 à 450 et on a trié ces listes avec chacun des algorithmes et chronométré le temps en secondes. Repère :

  • de 1 à 450 pour la taille de la liste triée en abscisses,
  • de zéro à 0,5 secondes en ordonnées.

J’ai utilisé ses codes pour générer l’animation ci-dessous.

TR - 2020_01_15 - Temps de traitement Algorithmique

Repère :

  • de 1 à 150 pour la taille de la liste triée en abscisses,
  • de zéro à 0,3 secondes en ordonnées.

Fini ? Déjà fait ? Alors on continue le …

Travail sur les mini-projets et le site web qui les présente.

Algorithmes de tri

Exposé du jour :

Cinquième exposé de notre cycle par Léa, Zoé P. & Noé.

Algorithme de tri par sélection, par insertion, par bulles, par fusion, comparaison

Des élèves trient ensuite au tableau « à la main » avec l’aide des exposant.e.s :

cm 2020-01-09 ISN algorithmes de tri

TP : algorithmes de tris

On considère le code suivant :

from random import randint

liste=[]
for i in range(8):
    liste.append(randint(1,101))

print(liste)

Il génère et affiche une liste de huit nombres pseudo-aléatoires entre 1 et 100.

[55, 99, 66, 11, 59, 14, 84, 15]

Le compléter pour qu’il réalise les trois tris suivants :

Tri par sélection : les étapes
[11, 99, 66, 55, 59, 14, 84, 15]
[11, 14, 66, 55, 59, 99, 84, 15]
[11, 14, 15, 55, 59, 99, 84, 66]
[11, 14, 15, 55, 59, 99, 84, 66]
[11, 14, 15, 55, 59, 99, 84, 66]
[11, 14, 15, 55, 59, 66, 84, 99]
[11, 14, 15, 55, 59, 66, 84, 99]

Tri par insertion : les étapes
[55, 99, 66, 11, 59, 14, 84, 15]
[55, 66, 99, 11, 59, 14, 84, 15]
[11, 55, 66, 99, 59, 14, 84, 15]
[11, 55, 59, 66, 99, 14, 84, 15]
[11, 14, 55, 59, 66, 99, 84, 15]
[11, 14, 55, 59, 66, 84, 99, 15]
[11, 14, 15, 55, 59, 66, 84, 99]

Tri par bulles : les étapes
[55, 66, 11, 59, 14, 84, 15, 99]
[55, 11, 59, 14, 66, 15, 84, 99]
[11, 55, 14, 59, 15, 66, 84, 99]
[11, 14, 55, 15, 59, 66, 84, 99]
[11, 14, 15, 55, 59, 66, 84, 99]
[11, 14, 15, 55, 59, 66, 84, 99]
>>>

Pseudo-code présenté en classe pour le tri par sélection :

cm 2020-01-09 ISN algorithmes de tri pseudo-code sélection

On n’a pas terminé – ceci fera l’objet d’une évaluation on reprendra la semaine prochaine.

Pour s’y préparer, de tels pseudo-codes se trouvent sur les pages wikipedia des tris en question.

Par ailleurs, ceci est une très belle explication à mon sens :

Les exposés à venir sont décalés d’une semaine.