Cours du 08 au 12 septembre

1 files changed, 138 insertions, 0 deletions

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
+```