Cours du 08 au 12 septembre

5 files changed, 587 insertions, 0 deletions

diff --git a/semestre 3/.gitignore b/semestre 3/.gitignore
new file mode 100644
index 0000000..0ff8d5e
--- /dev/null
+++ b/semestre 3/.gitignore
@@ -0,0 +1 @@
+edt*
diff --git a/semestre 3/architecture des ordinateurs/0- Info de rentrée.md b/semestre 3/architecture des ordinateurs/0- Info de rentrée.md
new file mode 100644
index 0000000..d527f00
--- /dev/null
+++ b/semestre 3/architecture des ordinateurs/0- Info de rentrée.md
@@ -0,0 +1,28 @@
+---
+tags:
+  - informatique
+  - sorbonne
+  - architecture-des-ordinateurs
+Semestre: 3
+---
+Cherche à expliquer
+|> comment on représente un programme en machine
+|> comment il s'exécute
+|> comment on construit des composants
+
+Cherche à démystifier l'ordinateur
+
+Le cours est entre l'électronique et l'informatique
+
+Partiel la semaine du 03/11 -> jusqu'au cours 6
+TME Solo le 03/11 -> jusqu'au cours 6
+50% examen, 30% partiel, 20% TME -> règle du max
+
+Il est attendu d'avoir fini tous les TME
+
+Il y a un memento
+
+Plan du cours :
+1. Représentation de l'information (nombres, caractères, codage)
+2. Programmation assembleur MIPS, implantation et exécution de programmes
+3. Logique combinatoire et séquentielle, exécution d'un programme sur un chemin de données
\ No newline at end of file
diff --git a/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md b/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md
new file mode 100644
index 0000000..9545578
--- /dev/null
+++ b/semestre 3/architecture des ordinateurs/1- Représentation de l'information.md
@@ -0,0 +1,293 @@
+---
+tags:
+  - sorbonne
+  - informatique
+  - architecture-des-ordinateurs
+semestre: 3
+---
+Architecture générale d'un ordinateur sur Moodle
+|> on s'intéresse au CPU, chipset et à la mémoire principale
+|> les choses sont liées grâce à des bus (un bus est un fil électrique)
+
+```mermaid
+flowchart LR
+	A["CPU"]-- Bus ---B["Mémoire centrale"]
+	B -- Bus --- C["Périphériques"]
+```
+
+CPU est celui qui traite l'information -> exécute les programmes
+Mémoire centrale est la RAM -> stocke les informations nécessaires à l'exécution du programme
+Bus -> support physique permettant les transferts d'information entre les différentes unités
+Périphériques -> les unités connexes
+
+Programme possède deux informations différentes :
+1. les données
+2. le traitement à effectuer (suite d'opérations sur les données)
+
+Les données sont représentées en binaire -> stocké dans la RAM
+Traitement à réaliser est traduit en une suite d'instructions compréhensibles par le processeur cible -> est le langage machine
+
+Schéma détaillant le stockage sur moodle
+
+Dans la mémoire, le code et les données sont bien séparés
+
+Processeur contient l'ALU (ce qui permet de faire des calculs arithmétiques et logiques) et les registres
+|> les registres permettent de stocker les données d'une manière très temporaire (contiennent max 32 ou 64 bits)
+|> l'ALU effectue des opérations sur les données dans le registre
+|> l'unité de commande dans le CPU définit ce qu'il doit faire à chaque instant
+
+L'unité de commande contient deux registres principaux -> Program Counter (PC) et Instruction Register (IR)
+|> PC contient l'adresse du programme exécuté
+|> IR contient les instructions à exécuté
+-> le CPU exécute sans la fin :
+1. lecture de l'adresse du code dans PC
+2. le place dans IR
+3. la lecture des instructions mise dans IR
+4. décode l'instruction
+5. exécute l'instruction
+6. mise à jour de l'instruction suivante (update dans PC)
+
+Ceci est une architecture de Von Neumann
+
+Les composants manipules surtout des tensions électriques
+|> deux valeurs possibles pour la tension
+|> 0V et 1.5V sont les deux valeurs utilisées (0V = 0 et 1.5V = 1)
+
+Représentation binaire :
+|> mot binaire = mot formé sur $\{0;1\}$
+|> bit = $0\lor1$
+|> octet = mot binaire composé de 8 bits
+|> quartet = mot binaire composé de 4 bits
+
+CPU 32 bits gèrent tout le temps 32 bits
+CPU 64 bits gèrent tout le temps 64 bits
+-> tout est décrit par ça
+
+Soit $M$ un mot binaire de $n$ bits, $M$ est décrit par la suite de bits $(m_{i})_{0\leqslant i\leqslant n-1}$
+|> plus $i$ est grand, plus le poids de ce bit est fort
+
+> [!NOTE] Nom des bits
+>$i = 0$ bit de poids faible
+>$i = n-1$ bit de poids fort
+
+Le bit représente l'information brute mais son interprétation dépend du reste !
+|> permet quand même de tout représenter (enfin, tant que l'ensemble de départ est en bijection avec $\mathbb{N}$)
+## Logique booléenne
+Logique booléenne -> formalisation des raisonnements basés sur des éléments qui peuvent être soit vrais, soit faux
+|> l'alphabet $\beta$ est $\{\text{VRAI},\text{FAUX}\} = \{\text V,\text F\} = \{0;1\}$
+|> ordre des éléments de $\beta = 0 < 1$
+|> variable booléenne est dans $\beta$
+|> fonction booléenne va de $\beta^n$ vers $\beta$
+
+Fonctions essentielles :
+|> complément (ou NON, ou NOT) -> $a = 0\implies\bar a = 1$ et $a = 1 \implies \bar a = 0$
+|> addition (ou OU, ou OR) -> $a+b=\max(a,b)$
+|> multiplication (ou ET, ou AND) -> $a\cdot b = \min(a,b)$
+
+| a   | b   | $\bar a$ | $a+b$ | $a\cdot b$ |
+| --- | --- | -------- | ----- | ---------- |
+| 0   | 0   | 1        | 0     | 0          |
+| 1   | 0   | 0        | 1     | 0          |
+| 0   | 1   | 0        | 1     | 0          |
+| 1   | 1   | 0        | 1     | 1          |
+Toute fonction booléenne peut être décrite par une composition des fonctions élémentaires ET, OU, NON car $<\beta, 0, 1,+,\cdot,\bar{}>$ forme une algèbre (voir séance 8 et suivantes)
+
+> [!NOTE] Définition des fonctions sur $n$ bits
+> On note $(a_i)_{i\in[0,n-1]}$ l'ensemble des bits de $A$. Notation analogue pour $B$ et $C$.
+> 
+> **NOT** -> $C = \bar A$ tel que $\forall i\in[0,n-1], c_i=\bar a_i$.
+> **OR** -> $C = A+B$ tel que $\forall i\in[0,n-1], c_i = a_i+b_i = \max(a_i,b_i)$
+> **AND** -> $C = A\cdot B$ tel que $\forall i\in[0,n-1], c_i = a_i\cdot b_i = \in(a_i,b_i)$
+> 
+> D'une manière générale, le résultat d'une opération sur un mot $M$ est le résultat des opérations sur les bits de $M$
+> -> est vrai pour toutes les fonctions booléennes (i.e. pour tout $f:\beta^n\to\beta$)
+### Décalage logique
+Soit $A$ un mot binaire de $n$ bits avec la famille $(a_i)_{i\in[0,n-1]}$ qui forme les bits de $A$.
+Si $p > n-1$, on a que $[p,n-1] = \varnothing$ par abus de langage
+
+$B = A << p$ tel que 
+|> $\forall i\in[0,p-1], b_i = 0$
+|> $\forall i\in[p,n-1], b_i = a_{i-p}$
+
+$B = A >> p$ tel que
+|> $\forall i\in[0,p-1], b_i = a_{i+p}$
+|> $\forall i\in[p,n-1], b_i = 0$
+
+> [!tip] Garder uniquement certains bits de $A$
+> On crée un mask $m$ qui sélectionne les bits, puis on fait $A + m$ et on décale
+> 
+> Si $A = 0101$ et qu'on souhaite avoir $10$, on fait $m = 0110$
+> |> $A+m = 0100$
+> Puis on décale de 1 pour supprimer la valeur inutile
+> |> $A >> 1 = 0010$
+
+> [!warning] Comment faire un bon mask ?
+> Toujours ne mettre que des 1 là où on veut garder des valeurs, sinon on risque de perdre des infos !
+> 
+> Exemple :
+> - $0101 + 0100 = 0100$ marche
+> - $0111 + 0100 = 0100$ ne marche pas
+> - $0011 + 0100 = 0000$ ne marche pas
+> 
+> C'est vraiment pas ouf !
+## Codage
+Le codage est la correspondance entre le représentation externe de l'information et sa représentation
+|> c'est comment on souhaite utiliser l'information qui définit quel codage on utilise !
+-> est ce qui définit les grandes classes de processeur (Intel, ARM, RISC...)
+
+Tout entier naturel $N$ peut être exprimé comme une somme de multiples de puissance de la base $B$
+|> $N = \sum_{i}a_iB^i$ avec $\forall i, a_i < B$  -> permet de convertir une notation dans la base $B$ vers $N$
+|> notation condensée est $a_{n-1}\ldots a_0$
+
+Mais comment sait-on dans quelle base sommes-nous ?
+|> on rajoute un indice après
+|> pour le binaire (base 2) -> $111_b$
+|> pour le décimal (base 10) -> $111_d$
+|> pour l'hexadécimal (base 16) -> $111_h$
+
+On peut aussi utiliser la notation avec un préfixe pour les mots binaires
+|> `0b1110` pour le binaire
+|> `0x111b` pour l'hexadécimal
+-> on garde tout, y compris si ce n'est pas pertinent de le garder, notamment pour les 0 inutiles !
+
+Exemple -> `0b0111` $= 111_b = (0\times2^3 + 1\times 2^2+1\times 2^1+1\times2^0)_b = 7$
+
+L'hexadécimal (de 0 à F) permet de compacter le binaire
+|> un mot de 4 bits binaire donnent un mot hexadécimal d'une seule lettre !
+-> l'hexadécimal est quatre fois plus cours que la notation en binaire
+
+> [!warning] Binaire et hexadécimal
+> On a donc que $1001_b\neq1001_h$ !
+
+> [!danger] Interprétation
+> Le codage ne permet toujours pas d'interpréter les données brutes !
+## Entiers
+### Entiers naturels
+Comme les mots sont de taille bornée, il n'est pas possible de tout représenter
+
+Sur $p$ symboles en base $B$, on peut représenter tous les entiers dans $[0,B^p-1]$
+
+Pour transformer un nombre de $n$ bits vers un mot de $N$ bits (où $n<N$), on rajoute $N-n$ 0 devant les bits :
+- $1011$ devient $00001011$ en 8 bits
+
+Preuve est trivial (car pour tout $i\in[n,N]$, on a $a_i = 0$)
+
+> [!danger] Extension pour les floatants et les autres
+> ÇA NE MARCHE PAS DE LA MÊME MANIÈRE
+
+Pour passer de la base $B_1$ vers $B_2$, on a besoin d'algorithmes de conversion
+|> division successive et tableau de correspondance
+
+```python title="Division successive"
+def div(N:int,B:int):
+	"""
+	N est le nombre
+	B est la base
+	"""
+	i = 0
+	Q = 1
+	a = []
+	while Q > 0:
+		Q = N/B
+		R = N % B
+		a.append(R) # si le tableau fait déjà la bonne taille, on fait a[i] = R
+		N = Q
+		i = i + 1
+	return "".join(a.reverse())
+```
+
+```elixir title="Division successive"
+def algo(n, b) do
+  q = div(n, b)
+  r = rem(n, b)
+  algorec(q, b, q, [r])
+end
+
+defp algorec(n, b, q, a) when q > 0 do
+  q = div(n, b)
+  r = Integer.mod(n, b)
+  algorec(q, b, q,[r | a])
+end
+
+defp algorec(_n, _b, 0, a) do
+  a
+end
+
+@doc """
+Print the result of the algo
+"""
+def print(a) do
+  Enum.map(a, &(Integer.to_string(&1)))
+  |> Enum.join("")
+end
+```
+
+Voir moodle pour l'algo complet
+
+Pour passer du binaire à l'héxa, on gère packet de 4 par packet de 4
+
+```python title="bin2hex"
+def bin_to_hex(b):
+	dec = len(b) % 4
+	hex = []
+	s = "01234567789ABCDEF"
+	if dec != 0:
+		v = div(b[:dec], 16)
+		hex.append(s[v])
+	for i in range(dec, len(b), 4):
+		v = div(b[i:i+4], 16)
+		hex.append(s[v])
+	return hex
+```
+
+```elixir
+def bin_to_hex(b) do
+	bin_to_hex_rec(b, [])
+end
+
+defp bin_to_hex_rec(before, after) when before != "" do
+	{b, a} = String.split_at(before, -4)
+	#TODO: convert algo
+	bin_to_hex_rec(b, [a | after])
+end
+
+defp bin_to_hex_rec("", after) do
+	after
+end
+```
+
+Pour réaliser une addition en binaire, on a besoin que les deux mots fassent la même taille
+
+Les additions / soustractions sont triviales
+
+Attention à l'overflow !
+|> arrive quand on dépasse la taille du bit
+|> est détectable à l'aide de la retenu -> revoir le moodle pour ça
+
+Les décalages servent à multiplier / diviser (voir le diapo)
+### Entiers relatifs
+On les appelle les nombre entiers signés
+
+La représentation classique en signe/module (i.e. un bit pour le signe, le reste pour le module)
+|> c'est compliqué car deux zéros, beaucoup de comparaisons...
+-> on utilise une autre représentation
+
+On utilise un système similaire légèrement plus complexe :
+$$ n = -k_{p-1}2^{p-1} + \sum^{p-2}_{i=0} k_i2^i $$
+où $(k_i)$ sont les bits représentés
+|> si le bit de poids fort est présent (est appelé le bit de signe), alors le tout est forcément négatif
+-> s'appelle représentation des entiers relatifs en complément à deux
+|> avec $n$ bits on peut donc représenter $[2^{n-1},2^{n-1}-1]$
+
+Pour prendre l'opposer, on prend son complémentaire et on lui ajoute 1
+|> est appelé le complément à deux
+|> le complémentaire de `0b1001` est `0b0110`
+
+**Preuve :**
+$$ N = a_{n-1}\ldots a_0 $$
+$$\bar N = \bar a_{n-1}\ldots \bar a_0$$
+$$ = \mathrm{0b}1\ldots1 = -1 $$
+Donc, on a que $\bar N$ doit être décalé de 1, d'où le plus 1
+|> cela est dû au fait que l'intervalle ne soit pas symétrique
+
+Voir le moodle pour la suite
\ No newline at end of file
diff --git a/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
new file mode 100644
index 0000000..8baee50
--- /dev/null
+++ b/semestre 3/mathématiques discrètes/1- Ensembles, relations, fonctions.md
@@ -0,0 +1,127 @@
+---
+tags:
+  - sorbonne
+  - informatique
+  - maths
+semestre: 3
+---
+Partiel en novembre
+
+On passe au TME après un certain temps
+
+QCM obligatoire
+|> commence le jour du cours et se finit le lundi en 8
+|> peut le faire plusieurs fois -> c'est la dernière qui compte
+|> il y en a 4
+
+Note : 50% examen + 25% partiel + 10% projet + 10% interro TD  + 5% QCM
+|> règle du max
+## Ensembles
+**Définition**
+Ensemble est une réunion dans une même entité de certains objets déterminés. Un ensemble ne possède pas d'ordre
+
+**Définition**
+Relation d'appartenance est noté $\in$. Elle indique si un élément $e$ appartient à un ensemble $E$.
+
+**Définition**
+$\varnothing$ est l'ensemble vide, celui qui ne contient rien
+$\{e\}$ est le singleton $e$ (i.e. l'ensemble contenant exclusivement $e$)
+
+**Définition**
+Le cardinal d'un ensemble est le nombre d'éléments appartenant à cet ensemble. On le note $|E|$ ou $\mathrm{card}(E)$.
+
+Par exemple, on a :
+$$|\{e\}| = 1$$
+> [!warning] Ensemble dans un ensemble
+> $2\not\in\{\{2\}\}$
+
+**Proposition**
+Tout ensemble contient l'ensemble vide.
+
+**Définition**
+La relation $A\subseteq B$ indique si $A$ est un sous-ensemble de $B$, i.e.
+$$ \forall a\in A,\quad a\in B $$
+**Proposition**
+Cette relation est réflexive, i.e. $E\subseteq E$ est vraie
+
+**Proposition**
+Cette relation est transitive, i.e. $E_1\subseteq E_2\land E_2\subseteq E_3\quad\implies\quad E_1\subseteq E_3$ est vraie
+
+**Définition**
+On dit que $A=B$ si, et seulement si :
+$$ A\subseteq B\quad\land\quad B\subseteq A $$
+
+**Proposition**
+Ainsi, on a que $\subseteq$ est anti-symétrique.
+
+**Définition**
+Une relation est d'ordre si elle est :
+- réflexive
+- transitive
+- anti-symétrique
+
+Elle est dite partielle si elle ne fonctionne par pour tous les éléments.
+
+**Proposition**
+Comme $\subseteq$ est réflexive, transitive et anti-symétrique, alors $\subseteq$ est une relation d'ordre.
+Par contre, deux ensembles ne sont pas nécessairement comparables avec $\subseteq$ : il s'agit donc d'une relation d'ordre partielle.
+
+**Définition**
+$A\cup B$ est l'union de $A$ et $B$, deux sous-ensembles de $E$, tel que :
+$$ A\cup B = \{x| x\in A\lor x\in B\} $$
+$A\cap B$ est l'intersection tel que :
+$$ A\cap B = \{x| x\in A\land x\in B\} $$
+> [!info] Construction d'ensembles
+> La construction des ensembles dans la dernière définition est dite par compréhension, comme en Python.
+
+**Définition**
+$A$ et $B$ sont disjoints si, et seulement si :
+$$ A\cap B = \varnothing $$
+
+**Théorème** - Formule du crible, formule de Poincaré
+Soient $A$ et $B$ deux sous-ensemble de $E$. On a :
+$$ |A\cup B| = |A|+|B|+|A\cap B| $$
+
+**Définition**
+La différence $A\backslash B$ , deux sous-ensembles de $E$, est :
+$$ A\backslash B = \{x|x\in A\land x\notin B\} $$
+
+**Définition**
+Le complémentaire de $A$, un sous-ensemble de $E$, est noté $\bar A$ et est défini tel que :
+$$ \bar A= E\backslash A $$
+
+**Définition**
+Le produit cartésien $A\times B$ est l'ensemble des couples $(a,b)$ avec $a\in A$ et $b\in B$. Donc :
+$$ A\times B = \{(a,b)|a\in A,b\in B\} $$
+
+**Proposition**
+Si $E_1,\ldots,E_n$ sont des ensembles finis, alors $$\left|\prod^n_{i=1} E_i\right| = \prod^n_{i=1}|E_i|$$
+Voir le diapo pour les propriétés classiques
+
+**Définition**
+Une partie $A$ d'un ensemble $E$ est un sous-ensemble de $E$.
+
+$\mathcal{P}(E)$ est l'ensemble des parties de $E$.
+
+> [!warning] $\mathcal{P}(E)$ ne peut jamais être vide !
+> En effet, on a $\mathcal{P}(\varnothing) = \{\varnothing\} \neq \varnothing$ !
+> Ne pas oublier que $\mathcal{P}(E)$ est un ensemble d'ensemble et que $\varnothing$ est bien un ensemble valide !
+
+**Construction de $\mathcal{P}(E)$**
+Si $E=\varnothing$, alors $\mathcal{P}(E) = \{\varnothing\}$
+Sinon, $E=\{e\}\cup F\neq\varnothing$ ($e$ est un élément de $E$ et $F$ est ce qui reste, il peut être vide !)
+Proposition : $$\mathcal{P}(\{e\}\cup F) = \mathcal{P}(F)\cup\{\{e\}\cup A|A\in\mathcal{P}(F)\}$$Ceci est un appel récursif de la fonction $\mathcal{P}$ permettant ainsi de construire l'ensemble des parties.
+
+**Corollaire**
+Si $E$ est un ensemble fini contenant $n$ éléments, alors $|\mathcal{P}(E)|=2^n$
+
+**Définition**
+Soit $E$ un ensemble.
+Quand on partitionne $E$, on construit des parties deux à deux disjointes.
+
+Une partition de $E$ est une famille $(A_i)_{i\in I}$ de parties de $E$ telle que :
+- $A_i\neq\varnothing$
+- $A_i\cap A_j = \varnothing$ si $i\neq j$ (pour tout $(i,j)$ dans $I$)
+- $E=\bigcup_{i\in I} A_i$
+
+> [!warning] Une partition de $E$ n'est pas unique dans le cas générale !
diff --git a/semestre 3/structures des données/1- Notions élémentaires.md b/semestre 3/structures des données/1- Notions élémentaires.md
new file mode 100644
index 0000000..06005d8
--- /dev/null
+++ b/semestre 3/structures des données/1- Notions élémentaires.md
@@ -0,0 +1,138 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 3
+---
+Comment gérer les structures de données ?
+-> objectif est d'optimiser
+|> références bibliographiques sur Moodle
+
+Note : 50% examen, 30% TME Solo final, 10% TME Solo, 10% note TD
+|> règle du max particulière : $\max(0.5\mathrm{examen}+0.1\mathrm{TD}+0.1\mathrm{TP},0.7\mathrm{examen})$
+-> TME Solo final est gardé en seconde session
+
+Une feuille A4 manuscrite est autorisée en examen
+## Abstraction
+Une structure de données est une implémentation concrète d'un type abstrait de données
+
+Abstraction = considérer l'un caractère d'une chose indépendamment des autres
+|> abstraction par simplification -> réduction la description d'un objet
+|> abstraction par généralisation -> partir du particulier pour arriver au cas général
+
+Abstraction en informatique = synthétiser les caractéristiques communes applicables à des entités ou concepts variés, afin de simplifier et unifier leur manipulation
+
+> [!note] Abstraction est une bonne chose
+> Mais il ne doit pas rendre le programme plus lent !
+
+Un type abstrait de données est une spécification mathématique d'un ensemble d'objets et d'un ensemble d'opérations applicables à ces objets
+
+Le type abstrait ne définit pas l'implémentation des méthodes ou la manière dont les données sont stockées
+-> permet de rendre le code plus abstrait pour mieux le comprendre
+
+Une structure de données représente concrètement les données dans la mémoire
+|> elle implémente les opérations sur cette représentation
+
+Le choix de la structure de données implique un coup
+|> coup spatiale (mémoire que ça prend)
+|> coup temporel (temps que ça prend)
+-> toutes les structures de données n'ont pas les mêmes performances
+
+Un programme est un ensemble :
+- de variables
+- d'opérations élémentaires
+- de structures de contrôle
+
+Variable = une boite contenant des données
+Opération élémentaires = opération réalisant quelque chose de simple (ordinateur les faits en un nombre fini d'appels au CPU)
+Structure de contrôle = instruction décrivant comment le programme s'exécute
+
+Un algorithme est un programme résolvant un problème
+|> problème = valeurs + question
+-> doit avoir un nombre fini d'opérations élémentaires (terminaison)
+-> doit répondre correctement à la question (vérification)
+## Complexité
+On estime la complexité temporelle en comptant le nombre d'opérations élémentaires faites
+|> selon les entrées, il peut y avoir une complexité temporelle -> on regarde donc le pire des cas et le meilleur des cas
+
+**Notation de Landau : $O$**
+Soient $f(n)$ et $g(n)$ deux fonctions positives définies sur $\mathbb{N}$.
+On dit que $f(n)$ est en $O(g(n))$ si la fonction $f$ est asymptotiquement bornée supérieurement par la fonction $g$ à un facteur près. Plus formellement, $f(n)$ est en $O(g(n))$ si :
+$$ \exists n_0\in\mathbb{N},\quad\exists k\in\mathbb{R}>0,\quad\forall n \geqslant n_0,\quad f(n)\leqslant kg(n) $$
+
+> [!NOTE] Simplification de la notation
+> Quand on a $O(2n+4)$, on peut noter $O(n)$ car :
+> - $2n+4\leqslant kn$ pour tout $n$ et pour tout $k > 4$
+> 
+> Cette simplification est valide pour tous les cas similaires
+
+**Notation de Landau : $\Omega$**
+Soient $f(n)$ et $g(n)$ deux fonctions positives définies sur $\mathbb{N}$.
+On dit que $f(n)$ est en $\Omega(g(n))$ si la fonction $f$ est asymptotiquement bornée inférieurement par la fonction $g$ à un facteur près. Plus formellement, $f(n)$ est en $\Omega(g(n))$ si :
+$$ \exists n_0\in\mathbb{N},\quad\exists k\in\mathbb{R}>0,\quad\forall n \geqslant n_0,\quad f(n)\geqslant kg(n) $$
+
+> [!NOTE] Simplification de la notation
+> Même principe !
+
+**Notation de Landau : $\Theta$**
+Soient $f(n)$ et $g(n)$ deux fonctions positives définies sur $\mathbb{N}$.
+On dit que $f(n)$ est en $\Theta(g(n))$ si la fonction $f$ est dominée et soumise par la fonction $g$ asymptotiquement. Plus formellement, $f(n)$ est en $\Theta(g(n))$ si :
+$$ \exists n_0\in\mathbb{N},\quad\exists (k_2,k_1)\in\mathbb{R}^2,\quad k_2\geqslant k_1>0\quad\implies\quad\forall n \geqslant n_0,\quad k_1g(n)\leqslant f(n)\leqslant k_2g(n) $$
+
+La complexité spatiale est la place que prend un programme en mémoire
+|> est l'analogue de la complexité temporelle pour la RAM
+## Compilation et module en C
+Programmation modulaire est le fait de séparer son code en plusieurs programmes
+-> demande une réflexion sur le découpage du code
+
+Un module en C est composé :
+- du header `.h` qui donne les interfaces du module
+- du fichier source `.c` qui contient le code source décrit dans le fichier header
+
+Besoin de rajouter `#include "file.h"` en début pour implémenter le header
+
+Quand on écrit un fichier header, on rajoute toujours :
+```c
+#ifndef FILE_H
+#define FILE_H
+
+// contenu du fichier
+
+#endif
+```
+Ça permet d'éviter d'avoir des erreurs lors de la compilation
+|> éviter d'inclure plusieurs fois le même chode
+
+On peut compiler les fichiers seuls avec :
+```bash
+gcc -c file1.c # crée le fichier1.o
+gcc -c file2.c # crée le fichier2.o
+gcc -c main.c # crée le main.o
+```
+Et on peut créer l'exécutable `main` avec :
+```bash
+gcc -o main -c main.o fil2.o file1.o
+```
+Ceci permet de compiler le programme en plusieurs fois -> permet de gagner du temps si le projet est long à compiler
+
+Le `Makefile` permet d'automatiser tout ça
+|> il exécute uniquement ce qui est nécessaire
+|> évaluation récursive des règles (voir le diapo pour plus d'infos)
+```Makefile
+build : main // peut utile car on n'a qu'un seul exécutable
+
+main : main.o file2.o file1.o
+	gcc -o main -c main.o file2.o file1.o
+
+main.o:
+	gcc -c main.c
+
+file2.o:
+	gcc -c file2.c
+
+file.o:
+	gcc -c file1.c
+
+clean:
+	rm -f *.o main
+```