Course: Information, calcul, communication

Weekly outline

Informations générales
Ce cours s’adresse aux étudiant.e.s en génie civil et science et génie des matériaux de première année à l’EPFL. Le premier cours aura lieu le vendredi 23 septembre 2022 à 8h15, en salle CM 1 3 (retransmis en parallèle sur Zoom).

Enseignants: Olivier Lévêque (partie théorique) et Jean-Philippe Pellet (partie programmation)

Assistant·e·s:
Partie théorique: Robin Zbinden, Gabriel Burkhard, Cynthia Papon, Valérie Costa, François Dumoncel-Kessler, Pierre Sintre, Marine Jacob, Patrick Yerly, Nathan Kabas, Joe El Helou, Fred Fayad, Etienne Bruno

Partie programmation: Molly Petersen, Hafsa Aoutir, Etienne Bruno, Alexandre Carlhammar, Baptiste Copros, Valérie Costa, Alaa El Ouahabi, Axel Giboulot, Gaiëtan Renault, Karim Sabaa, Pierre Sintre
Horaires:
Partie théorique:

    cours les vendredis de 8h15 à 10h00:

   en salle CM 1 3 (a.k.a. CM3) et sur Zoom (enregistrements)

séances d'exercices les vendredis de 10h15 à 11h15+:

   en salles CM 1 120 (lettres A à J), MA A3 30 [anciennement GC B3 31] (lettres K à O), GR A3 32 [anciennement GC C3 30] (lettres P à Z)

Partie programmation:

cours les vendredis de 13h15 à 14h00:

   en salle CM 1 1 (a.k.a. CM1) et sur Zoom (enregistrements)

séance d'exercices les vendredis de 14h15 à 16h00:

   en salles BC07-08 (MX), et CM 1 103 et CM 1 112 (GC)
Séances supplémentaires de réponses aux questions, pour les deux parties du cours (à partir du mardi 27.9):
pour MX: les mardis soirs de 17h30 à 19h00 en salle CO 023
pour GC: les mercredis soirs de 17h30 à 19h00 en salle CO 021

Ressources pour le cours (partie théorique):

Chaîne Switchtube avec vidéos pré-enregistrées et enregistrements du cours
MOOC sur courseware.epfl.ch (en développement)

Livre «Découvrir le numérique», EPFL Press, 2016
(voir aussi les solutions des exercices du livre)
Semaine 1 (vendredi 23 septembre)
- Partie théorique:
  Algorithmes: introduction générale
  Ingrédients de base des algorithmes
- Cours 1 File
- Comment écrire un algorithme en pseudo-code? File
- Série 1 File
- Partie programmation:
  Généralités
  Déclaration de variables; types de données
  Arithmétique de base et conversions entre types
  Appel de fonctions/méthodes prédéfinies et de print
- Cours 1 File
- Enregistrement URL
- Série 1 File
- Fichiers pour la configuration sur les machines virtuelles de l'EPFL, à télécharger et utiliser selon les instructions du PDF:
- setup.sh File
- Mémo connexion VDI File
- Guide pour activer l’authentification forte URL
- Fichiers pour la configuration sur vos propres machines, à télécharger et utiliser selon les instructions du PDF:
- workspace.zip File
- Fichiers communs pour le reste de la série:
- Code pour l’exercice 4 Page
- Corrigé Page
Semaine 2 (vendredi 30 septembre)
- Partie théorique:
  Algorithmes et sous-algorithmes
  Complexité temporelle d'un algorithme
- Cours 2 File
- Algorithmes et complexité temporelle File
- Codes liés au cours 2 Folder
- Série 2 File
- Partie programmation:
  Syntaxe: fonctions, méthodes, slicing
  Conditions
  Boucles
  La fonction range()
- Cours 2 File
- Enregistrement Zoom URL
- Série 2 File
- Code initial pour l’exercice 3 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (texte) Page
- Corrigé exercice 2 (vidéo) URL
- Corrigé exercice 3 (texte) Page
- Corrigé exercice 3 (vidéo) URL
Semaine 3 (vendredi 7 octobre)
- Partie théorique:
  Récursivité: principes - ingédients de base
  Applications: recherche par dichotomie et tri par fusion
- Cours 3 File
- Algorithmes récursifs: quelques clarifications File
- Codes liés au cours 3 Folder
- Série 3 File
- Partie programmation:
  Révision des boucles
  Déclaration et appel de fonctions simples
- Cours 3 File
- Enregistrement Zoom URL
- Série 3 File
- Code initial exercice 3 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (texte) Page
- Corrigé exercice 2 (vidéo) URL
- Corrigé exercice 3 (texte) Page
- Corrigé exercice 3 (vidéo) URL
Semaine 4 (vendredi 14 octobre)
- Partie théorique:
  Rendu de pièces de monnaie:
  1. algorithme glouton
  2. programmation dynamique et mémoïsation
  La théorie de la calculabilité et le problème de l'arrêt
- Cours 4 File
- Argument de la diagonale de Cantor File
- Codes liés au cours 4 Folder
- Série 4 File
- Partie programmation:
  Listes
- Cours 4 File
- Enregistrement Zoom URL
- Série 4 File
- Code initial de l’exercice 2 Page
- Code initial de l’exercice 3 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (texte) Page
- Corrigé exercice 2 (vidéo) URL
- Corrigé exercice 3 (texte) Page
- Corrigé exercice 3 (vidéo) URL
Semaine 5 (vendredi 21 octobre)
- Partie théorique:
  Classes de complexité des problèmes
  Problèmes d'optimisation discrète
  Résolution avec garanties d'approximation
- Cours 5 File
- Pourquoi s'intéresser à la théorie de la complexité? File
- Série 5 File
- Partie programmation:
  Objets immuables, objets modifiables et références
  Imports, modules
  Sets
- Cours 5 File
- Code de simulation du problème des prisonniers Page
- Enregistrement Zoom URL
- Série 5 File
- Code initial de l’exercice 2 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (texte) Page
- Corrigé exercice 2 (vidéo) URL
Semaine 6 (vendredi 28 octobre)
- Partie théorique:
  Représentation de l'information:
  - représentation binaire des nombres entiers
  - représentation binaire des nombres réels
- Cours 6 File
- Série 6 File
- Partie programmation:
  Révisions: Listes
  Sets
  Dictionnaires
- Cours 6 File
- Enregistrement Zoom URL
- Série 6 File
- Code initial de l’exercice 2 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Partie programmation: examens d’entraînement
- Exemples de QCM d’une autre année (prog.) Page
- Examen intermédiaire de 2019 File
  Pour vous préparer, cette année, vous n’avez pas besoin de faire l’exercice 4, qui utilise les classes, que nous n’avons pas encore vues.
- Code initial Page
- Proposition de corrigé Page
- Examen intermédiaire de 2018 File
  Pour vous préparer, cette année, vous n’avez pas besoin de faire l’exercice 4, qui utilise les classes, que nous n’avons pas encore vues, et vous pouvez sauter le 3 (f), qui utilise les compréhensions de listes, que nous n’avons pas discutées.
- Code initial Page
- Proposition de corrigé Page
- Examen intermédiaire de 2017 File
  Pour vous préparer, cette année, vous n’avez pas besoin de faire l’exercice 4, qui utilise les classes, que nous n’avons pas encore vues.
- Code initial Page
- Proposition de corrigé Page
- Ces deux enregistrements sont tirés du cours de l’année 2020 et montrent comment résoudre cet examen. Rappel: il n’est pas attendu de vous que vous puissiez faire l’exercice 4 avec les classes.
- Enregistrement Zoom (1/2) URL
- Enregistrement Zoom (2/2) URL
Semaine 7 (vendredi 4 novembre)
Vendredi 4 novembre, matin: examen intermédiaire de 8h00 à 11h00, en salles INF 1 (lettres A à F), INF 2 (lettres G à P), AAC 008 (lettres R et S) et AAC 006 (lettres T à Z + Paratte)

Matériel autorisé: une page A4 recto-verso manuscrite (ou préparée avec stylet+tablette), sur laquelle vous pouvez écrire tout ce que vous pensez être important concernant le cours et les exercices.

Non-autorisé: appareil électronique tel que calculatrice, smartphone/watch, tablette, ordinateur, etc.

Vendredi 4 novembre, après-midi: cours pour la partie théorique de 13h15 à 15h00 (en salle CO 3) et exercices correspondants de 15h15 à 16h15+ (en salles SG 0211 et SG 0213).

Pas de cours de programmation pendant cette semaine
- Proposition de corrigé du midterm pour la partie programmation Page
- Partie théorique:
  Circuits logiques et transistors
  Circuits quantiques
- Cours 7 File
- How semiductors work URL
  Première vidéo (en anglais) de Ben Eater sur le fonctionnement d'une diode, le plus simple des semi-conducteurs
- How a transistor works URL
  Deuxième vidéo (toujours en anglais) de Ben Eater sur le fonctionnement d'un transistor
- Série 7 File
Semaine 8 (vendredi 11 novembre)
- Partie théorique:
  Signaux: filtrage et échantillonnage
- Cours 8 File
- Lien vers les graphiques vus en cours URL
- Série 8 File
- Partie programmation:
  Classes simples (@dataclass)
  Modélisation avec des classes
- Cours 8 File
- Enregistrement Zoom URL
- Série 8 File
- Code initial de l’exercice 2 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (texte) Page
- Corrigé exercice 2 (vidéo) URL
- Corrigé exercice 3 (texte) Page
- Corrigé exercice 3 (vidéo) URL
Semaine 9 (vendredi 18 novembre)
- Partie théorique:
  Signaux: reconstruction et théorème d'échantillonnage
- Cours 9 File
- Lien vers les graphiques vus en cours URL
- Série 9 File
- Partie programmation:
  
  Manipulation d’images
  Introduction au miniprojet
- Cours 9 File
- Enregistrement Zoom URL
- Semaine 9 (Miniprojet 1) File
- miniproject-start.zip File
Semaine 10 (vendredi 25 novembre)
- Partie théorique:
  Compression sans pertes et entropie
- Cours 10 File
- Série 10 File
- Partie programmation:
  Suite du miniprojet
- Cours 10 File
- Enregistrement Zoom URL
- Série 10 (Miniprojet 2) File
- Nouveau contenu pour miniprojectutils.py (à copier-coller) Page
- Nouveau fichier miniprojectutils.py (à télécharger) File
- Structure de base pour find_seam (à copier-coller) Page
- Résultat attendu – americascup.zip File
- Résultat attendu – cats.zip File
- Résultat attendu – doves.zip File
- Résultat attendu – tower.zip File
Semaine 11 (vendredi 2 décembre)
- Partie théorique:
  Algorithmes de Shannon-Fano et Huffman
  Théorème de Shannon
  Compression avec pertes
- Cours 11 File
- Série 11 File
- Partie programmation:
  Compréhensions de listes
  Fonctions d’ordre supérieur
  Lambdas
- Cours 11 File
- Enregistrement Zoom URL
- Formation des groupes pour le miniprojet URL
- Cliquez ici pour connaître votre ID Moodle URL
- Série 11 File
- Code initial des exercices 1 et 2 Page
- Corrigé exercice 1 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (texte) Page
- Corrigé exercice 2 (vidéo) URL
Semaine 12 (vendredi 9 décembre)
- Partie théorique:
  Correction d'erreurs et codes de Reed-Solomon
  Réseaux: protocoles TCP et IP
- Cours 12 File
- Série 12 File
- Partie programmation — attention, pas de cours à 13h15:
  
  Lecture et écriture de fichiers texte
  
  Opération sur des chaînes de caractères
- Cours 12 File
- Enregistrement Zoom de l’année passée URL
- Série 12 File
- Fichier cars.txt File
- Corrigé exercices 1-2-3 (texte) Page
- Corrigé exercice 1 (vidéo) URL
- Corrigé exercice 2 (vidéo) URL
- Corrigé exercice 3 (vidéo) URL
- Rendu du miniprojet Assignment
Semaine 13 (vendredi 16 décembre)
- Partie théorique:
  Cryptographie (clé privée / clé publique) et sécurité
- Cours 13 File
- Série 13 File
- Partie programmation:
  Threads
  Problème des données partagées
  Exercices: examens des années précédentes
- Cours 13 File
- Enregistrement Zoom URL
- Examen final de 2018 (partie programmation seulement sur papier) File
- Proposition de corrigé Page
- Examen final de 2019 (partie programmation seulement sur papier) File
  Au 2 (a), sautez la première parle de la méthode __init__.
  Dans le QCM, sautez la question 20.
- Corrigé du QCM File
- Proposition de corrigé Page
- Examen final de 2021 (partie programmation seulement sur papier) File
- Proposition de corrigé Page
Semaine 14 (vendredi 23 décembre)
Examen final le vendredi 23 décembre de 8h15 à 10h30, en salles INF 1 (lettres A à F), INF 2 (lettres G à P) et SG 0211 (lettres R à Z + Paratte)

Matériel autorisé: deux pages A4 recto-verso manuscrites (ou préparées avec stylet+tablette), sur lesquelles vous pouvez écrire tout ce que vous pensez être important concernant le cours et les exercices.

Non-autorisé: appareil électronique tel que calculatrice, smartphone/watch, tablette, ordinateur, etc.