Information, calcul, communication
Weekly outline
-
- Théorie
- Cours: les vendredis de 14h15 à 16h00, en salles SG 1 et par Zoom
- Exercices: les vendredis de 16h15 à 17h15+, en salles DIA 004, DIA 005, INF 1, INF 119 et INJ 218
- Assistant principal: Pierre Quinton (pierre.quinton@epfl.ch)
- Cours: les vendredis de 14h15 à 16h00, en salles SG 1 et par Zoom
- Programmation
- Cours: les mardis de 14h15 à 15h00, en salle SG 1 / les cours enregistrés
- Exercices: les mardis de 15h15 à 17h00, en salles BC 07-08, CO 020, CO 021, CO 023, INF 3
Examen final: Lundi 24 juin, 15h15-18h15, en salles CE 1515, CE 4, CE 6, MA A1 10, PO 01.Matériel autorisé: 2 pages A4 recto-verso manuscrites, rien d'électroniqueRemarquez que dans la partie théorique, vous avez le droit de réutiliser les algorithmes vus en cours.-
You will need to choose one of the machines IC-CO-IN-SC-(INJ/MA)
- Théorie
-
Mardi: Programmation
Cours: 14h-15h, Exercices: 15h-17h
Vendredi: Théorie
Cours: 14-16h , Exercices: 16-17h+
Cours (rediffusion):
- Introduction
- Constantes, variables, fonctions
- Sortie standard
Cours:
-
Introduction et logistique
- Algorithmes: ingrédients de base
Exercices:
- Préparer l'environment (Unix + VS Code)
- Premiers programmes en C
Exercices:
- Lire et écrire des algorithmes
-
On vous encourage à installer l'environment pour développer en C sur votre propre ordinateur. Par contre vous pouvez également utiliser les machines virtuelles mises à disposition par l'EPFL.
Etape 1: Mise en place
Option 1: Installer l'environment sur votre ordinateur
Selon votre OS MacOS 🍏
Il vous faut installer le compilateur clang. Dans un terminal entrez la commande:
xcode-select --installInstallez VS Code pour Mac. Ensuite activez l'extension C/C++.
iTerm2 est un bon terminal pour Mac. Le gestionnaire de package Homebrew est aussi fortement conseillé.
Microsoft Windows 🪟
Installez WSL: https://learn.microsoft.com/fr-ch/windows/wsl/install
⚠️ Il est possible que vous deviez activer la virtualisation dans le BIOS de votre ordinateur...
Dans un terminal WSL installez le compilateur gcc et d'autres programmes utiles:
sudo apt-get updatesudo apt-get install build-essential gdb
Installez VS Code. Ensuite activez l'extension WSL, ainsi que l'extension C/C++.
Connectez-vous à WSL à partir de VS Code en cliquant sur l'icône verte:
puis
Dans WSL votre "C: Drive" sera sous /mnt/c.Linux 🐧
sudo apt-get updatesudo apt-get install build-essential gdb
Installez VS Code. Ensuite activez l'extension C/C++.Après avoir installé l'environment, suivez les exercices de la fiche ubuntu à partir de l'exercice 3. Pour Windows utilisez un terminal WSL.
Option 2: Utiliser les machines virtuelles
- Suivez les étapes de la fiche ubuntu.
- Ensuite effectuez la configuration initiale.
Etape 2: Premier programme en VS Code
Suivez les instructions de la fiche vscode.
Etape 3: La série
Essayez de résoudre les quelques exercices de la série.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Rappels
- Lecture depuis stdin
- Expressions et opérateurs
Cours:
- Algorithmes: complexité temporelle
- Notation "Grand Theta"
Exercices:
- Affichage, opérations, expressions
Exercices:
- Complexité temporelle
- Ecriture d'algorithmes
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Expressions, instructions conditionnelles
Cours:
- Récursivité
Exercices:
- Expressions, instructions conditionnelles
Exercices:
- Lire et écrire des algorithmes récursifs
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Instructions itératives (boucles)
Cours:
- Rendu de pièces de monnaie: algorithme
glouton et programmation dynamique - Introduction à la théorie de la calculabilité
Exercices:
- Boucles
Exercices:
- Divers exercices sur la récursivité
-
Une version précédente de la série contenait un exercice de plus, mais il a été déplacé à la série suivante.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Fonctions
Cours:
- Classes de complexité des problèmes
- Le problème du sac à dos
- Le problème du voyageur de commerce
Exercices
- Fonctions, boucles
Exercices:
- Identifier quels problèmes font partie de P/NP
-
Il y avait une coquille dans le 2ème exercice, dans l'exemple la somme des 9 éléments choisis de la matrice vaut 100, pas 90.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Pointeurs
Pas de cours (vendredi saint)Exercices:
- Boucles, Pointeurs, Fonctions
-
La question 6 est ambiguë...
Il y a deux options qui pourraient être justes:
La première teste les indices de 0 à 6 (car le plus grand i < 8 est i=7 et on regarde t[i-1])
for (i = 1; i < 8; i++) { if (!t[i-1]) zeros++; }et l'autre optionfor (i = 0; i <= (N-1); i++) { if ( !(t[i]) ) zeros++; }va de 0 à 7 et utilise N comme borne sup, pas la valeur 8.C'est la deuxième qui était marquée comme la bonne, mais je trouve la question ambiguë,car il n'y a que 7 éléments qui ont été initialisés...C'est tout à fait possible que le code marqué comme juste donne une mauvaise réponse,car il va regarder aussi le 8e élément non-initialisé qui pourrait avoir la valeur 0 par hasard.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Pointeurs et tableaux
Cours:- Représentation binaire des nombres entiers
- Représentation binaire des nombres réels
Exercices:
- Divers
Exercices:
- Nombres de bits nécessaires
- Utilisation de la représentation binaire
-
Mis à jour avec l'exemple de la pile.
-
L'exercice 5 est marqué avec une étoile, car il est un peu plus difficile à coder.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Révisions
- Debugging
Cours:- Portes logiques et opérations élémentaires
- Transistors et mémoire vive
- Circuits quantiques
Exercices:
- Mini-projet!
Exercices:
- Exercices sur les portes logiques et transistors
-
A rendre jusqu'au 26.04 au soir, modalités suivront.
-
Vous devez rendre un seul fichier .c comme celui ci.
Important:
- Les trois fonctions doivent être définies dans ce fichier. Si vous ne modifierez pas une des trois fonctions, laissez-la avec l'implémentation par défaut (`return -1`).
- Vous pouvez définir d'autres fonctions auxiliaires dans ce fichier si cela peut vous être utile.
- Attention! Il ne faut pas inclure une fonction main dans ce fichier.
Votre fichier doit compiler pour être pris en compte!
La commande suivante doit fonctionner sans avertissement, ni message d'erreur (si votre fichier s'appelle engine.c):
gcc -Wall -c engine.c -o engine.o
- Les trois fonctions doivent être définies dans ce fichier. Si vous ne modifierez pas une des trois fonctions, laissez-la avec l'implémentation par défaut (`return -1`).
-
Un banc de test pour vos fonctions.
Voici une nouvelle version qui mesure aussi le temps d'execution de la fonction en millisecondes.
-
Première vidéo (en anglais) de Ben Eater sur le fonctionnement d'une diode, le plus simple des semi-conducteurs
-
Deuxième vidéo (toujours en anglais) de Ben Eater sur le fonctionnement d'un transistor
-
Mardi: Programmation
Cours: 14h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Projets multi-fichier
- Préprocesseur
- Lire/écrire des fichiers
Cours:
- Signaux: fréquences et bande passante
- Filtrage de signaux
- Echantillonnage de signaux
- Effet stroboscopique
Exercices:
- Mini-projet
Exercices:- Bande passante
- Signaux périodiques et apériodiques
- Filtre à moyenne mobile
-
Un fichier engine.c avec les trois fonctions.
-
Remplacez tout simplement le fichier engine.c dans ce projet par celui que vous venez de coder et jouez à Candy Crush! La version fournie a un fichier engine.c qui ne fait rien, donc vous pouvez uniquement naviguer le tableau avec les flèches... (Fonctionne uniquement sous Mac et Linux, notamment sur les machines de l'EPFL).
$ unzip crush.zip $ cd crush $ make
Vous pour une taille plus grande du tableau lancez le programme avec l'option -s. Par exemple, une taille de 20x20 utilisez
$ ./crush -s 20
Une fois dans le jeu utilisez la touche "?" pour suggérer l'action suivante, "a" pour jouer une action suggérée, "A" pour utiliser le pilote automatique (re-appuyez sur "A" pour l'arrêter), et "q" pour sortir!
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Types composés
Cours:
- Reconstruction de signaux
- Théorème d'échantillonnage
- Sous-échantillonnage
Exercices: - Structures, données tabulaires
Exercices:
- Filtrer avant d'échantillonner
- Phénomène de battement
- Formule d'interpolation
-
Dans le présent dossier, vous trouvez les fichiers avec le morceau de Jazz (‘’Our love is here to stay’’, de Georges Gerschwin, joué par Roland Kirk) dans ses différentes versions, ainsi que leur analyse spectrale.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours ANNULÉ:
- -
Cours:
- Introduction à la compression de données
- Entropie
Exercices: Séance ANNULÉE
- -
Exercices:
- Calculs d'entropie
- Comparaison d'entropies
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Listes
Cours:
- Algorithmes de Shannon-Fano et Huffman
- Théorème de Shannon
- Compression avec pertes
Exercices:
- Listes
Exercices:
- Algorithmes de compression
- A la recherche d'un trésor
- Codage par plages (RLE)
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercises: 16-17h+
Cours (rediffusion):
- Récursivité
Cours:
- Correction d'erreurs: introduction
- Codes de Reed-Solomon
- Reseaux: Protocole TCP (algorithme AIMD)
- Réseaux: protocole IP (algorithme BFS et routage)
Exercices:
- Récursivité
Exercices:
- Distance minimale
- Codage de Hamming
- Code-barres
- Algorithme AIMD et variantes
- Exercices de routage
-
Nouvelle version corrigée - la complexité est O(2^n), pas O(n^2)
-
Petit changement de programme: je ne parlerai que de correction d'erreurs dans le cours aujourd'hui.
La seconde partie du cours sur les réseaux devient de fait optionnelle.
-
Vu le changement de programme du cours aujourd'hui, focalisez-vous sur les exercices 1,2 et 5*.
Vous pouvez donc laisser tomber les exercices 3 et 4 sur les réseaux.
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 14-16h, Exercices: 16-17h+
Cours (rediffusion):
- Fichiers
Cours:
- Cryptographie à clé secrète
- Cryptographie à clé publique
Exercises:
- Fichiers
Exercices:
- Protocoles de Diffie-Hellman et El-Gamal
- Recherche de grands nombres premiers
-
Version avec tous les slides montrés pendant le cours.
-
V2
3 exos sur les fichiers, 3 exos de révision.
-
