Les activités en détail
Les épreuves de NSI lors du bac
Voici un lien concernant les épreuves du bac sur le site de l'Etudiant.
Puis un lien vers le bulletin officiel concernant l'épreuve écrite et pratique de la spécialité NSI.
Enfin un lien vers le bulletin officiel concernant le grand oral.
... par des révisions de première
Nous allons commencer par quelques révisions du programme de première sur la programmation en Python à partir de fonctions.
Voici quelques exercices à réaliser en Python
et voilà quelques aides pour l'utilisation de Python.
Vous trouverez, ici, une fiche sur des algorithmes de recherches, de tris et autres.
A vous de jouer !
Structures de données
En informatique, une variable a un nom et correspond à de l’information placée en mémoire.
Le type de donnée (ou type) est contenu dans cette information :
- une valeur appartenant à un ensemble précis (entier, flottant, booléen, …)
- et l’ensemble des opérations autorisées avec cette valeur.
En Python, des types de données simples ( entiers, flottant, booléens, chaînes de caractères) ou construits ( listes, tuples, dictionnaires) sont implémentés. Il n’est pas besoin de savoir comment ces types sont représentés dans la machines pour pouvoir les utiliser.
Afin d’organiser et traiter des données, les manipuler avec des algorithmes et obtenir un traitement informatique efficace, on peut définir une structure de données. Celle-ci peut regrouper des objets de types différents et permet de stocker les données d’une manière particulière. Elle permet de représenter des données de façon moins élémentaires que de simples nombres mais plutôt comme un ensemble d’objets quelconques munis de diverses opérations propres à leur manipulation.
Il faut décider comment on attribue une quantité de mémoire pour stocker les données et comment on accède à ces données.
La quantité de mémoire utilisée peut être fixe, on parle de structure statique, c’est le cas des chaînes de caractères en Python, de type str.
Si la quantité de mémoire est variable on parle de structure dynamique, c’est le cas en Python des listes ou tableaux, de type list.
Pour pouvoir utiliser une nouvelle structure, l’utilisateur doit connaître ce qu’on nomme l’interface.
En Python on doit utiliser les crochets [ ] pour créer une liste (un tableau).
Cette connaissance est suffisante, il n’est pas besoin de savoir comment cet objet est représenté dans la machine ni comment le langage de programmation y accède, c’est-à-dire comment est implémentée cette structure.
En Python les entiers de type int sont illimités, ce n’est pas le cas dans d’autres langages où l’on a des types, longs, courts, signés, non signés. Mais, quelle que soit la façon dont est implémentée l’addition de deux entiers dans ces langages, nous avons juste besoin de savoir que, pour l’addition, il faut écrire a + b.
Cependant, la connaissance de l’implémentation en machine des différentes opérations et de la représentation de l’objet a son importance. Elle nous permet d’évaluer les coûts en temps et en espace, des algorithmes que nous programmons.
Considérons une pile d’assiettes. Nous supposons que les assiettes sont manipulées une par une, on peut poser une assiette sur la pile ou retirer une assiette de la pile.
De manière abstraite, on peut définir ce qu’est une pile, que ce soit une pile d’assiettes, de livres, de nombres, d’adresses, d’instructions, etc.
Un type abstrait de données ou une structure de données abstraite est un ensemble de données avec l’ensemble des opérations permises. C’est en quelque sorte un cahier des charges. On annonce quelles sont les données et on précise comment on les manipule, quelles sont les actions autorisées.
Cela ne dépend pas du langage de programmation utilisé.
Concrètement, on peut réaliser une pile en Python en utilisant un type de données connu comme la liste. Il convient alors de restreindre les opérations autorisées qu’il faut définir de manière explicite et très précise.
Quels que soient les éléments de la pile, les opérations et les différents algorithmes qui vont être utilisés sont indépendants de ces éléments. C’est pourquoi, on peut confondre un type abstrait de données avec une structure de données. Donc une pile est à la fois un type abstrait de données et une structure de données.
Une vidéo explicative sur les structures de données de monsieur Laporte
https://lewebpedagogique.com/dlaporte/nsi-cours-de-2eme-annee/
De nombreux algorithmes "classiques" manipulent des structures de données plus complexes que des simples nombres. Nous allons voir ici quelques-unes de ces structures de données :
- la programmation orientée objet,
- des structures qualifiés de linéaires : les listes, les piles et les files,
- les dictionnaires déjà vu, un peu, en première,
- les arbres,
- les graphes.
La programmation orientée objet
La programmation orientée objet, fait ses débuts dans les années 1960 avec le langage Lisp puis est formellement définie avec les langages Simula (vers 1970) et SmallTalk.
Elle s’est ensuite développée dans les langages anciens comme le Fortran, le Cobol et est même incontournable dans des langages récents comme Java.
La programmation orientée objet (POO) est un paradigme de programmation, c’est-à-dire une façon de concevoir un programme informatique, reposant sur l’idée qu’un programme est composé d’objets interagissant les uns avec les autres.
Python permet d'utiliser le paradigme impératif (comme nous l'avons fait jusqu'à présent), mais il permet aussi d'utiliser le paradigme objet. Il est même possible, d'utiliser les 2 paradigmes dans un même programme.
En réalité, nous avons déjà travaillé avec des objets, sans trop savoir qu’on les utilisait.
Par exemple, lorsqu’on utilise des chaînes de caractères ou les listes en Python, on travaille avec des objets. En effet, ces objets sont manipulés par l’intermédiaire de méthodes. Pour les listes Python on a par exemple len(), append(), sort() et bien d’autres encore.
Nous allons aborder maintenant cette manière de programmer avec les trois documents suivants :
- des exemples pour l’apprentissage,
- un bilan détaillé,
- une série d’exercices.
Sources :
zestedesavoir.com,https://pixees.fr/informatiquelycee/,
www.math93.com,NSI Bonnefoy, Petit, éditions ellipses
Des structures linéaires
Nous allons dans ce cours décrire des représentations des structures de données telles que les listes chaînées, les piles et les files.
Ce sont des structures de données à une dimension permettant de stocker de manière linéaire une suite finie de données.
On les dénomme aussi structures de données linéaires.
Voici un bilan de cette étude de structures.
Une application de pile avec un exemple de calculatrice.
Les dictionnaires
Les dictionnaires ont été un peu vus en première,
nous allons approfondir l'étude de ces structures de données linéaires autre que les listes, piles et files
dans ce TP.
et un bilan sur les dictionnaires.
Des structures hiérarchiques
Les listes, les piles et les files sont des structures de données linéaires.
Des structures non linéaires peuvent être intéressantes dans la représentations des données lorsque celles-ci sont hiérarchisées et particulièrement si le nombre des données est important.
Parmi celles-ci on trouve les arbres et en particulier les arbres binaires.
On parle d’arbre, de structures arborescente ou d’arborescence.
On trouve des arbres dans des domaines divers :
arbre généalogique,
arbre lexicographique (qui présente un ensemble de mots) où les préfixes communs à plusieurs mots n’apparaissent qu’une seule fois,
organigramme d’une société avec directeur, sous-directeurs, secrétaires, manutentionnaires, agents comptables,
etc.
Le contenu d’un livre peut être présenté sous la forme d’un arbre avec les dépendances entre les différents chapitres et les différentes sections et sous-sections.
Sur un écran d’ordinateur, le système d’exploitation nous présente, à l’aide de l’explorateur, les données sous forme d’arborescence. Cette forme de représentation nous permet d’accéder rapidement à une donnée particulière.
Dans cette partie nous allons aborder les arbres d’une façon générale avec leur vocabulaire
puis nous étudierons plus en détail une catégorie d’arbre, les arbres binaires.
Nous allons représenter les arbres binaires par des implémentations en Python .
Et nous terminerons pas quelques exercices sur les arbres comme le nombre de Catalan .
Des structures relationnelles
Les graphes se rencontrent fréquemment dans les sciences et leurs applications sont nombreuses.
En voici quelques unes.
Les réseaux routiers
openstreetmap.org
l’internet
pixees.fr
les réseaux sociaux
Gordon Johnson de Pixabay
un algorithme peut être considéré comme un graphe.
parentsconnectés.be
Dans cette partie, nous allons étudier les graphes et leur vocabulaire à partir de deux exemples
puis nous verrons comment les représenter en Python et en extraire des informations.
Bases de données
En classe de première nous avons eu l'occasion de travailler sur des données structurées en les stockant dans des fichiers au format CSV.
Cette méthode de stockage de l'information peut s'avérer pratique dans certains cas précis mais il est souvent souhaitable d'utiliser une base de données pour stocker des informations.
Le terme base de données est apparu au début des années 60.
C'est l'apparition des disques durs à la fin des années 50 qui a permis d'utiliser les ordinateurs pour stocker et manipuler des données.
Avec l'apparition du Web, la quantité de données à stocker n’a cessé de croître. Aujourd'hui, la plupart des sites internet utilisent au moins une base de données et celles-ci jouent un rôle fondamental dans notre monde devenu numérique où il est extrêmement facile de dupliquer l'information. Il est donc important de les étudier.
Voici les différentes parties de ce programme :
- une introduction rapide aux bases de données et aux systèmes de gestion des bases,
- une étude des bases de données relationnelles,
- un cours sur le langage SQL,
- SQL implémenté en Python.
Bases de données et systèmes de gestion
Quelques informations générales
sur les systèmes de gestion des bases de données
et sur les propriétés ACID
dans ce document.
Bases de données relationnelles
Il existe différents types de bases de données, par exemple, les bases de données hiérarchiques, les bases de données objet, les bases de données nosql ou bien encore les bases de données relationnelles.
(https://fr.wikipedia.org/wiki/Base_de_donn%C3%A9es)
Les bases de données relationnelles sont les plus utilisées au monde, c'est ce type de base de données que nous allons étudier.
Les bases de données relationnelles ont été mises au point en 1970 par Edgar Franck Codd, informaticien britannique (1923-2003).
Ces bases de données sont basées sur la théorie mathématique des ensembles.
Activité à faire sur les bases de données relationnelles.
Quelques exercices de mise en application des quelques notions vues.
Voici quelques vidéos pour illustrer ce cours.
Une première vidéo sur les bases de données.
Quatre vidéos de Nicolas Rangeon
sources: https://openclassrooms.com,
https://lewebpedagogique.com/dlaporte/
Les relations ou tableaux à deux dimensions.
Les clés.
Les clés étrangères.
Les projections.
Le langage SQL
Pour commencer, une vidéo de Marie Duflot-Kremer sur les bases de données relationnelles :
Nous avons eu l'occasion d'étudier la structure d'une base de données relationnelle.
Nous allons maintenant apprendre à réaliser des requêtes, c'est-à-dire que nous allons apprendre à :
- créer une base des données,
- créer des attributs,
- ajouter des données,
- modifier des données et enfin,
- nous allons surtout apprendre à interroger une base de données afin d'obtenir des informations.
Pour réaliser toutes ces requêtes, nous allons devoir apprendre un langage de requêtes :
le SQL (Structured Query Language).
SQL est propre aux bases de données relationnelles, les autres types de bases de données utilisent d'autres langages pour effectuer des requêtes.
Pour créer une base de données et effectuer des requêtes sur cette base de données, nous allons utiliser le logiciel "DB Browser for SQLite",
à télécharger sur le site suivant : https://sqlitebrowser.org/.
SQLite est un système de gestion de base de données relationnelle très répandu.
Il existe d'autres systèmes de gestion de base de données relationnelle comme MySQL ou PostgreSQL.
Dans tous les cas, le langage de requête utilisé est le SQL (même si parfois on peut noter quelques petites différences). Ce qui sera vu ici avec SQLite pourra, à quelques petites modifications près, être utilisé avec, par exemple, MySQL.
Voici les premières activités pour utiliser sqlite
une première fiche d'exercices pour s'entraîner,
puis une seconde fiche,
enfin un mémo de quelques fréquentes commandes SQL.
Ces différents documents ont été réalisés grâce à quelques contributeurs dont je n'ai plus les noms, de la liste NSI de groupes.renater.fr.
Qu'ils en soient remerciés !
SQL implémenté en Python
Il est possible de manipuler des bases de données avec Python.
Pour cela, on fait appel au module sqlite3 ou mysql.connector selon le serveur SQL qu’on a installé.
Nous avons utilisé SQLite (qui ne nécessite pas l’installation d’un serveur) et créé des bases au format sqlite (avec les extensions sqlite, sqlite3, sq3 ou db).
Dans ce cas le langage Python peut être utilisé pour interroger ces bases avec des requêtes SQL, les réponses s’affichant dans l’interpréteur.
Nous allons donc importer le module sqlite3 disponible avec la librairie standard de Python.
Cette méthode comme avec l’utilisation de SQLite ne nécessite pas l’installation d’un serveur.
Source : d’après Serge Bays, " NSI terminale " éditions Ellipses.
Voici un TP sur Python et les bases de données.
Architectures matérielles, systèmes d'exploitation et réseaux
Nous avons étudié, en première, les systèmes d'exploitation et plus particulièremment Linux et les réseaux.
Nous allons cette année travailler sur
les composants sur puce,
la gestion des processus,
les protocoles de routage
Les composants intégrés d'un système sur puce
Nous allons commencer par une vidéo sur l'évolution des circuits intégrés depuis plus de cinquante ans.
Les circuits intégrés vidéo de Stéphane Marty
Deus Ex Silicium : Les Circuits Intégrés
Nous allons maintenant étudier plus en détail certains de ces circuits intégrés, les SoCs !
Gestion des processus et des ressources
Nous allons maintenant aborder le sujet des processus et de leur gestion
avec le TP suivant sur la gestion des processus.
Quelques activités sur l'interblocage expérimenté en Python.
Protocoles de routage
Prérequis
Avant d'introduire les algorithmes de routage, il est important de bien maîtriser les concepts de base qui régissent la communication sur internet.
Pour bien suivre ce cours, il est nécessaire de maîtriser les bases sur les réseaux (réseau local, adresse IP, adresse réseau…). N'hésitez pas à vous replonger dans le cours de première si nécessaire.
Cette vidéo extraite du MOOC SNT
Introduction
Nous allons regarder en détails deux exemples de protocoles de routage (RIP et OSPF).
Afin de comprendre les enjeux de ces protocoles de routage, voici une petite vidéo introductive expliquant pourquoi et comment les routeurs communiquent entre eux afin de déterminer le meilleur itinéraire à faire emprunter aux paquets dont ils ont la charge.
Routage
Un premier TP ici pour expliquer le routage.
Nous allons maintenant étudier deux protocoles de routage :
le premier est le protocole RIP - Routing Information Protocol
la vidéo qui suit, explique le principe du routage RIP
le deuxième est le protocole OSPF - Open Shortest Path First
et la vidéo qui suit, explique le principe du routage OSPF
Sécurisation des communications
Programmation en Python
Des aides pour la programmation en Python
>
Pour vous aider à programmer en python, voici un mémo python
dans lequel vous trouverez de nombreuses commandes utiles. Il ne faut pas hésiter à l'utiliser.
>
Pour en apprendre plus sur le langage python et ses nombreuses commandes,
je vous invite à visiter ce site dédié à Python
>
La récursivité
Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60.
Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité.
Un algorithme qui contient un ou des appels à lui-même est dit récursif.
Le mot récursif provient du latin ‘recurrere’ signifiant courir en arrière.
Le document suivant décrit la programmation récursive à partir de deux exemples.
Puis bilan, validité et coût des algorithmes récursifs.
Enfin quelques exercices pour s'entraîner à programmer en récursif.
Et une autre série d'excercices en récursif.
L'algorithmique
Des algorithmes pour des arbres
Après avoir étudier les arbres comme structure de données nous allons aborder la partie qui permet de parcourir ces arbres de diverses façons puis de chercher ou d'insérer des clés et des valeurs dans les arbres binaires de recherche.
parcours d'arbres
recherche et insertion dans les arbres.
Des algorithmes pour des graphes
Les graphes peuvent être utilisé en informatique :
pour la recherche d’un chemin,
openclassrooms.com
la recherche de la meilleure route dans un réseau,
pixees.fr
la recherche d’un cycle ou comment ne pas tourner en rond dans un labyrinthe.
Clker-Free-Vector-Images de Pixabay
Dans les cours qui suivent nous allons aborder les algorithmes de parcours de graphes:
algorithmes de parcours en largeur,
algorithmes de parcours en profondeur,
La méthode "diviser pour régner"
L’expression "diviser pour régner", en anglais "divide and conquer" est très ancienne.
Au temps des romains, elle était employée au sénat (en latin "divide et regnes") et Jules césar utilisait l’expression "divide et impera".
L’expression est reprise par le penseur Machiavel au début du XVIe siècle dans ses récits présentant une conception de la politique et notamment dans "le prince" (1513).
C’est aussi une méthode de résolution de problèmes.
Dans ce cours nous allons décrire le principe de cette méthode puis l’utiliser dans plusieurs cas comme la recherche d’un élément dans une liste non triée ou dans le tri d’une liste de valeur.
Nous avons déjà utilisé ce paradigme en première avec un algorithme de recherche dichotomique (voir les révisions de début de terminale).
Nous allons étudier entre autre un algorithme de tri qui utilise le principe de "diviser pour régner". il s’agit du tri fusion ou "merge sort". Il s’agit d’un tri dichotomique avec un appel récursif.
D’après Donald Knuth (The art of computer programming), le tri fusion est l’une des premières méthodes de tri utilisées sur un ordinateur.
Voici le cours-TD sur la méthode "diviser pour régner".