Information, calcul, communication (CS-119(l))

Information, calcul, communication (CS-119(l)), cours de première année en Mathématiques à l’EPFL, donné par Sébastien Doeraene (6 crédits). Sur BA1 Planner : 14 fiches de révision et 70 flashcards.

Programme, semaine par semaine

M1.L1 — Représentation de l'information et des symboles

1.1 Notion d'information et de bit · 1.2 Codage des symboles · 1.3 ASCII et Unicode (UTF-8) · 1.4 Quantité d'information et nombre de bits nécessaires

M1.L1.3 — Représentation des entiers

2.1 Bases de numération et conversions · 2.2 Binaire et hexadécimal · 2.3 Entiers non signés et capacité · 2.4 Complément à deux et débordement

M1.L1.4 — Représentation des nombres à virgule

3.1 Virgule fixe et virgule flottante · 3.2 Norme IEEE 754 (signe, exposant, mantisse) · 3.3 Précision et erreurs d'arrondi · 3.4 Conséquences pratiques sur les comparaisons

M1.L2 — Algorithmes : les composants de base

4.1 Définition et propriétés d'un algorithme · 4.2 Séquence, condition, itération · 4.3 Variables et affectation · 4.4 Terminaison et correction

M1.L3 — Ordre de complexité, recherche et tri

5.1 Coût d'un algorithme et notation grand-O · 5.2 Recherche linéaire et dichotomique · 5.3 Tris élémentaires · 5.4 Comparaison des ordres de complexité

M1.L4 — Récursivité et programmation dynamique

6.1 Définition récursive et cas de base · 6.2 Coût des appels récursifs · 6.3 Mémoïsation · 6.4 Programmation dynamique

M1.L5 — Théorie du calcul

7.1 Modèle de calcul et machine de Turing · 7.2 Calculabilité · 7.3 Problème de l'arrêt · 7.4 Problèmes décidables et indécidables

M2.L1 — Signaux : filtrage et échantillonnage

8.1 Signal analogique et signal numérique · 8.2 Fréquence et spectre · 8.3 Filtrage · 8.4 Échantillonnage : principe

M2.L2 — Échantillonnage et reconstruction

9.1 Théorème d'échantillonnage de Nyquist-Shannon · 9.2 Repliement de spectre (aliasing) · 9.3 Quantification et bruit · 9.4 Reconstruction du signal

S10

M2.L3 — Compression I

10.1 Compression avec et sans perte · 10.2 Codes à longueur variable et codes préfixes · 10.3 Codage de Huffman · 10.4 Taux de compression

S11

M2.L4 — Entropie et compression II

11.1 Entropie de Shannon · 11.2 Longueur moyenne d'un code · 11.3 Théorème du codage de source · 11.4 Compression avec perte

S12

M3.L1 — Architecture du processeur

12.1 Modèle de von Neumann · 12.2 Unité de contrôle et unité arithmétique et logique · 12.3 Registres et jeu d'instructions · 12.4 Cycle fetch-decode-execute

S13

M3.L2-3 — Mémoires, stockage et réseaux

13.1 Hiérarchie mémoire et cache · 13.2 Stockage de masse · 13.3 Réseaux : couches et protocoles · 13.4 Adressage IP et routage

S14

M3.L4 — Sécurité informatique et synthèse

14.1 Chiffrement symétrique et asymétrique · 14.2 Fonctions de hachage et intégrité · 14.3 Authentification et signature · 14.4 Synthèse et pratique (C++)

Fiche de révision : semaine 1

L’essentiel

L'**information** se mesure en **bits** : un bit distingue deux possibilités équiprobables.
Avec $n$ bits, on distingue $2^n$ configurations. Inversement, coder $N$ symboles demande $\lceil \log_2 N \rceil$ bits.
Un **octet** (byte) = 8 bits → 256 valeurs.
**ASCII** code 128 symboles sur 7 bits (souvent stockés sur 8) : suffisant pour l'anglais, pas pour les accents.
**Unicode** attribue un point de code à chaque caractère de toutes les écritures ; **UTF-8** l'encode sur 1 à 4 octets, en restant compatible avec ASCII sur les 128 premiers caractères.
Représenter une information, c'est choisir une convention partagée entre émetteur et récepteur — le même motif binaire n'a de sens que par la convention.

Formules

$n$ bits → $2^n$ configurations
Coder $N$ symboles : $\lceil \log_2 N\rceil$ bits
1 octet = 8 bits = 256 valeurs
ASCII : 7 bits, 128 symboles

À savoir

En UTF-8, un caractère accentué occupe 2 octets, pas 1.
Le même motif binaire peut être un entier, un caractère ou une couleur : seule la convention tranche.
$\log_2 1000 \approx 10$, donc 10 bits suffisent pour 1000 valeurs.

Erreurs classiques

Confondre bit (b) et octet (B) : un débit de 8 Mb/s vaut 1 Mo/s.
Oublier l'arrondi supérieur dans $\lceil\log_2 N\rceil$.
Croire qu'un caractère occupe toujours un octet.
Confondre nombre de valeurs ($2^n$) et valeur maximale ($2^n - 1$).

Quelques flashcards

Combien de configurations avec $n$ bits ?

$2^n$.

Combien de bits pour coder 1000 symboles distincts ?

$\lceil\log_2 1000\rceil = 10$ bits.

Combien de symboles code l'ASCII, et sur combien de bits ?

128 symboles sur 7 bits.

Quelle plage pour un entier signé sur 8 bits en complément à deux ?

$-128$ à $+127$.

Comment calculer l'opposé en complément à deux ?

Inverser tous les bits puis ajouter 1.

Combien de bits représente un chiffre hexadécimal ?

Exactement 4.

Coche le cours et la série de Information, calcul, communication chaque semaine, révise avec les fiches et les flashcards, et entraîne-toi sur les questions d’examen corrigées. Les deux premières semaines sont gratuites.

Créer un compte gratuit