Aller au contenu principal
- Propositions, connecteurs ¬ ∧ ∨ → ↔, précédence ; tables de vérité
- Tautologie, contradiction, contingence ; implication et cas vides
- Équivalences : De Morgan, contraposée, p → q ≡ ¬p ∨ q
- Quantificateurs ∀ / ∃, leur ordre, leurs négations
- Schémas de preuve : récurrence (initialisation, hérédité), contraposition, absurde
- Opérations ∪ ∩ − complémentaire, produit cartésien, différence symétrique
- Cardinaux : |A ∪ B| = |A| + |B| − |A ∩ B|, |A × B| = |A| · |B|, |P(A)| = 2^|A|
- Fonctions : injection, surjection, bijection ; composition et réciproque
- Principe des tiroirs et ses conséquences (dont deux sommets de même degré)
- Équivalences : classes, partition, ensemble quotient A/R
- Ordres : partiels vs totaux, Hasse, éléments maximaux vs plus grand élément
- Vocabulaire : degrés, chemins, cycles, connexité ; lemme des poignées de mains et parité
- Représentations : liste d'adjacence O(n+m) contre matrice O(n²)
- BFS par couches (plus courts chemins non pondérés), DFS (cycles, composantes)
- Poids positifs : Dijkstra, invariant et contre-exemple si poids négatif
- MST : propriété de coupe, Kruskal (union-find), Prim (tas)
- Kahn : ordre topologique si et seulement si DAG
- Comptage de marches de longueur k par la puissance A^k
- Congruences : définition par n | (a − b), compatibilité avec +, ×, puissances
- Euclide, Bézout, inverse modulaire, indicatrice d'Euler
- Petit théorème de Fermat, théorème des restes chinois
- Applications : sommes de contrôle, empreintes, cryptographie
- Invariants de parcours et de boucle comme outils de preuve
- Dénombrement direct vs bijection ; principes d'addition et de multiplication
- Ordre de grandeur combinatoire : pigeonnier ⌈n/k⌉, explosion 2^n