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), GC B3 31 (lettres K à O), 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
- Cours 1 annoté File
- Comment écrire un algorithme en pseudo-code? File
- Série 1 File
- Solutions 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
This week
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()
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
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
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
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: List, Set
  Dictionnaires
  Classes simples
- Partie programmation: examens d’entraînement
- Exemples de questions vrai/faux d'une année précédente (partie programmation) File
- Examen intermédiaire de 2019 File
  Sautez les indications sur la méthode __init__ du 4 (a) et sautez le 4 (b) et la méthode __repr__. Le corrigé a été adapté en ce sens.
- Code initial Page
- Proposition de corrigé Page
- Examen intermédiaire de 2018 File
  Sautez le 3 (f), qui utilise les compréhensions de listes, que nous n'avons pas discutées. Pour l'exercice 4 (a), déclarez une dataclass comme on l'a appris cette année au cours et ne vous souciez pas de la méthode __init__. Sautez le 4 (b) et la méthode __repr__. Le corrigé a été adapté en ce sens.
- Code initial Page
- Proposition de corrigé Page
- Examen intermédiaire de 2017 File
  Pour le 4 (a): utilisez Optional['Person'] comme type pour les champs best_friend et worst_enemy et sautez les indications sur la méthode __init__. Sautez le 4 (b) et la méthode __repr__. Le corrigé a été adapté en ce sens.
- Code initial Page
- Proposition de corrigé Page
- Ces deux enregistrements sont tirés du cours de l'année passée et montrent comment résoudre cet examen.
- 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, INF 2, AAC 006, AAC 008 et AAC 014).

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
- Partie théorique:
  Circuits logiques et transistors
  Circuits quantiques
- Cours 7 File
- Série 7 File
Semaine 8 (vendredi 11 novembre)
- Partie théorique:
  Signaux: filtrage et échantillonnage
- Cours 8 File
- Série 8 File
- Partie programmation:
  Interfaces graphiques: Tkinter
  Widgets, grid, événements
Semaine 9 (vendredi 18 novembre)
- Partie théorique:
  Signaux: reconstruction et théorème d'échantillonnage
- Cours 9 File
- Série 9 File
- Partie programmation:
  
  Compréhensions de listes
  
  Fonctions d’ordre supérieur
Semaine 10 (vendredi 25 novembre)
- Partie théorique:
  Compression sans pertes et entropie
- Cours 10 File
- Série 10 File
- Partie programmation:
  Fonctions d’ordre supérieur (suite)
  Classes et sous-classes
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:
  Threads
  Problèmes des données partagées
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:
  
  Lecture et écriture de fichiers texte
  
  Opération sur des chaînes de caractères
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:
  Révisions
Semaine 14 (vendredi 23 décembre)
Examen final le vendredi 23 décembre de 8h00 à 11h00, en salles INF 1, INF 2 et SG 0211.