\documentclass[french,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc} % systématique
\usepackage{babel}
\usepackage[left=1.5cm, right=1.5cm, top=1.5cm, bottom=1.5cm]{geometry}
%\usepackage{fancybox}
\usepackage{color}
%\usepackage{graphics}
%\usepackage{multicol} % pour organiser le document en colonnes si \twocolumn insuffisant
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{stmaryrd} % some fonts / symbols (\llbracket for example)
%\usepackage{array} % étend les options des envts array et tabular
\usepackage{minted} % pour mettre en forme du code
%\usepackage{calrsfs} % lettres calligraphiées avec \mathcal
%\usepackage{esint} % for \oiint

\title{Informatique MPSI / MP : L'essentiel}
\author{Louis Alvin}
\date{\today}


\begin{document}


\maketitle



\section{Représentation des nombres}

\paragraph{Entiers (\(\mathbb{N}\))} sur n bits : \(2^{n}\) valeurs : de 0 à \(2^{n}-1\).\\
Pour convertir un nombre en binaire : méthode des divisions euclidiennes successives par 2.

\paragraph{Entiers relatifs (\(\mathbb{Z}\))} Méthode du complément à 2.\\
Si \(x > 0\), on le représente sur \(n-1\) bits. Si \(x < 0\) :\\
1) décomposition en binaire de \(2^{n} - x\)\\
2) écriture binaire de \(- x\) ~ \textrightarrow ~ inverser les bits ~ \textrightarrow ~ ajouter 1.\\
En complément à 2, on peut représenter \(\llbracket -2^{n-1}~;~2^{n-1} - 1 \rrbracket\)

\paragraph{Réels (\(\mathbb{R}\)) :} \(y = (1, b_{1}b_{2} ~ ... ~ b_{k})\) ; norme IEEE-754 sur 64 bits.\\
\begin{itemize}
\item 1 bit de signe \(s\)
\item exposant \(p\) sur 11 bits, représenté par \(p + 1023\)
\item mantisse \(m\) sur 52 bits
\end{itemize}



\section{Bases de données relationnelles -- SQL}


\subsection{Opérateurs de base}

\paragraph{Projection} \(\prod_{c_{1},...,c_{p}}(t)\) ~ : ~ \texttt{\textcolor{red}{SELECT [DISTINCT]} client \textcolor{red}{FROM} achats}

\paragraph{Sélection} \(\sigma_{c}(t)\) ~ : ~ \texttt{SELECT * FROM achats \textcolor{red}{WHERE} prix > 40}

\paragraph{Conditions} Opérateurs de comparaisons : =, !=, >, >=, ..., \textcolor{red}{\texttt{IS [NOT] NULL}}. \\
Opérateurs booléens : \texttt{AND, OR, NOT}.

\paragraph{Trier} \texttt{SELECT ... FROM ... \textcolor{red}{ORDER BY} ... \textcolor{red}{ASC/DESC}}

\paragraph{Renommage} \(\rho_{a \rightarrow b}(t)\) ~ :\\
\texttt{SELECT client,prix-prix*remise/100 \textcolor{red}{AS} prix\_reduit \\
FROM achats WHERE \textcolor{blue}{prix\_reduit} < 55}

\paragraph{Opérateurs ensemblistes} \texttt{UNION}, \texttt{INTERSECT} (sauf pour MySQL) ; \texttt{EXCEPT} (pour SQLite, \texttt{MINUS} sur MySQL).


\subsection{Opérateurs plus complexes}

\paragraph{Fonctions d'agrégation} \texttt{SELECT \textcolor{blue}{MAX(prix)} FROM achats}\\
Fonctions disponibles : \texttt{MAX, MIN, SUM, AVG, COUNT}\\
(\texttt{COUNT(c)} ~ \textrightarrow ~ nb colonnes non \texttt{NULL} ~ ; ~ \texttt{COUNT(*)} ~ \textrightarrow ~ nb total de colonnes)

\paragraph{Requêtes agrégatives} \texttt{GROUP BY} et \texttt{HAVING}\\
N.B. : \texttt{WHERE} ~ \textrightarrow ~ avant les groupes ~ ; ~ \texttt{HAVING} ~ \textrightarrow ~ après les groupes

\paragraph{Produit cartésien ; Jointures}
Dans l'algèbre relationnelle, la jointure symétrique de deux tables \(t\) et \(t'\) selon les attributs \(a\) et \(a'\), est notée : ~ \(t[a=a']t'\) ~ ou ~ \( t \underset{a=a'}\bowtie t'\) et est définie par :
\(t \underset{a=a'}\bowtie t' = \sigma_{a=a'}(t \times t')\).\\
En SQL : \texttt{SELECT * FROM batiments \textcolor{red}{JOIN} chambres\\
\textcolor{red}{ON} batiments.nom = chambres.batiment}

\paragraph{\texttt{LIMIT} et \texttt{OFFSET}} (tout à la fin d'une requête, généralement après \texttt{ORDER BY}) \\
\texttt{LIMIT} ~ \textrightarrow ~ renvoyer un nombre de lignes limité\\
\texttt{OFFSET} ~ \textrightarrow ~ effectue un décalage : nombre de lignes à passer avant de renvoyer le résultat\\



\section{Algorithmes numériques}


\subsection{Recherche dichotomique dans une liste triée}

\begin{minted}{python}
def recherche_dicho(x,L):
	i = 0
	j = len(L)-1
	while i <= j:
		p = (i+j)//2
		if L[p] == x:
			return True
		elif L[p] > x:
			j = p - 1
		else:
			i = p + 1
	return False
\end{minted}


\subsection{Calcul d'intégrale (méthode des rectangles)}

On utilise la méthode des rectangles (gauches), dont la formule est :
\[ I_{a,b}^{R}(f) = \frac{b-a}{n} \times \sum_{i=0}^{n-1} f(x _{i}) \]

\begin{minted}{python}
def rectangles(f,a,b,n):
	integrale = 0
	h = (b-a)/n
	x = a
	for i in range(n):
		integrale += f(x)
		x = x+h
	return h * integrale
\end{minted}

Remarque : méthode des trapèzes : on approxime \( \int_{a}^{b} f(x) dx \) par
\( \underset{i=0}{\overset{n-1}\sum} h \times \frac{f(x_{i}) + f(x_{i+1})}{2} \).


\subsection{Résolution d'équation par recherche dichotomique}

La fonction suivante renvoie une valeur approchée d'un zéro de \(f\) sur \([a,b]\) avec une précision \(\mathtt{epsilon}\).\\
\(f(a)\) et \(f(b)\) de signes opposés, ~ \(a < b\), ~ \(\varepsilon > 0\).

\begin{minted}{python}
def dichotomie(f, a, b, epsilon):
	u,v = a,b
	while v-u >= epsilon:
		milieu = (u+v)/2
		if f(u) * f(milieu) < 0:
			v = milieu
		else:
			u = milieu
	return u
\end{minted}


\subsection{Résolution d'équation par la méthode de Newton}

Conditions : \(f\) doit être de classe \(C^{1}\) sur \([a,b]\) et \(f(a)\) et \(f(b)\) doivent être de signe opposé.\\
La méthode de Newton consiste à itérer la suite \(x_{n}\) définie par :
\[ \left\{
	\begin{array}{ll}
		x_{0} \in [a,b] \\
		\forall n \in \mathbb{N}, ~ x_{n+1} = x_{n} - \frac{f(x_{n})}{f'(x_{n})}
	\end{array}
	\right. \]

\begin{minted}{python}
def newton_residu(f, fprime, x0, epsilon):
	x = x0
	while (abs(f(x)) > epsilon):
		x = x - f(x)/fprime(x)
	return x	
\end{minted}
\begin{minted}{python}
def newton_increment(f, fprime, x0, epsilon):
	x, y = x0, x0 - f(x0)/fprime(x0)
	while (abs(y - x) > epsilon):
		x, y = y, y - f(y)/fprime(y)
	return x
\end{minted}


\subsection{Résolution d'équation différentielle par la méthode d'Euler}

\paragraph{Ordre 1}
On considère une équation différentielle de la forme 
\( \left\{
	\begin{array}{ll}
		y' = f(t,y) \\
		y(t_{0}) = y_{0} ~\text{(condition initiale)}
	\end{array}
	\right. \)
sur l'intervalle \([a,b]\) (en général \(t_{0} = a\)). \\
On souhaite approximer la fonction \(y\) en un certain nombre d'instants répartis sur \([a,b]\). \\
On note \(y_{i}\) l'approximation de la fonction \(y\) à l'instant \(t_{i}\). On détermine les \(y_{i}\) de proche en proche : \\
\( y(t_{i+1}) = y(t_{i}+h) \underset{\text{(D.L.)}}= y(t_{i}) + h\, y'(t_{i}) + o(h)
\underset{\text{(y sol.)}}= y_{i}+h\, f(t_{i},\, y(t_{i})) + o(h)
\approx y_{i} + h\, f(t_{i},\, y_{i}) \) \\[6pt]
Au final, on a donc :
\( \left\{
	\begin{array}{ll}
		y_{i+1} = y_{i} + h \times f(t_{i}, y_{i}) \\
		t_{i+1} = t_{i} + h
	\end{array}
	\right. \)
avec
\( \left\{
	\begin{array}{ll}
		y_{0} \in \mathbb{R} \\
		t_{0} = a
	\end{array}
	\right. \)


\begin{minted}{python}
def euler(f, a, b, y0, n):
	h = (b-a)/n
	t, y = a, y0
	T, Y = [a], [y0]
	for i in range(n):
		y = y + h * f(t,y)
		Y.append(y)
		t = t + h
		T.append(t)
	return T, Y
\end{minted}

\paragraph{Ordre 2}
Pour résoudre numériquement un système différentiel contenant \(n\) équations, on le voit comme une seule ED de la forme \( Y'(t) = F(t,Y(t)) \) où \( t \rightarrow Y(t) \in \mathbb{R}^{n} \) est \textbf{une fonction vectorielle}.\\
Conséquence : dans la méthode d'Euler, la relation de récurrence vérifiée par les \( (y_{i}) \) est la même.\\
\begin{tabular}{r|l}
	Euler ordre 1         & \( y_{i+1} = y_{i} + h \times f(t_{i},y_{i}) \in \mathbb{R} \) \\
	Euler systèmes diff.  & \( Y_{i+1} = Y_{i} + h \times F(t_{i},Y_{i}) \in \mathbb{R}^{n} \) \\
	Implémentation Python & \textcolor{red}{\texttt{y = y + h * f(t,y)}}\\
\end{tabular} \\
Attention : pour l'implémentation, on n'utilise pas des listes mais des tableaux Numpy. Par exemple :
\begin{minted}{python}
def F(t,Y):
	u,v = Y # ou encore : u,v = Y[0],Y[1]
	x = 3*u + 4*v + t
	y = 4 * np.cos(u) - 3*t
	return np.array([x,y])
\end{minted}
On peut alors utiliser la fonction \texttt{euler} telle quelle : \texttt{LT,LY = euler(F,a,b,Y0,n)}.

\paragraph{Ordre supérieur}
On considère le vecteur \( Y(t) = \left(
\begin{array}{c}
	y(t) \\
	y'(t) \\
\end{array}
\right) \).\\
Alors \( Y'(t) = \left(
\begin{array}{c}
	y'(t) \\
	y''(t) \\
\end{array} \right)
= \left(
\begin{array}{c}
	y'(t) \\
	2y'(t) + sin(y(t)) + t^{2} \\
\end{array} \right)
=
F(t, Y(t)) \)
ne dépend que de \(t\), \textcolor{red}{\(y(t)\) et \(y'(t)\)}.\\
En Python :
\begin{minted}{python}
def F(t,Y):
	# Y = (y,y')
	return np.array([Y[1], 2*Y[1] + np.sin(Y[0]) + t**2])
\end{minted}
Cette méthode se généralise aux ED d'ordre \(p \geq 3\) et aux systèmes différentiels d'ordre \(p \geq 2\).


\subsection{Résolution de système linéaire}

On considère un système linéaire qu'on peut écrire matriciellement sous la forme :
\[ \left(
\begin{array}{ccc}
	a_{0,0} & \ldots & a_{0,n-1} \\
	\vdots && \vdots \\
	a_{n-1,0} & \ldots & a_{n-1,n-1} \\
\end{array} \right) \left(
\begin{array}{c}
	x_{0} \\
	\vdots \\
	x_{n-1} \\
\end{array} \right)
= \left(
\begin{array}{c}
	b_{0} \\
	\vdots \\
	b_{n-1} \\
\end{array} \right)
 ~ \Longleftrightarrow AX = B
 ,~~~~~ A \in \mathcal{M}_{n}(\mathbb{R}), ~ X \in \mathbb{R}^{n} ~ \text{(inconnue)}, ~ B \in \mathbb{R}^{n}.
\]
On suppose que \(A \in GL_{n}(\mathbb{R})\). Donc \(\exists! ~ X \in \mathbb{R}^{n}, ~ AX = B\).\\
Les matrices sont représentées par des tableaux Numpy à deux dimensions. On veillera à distinguer les opérations qui copient un tableau de celles qui le modifient directement ~ \textrightarrow ~ voir cours : \textit{Slices and views -- Coupes et vues}.\\
Exemples : si \( A = \left(
\begin{array}{ccc}
	1 & 4 & -3 \\
	-4 & 0 & 2 \\
\end{array} \right) \),~
\texttt{b = A[1]} contient \( (-4 ~~ 0 ~~ 2) \) ; \texttt{c = A[:,2]} contient \( \left(
\begin{array}{c}
	-3 \\
	2 \\
\end{array} \right) \).\\
Une instruction telle que \texttt{A[1,2] = 7} modifie aussi \texttt{b} (qui vaut alors \((-4 ~~ 0 ~~ 7)\)) et \texttt{c} : ce sont des vues.\\
On utilise cela lors de l'échange de deux lignes, pour éviter de copier le tableau entier.\\

\paragraph{Principe général}
Étape 1 : descente : on met le système sous forme triangulaire supérieure.\\
Étape 2 : remontée : on résout le système triangulaire.\\
Pour la formalisation, voir cours (Chap 15).
\begin{minted}{python}
def echange(A,i,j):
	tampon = A[i].copy()
	A[i] = A[j]
	A[j] = tampon

def recherche_pivot(A,j): # naïf
	i = j
	while A[i,j] == 0:
		i = i + 1
	return i

def elimination(A,b,j):
	i = recherche_pivot(A,j)
	echange(A,i,j)
	echange(b,i,j)
	for k in range(j+1, A.shape[0]):
		b[k] = b[k] - (A[k,j]/A[j,j]) * b[j]
		A[k] = A[k] - (A[k,j]/A[j,j]) * A[j]

def descente(A,b):
	for j in range(A.shape[1]-1):
		elimination(A,b,j)

def remonte(A,b):
	n = A.shape[0]
	X = np.zeros(n)
	for k in range(n-1, -1, -1):
		somme = 0
		for l in range(k+1, n):
			somme = somme + A[k,l]*X[1]
		X[k] = (b[k]-somme) / A[k,k]
	return X

def resolution(A,b):
	A_copie = A.copy()
	b_copie = b.copy()
	descente(A_copie, b_copie)
	return remonte(A_copie, b_copie)
\end{minted}



\newpage


\section{Algorithmes de tri}


\subsection{Tri insertion}

On insère \texttt{L[i]} à la bonne place dans la portion \texttt{L[:i]} déjà triée, pour \( \mathtt{i} \in \llbracket 1 ; \mathtt{len(L)} - 1 \rrbracket \).

Deux méthodes : soit on effectue des échanges à gauche tant que l'élément à insérer est inférieur à son voisin de gauche, soit on décale les éléments à déplacer avant d'insérer le nouvel élément.

\begin{minted}{python}
def tri_insertion(L):
	for i in range(1,len(L)):
		x = L[i]
		j = i - 1 # indice de l'élément à comparer avec x
		while j >= 0 and x < L[j]:
			L[j+1] = L[j] # recopie à droite
			j = j - 1
		L[j+1] = x # insertion de x à la bonne place
\end{minted}

Pas de \texttt{return L} : la liste est triée \textit{en place}.

\paragraph{Complexité}

Dans le meilleur cas, si la liste est déjà triée, la complexité de ce tri est en \(\mathcal{O} (n)\).

Dans le pire cas, \texttt{L} est triée dans l'ordre décroissant. On a alors une complexité en \(\mathcal{O} (n^{2})\).

Complexité moyenne en \(\mathcal{O} (n^{2})\) également.


\subsection{Tri fusion}

On coupe la liste en deux portions de taille presque égales qu'on trie récursivement, puis on fusionne en plaçant à chaque étape le plus petit des éléments en tête de liste à fusionner à la suite des éléments déjà extraits. \\
Exemple : \( \left[ 2,7,1,4,3,6,5,8 \right] \longrightarrow
\begin{array}{c}
\left[ 2,7,1,4 \right] \\ \left[ 3,6,5,8 \right]
\end{array}
\underset{\text{tri récursif}}\longrightarrow
\begin{array}{c}
\left[ 1,2,4,7 \right] \\ \left[ 3,5,6,8 \right]
\end{array}
\underset{\text{fusion}}\longrightarrow
\left[ 1,2,3,4,5,6,7,8 \right] \)

\begin{minted}{python}
def fusion(L1,L2):
	L = []
	while L1 != [] and L2 != []:
		if L1[0] > L2[0]:
			L.append(L2.pop(0))
		else:
			L.append(L1.pop(0))
	return L + L1 + L2

def tri_fusion(L):
	if len(L) <= 1:
		return L
	L1 = tri_fusion(L[:len(L)//2]) # // et pas /
	L2 = tri_fusion(L[len(L)//2:])
	return fusion(L1,L2)
\end{minted}

Fusion : On peut se passer des \texttt{pop()} en gardant en mémoire deux indices correspondant aux éléments de \texttt{L1} et \texttt{L2} à comparer.
À la sortie du \texttt{while}, une seule des deux listes \texttt{L1} et \texttt{L2} est vide et l'autre contient des éléments supérieurs à ceux de \texttt{L}.

Remarque : Ce n'est pas un tri en place (à cause des slicings).

\paragraph{Complexité}

\( T(n) = \mathcal{O} (n \log n) \) dans tous les cas (meilleur, pire, moyen).


\subsection{Tri rapide}

Aussi appelé \textit{Tri partition}, ou \textit{Quicksort} en anglais.

\paragraph{Principe}

On choisit un pivot \(p \in \mathtt{L}\). \\
La partition consiste à mettre la liste sous la forme :
\(\begin{array}{|c|c|c|}
\hline
\leq p & p & > p \\
\hline
\end{array}\). Puis on trie récursivement les deux parties \( \leq p \) et \(> p\).

Comment partitionner ? Schéma de Lomuto : à chaque étape, \texttt{L} est de la forme :
\(\begin{array}{ccccccc}
\mathtt{deb} & & \mathtt{i} & & \mathtt{j} & & \mathtt{fin} \\
\downarrow & & \downarrow & & \downarrow & & \downarrow \\
\hline
| ~p~ |& \leq p &| ~~ & > p &| ~~ & \text{???} & ~~ | \\
\hline
\end{array}\) \\
Initialement,
\(\begin{array}{|c|}
\hline
\leq p \\
\hline
\end{array}\) et
\(\begin{array}{|c|}
\hline
> p \\
\hline
\end{array}\) sont vides, donc \texttt{i = j = deb + 1}. \\
Au tour de boucle \texttt{j}, si \(\mathtt{L[j]} > p\), il est à la bonne place et on ne fait rien ; si \(\mathtt{L[j]} \leq p\), \textcolor{red}{on échange \texttt{L[j]} et \texttt{L[i]}}.

\begin{minted}{python}
def partition(L,deb,fin):
	i = deb + 1
	p = L[deb]
	for j in range(deb+1, fin+1):
		if L[j] <= p:
			L[i],L[j] = L[j],L[i]
			i = i + 1
	L[deb],L[i-1] = L[i-1],L[deb]
	return i - 1 # /!\

def tri_partition(L,deb,fin):
	if deb < fin:
		k = partition(L,deb,fin)
		tri_partition(L,deb,k-1)
		tri_partition(L,k+1,fin)
\end{minted}

C'est un tri en place. Pour trier une liste en entier, on exécute \texttt{tri\_partition(L, 0, len(L)-1)}.

\paragraph{Complexité}

\( \mathcal{O} (n^{2}) \) dans le pire cas. \(\mathcal{O} (n \log n)\) dans le meilleur.




\end{document}