Numération — conversions entre bases›
Décimal → Binaire
Divisions successives par 2, lire les restes de bas en haut.
25 ÷ 2 = 12 r1 / 12 ÷ 2 = 6 r0 / 6 ÷ 2 = 3 r0 / 3 ÷ 2 = 1 r1 / 1 ÷ 2 = 0 r1
→ 25₁₀ = 11001₂
Binaire → Décimal
Multiplier chaque bit par 2ⁿ (n=0 à droite, croît vers la gauche)
11001₂ = 1×2⁴ + 1×2³ + 0×2² + 0×2¹ + 1×2⁰ = 16+8+0+0+1 = 25₁₀
Hexadécimal (groupes de 4 bits)
0=0000 1=0001 2=0010 3=0011 4=0100 5=0101 6=0110 7=0111
8=1000 9=1001 A=1010 B=1011 C=1100 D=1101 E=1110 F=1111
Exemple : 10111100₂ = 1011|1100 = BC₁₆ = 188₁₀
Octal (groupes de 3 bits) — chiffres 0 à 7
Exemple : 110111₂ = 110|111 = 67₈
Puissances de 2 : 1·2·4·8·16·32·64·128·256·512·1024·2048·4096
Arithmétique modulaire›
Congruences
- a ≡ b (mod n) si n divise (a − b), c'est-à-dire a et b ont le même reste dans la division par n
17 ≡ 2 (mod 5) car 17 − 2 = 15 = 3×5
Propriétés : si a≡b et c≡d (mod n) → a+c ≡ b+d et a×c ≡ b×d
PGCD — algorithme d'Euclide
Diviser le grand par le petit, recommencer avec le reste, jusqu'à r=0.
PGCD(48, 18) :
48 = 2×18 + 12
18 = 1×12 + 6
12 = 2×6 + 0 → PGCD = 6
Nombres premiers
- Divisibles uniquement par 1 et eux-mêmes : 2, 3, 5, 7, 11, 13, 17, 19, 23…
- Crible d'Ératosthène : barrer les multiples de chaque premier jusqu'à √n
Application : cryptographie RSA
- Choisir 2 grands nombres premiers p et q → n = p × q
- Chiffrement : c ≡ m𝑒 (mod n) | Déchiffrement : m ≡ c𝑑 (mod n)
L'arithmétique modulaire est le fondement mathématique de la cryptographie RSA !
Suites numériques — arithmétiques & géométriques›
Suite arithmétique (raison r)
Terme général : uₙ = u₁ + (n−1) × r
Somme n termes : Sₙ = n × (u₁ + uₙ) / 2
Identifier : vérifier que uₙ₊₁ − uₙ = r = constante
Exemple : sal. u₁=1800€, r=50 → u₁₀ = 1800+9×50 = 2250€
Suite géométrique (raison q)
Terme général : uₙ = u₁ × q^(n−1)
Somme (q≠1) : Sₙ = u₁ × (1−qⁿ) / (1−q)
Identifier : vérifier que uₙ₊₁ / uₙ = q = constante
Comportement asymptotique (n → +∞)
- |q| < 1 → qⁿ → 0 (converge)
- q > 1 → qⁿ → +∞ (diverge)
- q = 1 : constante | q = −1 : oscille entre u₁ et −u₁
Exemple capital : 1000€ à 5%/an → uₙ = 1000 × 1,05^(n−1) (croissance exponentielle)
Calcul matriciel›
Opérations élémentaires
- Addition : même dimension obligatoire — terme à terme : (A+B)ᵢⱼ = aᵢⱼ + bᵢⱼ
- Multiplication A(m×n) × B(n×p) = C(m×p) — cᵢⱼ = ∑ᵘ aᵢᵘ × bᵘⱼ
⚠ Non commutative : AB ≠ BA en général !
Matrice identité et inverse
Identité I : diagonale=1, reste=0 → A×I = I×A = A
Inverse de A 2×2 : A=[[a,b],[c,d]]
A⁻¹ = 1/(ad−bc) × [[d, −b], [−c, a]] (condition : ad−bc ≠ 0)
Si A inversible : solution unique X = A⁻¹ × B
Résolution de système linéaire — pivot de Gauss
- Écrire sous forme A·X = B
- Opérations sur les lignes : échanger, multiplier, ajouter un multiple
- Objectif : matrice triangulaire supérieure, puis remontée
Exemple : x + 2y = 5 / 2x + y = 4
→ x = 5−2y dans 2ème éq.
→ 2(5−2y)+y = 4 → y = 2, x = 1
Logique — propositions, prédicats & ensembles›
Connecteurs logiques
| Connecteur | Notation | Vrai si… |
|---|---|---|
| Négation | ¬P | P est faux |
| ET (conjonction) | P ∧ Q | P et Q sont tous les deux vrais |
| OU (disjonction) | P ∨ Q | Au moins l'un est vrai |
| Implication | P ⇒ Q | Faux seulement si P vrai et Q faux |
| Équivalence | P ⇔ Q | P et Q ont la même valeur de vérité |
Tautologies : P ∨ ¬P = Vrai / P ∧ ¬P = Faux
De Morgan : ¬(P∧Q) = ¬P∨¬Q / ¬(P∨Q) = ¬P∧¬Q
Quantificateurs (prédicats)
- ∀x P(x) : "pour tout x, P(x) est vrai" | ∃x P(x) : "il existe un x tel que P(x)"
- Négation : ¬(∀x P(x)) = ∃x ¬P(x) | ¬(∃x P(x)) = ∀x ¬P(x)
Ensembles
- A ∪ B : union | A ∩ B : intersection | Â : complémentaire | A \ B : différence
- A × B : produit cartésien — toutes les paires (a,b) avec |A×B| = |A|×|B|
Relations sur un ensemble
- Réflexive + Symétrique + Transitive = relation d'équivalence
- Réflexive + Antisymétrique + Transitive = relation d'ordre
- Bijective = injective (f(a)=f(b)⇒a=b) + surjective (tout élément a un antécédent)
Algèbres de Boole & Karnaugh›
Opérateurs booléens
| Op. | Sym. | Règle |
|---|---|---|
| ET | ∧ | 1 seulement si toutes les entrées = 1 |
| OU | ∨ | 1 si au moins une entrée = 1 |
| NON | ¬ | Inverse l'entrée (¬0=1, ¬1=0) |
| XOR | ⊕ | 1 si les entrées sont différentes |
Priorité : ¬ > ∧ > ∨
Tautologie = toujours vraie / Contradiction = toujours fausse
Table de vérité : 2ⁿ lignes pour n variables
Propriétés fondamentales
a + 0 = a / a × 1 = a (neutres)
a + â = 1 / a × â = 0 (complémentation)
a + a = a / a × a = a (idempotence)
¬(A ∧ B) = ¬A ∨ ¬B / ¬(A ∨ B) = ¬A ∧ ¬B (De Morgan)
Table de Karnaugh (simplification de fonctions booléennes)
- Tableau à 2ⁿ cases pour simplifier une expression booléenne
- Regrouper les 1 par groupes de 2, 4 ou 8 (puissances de 2)
- Chaque groupe → éliminer les variables qui changent dans le groupe
- Application : simplification de circuits logiques et de conditions
Treillis
- Ensemble ordonné où toute paire a une borne sup (join ∨) et inf (meet ∧)
- Treillis distributif complémenté = algèbre de Boole
Graphes & Ordonnancement MPM›
Vocabulaire
- Sommet / Arête (non orienté) / Arc (orienté) | Degré : nb d'arêtes adjacentes
- Connexe : chemin entre toute paire de sommets
- Euler (arêtes 1×) : 0 ou 2 sommets de degré impair
- Hamilton (sommets 1×) : pas de condition simple
Algorithme de Dijkstra — plus court chemin
1. Init : source = 0, tous autres = ∞
2. Choisir le sommet non visité à distance minimale
3. Relaxer ses voisins : si d(u)+poids(u,v) < d(v) → maj d(v)
4. Marquer visité → répéter
→ Uniquement avec des poids positifs !
Méthode MPM — ordonnancement
Date au plus tôt D+(B) = max{ D+(A) + durée(A) } pour tous prédécesseurs A
Date au plus tard D−(A) = min{ D−(B) − durée(A) } pour tous successeurs B
Marge = D−(A) − D+(A)
Chemin critique = tâches avec marge = 0
⚠ Retarder une tâche critique = retarder tout le projet !
Diagramme de Gantt
- Tâches en lignes, temps en colonnes — chaque barre = durée de la tâche
- Placer une tâche dès que tous ses prédécesseurs sont terminés
- Date de fin = fin de la dernière barre = durée minimale du projet
En exam : toujours faire MPM en premier pour trouver le chemin critique, puis Gantt pour visualiser.