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

Information, calcul, communication (CS-119(h)), cours de première année en Sciences et ingénierie de l'environnement à l’EPFL, donné par Olivier Lévêque, Mirjana Stojilovic (6 crédits). Sur BA1 Planner : 14 fiches de révision et 70 flashcards.

Programme, semaine par semaine

Introduction : information, calcul et communication

1.1 Qu'est-ce que l'information · 1.2 Notion de calcul · 1.3 Chaîne de communication · 1.4 Plan et enjeux du cours

Écrire un algorithme

2.1 Spécification d'un problème · 2.2 Pseudo-code et structures de base · 2.3 Variables et affectation · 2.4 Terminaison et correction

Algorithmes classiques

3.1 Recherche linéaire et dichotomique · 3.2 Tris élémentaires · 3.3 Invariants de boucle · 3.4 Algorithmes sur les tableaux

Algorithmes récursifs

4.1 Définition récursive et cas de base · 4.2 Diviser pour régner · 4.3 Arbre d'appels et coût · 4.4 Récursif contre itératif

Complexité temporelle

5.1 Nombre d'opérations élémentaires · 5.2 Notation grand-O · 5.3 Pire cas, meilleur cas, cas moyen · 5.4 Hiérarchie des complexités

Aperçu de la calculabilité

6.1 Modèles de calcul · 6.2 Problèmes décidables et indécidables · 6.3 Problème de l'arrêt · 6.4 Conséquences pratiques

Représentation binaire des nombres

7.1 Bases de numération et conversions · 7.2 Entiers non signés et signés · 7.3 Complément à deux · 7.4 Nombres à virgule flottante

Échantillonnage des signaux

8.1 Signal analogique et numérique · 8.2 Fréquence et spectre · 8.3 Échantillonnage · 8.4 Théorème de Nyquist-Shannon

Reconstruction de signaux

9.1 Reconstruction à partir des échantillons · 9.2 Repliement de spectre (aliasing) · 9.3 Quantification et bruit · 9.4 Débit d'un signal numérisé

S10

Information et compression

10.1 Quantité d'information d'un symbole · 10.2 Entropie de Shannon · 10.3 Compression avec et sans perte · 10.4 Théorème du codage de source

S11

Algorithmes de Shannon-Fano et Huffman

11.1 Codes à longueur variable et codes préfixes · 11.2 Algorithme de Shannon-Fano · 11.3 Algorithme de Huffman · 11.4 Optimalité et longueur moyenne

S12

Correction d'erreurs : principes de base

12.1 Erreurs de transmission · 12.2 Bit de parité et détection · 12.3 Distance de Hamming · 12.4 Codes correcteurs et redondance

S13

Cryptographie à clé secrète

13.1 Chiffrement à clé secrète · 13.2 Masque jetable et sécurité parfaite · 13.3 Problème de l'échange de clé · 13.4 Introduction à la clé publique

S14

Pratique Python : structures de données et fonctions

14.1 Types de base et opérateurs · 14.2 Conditions et boucles · 14.3 Listes, tuples, ensembles et dictionnaires · 14.4 Fonctions et portée des variables

Fiche de révision : semaine 1

L’essentiel

Le cours articule trois notions : **information** (comment la représenter et la mesurer), **calcul** (ce qu'une machine peut faire, et à quel coût) et **communication** (comment transmettre de façon fiable et sûre).
L'unité d'information est le **bit** : il distingue deux possibilités équiprobables. Avec $n$ bits, $2^n$ configurations.
Toute information manipulée par un ordinateur — texte, image, son — est **réduite à des bits** ; seule la convention d'interprétation change.
La chaîne de communication typique : source → codage de source (compression) → codage de canal (correction d'erreurs) → canal bruité → décodage → destinataire.
Deux grandes limites théoriques structurent le cours : ce qui est **calculable** (Turing) et ce qui est **compressible** (Shannon).
Le cours comporte une partie théorique et une pratique en **Python**.

Formules

$n$ bits → $2^n$ configurations
Coder $N$ symboles : $\lceil\log_2 N\rceil$ bits
Chaîne : source → compression → correction → canal
1 octet = 8 bits

À savoir

Compression (codage de source) et correction d'erreurs (codage de canal) tirent en sens opposés : l'une retire de la redondance, l'autre en ajoute.
Le même motif binaire n'a de sens que par la convention choisie.
Toutes les données numériques sont in fine des suites de bits.

Erreurs classiques

Confondre bit et octet (facteur 8).
Croire qu'un fichier « contient » du texte plutôt que des bits interprétés.
Mélanger codage de source et codage de canal.
Confondre nombre de valeurs ($2^n$) et valeur maximale ($2^n-1$).

Quelques flashcards

Que distingue un bit ?

Deux possibilités équiprobables ; $n$ bits distinguent $2^n$ configurations.

Quelles sont les étapes de la chaîne de communication ?

Source → codage de source → codage de canal → canal → décodage → destinataire.

Quelle est la différence entre codage de source et codage de canal ?

Le premier retire de la redondance (compression), le second en ajoute (correction d'erreurs).

Que signifie spécifier un problème ?

Décrire précisément les entrées valides et la sortie attendue.

Quelles sont les trois structures de base d'un algorithme ?

Séquence, condition, itération.

Comment prouver qu'une boucle termine ?

Exhiber une quantité entière positive qui décroît strictement à chaque tour.

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