Advanced information, computation, communication I (CS-101)

Advanced information, computation, communication I (CS-101), cours de première année en Systèmes de communication à l’EPFL, donné par Olivier Lévêque, Rüdiger Urbanke (7 crédits). Sur BA1 Planner : 14 fiches de révision et 70 flashcards.

Programme, semaine par semaine

Logique propositionnelle

1.1 Propositions et valeurs de vérité · 1.2 Connecteurs logiques (¬, ∧, ∨, →, ↔) · 1.3 Tables de vérité · 1.4 Traduction du langage naturel en logique

Formes normales et logique des prédicats

2.1 Équivalences logiques et lois de De Morgan · 2.2 Formes normales conjonctive (CNF) et disjonctive (DNF) · 2.3 Prédicats et quantificateurs ∀ / ∃ · 2.4 Négation et imbrication des quantificateurs

Méthodes de preuve

3.1 Preuve directe · 3.2 Contraposée et raisonnement par l'absurde · 3.3 Preuve par cas et sans perte de généralité · 3.4 Contre-exemples et preuves d'existence

Ensembles et fonctions

4.1 Ensembles, inclusion, ensemble des parties · 4.2 Union, intersection, différence, complémentaire · 4.3 Produit cartésien · 4.4 Fonctions : injectivité, surjectivité, bijectivité, composition

Relations

5.1 Relations binaires et représentations · 5.2 Réflexivité, symétrie, antisymétrie, transitivité · 5.3 Relations d'équivalence et classes · 5.4 Relations d'ordre partiel

Suites, sommations et récurrence

6.1 Suites et notations de sommation · 6.2 Sommes télescopiques · 6.3 Sommes usuelles et séries géométriques · 6.4 Principe de récurrence (simple et forte)

Représentation des nombres et bases du dénombrement

7.1 Représentation en base b (binaire, hexadécimale) · 7.2 Arithmétique modulaire · 7.3 Règle de la somme et règle du produit · 7.4 Principe d'inclusion-exclusion

Algorithmes : recherche, tri, optimisation

8.1 Notion d'algorithme et pseudo-code · 8.2 Recherche linéaire et recherche binaire · 8.3 Tri par sélection et tri à bulles · 8.4 Algorithmes gloutons et preuve de correction

Croissance des fonctions et complexité

9.1 Notation grand-O · 9.2 Notations Ω et Θ · 9.3 Hiérarchie des croissances usuelles · 9.4 Complexité temporelle des algorithmes classiques

S10

Définitions et algorithmes récursifs

10.1 Définitions récursives de suites et d'ensembles · 10.2 Algorithmes récursifs · 10.3 Preuve de correction par récurrence structurelle · 10.4 Récursif vs itératif

S11

Dénombrement

11.1 Permutations et arrangements · 11.2 Combinaisons et coefficients binomiaux · 11.3 Principe des tiroirs (pigeonhole) · 11.4 Permutations avec répétitions

S12

Dénombrement avancé et fonctions génératrices

12.1 Relations de récurrence linéaires · 12.2 Résolution par équation caractéristique · 12.3 Séries formelles et fonctions génératrices · 12.4 Application au dénombrement

S13

Dénombrabilité

13.1 Cardinalité et équipotence · 13.2 Ensembles dénombrables · 13.3 Argument diagonal de Cantor · 13.4 Hôtel de Hilbert et paradoxes de l'infini

S14

Probabilités discrètes

14.1 Espace probabilisé et probabilité conditionnelle · 14.2 Indépendance et théorème de Bayes · 14.3 Variables aléatoires et loi (PMF) · 14.4 Espérance, linéarité et variance

Fiche de révision : semaine 1

L’essentiel

Une **proposition** est un énoncé qui est soit vrai (V) soit faux (F), jamais les deux.
Connecteurs : négation $\neg p$, conjonction $p \wedge q$, disjonction $p \vee q$, implication $p \to q$, équivalence $p \leftrightarrow q$.
L'implication $p \to q$ est **fausse dans un seul cas** : $p$ vrai et $q$ faux. En particulier, une implication à prémisse fausse est toujours vraie.
$p \to q$ se lit « si $p$ alors $q$ », mais aussi « $p$ seulement si $q$ » et « $q$ si $p$ » — attention au sens.
Traduction du français : « ne peut pas $B$ si $A$ » se code $A \to \neg B$, et deux conditions de ce type se combinent en $(A_1 \vee A_2) \to \neg B$.
Une **tautologie** est vraie pour toute affectation, une **contradiction** fausse pour toute affectation.

Formules

$p \to q \equiv \neg p \vee q$
Contraposée : $p \to q \equiv \neg q \to \neg p$
$p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)$
Table de $\to$ : seule la ligne (V, F) donne F

À savoir

Une table de vérité à $n$ variables comporte $2^n$ lignes.
La contraposée est équivalente à l'implication ; la réciproque ne l'est pas.
« A ou B » en logique est inclusif (le ou exclusif s'écrit $p \oplus q$).

Erreurs classiques

Confondre la réciproque $q \to p$ et la contraposée $\neg q \to \neg p$.
Coder « ne peut pas gagner si X » par $\neg B \to X$ au lieu de $X \to \neg B$.
Croire qu'une implication à prémisse fausse est fausse.
Traduire « ou » par un ou exclusif alors que le cours utilise le ou inclusif.

Quelques flashcards

Dans quel cas unique l'implication $p \to q$ est-elle fausse ?

Quand $p$ est vrai et $q$ est faux.

Réécrire $p \to q$ sans le connecteur $\to$.

$\neg p \vee q$.

Quelle est la contraposée de $p \to q$, et lui est-elle équivalente ?

$\neg q \to \neg p$ ; oui, elle est logiquement équivalente.

Que donne $\neg(p \vee q)$ par De Morgan ?

$\neg p \wedge \neg q$.

Comment lit-on la DNF sur une table de vérité ?

On prend les lignes VRAIES, une conjonction par ligne, le tout en disjonction.

Quelle est la négation de $\forall x\, P(x)$ ?

$\exists x\, \neg P(x)$.

Coche le cours et la série de Advanced information, computation, communication I chaque semaine, révise avec les fiches et les flashcards, et entraîne-toi sur les questions d’examen corrigées. Les deux premières semaines sont gratuites.

Créer un compte gratuit