Fundamentals of Computer Science

Ce document aborde les concepts fondamentaux de l'informatique, depuis son histoire et ses définitions clés jusqu'aux principes de programmation, en passant par la représentation des données, l'algèbre de Boole, l'architecture des ordinateurs et les algorithmes. Il offre une base solide pour comprendre le fonctionnement des systèmes informatiques et la logique derrière leur conception.

1. Introduction

1.1 Historique

L'histoire de l'informatique est marquée par l'évolution des outils de calcul, des simples dispositifs manuels aux ordinateurs électroniques complexes.

Appareils de calcul simples

• Abacus: Apparu vers 1100 av. J.-C. dans la région indo-chinoise. Utilisé pour l'addition, la soustraction, la multiplication, la division et l'extraction de racines carrées et cubiques.
• Règle à calcul: Inventée en 1622 par le mathématicien anglais William Oughtred. Adaptée aux opérations arithmétiques de base (principalement multiplication/division) et à des calculs plus complexes.

Machines à calculer

• 1623: William Schickard décrit la première machine à calculer, incluant un additeur/soustracteur et un dispositif pour multiplier et diviser.
• 1643: Blaise Pascal développe la "Pascaline", sa machine à calculer.
• 1673: Gottfried Wilhelm Leibniz présente sa machine à pas, le premier calculateur presque fonctionnel.
• 1703: Leibniz invente également le système de nombres binaires.

Développement de l'ordinateur

• 1805: Joseph-Marie Jacquard conçoit des métiers à tisser programmables par cartes perforées.
• 1820: Charles Babbage développe sa "machine à différences" et conceptualise une "machine analytique".
• 1843: George Scheutz crée le premier ordinateur mécanique basé sur les idées de Babbage. Ada Lovelace développe simultanément la première méthode de programmation pour les machines de Babbage, écrivant ainsi le premier programme informatique.
• 1890: Le recensement américain est effectué à l'aide du système de cartes perforées de Herman Hollerith.

L'ère des ordinateurs modernes

• 1935: IBM présente l'IBM 601, capable d'une multiplication par seconde.
• 1938: Konrad Zuse présente le calculateur programmable Zuse Z1, qui gère déjà l'arithmétique flottante.
• 1941: Le calculateur à relais Zuse Z3 peut exécuter tout algorithme dans les limites de sa mémoire, étant ainsi considéré comme le premier ordinateur au sens moderne et marquant la transition vers les machines électromécaniques/électroniques.
• 1941: L'Atanasoff-Berry-Computer, le premier ordinateur électronique, est conçu pour résoudre de grands systèmes d'équations linéaires (non librement programmable).
• 1943: Le calculateur à lampes Colossus est utilisé à Bletchley Park en Angleterre pour déchiffrer les messages allemands (avec Lorenz SZ40). Composé de 1500 tubes, il traite 5000 caractères par seconde.
• 1946: L'ENIAC, développé pour l'armée américaine, est le premier calculateur numérique universel entièrement électronique. Il comprend 17 468 tubes électroniques, 7 200 diodes, 1 500 relais, 70 000 résistances et 10 000 condensateurs, pèse 27 tonnes et consomme 174 kW.
• 1945: L'EDVAC, conçu par l'équipe de l'ENIAC, est le premier ordinateur basé sur l'architecture de Von Neumann, utilisé pour les calculs de la bombe à hydrogène.
• 1953: Le TRADIC est le premier ordinateur entièrement construit à partir de transistors (10 000 diodes, 800 transistors, 100W de consommation).
• 1960: Le DEC PDP-1, le premier mini-ordinateur (de la taille de deux réfrigérateurs), utilise l'assembleur ou Lisp.

L'ère des ordinateurs personnels

• 1968: Le HP 9100A, le premier ordinateur personnel (PC), coûte environ 5000 USD (un salaire annuel brut de l'époque) et dispose d'une mémoire de base magnétique pour 196 lignes de programme.
• 1971: Intel développe le 4004, le premier CPU sur puce (IC) avec 2300 transistors.
• 1973: Le Xerox Alto est le premier ordinateur avec une souris, une interface utilisateur graphique et une carte Ethernet intégrée.
• 1975/76: Apple Computer lance l'Apple I/II (CPU: 6502), suivi par d'autres comme le Commodore PET et l'Atari 400/800.
• 1981: Premiers ordinateurs domestiques (Commodore VC20, C64, Sinclair ZX Spectrum, Schneider CPC). IBM développe parallèlement l'IBM-PC.
• 1982: Le Sun-1, la première station de travail Unix, suivi par Apollo, DEC, HP, etc.
• 1985: Premiers ordinateurs domestiques 16 bits (Atari ST, Commodore Amiga) avec interfaces graphiques et multitâche préemptif (dix ans avant Windows 95). Apple lance parallèlement le Macintosh.
• 1988: Steve Jobs présente le NeXTCube. Sur cette machine, Tim Berners-Lee développe en 1989 le premier navigateur web et le serveur associé.

Le 21ème siècle

• Les années 90 sont marquées par le développement d'Internet et l'architecture client-serveur. Les PC/stations de travail voient l'émergence de processeurs 64 bits puissants (SPARC, Pentium Pro, AMD Athlon). Les coûteuses stations de travail Unix sont progressivement remplacées par des systèmes Linux compatibles PC. Windows s'impose comme le standard de facto pour les systèmes d'exploitation de bureau, tandis que les systèmes Unix continuent de dominer le secteur des serveurs.
• Au 21e siècle, l'ordinateur s'est intégré dans presque tous les aspects de la vie. Après le passage d'Apple aux processeurs Intel, les systèmes Mac OS X gagnent en importance (environ 8-10% de part de marché). La tendance générale est aux processeurs multicœurs, au traitement parallèle et à la virtualisation.
• Émergence de systèmes informatiques miniaturisés et économes en énergie pour les applications mobiles et embarquées.
  • Exemples:
    • Raspberry Pi: Système Linux complet avec lecteur MicroSD, USB, Ethernet, E/S numérique et analogique, module GSM optionnel, récepteur GPS.
    • FXI CottonCandyStick: ARM® Cortex™-A9@1.2GHz, 1 Go de RAM, MicroSD, Wifi, Bluetooth, USB, HDMI. GPU Quad Core ARM Mali-400MP. OS: Ubuntu, Android.

Citations célèbres

« Il n'y a aucune raison pour que quelqu'un veuille avoir un ordinateur à la maison. »
Ken Olson, Président et fondateur de DEC, 1977

« Je crois qu'il y aura un besoin d'environ cinq ordinateurs dans le monde. »
Thomas J. Watson, PDG d'IBM, 1943

« L'ordinateur est l'évolution logique de l'être humain : l'intelligence sans la morale. »
John Osborne, dramaturge anglais, 1924

« L'ordinateur est une grande invention. Il y a autant d'erreurs qu'avant. Mais personne n'est à blâmer. »
Auteur inconnu

« 640K devraient suffire à tout le monde. »
Bill Gates, 1981

1.2 Définitions des termes

Pour comprendre l'informatique, il est crucial de définir certains concepts fondamentaux tels que les données, l'information et les différentes branches de l'informatique.

Données et Informations

• Données: En général, des unités d'information regroupées logiquement. En informatique, ce sont des séquences de caractères auxquelles un contenu significatif est attribué, comme des nombres, des sons, des images, etc.
• Information: Les données deviennent des informations lorsqu'un contenu significatif leur est attribué.
• Traitement de données (TD): Le traitement de données désigne la transformation ciblée de grandes quantités de données par des humains ou des machines selon une procédure prédéfinie. Il s'agit en réalité de traitement d'informations.

Types d'informatique

L'informatique peut être divisée en plusieurs domaines spécialisés:

• Informatique Théorique: Se concentre sur l'abstraction et la modélisation. Ses sous-domaines incluent la théorie des automates, la théorie des algorithmes, la calculabilité, la théorie de la complexité et la construction de langages formels.
• Informatique Pratique: Gère la mise en œuvre concrète des concepts informatiques. Elle comprend les algorithmes, les structures de données, les systèmes d'exploitation, les bases de données, les langages de programmation et le génie logiciel.
• Informatique Technique: Concerne la construction du matériel informatique, en particulier l'ingénierie numérique, l'ingénierie réseau, l'automatisation et les systèmes temps réel.
• Informatique Appliquée: Applique l'informatique théorique, pratique et technique pour produire des systèmes informatiques et des produits logiciels.

2. Données et leur représentation

La manière dont les données sont représentées et stockées est fondamentale en informatique, incluant les systèmes de numération, l'encodage des caractères, la compression et la sécurité des données.

2.1 Représentation des nombres et des caractères

En informatique, les nombres et les caractères sont représentés de différentes manières, au-delà du système décimal habituel.

Nombres binaires (dual)

C'est le système de base pour les ordinateurs.

• Principes fondamentaux: Nous sommes habitués à représenter les nombres dans le système décimal, basé sur les chiffres 0 à 9, avec une base 10. Par exemple, 275 est interprété comme $2 \times 10^2 + 7 \times 10^1 + 5 \times 10^0$. De manière analogue, le système binaire (dual), avec une base 2, utilise seulement les chiffres 0 et 1. Par exemple, 1011 en binaire équivaut à $1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0$. Pour éviter toute ambiguïté, la base est ajoutée en indice, par exemple $275_{10}$ ou $1011_2$.
• Conversion:
  • Vers le système décimal (méthode de multiplication): On part du chiffre le plus significatif, on multiplie par la base (ici $B=2$) et on ajoute le chiffre suivant à chaque étape.

    Exemple: $1011_2 = ((1 \times 2 + 0) \times 2 + 1) \times 2 + 1 = (2 \times 2 + 1) \times 2 + 1 = (4+1) \times 2 + 1 = 5 \times 2 + 1 = 11_{10}$.

  • Depuis le système décimal (méthode de division): On divise de manière répétée par la base du système cible ($B=2$). Le reste de chaque division est un chiffre du nombre résultant, en commençant par le chiffre le moins significatif (LSB).

    $11 : 2 = 5$	Reste	1 (LSB)
    $5 : 2 = 2$	Reste	1
    $2 : 2 = 1$	Reste	0
    $1 : 2 = 0$	Reste	1 (MSB)

    Donc, $11_{10} = 1011_2$.

• Avantages:
  1. Deux états (0 et 1) sont facilement distinguables et stockables (bascules, cartes perforées, CD, DVD).
  2. Les calculs avec des nombres binaires sont très simples, ce qui permet de construire des machines de calcul (ordinateurs) relativement facilement.

Toutes les informations dans un ordinateur sont représentées en binaire (avec deux symboles différents). Un emplacement binaire est appelé 1 Bit (abréviation de binary digit). 8 Bits forment 1 Octect ou 1 Byte.

• $2^{10}$ Bytes = 1024 Bytes = 1 Kibibyte (KiB)
• $2^{20}$ Bytes = 1024 x 1024 Bytes = 1 Mebibyte (MiB)
• $2^{30}$ Bytes = 1024 x 1024 x 1024 Bytes = 1 Gibibyte (GiB)
• $2^{40}$ Bytes = 1024 x 1024 x 1024 x 1024 Bytes = 1 Tebibyte (TiB)

L'appellation traditionnelle de kilobyte pour 1024 Bytes est invalide depuis 1999 selon l'IEC et désigne désormais (conformément au SI) 1000 Bytes.

• $10^3$ Bytes = 1000 Bytes = 1 Kilobyte (kB) [2,4% de différence avec KiB]
• $10^6$ Bytes = 1000 x 1000 Bytes = 1 Megabyte (MB) [4,9% de différence avec MiB]
• $10^9$ Bytes = 1000 x 1000 x 1000 Bytes = 1 Gigabyte (GB) [7,4% de différence avec GiB]
• $10^{12}$ Bytes = 1000 x 1000 x 1000 x 1000 Bytes = 1 Terabyte (TB) [10% de différence avec TiB]

Terminologie des Bits:

Désignation	Remarques	Bits
Bit	0 ou 1	1
Nibble	aussi demi-octet, tétrade	4
Byte	aussi octet	8
Mot	La largeur dépend de l'architecture	16
Double mot	Aussi DWord	32

• Addition de nombres binaires: Les nombres binaires s'additionnent de la même manière que les nombres décimaux.

  $29_{10}$	$11101_2$
  $+ 11_{10}$	$+ 1011_2$
  $= 40_{10}$	$= 101000_2$

  Toutes les autres opérations arithmétiques peuvent être réduites à l'addition pour les nombres binaires.
• Nombres binaires négatifs (complément à deux): Pour former un nombre binaire négatif, on inverse chaque bit (complément à un) et on ajoute 1 (complément à deux). La longueur des bits doit être déterminée à l'avance. Le complément à deux offre l'avantage d'une définition unique de zéro et simplifie les calculs.

  Procédure pour les nombres binaires signés:

  1. Ignorer le signe et convertir la valeur absolue en binaire.
  2. Remplir toutes les nombres avec des 0 au bit le plus significatif (MSB) pour obtenir la même longueur.
  3. Insérer un 0 supplémentaire (correspondant à +) au MSB.
  4. Pour tous les nombres négatifs, former le complément à deux.

  Exemple de soustraction vue comme une addition d'un nombre négatif:

  $40_{10}$

  $+ (-11_{10})$

  $= 29_{10}$

  En binaire avec complément à deux:

  $00101000_2$

  $+ 11110101_2$

  $= 00011101_2$

• Multiplication de nombres binaires: Puisqu'on ne multiplie que par 0 ou 1, la multiplication binaire peut être réduite à une addition.

  $10101 \times 101$	$10101$
  	$10101$ (décalage à droite)
  $=$	$1101001$

  • Cas particuliers: Multiplication par 2 = décalage à gauche; Division par 2 = décalage à droite.
  • Pour construire une machine de calcul binaire, il faut implémenter l'addition, l'inversion de bits individuels et le "décalage".

Nombres hexadécimaux

Pour contrer le désavantage des nombres binaires, qui deviennent rapidement longs et illisibles, le système hexadécimal (base 16) est utilisé. Il utilise les chiffres 0-9 et les lettres A-F. Chaque chiffre hexadécimal correspond exactement à 4 chiffres binaires.

Hexadécimal:	Binaire:
0	0
...	...
9	1001
A (10)	1010
B (11)	1011
C (12)	1100
D (13)	1101
E (14)	1110
F (15)	1111
10 (16)	10000
...	...

Exemple: au lieu de $11111111111111110000000000011010_2$, on écrit FFFF:001A en hexadécimal.

Codage

Le concept de codage fait référence à la transformation d'un caractère d'un jeu de caractères A (par ex. 1111 binaire) en un caractère d'un jeu de caractères B (par ex. F hexadécimal). L'opération inverse (décodage) est également possible.

Codages fréquemment utilisés:

• Code binaire
• Code hexadécimal
• Code octal
• Code Gray
• Code BCD

• Code octal: Similaire au code hexadécimal, 3 bits binaires sont regroupés pour former un chiffre octal. Les chiffres 0 à 7 sont utilisés. Chaque chiffre octal correspond à 3 chiffres binaires.

  Octal:	Binaire:
  0	0
  ...	...
  7	111
  10	1000
  ...	...

• Code Gray: Utilisé en technologie numérique, ce code a la propriété que les mots de code adjacents ne diffèrent que par un seul bit. Cela augmente la robustesse du code face aux erreurs de synchronisation. Le code Gray à 4 bits montré est cyclique, ce qui signifie qu'une seule position change même lors du passage du nombre le plus élevé au plus petit.

  Code Gray:	Binaire:
  0000	0
  0001	1
  ...	...
  1000	1111

• Code BCD (Binary Coded Decimal): Chaque chiffre décimal est codé avec 4 bits (aussi appelé tétrade). En informatique, le code 8-4-2-1 est généralement utilisé. Les combinaisons non utilisées de 10 à 15 sont appelées pseudotétrades.

  Code BCD:	Décimal:
  0000	0
  ...	...
  1001	9
  0001 0000	10
  ...	...

Avec des nombres binaires d'une longueur limitée, on ne peut représenter qu'un nombre fini d'ENTIERS. Pour 32 bits, cela va de -2 147 483 648 à +2 147 483 647. En développement logiciel, ce type de données est appelé Integer ou int.

Nombres à virgule flottante

Les nombres réels sont stockés dans l'ordinateur comme un produit composé d'une mantisse et d'un exposant en base 2. La norme IEEE 754 est la plus courante. Si le bit de signe est activé, il s'agit d'un nombre réel négatif.

Exemple: $+11,25_{10}$ en binaire est $0.01101...$ (bit de signe, exposant, mantisse).

La conversion d'un nombre réel en binaire selon la norme IEEE 754 se fait en cinq étapes:

1. Calcul du Bias: $2^{(n-1)} - 1$ (où $n$ est le nombre de bits de l'exposant, par ex. 127 pour 8 bits).
2. Conversion du nombre décimal en un nombre binaire à virgule fixe sans signe.
3. Normalisation.
4. Calcul de l'exposant.
5. Détermination du bit de signe.

Exemple de conversion de 11,25:

• Conversion en virgule fixe:
  • Partie entière (11): $11 / 2 = 5$ Reste 1 (LSB); $5 / 2 = 2$ Reste 1; $2 / 2 = 1$ Reste 0; $1 / 2 = 0$ Reste 1 (MSB) $\rightarrow 1011_2$.
  • Partie décimale (0,25): $0,25 \times 2 = 0,5 \rightarrow 0$ (MSB); $0,5 \times 2 = 1 \rightarrow 1$ (LSB) $\rightarrow .01_2$.
  • Donc, $11,25_{10}$ équivaut à $1011.01_2$.
• Normalisation: $1011.01_2 \times 2^0$ équivaut à $1.01101_2 \times 2^3$. Le bit principal avant la virgule est toujours 1 et n'est pas stocké (Hidden Bit). Le nombre est positif, donc le bit de signe est 0.
• Détermination de l'exposant: Exponent = Bias + Décalage = $127 + 3 = 130_{10}$. Converti en binaire: $130_{10} \rightarrow 10000010_2$.
• Formation du nombre à virgule flottante (1 bit signe + 8 bits exposant + 23 bits mantisse):
  $0$ (signe) $10000010$ (exposant) $01101000000000000000000$ (mantisse sans le 1 principal).

Cas spéciaux:

• Zéros: Mantisse = $1.0...$, Exposant = $0...0$.
• L'infini: Mantisse = $1.0...$, Exposant = $2^r-1$.
• "Non-nombre" (NaN): Mantisse > $1.0...$, Exposant = $2^r-1$.

Problèmes des nombres à virgule flottante:

• Troncature (chopping): La partie au-delà de la longueur stockable est coupée, l'erreur d'arrondi est toujours négative.
• Arrondi (rounding): Si le chiffre après la dernière position stockable est $\ge 5$, le dernier chiffre est augmenté de 1. L'erreur d'arrondi est à la fois positive et négative.
• Débordement (overflow): Lorsque le nombre est plus grand que la valeur maximale représentable.
• Sous-débordement (underflow): Lorsque le nombre est plus petit que la valeur minimale représentable.

Formats courants de nombres à virgule flottante en développement logiciel:

Type	Taille (1+r+p)	Exposant (r)	Mantisse (p)	Plage (r)	Bias
single (float)	32 bit	8 bit	23 bit	$-126 \le e \le 127$	127
double	64 bit	11 bit	52 bit	$-1022 \le e \le 1023$	1023
long double	128 bit	15 bit	112 bit	$-16382 \le e \le 16383$	16383

Plage de valeurs:

Type	Chiffres décimaux	Plus petit nombre en valeur absolue	Plus grand nombre
float	7-8	$2^{-149} \approx 1,401 \times 10^{-45}$	$(1-2^{-24}) \times 2^{128} \approx 3,403 \times 10^{38}$
double	15-16	$2^{-1074} \approx 4,941 \times 10^{-324}$	$(1-2^{-53}) \times 2^{1024} \approx 1,798 \times 10^{308}$

Encodage des caractères

Différents encodages de caractères sont utilisés en informatique, notamment:

• ASCII (American Standard Code for Information Interchange):
  • Standard de 1967.
  • 7 bits, 127 caractères (95 imprimables, le reste étant des caractères de contrôle).
  • Étendue à 8 bits, connue sous le nom de jeu de caractères DOS.
  • Les encodages 8 bits ultérieurs basés sur ISO 8859-1 sont familièrement connus sous le nom de codes ANSI (utilisés par ex. dans Microsoft Windows).
• Unicode:
  • Standard de 1991.
  • 17 plans (chacun de 65536 caractères), permettant de coder théoriquement environ 1 million de caractères (actuellement environ 137 000 attribués, V11.0).
  • L'attribution d'un caractère est appelée Codepoint, notée U+xxxx (hexadécimal).
  • L'encodage réel peut se faire en UTF-8, UTF-16 ou UTF-32.

En C, le support d'Unicode doit être implémenté via des fonctions du système d'exploitation.

Exemples ASCII: '?' = 0111111, 'A' = 1000001, 'a' = 1100011.

2.2 Compression de données

La compression de données est l'application de méthodes pour réduire l'espace de stockage des données ou leur temps de transmission.

Types de compression

• Compression sans perte (lossless): Les données originales peuvent être reconstruites sans altération (textes, programmes). La compression est réalisée par réduction de redondance.
• Compression avec perte (lossy): Les données originales ne peuvent pas être reconstruites sans erreurs (images, sons, vidéos). La compression est réalisée par réduction d'irrélevance.

Algorithmes de compression sans perte

• RLE (Run Length Encoding):
  • Les répétitions de caractères sont stockées sous forme de paires (caractère/nombre de répétitions).
  • Exemple: aaaaaaabcccc → 7a1b4c.
  • Avantage: Très simple.
  • Inconvénient: Mauvaise compression pour de nombreux types de données. Généralement utilisé en combinaison avec d'autres méthodes.
  • Pour gérer les nombres dans le texte source, un marqueur (séquence d'échappement) est placé devant le nombre de répétitions (ex: @).
    • Exemple: aaaaaaabcccc → @7a@1b@4c.
    • Inconvénient: N'est rentable qu'à partir de 3 répétitions.
• Codage à longueur variable (Huffman Coding):
  • Les caractères sont codés avec des longueurs différentes: les caractères fréquents obtiennent un code plus court que les caractères rares.
  • Le code doit être préfixe, c'est-à-dire qu'aucun code de caractère ne doit être le début d'un autre code de caractère (arbre binaire).
  • Algorithme de Huffman:
    1. Créer une forêt d'arbres, chacun contenant un seul nœud (le caractère).
    2. Rechercher les deux arbres ayant la plus faible probabilité d'occurrence. Les fusionner en faisant d'eux les sous-arbres d'une nouvelle racine. Utiliser la probabilité totale de ce nouvel arbre pour l'analyse ultérieure.
    3. Répéter l'étape 2 jusqu'à ce qu'il ne reste qu'un seul arbre.

    Caractère	a	b	c	d	e
    Fréquence (supposée)	15	7	6	6	5
    Longueur de code fixe	000	001	010	011	100
    Longueur de code variable	0	100	101	110	111

• LZ77 (Lempel-Ziv 1977):
  • Utilise un mécanisme de "fenêtre glissante" qui recherche des motifs répétitifs dans une partie des données à compresser et stocke des références à ces motifs.
  • Les motifs sont stockés sous forme de triplets: (Position, Longueur, Caractère suivant).
  • Exemple de compression de "ANANAS":
    1. A: (0,0,A)
    2. N: (0,0,N)
    3. ANAN: Repéré en position 0, longueur 2. Le prochain caractère est 'A'. Fenêtre de recherche (8 caractères), Fenêtre de prévisualisation (4 caractères).

       ANANAS → (0,0,A), (0,0,N), (6,2,A), (0,0,S).

  • Problème: La fenêtre doit avoir une certaine taille pour une compression efficace (facteur de compression texte: env. 2-3). Même les caractères simples sont codés comme des triplets.
  • Amélioration: L'algorithme LZSS (Lempel-Ziv-Storer-Szymanski, 1982) introduit un marqueur pour distinguer les caractères normaux des triplets. LZSS combiné à Huffman forme l'algorithme deflate (utilisé dans ZIP).
• Codage différentiel:
  • Ce ne sont pas les données elles-mêmes qui sont stockées, mais leurs changements par rapport à la valeur précédente.
  • Si les valeurs de changement ne sont pas équitablement réparties, un codage à longueur variable peut être appliqué (ex: compression audio).

Algorithmes de compression avec perte

• JPEG (Joint Photographic Experts Group):
  • Compression d'images par réduction d'irrélevance. Des informations visuelles sont supprimées si elles dépassent la capacité de perception de l'œil humain.
  • Principes: L'œil est moins sensible à la résolution spatiale des couleurs qu'aux transitions de luminosité et plus sensible aux structures grossières.
  • Taux de compression: 10-100 (selon la qualité).
  • Processus:
    1. Conversion de l'espace couleur de RGB vers YCbCr.
    2. Filtrage passe-bas/sous-échantillonnage des signaux de chrominance Cb et Cr (avec perte).
    3. Division en blocs de $8 \times 8$ et transformation cosinus discrète de ces blocs (théoriquement sans perte).
    4. Quantification (avec perte).
    5. Réorganisation.
    6. Encodage entropique.
• MP3 (MPEG Audio Layer III):
  • Supprime les informations audio qui dépassent la perception sonore humaine.
  • Principes:
    • La fréquence audible la plus élevée chez l'adulte est d'environ 18-20kHz.
    • Les sons de forte amplitude masquent mieux les sons de faible amplitude s'ils ont une gamme de fréquences similaire. Les sons faibles sont masqués par les sons forts à proximité temporelle.
    • Les sons graves sont difficiles à localiser.

2.3 Sécurité et protection des données

La gestion des données implique des aspects cruciaux de sécurité et de protection afin de garantir leur intégrité, leur confidentialité et leur disponibilité.

Définition des termes

• Protection des données (Datenschutz):
  • Protection des données personnelles contre l'abus (droit fondamental à l'autodétermination informationnelle).
  • Protection des données scientifiques et techniques contre la perte ou l'altération (en fait, il s'agit de sécurité des données).
• Sécurité des données (Datensicherheit):
  • Assure la confidentialité (seuls les utilisateurs autorisés y ont accès).
  • Assure la disponibilité (prévention des pannes système).
  • Assure l'intégrité (les données ne doivent pas être modifiées inaperçues).

Principes de la protection des données

Les droits à la protection des données s'appliquent à la "collecte, au traitement et à l'utilisation de données personnelles" qui ne sont pas de nature purement privée.

• Minimisation des données et prévention des données: Collecter et stocker le moins de données possible.
• Nécessité: Les données ne doivent être collectées que si elles sont absolument nécessaires.
• Finalité: Les données ne peuvent être utilisées que pour les finalités pour lesquelles elles ont été collectées.
• Sécurité des données (restriction d'accès): Garantir que seules les personnes autorisées peuvent accéder aux données.

Autres conséquences de la protection des données:

• Obligation d'information envers les personnes concernées.
• Restriction de l'accès aux personnes autorisées.
• Surveillance de la conformité à la protection des données par une personne indépendante (Délégué à la protection des données).

Défis de la protection des données:

• Les lois nationales sur la protection des données sont difficilement applicables à l'échelle internationale.
• L'interconnexion croissante et les méthodes de traitement toujours plus puissantes créent le "citoyen transparent".
• Un processus d'équilibre entre les intérêts est nécessaire, par exemple entre la lutte contre le terrorisme et la protection des données.

Menaces à la sécurité des données

• Panne technique du système.
• Abus du système.
• Sabotage.
• Espionnage.
• Fraude ou vol.

Mesures de sécurité des données

• Systèmes de sauvegarde (systèmes redondants, sauvegarde des données):
  • Sauvegarde complète: Toutes les données sont copiées sur un support de sauvegarde.
  • Sauvegarde différentielle: Toutes les modifications depuis la dernière sauvegarde complète sont transférées.
  • Sauvegarde incrémentale: Toutes les modifications depuis la dernière sauvegarde sont transférées.
  Supports de sauvegarde: disques optiques (CD/DVD/BluRay), disques durs externes, clés USB, bandes (DAT, LTO, DLT, AIT), réseau (NAS), cloud ou FTP, rsync.
• Contrôles d'accès (profils d'utilisateurs, pare-feu).
• Journalisation (fichiers journaux).
• Chiffrement.

Principe des générations (Grand-père-Père-Fils):

• Décrit un schéma de rotation appliqué aux supports de sauvegarde pour réguler leur réutilisation.
• Garantit la présence de plusieurs sauvegardes à différentes étapes temporelles, permettant de retracer les modifications de données.
• Exemple: Du lundi au jeudi, les sauvegardes sont effectuées sur les médias "Fils" (S1-S4). Chaque vendredi, sur les médias "Père" (V1-V4). Le dernier jour du mois, sur les médias "Grand-père" (G1-G12).

3. Algèbre de Boole

L'algèbre de Boole est la base de la logique numérique et de la conception des circuits informatiques.

3.1 Algèbre de Boole

Les nombres binaires peuvent être interprétés comme "vrai" (1) ou "faux" (0) et être liés logiquement. Les règles de ces liens remontent au mathématicien britannique George Boole et sont appelées Algèbre de Boole.

Opérateurs booléens de base

• ET (AND, $\wedge$): Le résultat est vrai si et seulement si tous les opérandes sont vrais.

  x	y	x ET y
  0	0	0
  0	1	0
  1	0	0
  1	1	1

  (Conjonction)
• OU (OR, $\vee$): Le résultat est vrai si au moins un des opérandes est vrai.

  x	y	x OU y
  0	0	0
  0	1	1
  1	0	1
  1	1	1

  (Disjonction)
• NON (NOT, $\overline{x}$): Inverse la valeur de vérité de l'opérande.

  x	NON x
  0	1
  1	0

  (Négation)

Tous les autres opérateurs (ex. NOR, NAND, XOR, etc.) peuvent être dérivés de ceux-ci.

Représentations

Les opérateurs logiques et leurs combinaisons peuvent être représentés par des tables de vérité, des formules ou des symboles (symboles de commutation).

Formule:	Symbole:
$z = \overline{x}$	NON
$z = x \wedge y$	ET
$z = x \vee y$	OU

Axiomes de l'algèbre de Boole

• Lois commutatives:
  • $x \wedge y = y \wedge x$
  • $x \vee y = y \vee x$
• Lois associatives:
  • $(x \wedge y) \wedge z = x \wedge (y \wedge z)$
  • $(x \vee y) \vee z = x \vee (y \vee z)$
• Lois d'idempotence:
  • $x \wedge x = x$
  • $x \vee x = x$
• Lois distributives:
  • $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$
  • $x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)$
• Lois de neutralité:
  • $x \wedge 1 = x$
  • $x \vee 0 = x$
• Lois extrêmes:
  • $x \wedge 0 = 0$
  • $x \vee 1 = 1$
• Loi d'involution: $\overline{(\overline{x})} = x$
• Lois de De Morgan:
  • $\overline{(x \wedge y)} = \overline{x} \vee \overline{y}$
  • $\overline{(x \vee y)} = \overline{x} \wedge \overline{y}$
• Lois complémentaires:
  • $x \wedge \overline{x} = 0$
  • $x \vee \overline{x} = 1$
• Lois de dualité:
  • $\overline{0} = 1$
  • $\overline{1} = 0$
• Lois d'absorption:
  • $x \vee (x \wedge y) = x$
  • $x \wedge (x \vee y) = x$

Les méthodes de représentation et de résolution de l'algèbre de Boole sont idéales pour l'utilisation en technique de commutation numérique électronique. Lorsque l'on se réfère principalement à cette application, on parle d'Algèbre de commutation.

La représentation des portes logiques par des symboles ou des schémas est déjà une ébauche de plan de circuit, car elle indique les composants électroniques nécessaires et leur câblage.

3.2 Portes logiques de base (Grundgatter)

Les circuits qui connectent des valeurs logiques sont appelés portes logiques (Gatter). Les portes sont basées sur des interrupteurs qui peuvent prendre deux états: ouvert (faux / 0) ou fermé (vrai / 1).

• Porte ET (AND): Une connexion électriquement conductrice n'existe que si les deux interrupteurs sont fermés.
• Porte OU (OR): Une connexion conductrice existe dès que l'un des deux interrupteurs est fermé.

Dans les circuits électriques, vrai / faux (ou 1 / 0) sont représentés par des tensions +5 V / 0 V. Le transistor sert d'interrupteur dans les circuits électroniques. La tension appliquée à sa base influence sa résistance électrique entre le collecteur et l'émetteur.

• Inverseur / Porte NON (NOT):

  x	y
  0	1
  1	0

  Table de vérité

  Fonction de commutation: $y = \overline{x}$.

• Porte NAND (NON-ET):

  $X_2$	$X_1$	Y
  0	0	1
  0	1	1
  1	0	1
  1	1	0

  Table de vérité

  Fonction de commutation: $y = \overline{x_1 \wedge x_2}$.

  La réalisation technique de la porte NAND se fait avec des transistors CMOS.
• Porte NOR (NON-OU):

  $X_2$	$X_1$	Y
  0	0	1
  0	1	0
  1	0	0
  1	1	0

  Table de vérité

  Fonction de commutation: $y = \overline{x_1 \vee x_2}$.

3.3 FDNC (Forme disjonctive normale complète) et FCNC (Forme conjonctive normale complète)

Ces formes sont des représentations standardisées de fonctions logiques.

• FDNC (Forme disjonctive normale complète):
  • Pour la former, toutes les lignes de la table de vérité où la fonction prend la valeur 1 sont liées par un OU (disjonction).
  • Les vecteurs d'entrée individuels $x_i$ sont liés par un ET (conjonction) pour chaque terme. Ceci est appelé minterme. Un minterme contient toujours tous les vecteurs d'entrée.
  • Exemple pour XOR (OU exclusif), $y = \overline{x_2} x_1 \vee x_2 \overline{x_1}$.

    $X_2$	$X_1$	Y
    0	0	0
    0	1	1
    1	0	1
    1	1	0

    La KDNF peut ainsi être formée par une disjonction de tous les mintermes.

• FCNC (Forme conjonctive normale complète):
  • Pour la former, toutes les lignes de la table de vérité où la fonction prend la valeur 0 sont liées par un ET (conjonction).
  • Les vecteurs d'entrée INVERSÉS individuels $x_i$ sont liés par un OU (disjonction) pour chaque terme. Ceci est appelé maxterme. Un maxterme contient toujours tous les vecteurs d'entrée.
  • Exemple pour XOR, $y = (\overline{x_2} \vee \overline{x_1}) \wedge (x_2 \vee x_1)$. Les termes sont inversés par rapport aux minterms.

    $X_2$	$X_1$	Y
    0	0	0
    0	1	1
    1	0	1
    1	1	0

    La KKNF peut ainsi être formée par une conjonction de tous les maxtermes.

3.4 Procédures de minimisation

En ingénierie numérique, les méthodes de minimisation sont utilisées pour simplifier les fonctions logiques et ainsi économiser de l'espace sur les portes logiques et en silicium. La base de cette minimisation est l'application des axiomes de l'algèbre de Boole.

Diagrammes de Karnaugh-Veitch (diagrammes KV)

Les diagrammes de Karnaugh-Veitch (souvent appelés diagrammes KV ou tableaux KV) fournissent une aide à la minimisation des fonctions logiques. Ils peuvent être utilisés pour 2, 3 ou 4 variables d'entrée. Au-delà de 4 variables, ils sont possibles mais rarement utilisés.

Formation de blocs pour KDNF:

• Chaque 1 logique doit être dans au moins un bloc.
• Il faut former le moins de blocs possible, et les blocs doivent être les plus grands possible.
• Seules les tailles de bloc $2^n$ (c'est-à-dire 1, 2, 4, 8) sont autorisées.
• Les blocs diagonaux ne sont pas possibles.
• Un 1 logique peut apparaître dans plusieurs blocs.
• Les vecteurs d'entrée qui apparaissent à la fois niés et non niés dans un bloc sont omis.
• Les vecteurs d'entrée d'un bloc sont liés par un ET.
• Les blocs sont liés par un OU.

Minimisation avec KDNF:

Pour la minimisation, on regroupe des zones convexes maximales de $1, 2, 4, 8, \dots$ champs contenant un 1. Les champs trouvés sont décrits par une conjonction des variables d'entrée. Toutes les "uns" doivent être couverts.

Exemple de KDNF minimisée: $y = x_0 \overline{x_1} x_2 \vee x_0 x_2 x_3 \vee \overline{x_0} \overline{x_1} x_3 \vee \overline{x_0} \overline{x_2}$

Formation de blocs pour KKNF:

• Chaque 0 logique doit être dans au moins un bloc.
• Il faut former le moins de blocs possible, et les blocs doivent être les plus grands possible.
• Seules les tailles de bloc $2^n$ (c'est-à-dire 1, 2, 4, 8) sont autorisées.
• Les blocs diagonaux ne sont pas possibles.
• Un 0 logique peut apparaître dans plusieurs blocs.
• Les vecteurs d'entrée qui apparaissent à la fois niés et non niés dans un bloc sont omis.
• Les vecteurs d'entrée INVERSÉS d'un bloc sont liés par un OU.
• Les blocs sont liés par un ET.

Minimisation avec KKNF:

Pour la minimisation, on regroupe des zones convexes maximales de $1, 2, 4, 8, \dots$ champs contenant un 0. Les champs trouvés sont décrits par une disjonction des variables d'entrée inversées. Tous les "zéros" doivent être couverts.

Exemple de KKNF minimisée: $y = (\overline{x_0} \vee \overline{x_2} \vee \overline{x_3}) (\overline{x_0} \vee \overline{x_1} \vee \overline{x_2}) (\overline{x_0} \vee \overline{x_2}) (\overline{x_0} \vee \overline{x_1} \vee \overline{x_3})$

Fonctions incomplètement spécifiées:

Parfois, les fonctions ne sont pas spécifiées pour toutes les combinaisons possibles de valeurs d'entrée (par exemple, les pseudotétrades dans le code BCD). Ces valeurs de fonction sont marquées par un "x" ou un "d" (don't care) dans le diagramme KV. Elles peuvent être utilisées pour former des zones plus grandes, mais n'ont pas besoin d'être couvertes.

3.5 Demi-additionneur et additionneur complet

Les machines de calcul, comme les ordinateurs, sont basées sur l'addition des nombres binaires.

• Demi-additionneur: Calcule la somme et le report de deux bits binaires à un chiffre.

  $x_1$	$x_2$	s (somme)	ü (report)
  0	0	0	0
  0	1	1	0
  1	0	1	0
  1	1	0	1

  Formules:

  • $s = (\overline{x_1} \wedge x_2) \vee (x_1 \wedge \overline{x_2})$ (ce qui est $x_1$ XOR $x_2$)
  • $u = x_1 \wedge x_2$
  Cette arrangement est appelé demi-additionneur.
• Additionneur complet: Lors de l'addition de nombres binaires à plusieurs chiffres, un report possible de la position précédente doit être pris en compte comme troisième entrée. Un additionneur complet peut être développé à partir de deux demi-additionneurs.

4. Automates

Les automates sont des systèmes qui passent par une séquence d'états et sont fondamentaux pour la conception des circuits séquentiels et des mécanismes de contrôle.

4.1 Circuits combinatoires / circuits séquentiels

• Circuits séquentiels (Schaltwerke): Ce sont des circuits combinatoires où au moins une sortie est renvoyée à l'entrée. Ils sont capables de stocker des informations, appelées variables d'état. La sortie dépend alors des variables d'entrée actuelles ainsi que des variables d'entrée précédentes. Autres noms: (Finis) Automates, State Machines, FSM (Finite State Machines).
  • Circuits séquentiels asynchrones: Les changements d'état peuvent se produire à tout moment, en fonction des changements de leurs entrées.
  • Circuits séquentiels synchrones: Dans ces circuits, un registre cadencé est inséré dans le chemin de rétroaction. Un changement d'état ne peut se produire que de manière synchrone avec le signal d'horloge.

4.2 Bascule (Flipflop)

À partir de deux inverseurs, un autre composant important peut être réalisé: la bascule bistable ou Flipflop, qui peut stocker une valeur logique (1 bit).

• Bascule RS (Set-Reset): Un Flipflop RS peut être réalisé à partir de deux portes NOR.

  S	R	$Q^{m+1}$	$\overline{Q}^{m+1}$
  0	0	$Q^m$	$\overline{Q}^m$ (Mémorisation)
  0	1	0	1 (Reset)
  1	0	1	0 (Set)
  1	1	Interdit

  Table d'état
• Bascule D (Data):

  D	C	$Q^{m+1}$	$\overline{Q}^{m+1}$
  0	1	0	1
  1	1	1	0
  x	0	$Q^m$	$\overline{Q}^m$

  Table d'état

4.3 Automate de Moore

Les automates (également appelés State Machines, FSM pour Finite State Machines) parcourent une séquence d'états. Les changements d'état se produisent généralement de manière synchrone. Les changements d'état dépendent de l'état actuel et des entrées.

• Dans un automate de Moore, les grandeurs de sortie sont calculées uniquement à partir des variables d'état ($z^m$).
• Les sorties dépendent uniquement de l'état actuel et changent toujours de manière synchrone avec l'horloge.
• Les sorties sont notées sur les nœuds du diagramme.

4.4 Automate de Mealy

• Dans un automate de Mealy, les grandeurs de sortie sont calculées non seulement à partir des variables d'état ($z^m$) mais aussi des variables d'entrée.
• Les sorties dépendent de l'état actuel et des entrées, et peuvent changer plusieurs fois dans un cycle d'horloge si le signal d'entrée change.
• Généralement, ils peuvent être implémentés avec moins d'états.
• Les sorties sont notées sur les arrêtes du diagramme.

À partir des éléments discutés jusqu'à présent, une unité arithmétique et logique (UAL) peut être construite. Elle réalise l'addition, la soustraction, la multiplication et la division des nombres binaires par des instructions de décalage et des opérations logiques.

De ces éléments fondamentaux de l'électronique numérique, toutes les portes de l'algèbre de Boole peuvent être réalisées. À partir des éléments de mémoire et des portes, un organe de calcul et finalement le processeur peuvent être construits. Le nombre de transistors nécessaires est une mesure de la complexité de l'unité.

Flipflop	2-6 Transistors
Porte ET / Porte OU	4 Transistors
Additionneur complet pour mots de 32 bits	env. 200 Transistors
Processeur i7	env. 1 milliard de Transistors
GPU AMD Polaris	env. 18 milliards de Transistors

La loi de Moore décrit la régularité empirique selon laquelle le nombre de transistors sur les circuits intégrés double approximativement tous les deux ans. Ce progrès est important car d'autres aspects du progrès technologique (comme la vitesse de traitement ou le prix des produits électroniques) sont fortement liés à la loi de Moore.

5. Structure d'un ordinateur

L'architecture d'un ordinateur repose sur l'interaction de plusieurs composants essentiels, chacun ayant un rôle bien défini.

• Processeur (CPU - Central Processing Unit):
  • Contient plusieurs unités de calcul spécialisées, la logique nécessaire pour lire et écrire des données, contrôler les unités de calcul, et des mémoires tampons (Cache) pour accélérer l'accès aux instructions et aux données.
  • Dans la conception von Neumann, les données et les algorithmes proviennent de la même source: la mémoire principale. Les ordinateurs qui se composent de ces éléments fondamentaux (processeur, mémoire, dispositifs d'entrée/sortie) et où le programme et les données sont stockés dans la même mémoire sont appelés ordinateurs von Neumann. Cela signifie que les données et les programmes ne se distinguent pas physiquement.
• Bus:
  • Permet à tous les composants connectés de communiquer via des lignes de données, d'adresses et de contrôle.
  • On distingue les systèmes 16, 32 et 64 bits en fonction de la largeur du bus de données.
  • Exemples:
    • Bus PCI: 32 ou 64 bits, jusqu'à 4 Gbit/s.
    • Bus USB: Transmission série jusqu'à 480 Mbit/s.
• Mémoire:
  • Les composants de mémoire sont distingués par leur accessibilité:
    • ROM (Read Only Memory): Mémoire en lecture seule.
    • RAM (Random Access Memory): Mémoire à accès aléatoire.
  • Ils sont également distingués par la technologie utilisée:
    • Mémoires à semi-conducteurs: RAM, clé USB.
      • RAM (volatile):
        • SRAM: Le contenu reste stable tant que la tension est appliquée.
        • DRAM: Le contenu doit être rafraîchi cycliquement.
      • ROM (non volatile):
        • PROM: Programmable une seule fois.
        • EPROM: Effaçable par lumière UV.
        • EEPROM: Effaçable électriquement, cycles d'écriture de 1-10ms, effaçable et inscriptible par octet.
        • FlashEEPROM: Effaçable électriquement, cycles d'écriture de 1us-1ms, généralement inscriptible uniquement par blocs.
    • Mémoires à disque magnétique: Disque dur.
    • Mémoires optiques: CD-ROM, DVD, BluRay.
• Éléments d'E/S (Entrée/Sortie - Input/Output):
  • Exemples: clavier, souris, écran, scanner, imprimante.

6. Bases de la programmation

La programmation est l'art de concevoir et d'implémenter des instructions pour qu'un ordinateur exécute des tâches spécifiques. Elle repose sur des concepts fondamentaux comme les algorithmes, les langages de programmation et les environnements de développement.

6.1 Introduction

Pour développer des logiciels, il est essentiel de comprendre les différents types de logiciels, les langages de programmation et les environnements de développement.

Types de logiciels

• Firmware: Logiciel proche du matériel, généralement stocké dans des mémoires ROM et rarement modifié. Dans les systèmes embarqués, le système d'exploitation est souvent associé au firmware. Ex: BIOS.
• Systèmes d'exploitation (OS): Logiciel qui permet le fonctionnement de base d'un ordinateur. Il gère les ressources (mémoire, E/S) et contrôle l'exécution des programmes. Un OS est toujours composé d'un noyau.
• Logiciels d'application: Programmes qui offrent des avantages à l'utilisateur au-delà du simple fonctionnement de l'ordinateur.

Langages de programmation

• Langages machine: Le programme est directement sous forme de codes d'instruction du processeur exécutant. Représentation pour le programmeur généralement en hexadécimal.
• Langages assembleur: Représentation du code d'instruction du processeur avec des abréviations mnémoniques (MOV, ADD, CALL,...). Traduit en langage machine par un assembleur.
• Langages de haut niveau (3ème génération - 3GL): Langages de programmation orientés problème et indépendants du matériel, traduits en langage machine par un interpréteur ou un compilateur. Les déroulements de programme sont donnés séquentiellement et procéduraux (Ex: C, Pascal, BASIC).
• Langages de très haut niveau (4ème et 5ème générations - 4GL/5GL): Permettent des approches plus abstraites et orientées problème (4GL, ex: SQL) ou la programmation d'IA (5GL, ex: Lisp, Prolog).

Interpréteur vs Compilateur

• Interpréteur: Traduit un programme ligne par ligne et l'exécute immédiatement. Un programme peut ainsi être immédiatement exécuté sur toute plateforme pour laquelle un interpréteur existe.
  • Avantage: Flexibilité, portabilité.
  • Inconvénient: Vitesse d'exécution.
  • Exemples: BASIC, Interactive-C, PHP, PERL.
• Compilateur: Traduit une fois un programme (code source) en langage machine du système cible avant l'exécution.
  • Exemples: C, Pascal, Pearl.
• Combinaison (ex: Java): Un code source Java est traduit en bytecode indépendant de la plateforme, qui est ensuite interprété lors de l'exécution.

Le processus de développement d'un programme:

1. Le programmeur écrit le code source (ex: test.c).
2. Un compilateur (ex: gcc) traduit le code source en un programme exécutable (langage machine, ex: a.out).

Si un programme est composé de plusieurs fichiers, un linker (éditeur de liens) combine les différentes parties en un programme exécutable.

Environnements de développement

• Développement sans IDE: Le texte source est saisi avec un éditeur (ex: JEdit), et le compilateur/linker est appelé "manuellement" (ex: gcc -o x x.c dans un terminal Linux).
• Environnements de développement intégrés (IDE): Combinaison d'un éditeur spécialisé pour la saisie du code source, un compilateur, un linker et d'autres fonctions utiles.
  • Exemples: Dev-C++, Microsoft Visual Studio Express Edition.

6.2 Structogrammes

Un algorithme est une instruction d'action qui, utilisée précisément, conduit au résultat souhaité après un nombre fini d'étapes. Chaque algorithme désiré peut être construit à partir de seulement trois éléments (appelés "structures de contrôle"):

1. Séquence: Les actions sont exécutées dans l'ordre spécifié.

   Action 1

   Action 2

   ...

2. Branchement (Condition): Si une condition est vraie, une action est exécutée; sinon, une autre action (ou aucune) est exécutée.

   vrai	Condition	faux
   Action 1	Action 2

3. Répétition (Boucle):
   • Boucle contrôlée par la tête (Pré-condition): L'action est exécutée tant que la condition est vraie.

     Condition

     Action

   • Boucle contrôlée par le pied (Post-condition): L'action est exécutée jusqu'à ce que la condition soit fausse. L'action est exécutée au moins une fois.

     Action

     Condition

   • Boucle à compteur: Une forme spécifique de boucle contrôlée par la tête où le nombre d'exécutions de l'action est déjà connu à l'avance.

     n fois

     Action

Des parties de l'algorithme peuvent également être décrites comme un sous-programme (procédure, fonction, méthode) dans un structogramme distinct.

Chaque problème peut être résolu uniquement par des séquences, des branchements et des répétitions. Les sauts ne sont pas nécessaires et sont évités. Un tel "programme structuré" est clair et donc relativement sûr contre les erreurs.

6.3 Bases du langage de programmation C

C est actuellement le langage de programmation le plus important dans le développement logiciel industriel.

Structure du programme

Un exemple de programme C pour afficher "Hello World" à l'écran:

#include <stdio.h>

int main(void)
{
    printf("Salut ");
    printf("Monde");
}

• Inclusion de bibliothèques: L'instruction #include est nécessaire pour utiliser des fonctions de bibliothèques (ici, printf de la bibliothèque stdio.h).
• Point de départ / programme principal: Chaque programme C contient exactement une fois le mot-clé main. L'exécution du programme commence ici. Les accolades {} marquent le début et la fin d'un bloc d'instructions.
• Sortie de texte: Les commandes et les appels de fonctions sont exécutés séquentiellement, toujours terminés par un point-virgule (;). La fonction printf() écrit du texte à l'écran.
• Sortie de nombres: printf() peut aussi afficher des nombres. Dans ce cas, un espace réservé (ici: %i pour entier) est utilisé pour le nombre à afficher. Les textes doivent toujours être entre guillemets doubles ("...").
• Commentaires: Servent à améliorer la lisibilité du code source. Tout ce qui se trouve entre /* et */ est ignoré. Le texte à partir de // jusqu'à la fin de la ligne est ignoré par le compilateur.
• Sensibilité à la casse: C est "case-sensitive", c'est-à-dire que majuscules et minuscules sont distinguées. Main n'est donc pas la même chose que main.
• Format libre: Le C est un langage de format libre. Pour une meilleure lisibilité, des conventions sont recommandées:
  • Un seul instruction par ligne.
  • Indenter les blocs.
  • Noms de variables parlants (ex: somme au lieu de s).
  • Noms de variables commençant par une minuscule.
  • Commentaires suffisants.
  • Auteur et date dans l'en-tête du programme.

Variables

Un programme peut stocker des valeurs dans des variables. Avant qu'une variable ne puisse être utilisée pour la première fois, elle doit être déclarée, c'est-à-dire que son type, son nom et, le cas échéant, sa dimension sont définis.

• Propriétés d'un objet de données:
  • Nom: Sert de référence symbolique et est remplacé par le compilateur par l'adresse mémoire associée.
  • Type: Détermine l'espace mémoire requis et définit l'interprétation des données stockées. Ex: int, double, char.
  • Valeur: La grandeur concrète assignée et stockée.
  • Dimension (si applicable): Si c'est un tableau (array), la dimension indique le nombre de valeurs individuelles. Ex: int nombres[10] est un tableau de 10 valeurs entières.
• Nombres à virgule flottante (float): Pour les nombres à virgule flottante, le type float est utilisé. Le formatateur %f est utilisé avec printf() et scanf(). Le point . est utilisé comme séparateur décimal (non la virgule ,).
• Tableaux (Arrays): Des tableaux peuvent être formés à partir de n'importe quel type de données. La déclaration type nom[n] crée n variables du type spécifié, accessibles par leur indice de nom[0] à nom[n-1]. L'indice est toujours de type int. Le nombre d'éléments - 1 est l'indice maximal.
• Chaînes de caractères (Strings): Une chaîne de caractères n'est rien d'autre qu'un tableau de valeurs char. Le caractère nul '\0' est ajouté pour marquer la fin de la chaîne. Les caractères individuels sont entre apostrophes ('A'), les chaînes entre guillemets ("Bonjour").

Constantes

Les valeurs numériques et de caractères attribuées aux variables sont appelées constantes.

• Constantes entières:
  • Décimales: commencent par un chiffre différent de 0 (ex: 12122).
  • Octales: commencent par 0 (ex: 045 équivaut à $37_{10}$).
  • Hexadécimales: commencent par 0x ou 0X et utilisent 0-9, A-F (ex: 0xff équivaut à $255_{10}$).
  • Type par défaut: int. Possible aussi long en ajoutant l ou L (ex: 12344L).
• Constantes à virgule flottante:
  • Partie entière et fractionnaire séparées par un point (ex: 1.2122 ou .232).
  • Notation exponentielle possible (ex: 1.45e-10 pour $1.45 \times 10^{-10}$).
  • Type par défaut: double.
• Constantes de caractères: Un caractère du jeu de caractères représentable entre apostrophes (ex: 'a' ou '1'). Type char, stocké avec sa valeur de codage ASCII.
• Constantes de chaînes de caractères: Une séquence de caractères entre guillemets (ex: "Bonjour Monde"). Le caractère '\0' est automatiquement ajouté. Type char*.

Séquences d'échappement (Escape-Sequenzen)

Caractères spéciaux représentés par des séquences d'échappement (ex: '\n' pour nouvelle ligne, '\t' pour tabulation).

Séquence d'échappement	Signification
"\n"	Saut de ligne (new line)
"\t"	Tabulation horizontale
"\""	Guillemet double
"\\"	Barre oblique inverse (backslash)
"\ddd"	Caractère ASCII en notation octale
"\xdd"	Caractère ASCII en notation hexadécimale

Règles pour les noms de variables

• Composés de lettres, chiffres ou tirets bas (_).
• Ne doivent pas commencer par un chiffre.
• Éviter les tirets bas au début (collisions avec noms internes).
• La longueur peut être arbitraire, mais seuls les premiers 8 à 32 caractères sont souvent considérés.
• Ne doit pas être un mot-clé C réservé.
• Sensible à la casse.

Mots-clés réservés (ex: auto, break, case, char, const, continue, default, do, double, else, enum, extern, float, for, goto, if, int, long, register, return, short, signed, sizeof, static, struct, switch, typedef, union, unsigned, void, volatile, while).

Opérateurs

• Opérateurs arithmétiques: +, -, *, / (division entière pour entiers), % (modulo).
• Opérateurs de comparaison: == (égal), != (différent), <= (inférieur ou égal), >= (supérieur ou égal), < (inférieur), > (supérieur). Résultat: 0 (faux) ou 1 (vrai).
• Opérateurs logiques: && (ET), || (OU), ! (NON). Connectent des valeurs vraies/fausses, souvent utilisées avec des opérateurs de comparaison.
• Opérateurs bit à bit: & (ET), | (OU), ^ (XOR), ~ (NON, complément à un), >> (décalage à droite, division par 2), << (décalage à gauche, multiplication par 2).
• Incrément / Décrément: ++ (incrément), -- (décrément).
  • Post-fixé (a++): la valeur originale est utilisée, puis la variable est incrémentée.
  • Pré-fixé (++a): la variable est d'abord incrémentée, puis la nouvelle valeur est utilisée.
• Opérateurs d'affectation: = (simple affectation), +=, -=, *=, /=, %=, >>=, <<=, &=, |=, ^=.

Types de données

• Entiers (int): char (1 byte), short (2 bytes), int (2 ou 4 bytes), long (4 bytes). Versions unsigned (sans signe) disponibles, ainsi que signed (avec signe).
• Nombres à virgule flottante: float (4 bytes, 6 décimales), double (8 bytes, 15 décimales), long double (10 bytes, 19 décimales).

Entrée et sortie de données

• Entrée (scanf()): La fonction scanf() est utilisée pour entrer des données. Le type de nombre est spécifié par l'espace réservé (ex: %i pour entier). La variable doit être fournie avec l'opérateur d'adresse & (ex: &x).
• Sortie (printf()): La fonction printf() donne la sortie des caractères sur stdout. Elle renvoie le nombre de caractères affichés ou -1 en cas d'erreur. Le format peut être composé de caractères normaux, de séquences d'échappement et de spécificateurs de format (ex: %d, %f, %s).

7. Algorithmes

Les algorithmes sont des instructions précises pour résoudre un problème, et leur mise en œuvre est au cœur de la programmation informatique.

Exemples de problèmes mathématiques et d'algorithmes simples

La démarche pour résoudre un problème inclut:

1. Formulation en langage naturel des étapes de résolution ou de traitement nécessaires (éventuellement croquis).
2. Conception d'un structogramme approprié.
3. Encodage de la solution du problème en C.

• Exemple 1: Triangle: Vérifier si un triangle peut être construit à partir de trois longueurs de côtés a, b et c. (Indice: la somme de deux côtés doit être supérieure au troisième).
• Exemple 2: Année bissextile: Afficher les années bissextiles d'une période donnée. (Indice: une année est bissextile si elle est divisible par 4, sauf si elle est divisible par 100 mais pas par 400).
• Exemple 3: Factorielle: Calculer la factorielle n! d'un nombre.
• Exemple 4: Plus Grand Commun Diviseur (PGCD): Déterminer le PGCD de deux nombres a et b.
• Exemple 5: Test de primalité: Afficher les nombres premiers de 1 à 1000.

8. Examen blanc

Récapitulatif des connaissances essentielles

Introduction

• Avantages de la technologie numérique.
• Définition de Bit, Byte, KiB, MiB, GiB.
• Conversion décimal $\leftrightarrows$ binaire.
• Addition et soustraction de nombres binaires.
• Conversion binaire $\leftrightarrows$ hexadécimal.
• Méthodes de codage.
• Conversion décimal $\leftrightarrows$ virgule flottante.
• Types de données Int, Float, Char.
• Encodage de caractères.

Compression de données

• Terminologie (encodeur, décodeur,...).
• Types de compression (avec ou sans perte).
• Algorithmes RLE, LZ77, Huffman.
• Effets utilisés par JPEG et MP3 pour la compression.
• Applications de la compression avec perte.

Protection et sécurité des données

• Terminologie (protection des données, sécurité des données).
• Principes de protection des données.
• Conséquences de la protection des données.
• Scénarios de menace.
• Mesures de sécurité.
• Stratégies de sauvegarde.

Algèbre de commutation

• Axiomes de l'algèbre de Boole.
• Création de tables de vérité, de formules et de symboles de commutation.
• Réalisation technique des portes logiques.
• Utilisation des diagrammes KV pour la minimisation des réseaux de commutation.
• Demi-additionneur et additionneur complet.

Automates

• Différences entre automate de Moore et de Mealy.
• Diagrammes d'état.
• Types de bascules.
• Unité arithmétique et logique.

Structure d'un ordinateur

• Processeur.
• Bus (série vs parallèle).
• Architecture typique d'un ordinateur.

Bases de la programmation C

• Qu'est-ce qu'un langage de haut niveau? Un compilateur? Un linker? Un environnement de développement?
• Programmes simples en C.
• Intégration de bibliothèques.
• Fonction main().
• Affichage de texte avec printf.
• Commentaires.
• Déclaration de variables.
• Affectation de valeurs.
• Types de données élémentaires char, int, float, double.
• Saisie avec scanf(), gets().
• Tableaux / Arrays.
• Chaînes de caractères / Strings.
• Opérateurs.

Branchements (Conditions)

• Expressions logiques avec <=, >=, ==, !=, &&, ||.
• Branchements avec if, if + else, switch.
• Opérateur conditionnel.

Répétitions (Boucles)

• Boucles avec while, do-while, for.

Contrôle de flux et opérateurs

• Contrôle de transfert avec break et continue.
• Opérateurs et leurs priorités.
• Opérateur sizeof.

Fonctions

• Fonctions.
• Passage de paramètres: Call by value.
• Passage de paramètres: Call by reference.
• Valeurs de retour.