9 files changed, 577 insertions, 0 deletions

diff --git a/semestre 1/informatique/.gitignore b/semestre 1/informatique/.gitignore
new file mode 100644
index 0000000..ce7386d
--- /dev/null
+++ b/semestre 1/informatique/.gitignore
@@ -0,0 +1,3 @@
+1-\ Premier\ cours.md
+TME
+carteref.pdf
diff --git a/semestre 1/informatique/2- Instruction, variables, alternatives.md b/semestre 1/informatique/2- Instruction, variables, alternatives.md
new file mode 100644
index 0000000..853361c
--- /dev/null
+++ b/semestre 1/informatique/2- Instruction, variables, alternatives.md
@@ -0,0 +1,41 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 1
+---
+Une expression a un type et une valeur
+Une instruction s'interprète mais n'a pas de valeur
+
+Déclaration est :
+```python
+s : float
+```
+
+L'initialisation est :
+```python
+= "hello world"
+```
+
+Définition d'une variable est sa déclaration et son initialisation
+
+Occurrence est l'utilisation de la variable
+
+Réaffectation est une modification de sa valeur
+
+Inférence de type est une déduction automatique du type d'une variable
+
+> [!warning] Définitions de variable
+> Les définitions de variable sont toujours au début (sauf pour les variables d'occurration)
+
+La convention est la snake_case pour tout
+
+Alternative :
+```python
+if condition:
+	consequant1()
+elif condition2:
+	consequant2()
+else:
+	consequant3()
+```
diff --git a/semestre 1/informatique/3- Boucles.md b/semestre 1/informatique/3- Boucles.md
new file mode 100644
index 0000000..b0f553f
--- /dev/null
+++ b/semestre 1/informatique/3- Boucles.md
@@ -0,0 +1,119 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 1
+---
+On utilise `format(int) -> str` pour convertir un int en string
+
+```python
+def somme(n: int) -> int:
+	"""Precond: n >= 1
+	Retourne la somme des n premiers termes
+	"""
+	t: int = n
+	for i in range(1,n):
+		t += i
+	return t
+```
+## Simulation de boucle
+Durant l'examen, on peut nous demander de simuler une boucle
+Exemple de tableau :
+
+| tour de boucle | s   | i   |
+| -------------- | --- | --- |
+| entrée         | 0   | 1   |
+| 1              | 1   | 2   |
+| 2              | 3   | 3   |
+| 3              | 6   | 4   |
+| 4              | 10  | 5   |
+| 5 (sortie)     | 15  | 6   |
+($s$ et $i$ sont des variables)
+L'ordre des variables dépendent de leur ordre de modification dans la boucle 
+La valeur affichée est celle à la fin du tour du boucle
+
+Pour chaque imbrication de boucle, on rajoute une colonne dans le tableau
+## Correction
+La correction est la validité de la fonction, i.e.
+- correction de l'algorithme
+- correction de l'implémentation
+
+Pour vérifier la correction de l'implémentation, on a besoin de supposer que l'interpréteur est correct
+
+Un invariant est une expression booléenne impliquant les variables modifiées dans le corps de la boucle qui est vraie lors de l'entrée de boucle et après chaque tour de boucle
+|> particulièrement, il est vrai après la boucle
+
+Exemple pour une implémentation de la fonction $p(x,n)=x^n$
+
+| tour       | res | i   |
+| ---------- | --- | --- |
+| entrée     | 1   | 1   |
+| 1          | 2   | 2   |
+| 2          | 4   | 3   |
+| 3          | 8   | 4   |
+| 4          | 16  | 5   |
+| 5 (sortie) | 32  | 6   |
+On a que $res=x^{i-1}$ est invariant (il faudrait le montrer par récurrence)
+|> en L1, on détaille sur un exemple (avec en plus l'invariant) et on est bon
+
+Comment prouver qu'une fonction avec une boucle est correcte
+|> une simulation ne nous dit rien formellement
+|> besoin de trouver un invariant pour le démontrer formellement
+|> on utilise le fait que l'expression de $i$ est fausse à la fin
+|> on réinjecte dans l'invariant et on vérifie qu'elle est correcte
+
+Suite de l'exemple :
+>Comme $res=x^{i-1}$ est un invariant et que $i=n+1$ est la dernière valeur de $i$ après la boucle, on a que $res^{n+1-1}=res^n$, ce qui est vrai dans notre cas
+
+> [!important] Autre méthode
+> 1. On écrit notre $i$ et ce que l'on veut à la fin
+> 2. On se débrouille pour trouver un invariant avec ces deux valeurs
+
+Suite de l'exemple :
+Démonstration de l'invariant
+On a que l'invariant est vraie et pour le tour 0.
+On suppose que pour tout tour de boucle, on a que l'invariant est vrai.
+On pose :
+$$r'=rx$$
+$$ i'=i+1 $$
+On a donc que :
+$$ r' = xr=x\times x^{i-1} = x^i = x^{i'-1} $$
+Donc $r'$ est bon.
+(Voir le poly cours 4 pour une belle démo)
+## Terminaison
+Un variant de boucle est une expression arithmétique qui est un entier naturel positif, qui décroit strictement à chaque fois et qui vaut 0 en sortie de boucle
+|> permet de montrer que la boucle `while` se termine
+
+On le démontre de la même manière que l'invariant
+|> doit montrer qu'il s'agit d'un entier positif au début
+|> doit montrer que sa valeur décroit strictement entre le début et la fin d'un tour de boucle
+|> doit montrer qu'il vaut 0 quand la boucle est finie
+
+> [!info] Condition et variant
+> Le variant pourrait être utilisée comme condition dans le while
+
+Une boucle se termine si elle a un variant
+## Efficacité
+Un programme est correct vis-à-vis d'une fonction $F$ quand chaque calcul `f(x)` pour x satisfaisant les hypothèses, si le programme renvoie $v$, alors $F(x)=v$ (avec (x,v) représentation de $(x,v)$)
+|> est une propriété indécidable
+|> analyse statique est l'analyse du code
+|> analyse dynamique sont les tests et les simulations
+|> beaucoup de tests, de plus en plus de vérification
+
+On fait de l'analyse statique de boucle
+
+Un programme `f` est plus efficace en moyenne qu'un programme `g` :
+- `f` et `g` calculent la même fonction mathématique
+- sur toutes les entrées, `f` utilise en moyenne moins d'opération élémentaire que `g`
+
+> [!warning] Sanction sur l'efficacité
+> On doit limiter les répétitions de calcul
+> On ne compare pas des booléens, on évite les raccourcies logiques
+> On essaye de faire des algorithmes efficaces
+
+L'efficacité dépend du contexte
+|> espace mémoire en système intégré
+|> appels aux fonctions de lib graphique pour du jv
+etc
+
+Voir la slide de conclusion sur le diapo (cours 4)
\ No newline at end of file
diff --git a/semestre 1/informatique/4- Séquences & Chaînes.md b/semestre 1/informatique/4- Séquences & Chaînes.md
new file mode 100644
index 0000000..f32fe9c
--- /dev/null
+++ b/semestre 1/informatique/4- Séquences & Chaînes.md
@@ -0,0 +1,104 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 1
+---
+Commence la deuxième partie du cours : nouvelles données (nouveaux types)
+|> on va voir les String, les listes, les ensembles et les dictionnaires -> ce sont des séquences
+
+Actuellement, python est suffisamment expressif (Turing-complet)
+|> on peut faire des calculs numériques et logiques complexes
+|> notions correction, terminaison et efficacité
+## Structure de données
+On peut tout représenter par des entiers (codages de Gödel)
+|> existence de fonctions bijectives de $\mathbb{N}^m\to\mathbb{N}$
+|> tout est codé en bits
+
+Besoin d'une abstraction pour que ce soit plus simple
+-> ce sont les structures de données
+
+Une structure de données est une entité informatique qui regroupe et organise des données (ses éléments)
+|> interface est un ensemble de primitives qui permettent son utilisation (construction, destruction, utilisation)
+|> implémentation est le code implémentant l'interface
+## Séquence
+Sous-type d'une structure de données
+|> elles sont ordonnées, possèdent un nombre de données fini et des données de même type
+|> on peut itérer dessus pour tous les lire dans l'ordre
+On utilise une séquence pour répéter une action pour chacun de ses éléments dans l'ordre de la séquence
+|> la boucle s'arrête toujours
+
+Pour itérer sur une séquence, on écrit :
+```python
+v: type
+for v in seq:
+```
+
+`v` est la valeur successive dans la séquence `seq`
+
+> [!warning] On doit déclarer `v` avant la boucle !
+
+Pour récupérer une partie, on peut utiliser `var[m:n]`, attention `n` est exclu
+```python
+s: str = "01234567"
+print(s[2:5]) # "234"
+```
+
+Une réduction est la construction d'une information structurellement plus simple en parcourant la séquence
+
+On peut découper une séquence en utilisant `[i:j:n]`
+|> `i` est l'indice du début
+|> `j` est l'indice de fin *exclu*
+|> `n` est le pas entre chaque élément
+|> si `i` ou `j` ou `n` est négatif, prend les indices avec un ordre décroissant
+|> si `j<i`, alors donne `[]`
+|> si `j` est plus grand que la liste, alors donne toute la liste
+
+```python
+l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
+l[5:] # == [5, 6, 7, 8, 9]
+l[:5] # == [0, 1, 2, 3, 4]
+l[2:5] # == [2, 3, 4]
+l[::2] # == [0, 2, 4, 6, 8]
+l[1::2] # == [1, 3, 5, 7, 9]
+l[1:8:3] # == [1, 4, 7]
+```
+## Intervalle
+Séquence d'entiers consécutifs ordonnées par l'ordre standard
+i.e. $[|m,n|]$
+
+Pour créer un intervalle $[|m,n[|$, on fait :
+```python
+m: int
+n: int
+range(m, n)
+```
+
+> [!warning] $n$ est exclu !
+
+> [!info] On peut utiliser `range(n)`
+## Chaîne de caractères
+Type `str`
+Est une séquence
+
+On peut récupérer le caractère lié à un entier avec :
+```python
+chr(int) -> str
+```
+Et l'entier lié au caractère avec :
+```python
+ord(str) -> int
+```
+
+L'opérateur `*` est autorisé sur les string :
+```python
+s: str = "ab"
+s = s*3
+print(s) # "ababab"
+```
+
+L'opérateur `<` (resp. `>`) suit l'ordre lexicographique (resp. l'inverse de cet ordre) :
+- suit l'entier associé
+- `'Z' < 'a'` est vrai
+- `'a' < 'b'` est vrai
+- `'a' > '1'` est vrai
\ No newline at end of file
diff --git a/semestre 1/informatique/6- Listes & n-uplets & polymorphisme.md b/semestre 1/informatique/6- Listes & n-uplets & polymorphisme.md
new file mode 100644
index 0000000..84d0da1
--- /dev/null
+++ b/semestre 1/informatique/6- Listes & n-uplets & polymorphisme.md
@@ -0,0 +1,69 @@
+---
+tags:
+  - informatique
+  - sorbonne
+semestre: 1
+---
+## Liste
+Séquence d'un même type
+|> s'initialise avec `[]`
+|> type `List[T]` où `T` est un type valide (tous les éléments sont de type `T`)
+|> pas le droit d'avoir plusieurs types dans une même liste
+
+Principaux problèmes sur les listes :
+- réduction = transformer la liste vers un élément plus simple (`bool`, `int`, `str`)
+- filtrage = suppression de certains éléments de la liste en fonction d'un critère
+- transformation = modification de certains (ou tous les) éléments de la liste (⚠ doit faire la même taille)
+
+Le schéma de transformation `map` applique une même fonction à tous les éléments d'une liste
+
+Le schéma de filtrage `filter` applique un prédicat à tous les éléments et conservent ceux le validant
+
+L'opérateur `+` permet d'ajouter une liste à une autre
+|> est plus lourd que le `List[T].append(List[T])`
+
+> [!warning] Mutabilité des listes
+> Les listes sont mutables : si on les modifie, alors on modifie la variable mère !
+> 
+> Ici, on doit créer à chaque fois une nouvelle liste pour éviter de modifier la liste mère
+## Polymorphisme
+Une fonction peut prendre plusieurs types différents et renvoyer ce type à la fin (e.g., `f(int) -> int` et `f(str) -> str`)
+|> pour éviter de faire pleins de fonction, on définit une fonction globale qui prend un paramètre de type `T` et qui renvoie une valeur de type `T`
+## n-uplets
+Un $n$-uplets est la représentation d'une liste de taille fixée non homogène, par exemple : `HEURE, 13, 44`
+
+Un $n$-uplets est une séquence d'exactement $n$ éléments ordonnées, pouvant être de type différent
+|> s'initialise avec `(e_1, ..., e_n)`
+|> le type est `Tuple[T_1, ..., T_n]` où $\forall i\in [|1, n|]$, on a $e_i$ de type $T_i$
+
+Pour récupérer les variables d'un $n$-uplets, on fait appel à la déstructuration
+```python
+u: Tuple[T1, T2] = (value1, value2)
+e1, e2 = u
+```
+on n'a pas besoin de déclarer le type de `e1`, `e2`, etc.
+
+> [!warning] Accès directe et alternative
+> On n'a pas le droit d'utiliser l'opérateur `[]` sur les $n$-uplets.
+> Par contre, on a le droit d'utiliser la "variable poubelle" `_`, i.e. `e1, _, _, e4 = u`
+
+Les $n$-uplets servent à regrouper des données, à organiser des données et à manipuler des entités avec plusieurs caractéristiques
+|> servent principalement dans les paramètres d'une fonction, dans une valeur retour d'une fonction ou dans les listes
+
+On peut déclarer des alias de type avec la syntaxe `Nom = Type`, e.g.
+```python
+Point = Tuple[float, float]
+Nuage = List[Point]
+```
+
+> [!warning] Mutabilité des $n$-uplets
+> Contrairement aux listes, les $n$-uplets ne sont pas mutables !
+
+> [!tip] Itération sur une liste de $n$-uplets
+> On peut déconstruire les $n$-uplets dans une boucle `for` sans avoir besoin de déclarer leur type, e.g.
+```python
+nuages : Nuage
+for (x, y) in nuages:
+	print(x, y)
+```
+
diff --git a/semestre 1/informatique/7- Compréhensions.md b/semestre 1/informatique/7- Compréhensions.md
new file mode 100644
index 0000000..7cca9bd
--- /dev/null
+++ b/semestre 1/informatique/7- Compréhensions.md
@@ -0,0 +1,49 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 1
+---
+Il y a pleins de manière différente d'écrire une fonction
+|> comment on peut trier ces fonctions ?
+
+Du point de vue utilisateur, on s'en fout (s'il n'y a pas de diff niveau performance)
+
+Un code est mieux s'il est concis, s'il est lisible pour un être humain et si sa structure est bonne
+|> est subjectif
+## Linting dans l'UE
+- utiliser plus de `for` que des `while`
+- parcourir une structure directement sans passer par les indices quand c'est possible
+- minimiser le nombre de variable quand ça n'entraîne pas de calculs supplémentaires
+- minimiser le nombre de ligne quand ça n'altère pas sa lisibilité
+- décomposer son code en plusieurs fonctions
+## Compréhensions
+Les compréhensions sont les déclarations implicites de liste/d'ensemble
+
+Explicite en maths = $\{1, 2, 3, 4\}$ ou $E_1\cup E_2$
+Explicite en python = `[1, 2, 3, 4]`
+
+Implicite en maths = $\{n\in [|1, 10|], n = 1\pmod 2\}$
+Implicite en python = `[i for i in range(1, 11) if i % 2 == 1]`
+
+Elles s'écrivent :
+```python
+[exp for var in seq cond]
+```
+où :
+- `exp` est une expression pouvant utiliser `var` 
+- `seq` est une séquence
+- `cond` est une condition (utilisant possiblement une autre boucle)
+
+```python
+[(i,j) for i in range(3) if i % 2 == 0 for j in range(3) if j % 2 == 0] = [
+	(0, 0),
+	(0, 2),
+	(2, 0),
+	(2, 2)
+]
+```
+
+Les compréhensions permettent de 
+- gagner du temps (moins de chose à écrire)
+- gagner des points (souvent les compréhensions donnent des points bonus)
\ No newline at end of file
diff --git a/semestre 1/informatique/8- Ensembles & dictionnaires.md b/semestre 1/informatique/8- Ensembles & dictionnaires.md
new file mode 100644
index 0000000..f328267
--- /dev/null
+++ b/semestre 1/informatique/8- Ensembles & dictionnaires.md
@@ -0,0 +1,133 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 1
+---
+Problème de nos structures de données : comment on représente des structures non ordonnées ?
+|> les séquences ont forcément un ordre
+|> exemple de structure de données sans ordre : les ensembles mathématiques
+
+> [!fail] Problèmes des listes
+> pour ce type de structure de données
+> - ordonnées
+> - occurrences multiples
+> - besoin de parcourir toute la liste
+## Ensembles
+Ensembles :
+- il n'y a pas d'ordre
+- il n'y a pas de doublon
+- l'appartenance est efficace
+
+Ensemble = collection d'objets distincts, ses objets s'appellent les éléments de l'ensemble
+```python
+s: Set[T] = {e1, e2, ..., ei}
+```
+où `T` est un type immutable (e.g., entiers, strings) et $\forall ei$ de type `T` (si un `ei` est égal à un autre `ei`, alors il est retiré)
+|> l'ensemble doit être homogène
+
+> [!warning] Mutabilité des ensembles
+> Un ensemble est mutable, mais il contient des éléments immutable
+> |> on ne peut pas avoir d'ensemble de liste
+
+L'accès direct à partir de la clef est bien plus efficace que l'accès par indice classique
+
+Pour créer un ensemble, on utilise `set()` !
+```python
+ens: Set[T] = set()
+```
+
+On teste l'appartenance d'un élément à un ensemble avec l'opérateur booléen `in` :
+```python
+elem in ensemble
+```
+La non appartenance se note :
+```python
+elem not in ensemble
+```
+
+Pour ajouter des éléments, on utilise :
+```python
+ens.add(elem)
+```
+où `ens` est un `Set[T]` et `elem` est un `T`
+
+Pour retirer des éléments, on fait :
+```python
+ens.remove(elem)
+```
+où `ens` est un `Set[T]` et `elem` est un `T`
+
+> [!tip] Efficacité
+> `ens.add` est plus efficace que `l.append`, de même pour `ens.remove` (sachant que remove n'a pas d'équivalence sur les listes)
+
+On itère dessus en parcourant forcément par élément (car non ordonné !)
+```python
+ens: Set[T] = set()
+e: T
+for e in ens:
+	...
+```
+
+> [!info] Simulation sur les ensembles
+> On choisit un ordre arbitraire pour faire la simulation de boucle
+
+Opérateurs spéciaux booléens
+- `<` est équivalent à $\subset$
+- `<=` est équivalent à $\subset\lor =$ 
+- `>` est l'inverse de `<`
+- etc.
+
+Opérateurs spéciaux ensemblistes
+- `|` représente $\cup$
+- `&` représente $\cap$
+- `-` est la différence (i.e. `e1 - e2` = $E_1\backslash E_2$)
+- `+` est l'addition (i.e. `e1+e2` = $E_1+E_2$)
+
+On essaye d'utiliser un maximum ces opérateurs car :
+- ils sont plus élégants
+- ils sont parfois légèrement plus efficace
+
+On peut faire des compréhensions avec les ensembles, e.g.
+```python
+{exp for e in seq if pred}
+```
+où `exp` est une expression, `seq` un itérable et `pred` un prédicat
+## Dictionnaire
+Sont des tableaux associatifs
+|> prend des clefs *immutable* qui sont forcément associés à une valeur
+
+Les clefs forment un ensemble
+
+Création d'un dictionnaire :
+```python
+dictionnaire: Dict[str, str] = {
+	"hello": "world",
+	"what's": "up"
+}
+```
+
+Pour set et get :
+```python
+dico["hello"] = "world"
+s: str = dico["hello"] # s contient "world"
+```
+où `dico` est de type `Dict[str, str]`
+
+Deux manière d'itérer sur les dictionnaires :
+```python
+# sur les clefs
+for key in dico:
+	# ...
+for key, value in dico.items():
+	# ...
+```
+où `dico` est un dictionnaire
+
+Voir le diapo pour voir comment on fait une simulation
+
+On peut aussi faire des compréhensions avec les dictionnaires ! E.g.
+```python
+{exp1:exp2 for e in seq if pred}
+```
+où `exp1` et `exp2` sont deux expressions, `seq` un itérable et `pred` un prédicat
\ No newline at end of file
diff --git a/semestre 1/informatique/9- Programmation objet.md b/semestre 1/informatique/9- Programmation objet.md
new file mode 100644
index 0000000..edd1eae
--- /dev/null
+++ b/semestre 1/informatique/9- Programmation objet.md
@@ -0,0 +1,59 @@
+---
+tags:
+  - sorbonne
+  - informatique
+semestre: 1
+---
+On utilise de plus des langages multi-paradigmes
+
+Les langages les plus connus en POO sont Java et C++
+
+POO permet de créer ses propres types de données
+
+Une classe est un modèle des objets
+```python
+class FeuTricolore:
+	def __init__(self) -> None:
+		self._couleur = "rouge"
+	def couleur(self) -> str:
+		return self._couleur
+	def change(self) -> None:
+		if self._couleur == "rouge":
+			self._couleur = "vert"
+		elif self._couleur == "vert":
+			self._couleur = "orange"
+		elif self._couleur == "orange":
+			self._couleur = "rouge"
+	def __rep__(self) -> str:
+		"""est l'équivalent du toString en Java"""
+		return f"couleur {self._couleur}"
+
+feu: FeuTricolore = FeuTricolore()
+for _ in range(10):
+	feu.change()
+	print(f"la couleur du feu est {feu}")
+```
+
+Pour faire hériter une classe, on la met entre parenthèse, e.g.
+```python
+class Point:
+	# ...
+class PointColore(Point):
+	# hérite de Point
+```
+cela permet d'avoir accès à toutes les méthodes de la méthode parente
+
+On représente des classes avec des diagrammes de classes (UML)
+
+Typage nominal = le nom de la classe détermine le type
+|> simple mais limité
+
+Typage structurel = le nom de la classe et toutes les méthodes dans la classe (alourdie le type)
+|> puissant mais lourd
+
+En python, c'est canardesque : duck-typing en anglais ; le typage est dynamique
+|> presque aucun effort mais dangereux
+
+On vérifie le type avec la fonction `isinstance`
+
+Voir le cours pour créer des itérables
\ No newline at end of file
diff --git a/semestre 1/informatique/exos partie 1.pdf b/semestre 1/informatique/exos partie 1.pdf
new file mode 100644
index 0000000..619656f
--- /dev/null
+++ b/semestre 1/informatique/exos partie 1.pdf