\documentclass[utf8,crop,realfonts,rabat]{prepamath}
\usepackage{rabat}
\usepackage{nicematrix}
\graphicspath{{figures/}}
\title{Rabats pour le livre TNSI}
\author{Stéphane Pasquet}
\definecolor{tabularcolorline}{cmyk}{0,0.2,0.5,0}
\renewcommand{\DirListing}{listings/}
\lstset{tabsize=1}
%%%%%%%%%%%%
\begin{document}
% Types de programmation

\begin{colonne}

\begin{cadre}{Types de programmation}
\novspace
\point{Exécution d'un programme}
\vspace*{-3mm}
Il existe différents moyens d'exécuter un programme suivant le langage utilisé.
\Par
\begin{tabular}{|>{\columncolor{tabularcolorline}}Z{m{30mm}}|Z{m{58mm}}|Z{m{15mm}}|}
\rowcolor{tabularcolorline}\hline
\centering\arraybackslash
Type d'exécution
&
\centering\arraybackslash
Représentation
&
\centering\arraybackslash
Exemple
\\\hline
Compilation & \includegraphics{compilation} & C, C++,\newline Pascal\\
\hline
Interprétation & \includegraphics{interpretation} & Python,\newline javascript\\
\hline
Semi-interprétation & \includegraphics{semiInterpretation} & Java\\
\hline
\end{tabular}

\vspace*{-3mm}
\point{Paradigmes de programmation}
\vspace*{-3mm}

Un \textit{paradigme} de programmation est un type de programmation.

\Par

\begin{tabular}{|>{\columncolor{tabularcolorline}}Z{p{21mm}}|*3{Z{p{20mm}}|}Z{p{15mm}}|}
\rowcolor{tabularcolorline}
\hline
\centering\arraybackslash
\hspace*{3mm}Type de\newline
programmation
&
\centering\arraybackslash
\hspace*{2mm}Concepts\newline
utilisés
&
\centering\arraybackslash
\raisebox{-2mm}{Avantages}
&
\centering\arraybackslash
\raisebox{-2mm}{Inconvénients}
&
\centering\arraybackslash
\raisebox{-2mm}{Exemple}
\\\hline
\raisebox{-6mm}{Impérative}
&
• Séquences\newline
d'instructions\newline
• Variables%\newline\hspace*{2mm}globales
&
• Facile à\newline
apprendre\newline
• Simplicité\newline
d'utilisation
&
• Effets\newline\hspace*{1mm}
de bord\newline
• \scalebox{0.95}{Peu structuré}
&
Langage\newline
machine\newline
\mbox{Langage C}\newline
Fortran
\\\hline
\raisebox{-10mm}{Fonctionnelle}
&
• Fonctions,\newline
éventuellement récursives\newline
• {\small Les fonctions} sont aussi des données%Variables\newline\hspace*{2mm}globales\newline\hspace*{2mm}interdites
&
• Structuré\newline
• Pas d'effet\newline\hspace*{2mm}de bord
&
• Difficile\newline\hspace*{2mm}
d'accès\newline
• Complexe\newline\hspace*{2mm}
à utiliser
&
LISP\newline
Ocaml
\\\hline
\raisebox{-10mm}{Orientée objet}
&
• les types (appelés \textit{classes})\newline
définissent une structure et un comportement
%Objets en\newline\hspace*{1mm}
%interaction\newline\hspace*{1mm}
%mutuelle,\newline\hspace*{1mm}
%structurés\newline\hspace*{1mm}
%en classes
&
%\mbox{• \scalebox{0.95}{Modélisation}}\newline 
%proche du réel\newline
Structuration forte\newline
• Modularité\newline
• \'Evolutivité
&
• Concepts\newline\hspace*{1mm} 
sophistiqués\newline
• Consom-\newline
mation de\newline
ressource\newline
importante
&
Java\newline
C++\newline
C\#\newline
Visual\newline Basic
\\\hline
\end{tabular}
\vspace*{-4mm}
\end{cadre}


\end{colonne}

% Réseau & architecture matérielle

\begin{colonne}
\begin{cadre}{Architecture matérielle}
Organisation de l'architecture d'un ordinateur:
\begin{center}
\includegraphics{architecture-materielle}
\end{center}
\vspace*{-7mm}
\end{cadre}

\Par

\begin{cadre}{Réseaux}
\novspace
\point{Encapsulation des données via IP sur un réseau ethernet}
\vspace*{-3mm}
\begin{center}
\includegraphics{reseau}
\end{center}

\vspace*{-3mm}
\point{Masque de réseau}
\vspace*{-3mm}
Décomposition d'une adresse IP en adresse de réseau et de machine.
\begin{center}
\includegraphics{08-masque-reseau}
\end{center}

\vspace*{-7mm}
\point{Protocoles de routage RIP et OSPF}
\vspace*{-3mm}
%\begin{center}\begin{tabular}{|>{\columncolor{tabularcolorline}}Z{m{31mm}}|Z{m{77mm}}|}\hline RIP (Routing\newline Information Protocol)& Le plus court chemin déterminé par le nombre de sauts.\\\hline OSPF (Open\newline Shortest Path First) & Le plus court chemin est déterminé par le coût des routes.\\\hline\end{tabular}\end{center}
\begin{center}
\includegraphics{RIP-OSPF}
\end{center}
\vspace*{-9mm}

\end{cadre}

\end{colonne}


% Arbres

\begin{colonne}

\begin{cadre}{Arbres}
Arbre : structure de données prenant la forme d'un graphe orienté connexe dont tous les n\oe uds ont un unique n\oe ud parent, à l'exception du n\oe ud racine (qui n'en a aucun).
\begin{center}
\includegraphics{arbre}
\end{center}
\vspace*{-5mm}
\point{Propriétés des arbres binaires}
\vspace*{-1em}
Soit un arbre de hauteur $h$ à $f$ feuilles et $n$ n\oe uds.
\Par
\begin{tabularx}{\linewidth}{@{}|Z{>{\centering\arraybackslash}X}|Z{>{\centering\arraybackslash}X}|@{}}
\hline
$n\leqslant2^{h+1}-1$ 
& 
$\log_2(n+1) - 1 \leqslant h \leqslant n$
\\
\hline
$h \geqslant \log_2(f)$
&
$\log_2(f) \leqslant \log_2\left(\dfrac{n+1}{2}\right)$
\\
\hline
\end{tabularx}
\vspace*{-5mm}
\point{Parcours en profondeur}
\vspace*{-5mm}
\begin{center}
\includegraphics{parcours-arbre}
\end{center}
\vspace*{2mm}
\begin{tabular}{|Z{m{13mm}}|Z{m{45mm}}|Z{m{47mm}}|}
\rowcolor{tabularcolorline}\hline
\centering\arraybackslash
Ordre &
\centering\arraybackslash Description &
\centering\arraybackslash Liste des n\oe uds \\
\hline
Préfixe & Ordre dans lequel on rencontre les n\oe uds pour la première fois. & A -- B -- D -- E -- G -- H -- C -- F -- I\\
\hline
Postfixe & Ordre dans lequel on rencontre les n\oe uds pour la dernière fois. & D -- G -- H -- E -- B -- I -- F -- C -- A\\\hline
Infixe & Chaque n\oe ud ayant un fils gauche est répertorié la seconde fois qu'on le rencontre, et chaque n\oe ud n'ayant pas de fils gauche est répertorié la première fois qu'on le rencontre. & D -- B -- G -- E -- H -- A -- C -- I -- F\\\hline
\end{tabular}
\vspace*{-6mm}
\point{Parcours en largeur}
\vspace*{-1em}
On liste les n\oe uds suivant leur niveau dans l'arbre:
\[
\underbrace{\rm A}_{\text{niveau 0}}\kern-2mm -\; \underbrace{\rm B - C}_{\text{niveau 1}} - \underbrace{\rm D - E - F}_{\text{niveau 2}} - \underbrace{\rm G - H - I}_{\text{niveau 3}}
\]
\vspace*{-5mm}
\end{cadre}
\end{colonne}

% Graphes & Structures de données élémentaires

\begin{colonne}

\begin{cadre}{Graphes}
Graphe : structure de données relationnelle qui formalise les connexions entre plusieurs états.

\Par

%\textit{Représentation sagittale}: représentation graphique d'un graphe où les états sont des \textit{sommets}.
%\vspace*{-4mm}
%\point{Types de graphes}
%\vspace*{-3mm}
%\renewcommand{\arraystretch}{1.4}
%\begin{tabular}{|>{\columncolor{tabularcolorline}}m{24mm}|Z{m{102mm}}|}\rowcolor{tabularcolorline}\hline\centering\arraybackslash Type &\centering\arraybackslash Représentation sagittale\\\hlineNon orienté & Deux sommets peuvent être reliés par une \textit{arête} non fléchée.\\\hlineOrienté & Deux sommets peuvent être reliés par un \textit{arc} fléché.\\\hline Pondéré\newline(valué) & Deux sommets peuvent être reliés par une arête ou un \textit{arc} couplé.e. avec un nombre.\\\hline\end{tabular}

\begin{tabular}{|>{\columncolor{tabularcolorline}}m{24mm}|>{\centering\arraybackslash}Z{m{45mm}}|>{\centering\arraybackslash}Z{m{53mm}}|}
\rowcolor{tabularcolorline}\hline
 & Graphes non pondérés & Graphes pondérés\\
\hline
Représentation\newline
sagittale
& 
\includegraphics{graphe} 
& 
\includegraphics{graphe-pondere}
\\\hline
\raisebox{-1mm}{
\begin{minipage}{24mm}
Matrice\newline
d'adjacence ou\newline
de valuation 
\end{minipage}}
& 
\renewcommand{\arraystretch}{1}
$
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=4]
A  & B & C\\
0 & 1  & 1 & A\\
1 & 0  & 1 & B\\
1 & 1  & 0 & C
\end{pNiceMatrix}
$
&
\renewcommand{\arraystretch}{1}
$
\NiceMatrixOptions{code-for-first-row=\color{DB}\scriptstyle,code-for-last-col=\color{DB}\scriptstyle}
M = \begin{pNiceMatrix}[first-row,last-col=4]
A  & B & C\\
0 & 5  & 7 & A\\
5 & 0  & 2 & B\\
7 & 2  & 0 & C
\end{pNiceMatrix}
$
\\
\hline
\raisebox{-4mm}{
\begin{minipage}{24mm}
Implémentation de la matrice  
\end{minipage}}
& 
\begin{minipage}{30mm}
\ttfamily
M = [\newline
\hspace*{10mm}[0,1,1],\newline
\hspace*{10mm}[1,0,1],\newline
\hspace*{10mm}[1,1,0]\newline
\hspace*{8mm}]
\end{minipage}
&
\begin{minipage}{30mm}
\ttfamily
M = [\newline
\hspace*{10mm}[0,5,7],\newline
\hspace*{10mm}[5,0,2],\newline
\hspace*{10mm}[7,2,0]\newline
\hspace*{8mm}]
\end{minipage}
\\\hline
\raisebox{-2mm}{
\begin{minipage}{24mm}
Implémentation par dictionnaire\newline
(liste\newline
d'adjacence)
\end{minipage}}
&
\begin{minipage}{40mm}
\ttfamily
G = \{\newline
\hspace*{10mm}'A' : ['B','C'],\newline
\hspace*{10mm}'B' : ['A','C'],\newline
\hspace*{10mm}'C' : ['A','B']\newline
\hspace*{8mm}\}
\end{minipage}
&
\begin{minipage}{53mm}
\ttfamily
G = \{\newline
\hspace*{1mm}'A' : \{ 'B' : 5 , 'C' : 7 \},\newline
\hspace*{1mm}'B' : \{ 'A' : 5 , 'C' : 2 \},\newline
\hspace*{1mm}'C' : \{ 'A' : 7 , 'B' : 2 \}\newline
\hspace*{8mm}\}
\end{minipage}
\\\hline
\end{tabular}

%\vspace*{-3mm}\point{Parcours}\vspace*{-3mm}\begin{tabular}{|>{\columncolor{tabularcolorline}}m{24mm}|Z{m{102mm}}|Z{m{53mm}}|}\hline En largeur & On part d'un sommet, on enfile ses voisins directs absents de la \textit{file} et on défile tant que la file n'est pas vide.\\\hline En profondeur & On empile un sommet; tant que la \textit{pile} n'est pas vide, on choisit l'un des voisins du sommet de la pile absent de celle-ci et qui ne sont pas passés par la pile. Sinon, on dépile.\\\hline\end{tabular}
%\vspace*{-3mm}
%\point{Algorithme de Dijkstra}
%\vspace*{-3mm}
%Recherche autant de plus courts chemins qu'il existe de sommets accessibles depuis le sommet de départ.
\vspace*{-6mm}
\end{cadre}

\begin{cadre}{Structures de données élémentaires}

\vspace*{-5mm}
\begin{center}
\begin{tabular}{|>{\columncolor{tabularcolorline}\centering\arraybackslash}m{25mm}|Z{m{75mm}}|}
\hline
Tableau & Séquence finie et de taille fixe d'éléments auxquels on peut accéder par leur indice.\\
\hline
Dictionnaire & Association dynamique de paires clé/valeur.\\
\hline
Liste & Groupe d'éléments ordonnés que l'on peut manipuler individuellement.\\
\hline
Pile & Collection remplie sur le principe \og dernier arrivé, premier sorti \fg (LIFO).\\
\hline
File & Collection remplie sur le principe \og premier arrivé, premier sorti \fg{} (FIFO).\\
\hline
\end{tabular}
\end{center}
\vspace*{5mm}
\begin{minipage}{6cm}
\point{Pile}
\vspace*{-12mm}\hspace*{10mm}
\includegraphics{pile}
\end{minipage}
\hspace*{1cm}
\begin{minipage}{6cm}
\point{File}
\vspace*{-12mm}\hspace*{10mm}
\includegraphics{file}
\end{minipage}

%\vspace*{-8mm}
\end{cadre}

\end{colonne}

% Processus

\begin{colonne}

\begin{cadre}{Sécurité}
Principe de l'authentification d'un message entre deux correspondants:
\Par
\begin{center}
\includegraphics{securite}
\end{center}
\vspace*{-3mm}
\end{cadre}

\Par

\begin{cadre}{Processus}
\textit{Processus} (\textit{process} en anglais) : instance d'un programme, chargée en mémoire,\\qui est exécutée de manière continue ou discontinue par le système d'exploitation.

\vspace*{-3mm}
\point{\'Etats principaux d'un processus}
\vspace*{-1em}
\begin{center}
\includegraphics{07-etats-03}
\end{center}

\point{Deadlock (interblocage)}
\vspace*{-0.7em}

Deux processus (A) et (B) sont chacun en attente d'un travail que doit fournir l'autre.

\vspace*{-5mm}
\end{cadre}





\end{colonne}

% SGBD

\begin{colonne}

\begin{cadre}{Système de gestion de bases de données (SGBD)}
\novspace
\point{Principe de fonctionnement d'un SGBD}
\vspace*{-1mm}
\begin{center}
\includegraphics{sgbdr-structure}
\end{center}

\vspace*{-3mm}
\point{Les différentes jointures de tables}
\vspace*{-5mm}
\begin{center}
\includegraphics{sgbd}
\end{center}
\vspace*{-4mm}
\point{Requêtes SQL}
\vspace*{-4mm}
\begin{itemize}
\item[$\to$] Requête de sélection: 
\begin{center}
\tt 
SELECT ... FROM <table> WHERE ... AND ... 
\end{center}

\Par

\item[$\to$] Requête d'insertion:
\begin{center}
\ttfamily
INSERT INTO <table> VALUES ...
\end{center}

\Par

\item[$\to$] Requête de suppression:
\begin{center}
\ttfamily
DELETE FROM <table> WHERE ...
\end{center}

\Par

\item[$\to$] Requête de modification:
\begin{center}
\ttfamily
UPDATE <table> SET ... = ...  WHERE ...
\end{center}
\end{itemize}

\vspace*{7mm}~
\end{cadre}
\end{colonne}



\end{document}
