Skip to main content
Side panel
Home
More
English (en)
English (en)
Français (fr)
You are currently using guest access
Log in
Home
Open course index
CS-119(d)
Semaine 4 : for & while / Théorie du calcul (P & NP)
Transparents complément théorie I.3
Transparents complément théorie I.3
Click
reviews-handout-04.pdf
link to view the file.
◄ I.3 Théorie du calcul 9 : conclusions : (1) Et Prem ? (2) Et en pratique ? [07:53]
Jump to...
Jump to...
Annonces du cours
Forum de discussion
Descriptif du cours (à lire absolument)
Série « d'exercices » : prise en main
Documentation complémentaire : UNIX, fichiers, éditeurs
Transparents « Introduction générale du cours »
Transparents leçon « Introduction »
Transparents leçon I.1 (« algorithmes »)
0 Introduction, 1 : qu'est-ce que l'Informatique ? [13:35]
0 Introduction, 2 : les trois domaines de l'informatique [09:08]
0 Introduction, 3 : quatrième pilier de la culture [10:26]
0 Introduction, 4 : déroulement du cours ICC [08:20]
I.1 Calcul et algorithmes 1.1 : qu'est-ce qu'un algorithme ? [06:11]
I.1 Calcul et algorithmes 1.2 : premier exemple d'algorithme [11:25]
I.1 Calcul et algorithmes 1.3 : méthodologie [06:02]
I.1 Calcul et algorithmes 1.4 : première définition de « algorithme » [10:15]
Transparents complément théorie 0 & I.1a
Exercices semaine 1
Corrigé des exercices de la semaine 1
Importance de l'informatique : conférence du 26.10.2019 de Gérard Berry (professeur émérite au Collège de France ; médaille d’or du CNRS en 2014)
Semaine 1 du MOOC : Initiation à la programmation
Compiler en C++ sur les VM de l'Ecole
[optionnel] Tutoriel QtCreator
Transparents de complément « Variables & Expressions »
Transparents leçon I.1 (« algorithmes »)
I.1 Calcul et algorithmes 2.1 : ingrédients de base des algorithmes [10:51]
I.1 Calcul et algorithmes 2.2 : exemple (équation du 2nd degré) [05:23]
I.1 Calcul et algorithmes 2.3 : algorithmes de recherche (1) : deux exemples [12:33]
I.1 Calcul et algorithmes 2.4 : complexité (temporelle) d'un algorithme (1) : définition et exemples [17:46]
I.1 Calcul et algorithmes 2.5 : algorithmes de recherche (2) : recherche par dichotomie [11:27]
I.1 Calcul et algorithmes 2.6 : complexité (temporelle) d'un algorithme (2) : notation Theta [07:37]
I.1 Calcul et algorithmes 2.7 : algorithmes de recherche (3) : résumé [02:57]
I.1 Calcul et algorithmes 2.8 : algorithmes de tri [08:31]
I.1 Calcul et algorithmes 2.9 : algorithmes de plus court chemin et conclusion (et retour sur les algorithmes de recherche) [13:48]
Transparents complément théorie I.1b
Exercices (semaine 2)
Corrigé des exercices de la semaine 2
Complément (PDF) : comment bien écrire un algorithme ?
Complément vidéo : Méthode de calcul de la complexité d'un algorithme
Complément vidéo : L'algorithme EdgeRank (Facebook)
Complément vidéo : L'algorithme PageRank (Google)
Semaine 2 du MOOC : Structures de contrôle (1) : branchements conditionnels
Transparents de complément « branchements conditionnels »
Solution de l'étude de cas « branchements conditionnels »
Transparents leçon I.2
I.2 Stratégies de résolution de problèmes 1 : présentation générale [19:09]
I.2 Stratégies de résolution de problèmes 2 : récursion [15:19]
I.2 Stratégies de résolution de problèmes 3 : somme des N premiers entiers (récursif) [06:34]
I.2 Stratégies de résolution de problèmes 4 : somme des premiers entiers (récursif) : complexité [05:30]
I.2 Stratégies de résolution de problèmes 5 : tri par insertion (récursif) [07:29]
I.2 Stratégies de résolution de problèmes 6 : programmation dynamique [16:00]
I.2 Stratégies de résolution de problèmes 7 : complexité du calcul des coefficients du binôme par programmation dynamique [03:46]
I.2 Stratégies de résolution de problèmes 8 : programmation dynamique : algorithmes de plus courts chemins [16:45]
tri par insertion : solutions des 3 sous-algorithmes
Transparents complément théorie I.2
Exercices (semaine 3)
Corrigé des exercices de la semaine 3
Complément vidéo : récursion
Semaine 3 du MOOC : Structures de contrôle (2) : boucles et itératons
Transparents de complément « boucles & itérations »
Solution de l'étude de cas « boucles & itérations »
Transparents leçon I.3
I.3 Théorie du calcul 1 : définition formelle d'algorithmes : machines de Turing [11:44]
I.3 Théorie du calcul 2 : exemple d'une machine de Turing [10:41]
I.3 Théorie du calcul 3 : LA machine de Turing universelle [05:33]
I.3 Théorie du calcul 4 : problèmes : définition, puis comptage (dénombrabilité) [16:01]
I.3 Théorie du calcul 5 : problèmes non décidables [17:15]
I.3 Théorie du calcul 6 : complexité des problèmes : P [05:55]
I.3 Théorie du calcul 7 : complexité des problèmes : NP [07:17]
I.3 Théorie du calcul 8 : exemple de problèmes dans NP [09:30]
I.3 Théorie du calcul 9 : conclusions : (1) Et Prem ? (2) Et en pratique ? [07:53]
Exercices (semaine 4)
Corrigé des exercices de la semaine 4
Complément vidéo : Calculabilité
Complément vidéo : Non-dénombrabilité de l'ensemble des réels
Complément vidéo : Décidabilité et indécidabilité
Complément vidéo : P vs NP
Complément vidéo : la machine de Turing (1/2)
Complément vidéo : la machine de Turing (2/2)
Semaine 4 du MOOC : Fonctions
Exercice supplémentaire C++ : PGDC [version HTML]
Exercice supplémentaire C++ : PGDC [version PDF]
Corrigé PGDC [HTML]
Corrigé PGDC [PDF]
Liste des exercices de C++ spécifiques à ICC (lien programmation - théorie)
Transparents de complément « fonctions (1/2) »
Solution de l'étude de cas « fonctions (1/2) : somme et produit de chiffres »
Transparents leçon I.4
I.4 Représentation de l'information 1 : conventions de représentation [08:12]
I.4 Représentation de l'information 2 : représentations en binaire [08:22]
I.4 Représentation de l'information 3 : représentation des entiers positifs [14:58]
I.4 Représentation de l'information 4 : représentation des entiers négatifs [18:58]
I.4 Représentation de l'information 5 : domaine couvert de la représentation des entiers négatifs [09:07]
I.4 Représentation de l'information 6 : représentation des nombres à virgule : erreur absolue et erreur relative [11:55]
I.4 Représentation de l'information 7 : représentation des nombres à virgule : virgule flottante [07:02]
I.4 Représentation de l'information 8 : OPTIONNEL : représentation des nombres à virgule : virgule flottante étendue [04:54]
I.4 Représentation de l'information 9 : virgule flottante : conséquences pour la programmation [07:15]
Transparents complément théorie I.4
Exercices (semaine 5)
Corrigé des exercices de la semaine 5
Compléments vidéo: Carte conceptuelle
Complément vidéo : Représentation de l’information en binaire
Complément vidéo : Machines numériques : organisation de la mémoire centrale
Complément vidéo : Représentation des entiers en binaire
Complément vidéo : Représentation d’entiers relatifs en binaire – Machines Numériques
Complément vidéo : Domaine couvert avec complément à 2 – Machines Numériques
Complément vidéo : Représentation de l’information en hexadécimal
Complément vidéo : Représentation des nombres à virgule en virgule fixe
Complément vidéo : Erreur relative en virgule fixe
Complément vidéo : Représentation de nombres en virgule flottante
Complément vidéo : Représentation des nombres à virgules conversion décimal flottant IEEE 754 – Machines Numériques
Semaine 4 du MOOC : Fonctions
Transparents de complément « fonctions (2/2) »
Solution de l'étude de cas « fonctions (2/2) : int2bin() et augmente() »
Exercice supplémentaire C++ (lien ICC) : factorielle récursive [version HTML]
Corrigé exercice factorielle récursive
Exercice supplémentaire C++ (lien ICC) : factorielle récursive [version PDF]
Corrigé exercice factorielle récursive [version PDF]
Transparents leçon II.1
II.1 Échantillonnage des signaux 1 : introduction [07:19]
II.1 Échantillonnage des signaux 2 : signal et fréquence [13:35]
II.1 Échantillonnage des signaux 3 : bande passante et spectre [07:15]
II.1 Échantillonnage des signaux 4 : filtrage (passe-bas idéal) [11:15]
II.1 Échantillonnage des signaux 5 : échantillonnage [06:25]
II.1 Échantillonnage des signaux 6 : échantillonnage d'une sinusoïde pure [06:46]
II.1 Échantillonnage des signaux 7 : effet stroboscopique (repliement de spectre) [04:13]
Transparents complément théorie II.1
Semaine 5 du MOOC : Tableaux
Transparents de complément « vector »
Solution de l'étude de cas « vector : moyenne mobile »
Exercice supplémentaire C++ (lien ICC) : tris [version HTML]
Corrigé exercice tris
Exercice supplémentaire C++ (lien ICC) : tris [version PDF]
Corrigé exercice tris [version PDF]
Objectifs pédagogiques C++
Objectifs pédagogiques Module 1
Examen 1 de 2022
Examen 1 de 2021
Corrigé de l'examen no1 de 2022
Corrigé de l'examen no1 de 2021
Semaine 6 du MOOC : chaînes de caractères (et structures)
Transparents de complément « array & string »
Solution de l'étude de cas « palindromes »
Exercice supplémentaire C++ (lien ICC) : conversions décimal-binaire [version HTML]
Corrigé exercice conversions décimal-binaire
Exercice supplémentaire C++ (lien ICC) : conversions décimal-binaire [version PDF]
Corrigé exercice conversions décimal-binaire [version PDF]
Exercice supplémentaire C++ (lien ICC) : entropie [version HTML]
Corrigé exercice entropie
Exercice supplémentaire C++ (lien ICC) : entropie [version PDF]
Corrigé exercice entropie [version PDF]
Exercice supplémentaire C++ (lien ICC) : tours de Hanoï [version HTML]
Corrigé exercice tours de Hanoï
Exercice supplémentaire C++ (lien ICC) : tours de Hanoï [version PDF]
Corrigé exercice tours de Hanoï [version PDF]
Transparents leçon II.2
II.2 Reconstruction (théorème d'échantillonnage) 1 : rappels [03:25]
II.2 Reconstruction (théorème d'échantillonnage) 2 : reconstruction d'un signal (en général) [14:29]
II.2 Reconstruction (théorème d'échantillonnage) 3 : formule de reconstruction [07:40]
II.2 Reconstruction (théorème d'échantillonnage) 4 : théorème d'échantillonnage [04:42]
II.2 Reconstruction (théorème d'échantillonnage) 5 : exemples de reconstruction [04:29]
II.2 Reconstruction (théorème d'échantillonnage) 6 : effet stroboscopique expliqué [04:46]
II.2 Reconstruction (théorème d'échantillonnage) 7 : éléments de démonstration du th. d'échantillonnage [12:39]
II.2 Reconstruction (théorème d'échantillonnage) 8 : sous-échantillonnage (effet stroboscopique) et filtrage [10:35]
II.2 Reconstruction (théorème d'échantillonnage) 9 : conclusion [01:49]
Transparents complément théorie II.2
Exercices (semaine 8)
Corrigé des exercices semaine 8
Complément vidéo : La formule de reconstruction
son jazz original 44.1 kHz
jazz avec repliement 8820 Hz
jazz filtré 4400 Hz
jazz sans repliement (filtré) à 8820 Hz
Semaine 6 du MOOC : (chaînes de caractères et) structures
Transparents de complément « struct »
Solution de l'étude de cas « fondue »
Exercice supplémentaire C++ (lien ICC) : échantillonnage [version HTML]
Corrigé exercice échantillonnage
Exercice supplémentaire C++ (lien ICC) : échantillonnage [version PDF]
Corrigé exercice échantillonnage [version PDF]
Exercice supplémentaire C++ (lien ICC) : problème du sac à dos [version HTML]
Corrigé exercice du problème du sac à dos
Exercice supplémentaire C++ (lien ICC) : problème du sac à dos [version PDF]
Corrigé exercice problème du sac à dos [version PDF]
Exercice supplémentaire C++ (lien ICC) : codes de Huffman [version HTML]
Corrigé exercice codes de Huffman
Exercice supplémentaire C++ (lien ICC) : codes de Huffman [version PDF]
Corrigé exercice codes de Huffman [version PDF]
Exercice supplémentaire C++ (lien ICC) : machines de Turing [version HTML]
Corrigé exercice machines de Turing
Exercice supplémentaire C++ (lien ICC) : machines de Turing [version PDF]
Corrigé exercice machines de Turing [version PDF]
Devoir à la maison : discussions on-line
Transparents leçon II.3
II.3 Compression des données et entropie 1 : rappels et introduction [08:13]
II.3 Compression des données et entropie 2 : entropie comme « jeu des questions » [09:34]
II.3 Compression des données et entropie 3 : définition de l'entropie [03:53]
II.3 Compression des données et entropie 4 : interprétation de l'entropie [03:47]
II.3 Compression des données et entropie 5 : propriétés de l'entropie [01:23]
II.3 Compression des données et entropie 6 : démonstration des propriétés de l'entropie [24:26]
II.3 Compression des données et entropie 7 : illustration des propriétés de l'entropie [02:10]
II.3 Compression des données et entropie 8 : compression [05:15]
II.3 Compression des données et entropie 9 : algorithme de Shannon-Fano [10:05]
II.3 Compression des données et entropie 10 : compression en pratique [03:46]
II.3 Compression des données et entropie 11 : conclusion (temporaire) [01:34]
Transparents complément théorie II.3
Exercices (semaine 9)
Annexe : calcul rapide de l'entropie
Corrigé des exercices de la semaine 9
Complément mathématique : concavité du logarithme
Complément vidéo : l'entropie
Semaine 7 du MOOC : pointeurs et références
Transparents de complément « pointeurs & références »
Solution de l'étude de cas « réseau d'amis »
[HTML] Exercice C++ « niveau 0 » : pointeurs : listes chaînées
[PDF] Exercice C++ « niveau 0 » : pointeurs : listes chaînées
[HTML] Exercices supplémentaires C++ sur les pointeurs
[HTML] Corrigés exercices supplémentaires sur les pointeurs
[PDF] Exercices supplémentaires C++ sur les pointeurs
[PDF] Corrigés exercices supplémentaires sur les pointeurs
Transparents leçon II.4
II.4 Compression des données et th. de Shannon 1 : rappels [03:30]
II.4 Compression des données et th. de Shannon 2 : code de Shannon-Fano (général) [15:54]
II.4 Compression des données et th. de Shannon 3 : exemple de calcul de l'entropie [03:26]
II.4 Compression des données et th. de Shannon 4 : définitions [06:21]
II.4 Compression des données et th. de Shannon 5 : théorème de Shannon [01:45]
II.4 Compression des données et th. de Shannon 6 : démonstration du théorème de Shannon [14:23]
II.4 Compression des données et th. de Shannon 7 : analyse de performance du th. de Shannon [03:32]
II.4 Compression des données et th. de Shannon 8 : codes de Huffman [10:55]
II.4 Compression des données et th. de Shannon 9 : résumé [05:14]
II.4 Compression des données et th. de Shannon 10 : compression avec pertes [16:29]
II.4 - 11 : Conclusions sur le module II [01:41]
Transparents complément théorie II.4
Exercices (semaine 10)
Corrigé des exercices de la semaine 10
Complément vidéo : codes de Shannon-Fano
Complément vidéo : codes de Huffman
Vidéo du cours « C++ : entrées/sorties »
Transparents cours C++ « entrées/sorties »
Transparents de complément « entrées / sorties »
Solution de l'étude de cas « entrées / sorties » (sapin)
Tutoriel « entrées/sorties » 1 [HTML]
Tutoriel « entrées/sorties » 2 [HTML]
Tutorlels « entrées/sorties » 1 & 2 [PDF]
Exercices de C++ « entrées/sorties » [HTML]
Corrigés des exercices de C++ « entrées/sorties » [HTML]
Exercices C++ « entrées/sorties » [PDF]
Corrigés des exercices C++ « entrées/sorties » [PDF]
Transparents leçon III.1
III.1 Architecture des ordinateurs 1 : introduction [04:26]
III.1 Architecture des ordinateurs 2 : des algorithmes aux programmes (compilation) [16:54]
III.1 Architecture des ordinateurs 3 : construction du CPU [15:32]
III.1 Architecture des ordinateurs 4 : langage machine [05:32]
III.1 Architecture des ordinateurs 5 : calculs électroniques (à base de transistors) [16:22]
III.1 Architecture des ordinateurs 6 : mémorisation électronique (à base de transistors) [09:20]
III.1 Architecture des ordinateurs 7 : résumé [03:48]
III.1 Architecture des ordinateurs 8 : performance des CPU (computer engineering) [15:37]
Transparents complément théorie II.4 et III.1
Exercices (semaine 11)
Corrigé des exercices de la semaine 11
Vidéo du cours « C++ : gestion des erreurs »
Transparents cours C++ « erreurs & exceptions »
dernier exemple du cours : temperatures.cc
Transparents de complément semaine 12 (exception et synthèse du cours)
Tutoriel « exceptions » [HTML]
Tutorlels « exceptions » [PDF]
Exercices de C++ « erreurs & exceptions » [HTML]
divisions.cc
gdbTest.zip
Corrigés des exercices de C++ « erreurs & exceptions » [HTML]
Exercices C++ « erreurs & exceptions » [PDF]
Corrigés des exercices C++ « erreurs & exceptions » [PDF]
Transparents leçon III.2
Vidéo du cours « stockage et transmission des données »
III.2 Stockage et transmission des données 1 : introduction ; besoin de structure [14:22]
III.2 Stockage et transmission des données 2 : méta-données pour les disques [08:21]
III.2 Stockage et transmission des données 3 : accès à l'information [17:11]
III.2 Stockage et transmission des données 4 : protocoles et couches réseaux [12:42]
III.2 Stockage et transmission des données 5 : routage et transport Internet (TCP/IP) [06:55]
III.2 Stockage et transmission des données 6 : adressage et routage IP [18:08]
III.2 Stockage et transmission des données 7 : transport TCP et couche 5 [06:49]
Transparents complément théorie III.1 et III.2
Exercices (semaine 12)
Corrigé des exercices de la semaines 12
Tutoriel : debugging avec Qt Creator
Transparents leçon « sécurité »
Vidéo du cours « sécurité informatique 1 »
IV Sécurité informatique 1 : introduction, menaces et défenses [15:18]
IV Sécurité informatique 2 : exemple : destruction/disponibilité [06:27]
IV Sécurité informatique 3 : cryptographie : cadre général [16:33]
IV Sécurité informatique 4 : cryptographie symétrique (One-Time Pad) [11:32]
IV Sécurité informatique 5 : sécurité algorithmique (DES) [07:06]
IV Sécurité informatique 6 : cryptographie à clés publiques (RSA) [24:49]
IV Sécurité informatique 7 : intégrité et responsabilité [09:53]
Transparents complément théorie « sécurité »
Exercices de théorie (vendredi, semaine 13)
Corrigé des exercices de la semaine 13
Objectifs pédagogiques Module 2
Objectifs pédagogiques Module 3
Objectifs pédagogiques en C++
Examen final 2022
Examen final 2021
Corrigé de l'examen final 2022
Corrigé de l'examen final 2021
Descriptif du cours (à lire absolument)
fiches résumé de C++
Exercices de C++ spécifiques à ICC (lien programmation - théorie)
Environnement UNIX -- Fichiers -- Éditeur
Livre de référence pour la théorie : Découvrir le numérique, PPUR, 2016.
Livre d'exercices de C++ : « C++ par la pratique » (4e ed.), PPUR, 2017.
Vidéo de l'ancien cours sur les hiérachies de mémoires (hors programme en 2022)
Transparents de l'ancien cours sur les hiérarchies de mémoires (hors programme en 2022)
vidéo du cours (hors programme) « Sécurité (2) »
Transparents « Sécurité (2) » (hors programme)
Instal. programmation : Ubuntu sous Windows (WSL)
Sécurité : jeu de la RTS sur la gestion des données privées
Exercices (semaine 4) ►
Contact
EPFL CH-1015 Lausanne
+41 21 693 11 11
Follow the pulses of EPFL on social networks
Accessibility
Legal notice
Privacy policy
© 2023 EPFL, all rights reserved
