From 11d5e7431489b8b40cf479a7f88c171d6fbf77a7 Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Sat, 13 Sep 2025 00:16:52 +0200 Subject: Cours du 08 au 12 septembre --- semestre 3/.gitignore | 1 + .../0- Info de rentr\303\251e.md" | 28 ++ .../1- Repr\303\251sentation de l'information.md" | 293 +++++++++++++++++++++ .../1- Ensembles, relations, fonctions.md" | 127 +++++++++ .../1- Notions \303\251l\303\251mentaires.md" | 138 ++++++++++ 5 files changed, 587 insertions(+) create mode 100644 semestre 3/.gitignore create mode 100644 "semestre 3/architecture des ordinateurs/0- Info de rentr\303\251e.md" create mode 100644 "semestre 3/architecture des ordinateurs/1- Repr\303\251sentation de l'information.md" create mode 100644 "semestre 3/math\303\251matiques discr\303\250tes/1- Ensembles, relations, fonctions.md" create mode 100644 "semestre 3/structures des donn\303\251es/1- Notions \303\251l\303\251mentaires.md" 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\303\251e.md" "b/semestre 3/architecture des ordinateurs/0- Info de rentr\303\251e.md" new file mode 100644 index 0000000..d527f00 --- /dev/null +++ "b/semestre 3/architecture des ordinateurs/0- Info de rentr\303\251e.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\303\251sentation de l'information.md" "b/semestre 3/architecture des ordinateurs/1- Repr\303\251sentation de l'information.md" new file mode 100644 index 0000000..9545578 --- /dev/null +++ "b/semestre 3/architecture des ordinateurs/1- Repr\303\251sentation 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 [!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\303\251matiques discr\303\250tes/1- Ensembles, relations, fonctions.md" "b/semestre 3/math\303\251matiques discr\303\250tes/1- Ensembles, relations, fonctions.md" new file mode 100644 index 0000000..8baee50 --- /dev/null +++ "b/semestre 3/math\303\251matiques discr\303\250tes/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\303\251es/1- Notions \303\251l\303\251mentaires.md" "b/semestre 3/structures des donn\303\251es/1- Notions \303\251l\303\251mentaires.md" new file mode 100644 index 0000000..06005d8 --- /dev/null +++ "b/semestre 3/structures des donn\303\251es/1- Notions \303\251l\303\251mentaires.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 +``` -- cgit v1.2.3