%\chapter{Ensembles, logique}


\modeexercice

\section*{Ensembles, logique, arithmétique}


  \begin{exercice}[Ensembles égaux]
    Parmi les ensembles suivants, quels sont ceux qui sont égaux?
    \begin{multicols}{2}
\begin{enumerate}
\item $A=\bigl\{x\mid x\in \bbr \text{ et } x^2-4x+3=0\bigr\}$
\item $B=\bigl\{x\mid x\in\bbr \text{ et } x^2-3x+2=0\bigr\}$
\item $C=\bigl\{x\mid x\in\bbn \text{ et } x<3 \bigr\}$
\item $D=\bigl\{x\mid x\in\bbn  \text{ et } x<5 \text{  et }x \text{ est
      impair }\bigr\}$
\item $E=\bigl\{1,2\bigr\}$
\item $F=\bigl\{1,2,1\bigr\}$
\item $G=\bigl\{3,1\bigr\}$
\item $H=\bigl\{1,1,3\bigr\}$
\end{enumerate} 
\end{multicols}
  \end{exercice}



%%
\begin{exercice}[Ensembles définis en extension]
$E=\left\{ 0,1,2,3,4,5,6\right\}  .$ Définir  en extension  (c'est-à-dire lister
tous les éléments) les ensembles
suivants :
 \begin{multicols}{3}
\begin{enumerate}
\item $A_{1}=\left\{ x\in \mathbb{N}\mid x^{2}\in E\right\} $

\item $A_{2}=\left\{ x\in \mathbb{R}\mid x^{2}\in E\right\} $

\item $A_{3}=\left\{ x\in E\mid x^{2}\in E\right\} $

\item $A_{4}=\left\{ x\in E\mid \sqrt{x}\in E\right\} $

\item $A_{5}=\left\{ x\in E\mid 2x\in E\right\} $

\item $A_{6}=\left\{ x\in E\mid \frac{x}{2}\in E\right\} $
\end{enumerate}
\end{multicols}
\end{exercice}



%

\begin{exercice}[Ensemble défini par compréhension]
 Écrivez en compréhension l'ensemble $ \bbd$ des décimaux, l'ensemble
  $ ℚ$ des rationnels, l'ensemble $ ℂ$ des complexes.

  L'ensemble des réels  $ ℝ$ est un peu plus  délicat à définir malgré
  son nom...
\end{exercice}


%

\begin{exercice}[Négation des quantificateurs]

Quelle peut-être la négation de $(∀ x)(P(x))$? De $(∃ x)(P(x))$?



 L'ensemble universel est $S=\bigl\{1,2,3,4,5\bigr\}$.  Pour chacune des propositions suivantes,
donnez-en la négation puis la valeur de vérité.

\begin{multicols}{2}
\begin{enumerate}
\item $(\exists x)(x + 3 = 10)$
\item $(\forall x)(x +3<10)$
\item $(\exists x )(x+3<5)$
\item $(\forall x)(x+3 \leqslant 7)$
\end{enumerate}
\end{multicols}
\end{exercice}

%


\begin{exercice}[Pas d'erreur de type!]




$E=\left\{ 0,1,2,3,4\right\} .$ Compléter, lorsque c'est possible, par
un des symboles (il peut y avoir plusieurs solutions, mais on s'obligera 
\`{a} choisir celle qui donne le plus \og de renseignements\fg{}): 
$$
\in ,\ni ,\subseteq ,\supseteq ,=,\neq ,\varsubsetneq, \not\subseteq
,\cdots$$


\begin{multicols}{4}
\begin{enumerate}
\item $2\cdots E,$ 
\item $\left\{ 2,3\right\} \cdots E,$ 
\item $\left\{ 2\right\} \cdots E$,
\item $\left\{ 2,3,4\right\} \cdots \left\{ 4,3,2\right\} ,$ 
\item $\left\{2,3,4\right\} \cdots \left\{ 4,3,0\right\} $,
\item $\{\} \cdots E,$ 
\item $E\cdots E,$ 
\item $E\cdots \left\{ E\right\} ,$ 
\item $\{\}  \cdots \left\{ E\right\} $,
\item $E\cdots \left\{ 0,1,2,3,\ldots ,10\right\}$,
\item  $\left\{0,1,2,3,4,5\right\} \cdots E$
\end{enumerate}
\end{multicols}

\end{exercice}


%
\begin{exercice}[Erreur de type]
  Essayez d'expliquer ce qui se passe:
\begin{pythoncode}
In [8]: M = [1,2,3]

In [9]: 1 in M
Out[9]: True

In [10]: [1,2] in M
Out[10]: False  
\end{pythoncode}


\end{exercice}






%
  \begin{exercice}
    Créez des fonctions Python qui:
    \begin{itemize}
    \item calcule la somme de 2 entiers;
\item calcule la somme d'une collection d'entiers;
\item calcule la longueur d'une collection;
\item calcule la moyenne d'une collection d'entiers;
\item calcule la somme des carrés d'une collection d'entiers;
\item concatène une liste de chaînes de caractères;
\item met en majuscules une chaîne de caractères.
    \end{itemize}
  \end{exercice}

%

\begin{exercice}[multi-ensemble]
  On dispose d'un fichier  relevant le nombre de lignes de  code python écrites par
jour par un étudiant sur un an.

\begin{enumerate}
\item 
\begin{enumerate}
\item On veut  tracer la courbe représentant l'évolution du  nombre de lignes en
  fonction du temps:  quelle est la structure adaptée pour  modéliser le fichier
  de données?
\item Et pour calculer le nombre moyen de lignes écrites? 


\end{enumerate}

\item Remarque: un  \textit{multi-ensemble} est un  ensemble dont les  éléments peuvent
être répétés: on dit qu'ils ont un \textit{ordre de multiplicité}.


Par exemple, si $M=\bigl\{a,a,b,b,b,b,f\bigr\}$, l'ordre de multiplicité de $a$ est 2,
celui de $b$ est 4, celui de $f$ est 1, celui de $e$ est 0.

C'est en fait la donnée d'un \textit{ensemble} d'éléments E et d'une application $m$
de cet ensemble vers $\bbn$.

Dans l'exemple précédent, E peut être par exemple $\bigl\{a,b,c,d,e,f,g\bigr\}$ et
$m$  est définie  sur  $E$ par  $m(a)=2$,  $m(b)=4$, $m(c)=m(d)=m(e)=m(g)=0$  et
$m(f)=1$.

\begin{enumerate}
\item Expliquez la  différence entre un multi-ensemble et un  ensemble, entre un
  multi-ensemble et une suite.
\item Proposez  au moins  quatre fonctions Python  qui calculent  la multiplicité
  d'un élément \texttt{x}  dans un multi-ensemble \texttt{M}  qui sera représenté
  par une \textit{liste} d'éléments entre crochets. On pourra comparer les temps
  d'exécution avec \mintinline{python}{%timeit}
 et utiliser des boucles ou des définitions par compréhension.

\begin{pythoncode}
In [33]: M = [ 1,1,1,2,2,3,8,9 ] * 10000

In [34]: %timeit multi4(2, M)
100 loops, best of 3: 2.77 ms per loop  
\end{pythoncode}

\item Prposez des idées de test d'égalité de deux multi-ensembles.


\item Déterminez une  fonction (au moins) qui calcule la  \og somme\fg{} de deux
  multi-ensembles:   c'est  le   multi-ensemble  obtenu   en  additionnant   les
  multiplicités de chaque élément.

  Par   exemple,   $\{1,1,2,2\}   +  \{1,2,2,2,3,3\}   =   \{1,1,2,2,1,2,2,2,3,3\}   =
  \{1,1,1,2,2,2,2,2,3,3\}$.


\item Déterminez une  fonction (au moins) qui calcule la  \og réunion\fg{} de deux
  multi-ensembles: c'est le multi-ensemble obtenu  en affectant aux éléments des
  deux multi-ensembles leur plus grande multiplicité.

  Par exemple, $\{1,1,2,2\} ∪ \{1,2,2,2,3,3\} = \{1,1,2,2,2,3,3\}$.



\item Déterminez une  fonction (au moins) qui calcule l'  \og intersection\fg{} de deux
  multi-ensembles:  c'est le  multi-ensemble  obtenu en  affectant aux  éléments
  communs aux 
  deux multi-ensembles leur plus petite multiplicité.

  Par exemple, $\{1,1,2,2\} ∩ \{1,2,2,2,3,3\} = \{1,2,2\}$.


\item Déterminez une  fonction (au moins) qui calcule la  \og différence\fg{} de deux
  multi-ensembles:  c'est le  multi-ensemble  obtenu en  affectant aux  éléments
  du premier le maximum entre 0 et sa multiplicité dans le deuxième.

  Par exemple, $\{1,1,2,2\} - \{1,2,2,2,3,3\} = \{1\}$.

\item Est-ce que  ces opérations sont compatibles avec  les opérations homonymes
  sur les ensembles?
\end{enumerate}




\end{enumerate}
\end{exercice}



%%

\begin{exercice}[Paire ordonnée - Produit de deux ensembles]

Comment créer de l'ordre à partir du désordre...

\begin{definition}[Paire ordonnée]
On note $\langle a,b\rangle = \bigl\{\{a\},\{a,b\}\bigr\}$
\end{definition}


On remarque tout de suite que les rôles de $a$ et $b$ ne sont pas symétriques.

L'égalité des ensembles va nous permettre  de définir une égalité des paires: ce
n'est pas la même! Un(e) informathicien(ne) doit bien s'en rendre compte...

Démontrez tout d'abord que:

$$(\bigl\{a,b\bigr\} =_{\text{ens}}\bigl\{x,y\bigr\}) \equiv  ((a=x \land b=y) \lor
(a=y \land b=x))$$ 

puis que

  $$(\langle a,b\rangle =_{\text{paire}}\langle x,y\rangle) \equiv (a=x \land b=y)$$

On  peut alors  définir le  produit (cartésien)  de deux  ensembles comme  étant
l'ensemble des paires formées d'éléments de ces ensembles...


\begin{definition}
 $$A\otimes B = \bigl\{\langle a,b\rangle \mid (a\in A) \land (b\in B)\bigr\}$$ 
\end{definition}

Pour se repr\'{e}senter le produit cart\'{e}sien $E\otimes F$ avec $%
E=\left\{ a,b,c\right\} $ et $F=\left\{ 1,2,3,4,5\right\} ,$ on peut \'{e}%
videmment l'\'{e}crire en extension: il poss\`{e}de $3\times 5=15$ \'{e}l%
\'{e}ments (voir \`{a} ce sujet le paragraphe suivant).%


$$
E\otimes F=\bigl\{ \langle a,1\rangle ,\langle a,2\rangle ,\cdots ,\langle
c,5\rangle \bigr\}
$$


mais il est souvent pr\'{e}f\'{e}rable de faire appel \`{a} un tableau du
type suivant :%
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\otimes $ & $\bm{1}$ & $\bm{2}$ & $\bm{3}$ & $\bm{4}$ & $%
\bm{5}$ \\ \hline
$\bm{a}$ & $\langle a,1\rangle $ & $\langle a,2\rangle $ & $\langle
a,3\rangle $ & $\langle a,4\rangle $ & $\langle a,5\rangle $ \\ \hline
$\bm{b}$ & $\langle b,2\rangle $ & $\langle b,2\rangle $ & $\langle
b,3\rangle $ & $\langle b,4\rangle $ & $\langle b,5\rangle $ \\ \hline
$\bm{c}$ & $\langle c,1\rangle $ & $\langle c,2\rangle $ & $\langle
c,3\rangle $ & $\langle c,4\rangle $ & $\langle c,5\rangle $ \\ \hline
\end{tabular}%
\end{center}


Avec Python:

\begin{pythoncode}
In [1]: { (x, y) for x in {'a', 'b', 'c'} for y in {1, 2, 3, 4, 5 } }
Out[1]: 
{('a', 1),
 ('a', 2),
 ('a', 3),
 ('a', 4),
 ('a', 5),
 ('b', 1),
 ('b', 2),
 ('b', 3),
 ('b', 4),
 ('b', 5),
 ('c', 1),
 ('c', 2),
 ('c', 3),
 ('c', 4),
 ('c', 5)}  
\end{pythoncode}



\end{exercice}


%%




\begin{exercice}[Produit cartésien]
  \begin{enumerate}
  \item  Soit  $A=\bigl\{0,1\bigr\}$.  Déterminer  $\left(A^2\setminus
        \bigl\{\langle 0,0\rangle\bigr\}\right)\otimes A$.
    \item            Soit           $A=\bigl\{3,5,7\bigr\}$           et
          $B=\bigl\{a,b\bigr\}$. Déterminer $A^2$, $B^2$, $A\otimes B$,
          $B\otimes A$, $B^2\otimes A$.
  \end{enumerate}
\end{exercice}

%%

\begin{exercice}[CSV]
Quelle structure pourriez-vous associer à un fichier CSV?
\end{exercice}

%%


\begin{exercice}[Ensembles  par  compréhension,   enregistrements  et  bases  de
  données]

Afin de s'exercer à définir des ensembles par compréhension à l'aide de filtres,
nous allons introduire des \og  classes\fg{} Python. Il s'agit normalement d'une
notion de la Programmation Orientée Objet mais nous ne l'utiliserons en fait que
comme  un \textit{enregistrement},  structure que  l'on retrouve  dans tous  les
types de programmation  et que vous explorerez notamment  avec M. \textsc{Morin}
en C. 

Il faudra  juste, pour  l'instant, prendre ça  comme un moyen  de créer  des \og
fiches\fg{} de renseignements.

Prenons par exemple la manière d'enregistrer un alien:

\begin{pythoncode}
class Alien:
    def __init__(self, Nom, Sexe, Planete, NoCabine):
        "Constructeur d'Aliens"
        self.nom       = Nom
        self.sexe      = Sexe
        self.planete   = Planete
        self.no_cabine = NoCabine  
\end{pythoncode}

Cela indique qu'un  alien sera créé en  indiquant son nom, son  sexe, sa planète
d'origine et son numéro de cabine, aucune valeur par défaut n'étant donnée.

On peut donc enregistrer un alien ainsi:

\begin{pythoncode}
In [88]: a = Alien ( "Zorglub", "M", "Trantor", 1 ) 
\end{pythoncode}

et avoir accès à ses \textit{attributs}:

\begin{pythoncode}
In [89]: a.nom
Out[89]: 'Zorglub'

In [90]: a.sexe
Out[90]: 'M'

In [91]: a.planete
Out[93]: 'Trantor'

In [94]: a.no_cabine
Out[96]: 1
\end{pythoncode}

On a créé des \og bases\fg{} regroupant chaque objet créé selon sa classe:

\begin{pythoncode}
baseAlien =  {
  Alien ( "Zorglub",    "M", "Trantor", 1 ),
  Alien ( "Blorx",      "M", "Euterpe", 2 ),
  Alien ( "Urxiz",      "F", "Aurora",  3 ),
  Alien ( "ZBleurdite", "F", "Trantor", 4 ),
  Alien ( "Darneurane","M", "Trantor", 5 ),
  Alien ( "Mulzo",      "M", "Helicon", 6 ),
  Alien ( "Zzzzz",      "F", "Aurora",  7 ),
  Alien ( "Arggh",      "M", "Nexon",   8 ),
  Alien ( "Joranum",    "F", "Euterpe", 9 )
  }  
\end{pythoncode}

On peut ainsi obtenir l'ensemble des noms des aliens:

\begin{pythoncode}
In [98]: { a.nom for a in baseAlien }
Out[100]: 
{'Arggh',
 'Blorx',
 'Darneurane',
 'Joranum',
 'Mulzo',
 'Urxiz',
 'ZBleurdite',
 'Zorglub',
 'Zzzzz'}  
\end{pythoncode}

ou la liste des aliments mangés par les aliens venant de Trantor:

\begin{pythoncode}
In [101]: %paste
lesAlimTrantor = { m.aliment
                   for m in baseMiam
                   for a in baseAlien
                   if m.nom_alien == a.nom
                   if a.planete == "Trantor" }

## -- End pasted text --

In [102]: lesAlimTrantor
Out[106]: {'Bortsch', 'Schwanstucke'}  
\end{pythoncode}

Récupérez le fichier source disponible sur 
\href{http://informathix.tuxfamily.org/?q=node/153}{http://informathix.tuxfamily.org/?q=node/153}
et répondez aux questions posées.
\end{exercice}


%%



\begin{exercice}[Langage formel / langage courant]
  Soit $p$ la proposition \og Je mâche du foin\fg{} et $q$ la proposition \og Je
  mâche du grain\fg{}. Traduire par une phrase en français:

\begin{multicols}{3}
  \begin{enumerate}
    \item $\lnot p$ 
    \item $p\land q$
    \item $p\lor q$
    \item $q \lor \lnot p$
    \item $\lnot (p \land q)$
    \item $(\lnot p) \land (\lnot q)$
    \end{enumerate}
  \end{multicols}
\end{exercice}


%%


\begin{exercice}[Logique d'Hélène et les garçons]
  On  considère les  propositions atomiques  B, T,  V, C  représentant les
assertions  suivantes:  \og  Hélène   est  belle\fg{},  \og  Hélène  joue
au Tennis\fg{}, \og Hélène fait du vélo\fg{}, \og Chri-Chri
aime   Hélène\fg{}.   Énoncez  des   phrases   simples  traduisant   les
propositions suivantes:
\begin{enumerate}
\item 
\begin{multicols}{2}
  \begin{enumerate}
  \item $\lnot B$
\item $\lnot B \land \lnot T$
\item $\lnot(B\lor T)$
\item $(B\land V)⟹ C$
\item $C⟹(B ⟺V)$
\item $((B\lor T)\land \lnot V)⟹ \lnot C$
  \end{enumerate}
  \end{multicols}
\item 

Traduisez par une proposition simple les phrases 
\begin{enumerate}
\item \og Chri-Chri aime Hélène
seulement si elle fait du vélo\fg{}.
\item  \og Chri-Chri aime Hélène
 si elle fait du vélo\fg{}.
\item   \og Chri-Chri aime Hélène
si, et seulement si, elle fait du vélo\fg{}.
\item \og Si Chri-Chri aime Hélène
alors elle fait du vélo\fg{}.
\item \og Si Hélène fait du vélo alors Chri-Chri l'aime\fg{}.
\item \og Il est suffisant qu'Hélène fasse du vélo pour que
      Chri-Chri l'aime\fg{}.
\item \og Il est nécessaire qu'Hélène fasse du vélo pour que
      Chri-Chri l'aime\fg{}.
\end{enumerate}

\end{enumerate}
\end{exercice}

%



\begin{exercice}[Contraposée, réciproque et négation d'une implication]

  \begin{enumerate}
  \item \begin{enumerate}
    \item La contraposée  de $A \Longrightarrow B$ est  $\lnot B \Longrightarrow
      \lnot A$: une implication et sa contraposée      sont-elles équivalentes?
    \item La réciproque de $A\Longrightarrow B$ est $B \Longrightarrow A$.
    \item Exprimez $\lnot(A\Longrightarrow B)$ avec les opérateurs $\lnot$, $\land$ et $\lor$ mais sans
      parenthèses ni $\Longrightarrow$.
    \end{enumerate}
  \item  Déterminez les contraposées, les réciproques puis les négations des propositions suivantes:
    \begin{enumerate}
    \item Si Max n'étudie pas son cours de maths, les filles le fuient.
    \item Bill embrassera Céleste seulement s'il écrit de bons programmes en Python
    \item  Paul marquera  un  but  seulement s'il lit  la  vie de  Carl
      \textsc{Gau\ss} en latin.
    \end{enumerate}
  \end{enumerate}
\end{exercice}


%%




\begin{exercice}[Logique et politique]
  
\begin{quote}
\og In summary, I would like to convey  a little positive message to you...I do not have any...Would two negative messages suit you? 
  \fg{}

\begin{flushright}
  Woody \textsc{Allen}
\end{flushright}
\end{quote}


Reformulez  la  phrase suivante, prononcée lors  du  grand
meeting du  PUB, Parti  Unique Bordure,  afin de  choisir l'unique  candidat des
futures élections dictatoriales, sans négation.

{\itshape Dieter de Villenstein: \og{} Il faut soutenir Josef Chrtzw.  Et
soutenir l'action de  M. Chrtzw, ce n'est pas ne  pas soutenir notre ami
à tous: Nikalaï Schrpuntz\fg{}.}




\end{exercice}


%%



\begin{exercice}[Nouvel opérateur logique]
   Le connecteur$\oplus$ est défini par:
 $1\oplus 1=0$, $ 1\oplus 0=1$, $ 0\oplus 1=1$ et $ 0\oplus 0=0$.
\begin{enumerate}
\item Simplifier:
   \begin{multicols}{4}
     \begin{enumerate}
     \item $ x \oplus 0 $
     \item $ x\oplus 1 $
     \item $ x\oplus x $ 
     \item $ x \oplus \lnot x $
     \end{enumerate}
   \end{multicols} 
 
\item Montrer que:
\begin{multicols}{2}

  \begin{enumerate}
  \item $x \oplus y\equiv \left(x\lor y\right)\land \lnot\left(x\land y\right)$
  \item $ x\oplus y\equiv \left(x\land \lnot y\right)\lor\left(\lnot x \land y\right)$
  \end{enumerate}
\end{multicols}

\item L'opération $\oplus$ est-elle commutative?

\item Vrai ou faux?
\begin{multicols}{3}

  \begin{enumerate}
  \item $  x \oplus \left(y\oplus  z\right)\equiv \left(x\oplus y\right)\oplus
    z$
  \item $x\lor\left(y\oplus z\right)\equiv (x\lor y)\oplus(x\lor z)$
\item $x \oplus(y\lor z)\equiv (x\oplus y)\lor (x\oplus z)$
  \end{enumerate}
\end{multicols}
\end{enumerate}
\end{exercice}




%%



\begin{exercice}[Si ma tante en avait...]
  Commentez  les   phrases  suivantes  en  fonction  de   la  logique  des
propositions:
\begin{multicols}{2}
\begin{enumerate}
\item Si les poules ont des dents alors $2+2=5$;
\item Si $2+2=5$ alors les poules n'ont pas de dents;
\item Si $2+2=5$ alors les poules ont des dents.
\end{enumerate}
\end{multicols}
\end{exercice}

%%



%%


\begin{exercice}[Logique au pays des merveilles]
  

\begin{center}
\includegraphics[width=0.3\linewidth]{MadHatter}
\end{center}


\textit{<<~Reprenez donc un peu de thé~>> propose le Lièvre de Mars.}

\textit{<<~Je n'ai rien pris du tout, je ne saurai donc reprendre de rien~!~>>}

\textit{<<~Vous voulez dire que vous ne sauriez reprendre de quelque chose~>> répartit le Chapelier.\\
 <<~Quand il n'y a rien, ce n'est pas
facile d'en reprendre~>>.}

\sm

 \begin{itemize}

 \item Alors comme ça, vous êtes étudiante?
 \item Oui, en informatique par exemple.
 \item Alors que vaut cette fraction : un sur deux sur trois sur quatre?
 \item Eh bien ...
 \item Elle vaut deux tiers, la devança le Loir.
 \item Ou trois huitièmes si vous préférez, ajouta le Lièvre de Mars.
 \item Ou encore un sur vingt-quatre, affirma le Chapelier.
 \item En fait, je crois que...
\item Aucune importance! Dîtes-nous plutôt combien vous voulez de sucre dans votre thé?
\item Deux ou trois, ça dépend de la taille de la tasse.
\item Certainement pas, car de toute façon, deux ou trois c'est pareil.
\item Parfaitement~! approuva le Loir en fixant Alice qui écarquillait les yeux.
\item Ce n'est pourtant pas ce qu'on m'a appris, fit celle-ci.
\item Pourtant, ce n'est pas compliqué à comprendre, en voici une démonstration des plus élémentaires\\
                On sait que pour tout entier $n$ on a successivement
                $$(n+1)^2=n^2+2n+1$$
                $$(n+1)^2-2n-1=n^2$$
                Retranchons $n(2n+1)$ des deux côtés
                $$(n+1)^2-(n+1)(2n+1)=n^2-n(2n+1)$$
                Mézalor, en ajoutant $(2n+1)^2/4$, on obtient

                $$(n+1)^2-(n+1)(2n+1)+\fr{(2n+1)^2}{4}=
                     n^2-n(2n+1)+\fr{(2n+1)^2}{4}$$
                Soit
                $$\pa{(n+1)-\fr{2n+1}{2}}^2=\pa{n-\fr{2n+1}{2}}^2$$
En passant à la racine carrée, on obtient
$$(n+1)-\fr{2n+1}{2}=n-\fr{2n+1}{2}$$
d'où
$$n+1=n$$
Et si je prends $n=2$, j'ai aussitôt $3=2$
\item Alors, qu'est-ce que vous en dites~?
\item Je...commença Alice.
\item D'ailleurs, cela prouve que tous les entiers sont égaux, la coupa le Lièvre de Mars.
\item Pas mal du tout! Qu'en dites-vous mademoiselle l'informaticienne?
\item Je vais vous dire tout de suite ce que j'en pense.
\item Ah non! Nous préférerions de loin que vous pensiez ce que vous allez nous dire.
\item C'est pareil! grinça Alice qui commençait à en avoir assez.
\item Comment  ça, c'est  pareil~? Dire  ce que  l'on pense  ce serait
  pareil que penser ce que l'on dit? S'étrangla le Lièvre de Mars. 
\item Incroyable ! Et manger ce qu'on voit ce serait pareil que voir ce qu'on mange?
\item Mais...
\item Et respirer quand on dort pareil que dormir quand on respire?
\item En logique, nous vous mettons 3 sur 5.
\item Autant dire moins que un.
\item C'est à dire zéro, puisque si 2=3 alors 1=0.
\item Parce que chez vous, 3 c'est moins que 1? s'indigna Alice.
\item On se demande ce qu'on vous apprend à l'école!%  Bien sûr que oui! Tenez, considérez
% $$f(x)=\fr{x^2+32}{2x^2+1}+\fr{|x|+1}{2x+51}$$
% Eh bien il  est facile de voir  que cette fonction a pour  limite 0 en
% moins l'infini et 1 en plus l'infini. 
% \item Je ne dis pas le contraire, protesta Alice.
% \item  Donc l'image  par $f$  de $\bbr$  est l'intervalle  $]0,1[$, or
%   $f(0)=3$, donc 3 appartient à $]0,1[$ à ce titre : on a bien 3 plus 
% petit que 1. 
Tiens, et  je peux  même vous donner  une démonstartion  beaucoup plus
simple.

Prenez deux nombres non nuls et égaux:
$$ a=b$$ 

Alors

$$a^2=ab $$

et

$$ a^2-b^2=ab-b^2$$

Un peu d'identité remarquable:

$$
(a+b)(a-b)=b(a-b)
 $$

Je simplifie:

$$ a+b = b$$

Mais comme $ a=b$:

$$ 2b=b$$

et je simplifie:

$$2=1 $$




\item C'est de la folie pure, pensa Alice...
\end{itemize}

\it{Merci à Pierre \textsc{Osadtchy}}
\end{exercice}

%%


\begin{exercice}[jeu logique]
  Les jeux virtuels sur ordinateur font souvent appel à des énigmes logiques régies par le calcul des
propositions. Vous participez actuellement à une partie dont les règles sont les suivantes:


{\itshape Les propositions composant une énigme sont alternativement vraies et fausses, c'est-à-dire que:
  \begin{itemize}
  \item  soit les  propositions  de numéro pair  sont  vraies et  les
        propositions de numéro impair fausses;
\item soit les propositions de numéro pair sont fausses et les propositions de numéro impair vraies.
  \end{itemize}
}
 Dans un labyrinthe, vous vous retrouvez bloqué dans une salle face à une porte sur laquelle se
trouvent deux interrupteurs etiquetés A et B en position ouverte. Sur son seuil figure l'inscription
suivante:

\textit{
Pour ouvrir la porte :
\begin{description}
\item[P1] Il faut fermer l'interrupteur A.
\item[P2] Il faut fermer simultanément les interrupteurs A et B.
\item[P3] Il ne faut pas fermer l'interrupteur B.
\end{description}
Attention, en cas d'erreur la salle s'auto-détruira...
}

\begin{enumerate}

\item  Exprimer P1 , P2 et P3 sous la forme de formules du calcul des propositions dépendant
de A et de B.

\item  Exprimer la règle du jeu dans le contexte des propositions P1 , P2 et P3.

\item  En utilisant le  calcul des  propositions, déterminer  l'action à
       effectuer pour ouvrir la porte.

% \item  Les interrupteurs A et B laissent passer un courant (valeur logique vraie) quand ils sont
% fermés. Proposer un circuit électronique composé de portes logiques comportant deux sorties O et D.
% La sortie O laisse passer le courant pour ouvrir la porte. La sortie D laisse passer le courant pour
% détruire la salle.
\end{enumerate}

\end{exercice}
%

  \begin{exercice}[Complément à 2 puissance n]\label{exo::comp2}
    \begin{quote}
      {\itshape
Le monde se sépare en 10 catégories: ceux qui comprennent cette phrase
et les autres.
}
\begin{flushright}
  {\small Zorglub in \og Les aventures de Zorglub et Martine au Far-West\fg{}}
\end{flushright}
    \end{quote}

Nous  allons,  pour  favoriser  la  compréhension  et  simplifier  les
écritures,  travailler  sur 8  bits.  Cela  signifie que  nos  nombres
entiers peuvent être codés avec 8 chiffres égaux à 0 ou 1 en base 2.

\begin{enumerate}

\item Écrivez les nombres de 0 à 17  en base 2. Quel est le plus grand
  nombre que l'on peut écrire avec 8 bits?
  
\item  En fait,  on aimerait  avoir des  entiers signés,  c'est-à-dire
  pouvoir  représenter des  entiers  tant positifs  que négatifs  avec
  cette contrainte.

  On va donc réserver un bit (le plus à gauche) pour indiquer le signe
  du nombre: on mettra un 0 s'il est positif et un 1 s'il est négatif.

  Écrivez en compréhension l'ensemble des  nombres que l'on peut ainsi
  représenter.

\item  Bon,  pas  de  problème...enfin  si  quand  même  un  peu.  Que
  pensez-vous de ces deux nombres:

  \begin{Verbatim}
    00000000 10000000
  \end{Verbatim}

\item On voudrait additionner facilement  ces nombres. Une idée serait
  d'utiliser l'addition  posée comme  à l'école primaire.  Par exemple
  pour calculer $ 5 + 9$

  \begin{Verbatim}
    00000101
+   00001001
------------
    00001110
  \end{Verbatim}

  On trouve bien 14.
  
  et maintenant si on veut calculer $ 5 + (-9)$, qu'est-ce que cela donne avec ce système?

\item  Considérez maintenant  le  nombre \texttt{m  = 11111111}  et
  ajoutez-lui 1  (vous n'avez que  8 bits  à disposition). Que  vaut $
  m+1$? Que cela vous donne-t-il comme idée?

  Considérez \texttt{n=11111110} et calculez $ n+2$.

  Considérez \texttt{n=11111100} et calculez $ n+4$.

  Considérez \texttt{n=11111000} et calculez $ n+8$.

  Considérez \texttt{n=11111010} et calculez $ n+6$.

  Des idées?

\item Si l'on considère que $ 2^8$ vaut 0 sur 8 bits,
que pensez-vous de $x$ et de $2^8-|x|$ si $ x$ est négatif?

Comment s'écrit $2^8-|x|$ sur 8 bits?

Bon, vous commencez à voir ce qui se passe?

Alors expliquez pourquoi ce code:

\begin{ccode}
#include <stdio.h>

int
main(void)
{
  char n = 52 ;
  char deux = 2 ;
  char centquatre = n * deux  ;
  char deuxcenthuit = centquatre * deux ;
  char quatrecentseize = deuxcenthuit * deux ;
  
  printf("104 = %d\n208 = %d\n416 = %d\n", centquatre,deuxcenthuit,quatrecentseize );
  return 0;
}
\end{ccode}

donne:

\begin{ccode}
104 = 104
208 = -48
416 = -96  
\end{ccode}

Généralisez, énoncez votre  norme de représentation des  entiers sur 8
bits,  énoncez un  \og truc\fg{}  pour trouver  facilement de  tête le
complément à $ 2^8$.


\end{enumerate}
  \end{exercice}

%


  \begin{exercice}[8 bits sur Python]

Un entier  en base 16 peut  être introduit en  Python en le faisant  précéder de
\texttt{0x}:

\begin{pythoncode}
In [25]: 0xa1
Out[25]: 161  
\end{pythoncode}

Un entier  en base 2 peut  être introduit en  Python en le faisant  précéder de
\texttt{0b}:

\begin{pythoncode}
In [26]: 0b1101
Out[26]: 13  
\end{pythoncode}


L'opérateur \mintinline{python}{&} entre deux entiers  $a$ et $b$ crée un entier
dont les bits sont positionnées à 1 si, et seulement si, ils sont positionnées à
1 dans $a$ et $b$.


\begin{pythoncode}
In [31]: 0b11 & 0b111000110101
Out[31]: 1

In [32]: 0b11 & 0b111000110111
Out[32]: 3

In [33]: 0b11 & 0b11100011011111011
Out[33]: 3

In [34]: 0b11 & 0b1110001101111101100
Out[34]: 0  
\end{pythoncode}


Imaginez alors un moyen de calculer sur des entiers 8 bits non signés en Python.

Comment faire s'ils sont signés?

  \end{exercice}


%%



\begin{exercice}[Nombre de chiffres]
Trouvez une fonction \texttt{nb\_chiffres} qui renvoie le nombre de
chiffres de l'écriture décimale de $n$.

On pourra utiliser le logarithme décimal:
\begin{pythoncode}
from math import log10  
\end{pythoncode}


\end{exercice}




%%




\begin{exercice}[Décomposition en base quelconque]
Trouvez une fonction \texttt{base(b,n)} qui renvoie la liste des
chiffres de l'écriture normalisée de n en base b avec $1<b<10$.

\begin{pythoncode}
In [1]: base(2,97) 
[1, 1, 0, 0, 0, 0, 1]
\end{pythoncode}
\end{exercice}

%%


\begin{exercice}[Écriture littérale]
  Déterminez une  fonction qui renvoie l'écriture  littérale d'un nombre
 dont l'écriture décimale est comprise entre 1 et 999.
\end{exercice}



%%




\begin{exercice}[Persistance d'un entier]
Un entier naturel $n$ étant donné, on calcule le produit \texttt{prod(n)}
de  ses chiffres  dans  son écriture  en  base 10  puis  le produit  des
chiffres de \texttt{prod(n)} et on recommence ainsi l'application de
\texttt{prod} jusqu'à obtenir  un chiffre entre 0 et  9. Le nombre minimal
de fois  où on applique \texttt{prod}  pour transformer $n$  en un chiffre
entre 0 et 9 est appelé  la \textit{persistance} de $n$. Par exemple, la
persistance  de  9 est  égale  à  0,  celle de  97  est  égale à  3  car
\texttt{prod}$(97)=9\cdot     7=63$,     \texttt{prod}$(63)=6\cdot    3=18$,
\texttt{prod}$(18)=1\cdot 8=8$. et celle  de $\numprint{9575}$ est égale à
5.

On voudrait connaître le plus petit entier naturel de
persistance 5.

\end{exercice}





%%



\begin{exercice}[Critères de divisibilité]

Calculer $x$ modulo $n$ c'est déterminer  le reste de la division euclidienne de
$x$ par $n$. On note par exemple:

$$7\equiv 1 [3] \qquad \text{ ou }\qquad 7\equiv_3 1$$


En  travaillant  modulo  le   bon  entier,  démontrer  les  critères  de
divisibilité usuels par 2, 3, 4, 5, 9, 10 et 11.

On rappelle que l'écriture en base 10 d'un nombre $n$ est définie par la
donnée de l'unique famille $(a_0,a_1,...,a_k)$ vérifiant:

$$n= a_k10^k+a_{k-1}10^{k-1}+\cdots+a_210^2+a_110+a_0$$

avec $a_k\neq 0$ et $0 \leqslant a_1 <10$ pour tout $i\in \bigl\{0,1,..,k\bigr\}$.

\end{exercice}

%%%


\begin{exercice}[Liste des diviseurs]
Trouver une fonction qui calcule la liste des diviseurs
positifs d'un entier naturel donné.
\end{exercice}


%%%

\begin{exercice}[Bibinaire]
 Boby   \textsc{Lapointe},  célèbre   chanteur   français,  était   aussi
mathématicien à ses heures. Ayant  trouvé le code binaire trop compliqué
à utiliser, il inventa le  code... bibinaire. Il suffit de remplacer les
chiffres  par des lettres.  On commence  par couper  le nombre  écrit en
binaire en  paquets de  2.  S'il y  a un  nombre impair de  chiffres, on
rajoute un zéro à gauche, ce qui ne modifie pas la valeur de nombre.  On
commence par le premier
groupe de deux chiffres  le plus à droite. On remplace 00  par O, 01 par
A, 10 par E, 11 par I.\\
Puis on  prend le paquet  de deux chiffres  suivants en se  déplaçant de
droite à gauche. On remplace 00
par H, 01 par B, 10 par K, 11 par D.\\
Pour le paquet suivant, on recommence avec les voyelles. S'il y a encore
un groupe, on remplace par une consonne, etc.




Écrivez  les nombres  de  0 à  25  en bibinaire.   Pourquoi Boby  a-t-il
finement choisi le H~?

Écrivez la table de 3 en bibinaire.


Écrivez les  nombres de  255 à 257  en bibinaire.   Quel est la  base du
bibinaire~? Écrivez 355 en bibinaire.

Écrivez KEKIDI et HEHOBOBI en base 10.

Pourquoi est-il pratique  d'écrire les nombres en base  2 avec un nombre
de chiffres multiple de 4 avant de les traduire en bibinaire~?

Vous pouvez écrire un traducteur bibinaire en Python...
\end{exercice}



\vfill

\eject





\section*{Fonctions, relations}






%


\begin{exercice}[Toutes les Bool]
  Déterminez  toutes les  fonctions qui  prennent deux  booléens en  argument et
  renvoient un booléen.
\end{exercice}











\begin{exercice}[operator]

Python   dispose  d'une   bibliothèque  \texttt{operator}   comprenant
quelques fonctions usuelles.
  

\begin{pythoncode}
In [1]: from operator import add,mul

In [2]: mul(add(2, mul(4, 6)), add(3, 5))
Out[2]: 208
\end{pythoncode}



Comment la machine peut évaluer cette expression?

Il faut savoir comment Python procède.

\begin{pythoncode}
In [9]: def fst(c): return c[0]

In [10]: fst((1,2))
Out[10]: 1

In [11]: fst((1,1/0))
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-11-707229f26363> in <module>()
----> 1 fst((1,1/0))

ZeroDivisionError: division by zero
\end{pythoncode}


Tout le monde ne fait pas pareil. En Haskell:

\haskell

\begin{pythoncode}
Prelude> let fst (a,b) = a
Prelude> fst (1,2)
1
Prelude> fst (1,1/0)
1
\end{pythoncode}

\pythonc

Dresser un arbre d'expression qui traduit l'évalutation de \texttt{ mul(add(2, mul(4, 6)), add(3, 5))}.


\end{exercice}



\begin{exercice}[Signature mystérieuse]

Voici une fonction mystérieuse:

\begin{pythoncode}
def f(n) :
    def g(m) :
        return m*n
    return g
\end{pythoncode}

Analysez cette fonction, déterminez sa signature, comment l'utiliser, donnez des exemples.

  
\end{exercice}




\begin{exercice}[Une première fonction cryptographique]

On considère la fonction définie sur \mintinline{python}{range(10)} par:
\begin{pythoncode}
def f(n) :
    return n + (-1)**n
\end{pythoncode}


\begin{enumerate}
\item   Calculez   \mintinline{python}{f(f(n))}   pour  tout   entier   $n$   de
  \mintinline{python}{range(10)}.
\item Pouvez-vous utiliser cette fonction pour crypter votre code de carte bleue?

\end{enumerate}


  
\end{exercice}



%

\begin{exercice}[Trouver x]



%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{findX}
\end{center}
%\end{figure}



Voici une petite fonction:

\begin{pythoncode}
x = 0

def change_x(val) :
    global x
    print("valeur x avant  : " + str(x))
    print("adresse x avant : " + str(id(x)))
    x = val
    print("valeur x après  : " + str(x))
    print("adresse x après : " + str(id(x)))
\end{pythoncode}

Et quelques-unes de ses exécutions:

\begin{multicols}{2}
\begin{pythoncode}
In [37]: change_x(2)
valeur x avant  : 0
adresse x avant : 10771488
valeur x après  : 2
adresse x après : 10771552

In [38]: change_x(2)
valeur x avant  : 2
adresse x avant : 10771552
valeur x après  : 2
adresse x après : 10771552

In [39]: change_x('a')
valeur x avant  : 2
adresse x avant : 10771552
valeur x après  : a
adresse x après : 139992609175120

In [40]: type(change_x)
Out[40]: function

In [41]: type(change_x(2))
valeur x avant  : a
adresse x avant : 139992609175120
valeur x après  : 2
adresse x après : 10771552
Out[41]: NoneType

In [42]: change_x(change_x(2))
valeur x avant  : 2
adresse x avant : 10771552
valeur x après  : 2
adresse x après : 10771552
valeur x avant  : 2
adresse x avant : 10771552
valeur x après  : None
adresse x après : 10288288

In [43]: print(change_x(2))
valeur x avant  : None
adresse x avant : 10288288
valeur x après  : 2
adresse x après : 10771552
None  
\end{pythoncode}
\end{multicols}

Commentez...


\end{exercice}


%



\begin{exercice}[Traquez les impures]

  \begin{multicols}{2}
    
%\begin{figure}
%\begin{center}
  \includegraphics[height=4.5cm]{valid}
%\end{center}
%\end{figure}


%\begin{figure}
%\begin{center}
  \includegraphics[height=4.5cm]{invalid}
%\end{center}
%\end{figure}

  \end{multicols}


Nous avons déjà trouvé la fonction impure \mintinline{python}{print}. 
Traquez d'autres fonctions impures se cachant dans Python...

\end{exercice}



%


\begin{exercice}[Approximation affine d'une fonction numérique]
  
Vous vous souvenez que $f'(x)=\displaystyle\lim_{dx\to 0}\frac{f(x+dx)-f(x)}{dx}$.

On  peut   donc  considérer   que  pour   $dx$  \og   petit\fg{},  $f'(x)\approx
\frac{f(x+dx)-f(x)}{dx}$.

Déterminez une fonction qui a comme paramètres  une fonction à dériver et un pas
$dx$ et qui renvoie l'approximation de la fonction dérivée.

Testez  sur plusieurs  exemples de  fonctions que  vous connaissez  bien, faites
varier aussi le pas. Commentaires?





\end{exercice}





%

\begin{exercice}[Composée $n$ fois]

Déterminez une fonction qui renvoie la composée itérée d'une fonction donnée en argument.
  
\end{exercice}

%

\begin{exercice}[Moyenne olympique]
 Décrire une fonction qui étant donnés quatre flottants leur associe la moyenne
  des deux  nombres parmi les  quatre qui ne  sont ni le  plus grand ni  le plus
  petit. Par exemple, la moyenne olympique de 10, 8, 12 et 14 est 11 et celle de
  12, 12, 12 et 12 est 12. Généraliser.
  
\end{exercice}


%

\begin{exercice}[Curryfication]

Vous n'avez travaillé  le plus souvent qu'avec des fonctions  d'une variable. Or
la multiplication est en fait une fonction de deux variables:

\begin{pythoncode}
def mul(x,y) :
    return x * y
\end{pythoncode}

On peut fabriquer une fonction qui multiplie un nombre par $2$:

\begin{pythoncode}
def mul_2(n) :
    return 2 * n 
\end{pythoncode}


On peut fabriquer une fonction qui multiplie un nombre par $3$:

\begin{pythoncode}
def mul_3(n) :
    return 3 * n 
\end{pythoncode}


On peut fabriquer une fonction plus générale qui renvoie ces fonctions, pour 2, 3 ou n'importe quel autre nombre:

\begin{pythoncode}
def mul_curry(k) :
    return lambda n : k * n  
\end{pythoncode}

Ainsi \mintinline{python}{mul(3) == mul_3} 

Alors \mintinline{python}{mul(x,y) = mul_curry(x)(y)}

Dessinez des flèches pour illustrer cela.

Fabriquer une fonction \mintinline{python}{curry}  telle que \mintinline{python}{curry(mul) == mul_curry} 

Dessinez les flèches correspondantes. Pensez types.
 





\end{exercice}


%

\begin{exercice}[filtres]
 Créez une fonction \mintinline{python}{filtre} 
qui prend une liste en argument et un prédicat et renvoie les éléments de la liste qui vérifient le prédicat.

 Créez une fonction \mintinline{python}{prend_tant_que} 
qui prend une liste en argument et un prédicat et renvoie les premiers éléments de la liste qui vérifient le prédicat et s'arrête au premier échec.

 Créez une fonction \mintinline{python}{partition} 
qui prend une liste en argument et un prédicat et renvoie deux listes: l'une qui
contient les  éléments qui vérifient le  prédicat et une autre  qui contient les
autres.

 
\end{exercice}


%




\begin{exercice}
  
On se propose de d\'{e}montrer que tous les \'{e}tudiants d'\textsc{Iut}
ont le m\^{e}me \^{a}ge et, pour cela, on note $P\left( n\right) $
l'affirmation%



\og \textit{si \ on choisit $n$ \'{e}tudiants  $\left( n\in \mathbb{N}%
^{\ast }\right) $, il est s\^{u}r qu'ils ont tous le m\^{e}me \^{a}ge}\fg{}%



Il est clair que $P\left( 1\right) $ est vraie. 

D\'{e}montrons que $P\left(
n\right) \limp P\left( n+1\right)$. Pour cela nous supposons que $%
P\left( n\right) $ est vraie (c'est l'hypoth\`{e}se de r\'{e}currence) et
nous choisissons un groupe quelconque de $n+1$ \'{e}tudiants que nous
ordonnons par ordre alphab\'{e}tique (pourquoi pas). D'apr\`{e}s l'hypoth%
\`{e}se de r\'{e}currence, les $n$ premiers de l'ordre alphab\'{e}tique ont
tous le m\^{e}me \^{a}ge ainsi que les $n$ derniers. Comme ces deux groupes
de $n$ \'{e}tudiants ont au moins un \'{e}tudiant en commun, on en d\'{e}%
duit qu'ils ont tous le m\^{e}me \^{a}ge.%

Nous venons de d\'{e}montrer que $P\left( n\right) \limp P\left(
n+1\right) $ pour tout $n\geq 1$ et, comme $P\left( 1\right) $ est vrai, $%
P\left(  n\right) $  est toujours  vrai pour  tout $n\geqslant  1.$ \textbf{Y
  a-t-il une erreur dans le raisonnement ?}
\end{exercice}



\begin{exercice}[Javanais for dummies]
On va simplifier le javanais habituel  sans tenir compte de la découpe
selon les syllabes.
On  introduit  les lettres  \og  av\fg{}  devant la  première  voyelle
rencontrée dans le mot en partant de la gauche.
Créez une foncton \texttt{javanais(mot)}:

\begin{pythoncode}
>>> javanais("chrome")
"chravome"

>>> javanais("air")
"avair"
\end{pythoncode}
  
\end{exercice}





\begin{exercice}[CCP MP 2015]
{\itshape Non, non, ce n'est pas un extrait d'un livre de seconde, c'est un sujet 0
proposé pour l'épreuve de Math du concours CCP...}
  \begin{enumerate}
  \item Écrire une fonction factorielle qui  prend en argument un entier naturel
    $ n$ et renvoie $ n!$ (on n'accepetra pas bien sûr de réponse utilisant la
    propre fonction factorielle du module math de Python ou Scilab).
  \item Écrire une fonction  \lstinline{seuil} qui prend en argument un  entier $ M$ et renvoie
    le plus petit entier naturel $ n$ tel que $ n!>M$.
  \item Écrire une fonction booléenne nommée \lstinline{est_divisible}, qui pend
    en argument un entier naturel $ n$  et renvoie \lstinline{True} si $ n!$ est
    divisible par $ n+1$ et \lstinline{False} sinon.
  \item On considère la fonction suivante nommée \lstinline{mystere}:
    \begin{pythoncode}
def mystere(n):
    s = 0
    for k in range(1,n+1):
        s = s + factorielle(k)
    return s
    \end{pythoncode}
    \begin{enumerate}
    \item Quelle valeur renvoie \lstinline{mystere(4)}?
    \item Déterminer    le     nombre    de    multiplications    qu'effectue
      \lstinline{mystere(n)}.
    \item Proposer une amélioration du script de la fonction \lstinline{mystere}
      afin d'obtenir une complexité linéaire.
    \end{enumerate}
  \end{enumerate}
\end{exercice}





\vfill

\eject



\begin{exercice}[Ils ont osé: écrit Maths II CCP MP 2015]

\begin{enumerate}

\item Donnez la décomposition en binaire (base 2) de l'entier 21.

On considère la fonction \texttt{mystere} suivante:

\begin{pythoncode}
def mystere(n, b) :
    """Données : n > 0 un entier et b > 0 un entier
       Résultat : ......."""
    t = [] # tableau vide
    while n > 0 :
        c = n % b
        t.append(c)
        n = n // b
    return t
\end{pythoncode}

On  rappelle  que la  méthode  \texttt{append}  rajoute  un  élément en  fin  de
liste. Si  l'on choisit  par exemple  \texttt{t =  [4,5,6]}, alors,  après avoir
exécuté    \mintinline{python}{t.append(12)},   la    liste   a    pour   valeur
\texttt{[4,5,6,12]}.

Pour $k\in\bbn^\star$, on note $c_k$, $t_k$  et $n_k$ les valeurs prises par les
variables  \texttt{c},  \texttt{t} et  \texttt{n}  à  la  sortie de  la  $k$-ème
itération de la boucle \og while\fg{}.
\item     Quelle     est     la    valeur     renvoyée     lorsqu'on     exécute
  \mintinline{python}{mystere(256,10)} ?

On  recopiera  et  complètera  le  tableau suivant  en  rajoutant  les  colonnes
nécessaires pour tracer entièrement l'exécution:

\begin{tabular}[h]{|c|c|c|c}
\hline
  $k$&1&1&$\cdots$\\
\hline
$c_k$&&&$\cdots$\\
\hline
$t_k$&&&$\cdots$\\
\hline
$n_k$&&&$\cdots$\\
\hline
\end{tabular}

\item Soit  $n>0$ un  entier. On exécute  \mintinline{python}{mystere(n,10)}. On
  pose $n_0=n$.
  \begin{enumerate}
  \item Justifier la terminaison de la boucle \mintinline{python}{while}. 
  \item   On  ote   $p$  le   nombre   d'itérations  lors   de  l'exécution   de
    \mintinline{python}{mystere(n, 10)}. Justifiez que pour tout $k\in\llbracket
    0,  p\rrbracket$,  on  a  $n_k \leqslant  \frac{n}{10^k}$.  Déduisez-en  une
    majoration de $p$ en fonction de $n$.


  \end{enumerate}
\item En vous aidant du script de la fonction \mintinline{python}{mystere},
  écrivez  une   fonction  \mintinline{mpython}{somme_chiffres}  qui   prend  en
  argument un entier  naturel et renvoie la somme de  ses chiffres. Par exemple,
  \mintinline{python}{somme_chiffres(256)} devra renvoyer 13.
\item     Écrivez      une     version     récursive     de      la     fonction
  \mintinline{python}{somme_chiffres} que vous nommerez \mintinline{python}{somme_rec}. 





  \end{enumerate}
\end{exercice}


\begin{exercice}[lambda]
  Calculez, écrivez sans $λ$ mais avec $↦$ et traduisez en Python:
  \begin{multicols}{3}
    \begin{enumerate}
    \item $(λx\cdot(x+y))(2)$
    \item $(λx\cdot(x+y))(2y)$
    \item $(λx\cdot(λy\cdot(x+y))(3))(2)$
    \item $(λx\cdot(λy\cdot(x+y))(a))(b)$
    \item $(λx\cdot 4)(2)$
    \end{enumerate}
  \end{multicols}
\end{exercice}

\begin{exercice}[Composition]
Soit                                  $f=\bigl\{(1,c),(2,a),(3,b),(4,c)\bigr\}$,
$g=\bigl\{(a,2),(b,1),(c,4)\bigr\}$                                           et
$h=\bigl\{(1,A),(2,B),(3,D),(4,D)\bigr\}$.

Calculez, si c'est possible, $g\circ f$, $f\circ g$, $h\circ(g\circ f)$, $h\circ
g$ et $(h\circ g)\circ f$.

Déterminez $$
\end{exercice}


\begin{exercice}[fonction injective, surjective]
Déterminez si les fonctions suivantes sont injectives, surjectives, bijectives:
\begin{multicols}{2}
  \begin{enumerate}
  \item $f:\bbn → \bbn$, $x ↦ x^2+2$
  \item $f:\bbn → \bbn$, $x↦ x \text{ mod } 3$
  \item $f:\bbn → \bbn$, $x↦
    \begin{cases}
      1 \text{ si } x \text{ est pair}\\
      0\text{ sinon}
    \end{cases}
$
 \item $f:\bbn → \bigl\{0,1\bigr\}$, $x↦
    \begin{cases}
      1 \text{ si } x \text{ est pair}\\
      0\text{ sinon}
    \end{cases}
$

\item $f:\bbn ⊗\bbn → \bbn$, $f(x,y)=x+y$

  \end{enumerate}
\end{multicols}

\end{exercice}


















\begin{exercice}[Exponentiation]
  \begin{enumerate}
  \item Voici une définition très classique de la puissance entière d'un entier:
    $ x^0=1$ et $ x^n=x×x^{n-1}$

Cela donne:

\begin{pythoncode}
def pow1(a, n) :
    assert n >= 0, "L'exposant doit être entier naturel"
    if n == 0 :
        return 1
    else :
        return a * pow1(a, n - 1)
\end{pythoncode}

Démontrez  alors   que  pour  tous  entiers   naturels  $  x$,  $n$   et  $  m$,
\mintinline{python}{pow1(x, n + m) == pow1(x, n) * pow1(x,m)}

Attention, il y a une petite subtilité...

\item      Démontrez     ensuite,      toujours      par     induction,      que
  \mintinline{python}{pow1(x, n) * pow1(x, n) == pow1(x*x, n)}. 


\item Mais il y  a mieux à faire en remarquant que, quand  n est pair, $x^n=(x ×
  x)^{n/2}$:  quel est  l'intérêt, algorithmiquement  parlant? Comment  en tirer
  parti?

  Vous  pourrez avoir  besoin de  l'opérateur \lstinline{//}  qui retourne  le
  quotient de la division euclidienne de deux entiers.

  Vous noterez par exemple \lstinline{pow2} cet nouvelle fonction.


Souvenez-vous de  vos cours de  6\up{eme}. Effectuer la division  euclidienne de
deux entiers $ a$ et $ b$, $ b$ étant non nul, c'est déterminer les entiers $ q$
et $ r$ tels que:

$$a = b×q+r\qquad{0 \leqslant r < |b| } $$

Comparez le  nombre d'étapes  nécessaires pour calculer  $3^{25}$ avec  l'une et
l'autre méthode.  Nous essaierons  de généraliser tout  à l'heure  mais revenons
d'abord à nos moutons.

\item Il  s'agit maintenant  de démontrer que  les fonctions  \lstinline{pow1} et
  \lstinline{pow2} sont équivalentes.

Le cas $ n$ impair est assez direct. Pour le cas pair, il y a plus de travail...

\item Moralité?  Parmi ces  deux codes, un  est simple à  lire et  peu efficace,
  l'autre est compliqué à lire et efficace: faut-il malgré tout jeter le premier
  à la poubelle?

\item  Peut-on avoir  un ordre  de grandeur  du nombre  d'étapes nécessaires  au
  calcul  de $  x^n$?  Cela peut  avoir une  importance  capitale, notamment  en
  cryptographie  où on  calcule régulièrement  des  entiers à  la puissance  des
  nombres d'une centaine de chiffres.

  Faisons  pour   cela  un  petit   rappel  sur  une  fonction   primordiale  en
  informatique.  Nous  voudrions  savoir  combien de  bits  sont  nécessaires  à
  l'écriture d'un entier et combien de bits sont égaux à 1...Menez l'enquête.  Peut-être aurez-vous besoin
  d'introduire le logarithme de base 2:

$$\log_2(x)=\frac{\ln x}{\ln 2} $$




  \end{enumerate}
\end{exercice}





\begin{exercice}[Fabriquons la multiplication]
 
On a  défini l'exponentiation comme itération  de la multiplication. On  peut de
même définir la multiplication comme itération de l'addition:



\begin{pythoncode}
def mul1(a, b) :
    if b < 0 :
        return -mul1(a, -b)
    if b == 0 :
        return 0
    return a + mul1(a, b - 1)
\end{pythoncode}


Combien       faut-il      effectuer       d'opérations      pour       calculer
\mintinline{python}{mul1(a,b)} ?

On  dispose  de  deux  opérations  élémentaires sur  les  chaînes  de  bits  qui
permettent de doubler ou  de couper en 2 un nombre en décalant  d'un bit vers la
droite ou la gauche:

\begin{pythoncode}
def double(n) :
    return n << 1

def demi(n) :
    return n >> 1  
\end{pythoncode}



Déterminez alors une multiplication plus efficace  en vous inspirant de ce qui a
été fait pour l'exponentiation.


Démontrez que votre nouvelle fonction calcule effectivement le produit de ses arguments.

Donnez des processus récursifs et itératifs.

\end{exercice}






\begin{exercice}[Nombres premiers]
 
\subsubsection{Définition}
Quoi de plus simple qu'un nombre premier :


\setindent{\indentationcours}
\begin{definitions}
 Un entier naturel  est dit premier s'il est  supérieur ( i.e. supérieur
 ou égal ) à 2 et n'est 
divisible que par 1 et lui-même. 
\end{definitions}
\setindent{0cm}

et pourtant, ils renferment tant de mystères que les plus grands esprits depuis 
des siècles n'ont toujours pas réussi à en percer tous
les secrets et ce malgré les énormes progrès technologiques et les  
investissements colossaux consentis par les pouvoirs tant civils que
militaires pour assurer ou percer la confidentialité des transmissions de toutes 
natures qui continuent de dépendre d'une meilleure
connaissance des nombres premiers, ce que nous verrons un peu plus loin. Qui 
sont-ils ? Combien sont-ils ? Où sont-ils ? À quoi
servent-ils ? Nous essaierons de donner quelques éléments de réponses à ces 
questions.


Mais tout d'abord, pourquoi jouent-ils un rôle si important ? Fondamentalement, 
il existe deux manières d'engendrer $\bbn$ : 
\begin{itemize}
\item si on veut engendrer $\bbn$ en utilisant l'addition, on s'aperçoit que le nombre 1 nous suffit : on <<~fabrique~>> 2  en additionnant 1 avec lui-même; 3 en additionnant 1 avec
2, etc.
\item si on veut engendrer $\bbn$ en utilisant la multiplication, là, les choses se compliquent. Pour <<~fabriquer~>> 2, il 
faut le créer; même problème pour  3. On fabrique  4 en multipliant  2
avec lui-même, mais il faut créer 5. On fabrique  6 en multipliant 3 avec 2. On crée 7. On fabrique 8 à partir de 2. On fabrique 9 à partir de 3. On fabrique 10 à partir de 2 et 5, etc.

 Les 
nombres que l'on est obligés de créer sont les briques nécessaires à
fabriquer tous les autres. C'est bien plus compliqué que l'addition me 
direz-vous, mais la multiplication est plus <<~puissante~>> et
nous permet d'aller bien plus vite et plus loin. 
\end{itemize}

\sm

Les nombres premiers sont donc ces éléments qui nous permettent de fabriquer tous 
les autres. Un des premiers problèmes étudiés à été de
savoir s'ils peuvent tenir dans une boîte. 
Euclide à répondu à cette question il y a vingt-trois siècles
et la réponse est non.

Pour le prouver, nous aurons besoin d'un résultat intermédiaire:

\setindent{\indentationcours}
\begin{theoreme}\label{infinite}
  Tout entier naturel admet au moins un diviseur premier.
\end{theoreme}
\setindent{0cm}



Si ce nombre, appelons-le $n$, est premier, tout va bien.

Sinon, l'ensemble de ses diviseurs étant non vide ( $n$ est dedans ) et borné ( 
par 1 et lui-même), il admet un plus petit élément $p\neq 1$.
Ce nombre n'est pas divisible par un autre, sinon ce nombre plus petit que $p$ 
divisant $p$ diviserait $n$ et alors $p$ ne serait plus le
plus petit diviseur de $n$. Le nombre $p$ est donc premier et voilà.

\setindent{\indentationcours}
\begin{theoreme}
  Il y a une infinité de nombres premiers.
\end{theoreme}
\setindent{0cm}




 \emph{Raisonnons par l'absurde} et 
supposons qu'il existe exactement $n$ nombres premiers qu'on
nommera $p_1$, $p_2,\cdots,\ p_n$ et appelons $N$ le nombre  \[N=p_1p_2\cdots 
p_n+1\]
%\footnote{Ce style de nombre réapparaîtra souvent}. 
Il
est plus grand que tous les $p_i$, donc il n'est pas premier d'après notre 
hypothèse, donc il admet un diviseur  premier $p$ qui est donc
un des $p_i$, puisqu'il n'y a qu'eux. Soit $i_0$ tel que $p=p_{i_0}$. Alors $p$ 
divise $p_1p_2\cdots p_n$. Or il divise $N$, donc il
divise leur différence $N-p_1p_2\cdots p_n$, c'est à dire 1, donc $p=1$ ce qui 
est absurde puisqu'il est premier. Ainsi, il n'existe pas
de plus grand nombre premier.


\sm


Il y en a donc une infinité et l'aventure ne fait que commencer. 



\subsubsection{Comment vérifier qu'un nombre est premier?} 


\paragraph*{Force brute}

Créez une fonction \lstinline{divise k n} qui teste si l'entier $ k$ divise $ n$.

\begin{pythoncode}
In [70]: divise(7,63)
Out[70]: True
\end{pythoncode}

Créez une fonction \lstinline{les_diviseurs :: Int -> [Int]} qui renvoie l'ensemble
des diviseurs de $n$. On pourra utiliser la méthode \mintinline{python}{extend}: 


\begin{pythoncode}
In [71]: les_diviseurs(100)
Out[71]: {1, 2, 4, 5, 20, 25, 50, 100}
\end{pythoncode}

Déduisez-en un test \lstinline{est_premier :: Int -> Bool}

\begin{pythoncode}
In [77]: est_premier(2**10 - 1)
Out[77]: False
\end{pythoncode}


On peut alors créer une fonction \lstinline{find}:


\begin{lstlisting}
find :: (a -> Bool) -> [a] ->  a	
The find function takes a predicate and a list and returns the first element in the list matching the predicate, or None if there is no such element.
\end{lstlisting}

pour déterminer  une fonction \lstinline{prochainPremier} qui  calcule le nombre
premier qui suit l'argument:

\begin{pythoncode}
In [81]: prochain_premier(2**10 - 1)
Out[81]: 1031
\end{pythoncode}


Cependant,  l'efficacité de  cette fonction  laisse à  désirer...Comment peut-on
améliorer \lstinline{les_diviseurs}?

Mais si on ne cherche que les nombres premiers, a-t-on besoin de tous les diviseurs?


\paragraph*{Étudions le problème pour être plus efficaces}


 Observons les diviseurs de 1321 par exemple: si aucune des 1319 divisions ne 
<<~tombe juste~>>, alors on pourra dire que 1321 premier.
Et puis d'abord, il est impair, il ne semble pas être divisible par 3, alors 
pourquoi pas...



\begin{center}
\footnotesize{ {\setlength{\tabcolsep}{0.1cm}
\begin{tabular}{IcIccccccccccccI}
\whline
 diviseur& 2& 3& 4& 5& 6&  7&8&9&10&11&12&13\\ \hline
  quotient&660,5&440,3&330,3&264,2
&220,2&188,7&165,1&146,8&132,1& 120,1& 110,1&101,6\\ \whline
 diviseur &14&15&16&17&18&19&20&21&22&23&24&25\\ \hline
quotient &94,36&88,07&82,56&77,71&73,39&69,53 &66,05&62,90&60,05&57,43
&55,04&52,84\\ \whline diviseur&26&27&28&29&30&31&32&33&34&35&36&37 \\ \hline
  quotient&50,81&48,93&47,18& 45,55& 44,03&42,61&41,28&40,03&38,85&37,74 &36,69& 
35,70\\ \whline

\end{tabular}}
}
\end{center}


Le tableau est incomplet: il reste encore à essayer les quotients de 38 à 1320, 
mais cela aurait été mauvais pour la planète.


 Tout d'abord,  nous n'avons pas trouvé  de quotient entier  en ce début
 d'enquête.  
Nous observons de plus que si la suite des diviseurs
 est  croissante,  celle  des  quotients  est  décroissante.  Vous  avez
 sûrement remarqué qu'à partir de 37, 
 les  quotients sont  inférieurs aux  diviseurs donc  nous  pouvons nous
 arrêter là: 
si pour un diviseur supérieur à 37, on trouvait un
 quotient entier $q$, alors en  divisant 1321 par $q$, qui est inférieur
 à 37, on devrait se trouver au début de notre liste de diviseurs et 
  ce diviseur serait entier. Le problème, c'est qu'aucune division par un 
entier inférieur à 37 n'a donné de quotient entier donc on
  peut s'épargner les 1283 divisions restantes.


\bigskip

  Mine de rien, nous venons de franchir un grand pas dans la théorie des
  nombres: pour tester si l'entier 1321 est premier, il nous a
  suffit  d'effectuer 36 divisions\footnote{Et  encore, nous  aurions pu
    faire mieux 
comme nous allons le voir tout de suite après.}. Deux
  problèmes se posent maintenant: pourquoi 36 et pouvons-nous généraliser ce 
résultat aux autres entiers? 

Un petit Joker : $\sqrt{1321}\simeq 36,3$...

Reprenons la  propriété \vref{infinite}. Tout naturel $n$  admet un plus
petit diviseur $p$ 
qui est premier. \'Ecartons le cas où $n$ est premier et
donnons un nom aux nombres qui restent :

\setindent{\indentationcours}
\begin{definition}
  Un entier naturel \emph{autre que 1} qui n'est pas premier est dit 
\textbf{composé}.
\end{definition}
\setindent{0cm}



L'entier $n$ étant  composé, il s'écrit donc $n=pq$,  avec $q$ un entier
supérieur 
à $p$ (car $p$ est le plus petit diviseur). Ainsi $$
p \leqslant q\ \text{ et donc }\ p^2 \leqslant  pq=n\ \text{ c'est à dire }\
p \leqslant \sqrt{n}$$ 

Nous pouvons donc généraliser l'observation précédente

\setindent{\indentationcours}
\begin{theoreme}
  Si un entier est composé, alors il admet un diviseur premier 
inférieur à sa racine carrée.
\end{theoreme}
\setindent{0cm}

Inspirez-vous de ce résultat pour encore améliorer les fonctions précédentes.

Vous  pourrez fabriquer  par  exemple une  fonction qui  renvoie  le plus  petit
diviseur d'un nombre (autre que 1 bien sûr):

\begin{pythoncode}
In [100]: ppd(2**59-1)
Out[100]: 179951  
\end{pythoncode}



Par  exemple, il  faut 3  secondes pour  déterminer le  nombre premier  qui suit
$2^{50}$:


\begin{pythoncode}
In [92]: %timeit prochain_premier(2**50)
1 loops, best of 3: 3.45 s per loop  
\end{pythoncode}



Vous pouvez  ensuite vous lancer dans  l'écriture d'une fonction qui  renvoie la
décomposition  d'un entier  en produit  de  facteurs premiers  sachant que  nous
admettrons le  théorème suivant (mais rien  ne vous empêche de  vous lancer dans
une démonstration...):

\setindent{\indentationcours}
\begin{theoreme}
  Tout entier $n$ supérieur à 2 admet une et une seule (à l'ordre près 
des termes) décomposition en produit fini de nombres
premiers
\end{theoreme}
\setindent{0cm}



\end{exercice}








\begin{exercice}[Test de Fermat]
Pour  nos  calculs en  cryptographie,  nous  aurons  besoin de  calculer
$a^{p-1}(\modu p)$ avec $a$ ou $p$ des \og grands\fg{} nombres entiers.

Par      exemple,     que      vaut     $97^{p-1}(\modu      p)$     avec
$p=2^{400}$?...

Cela  risque  de  prendre pas  mal  de  temps  si nous  calculons  cette
puissance naïvement.

Déterminez une fonction \mintinline{python}{pow_mod} qui calcule $a^p\mod n$.

\begin{pythoncode}
In [123]: pow_mod(97, 2**400-1, 2**400-1)
Out[123]: 21481264948376355149171821073476653538493776296448586677799897673484
29080159664570727704067023680946885559654463293277443
\end{pythoncode}



Nous avons mis au point 
une méthode 
permettant de tester si un entier est premier ou non. Cela
marche assez bien pour des petits nombres, mais cette méthode devient 
impraticable s'il s'agit de tester un entier d'une centaine de
chiffres. 

Nous avons besoin  d'un dernier résultat:  le fameux \og petit
théorème de \textsc{Fermat}\fg{}.S'il est qualifié de petit, c'est qu'une
conjecture célèbre du même Fermat, restée indémontrée pendant des siècles, s'est 
accaparée le titre de \textit{Grand Théorème de \textsc{Fermat}}.
$$ x^n+y^n=z^n\quad \text{n'a pas de solution dans }\bbn^3\quad\text{pour } n>2$$
Dans la marge d'un manuscrit, \textsc{Fermat} prétendait en avoir trouvé la démonstration 
mais manquer de place pour l'écrire. Il a pourtant fallu
attendre 1994 pour qu'Andrew \textsc{Wiles} le démontre en utilisant des
outils 
surpuissants: l'entêtement d'une multitude de chercheurs a abouti
à la démonstration de ce théorème, mais surtout a permis de développer 
d'importants outils en cryptographie donc en sécurité informatique.

Voici celui qui nous sera utile qui n'est en fait qu'une conséquence du théorème d'\textsc{Euler}...

\setindent{\indentationcours}
\begin{theoreme}[Petit théorème de \textsc{Fermat}]
Si $p$ est premier, $a^p\equiv a (\modu p)$ (ie $a^p-a$ est un multiple de $p$). 
\end{theoreme}
\setindent{0mm}


Comment  interpréter  alors  le  résultat   donné  par  python  juste  au-dessus
concernant $2^{400}1$?


Créez  une  fonction \mintinline{python}{test_f}  qui  teste  si un  nombre  $a$
vérifie $a^p=a\mod p$.


Que peut-on dire d'un  nombre $p$ qui ne passe pas ce test?  Et s'il le passe?


On va donc faire des  tests aléatoires en utilisant \mintinline{python}{randint}
qui renvoie  un entier  aléatoirement choisi  entre deux
entiers selon une distribution uniforme.

Pourquoi avoir précisé \mintinline{python}{randint(11,min(n, 2**63 - 1))}? 



\begin{pythoncode}
from numpy.random import randint

def test_fermat_alea(n) :
    a = randint(11,min(n, 2**63 - 1))
    return test_f(a,n)  
\end{pythoncode}


Créez alors une fonction qui teste si un nombre est probablement premier.


\begin{pythoncode}
In [145]: proba_premier(2**3217 - 1, 100)
Out[145]: True

In [146]: proba_premier(2**4423 - 1, 100)
Out[146]: True

In [147]: proba_premier((2**3217 - 1) * (2**4423 - 1), 10)
Out[147]: False  
\end{pythoncode}





\end{exercice}







\begin{exercice}[Recherches séquentielles et par saut]
Un fichier séquentiel informatisé est schématiquement constitu%
é ainsi, chaque fiche contient


\begin{itemize}
\item \textit{L'adresse }$S$\textit{\ de la fiche suivante si elle existe
sinon }$\func{nil}$\textit{\ pour indiquer la fin du fichier.}

\item \textit{L'adresse }$P$\textit{\ de la fiche précédente si elle
existe sinon }$\func{nil}$\textit{\ pour indiquer qu'il n'y a rien en de\c{c}%
à.}

\item \textit{Une donnée }$D_{i}$\textit{\ alphanumérique}

\item \textit{Une première adresse }$\mathbf{d\acute{e}but}$\textit{\
qui est l'adresse de la première fiche.}
\end{itemize}

Nous supposerons que le fichier est trié suivant l'ordre croissant et
pour simplifier l'étude nous poserons $D_{i}=i$\ (la donnée est é%
gale au numéro de la fiche). Le fichier contient $N$\ fiches. Nous
appellerons temps d'accès à la fiche numéro $i$\ le nombre de
fiches lues en partant de $d\acute{e}but$\ pour arriver à la fiche $i$\
y compris la fiche $i.$\ Ainsi le temps d'accès à la fiche 1 est 1.

\textbf{Recherche séquentielle.}

Pour trouver la fiche $i$\ ($1\leq i\leq N)$\ on part de $d\acute{e}but,$\
on lit les fiches dans l'ordre des numéros jusqu'à obtenir la fiche $%
i.$%
% \[
% \FRAME{itbpF}{10.2846cm}{2.1703cm}{0cm}{}{}{ftp2.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 10.2846cm;height 2.1703cm;depth
% 0cm;original-width 10.1594cm;original-height 2.089cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/FTP2.wmf';file-properties "XNPEU";}} 
% \]

Si on cherche successivement les fiches 1,2,3,$\cdots ,N$\ en repartant de $d%
\acute{e}but$\ à chaque fois, quel est le temps moyen d'accès à
une fiche ?

\textbf{Recherche par saut.}

\begin{itemize}
\item \textit{Nous supposerons ici que }$N$\textit{\ est le carré d'un
entier, }$N=a^{2}$\textit{\ (}$a\in N^{\ast }).$\textit{\ Soit }$k$\textit{\
un entier divisant }$N$\textit{\ et supérieur à 1, }$N=kj$\textit{.}

\item \textit{Nous créons un autre fichier dit de n\oe uds }$%
N_{1},N_{2},\ldots ,N_{j}.$

\item \textit{Le départ, noté }\textbf{dép}$,$\textit{\ contient
l'adresse du premier n\oe ud.}

\item \textit{Le premier n\oe ud contient l'adresse de la fiche numéro }$%
k,$\textit{\ la donnée de la fiche numéro }$k$\textit{\ l'adresse
du n\oe ud suivant et l'adresse de la fiche $k-1$.}

\item \textit{Le deuxième n\oe ud contient l'adresse de la fiche numé%
ro }$2k,$\textit{\ la donnée de la fiche numéro 2}$k$\textit{\ 
l'adresse du n\oe ud suivant et de la fiche numéro $2k-1$.}

\item ${\ldots \ldots }$

\item \textit{Le dernier n\oe ud (le }$j^{\grave{e}me})$\textit{\ contient
l'adresse de la fiche numéro }$N,$ et celle de $N-1$, \textit{\ la donnée de la fiche num%
éro }$N$\textit{\ et }$\func{nil}.$%
% \[
% \FRAME{itbpF}{14.3769cm}{4.4482cm}{0cm}{}{}{ftp3.wmf}{\special{language
% "Scientific Word";type "GRAPHIC";maintain-aspect-ratio TRUE;display
% "USEDEF";valid_file "F";width 14.3769cm;height 4.4482cm;depth
% 0cm;original-width 14.2297cm;original-height 4.3515cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/FTP3.wmf';file-properties "XNPEU";}} 
% \]
\end{itemize}

Pour chercher une fiche $i$\ on part de \textbf{dép}, on passe au
premier n\oe ud et on regarde la donnée $\alpha $\ portée par le n%
\oe ud. Si $\alpha <i$\ on passe au n\oe ud suivant, sinon on passe à la
fiche indiquée par le n\oe ud et, si nécessaire, on revient en arri%
ère dans le fichier jusqu'à atteindre la fiche $i.$\ Un temps d'acc%
ès à une fiche sera le nombre de n\oe uds parcourus $+$\ le nombre
de fiches parcourues y compris celle cherchée.

Si on cherche successivement les fiches 1,2,3,$\cdots ,N$\ en repartant de 
\textbf{dép} à chaque fois, on se propose de déterminer le temps
moyen d'accès à une fiche et trouver la valeur de $k$\ qui minimise
ce temps moyen.

\begin{enumerate}
\item Relier la recherche par saut avec la \vref{exo::saut}

\item Déterminer le temps d'accès à la fiche $1$.

\item Déterminer le temps d'accès à la fiche $2$ (si $k>2).$

\item Déterminer le temps d'accès à la fiche $k$.

\item Déterminer le temps d'accès à la fiche $k-1$.

\item Déterminer le temps d'accès à la fiche $k+1.$

\item Déterminer le temps d'accès à la fiche $ik.$

\item Déterminer le temps d'accès à la fiche $N.$

\item Déterminer le temps d'accès à la fiche $j.$

\item Déterminer le temps total d'accès aux fiches du $i^{\grave{e}%
me}$\ paquet.

\item Déterminer le temps total d'accès à toutes les fiches.

\item Déterminer le temps moyen d'accès à une fiche en fonction
de $k$\ et de $N.$

\item Déterminer la valeur de $k$\ qui minimise ce temps moyen.

\item Comparer le temps moyen d'accès à une fiche par une recherche s%
équentielle et une recherche par saut en prenant $N=$\ 10 000 et une unit%
é de temps égale à $10^{-2}s.$
\end{enumerate}


\end{exercice}









\begin{exercice}[Schéma de Horner-Ruffini-Holdred-Newton-Al-Tusi-Liu-Hui...]


%\subsection*{Un peu d'histoire...}



%\end{minipage}

La  méthode que nous  allons voir  porte le  nom du  britannique William
George  \textsc{Horner} (1786  - 1837)  mais  en fait  elle fut  publiée
presque  10  ans  auparavant  par  un  horloger  londonien,  Theophilius
\textsc{Holdred} et simultanément par l'italien Paolo \textsc{Ruffini} (1765 - 1822)
mais fut déjà utilisée par  \textsc{Newton} 150 ans auparavant et par le
chinois \textsc{Zhu  Shije} cinq siècles  plus tôt (vers 1300)  et avant
lui  par le Persan  \textsc{Sharaf al-Din  al-Muzaffar ibn  Muhammad ibn
al-Muzaffar al-Tusi} vers (1100) et avant lui par le
Chinois \textsc{Liu  Hui} (vers 200)  révisant un des  résultats présent
dans \textit{Les Neuf
Chapitres sur l'art mathématique} publié avant la naissance de JC...



Il faut  cependant noter que  \textsc{Ruffini} l'avait employée  en fait
comme  un moyen  de calculer  rapidement le  quotient et  le  reste d'un
polynôme  par $(X-\alpha)$.  



Dans toute  la suite, un  polynôme de dégré  $n$ sera représenté  par le
vecteur de ses coefficients. Par exemple, \texttt{[1 2 3]} correspond au
polynôme $1+2x+3x^2$. 


Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications.




On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}


Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions. 


 Comparez les
complexités au  pire du calcul de $P(t)$  pour $t\in\bbk$. Vous
prendrez comme \og unité de complexité\fg{} les opérations arithmétiques
de base: \texttt{+ - *}.

Déterminez une  fonction \texttt{horner(P,t)}  qui évalue  le polynôme
\texttt{P} en \texttt{t} selon le schéma de \textsc{Horner}.

\end{exercice}



\begin{exercice}
On travaille dans $\mathbb{R}.$ Calculer les sommes :
\end{exercice}

\begin{enumerate}
\item $\sum\limits_{i=3}^{6}ij,$ $\sum\limits_{i=0}^{4}i^{2},$ $%
\sum\limits_{k=0}^{4}k^{2},$ $\sum\limits_{j=0}^{4}i^{2},\sum%
\limits_{i=1}^{50}a_{j}$

\item $\sum\limits_{i=1}^{n\geq 1}a,$ $\sum\limits_{i=h}^{n\geq h}a,$ $%
\sum\limits_{i=1}^{n\geq 1}3$

\item $\sum\limits_{1\leq i<j\leq 5}ij,$ $\sum\limits_{1\leq i<j\leq
5}(i+2j) $
\end{enumerate}


\begin{exercice}
On travaille dans $\mathbb{R},$ calculer les sommes $\sum\limits_{i=1}^{n}i,$
$\sum\limits_{i=50}^{100}j,$ $\sum\limits_{i=h}^{k}i,$ $\sum%
\limits_{i=h}^{k}(i+j),$ $\sum\limits_{i=h}^{k}ij,$ $\sum\limits_{i=h}^{k}(%
\alpha i+j)$
\end{exercice}

\begin{exercice}
On consid\`{e}re un tableau de nombres ayant $n$ lignes et $p$ colonnes. Les
lignes sont num\'{e}rot\'{e}es du haut en bas et les colonnes de la gauche
vers la droite. Le nombre se trouvant sur la $i^{\grave{e}me}$ ligne et $j^{%
\grave{e}me}$ colonne est not\'{e} $a_{i,j}$ ou $a_{ij}.$ Par exemple, si $%
n=4$ et $p=3,$ le tableau se pr\'{e}sente par%
\[
\begin{tabular}{|c|c|c|}
\hline
$a_{1,1}$ & $a_{1,2}$ & $a_{1,3}$ \\ \hline
$a_{2,1}$ & $a_{2,2}$ & $a_{2,3}$ \\ \hline
$a_{3,1}$ & $a_{3,2}$ & $a_{3,3}$ \\ \hline
$a_{4,1}$ & $a_{4,2}$ & $a_{4,3}$ \\ \hline
\end{tabular}%
\]%
On note $L_{i}$ la somme des nombres de la ligne num\'{e}ro $i$, $C_{j}$ la
somme des nombres de la colonne $j$ et $T$ la somme de tous les nombres du
tableau.
\end{exercice}

\begin{enumerate}
\item Exprimer $L_{i}$\ et $C_{j}$\ \`{a} l'aide d'un symbole $\sum .$

\item Exprimer $T$\ de deux fa\c{c}ons.
\end{enumerate}

\begin{exercice}
On reprend les notations de l'exercice pr\'{e}c\'{e}dent avec $n=p=5.$
Que calculent les sommes suivantes ? On pourra donner la solution en
grisant les cases du tableau qui correspondent aux nombres intervenant dans
les sommes.%
% \[
% \FRAME{itbpF}{2.7084cm}{2.7084cm}{0cm}{}{}{sommecases1.wmf}{\special%
% {language "Scientific Word";type "GRAPHIC";maintain-aspect-ratio
% TRUE;display "USEDEF";valid_file "F";width 2.7084cm;height 2.7084cm;depth
% 0cm;original-width 2.6228cm;original-height 2.6228cm;cropleft "0";croptop
% "1";cropright "1";cropbottom "0";filename
% '../../DessinsMaludi/SommeCases1.wmf';file-properties "XNPEU";}} 
% \]

\begin{multicols}{3}

\begin{enumerate}
\item $\sum\limits_{i=1}^{5}\sum\limits_{j=1}^{5}a_{ij}$

\item $\sum\limits_{j=1}^{5}\sum\limits_{i=1}^{5}a_{ij}$

\item $\sum\limits_{i=1}^{5}\sum\limits_{j=1}^{i}a_{ij}$

\item $\sum\limits_{j=1}^{5}\sum\limits_{i=1}^{j}a_{ij}$

\item $\sum\limits_{i=1}^{5}\sum\limits_{j\geq i}a_{ij}$

\item $\sum\limits_{i+j=6}a_{ij}$

\item $\sum\limits_{1\leq i<j\leq 5}a_{ij}$
\end{enumerate}

\end{multicols}
\end{exercice}




\begin{exercice}[Tapis de \textsc{Sierpinski}]
  

Monsieur \textsc{Sierpinski}  avait ramen\'e d'un voyage en Orient un tapis carr\'e de $1$ m\`etre de
c\^ot\'e dont il \'etait tr\`es content. Jusqu'au jour o\`u les mites s'introduisirent chez lui.

En 24 heures, elles d\'evor\`erent dans le tapis un carr\'e de
c\^ot\'e trois fois plus petit, situ\'e exactement au centre du
tapis. En constatant les d\'egats, Monsieur Sierpinski entra dans
une col\`ere noire~! Puis il se consola en se disant qu'il lui
restait huit petits carr\'es de tapis, chacun de la taille du
carr\'e disparu. Malheureusement, dans les 12 heures qui
suivirent, les mites avaient attaqu\'e les huit petits carr\'es
restants~: dans chacun, elles avaient mang\'e un carr\'e central
encore trois fois plus petit. Et dans les 6 heures suivantes elles
grignot\`erent encore le carr\'e central de chacun des tout petits
carr\'es restants. Et l'histoire se r\'ep\'eta, encore et encore~;
\`a chaque \'etape, qui se d\'eroulait dans un intervalle de temps
deux fois plus petit que l'\'etape pr\'ec\'edente, les mites
faisaient des trous de taille trois fois plus petite...

\begin{enumerate} \item Faire des dessins pour bien comprendre la g\'eom\'etrie du tapis trou\'e.
 Calculer le nombre total de trous dans le tapis de Monsieur Sierpinski
apr\`es $n$ \'etapes. Calculer la surface $S_n$ de tapis qui n'a
pas encore \'et\'e mang\'ee apr\`es $n$ \'etapes. Trouver la
limite de la suite $(S_n)_{n \geq 0}$. Que reste-t-il du tapis \`a
la fin de l'histoire~?

\item Calculer la dur\'ee totale du festin \og mitique\fg{}...


\end{enumerate}



\end{exercice}




\begin{exercice}
$\left\vert x\right\vert <1$ et on note $S_{n}\left( x\right)
=\sum\limits_{k=0}^{n}x^{k},\sigma _{n}\left( x\right)
=\sum\limits_{k=0}^{n}kx^{k}=\sum\limits_{k=1}^{n}kx^{k}.$


\begin{enumerate}
\item Calculer $S_{n}^{\prime }\left( x\right) .$

\item Calculer $\sum\limits_{k=0}^{+\infty }x^{k}.$

\item Calculer la limite de $S_{n}^{\prime }\left( x\right) $ lorsque $n$
tend vers $+\infty .$

\item Exprimer $\sigma _{n}\left( x\right) $\ \`{a} l'aide de $S_{n}\left(
x\right) .$

\item Calculer $\sum\limits_{k=0}^{+\infty }kx^{k}.$
\end{enumerate}
\end{exercice}




\begin{exercice}
  On considère que op est une opération à temps constant.

Combien d'op sont réalisées dans les boucles suivantes:

\begin{multicols}{2}



  \begin{algo}
    \FOR{i}{1}{n}
 \STATE{op}
\ENDFOR
  \end{algo}








\begin{algo}
  \FOR{i}{1}{n*n}
  \FOR{j}{1}{n*3}
  \FOR{k}{1}{n}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}





\begin{algo}
 \FOR{i}{1}{n}
 \FOR{j}{1}{n}
 \STATE{op}
\ENDFOR
\FOR{k}{1}{n}
\STATE{op}
\ENDFOR
\ENDFOR
\end{algo}



  \begin{algo}
    \FOR{i}{1}{n}
\FOR{j}{1}{n}
 \STATE{op}
\ENDFOR
\ENDFOR
  \end{algo}




\begin{algo}
  \FOR{i}{1}{n}
  \FOR{j}{1}{n}
  \FOR{k}{1}{n}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}


\begin{algo}
 \FOR{i}{1}{n}
 \FOR{j}{1}{90n}
 \STATE{op}
\ENDFOR
\FOR{k}{40n}{1}
\STATE{op}
\ENDFOR
\ENDFOR
\end{algo}


  \begin{algo}
    \FOR{i}{1}{n}
\FOR{j}{1}{i}
 \STATE{op}
\ENDFOR
\ENDFOR
  \end{algo}




\begin{algo}
  \FOR{i}{1}{n}
  \FOR{j}{1}{i}
  \FOR{k}{1}{j}
  \STATE{op}
  \ENDFOR
  \ENDFOR
  \ENDFOR
\end{algo}



\begin{algo}
  \STATE{s\recoit{}0}
  \STATE{i\recoit{}n}
  \WHILE{$\mathtt{i > 0}$}
  \FOR{j}{0}{$\mathtt{i - 1}$}
  \STATE{s\recoit{}$\mathtt{s + 1}$}
  \ENDFOR
  \STATE{i\recoit{}$\mathtt{i\ //\ 2}$}
  \ENDWHILE
  \RETURN{s}
\end{algo}






\begin{algo}
  \STATE{s\recoit{}0}
  \STATE{i\recoit{}1}
  \WHILE{$\mathtt{i < n}$}
  \FOR{j}{0}{$\mathtt{i-1}$}
  \STATE{s\recoit{}$\mathtt{s+1}$}
  \ENDFOR
  \STATE{i\recoit{}$\mathtt{i*2}$}
  \ENDWHILE
  \RETURN{s}
\end{algo}


\begin{algo}
  \STATE{s\recoit{}0}
  \STATE{i\recoit{}1}
  \WHILE{$\mathtt{i < n}$}
  \FOR{j}{0}{$\mathtt{n-1}$}
  \STATE{s\recoit{}$\mathtt{s+1}$}
  \ENDFOR
  \STATE{i\recoit{}$\mathtt{i*2}$}
  \ENDWHILE
  \RETURN{s}
\end{algo}





\end{multicols}

\end{exercice}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyMD1_15"
%%% End: 
