Vidéo – Algorithmique, on suit la recette

Un jeune chasseur du néolithique apprend avec son père à fabriquer une hache à partir de bois, de silex et d’os. Tout doit être exécuté à la perfection, dans un ordre précis. Mais aujourd’hui, nous utilisons des machines qui travaillent à notre place en obéissant à un programme spécifique. Cet épisode revient sur les étapes qui ont permis à l’être humain de découvrir et maîtriser les algorithmes.

Des expériences réalisées avec des objets du quotidien, des petites histoires dans la grande, des paraboles : à travers une narration enlevée et des illustrations concrètes, cette série d’animation documentaire écrite par Pierre Lergenmüller (Points de repères) se propose de décrypter treize concepts épineux en les rendant accessibles à tous, y compris au jeune public et aux esprits hermétiques à la science.

 

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Comment visualiser l’algorithme de tri rapide ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri rapide

L’algorithme de tri rapide (ou Quick Sort Algorithm) est un algorithme de tri très efficace, basé sur le partitionnement d’un ensemble de données en plus petits tableaux. Un grand tableau est partitionné en deux tableaux, l’un contenant des valeurs inférieures à la valeur spécifiée, par exemple un pivot, sur la base de laquelle la partition est effectuée, et un autre tableau contenant des valeurs supérieures à la valeur du pivot.

L’algorithme de tri rapide partitionne un tableau et se fait appeler récursivement deux fois pour trier les deux sous-tableaux résultants. Cet algorithme est très efficace pour les ensembles de données de grande taille, car sa complexité moyenne et sa complexité dans le pire des cas sont respectivement O(nLogn) et O(n2).

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape de l’algorithme de tri rapide (ou Quick Sort Algorithm).

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Ecran couleur

La reconstitution des couleurs est basée sur la synthèse additive des couleurs. Les curseurs glissants permettent de régler les niveaux d’intensité pour chaque couleur (Rouge, Vert, Bleu).

Rouge, Vert et Bleu sont les trois couleurs primaires. Comme l’indique la simulation synthèse additive des couleurs, leur mélange permet de générer quatre autres couleurs: Le cyan (vert+bleu), le magenta (bleu + rouge), le jaune (rouge + vert) et le blanc (somme des trois). Depuis la fin du XIXe siècle, nous savons qu’il est possible de générer toutes les couleurs connues en jouant sur les intensités de ces couleurs primaires. Cela permet de générer toutes les couleurs de l’arc en ciel comme l’illustre cette autre simulation: RVB.

Faire glisser le  pour modifier l’intensité de la couleur correspondante.

 

Les écrans affichent des images couleurs à partir de ce principe de colorimétrie nommé trichromieC’est aussi de cette façon que notre oeil perçoit les couleurs.

Extrait du programme de SNT

Cet article peut être un élement de cours sur la photographie numérique du programme d’enseignement commun en seconde de SNTSciences numériques et technologie

Contenus Capacités attendues
Photosites, pixels, résolution (du capteur, de l’image), profondeur de couleur Distinguer les photosites du capteur et les pixels de l’image en comparant les résolutions du capteur et de l’image selon les réglages de l’appareil.
Métadonnées EXIF Retrouver les métadonnées d’une photographie.
Traitement d’image Traiter par programme une image pour la transformer en agissant
sur les trois composantes de ses pixels.
Rôle des algorithmes dans les appareils photo numériques Expliciter des algorithmes associés à la prise de vue.
Identifier les étapes de la construction de l’image finale.

Vous trouverez l’ensemble du programme en cliquant ici.

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

Nouveau livre de Terminale NSI – 2 /4

Spécialité Numérique et sciences informatiques : 24 leçons avec exercices corrigés – Terminale

 

Cet ouvrage propose un cours structuré couvrant l’intégralité du programme de la spécialité NSI en classe de terminale. Il offre vingt-quatre leçons clés en main, accompagnées d’exercices corrigés et d’encarts thématiques et historiques permettant d’approfondir les leçons.

Ce livre est constitué de quatre parties :

  • programmation
  • algorithmique
  • bases de données
  • architectures matérielles, systèmes d’exploitation et réseaux.

Le site qui accompagne cet ouvrage fournit du matériel librement téléchargeable, comme du code source Python, des fichiers de données pour les projets ou encore un aide-mémoire Python.

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

Comment visualiser l’algorithme de tri par insertion ?

Le tri est un problème très classique de réorganisation des données (qui peuvent être comparées, par exemple des nombres entiers, des nombres à virgule flottante, des chaînes de caractères, etc.) d’un tableau (ou d’une liste) dans un certain ordre (croissant, non décroissant, décroissant, non croissant, lexicographique, etc.)

Il existe de nombreux algorithmes de tri différents, chacun ayant ses propres avantages et limites.

Le tri par insertion

L’algorithme de tri par insertion (ou Insertion Sort Algorithm) considère la première valeur d’une liste comme une sous-liste triée (d’une seule valeur pour commencer). Cet algorithme itératif vérifie ensuite une à une toutes les valeurs de la liste restante. Il insère la valeur dans la sous-liste triée de l’ensemble de données à la bonne position, en déplaçant les éléments de rang supérieur vers le haut si nécessaire.

Cet algorithme n’est pas toujours très efficace et est surtout recommandé lors du tri d’une petite liste de valeurs ou d’une liste déjà presque triée.

Vous pouvez lire toute la théorie du monde sur les algorithmes de tri, mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre liste de nombre et visualiser simultanément le résultat du tri et l’évolution étape par étape de l’algorithme de tri par insertion (ou Insertion Sort Algorithm)

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Filtres photo

Exemple réel de synthèse soustractive. Vous pouvez sélectionner différents filtres en cliquant dessus puis observer leur action en survolant la photo.

Les filtres ‘couleurs primaires’ ne laissent passer que leur couleur. Les filtres ‘couleurs complémentaires’ laissent passer deux couleurs primaires.

Cliquer puis faire glisser le filtre sélectionné sur l’image.

 

Extrait du programme de SNT

Cet article peut être un élement de cours sur la photographie numérique du programme d’enseignement commun en seconde de SNTSciences numériques et technologie

Contenus Capacités attendues
Photosites, pixels, résolution (du capteur, de l’image), profondeur de couleur Distinguer les photosites du capteur et les pixels de l’image en comparant les résolutions du capteur et de l’image selon les réglages de l’appareil.
Métadonnées EXIF Retrouver les métadonnées d’une photographie.
Traitement d’image Traiter par programme une image pour la transformer en agissant
sur les trois composantes de ses pixels.
Rôle des algorithmes dans les appareils photo numériques Expliciter des algorithmes associés à la prise de vue.
Identifier les étapes de la construction de l’image finale.

Vous trouverez l’ensemble du programme en cliquant ici.

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

Quel livre choisir en première NSI ?

Il existe actuellement 6 livres destinés aux élèves de Première qui ont choisi la spécialité NSI  (« Numérique et sciences informatiques ») et qui souhaitent acquérir un très bon niveau dans l’optique d’aborder dans les meilleures conditions la Terminale et, bien sûr, de réussir le bac, pourquoi pas avec mention.

Ils sont un outil indispensable pour ceux qui souhaitent poursuivre des études supérieures dans une formation ayant une composante informatique importante.

Tous ces livres de première NSI, suivent strictement le programme de la spécialité conforme à la réforme du Bac 2021. Ils exposent en détail chaque notion avec rigueur. Ils aident à acquérir des savoirs solides permettant de développer des capacités de raisonnement et de résolution qui sont la clé de la réussite dans les études supérieures scientifiques.

Les 6 livres de première NSI ont des différences que je développerai dans d’autres articles mais aussi des points communs.

  • Le cours, sous forme de synthèse ou rappel de cours,  pour vous permettre d’accéder à une connaissance synthétique des notions.
  • Des QCM, pour tester votre compréhension du cours et vous éviter de tomber dans les erreurs classiques.
  • Des exercices et les corrigés détaillés et commentés.

Python pour la carte micro:bit: SNT Lycées. Mathématiques. Sciences

Python pour la carte micro:bit: SNT Lycées. Mathématiques. Sciences

Deux fois plus petite qu’une carte de crédit et coûtant moins de 20€, la carte micro:bit est un nano-ordinateur lancé en 2016 au Royaume- Uni par la BBC pour initier les collégiens au codage et au pilotage de systèmes numériques. Pouvant être programmée depuis un PC, un smartphone, une tablette ou encore un Raspberry Pi, cette carte est compacte, robuste, simple d’utilisation, facile à connecter, fédérant une communauté très importante et s’accompagnant d’un grand nombre d’extensions. Pour la piloter, plusieurs langages de programmation sont disponibles : Python, JavaScript, MakeCode…

Cet ouvrage se concentre sur la programmation de la carte micro:bit avec Python, le langage officiel pour l’enseignement de l’informatique au lycée. Ne nécessitant aucune compétence particulière en codage, il est organisé en trois parties. La première pose les bases du langage Python (variables, boucles, fonctions…), la deuxième regroupe différentes applications concrètes et facilement réalisables avec la carte micro:bit, et la troisième présente des projets plus complexes faisant appel aux extensions de la carte. Le lecteur sera ainsi amené à fabriquer un chronomètre, une boussole, ou encore à jouer de la musique.

À qui s’adresse ce livre ?

  • Aux enseignants (SNT, mathématiques, sciences) et à leurs élèves de lycée
  • Aux makers, geeks, roboticiens, FabLabs…

Pour aller plus loin

Pour approfondir vos connaissances, et développer vos compétences, je vous propose cette sélection de livre.

Comment visualiser les parcours d’un arbre binaire de recherche (ABR) ?

Un arbre de recherche binaire (ABR) est un arbre binaire dans lequel chaque sommet n’a que 2 enfants au maximum qui satisfait à la propriété d’un ABR : Tous les sommets dans le sous-arbre gauche d’un sommet doivent avoir une valeur inférieure à la sienne et tous les sommets dans le sous-arbre droit d’un sommet doivent avoir une valeur supérieure à la sienne (nous supposons que toutes les valeurs sont des entiers distincts dans cette visualisation et qu’un petit ajustement est nécessaire pour tenir compte des doublons et des non-entiers).

La visualisation des parcours DFS et BFS

Vous pouvez lire toute la théorie du monde sur les parcours en profondeur dans un arbre de recherche binaire (ABR), mais voir ces structures en action peut vraiment vous faire avancer. Si vous êtes le genre de programmeur qui apprend mieux avec des images plutôt qu’avec des mots, consultez VisualAlgo

Avec VisualAlgo, vous pouvez créer votre propre arbre de recherche binaire (ABR) et visualiser les 2 types de parcours :

  • parcours en profondeur (ou DFS, pour Depth-First Search)
  • parcours en largeur (ou BFS, pour Breadth First Search en anglais)

VisualAlgo est un outil de visualisation d’algorithmes

VisualAlgo est un outil de visualisation d’algorithmes basé sur le web sans qu’il soit nécessaire d’installer un logiciel supplémentaire.

Il utilise les dernières technologies web : HTML5, CSS3, JavaScript.

Il permet aux utilisateurs de spécifier leurs propres entrées d’algorithme et la visualisation fonctionnera sur avec ces entrées. Il s’agit d’une collection de visualisations d’algorithmes avec une interface unifiée.

La visualisation est très efficace pour comprendre l’algorithme, et il en va de même pour comprendre la visualisation du programme. Ainsi, au fur et à mesure que la compréhension des algorithmes et de la programmation progresse, le site “VisualAlgo” permet d’apprendre simultanément les algorithmes et la programmation en visualisant le code du programme qui décrit l’algorithme en une seule fois.

Le site est interactif, vous pouvez donc choisir ou insérer des éléments dans la collection d’exemples et de regarder comment elle fonctionne visuellement.

Le coin supérieur gauche fournit généralement une explication de ce qui se passe, tandis qu’un pseudo-code apparaît en bas à droite.

C’est un très bon outil pour visualiser les concepts de structure de données et les algorithmes.

Pour aller plus loin

Pour approfondir cette notion, et développer vos compétences vous pouvez consulter cette ouvrage.

Comment effacer des éléments dans une liste chainée en Python ?

Comme nous l’avons vu dans un autre article pour l’insertion, il peut y avoir plusieurs façons de supprimer des éléments d’une liste doublement liée. Dans cette section, nous allons passer en revue certaines d’entre elles.

Suppression d’éléments au début de la liste

La façon la plus simple de supprimer un élément d’une liste doublement liée est de le faire dès le début. Pour ce faire, il suffit de fixer la valeur du nœud de départ au nœud suivant, puis de fixer la référence précédente du nœud de départ à Aucune. Mais avant cela, nous devons effectuer deux vérifications. Tout d’abord, nous devons voir si la liste est vide. Ensuite, nous devons voir si la liste ne contient qu’un seul élément ou non. Si la liste ne contient qu’un seul élément, nous pouvons simplement mettre le nœud de départ sur None (Aucun). Le script suivant peut être utilisé pour supprimer des éléments du début de la liste doublement liée.

Suppression d’éléments à la fin de la liste

Pour supprimer l’élément de la fin, nous vérifions à nouveau si la liste est vide ou si la liste contient un seul élément. Si la liste ne contient qu’un seul élément, il suffit de mettre le nœud de départ sur Aucun. Si la liste contient plus d’un élément, nous répétons l’opération jusqu’à ce que le dernier nœud soit atteint. Une fois que nous avons atteint le dernier nœud, nous fixons la référence suivante du nœud précédant le dernier nœud, à None (Aucun), ce qui supprime effectivement le dernier nœud. Le script suivant peut être utilisé pour supprimer l’élément de la fin.

Suppression d’éléments par valeur

La suppression d’un élément par valeur est la plus délicate de toutes les fonctions de suppression dans les listes doublement liées, car plusieurs cas doivent être traités afin de supprimer un élément par valeur. Voyons d’abord à quoi ressemble la fonction, puis nous verrons l’explication de l’élément par valeur.