Information, calcul, communication
Weekly outline
-
- Théorie
- Cours: les vendredis de 13h15 à 15h00, en salles SG 1 et par Zoom
- Exercices: les vendredis de 15h15 à 16h15+, en salles:
Lettres A à H: CO 010, CO 011, CO 015, CO 016, CO 017
Lettres J à Z: CO 120, CO 121, CO 122, CO 123, CO 124
- Cours: les vendredis de 13h15 à 15h00, 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
- Date de l'examen final: mardi 24 juin, de 15h15 à 18h15, en salles CE 1 4, CE 1 515, CE 1 6, PO 01 (répartition dans les salles à venir)
Répartition des points: 50 points pour la théorie (pas de QCM), 35 points pour la programmation (dont 10 QCM valant chacune 2 points)
Matériel autorisé: 2 pages A4 recto-verso manuscrites, rien d'électronique sauf une calculatrice simple (du type TI-30 eco RS, ou même plus simple: il n'y a bien sûr pas besoin que ce soit précisément ce modèle!)
Remarquez finalement 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)
-
Ce quiz compte pour 5% de la note finale.
Vous avez droit à 2 tentatives d’une heure.
- Théorie
-
Mardi: Programmation
Cours: 14h-15h, Exercices: 15h-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
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: 13-15h , Exercices: 15-16h+
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: 13-15h , Exercices: 15-16h+
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: 13-15h , Exercices: 15-16h+
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é
-
Il y avait une (petite) erreur dans l'énoncé -- 20 n'est pas un diviseur de 110...
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
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
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
- Pointeurs
Cours:
- Représentation binaire des nombres entiers
- Représentation binaire des nombres réels
Exercices:
- Boucles, Pointeurs, Fonctions
Exercices:
- Nombres de bits nécessaires
- Utilisation de la représentation binaire
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
Le cours aura lieu au Rolex entre 14h et 15h.- Pointeurs et tableaux
Cours:
- Portes logiques et opérations élémentaires
- Transistors
- Circuits quantiques
Exercices:
- Divers
Exercices:
- Exercices sur les portes logiques et transistors
-
Nouvelle version -- meilleure illustration de l'implémentation de la pile + motivation des pointeurs.
-
L'exercice 5 est marqué avec une étoile, car il est un peu plus difficile à coder.
-
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: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
- Types composés
Cours:
- Signaux: fréquences et bande passante
- Filtrage de signaux
- Echantillonnage de signaux
- Effet stroboscopique
Exercices:
- Structs
Exercices:
- Bande passante
- Signaux périodiques et apériodiques
- Filtre à moyenne mobile
-
Attention à la lecture, dans le fichier texte l'ordre des colonnes est:
`no_client`, `date`, `no_tel_appel`, `minutes`.L'ordre des champs dans la définition proposée de `struct call_record` est différent, donc attention à ce que vous mettez dans `scanf`.
-
Mardi: Programmation
Cours: 14h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
- Types composés
- Listes
Pas de cours (vendredi saint) Exercices:
- Listes
-
Erratum:
Slides 21, 22:
remplacer `malloc(sizeof(cell_t))` par `malloc(sizeof(struct cell))`
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
- Projets en C
Cours:
- Reconstruction de signaux
- Théorème d'échantillonnage
- Sous-échantillonnage
Exercices: - Mini-projet
Exercices:
- Filtrer avant d'échantillonner
- Phénomène de battement
- Formule d'interpolation
-
La date limite pour rendre le projet est le
vendredi 9 mailundi 12 mai le soir. Il faut rendre uniquement un fichier `engine.c` avec les fonctions requises (sans fonction `main`). Vous pouvez définir d'autres fonctions dont vous auriez besoin dans le même fichier.Précisions (30.04.2024)
- La date limite du projet est reportée au lundi 12 mai, vos délégués m'ont informé que vous aviez deux autres projets en cours.
- Question 3: dans le projet de test, le fichier `engine.c` contenait une instruction `return board->n_rows-piece->size-1;` qu'il faut remplacer par votre code, ne la conservez pas.
- Question 5: La hauteur (H) et le nombre de trous (T) sont calculés *avant* l'élimination des potentielles lignes remplies.
- Il ne faut pas se soucier d'afficher des messages d'erreur, tout ce qui compte est la valeur de retour de votre fonction et la valeur des paramètres "de sortie".
- Le projet de test vous donne seulement un point de départ pour tester vos fonctions, c'est à vous de tester chaque fonction et d'imaginer des valeurs possibles pour la grille de jeu et pour la forme des pièces, etc.
- Pas besoin de mettre à jour `engine.h` avec les signatures des fonctions auxiliaires que vous définissez, puisqu'elles seront utilisées uniquement dans le fichier engine.c -- juste définissez-les au début du fichier `engine.c` avant la définition des fonctions requises.
Bon projet!
-
Editez le fichier `test.c` pour tester le code de `engine.c`.
Pour compiler le projet rentrez dans le folder `test_engine` et tapez `make`.
Update: Corrigé un bug dans la création d'une grille de jeu (merci Yaëlle Dutoit!)
-
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: 13-15h , Exercices: 15-16h+
Cours (Rediffusion):
- Debugging & Fichiers
Cours:
- Introduction à la compression de données
- Entropie
Exercices:
- Mini-projet
Exercices:
- Calculs d'entropie
- Comparaison d'entropies
-
Voici le code pour jouer à Tetris.
Une fois votre code de `engine.c` testé, vous pouvez le brancher dans ce projet et le voir en action!
Attention, comme indiqué pendant le cours votre note sera déterminée par des tests automatiques sur chaque fonction contenue dans `engine.c`.
Compiler le projet
Ce projet ne fonctionne que sous Mac et Linux (y compris Windows + WSL). Le système Windows natif n'est pas supporté...
Le projet contient un fichier `engine.c` qui compile, mais qui ne fait rien d'intéressant. Remplacez-le par votre code.
Il suffit de faire `make` dans le répertoire du projet (ou alors `make all`) et l'exécutable `tetris` apparaîtra.
Assurez-vous que la version dev de la bibliothèque `ncurses` est bien installée. Si votre compilation échoue avec un message d'erreur indiquant que le fichier `ncurses.h` est introuvable, c'est que cette bibliothèque n'est pas installée. Pour l'installer sur Linux lancez la commande suivante (le système vous demandera le MDP root):
sudo apt-get install libncurses5-dev
Jouer à Tetris
Vous pouvez contrôler les pièces avec les flèches (flèche vers le haut = rotation) et avec la touche espace (envoie la pièce en bas de la grille).
Les touches + et - contrôlent la vitesse à laquelle descendent les pièces.
Si vous appuyez sur 'a', le pilote automatique entre en jeu et joue pour vous. S'il réagit trop lentement, appuyez sur ^ pour le faire aller plus vite, et sur _ pour le ralentir. Si vous voulez repasser en mode manuel, appuyez de nouveau sur 'a'.
Pour sortir il suffit d'appuyer sur `q` ou sur la touche Esc.
Vous pouvez vous amuser à modifier le fichier `pieces.txt` pour dessiner vos propres pièces.
-
Le rendu consiste en un seul fichier engine.c qui contient vos implémentations des 6 fonctions demandées.
Assurez-vous que le fichier compile correctement -- la commande suivante ne devrait afficher aucun message:gcc -c -Wall engine.c -o engine.o
Vérifiez également que les signatures des fonctions sont identiques à celles de l'énoncé et que toute fonction auxiliaire que vous auriez pu définir est également comprise dans le fichier engine.c
-
ICC-T Solutions 10 File
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
- Fonctions récursives
Cours:
- Algorithmes de Shannon-Fano et Huffman
- Théorème de Shannon
- Compression avec pertes
Exercices:
- Fichiers
- Fonctions récursives
Exercices:
- Algorithmes de compression
- A la recherche d'un trésor
- Codage par plages (RLE)
-
ICC-T Solutions 11 File
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
Cours (rediffusion):
- Récursivité
Cours:
- Correction d'erreurs: introduction
- Codes de Reed-Solomon
- Distance minimale
Exercices:
- Récursivité
Exercices:
- Distance minimale
- Codage de Hamming
- Code-barres
-
ICC-T Solutions 12 File
-
Mardi: Programmation
Cours: 14-15h, Exercices: 15-17h
Vendredi: Théorie
Cours: 13-15h , Exercices: 15-16h+
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
-
ICC-T Solutions 13 File
