Classe : Terminale
Spécialité : Numérique et Sciences Informatiques
Professeur : M. MICHEL
Année scolaire : 2024 / 2025

 

nsi.gecif.net

Rappel du règlement et des objectifs pour lesquels on vient en classe

Rappel des horaires des séances de la spécialité Numérique et Sciences Informatiques en terminale (6 H par semaine) :

Les retards étant interdits en application du règlement intérieur, il faut être présent dans le hall du bâtiment F aux horaires de début de séance indiqués en rouge ci-dessus.

Pour les séances de N.S.I. il faut venir en classe :

Travail à faire systématiquement à la maison :

Le classeur de N.S.I. est structuré en 5 intercalaires :

Sur tous les documents présents dans le classeur, l'intercalaire et la date doivent être inscrites dès la distribution de la photocopie. Dans chaque intercalaire les documents sont rangés par ordre chronologique en utilisant l'information "date".

En cas d'absence à une évaluation, un zéro provisoire est inscrit sur Pronote jusqu'à ce que l'élève rattrape l'évaluation en classe.

 

Contenu du cahier de texte

Le cahier de texte ci-dessous rappelle, pour chacune des séances de N.S.I., le travail qui a été fait en classe. Il permet également de connaître pour chaque document distribué en classe sa date et son intercalaire (inscrite entre parenthèses ci-dessous) afin de le ranger dans le classeur.

Pour accéder à une séance précise saisissez une date :

  Aller directement à la séance choisie

DateTravail fait en classe durant cette séance
vendredi 6 septembre 2024Pas cours de NSI
lundi 9 septembre 2024- accueil des élèves et rappel des horaires en terminale
- précisions sur le programme et l’organisation de l’année de terminale
- Partie DECOUVERTE de l'accès aux fichiers en Python
mardi 10 septembre 2024- Cours "Accès aux fichiers en Python" (L)
- précisions sur certaines fonctions ou méthodes Python relatives à l'accès aux fichiers :

open() read() readlines() write() seek() tell() close() getcwd() chdir()

- fin de la partie DECOUVERTE de l'accès aux fichiers en Python
- début de la partie APPLICATION de l'accès aux fichiers en Python
vendredi 13 septembre 2024Précisions sur le BOM, caractère unicode de point de code U+FEFF enregistré sur 3 octets au début d’un fichier UTF-8 et servant de marqueur pour confirmer l’encodage du fichier.

Partie APPLICATION de l'accès aux fichiers en Python

Application 5 : lecture d'un fichier texte
lundi 16 septembre 2024Partie APPLICATION de l'accès aux fichiers en Python

Application 6 : écriture d'un fichier texte
mardi 17 septembre 2024Évaluation sur tous les thèmes du QCM transversal de N.S.I. de fin de première :

- Nombre de thèmes : 18
- Nombre de questions : 200
- Temps maximal : 2 heures
- Documents et logiciels interdits
- Brouillon et calculatrice autorisés

Travail au choix dans le temps restant :
- suite des applications sur les fichiers
- possibilité de gagner 1 point de bonus toutes les 20 questions consécutives justes sur tous les thèmes de la version "STOP à la première erreur" du QCM transversal de N.S.I. de fin de première
vendredi 20 septembre 2024Fin de la partie APPLICATION de l'accès aux fichiers en Python

Application 7 : traitement d'un fichier CSV

Notions abordées dans cette application :
- organisation des données en table
- enregistrement des données dans un fichier au format CSV (Comma-Separated Values)

Les applications non finies en classe sont à finir à la maison.
lundi 23 septembre 2024COURS (D) : "Les structures de données linéaires"

Entraînement sur le QCM "Les structures de données"

Découverte du thème "Les structures linéaires" (25 questions)

Objectif à atteindre : 50 questions consécutives sans aucune erreur en utilisant la version « STOP à la première erreur » du QCM

En cas d'erreur on recommence à zéro la série de 50 questions jusqu'à atteindre l'objectif de travail demandé. Si l'objectif de travail n'est pas atteint en classe il est à finir à la maison.
mardi 24 septembre 2024COURS (D) : "Les graphes"

Entraînement sur le thème "Les graphes" du QCM "Les structures de données"

Objectif à atteindre : 50 questions consécutives sans aucune erreur en utilisant la version « STOP à la première erreur » du QCM

En cas d'erreur on recommence à zéro la série de 50 questions jusqu'à atteindre l'objectif de travail demandé. Si l'objectif de travail n'est pas atteint en classe il est à finir à la maison.
vendredi 27 septembre 2024COURS (D) : "Les arbres" (pages 1 à 3)

Entraînement sur les 2 thèmes suivants du QCM "Les structures de données" :
- Les arbres
- Qu’ai-je retenu de tous mes cours

Objectif à atteindre : 50 questions consécutives sans aucune erreur en utilisant la version « STOP à la première erreur » du QCM

En cas d'erreur on recommence à zéro la série de 50 questions jusqu'à atteindre l'objectif de travail demandé. Si l'objectif de travail n'est pas atteint en classe il est à finir à la maison.
lundi 30 septembre 2024Fin du COURS (D) : "Les arbres" (page 4)
- Parcours d'un arbre
- Les arbres binaires de recherche

Entraînement sur les 3 thèmes suivants du QCM "Les structures de données" :
- Les arbres
- Les arbres binaires de recherche
- Parcours d'un arbre

Objectif à atteindre : 50 questions consécutives sans aucune erreur en utilisant la version « STOP à la première erreur » du QCM

En cas d'erreur on recommence à zéro la série de 50 questions jusqu'à atteindre l'objectif de travail demandé. Si l'objectif de travail n'est pas atteint en classe il est à finir à la maison.
mardi 1 octobre 2024Définitions affinées concernant les arbres :
- définition du nœud racine
- définition des nœuds internes
- définition des feuilles

Précisions sur :
- l’arbre nul (le seul arbre possédant aucun nœud et de hauteur 0)
- l’arbre unitaire (le seul arbre possédant un seul nœud et de hauteur 1)
- l'algorithme de parcours d'un arbre en largeur utilise une file
- l'algorithme de parcours d'un arbre en profondeur utilise une pile

Entraînement sur tous les thèmes du QCM "Les structures de données" avec validation des points bonus.

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant tous les thèmes de la version « STOP à la première erreur » du QCM selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points
vendredi 4 octobre 2024Entraînement sur tous les thèmes du QCM "Les structures de données" avec validation des points bonus.

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant tous les thèmes de la version « STOP à la première erreur » du QCM durant les séances d'entraînement en classe selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points

Ceux qui ont atteint au moins 40 questions consécutives sans erreur (et qui n'ont donc plus de malus) ont le choix entre deux activités à réaliser :

- soit poursuivre l'entraînement sur tous les thèmes du QCM "Les structures de données" afin de gagner des points bonus (objectif à atteindre : répondre à plus de 60 questions consécutives sans erreur)
- soit commencer l'Application 6 du module Turtle de Python : le tracé d'un graphe décrit par sa matrice d'adjacence
lundi 7 octobre 2024Remarques sur les structures de données :

- rappel sur les graphes simples et orienté
- la racine du SAG = le fils gauche
- la racine du SAD = le fils droit
- un nœud N qui n'a pas de fils = une feuille
- un nœud N dont le SAG et le SAD sont des arbres nuls = une feuille
- un nœud N dont le SAG et le SAD sont des arbres de hauteur 0 = une feuille
- un nœud N dont le SAG et le SAD sont des arbres de hauteur 1 = le père d'une feuille
- un nœud N dont le SAG et le SAD sont des arbres de hauteur 2 = le grand-père d'une feuille
- racine du SAG = fils gauche donc Fils de la racine du SAG = petit-fils gauche
- termes anglais liés aux structures de données :
un tableau : array
une pile : stack
une file : queue
le sommet : peek
empiler : push
dépiler : pop
enfiler : enqueue
défiler : dequeue
- Structure Linéaire ou non linéaire : Lorsque les éléments sont ordonnés (liste) on
parle de structure linéaire. Un dictionnaire est une structure non linéaire.
- Structure homogène ou non : Les éléments sont tous du même type ou non. En Python
on peut mettre n’importe quel type dans des listes, donc la structure sera non
homogène.
- Structure Statique ou Dynamique : La taille est fixée et ne peut être modifiée en
fonction des besoins. Une liste est une structure dynamique, mais un tuple est une structure statique.

Entraînement sur tous les thèmes du QCM "Les structures de données" avec validation des points bonus.

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant tous les thèmes de la version « STOP à la première erreur » du QCM durant les séances d'entraînement en classe selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points

Ceux qui ont atteint au moins 40 questions consécutives sans erreur (et qui n'ont donc plus de malus) ont le choix entre deux activités à réaliser :

- soit poursuivre l'entraînement sur tous les thèmes du QCM "Les structures de données" afin de gagner des points bonus (objectif à atteindre : répondre à plus de 60 questions consécutives sans erreur)
- soit poursuivre l'Application 6 du module Turtle de Python : le tracé d'un graphe décrit par sa matrice d'adjacence
mardi 8 octobre 2024Remarques sur les arbres binaires de recherche (ABR) :

- si un nœud possède ses 2 fils (racine ou nœud interne) alors sa valeur est comprise entre ses 2 fils
- si un nœud interne possède un seul fils alors il faut consulter l’arbre vers ses ascendants pour connaître son intervalle de valeur
- si un nœud possède aucun fils (c'est donc une feuille) alors il faut consulter l’arbre vers ses ascendants pour connaître son intervalle de valeur
- si on ajoute une nouvelle valeur dans l’ABR c’est forcément une feuille
- si les valeurs entrées dans l’ABR sont déjà triées (ex : dans l’ordre croissant) alors on obtient un arbre binaire dégénéré

Entraînement sur tous les thèmes du QCM "Les structures de données" avec validation des points bonus.

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant tous les thèmes de la version « STOP à la première erreur » du QCM durant les séances d'entraînement en classe selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points

Ceux qui ont atteint au moins 40 questions consécutives sans erreur (et qui n'ont donc plus de malus) ont le choix entre deux activités à réaliser :

- soit poursuivre l'entraînement sur tous les thèmes du QCM "Les structures de données" afin de gagner des points bonus (objectif à atteindre : répondre à plus de 60 questions consécutives sans erreur)
- soit poursuivre l'Application 6 du module Turtle de Python : le tracé d'un graphe décrit par sa matrice d'adjacence
vendredi 11 octobre 2024Évaluation sur tous les thèmes du QCM "Les structures de données" :

- Nombre de thèmes : 6
- Nombre de questions : 150
- Temps maximal : 2 heures
- Documents, logiciels et calculatrice interdits
- Brouillon autorisé

Travail au choix dans le temps restant :
- suite du programme en Python pour tracer un graphe avec le module Turtle (seulement pour ceux qui n'ont plus de malus)
- validation définitive des points bonus avec les 6 thèmes du QCM "Les structures de données"

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant tous les thèmes de la version « STOP à la première erreur » du QCM selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points

Exemples de sujets de bac à voir : les exercices 1 des sujets 3, 10, 11 et 14 de l'épreuve écrite de NSI de 2022
lundi 14 octobre 2024Implémentation des arbres en Python sans utiliser la programmation orienté objet

TP1 Les arbres binaires en Python : représentation avec matplotlib, ABR, codage de Huffman

- définition récursive des arbres binaires
- implémentation d'un nœud avec un tuple (racine,fils gauche,fils droit)
- l’arbre vide est représenté par None
- codage d'un arbre binaire avec des tuples de tuples
- par exemple : arbre=(2,(1,(0,None,None),None),(5,(4,(3,None,None),None),(12,(9,(8,(6,None,(7,None,None)),None),(10,None,(11,None,None))),(13,None,(14,None,(18,(17,(15,None,(16,None,None)),None),(19,None,None)))))))
- affichage du nombre de nœuds, du nombre de feuilles, de la liste de feuilles et de la hauteur de l'arbre binaire
- tracé graphique de l'arbre binaire en utilisant la bibliothèque matplotlib
mardi 15 octobre 2024Suite du TP1 Les arbres binaires en Python : représentation avec matplotlib, ABR, codage de Huffman

- implémentation d'un arbre binaire de recherche (ABR) avec des tuples de tuples
- recherche récursive d'une valeur dans l'ABR
- recherche du minimum (on va à fond à gauche) et du maximum (on va à fond à droite) dans l'ABR
- modification de l'ABR : ajout et suppression d'une valeur
- génération d'un ABR aléatoire à partir d'une liste aléatoire
- implémentation des différents types de parcours d'un arbre
- le parcours en largeur (parcours niveau par niveau)
- distinction entre les 3 parcours en profondeur :
- le parcours préfixe : R,G,D
- le parcours infixe : G,R,D (donne une liste triée des nœuds de l’ABR)
- le parcours suffixe : G,D,R
- utilisation d'un ABR pour trier une liste aléatoire : on range la liste dans un ABR puis on donne son parcours infixe
vendredi 18 octobre 2024Fin du TP1 Les arbres binaires en Python : représentation avec matplotlib, ABR, codage de Huffman

- rappel de la création d'une liste par compréhension : [2*k for k in range(8)] donne [0, 2, 4, 6, 8, 10, 12, 14]
- codage d'un texte en binaire en utilisant les codes ASCII des caractères
- décodage d'un message binaire pour retrouver les codes ASCII
- notion de code-préfixe (aucun mot du code préfixe ne peut se prolonger pour donner un autre mot du code)
- codage de Huffman pour la compression de données : il génère pour chaque caractère un code-préfixe à taille variable
- utilisation d'un file de priorité (file auto-triée lors de l'ajout d'un élément) avec le module heapq de Python
- estimation du taux de compression obtenu avec le codage de Huffman par rapport au codage ASCII
Vacances de ToussaintTravail à faire pendant les vacances de Toussaint :

- réviser tout le chapitre sur les structures de données (cours, exemples, et TP Python)
- terminer l'Application 6 du module Turtle qui trace un graphe en fonction de sa matrice d'adjacence
- terminer le TP sur l’implémentation et l’utilisation des arbres binaires en Python
- exemples de sujets de bac à voir : les exercices 1 des sujets 3, 10, 11 et 14 de l'épreuve écrite de NSI de 2022
lundi 4 novembre 2024Introduction à la Programmation Orientée Objet (POO)

TP2 : Implémentation d'un arbre binaire en Python en utilisant la POO

Création d'une classe Arbre possédants les méthodes __init__(self, val), ajout_gauche(self, val), ajout_droit(self, val), taille(self) et hauteur(self)

Ajout d'une méthode vide(self) renvoyant True si l'arbre est vide

Création d'une fonction parcours_prefixe(arbre) externe à la classe Arbre affichant le parcours en profondeur préfixe de l'arbre passé en paramètre
mardi 5 novembre 2024Fin du TP2 : Implémentation d'un arbre binaire en Python en utilisant la POO

Création de 3 fonctions externes à la classe Arbre prenant en paramètre un objet "arbre" de classe Arbre et affichant chacune un parcours en profondeur sur une ligne dans la console :
- parcours_prefixe(arbre)
- parcours_infixe(arbre)
- parcours_suffixe(arbre)

Enrichissement de la classe Arbre en créant 3 nouvelles méthodes qui affichent chacune un parcours en profondeur de l'arbre lui-même sur une ligne dans la console :
- parcours_prefixe(self)
- parcours_infixe(self)
- parcours_suffixe(self)
vendredi 8 novembre 2024Correction du TP 2 : explication de la solution optimisée des 3 méthodes parcours_prefixe(self), parcours_infixe(self) et parcours_suffixe(self) de la classe Arbre.

TP3 : Implémentation des structures de données linéaires en Python en utilisant la POO

- rappel des bases de la POO : classes, attributs et méthodes
- rappel sur les structures de données (linéaire ou non linéaire, homogène ou non, statique ou dynamique)
- création, test et solution de la classe Perso
lundi 11 novembre 2024Armistice 1918
mardi 12 novembre 2024Suite du TP3 : Implémentation des structures de données linéaires en Python en utilisant la POO
- création d'un classe Tableau avec les méthodes insert et supprime (programme de base à compléter puis solution finale donnée)
vendredi 15 novembre 2024Distribution de la fiche pratique "Les listes en Python" récapitulant l'ensemble des syntaxes vues en première et utilisables avec les listes (opérateurs, tranchage, méthodes, fonctions externes, etc.).

Fin du TP3 : Implémentation des structures de données linéaires en Python en utilisant la POO :
- création d'un classe Pile (programme de base à compléter puis solution finale donnée)
- création d'un classe File (programme de base à compléter puis solution finale donnée)
- création d'un classe Maillon pour implémenter une liste chaînée (programme de base à compléter puis solution finale donnée)
lundi 18 novembre 2024Cours "Premiers pas en algorithmique" :
- pseudo code
- complexité temporelle et spatiale
- variant et invariant de boucle
- distinction entre un algorithme itératif et un algorithme récursif
- distinction entre un algorithme et un algorigramme

Application : comparaison de 2 implémentations en Python de la fonction factorielle :
- algorithme itératif
- algorithme récursif
- comparaison des complexités temporelle (mesure du temps d'exécution) et spatiale (limite du nombre d'appel récursif)

Découverte du thème "Analyse d'algorithmes" du QCM "Algorithmes et algorigrammes" en s'aidant d'une calculatrice programmable ou de Python pour les algorithmes itératifs

Travail à faire à la maison : s'entraîner sur le thème "Analyse d'algorithmes" du QCM "Algorithmes et algorigrammes" en s'aidant d'une calculatrice programmable ou de Python pour les algorithmes itératifs
mardi 19 novembre 2024COURS : Les algorithmes de compression
- compression RLE
- la codage de Huffman

Distribution de l'exemple "La codage de Huffman" donnant la solution pour coder le mot "anticonstitutionnellement"

Application : découverte du thème "Les algorithmes de compression" du QCM "Algorithmes et algorigrammes" avec prise de notes sur une nouvelle fiche "Les algorithmes de compression"

Objectif à atteindre : dépasser une note de 15/20 avec 50 questions

Application pratique du codage de Huffman page 16 du TP1 "Représentation des arbres binaires en Python (sans POO)"

Travail à faire à la maison : s'entraîner sur le thème "Les algorithmes de compression" du QCM "Algorithmes et algorigrammes"
vendredi 22 novembre 2024Expérimentation des 3 algorithmes de tri classiques avec des cartes :
- le tri par insertion
- le tri par sélection
- le tri à bulles

Explication et description de chacun des ces 3 algorithmes de tri.

Comparaison des 3 algorithmes de tri en terme de nombres de permutations dans le pire des cas en comptant le nombres d'échanges avec les cartes.

Application : découverte du thème "Les algorithmes de tri" du QCM "Algorithmes et algorigrammes" avec prise de notes au brouillon.
lundi 25 novembre 2024COURS : Les algorithmes de tri

- le tri par sélection
- le tri par insertion
- le tri à bulles
- le tri fusion

Illustration de la fusion de deux listes triées.

Création de 4 fiches pratiques vierges sur une copie double afin de prendre des notes concernant les différents thèmes lors de l'entraînement sur le QCM ou en cas de questions :
- Les algorithmes de compression
- Les algorithmes de tri
- Les algorithmes
- Les algorigrammes (NIVEAU 1 et NIVEAU 2)

Découverte des applications interactives illustrant les différents algorithmes de tri :
- le tri par insertion
- le tri par sélection
- le tri bulle
- le tri fusion

Découverte des 6 cartes virtuelles (complétant les 12 cartes en papier) pour simuler et analyser un algorithme de tri

Création sur la fiche "Les algorithmes de tri" du tableau donnant le nombre de comparaisons et de déplacements pour les tris par insertion, par sélection et à bulles dans différentes situations (pire des cas et meilleur des cas)

Recherche expérimentale des solutions pour remplir le tableau :
- utilisation des cartes pour simuler un algorithme de tri en particulier
- consultation du site avec les animations des tris
- prise de notes en utilisant le thème "Les algorithmes de tri" du QCM "Algorithmes et algorigrammes"

Entraînement sur le thème "Les algorithmes de tri" du QCM "Algorithmes et algorigrammes" avec prise de notes sur la fiche "Les algorithmes de tri"

Objectif à atteindre : dépasser une note de 15/20 avec 50 questions

Travail à faire à la maison : s'entraîner sur les 3 premiers thèmes du QCM "Algorithmes et algorigrammes"

Liste des 3 thèmes à travailler :
- Les algorithmes de compression
- Les algorithmes de tri
- Analyse d'algorithmes
mardi 26 novembre 2024Découverte des algorigrammes en utilisant la page d'aide du QCM "Algorithmes et algorigrammes" avec prise de notes sur une nouvelle fiche "Les algorigrammes" :
- allumage des LED avec un bloc sortie (puissances de 2)
- récupération de l'état des 8 interrupteurs dans un bloc entrée (binaire naturel)
- affectation d'une valeur à une variable dans un bloc calcul
- utilisation d'un bloc condition pour faire un test
- boucle x fois pour réaliser une itération
- boucle tant que avec le test en début ou en fin de boucle
- boucle jusqu'à avec le test en début ou en fin de boucle

Application : entraînement sur les thèmes "Analyse d'algorigrammes NIVEAU 1" et "Analyse d'algorigrammes NIVEAU 2" du QCM "Algorithmes et algorigrammes" recherche expérimentale pour certaines réponses et avec prise de notes sur la fiche "Les algorigrammes".

Objectif à atteindre : dépasser une note de 15/20 avec 50 questions en utilisant les 2 thèmes à la fois (après découverte séparée de chacun des thèmes).

Travail à faire à la maison : s'entraîner sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes" avec prise de notes sur les fiches pratiques.

Liste des 5 thèmes à travailler :
- Les algorithmes de compression
- Les algorithmes de tri
- Analyse d'algorithmes
- Analyse d'algorigrammes NIVEAU 1
- Analyse d'algorigrammes NIVEAU 2
vendredi 29 novembre 2024Précisions sur les 3 points suivants :

- recherche dichotomique dans un tableau trié
- possibilités d'amélioration du tri à bulles : tri à peigne et bidirectionnalité
- niveau de complexité d'un algorithme

Mesure et notation de la complexité de différents algorithmes :

- taille d'un tableau : O(1)
- recherche linéaire dans un tableau non trié : O(n)
- tri par sélection, tri par insertion et tri à bulles : O(n²)
- recherche dichotomique dans un tableau trié : O(log(n))
- tri fusion : O(n.log(n))

Test et comparaison de la complexité temporelle de différents algorithmes de tri en Python :

- le tri par sélection
- le tri par insertion
- le tri à bulles
- le tri à peigne
- le tri fusion
- tri rapide
- tri natif dans les méthodes des listes de Python
- tri par extraction du parcourt en profondeur dans l'ordre infixe d'un arbre binaire de recherche

Travail à faire à la maison : s'entraîner sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes" avec prise de notes sur les fiches pratiques

Objectif à atteindre : dépasser le seuil des 40 questions consécutives sans erreur en utilisant les 5 premiers thèmes sur la version STOP à la première erreur du QCM "Algorithmes et algorigrammes"

Liste des 5 thèmes à travailler :
- Les algorithmes de compression
- Les algorithmes de tri
- Analyse d'algorithmes
- Analyse d'algorigrammes NIVEAU 1
- Analyse d'algorigrammes NIVEAU 2
lundi 2 décembre 2024Présentation de la version 2 du programme en Python qui compare 14 algorithmes de tri permettant d'estimer leur complexité temporelle :
- tri par sélection
- tri par insertion
- tri à bulles
- tri à bulles bidirectionnel (tri "shaker", ou tri "Cocktail", ou tri "Shuttle")
- tri à peigne
- tri à peigne bidirectionnel (tri "oyelami" : mélange de tri à peigne et tri shaker)
- tri shell (une variante du tri par insertion : on trie séparément des sous-suites)
- tri gnome (tri par insertion avec des permutations comme dans le tri à bulles)
- tri fusion (diviser pour mieux régner)
- tri rapide (utilise un pivot)
- tri avec la fonction sorted() de Python
- tri natif avec la méthode sort() des listes de Python
- tri par extraction du parcourt en profondeur dans l'ordre infixe d'un arbre binaire de recherche
- tri maximier ou "tri par tas" (création d'un arbre binaire dont le parcourt en largeur donne les noeuds dans l'ordre croissant)

Entraînement sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes" avec validation des points bonus.

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant les 5 premiers thèmes de la version « STOP à la première erreur » du QCM durant les séances d'entraînement en classe selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points

Liste des 5 thèmes :
- Les algorithmes de compression
- Les algorithmes de tri
- Analyse d'algorithmes
- Analyse d'algorigrammes NIVEAU 1
- Analyse d'algorigrammes NIVEAU 2

Travail à faire à la maison :
- continuer l'entraînement sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes". Objectifs à atteindre : dépasser 40 questions consécutives sans erreur, puis dépasser une notre de 15/20 avec 150 questions
- tester la version 2 du programme en Python permettant de comparer 14 algorithmes de tri et les classer par performance
mardi 3 décembre 2024Pas cours de N.S.I.
vendredi 6 décembre 2024Conclusion et classement des algorithmes de tri en fonction de leur complexité temporelle tous en O(n.log(n)) :

1 : algorithme Timsort (utilisé par Python)
2 : tri rapide
3 : tri fusion
4 : tri à peigne
5 : tri par tas
6 : tri par ABR
7 : tri Shell

Loin derrière, les 6 autres en O(n²) :

shaker, Oyelami, Gnome, bulles, insertion et sélection

Explication détaillée des 7 algorithmes itératifs 1, 2, 3, 11, 12, 13 et 15 du thème "Analyse d'algorithmes" du QCM "Algorithmes et algorigrammes" afin d'en déduire rapidement le résultat avec une simple calculatrice collège ou de tête, et sans devoir les programmer.

Travail à faire à la maison :
- mettre au propre les 4 fiches relatives aux algorithmes (compression, tri, algortihmes et algorigrammes)
- continuer l'entraînement sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes". Objectifs à atteindre : dépasser 40 questions consécutives sans erreur, puis dépasser une notre de 15/20 avec 150 questions
lundi 9 décembre 2024Validation des points bonus sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes".

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant les 5 premiers thèmes de la version « STOP à la première erreur » du QCM durant les séances d'entraînement en classe selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points

Liste des 5 thèmes :
- Les algorithmes de compression
- Les algorithmes de tri
- Analyse d'algorithmes
- Analyse d'algorigrammes NIVEAU 1
- Analyse d'algorigrammes NIVEAU 2
mardi 10 décembre 2024Pas cours de N.S.I.
vendredi 13 décembre 2024Évaluation sur les 5 premiers thèmes du QCM "Algorithmes et algorigrammes" :

- Nombre de thèmes : 5
- Nombre de questions : 150 (30 questions par thème en moyenne)
- Temps maximal : 2 heures
- Documents et logiciels interdits
- Brouillon et calculatrice autorisés

Liste des 5 thèmes :
- Les algorithmes de compression
- Les algorithmes de tri
- Analyse d'algorithmes
- Analyse d'algorigrammes NIVEAU 1
- Analyse d'algorigrammes NIVEAU 2

Dans le temps restant, validation définitive des points bonus avec les 5 premiers thèmes du QCM "Algorithmes et algorigrammes"

Les points bonus sont élaborés en fonction du nombre maximal de bonnes réponses consécutives atteint en utilisant les 5 premiers thèmes de la version « STOP à la première erreur » du QCM selon le barème suivant (tous documents autorisés) :
- moins de 20 réponses consécutives justes : -2 points
- entre 20 et 39 réponses consécutives justes : -1 point
- entre 40 et 59 réponses consécutives justes : 0 point
- entre 60 et 79 réponses consécutives justes : +1 point
- 80 réponses consécutives justes ou plus : +2 points
lundi 16 décembre 2024Découverte des autres types d'algorithmes :
- l'algorithme par force brute
- l'algorithme glouton

COURS "Les algorithmes gloutons" :
- le rendu de monnaie
- problème du sac à dos

Pour le problème du sac à dos, comparaison des performances de l'algorithme glouton en choisissant soit la meilleure valeur, soit la meilleure valeur massique à chaque étape pour différentes données du problème.

TP "Le problème du sac à dos"

Programmation des algorithmes gloutons en Python.

Comparaison avec l'algorithme par force brute pour le problème du sac à dos.
mardi 17 décembre 2024Exemple d'utilisation de l'algorithme par force brute : recherche d’un mot de passe inconnu ou d'un carré magique en utilisant la fonction permutations(P,n) du module itertools de Python

Fin du TP "Le problème du sac à dos" pour résoudre le problème des 7 vidéos :
- les 3 solutions gloutonnes ne donne pas la solution optimale
- seule la recherche par force brute donne la solution optimale
- en utilisant la fonction permutations(P,n) du module itertools l'implémentation de la force brute est simple
vendredi 20 décembre 2024Les solutions finales des problèmes suivants sont disponibles sur nsi.gecif.net :
- le problème des 7 vidéos par force brute
- la recherche d'un carré magique par force brute

Découverte d'autres types de problèmes à résoudre : des problèmes avec contraintes.

Exercice "Exemples de problèmes logiques".

Travail à faire :
1 - résoudre ces problèmes de tête sur la papier : réflexion et intelligence humaine
2 - quel algorithme permettrait de résoudre automatiquement ces problèmes ?
3 - comment Python peut-il solutionner ces problèmes ? (intelligence artificielle ?)

Découverte de la nouvelle page "Implémentation en Python de la force brute"
Vacances de NoëlTravail à faire pendant les vacances de Noël :

Ranger le classeur et se remémorer son contenu depuis de début de l'année.

Relire l'intégralité du cahier de texte depuis le début de l'année, s'auto-évaluer sur tous les savoir-faire acquis, et réviser, rattraper ou refaire éventuellement les activités concernant des connaissances oubliées (cours, TP, QCM, pratique de Python, Programmation Orientée Objet, etc.).

Objectif : revenir en janvier en ayant en tête tous les éléments du programme vus dans les différentes activités réalisées depuis le début de l'année et rappelés dans le cahier de texte.

Expérimenter les différents programmes en Python donnés sur la nouvelle page "Implémentation en Python de la force brute".
lundi 6 janvier 2025Utilisation de la nouvelle page "Implémentation en Python de la force brute"

Résolution du problème "Qui a le zèbre ?" par force brute en Python.

Comparaison pour les 5 problèmes de logiques des solutions données par Python avec les solutions trouvées sur le papier.

Implémentation en Python de l'algorithme par force brute pour résoudre de nouveaux problèmes logiques.

Choix de l'ordre des conditions dans le programme pour diminuer la complexité temporelle.
mardi 7 janvier 2025Résolution du problème "Qui a le zèbre ?" par force brute en Python en optimisant le programme pour diminuer la complexité temporelle :
- choix de l'ordre des conditions dans le programme
- préremplissage de 3 ou 5 cases dans le tableau à analyser

Quelles sont les 5 cases (1 case par ligne) les plus simples à trouver d'après l'énoncé du problème ?
- une nationalité
- une couleur
- une boisson
- une profession
- un animal

Si Python doit tester toutes les cases d'un tableau vide il teste 120**5=24 milliards de tableaux en 120 heures environ (5 jour).

Si on fournit 5 cases préremplies à Python (1 case par ligne) il teste 24**5=7 millions de tableaux en 3 minutes environ : en divisant le nombre de tableaux par 3000 on a divisé la complexité temporelle par 3000.

Solution définitive du problème "Qui a le zèbre ?" par force brute en Python en 3 versions :
- version 1 lente : teste 24 milliards de tableaux en 120 heures environ
- version 2 moyenne : teste 200 millions de tableaux en 1 heure environ (en remplissant 3 cases)
- version 3 rapide : teste 7 millions de tableaux en 3 minutes environ (en remplissant 5 cases)

Application avec les autres problèmes logiques similaires au zèbre : "Où est le kangourou ?", ainsi que les problèmes n°1 à n°6 et n°9

Comparaison des résultats obtenus par Python avec les solutions trouvées par une intelligence artificielle.
vendredi 10 janvier 2025Introduction aux bases de données relationnelles.

Découverte du langage SQL en testant des requêtes de recherche en ligne sur le site fxjollois.github.io/cours-sql : Requêtage simple

Distribution de la fiche pratique "Le langage SQL"

Test puis rédaction sur la fiche du rôle et de la syntaxe des mots clé SQL suivant :
- FROM
- SELECT
- ORDER BY
- WERE
- COUNT
- DISTINCT
- LIMIT
- etc.

Distribution du cours "BASES DE DONNÉES RELATIONNELLES ET SQL" à lire pour la prochaine séance.
lundi 13 janvier 2025
mardi 14 janvier 2025
vendredi 17 janvier 2025
lundi 20 janvier 2025
mardi 21 janvier 2025
vendredi 24 janvier 2025
lundi 27 janvier 2025
mardi 28 janvier 2025
vendredi 31 janvier 2025
lundi 3 février 2025
mardi 4 février 2025
vendredi 7 février 2025
lundi 10 février 2025Pas cours de NSI : semaine blanche
mardi 11 février 2025Pas cours de NSI : semaine blanche
vendredi 14 février 2025Pas cours de NSI : semaine blanche
Vacances d'Hiver
lundi 3 mars 2025
mardi 4 mars 2025
vendredi 7 mars 2025
lundi 10 mars 2025
mardi 11 mars 2025
vendredi 14 mars 2025
lundi 17 mars 2025
mardi 18 mars 2025
vendredi 21 mars 2025
lundi 24 mars 2025
mardi 25 mars 2025
vendredi 28 mars 2025
lundi 31 mars 2025
mardi 1 avril 2025
vendredi 4 avril 2025
lundi 7 avril 2025
mardi 8 avril 2025
vendredi 11 avril 2025
Vacances de Printemps
lundi 28 avril 2025
mardi 29 avril 2025
vendredi 2 mai 2025
lundi 5 mai 2025
mardi 6 mai 2025
vendredi 9 mai 2025
lundi 12 mai 2025
mardi 13 mai 2025
vendredi 16 mai 2025
lundi 19 mai 2025
mardi 20 mai 2025
vendredi 23 mai 2025
lundi 26 mai 2025
mardi 27 mai 2025
vendredi 30 mai 2025Pont de l'Ascension
lundi 2 juin 2025
mardi 3 juin 2025
vendredi 6 juin 2025
lundi 9 juin 2025Lundi de Pentecôte
mardi 10 juin 2025
vendredi 13 juin 2025
lundi 16 juin 2025
mardi 17 juin 2025
vendredi 20 juin 2025
lundi 23 juin 2025
mardi 24 juin 2025
vendredi 27 juin 2025
lundi 30 juin 2025

nsi.gecif.net

© Septembre 2024