# Introduction

Ce livre contient de nombreux articles utiles aux étudiants de classe de Terminale qui sont inscrits à la spécialité Informatique et Sciences du numérique. Il est écrit en développant différentes parties du programme officiel du Ministère de l'Éducation Nationale.

# La représentation de l'information

* Dans un contexte informatique, l'information est représentée par des suites de nombres. La numérisation est l'opération qui associe à un objet réel du monde physique une description à l'aide d'un ensemble d'informations exploitables par un ordinateur ou, plus généralement, une machine numérique. À cause de l'échantillonnage sous-jacent, la numérisation induit des effets importants sur la qualité de l'information numérique. Elle entraîne des conditions spécifiques de création, de stockage, de traitement et de circulation de l'information.
* Les capacités de traitement et de stockage des ordinateurs croissent de façon continue depuis leur apparition. Il est donc crucial d'organiser ces flux d'informations en local sur une machine ou de façon distribuée sur un réseau.
* L'intégration croissante du numérique dans les activités humaines et la numérisation de l'information suscitent des transformations culturelles, socio-économiques, juridiques et politiques profondes qui font apparaître de nouvelles opportunités, de nouveaux risques et de nouvelles contraintes qu'il convient d'étudier.
* Source : programme officiel (www.education.gouv.fr/...bo=57572)
* Les prochaines citations de ce programme officiel seront signalées par le logo suivant :

## La représention binaire

| Savoirs : | Un ordinateur est une machine qui manipule des valeurs numériques représentées sous forme binaire. |
| Capacités : | Manipuler à l'aide d'opérations élémentaires les trois unités de base : bit, octet, mot. |
| Observation : | On met en évidence, sous forme de questionnement, la présence du numérique dans la vie personnelle et professionnelle, au travers d'exemples. |

### Systèmes de numération

Quand des sociétés humaines ont commencé à compter, des systèmes de numération ont été mis au point, pour permettre de communiquer des nombres avec moins de mots.
La numération la plus évidente à inventer consiste à montrer des collections de symboles. Des comptables de Mésopotamie ont utilisé des cylindres pour imprimer sur de l'argile des données commerciales. Les « imprimés » étaient complétés par des marques faites à l'aide d'un stylo en roseau, le calame.
Exercice
* Pourquoi cette méthode a-t-elle été remplacée par d'autres plus tard ?
* Retrouvez l'origine du mot calcul en Mésopotamie : qu'appelait-on les calculi ?
Les comptages simples, tels que des encoches sur un morceau de bois ou d'os, les collections de calculi dans une bourse en terre, deviennent plus pratiques quand on regroupe les unités par paquets. En Mésopotamie, la méthode utilisée consistait à faire des paquets de 60 : ça a mené à l'invention d'un système numérique à base 60.
Autres civilisations, autre mœurs, autres bases de numération, voici quelques exemples :
| Époque | Civilisation | base de numération |
| Depuis -3000 | Civilisation Sumérienne, puis Mésopotamienne, Chine, Inde | Base sexagésimale (60) : on peut utiliser les pouces et les phalanges pour compter jusqu'à 60 avec les mains |
| Encore valide en 2013 | Tous pays | Base sexagésimale (60) : une heure compte 60 minutes, elles-même subdivisées en 60 secondes. |
| Jusqu'au XVIème siècle | Civilisations aztèque, civilisation Maya | Base vicésimale (20) : les calculs étaient faits dans cette base jusqu'à l'invasion espagnole |
| Moyen-Âge | Pays européens | Base vicésimale (20) : cette base était souvent utilisée en concurrence avec la base décimale. Il en reste de nombreux vestiges : le nombre « quatre vingt » toujours utilisé, le sou, égal à un vingtième de franc. |
| -200 | Empire romain | Base duodécimale (12). Le comptage par douze est souvent utilisé, et a laissé de nombreuses traces dans notre vocabulaire. Quelles sont les traces que vous connaissez ? Cherchez les sens du mot « grosse ». |
| Jusqu'à 1971 | Empire brittanique | Base duodécimale (12). La pièce de 1 shilling valait 12 pence (pluriel de penny) |
| Encore valide en 2013 | États-Unis | Base duodécimale (12). Un pied (mesure de longueur) se divise en 12 pouces |

#### Questions sur les bases de numération

La base décimale que nous utilisons aujourd'hui vient de nos chiffres « arabes », qui ont été inventés en Inde.
* Pourquoi la base 10 est-elle utilisée très largement partout ?
* Est-ce la base la mieux appropriée dans tous les cas ?
* Est-il facile de construire une machine à calculer qui fonctionne avec la base 10 ?

### Exemple en base 5

Comme la majorité d'entre nous a cinq doigts aux membres, l'utilisation d'une base 5 paraît judicieuse.
Cette base est souvent utilisée, par exemple pour compter des points dans une rencontre sportive, ou pour compter des voix dans un bureau de vote.

#### Exercice résolu

Comment pourrions-nous noter le nombre de jours d'une année non bissextile, en base 5 ? Les symboles utilisés pour les chiffres seront 0, 1, 2, 3 et 4.
Solution Les calculs seront menés en base 10, qui nous est plus familière.
On divise 365 par 5 : $365\div 5=73$, reste $0$.
On divise 73 par 5 : $73\div 5=14$, reste $3$.
On divise 14 par 5 : $14\div 5=2$, reste $4$.
On divise 2 par 5 : $2\div 5=0$, reste $2$.
On s'arrête là, et on écrit la suite des restes à l'envers : $2430$. C'est la représentation en base 5 du nombre de jours d'une année non bissextile.
On peut vérifier que : ${\begin{array}{rcl}2\times 5^{3}+4\times 5^{2}+3\times 5^{1}+0\times 5^{0}&=&\\2\times 125+4\times 25+3\times 5+0\times 1&=&\\250+100+15&=&365\end{array}}$

#### Convention de notation

On utilise souvent les premiers symboles de la suite 0123456789ABCDEF... (autant qu'il en faut, pas plus); comme symboles numériques pour une base donnée. Par exemple, pour la base 12, les symboles sont 0123456789AB.
Chaque fois qu'une ambiguïté est possible, on place un symbole de la base en indice du nombre écrit. Par exemple, le résultat de l'exercice résolu peut s'écrire $365_{10}=2430_{5}$, ou encore $365_{dec}=2430_{quin}$, ce qui signifie que 365 en base 10 (décimale) vaut 2430 en base 5 (quinaire).

### La base 2 pour les ordinateurs

La base 5, ou base quinaire, semble adaptée pour les humains, à cause de leurs cinq doigts. Il existe des méthode de comptage avec les mains pour les bases 10, 12, 20 et 60.
Cependant les ordinateurs sont faits d'automatismes électroniques, où il est plus facile de distinguer deux états seulement : arrêt/marche, ou éteint/allumé, qu'on représente aussi souvent comme faux/vrai, ou 0/1.
Exemple : les composants électroniques de la famille TTL (transistor-transistor logic) obéissent à la norme suivante :
* les tensions utilisées sont toujours entre 0 et 5 V ;
* les tensions entre 0 et 2 V correspondent à la valeur binaire $0_{bin}$ ;
* les tensions entre 3 et 5 V correspondent à la valeur binaire $1_{bin}$ ;
* les tensions ne restent presque jamais entre 2 et 3 V, et on s'arrange pour ne faire des calculs qu'en dehors des moments où existent des risques (aléas) d'avoir des tensions entre 2 et 3 volt.

#### Exercice résolu

Trouver la représentation en binaire de 365 en décimal.
Solution
On effectue la suite d'opérations suivantes :
${\begin{array}{rcl}365\div 2=184&{reste}&1\\184\div 2=92&{reste}&0\\92\div 2=46&{reste}&0\\46\div 2=23&{reste}&0\\23\div 2=11&{reste}&1\\11\div 2=5&{reste}&1\\5\div 2=2&{reste}&1\\2\div 2=1&{reste}&0\\1\div 2=0&{reste}&1\\\end{array}}$
Donc la solution est : $365_{dec}=101110001_{bin}$
Vérifiez que... ${\begin{array}{lcl}1\times 2^{8}+&&\\0\times 2^{7}+&&\\1\times 2^{6}+&&\\1\times 2^{5}+&&\\1\times 2^{4}+&&\\0\times 2^{3}+&&\\0\times 2^{2}+&&\\0\times 2^{1}+&&\\1\times 2^{0}&=&365\end{array}}$
Dans l'exemple précédent, on voit que pour représenter $365_{dec}$ en binaire, 9 chiffres sont nécessaires. On peut retenir que pour un même nombre, l'écriture binaire est toujours environ trois fois plus longue que l'écriture décimale. Ce désavantage, pour les ordinateurs, est largement compensé par la grande simplicité des opérations que permet le système binaire.

#### La simplicité des opérations en binaire

Comparez les tables de multiplications en systèmes décimal et binaire !
Combien vous a-t-il fallu de temps pour mémoriser les tables de multiplication au cours de votre scolarité ? Les connaissez-vous bien ?
La table de multiplication en binaire est beaucoup plus simple ! (On a retiré la multiplication par zéro des tables de l'illustration, et on a un peu triché en supprimant les lignes et colonnes de 10 dans le cas de la table en base deux).
Exercices
* Retrouvez les tables de multiplication complètes en système binaire. On doit tenir compte du chiffre zéro. Il faut la table de multiplication et la table d'addition. Ne pas oublier de signaler quand il y a une retenue.
* Multipliez $101110001_{bin}$ par $11_{bin}$, vérifiez que le résultat est le même que pour la multiplication de 365 par 3.

### Conversions d'un nombre d'une base à l'autre

En vous inspirant des exercices ci-dessus, on peut décrire en toute généralité l'algorithme qui permet de convertir un nombre écrit en base X vers sa représentation en base Y. Il faut pour cela :
* passer de la suite des symboles représentant le nombre en base X au nombre entier représenté,
* puis de ce nombre vers la suite de symboles le représentant en base Y.

#### Algorithme pour passer de la représentation d'un nombre en base X à sa valeur

Exemple de fonctionnement
On lance le programme, et on répond "101" puis "2".
À ce stade, (ligne 10)
* symboles vaut "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ",
* val vaut 0,
* nombreEnBaseX vaut "101",
* X vaut 2.
* Les valeurs de c et i sont indéterminées.
Au premier passage dans la boucle tantQue,
* la longueur de nombreEnBaseX vaut 3, dont on entre dans la boucle.
* val prend la valeur 2 * 0, il reste nul.
* puis c prend la valeur "1" et
* nombreEnBaseX est raccourci à gauche pour devenir "01".
* i prend la valeur 1 (position de "1" dans la chaîne "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"),
* puis val prend la valeur 0+1 = 1.
Au deuxième passage dans la boucle tantQue,
* la longueur de nombreEnBaseX vaut 2, dont on entre dans la boucle.
* val prend la valeur 2 * 1 = 2.
* puis c prend la valeur "0" et
* nombreEnBaseX est raccourci à gauche pour devenir "1".
* i prend la valeur 0 (position de "0" dans la chaîne "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"),
* puis val prend la valeur 2+0 = 2.
Au troisième passage dans la boucle tantQue,
* la longueur de nombreEnBaseX vaut 1, dont on entre dans la boucle.
* val prend la valeur 2 * 2 = 4.
* puis c prend la valeur "1" et
* nombreEnBaseX est raccourci à gauche pour devenir "".
* i prend la valeur 1 (position de "1" dans la chaîne "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"),
* puis val prend la valeur 4+1 = 5.
Il n'y a pas de quatrième passage dans la boucle tantQue, puisque la longueur de nombreEnBaseX vaut 0. On passe donc à la suite, ce qui établit le résultat à 5.
Exercice
* Vérifiez que si on lance l'algorithme et qu'on répond "75" puis "8", le résultat vaut 61 (en base décimale).
* Vérifiez que si on lance l'algorithme et qu'on répond "AA" puis "16", le résultat vaut 176 (en base décimale).

#### Algorithme pour passer d'une valeur entière à sa représentation base Y

Exemple de fonctionnement
On lance l'algorithme et on répond "5" et "2". À ce moment-là (à la ligne 11),
* symboles vaut "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ",
* val vaut 5, Y vaut 2 et
* repr vaut "" (chaîne vide).
* Les valeurs de c, quotient, reste sont indéterminées.
Au premier passage dans la boucle,
* val vaut 5, donc on y entre.
* quotient prend la valeur 2 et
* reste prend la valeur 1 ;
* val prend la valeur 2 ;
* c devient "1" puisque c'est le caractère numéro 1 de "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;
* repr devient "1" attaché à "", donc "1".
Au deuxième passage dans la boucle,
* val vaut 2, donc on y entre.
* quotient prend la valeur 1 et
* reste prend la valeur 0 ;
* val prend la valeur 1 ;
* c devient "0" puisque c'est le caractère numéro 0 de "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;
* repr devient "0" attaché à "1", donc "01".
Au troisième passage dans la boucle,
* val vaut 1, donc on y entre.
* quotient prend la valeur 0 et
* reste prend la valeur 1 ;
* val prend la valeur 0 ;
* c devient "1" puisque c'est le caractère numéro 1 de "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;
* repr devient "1" attaché à "01", donc "101".
Il n'y a pas de quatrième passage dansla boucle, puisque val vaut 0. On passe donc à la suite et le résultat vaut "101".
Exercice
* Vérifiez que si on lance l'algorithme et qu'on répond "61" puis "8", le résultat vaut 75 (en base octale).
* Vérifiez que si on lance l'algorithme et qu'on répond "176" puis "16", le résultat vaut AA (en base hexadécimale).

### D'autres bases pour les octets

La valeur $176_{dec}$ est égale à $10101010_{bin}$.
Il est assez facile de repérer une faute de frappe quand on écrit 176, quand on se relit. Cependant, une faut de frappe telle que 10101110 au lieu de 10101010 peut passer plus facilement inaperçue. Et le risque augmente avec la longueur des nombres.
Remarquons que $10101010_{bin}=176_{dec}$, cependant que $10101110_{bin}=180_{dec}$. L'erreur est plus évidente à repérer en codage décimal.

#### Base hexadécimale (16)

On utilise très souvent la base hexadécimale pour représenter les octets, c'est à dire les nombres binaires à 8 chiffres, de 00000000 à 11111111. En effet, seize est égal à deux puissance quatre : autrement dit, chaque chiffre hexadécimal correspond directement à quatre chiffre binaires, sans erreur possible.
$10101010_{bin}=AA_{hex}$, cependant que $10101110_{bin}=AE_{hex}$. L'erreur est plus évidente à repérer en codage hexadécimal, et en plus, elle montre tout de suite que l'erreur se situe dans les quatre chiffre binaires de poids faible (à droite du nombre).
N.B. : en base hexadécimale, les chiffres sont 0123456789ABCDEF.

#### base octale (8)

De même que la base hexadécimale est très pratique pour exprimer des nombres binaires de quatre ou huit chiffres, la base octale va bien pour exprimer des nombres binaires de 3, 6, 9 ou 12 chiffres : en effet, huit est égal à deux à la puissance 3.
N.B. : en base octale, les chiffres sont 01234567.

## Les opérations booléennes

| Savoirs : | Présentation des opérations booléennes de base (et, ou, non, ou-exclusif). |
| Capacités : | Exprimer des opérations logiques simples par combinaison d'opérateurs de base. |
| Observation : | On découvre les opérations logiques de base à l'aide d'exercices simples et on met en évidence ces opérations dans les mécanismes de recherche. En parallèle avec les séances d'algorithmique, on peut expliquer le principe d'addition de deux octets. |

### Logique à deux états

On appelle « logique à deux états », ou logique booléenne, un système d'opérations qu'on peut faire sur des objets qui ne peuvent prendre que deux valeurs, appelées faux/vrai ou 0/1.
Les circuits logiques à deux états sont nombreux dans un ordinateur, il en existe plusieurs normes. Par exemple, selon le standard TTL, la valeur 0 est définie par un tension électrique comprise entre 0 et 0,5 V, la valeur 1 est définie par une tension comprise entre 2,4 et 5 V. On arrive à garantir que ces valeurs de tensions soient respectées en concevant correctement les montages logiques :
* en contrôlant le courant maximal demandé à chaque porte logique ;
* en utilisant une horloge pour déterminer à quel moment les valeurs logiques sont bien établies.

### Circuits logiques CMOS

Le standard CMOS est plus récent que le standard TTL. Il est basé sur l'utilisation de transistors Complémentaires utilisant une technologie Metal-Oxyde-Semiconducteur (d'ou l'acronyme CMOS).
Un transistor MOS peut être considéré comme un petit barreau de semi-conducteur (en silicium dopé), avec deux extrémités nommées drain (D) et source (S), dont la conductivité électrique est contrôlée par une électrode nommée la porte ou la grille (G) : cette électrode métallique est placée très près du barreau, elle n'en est séparée que par film isolant en oxyde de silicium très fin (quelques nm).
Pour le standard CMOS, la valeur FAUSSE (0) est définie par une tension comprise entre 0 V et la moitié de la tension d'alimentation, la valeur VRAIE (1) est définie par une tension coprise entre la 0,5 fois et une fois la tension d'alimentation. La tension d'alimentation peut varier entre 3 et 18 V, ce qui facilite l'emploi de ces circuits électroniques dans divers montages.

### Autres circuits logiques

Il existe d'autres circuits logiques que les circuits logiques à deux états, par exemple des circuits dont la sortie peut être « fausse », « vraie » ou en haute impédance (ils se comporte alors comme s'ils étaient débranchés du circuit).

### Opération booléenne NON

L'opération NON est ue opération unaire, c'est à dire à un seul opérande.
(NON a) est VRAI si A est FAUX; (NON a) est FAUX si a est VRAI.
(NON a) se note ${\overline {a}}$

#### Table de vérité du NON

| $a$ | ${\overline {a}}$ |
| 0 | 1 |
| 1 | 0 |

#### Réalisation d'une porte NON avec un transistor MOS à effet de champ

Le barreau semi-conducteur entre drain et source peut changer de conductivité électrique :
* quand la tension électrique entre grille et source $U_{GS}$ est faible (valeur logique 0 ou FAUX), le "barreau" entre drain et source est isolant, on peut le considérer comme non existant dans le circuit électrique ;
* quand la tension électrique entre grille et source $U_{GS}$ est importante (valeur logique 1 ou VRAI), le "barreau" entre drain et source est conducteur, on peut le considérer comme un fil électrique.
Il est donc possible de réaliser un simple porte NON à l'aide d'un transistor et d'une résistance électrique. Voici un schéma qui montre comment, avec un signal logique 0 à l'entrée d'un tel montage, on obtient en sortie un signal de valeur logique 1 :
| la tension $U_{GS}$ est nulle, le transistor est isolant | tout se passe comme si le transistor n'était pas là, la sortie est reliée au pôle positif à travers la résistance |
Le schéma suivant montre qu'avec un signal logique 1 à l'entrée du montage, on obtient en sortie un signal de valeur logique 0 :
| la tension $U_{GS}$ est égale à $U_{DS}$, le transistor est conducteur | on peut le remplacer par un fil électrique, la résistance n'intervient plus |
Remarque : dans les circuits logiques CMOS, la résistance est remplacée par un autre transistor MOS dont le comportement est complémentaire : ça symétrise mieux le comportement des portes logiques.

### Opération booléenne OU

le résultat de (a OU b) est VRAI si et seulement si plus d'une valeur boolénnes a et b sont VRAIES (une seule VRAIE, ou les deux VRAIES en même temps).
(a OU b) se note : $a\lor b$

#### Table de vérité du OU

| $a$ | $b$ | $a\lor b$ |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

#### Réalisation d'une porte OU avec des transistors MOS

Le circuit ci-dessus fabrique à partir des signaux d'entrée $a$ et $b$ un signal intermédiaire $c$ (à l'intérieur du circuit), puis un signal de sortie $d$, par action d'un transistor monté en porte NON.
On peut montrer que $c={\mbox{NON}}(a\ {\mbox{OU}}\ b)$, ou, noté autrement, $c={\overline {a\lor b}}$. Comme $d$ est la négation de $c$ et que la double négation revient à une copie en logique binaire, $d={\overline {c}}={\overline {\overline {a\lor b}}}=a\lor b$.
Exercice : dessiner le schéma d'une porte "OU NON", réalisée à l'aide de transistors MOS canal N et de résistances. La table de vérité du "OU NON" est la suivante :
| $a$ | $b$ | $a\ {\mbox{OU NON}}\ b$ |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |

### Opération booléenne ET

le résultat de (a ET b) est VRAI si et seulement si les deux valeurs boolénnes de a et b sont VRAIES en même temps.
(a ET b) se note : $a\cdot b$ ou encore $a\land b$
La table de vérité faux/vrai de l'opérateur booléen ET est exactement identique à la la table de multiplication de deux chiffres binaires.

#### Table de vérité du ET

| $a$ | $b$ | $a\land b$ |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
autre présentation : table à deux entrées.
| $\land$ | F | V |
| F | F | F |
| V | F | V |
la table à deux entrées correspond point par point à la table de multiplication en binaire :
| $\times$ | 0 | 1 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Exercice : trouver un schéma d'une porte ET réalisée à l'aide de transistors MOS canal N et de résistances.

### Opération booléenne OU EXCLUSIF

la valeur de $a\ {\mbox{OU EXCLUSIF}}\ b$ est VRAIE si et seulement si une seule des valeurs $a$ ou $b$ est VRAIE (donc l'autre est fausse, en même temps).

#### Table de vérité du OU EXCLUSIF

| $a$ | $b$ | $a\ {\mbox{OU EXCLUSIF}}\ b$ |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

#### Équation logique du OU EXCLUSIF

Cette opération peut se formuler comme : « a est VRAI ET b est FAUX, ou a est FAUX et B est VRAI ».
* On peut traduire « a est VRAI ET b est FAUX » par $a\land {\overline {b}}$ :
* on peut traduire « a est FAUX et B est VRAI » par ${\overline {a}}\land b$.
Donc l'équation logique de a OU EXCLUSIF b est : $(a\land {\overline {b}})\lor ({\overline {a}}\land b)$

#### Exercices sur les opérateurs logiques

N.B. : le symbole $\oplus$ est celui de l'opération OU EXCLUSIF.
Exercice 1 :
Remplissez les cases de ce tableau de vérité :
| $a$ | $b$ | ${\overline {a}}$ | ${\overline {b}}$ |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | | |
| 1 | 1 | | |
Exercice 2 :
Montrez que ${\overline {(a\land b)\lor ({\overline {a}}\land {\overline {b}})}}$ est une autre expression possible pour $a$ OU EXCLUSIF $b$.
Exercice 3 :
Donnez une expression logique pour l'opération "TRUC" dont la table de vérité est ci-dessous :
| $a$ | $b$ | $a\ {\mbox{TRUC}}\ b$ |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Montrer que l'opération "TRUC" peut aussi s'interpréter comme "a IMPLIQUE b", ou "si a est VRAI, alors b est VRAI".

### Combinaisons de portes logiques

On peut schématiser les portes logiques comme des rectangles branchés à des fils électriques. Par convention, on place les fils de sorties des portes logiques du même côté, en général à droite quand c'est possible. Une inscription sur le rectangle rappelle la fonction de la porte logique.
On peut se procurer une « boîte à outils » contenant des portes logiques, par exemple en achetant des circuits intégrés logiques de la série CMOS, ou TTL. Les schémas de portes logiques ne contiennent pas les fils d'alimentation électrique qui permettent aux portes de fonctionne. Bien évidemment, quand on réalise un montage réel avec les portes logiques, il convient de bien brancher les fils d'alimentation.

#### Notre boîte à outils « de départ »

Notre boîte à outil de départ contient les portes ET, OU et NON. La sortie de chaque porte est du côté arrondi du rectangle.
| porte ET | porte OU | porte NON |

#### Exercices avec des portes logiques : quatre pour une

Trouvez la table de vérité de la porte logique obtenue par des combinaisons ci-dessous :
Cette table de vérité permet-elle de créer une nouvelle porte pour notre « boîte à outils » ?

#### Exercices avec des portes logiques : OU EXCLUSIF

Rappeler une formule logique utilisant les opérateurs ET, OU, NON, qui permet d'obtenir l'opération OU EXCLUSIF.
Câbler cette formule logique en utilisant des portes ET, OU, NON. À partir de là, on peut considérer qu'on a rajouté une porte OU EXCLUSIF à notre boîte à outils. On l'étiquettera "OUEX".

#### Exercices avec des portes logiques : demi-additionneur à 1 bit

Voici une table d'addition pour le système binaire :
| 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0$^{*}$ |
L'étoile en exposant, dans la case en bas à droite de la table, signifie qu'il y a une retenue : « un et un fait zéro et je retiens un ».
Voici un schéma de montage qui additionne deux bits $a$ et $b$ (les chiffres binaires sont des Binary digITs), calcule le bit de somme et le bit de retenue :
Peut-on associer des montages de ce genre pour faire un additionneur qui traite les deux fois 8 bits de deux octes à additionner, d'un seul coup ? Justifier le nom "demi-additionneur" de ce circuit.

#### Exercices avec des portes logiques : additionneur complet

On trouve, publié dans Wikipedia, un schéma d'additionneur ; celui-ci se schématise comme ceci, avec notre convention de représentation des portes logiques :
Complétez la table de vérité de cette porte à trois entrées et deux sorties :
| a | b | retenue entrante |
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
Vérifier que cette porte est effectivement utilisable pour additionner des mots de plusieurs bits, en en associant autant que nécessaire.

### Exercices de programmation
#### Recherche d'entiers pairs non divisibles par trois

On veut la liste de tous les nombres pairs et non divisibles par trois compris entre 1 et 100. On utilisera l'opération "modulo", qui permet d'obtenir le reste de la division d'un nombre par un autre.
Soit $a$ la proposition "le nombre $x$ est pair". Cette proposition peut se transcrire par l'expression $x{\bmod {2}}=0$.
x "modulo 2" est nul, signifie que le reste de la division de x par 2 est nul.
Soit $b$ la proposition "le nombre $x$ n'est pas divisible par 3". On peut la transcrire par l'expression $x{\bmod {3}}\neq 0$
On peut donc utiliser l'algorithme suivant pour trouver la liste des nombres pairs non divisibles par trois :
Programmer cet algorithme dans un ou plusieurs langages et tester les programmes.

#### Recherche de nombres premiers

Problème facile
La liste des nombres premiers inférieurs à 10 est : 2, 3, 5 et 7
Écrire un algorithme qui permet de trouver la liste des nombres premiers (c'est à dire divisibles seulement par eux-même et par 1) entre 11 et 49. Programmer l'algorithme et le tester.
Problème difficile
On donne un nombre, trouver la liste des nombres premiers plus petits que celui-ci.
Écrire un algorithme, programmer, tester.

## Numérisation des données

| Savoirs : | L'ordinateur manipule uniquement des valeurs numériques. Une étape de numérisation des objets du monde physique est donc indispensable. |
| Capacités : | Coder un nombre, un caractère au travers d'un code standard, un texte sous forme d'une liste de valeurs numériques. Numériser une image ou un son sous forme d'un tableau de valeurs numériques. Modifier format, taille, contraste ou luminance d'images numériques. Filtrer et détecter des informations spécifiques. Créer une image à l'aide d'un logiciel de modélisation. |
| Observation : | Il est ici utile de faire référence à des notions technologiques introduites à propos des architectures matérielles. Les images et les sons sont choisis comme contexte applicatif et sont manipulés via des logiciels de traitement ou de synthèse. Le traitement numérique de la lumière et du son est en lien avec les principes physiques sous-jacents, qu'il est utile d'évoquer au moment voulu. |

## Signal analogique, signal numérique

Un signal analogique se présente souvent sous forme d'une tension électrique qui varie avec le temps. On dit que le signal est analogique quand n'importe quelle valeur de la tension électrique a de la signification. Un signal numérique est aussi une tension qui varie avec le temps, mais seules quelques valeurs de tension ont une signification précise.

## Numérisation d'un signal

Un convertisseur analogique numérique (CAN) reçoit en entrée un signal analogique (par exemple,le signal électrique venu d'un microphone,qui représente les variations de la pression acoustique), et un signal d'horloge. À chaque top de l'horloge, le convertisseur CAN doit présenter sur son bus de sortie une valeur binaire qui représente au mieux le signal analogique d'entrée.
Pour obtenir une numérisation de haute qualité, il faut :
* un signal d'horloge assez rapide : le nombre de tops d'horloge à chaque seconde s'appelle la fréquence d'échantillonnage ; elle doit être plus rapide que les variations typiques du signal analogique à numériser.
* une résolution suffisante pour les données en sortie : si le bus de sortie possède $n$ bits, alors il peut représenter $2^{n}$ valeurs numériques différentes.

## Un exemple de numérisation

| Graphique d'un signal analogique | Numérisation du signal | Graphique d'un signal numérique |
Dans les exemples présentés ci-dessus, la numérisation du signal analogique a été réalisée en distinguant 32 valeurs différentes (et 32 seulement : codage possible sur 5 bits) dans l'intervalle compris entre -1 V et +1 V. Un millier d'échantillons de du signal analogique ont été évalués pour effectuer la numérisation.

### Exercice : analogique/numérique

* À quoi ressemblerait le signal numérique si celui-ci était codé sur 2 bits, c'est à dire que 4 valeurs différentes seulement du signal peuvent exister ?
* Supposons que le signal numérique ait une forte résolution (par exemple 10 bits, ce qui permet 1024 valeurs significatives distinctes), mais que les échantillons soient peu nombreux. À quoi ressemblerait le signal numérisé s'il n' avait que deux échantillons numérisés pendant la durée représentée sur le graphique ?... et s'il n'y avait qu'un seul échantillon ?

## Images numériques

Les appareils photo et les caméras les plus utilisés maintenant fonctionnent avec des capteurs CCD, qui sont des matrices formées de petits rectangles sensibles à la lumière. L'électronique associé au capteur CCD échantillonne sur commande les valeur des charges électriques apparues sur chaque petit rectangle, qui dépend de la lumière reçue. La valeur de chacune de ces charges électriques est numérisée, et un tableau de valeurs numériques est enregistré dans une mémoire.
Les appareils de bonne qualité utilisent de grandes quantités de mémoire, quand les images et les vidéos sont conservées sans chercher à comprimer les données (formats de type "RAW"). De nombreux appareils grand public compriment systématiquement les données afin de pouvoir en emmagasiner plus dans la même mémoire.

### Comparaison entre formats de fichiers pour des images

| Format de fichier | BMP | XPM | PNG (couleurs indexées) | JPG |
| principales caractéristiques | non comprimé, 32 bits par pixel | non comprimé, indexé, fichier texte lisible | comprimé, sans perte | comprimé, avec des pertes |
| Taille en kilo-octets | 16,5 | 4,5 | 0,6 | 2,5 |
L'image choisie pour le tableau ci-dessus mesure $64\times 64$ pixels, elle comporte 4096 pixels indépendants. On peut remarquer que les tailles de certains fichiers non-comprimés sont prévisibles :
* format BMP : Présence d'un en-tête, plus 4 octets par pixels : $4\times 64\times 64=16384$, pour un total de 16,6 kO.
* format XPM : présence d'un en-tête, plus un octet par pixel : $1\times 64\times 64=4096$, pour un total de 4,5 kO.
Les systèmes de compression ont des efficacités variables selon le type d'image à encoder. Comme l'image choisie a un nombre limité de couleurs (huit) la compression PNG réussit très bien : le fichier pèse moins d'un kilo-octet. Le fichier JPG pèse plus du double. Observez bien les pixels de ce dernier fichier : on distingue des altérations.

### Les composantes R, V, B d'une image en couleur

Les écran et les vidéoprojecteurs connectés aux ordinateurs utilisent la synthèse additive pour créer les palettes de couleurs qui nous sont présentées.
En synthèse additive, les couleurs primaires sont rouge, vert, bleu (RVB en français, RGB en anglais).
Ci dessous, voici une table de synthèse additive pour les couleurs primaires. Les notations rgb(x,y,z) sont des triplets de valeurs permettant de donner la composition d'une lumière. Les valeurs de x, y et z sont dans un intervalle de 0 (le minimum) à 255 (le maximum). Le couleurs primaires correspondent aux notation suivantes :
* R rgb(255,0,0)
* V rgb(0,255,0)
* B rgb(0,0,255)
| $+$ | R | V | B |
| R | | J rgb(255,255,0) | M rgb(255,0,255) |
| V | J rgb(255,255,0) | | C rgb(0,255,255) |
| B | M rgb(255,0,255) | C rgb(0,255,255) | |
Le couleurs J, M, C sont respectivement le jaune, le magenta et le cyan. Le noir (N rgb(0,0,0)) est l'absence de lumière (ni R, ni V, ni B), le blanc (Bl rgb(255,255,255)) s'obtient en additionnant R, V et B.

### Transformer une image par calcul

On peut représenter les images dans un ordinateur par un tableau rectangulaire de nombres représentant chacun un pixel de l'image. Il est quelque fois commode de considérer trois tableaux de même dimension, pour les trois composantes RVB de l'image.
Des calculs appliqués aux cases du tableau rectangulaire qui représente une image permettent de créer des images nouvelles aux propriétés intéressantes.
On peut par exemple remplacer le chiffre dans chaque case par une moyenne (avec coefficients) des chiffres de cases voisines. En choisissant bien les coefficients, on peut obtenir des opérations nommées « filtres », pour simuler un flou, un flou cinétique, pour accentuer les détails, ou pour extraire les bords d'objets contrastés.

#### Un exemple d'algorithme

Les données de l'image de départ se présentent sous forme d'une table t, organisée en hauteur lignes et largeur colonnes.
Une nouvelle table t1 de même dimension est créée pour contenir la nouvelle image.
Deux boucles indicées par les variables x et y permettent de parcourir chaque pixel de la table t1, qui résulte d'un calcul basé sur les valeurs contenues dans la table t et les coordonnées (x,y). Le calcul est réalisé par la fonction nommée traitement.
Les implémentations ci-dessous utilisent une petite table nommée « filtre » contenant un jeu de coefficients. Une moyenne est faite des valeurs de pixels de la table t, en utilisant les coefficients du filtre. Cette méthode permet entre autres de flouter l'image de départ.

#### Exemple en Python
##### Exécution du programme

Voici une trace de l'exécution de ce programme dans une console :
L'image d'origine est celle- ci :
Voici les images affichées :
* le canal R de l'image :
* le canal R de l'image après application du filtre de flou :
* le canal R de l'image après application du filtre d'accentuation :
* le canal R de l'image après application des deux filtres :

#### Utilisation d'un logiciel de traitement d'image
## Les formats de données pour les ordinateurs

| Savoirs : | Les données numériques sont agencées de manière à en faciliter le stockage et le traitement. L'organisation des données numériques respecte des formats qui sont soit des standards de fait, soit des normes. |
| Capacités : | Identifier quelques formats de documents, d'images, de données sonores. Choisir un format approprié par rapport à un usage ou un besoin, à une qualité, à des limites. |
| Observation : | Le choix d'un format approprié pose le problème de l'interopérabilité, qui est le fait d'assurer un usage sans restriction des mêmes données sur un système différent. |
Pour représenter une donnée conséquente, comme une image, un son, une vidéo, un texte structuré, un plan d'architecte ... il existe plus d'une façon d'organiser les valeurs numériques qui les représentent dans un fichier. Chaque programmeur, chaque entreprise qui produit du logiciel, peuvent choisir d'utiliser un format particulier.

### Avantages d'utiliser un format non standardisé

Dans un premier temps, on peut penser que l'utilisation d'un format inconnu des autres personnes permet de se réserver l'exclusivité de l'exploitation d'un programme.
Cette idée n'est peut-être pas si forte : durant la deuxième guerre mondiale, des formats « non standardisés » très sophistiqués ont été utilisés pour l'échange entre armées allemandes. Les machines Enigma, fleurons de la technologie de cryptage, n'ont pas empêché des mathématiciens anglais, menés par Allan Turing, de casser les codes utilisés.

### Avantages d'utiliser un format standardisé

Quand un format standard est utilisé, les programmeurs peuvent se focaliser vers le développement de nombreuses applications travaillant avec ce format-là, et les échanges de données sont facilités. Si on veut protéger une donnée confidentielle encodée dans un format standard, on peut utiliser une méthode de chiffrement générique ; nous disposons de méthodes de chiffrement fortes, elles aussi standardisées.

## Formats ouverts
### Un exemple de format fermé : le DOC

Il existe des standards de fait, ça a été le cas du format DOC, utilisé par la compagnie Microsoft pour le format texte structuré. Ce format n'est pas spécifié dans un document public, ce qui n'a pas empêché de créer des lecteurs du format DOC pour les concurrents. Il y a plus d'un exemple de fichier DOC enregistré avant 1995 que le logiciel Word de Microsoft ne savait pas ouvrir en l'an 2000, et qu'on a pu récupérer à l'aide du logiciel StarOffice (fabriqué par une société concurrente), qui comportait un filtre d'importation fonctionnant correctement.

### Le format GIF

La spécification du format GIF était publiée, mais ce format n'était pas ouvert tant que son utilisation était limitée par la législation des brevets. Le dernier brevet portant sur le format GIF s'étant éteint en 2001, on peut le considérer comme ouvert maintenant.

### Liste de formats ouverts

Un format ouvert, c'est un format de fichier dont on peut trouver une spécification claire et complète, accessible librement à tous.
Utiliser des formats ouverts, c'est s'assurer que les données fabriquées aujourd'hui resteront lisibles dans le futur.
| domaine d'utilisation | nom des formats |
| représentation d'images | GIF, PNG, JPG, TIFF, TGA, XBM, XPM, MNG, ICO, PPM |
| représentation de sons | WAV, RIFF, FLA, AU, OGG |
| représentation de vidéos | Theora/Vorbis, WebM |
| représentation de textes structurés | TXT, RTF, ODT, DocBook XML, HTML, DOCX à condition que le logiciel n'utilise pas certaines « extensions » |
| Représentation de pages 2D | PS, PDF |

## Exercices
### Formats pour traiter le texte

Visitez le site de l'organisation Gutenberg et téléchargez une œuvre du domaine public de taille conséquente, à un format que vous pourriez travailler avec un traitement de texte : par exemple, le tome I de la Légende des siècles de Victor Hugo.
Ouvrez ce fichier, puis enregistrez-le aux formats suivants :
* TXT : format texte pur
* RTF :format de texte enrichi
* ODT : format texte OpenDocument
* DOC (Word 97) : format texte de Microsoft Word
* DOCX : format texte actuel de Microsoft Word
Ensuite,
* comparez les tailles de ces fichier
* essayez de les visualiser avec un simple pageur, qui permet de présenter à l'écran la suite de codes composant le fichier, en format hexadécimal et/ou décodé selon le code ASCII.
* essayez de décompresser les fichiers dont le code est « illisible » directement avec le pageur, puis examinez et décrivez lz résultat.
Note:
faites votre travail dans un répertoire séparé, pour faciliter la gestion des divers fichiers.

### Formats pour traiter le son

Trouvez un site qui permette de télécharger de la musique sous une licence Creative Commons, et récupérez un fichier représentant quelques minutes de musique au plus.
Ouvrez ce fichier à l'aide d'un éditeur de son, puis notez tous les renseignements techniques au sujet de l'encodage des sons qui y sont contenus (résolution utilisée, fréquence d'échantillonnage).
Sélectionnez un extrait de moins de trente secondes de ce fichier et jetez le reste. Enregistrez cet extrait aux formats WAV, OGG, MP3. Si possible essayez de varier les paramètres de compression quand ceux-ci sont disponibles. Comparez les tailles des fichiers enregistrés.
Fermer l'éditeur de musique, puis écouter avec attention le même extrait à l'aide d'un logiciel de rendu musical. Y a-t-il des différences qualitatives entre les écoutes des divers formats que vous aviez enregistrés ?

### Formats pour traiter des images

À l'aide d'une webcam, faites un auto-portrait, puis recadrez-le à l'aide d'un logiciel de traitement d'image, pour faire une sorte de photo d'identité. Normalisez la taille de l'image afin que sa largeur fasse environ 100 pixels (un peu comme pour faire un avatar). Ensuite, enregistrez cette photo aux formats suivants : PNG, XPM, JPG, GIF.
Des paramètres particuliers sont-ils applicables pour l'enregistrement dans certains formats ? Notez bien les paramètres choisis le cas échéant.
Après fermeture du logiciel de traitement d'image, comparez les tailles des divers fichiers. Voyez le contenu du fichier XPM à l'aide d'un éditeur de texte, comparez à d'autres formats (au format texte).
Rouvrez les images des divers fichiers et comparez finement les différences existant entre elles.
En supplément : jusqu'à quel niveau de (basse) qualité pouvez-vous dégrader votre portrait au format JPG, avant de devenir moins reconnaissable ?

### À la recherche de formats ouverts

Trouvez quels formats sont utilisables pour représenter un plan d'architecte.
Parmi ces formats, lesquels sont ouverts ? Justifiez votre sélection.

## Compression des données

| Savoirs : | Notion de compression de données. Compression avec et sans perte d'information. |
| Capacités : | Utiliser un logiciel de compression. |
| Observation : | On met en évidence l'effet de la compression d'une image ou d'un son en comparant deux systèmes de compression (avec ou sans perte). |
La plupart des données qui intéressent les humains sont très redondantes, si bien qu'on sait mettre au point des façons d'en compresser efficacement la représentation numérique.
Voici un exemple de fichier « significatif », enregistré sans compression et avec compression :
| Description du fichier | taille du fichier |
| Le fichier non comprimé (image de $300\times 150$ au format BMP) | 22934 octets |
| Le fichier comprimé (image de $300\times 150$ au format GIF) | 884 octets |
| Le fichier comprimé (image de $300\times 150$ au format PNG) | 225 octets |
| Le fichier comprimé (image de $300\times 150$ au format JPG) | 1443 octets |
L'information dans ce fichier d'image est très redondante : par exemple, la phrase en langue française ...
Un rectangle de 100 x 150 pixels accolés de gauche à droite, bleu, blanc, rouge, ne contient que 80 octets, ce qui bien encore mieux que l'encodage PNG... et on pourrait certainement faire encore mieux... Comment ?

### Exercice : examiner un fichier comprimé

Récupérez le fichier (267 octets), et voyez comment il est comprimé (utilisez un logiciel capable de prendre en charge plusieurs standards de compression). Quelle est la structure de ce fichier après décompression ?
Comparez-le au fichier (587 octets). Essayez de visualiser ce fichier à l'aide d'un logiciel approprié au format SVG (Standard Vector Graphics). La compression au format SVGZ peut-elle être considérée comme efficace ?

### Notion de compression de données

Pour comprimer un fichier, on peut faire en sorte d'y repérer des redondances, puis d'encoder les parties redondantes d'une façon plus efficace.

#### Exemple simple 1

proposez une façon simple d'encoder le texte suivant :
qui mesure 30 octets, en moins de 30 octets.
Une fois que le texte est comprimé, de quoi a-t-on besoin pour le décompresser, c'est à dire pour le rétablir à l'identique ?

#### Exemple simple 2

est une version comprimée du texte d'origine suivant :
devinez une méthode simple pour la décompression. Une fois la méthode trouvée, décompressez le code suivant :
Cette méthode de compression/décompression a des inconvénients : est-il possible de deviner facilement si on a affaire à un objet comprimé ou à un objet non comprimé ? ... Qu'obtient-on si on essaie de comprimer le texte « 164794581484 » ?

#### Quelques points communs de logiciels de compression standards

* les fichiers comprimés à l'aide de ces logiciels contiennent un signe simple permettant de suggérer le type de compression utilisé.
* les compressions se font souvent en deux temps au moins :
** repérage de redondances caractéristiques souvent constatées dans le type de fichier qu'on traite le plus souvent (par exemple, pour un texte, présence de certains mots souvent utilisés)
** utilisation d'algorithmes généraux permettant une bonne compression dans les cas généraux : algorithme de Huffmann par exemple.

### Compression avec et sans perte d'information

Dans le cas de fichiers décrivant des sons et des images, on peut obtenir d'excellents taux de compression si on admet de perdre quelques informations que les sens humains distinguent difficilement.

#### Exemple de deux fichiers de même poids, issus du même original

Voici deux versions de la même image, la première version est comprimée avec l'algorithme JPG, qui perd des informations, et la deuxième version est comprimée avec l'algorithme PNG qui ne perd pas d'information. On s'est forcé à choisir deux fichiers pesant environ le même nombre d'octets.
| fichier image au format JPG (70 kO) | fichier image au format PNG (72 kO) |
La photo de gauche semble beaucoup plus riche en information que la photo de droite, bien que son fichier soit plus léger de quelques 2 kilo-octets. Cependant, quand on y regarde de plus près, on peut apercevoir des déformations dans laphoto de gauche, qui sont dues au procédé JPG, qui change l'information initiale (et perd irrémédiablement certaines des données).

#### Mise en évidence de la perte d'information

Ci-dessous on a agrandi 8 fois les dimensions d'une petite partie de la photo enregistrée au format JPG : il apparaît de légères déformations, visibles dans la partie verte floue, au voisinage du bord du pétale. Ces déformations n'existent pas dans le fichier PNG (vérifiez-le). On peut aussi examiner l'image d'origine en haute résolution, qui pèse plus de 600 kilo-octets.
| agrandissement d'un détail de la photo qui était encodée en JPG | fichier image d'origine en haute résolution (format XCF, valide pour le logiciel libre GIMP) |

#### Concluez : avantage/désavantage de la compression avec pertes ?

Quelle est la compression préférable pour l'image,
* quand la place pour les données est limitée ? (exemple :limite à 75 kilo-octets) ;
* quand la place pour les données est moins strictement limitée ? (exemple : limite à 1 méga-octet).

## Structuration et organisation de l'information

| Savoirs : | On manipule de grandes quantités d'informations. Il est nécessaire de les organiser. |
| Capacités : | Classer des informations, notamment sous forme d'une arborescence. |
| Observation : | On peut ici étudier le système d'organisation de fichiers en dossiers. Un ensemble de documents unis par des liens hypertextes fournit un exemple de classement de type graphe. |
Imaginez une encyclopédie de cinq mille pages, dont les articles ne seraient pas ordonnés, elle serait difficilement utilisable pour y retrouver un article en particulier.
Les dictionnaires et encyclopédies possèdent une organisation, le classement par ordre alphabétique du mot qui y est défini ou illustré. Cette organisation est cependant insuffisante pour de nombreux exemples de recherches. Comment feriez-vous par exemple, pour trouver rapidement tous les mots du dictionnaire qui s'écrivent en quatre lettres ?
Pour faciliter les recherches dans une encyclopédie, on utilise des index ; il peut exister plus d'un index pour la même encyclopédie, qu'on utilisera dans des circonstances différentes.

### Systèmes de classifications efficaces

Quand on peut définir une relation d'ordre dans une collection d'articles, on peut trier les articles. S'il y a plus d'une relation d'ordre, c'est préférable de réaliser un index pour chacune des relations. Les index les plus efficaces ont une structure d'arbres binaires.

#### Exemple trivial de classement

Prenons comme « articles » les lettres de l'alphabet, et comme ordre, l'ordre alphabétique.
Un index séquentiel évident est :
On peut préférer un index arborescent :

#### Supériorité de l'index organisé en arbre

Si on veut faire un traitement automatique des informations, on peut se préoccuper de la durée du traitement.
Comparons les durées de classement d'un lettre de l'alphabet tirée au hasard, en supposant que la durée augmente comme le nombre de comparaisons alphabétiques à faire :
* pour l'index séquentiel, ça peut aller très vite (si on doit classer un A) ou 26 fois plus lentement (si on doit classer un Z). On peut supposer qu'en moyenne, on doit faire 13 comparaisons ;
* pour l'index arborescent, on doit faire entre 4 et 5 comparaisons (moyenne 4,5).
L'avantage de l'index arborescent devient de plus en plus évident quand on dispose d'un grand nombre de données à classer :
* pour un index séquentiel, la durée moyenne de classement double quand le nombre de données double. Par exemple pour un million de données, on fait en moyenne un demi-million de comparaisons pour classer un nouvel article.
* pour un index arborescent, il suffit d'une comparaison de plus chaque fois que le nombre de données est doublé. Pour un million de données, une vingtaine de comparaisons est suffisante !

### Organisations en arbre souvent utilisées
#### Systèmes de fichiers : répertoires et fichiers

Les disques durs utilisés en 2013 contiennent couramment des centaines de giga-octets, c'est à dire,
* quelques centaines de films, ou
* quelques millions de photos,
* quelques milliards de pages imprimables,
* etc.
Pour arriver à maintenir de telles collections de données, une simple liste séquentielle est tout à fait inappropriée.
Un système d'arbre est utilisé : les répertoires (ou dossiers) sont les nœuds de l'arbre, les fichiers sont les feuilles.
Dans les systèmes de fichiers Unix et Mac OS, un seul arbre permet de regrouper tous les fichiers. Pour Windows, il peut y avoir 26 arbres distincts, correspondant à autant de « lecteurs différents », nommés de A: à Z:.

#### Les index de bases de données

Les systèmes de gestion de base de données relationnelles (MySQL, PostgreSQL, Oracle, Access) permettent de définir des index pour permettre un accès plus rapide aux données. Créer un index est utile pour tous les champs qui peuvent faire l'objet d'une recherche : l'exemple trivial ci-dessus montre qu'un index semble « rentable » dès qu'on a plus de huit articles différents à gérer.

### Exercices
#### Compter les fichiers de votre ordinateur

Documentez-vous sur la commande find, puis trouvez une façon de compter le nombre de fichiers existant sur le disque dur de votre ordinateur.
Astuces :
* on peut renvoyer la sortie de find vers un fichier, puis compter les lignes de ce fichier à l'aide d'un éditeur de texte.
* il est possible d'utiliser la commande wc.

#### Déterminez la profondeur maximale de l'arbre de votre système de fichiers

Cette profondeur peut être trouvée en retraitant le fichier contenant la sortie de la commande find précédente, en comptant le nombre de caractères « séparateurs » de chemin dans les noms de fichier : le slash pour Unix, l'antislash pour Windows ...
Voici une ligne de commande Unix qui permet d'afficher le nombre de répertoires/fichier le long d'un chemin, pour chaque ligne du fichier find.txt qu'on aura fabriqué à l'exercice précédent :
La commande cat permet de dérouler le contenu d'un fichier ; la barre verticale | sert à « piper » (en mauvais franglais), c'est à dire à « tuyauter » le flux de sortie de la commande cat dans l'entrée standard de la commande awk.
Lisez la page de manuel de la commande awk, pour trouver la signification de l'option "-F /", et la signification de la variable NF.
Astuces :
Utilisez les commandes sort et uniq (après avoir consulté leurs pages de manuel) pour clarifier le résultat de la commande awk.

## Persistance de l'information

| Savoirs : | Les données, notamment personnelles, sont susceptibles d'être mémorisées pour de longues périodes sans maîtrise par les personnes concernées. |
| Capacités : | Prendre conscience de la persistance de l'information sur les espaces numériques interconnectés. Comprendre les principes généraux permettant de se comporter de façon responsable par rapport au droit des personnes dans les espaces numériques. |
| Observation : | La persistance de l'information se manifeste tout particulièrement au sein des disques durs mais aussi des mémoires caches. Elle interagit avec le droit à la vie privée et fait naître une revendication du « droit à l'oubli ». |

### Exercices

Votre grand-père ou votre grand-mère veut créer une page « Feacebouqué », mais ils ne savent pas très bien comment faire, et ont entendu qu'il faut se méfier quand même de ne pas faire n'importe quoi.
* Rédigez dans un langage soutenu une suite de recommandations à votre grand-père ou à votre grand-mère, pour leur permettre de garder le contrôle sur les informations qu'ils présenteront au public.
* Cherchez dans le passé récent des cas où des données personnelles ont été dévoilées à tort, avec des conséquences indésirables. Rédigez un court signalement d'un de ces cas.
* Les organismes français qui conservent des données personnelles sur vous sont censés obéir à la loi « Informatique et Libertés ». Cette loi les oblige à vous communiquer les données qui vous concernent si vous le leur demandez. Choisissez un de ces organismes et demandez la communication des données qui vous concernent (vous pouvez arguer du fait que vous faites cette démarche dans le cadre de vos enseignements obligatoires).

## La non-rivalité de l'information

| Savoirs : | Existence de lois régissant la détention et la circulation de données numériques. |
| Capacités : | Prendre conscience de la non-rivalité des biens immatériels. Distinguer différents types de licences (libres, propriétaires). |
| Observation : | La non-rivalité d'un bien se définit par le fait que son usage par une personne n'en limite pas l'usage par d'autres (ainsi, le poste de radio est rival mais l'émission ne l'est pas). À l'occasion d'exposés suivis de débats, on sensibilise les élèves à l'évolution des valeurs et du droit (en France et ailleurs) induite par l'émergence de biens immatériels. |

# Algorithmique

* Un algorithme se définit comme une méthode opérationnelle permettant de résoudre, en un nombre fini d'étapes clairement spécifiées, toutes les instances d'un problème donné. Cette méthode peut être exécutée par une machine ou par une personne.
* Les élèves ont été confrontés aux algorithmes très tôt dans leur parcours scolaire (avec les quatre opérations arithmétiques) et régulièrement de nouvelles situations de nature algorithmique leur ont été proposées ; ainsi, la construction de figures en géométrie euclidienne, la transcription des « formules » moléculaires en chimie, le code génétique ou encore l'analyse fonctionnelle en technologie sont autant de situations évoquant des algorithmes. Les programmes de mathématiques des classes de seconde et première contiennent une initiation à l'algorithmique sur laquelle il convient de s'appuyer.
* À travers l'étude de quelques algorithmes, on développe la faculté de lire et comprendre un algorithme conçu par d'autres, puis d'en concevoir de nouveaux. Ces algorithmes sont exprimés dans un langage de programmation et exécutés sur une machine ou bien définis de manière informelle.
* Source : programme officiel (www.education.gouv.fr/...bo=57572)
* Les prochaines citations de ce programme officiel seront signalées par le logo suivant :

## Algorithmes simples

| Savoirs : | rechercher un élément dans un tableau trié par une méthode dichotomique ; trier un tableau par sélection ; ajouter deux entiers exprimés en binaire. |
| Capacités : | Comprendre un algorithme et expliquer ce qu'il fait. Modifier un algorithme existant pour obtenir un résultat différent. Concevoir un algorithme. Programmer un algorithme. S'interroger sur l'efficacité d'un algorithme. |
| Observation : | On présente simultanément les notions d'algorithme et de programme, puis on les distingue. L'objectif est une compréhension de ces algorithmes et la capacité à les mettre en œuvre. Les situations produisant une erreur (division par zéro, dépassement de capacité) sont mises en évidence. |

## Algorithmes plus avancés

| Savoirs : | tri par fusion ; recherche d'un chemin dans un graphe par un parcours en profondeur (DFS) ; recherche d'un plus court chemin par un parcours en largeur (BFS). |
| Capacités : | Comprendre et expliquer (oralement ou par écrit) ce que fait un algorithme. S'interroger sur l'efficacité d'un algorithme. |
| Observation : | L'objectif se limite à une compréhension des principes fondamentaux sans exiger leur programmation. |

# Langages et programmation

* La programmation est l'expression d'un algorithme dans un langage exécutable par une machine et joue un rôle central dans le développement des systèmes et produits informatiques.
* L'apprentissage de la programmation vise d'une part à savoir programmer un algorithme décrit en langue naturelle et d'autre part à comprendre un programme et exprimer en langue naturelle l'algorithme sous-jacent.
* On commence par rappeler les éléments de base de tout langage de programmation (affectation, séquence, test et boucle) tels qu'ils ont été présentés en mathématiques en classe de seconde et consolidés en classe de première. On introduit alors la notion de fonction qui permet d'éviter des redondances, de structurer les programmes et d'organiser leur conception. Enfin, on met en évidence la qualité des programmes en les testant sur différents jeux de données.
* On insiste sur la clarté et la documentation qui facilitent la reprise du code par d'autres programmeurs. On montre enfin l'universalité de la notion de langage au-delà de la programmation.
* L'enseignant choisit un langage de programmation selon les critères suivants : simplicité d'utilisation, liberté d'installation, présence d'outils associés, existence d'une communauté d'utilisateurs et de bibliothèques facilitant le développement.
* Source : programme officiel (www.education.gouv.fr/...bo=57572)
* Les prochaines citations de ce programme officiel seront signalées par le logo suivant :

## Types de données

| Savoirs : | nombre entier ; virgule flottante ; booléen ; caractère ; tableau ; chaîne de caractères. |
| Capacités : | Choisir un type de donnée en fonction d'un problème à résoudre. |
| Observation : | On adapte la présentation de ces notions en fonction du langage de programmation retenu. |

## Pourquoi typer des données

Dans un ordinateur, tout est représenté par des uns et des zéros. Alors, pourquoi vouloir distinguer des types de données ?
Pour l'essentiel, c'est une question de codage !
Prenons l'exemple du nombre $01000001_{\mbox{bin}}$, il pourrait représenter :

### un entier court,

    le nombre décimal 65, codé sur un seul octet ;

### un réglage particulier d'options (tableau booléen),

    supposons 8 options de personnalisation d'une automobile vraies ou fausses, par exemple :
| toit ouvrant | freinage assisté | GPS intégré | lecteur multimedia MP3 | jantes larges | couleur métallisée | système de détection de collision | assistance au créneau |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |

### un caractère ASCII,

    ici, c'est le « A » ;
Pour des données plus longues, il existe de nombreuses autres interprétations possibles. Décider quel codage s'applique, c'est typer la donnée.

## Bien connaître les types de données

Si on ignore les types de données, des bugs étranges et incompréhensibles peuvent se produire.

### Le type entier

Selon les ordinateurs et les systèmes utilisés, un entier peut être codé sur une longueur fixe :

#### 1 octet (8 bits)

    il est dans l'intervalle [0, 255] (entier non signé), ou dans l'intervalle [-128, 127] (entier signé)

#### 2 octets (16 bits)

    il est dans l'intervalle [0, 65535] (entier non signé), ou dans l'intervalle [-32768, 32767] (entier signé)
Exercice
Quelles sont les limites qui concernent la représentation d'un entier sur 64 bits ?
Des bibliothèques de programmes existent pour faire du calcul en précision arbitraire. Dans ce cas, un entier peut être représenté par un nombre variable d'octets, selon les besoins.

### Le type virgule flottante

Un ordinateur n'utilise que des zéros et et des uns. Même si vous utilisez plusieurs giga-octets pour représenter un nombre tel que $\pi$ ou ${\sqrt {2}}$, la représentation sera toujours fausse.
On représente donc les nombres « réels » par une suite limitée de chiffre binaires. Un type à virgule flottante contient quelques bits pour donner l'ordre de grandeur (un exposant positif ou négatif pour faire une puissance de deux), et un nombre entier qui est multiplié par cette puissance de deux.
Extrait de l'article Virgule flottante de Wikipedia
| | Encodage | Signe | Exposant | Mantisse | Valeur d'un nombre | Précision | Chiffres significatifs |
| Simple précision | 32 bits | 1 bit | 8 bits | 23 bits | $(-1)^{S}\times M\times 2^{(E-127)}$ | 24 bits | environ 7 |
| Double précision | 64 bits | 1 bit | 11 bits | 52 bits | $(-1)^{S}\times M\times 2^{(E-1023)}$ | 53 bits | environ 16 |

### Le type booléen

Il s'agit d'un type de donnée qui ne peut avoir que deux valeurs différentes : vrai/faux ou 1/0.
La plupart des ordinateurs n'ont de mécanismes simples que pour accéder à des octets ; alors, il arrive que les valeurs vrai/faux soient encodées par les octets 11111111 et 00000000. Ce n'est pas un problème pour des systèmes riches en mémoire. Pour des micro-systèmes disposant d'une mémoire très limitée, il peut être bon de considérer des méthodes d'empaquetage de plusieurs booléens dans un seul octet, pour économiser une ressource précieuse.

### Le type caractère

Le tableau suivant résument l'encodage de caractères non accentués, du code ASCII (début de l'UNICODE). Il a été adapté d'une page de Wikipedia.
Pour connaître le code d'un caractère, prendre le chiffre hexadécimal en début de ligne, puis le chiffre hexadécimal en tête de colonne. Par exemple, 0041 est le code hexadécimal du caractère « A »
Évidemment, ce ne sont pas les seuls caractères qu'on ait à encoder dans le monde.

### Le type tableau

Le type tableau se présente le plus souvent dans la mémoire de l'ordinateur comme une succession de données du même type (entiers, ou flottants, etc...), les unes à la suite des autres.
La particularité du tableau c'est qu'on doit pouvoir accéder à une des « cases » de ce tableau en donnant sont « index » : un seul numéro (tableaux à une dimension), ou plusieurs (tableaux à plusieurs dimensions).

### Le type chaîne de caractères

Une chaîne de caractères, ça peut être implémenté comme un tableau de caractères.
Dans certains cas, cependant, on préfère réserver une code particulier qui signifie « fin de la chaîne de caractères ». Par exemple, en langage C, le premier octet nul marque la fin de la chaîne de caractères.
Une autre méthode (utilisée par certains langages Pascal), consiste à coder tout au début de la chaîne un entier qui représente la longueur de la chaîne de caractères.
Exercice
* Trouver au moins un inconvénient de la méthode du caractère terminal (pensez à ce qui se passe si à la suite d'un bug, ce caractère disparaît);
* Trouver au moins un inconvénient de la méthode de longueur encodée en début de chaîne.

## Fonctions

| Savoirs : | notion de fonction ; portée des variables et passage d'arguments ; définition récursive de fonctions. |
| Capacités : | Concevoir l'entête (ou l'interface) d'une fonction, puis la fonction elle-même. |
| Observation : | On adapte la présentation de ces notions en fonction du langage de programmation retenu. |

## Correction d'un programme

| Savoirs : | test ; instrumentation ; situations d'erreur ou bugs. |
| Capacités : | Mettre un programme au point en le testant, en l'instrumentant. Utiliser un outil de mise au point. |
| Observation : | On évoque les risques issus des programmes incorrects et des bugs qui en résultent, aux conséquences parfois graves. |

## Langages de description

| Savoirs : | Présentation du langage HTML et du principe de séparation du contenu et de la mise en forme. |
| Capacités : | Créer et analyser une page web en langage HTML. |
| Observation : | On met en valeur le double usage du langage, lisible par un humain et interprétable par une machine. On utilise HTML pour écrire une page « à la main », puis on insiste sur le fait que ce langage sert aussi de cible à des générateurs de pages. On évalue la qualité des pages du point de vue de la correction syntaxique et de l'efficacité du message. |

# Architectures matérielles

* Exprimer un algorithme dans un langage de programmation a pour but de le rendre exécutable par une machine numérique. La découverte de l'architecture de ces machines constitue une étape essentielle d'une initiation à l'informatique. De plus, mieux comprendre cette organisation est nécessaire pour programmer de manière efficace, en tenant compte des capacités et limitations des machines numériques.
* La progression pédagogique suit la chronologie du développement des systèmes informatiques : d'abord centralisés autour des machines à accès direct, ensuite connectés par l'intermédiaire d'une liaison série point à point et enfin répartis grâce aux réseaux où le transport des informations repose sur des méthodes de routage. Le développement de ces réseaux et leur utilisation massive ont induit des questions sociétales majeures qu'il est préférable d'aborder sous forme d'activités pluridisciplinaires. Finalement, l'étude d'un minirobot permet de découvrir les mécanismes de pilotage et de communication dans l'exécution de tâches complexes, interférant directement avec le monde physique.
* Source : programme officiel (www.education.gouv.fr/...bo=57572)
* Les prochaines citations de ce programme officiel seront signalées par le logo suivant :
ISN Architecture des ordinateurs

### Éléments d'architecture

| Savoirs : | Composants de base (unité centrale, mémoires, périphériques). |
| Capacités : | Expliquer le rôle des constituants d'un ordinateur. |
| Observation : | On se limite à une présentation générale de ces concepts autour d'une machine à accès direct (Random Access Machine). |

### Jeu d'instructions

| Savoirs : | Instructions simples (chargement, stockage, opérations arithmétiques et logiques, saut conditionnel). |
| Capacités : | Savoir dérouler l'exécution d'une séquence d'instructions simples de type langage machine. |
| Observation : | On propose des activités sous forme d'exercices sur papier sans utiliser d'ordinateur. |
ISN Réseaux

### Transmission point à point

| Savoirs : | Principes de base d'une transmission d'informations numériques entre un émetteur et un récepteur. |
| Capacités : | Établir une communication sérielle entre deux machines. |
| Observation : | On s'interroge sur la qualité d'une liaison série point à point. On se limite à l'analyse d'un trafic de type « chat » (échange de caractères codés). On introduit la notion de protocole (règles, formats et conventions, sur lesquels il est nécessaire de s'accorder pour communiquer). Au-delà de deux machines, le modèle de la liaison point à point ne convient plus. |

### Adressage sur un réseau

| Savoirs : | Mécanismes d'adressage pour identifier des machines distantes. |
| Capacités : | Décrire une situation d'adressage sur un type de réseau particulier. Analyser le trafic (trames) sur un réseau et mettre ainsi en évidence la notion de protocole. |
| Observation : | On introduit ces notions en comparant différents types d'adressages existants (téléphone, courrier postal). On fait appel à un outil d'analyse pour visualiser la transmission des trames nécessaires au dialogue entre machines numériques. |

### Routage

| Savoirs : | Mécanismes induits par la communication sur un réseau dont la structure est de type graphe. Notions de paquets, de chemins, de routage. |
| Capacités : | Analyser les entêtes de messages électroniques, pour décrire le chemin suivi par l'information. |
| Observation : | On se limite à la mise en œuvre d'une séance de travaux pratiques, avec analyse d'entêtes de courriels prédéfinis reçus (aspect distribué et non fiable des réseaux de grande taille, difficulté du passage à l'échelle). On explique la différence entre les réseaux de type arborescent et de type graphe. |

### La supranationalité des réseaux

| Savoirs : | Supranationalité des réseaux |
| Capacités : | Prendre conscience du caractère supranational des réseaux et des conséquences sociales, économiques et politiques qui en découlent. |
| Observation : | On met en évidence le fait que certains pays autorisent la mise en ligne d'informations, services ou contenus numériques dont la consultation n'est pas permise dans d'autres pays. |
ISN Initiation à la robotique

### Découverte d'un système robotique et de sa programmation

| Savoirs : | Découverte d'un système robotique et de sa programmation |
| Capacités : | Identifier les différents composants d'un minirobot et comprendre leurs rôles respectifs. Décrire un système à événements simple à l'aide d'une machine à états finis. Programmer (dans un langage de haut niveau) un minirobot pour lui faire exécuter une tâche complexe. |
| Observation : | On propose des activités adaptées aux équipements et logiciels disponibles dans l'établissement. |