Le mini-projet
Les exercices ci-dessous sont des mini-projets.
Production finale
La production finale est :
- un compte rendu écrit d'une ou deux pages où figurera la démarche envisagée pour résoudre le problème posé
- un script Python composé d'un programme principal clairement documenté faisant appel à des fonctions.
Présentation
- Une présentation orale de 10 minutes permettra à chaque élève du groupe de détailler sa partie.
- La lisibilité, la clarté du code sont un élément important de l’évaluation. On rappelle que des noms de fonctions et de variables bien choisis aident à la clarté de ce code, ainsi que des commentaires explicites sur le rôle des instructions.
- Le fonctionnement correct du programme est évidemment une nécessité.
Pour tester un mini-projet en cliquant sur "Résultat attendu" vous devez être sous le navigateur Mozilla Firefox
1. Le mot de passe
Pour sécuriser des informations sur internet, il est demandé aux utilisateurs de saisir un mot de passe.
L'objectif de ce mini projet est d'écrire un script javascript qui vérifie le niveau
de sécurité de ce mot de passe et s'il n'y a pas eu d'erreur de saisie.
Les vérifications pourront se faire soit à l'issue de la 2nde saisie, soit au fur et à mesure.
Vous inviterez l'utilisateur à saisir un nouveau mot de passe dans les cas suivants :
- mot de passe non identique
- mot de passe trop court (4 caractères ou moins)
- mot de passe trop long (plus de 10 caractères)
- mot de passe non conforme (2 chiffres ou moins)
Le script fonctionnera avec des majuscules ou des minuscules.
2. Le pendu
On souhaite programmer le jeu du pendu. Le programme consistera à :
- choisir un mot à deviner au hasard dans une liste de mots crée par le programmeur
- afficher la première lettre et la dernière du mot à trouver
- proposer 5 points de vies au joueur, à chaque erreur le joueur perd un point de vie
- afficher, lorsque le joueur a trouvé, le nombre de points de vies restants ou afficher "PENDU".
3. Conversion
Dans cet exercice on souhaite écrire la fonction decbin(decimal) qui entre en paramètre le nombre decimal et qui restitue sa conversion binaire sous la forme d'une chaîne de caractères.
Puis réciproquement on écrira la fonction bindec(binaire) qui entre en paramètre la chaîne de caractères binaire et qui restitue sa conversion décimale.
4. Codage de César
Pour coder un message, on procède de la manière suivante : à chacune des 26 lettres de l'alphabet, on commence par lui associer un entier $n$ de l'ensemble
$\Omega = \{0~;~ 1~;~2~;~\ldots~;~24~;~ 25\}$ selon le tableau ci-dessous :
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
A &B &C &D &E &F &G &H & I&J &K &L &M&N &O &P &Q &R &S &T &U &V &W &X &Y &Z\\ \hline
0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12&13 &14 &15 &16 &17 &18 &19 &20 &21 &22 &23 &24 &25\\ \hline\hline
\end{array}$$
Le texte s'obtient en remplaçant chaque lettre du texte clair original par une lettre à distance fixe, toujours du même côté, dans l'ordre de l'alphabet.
Pour les dernières lettres (dans le cas d'un décalage à droite), on reprend au début.
La distance fixe est la clé du codage, elle est donnée par deux lettres.
Si la clé est CH, la distance entre C et H est 5.
Avec un décalage de 5 vers la droite, A est remplacé par F, B devient G, et ainsi jusqu'à X devient C, puis Y devient D etc.
Il s'agit d'une permutation circulaire de l'alphabet.
La longueur du décalage, 5 dans l'exemple évoqué, constitue la clé du chiffrement qu'il suffit de transmettre au destinataire
— s'il sait déjà qu'il s'agit d'un chiffrement de César — pour que celui-ci puisse déchiffrer le message.
Dans le cas de l'alphabet latin, le chiffre de César n'a que 26 clés possibles (y compris la clé nulle, qui ne modifie pas le texte).
Pour simplifier, les messages à coder nous utiliserons seulement les lettres du tableau. Autrement dit, il n'y a pas de ponctuation, pas d'accents , etc.
Exemple : On veut coder la phrase " Je suis en BTS SIO" avec la clé CH
On utilisera :
- L'instruction ord() qui retourne le code ASCII du caractère
- L'instruction chr() qui retourne la lettre du code ASCII
- La méthode upper() qui transforme les lettres en majuscule
Votre script fera appel à quatre fonctions :
- function phrase_sans_les_espaces(phrase). Cette fonction retournera la phrase à coder sans espace et en majuscule
- function coder(phrase,cle) . Cette fonction retournera le mot (phrase précédente sans espaces) codé en utilisant l'entier clé.
- function decoder(phrase,cle) . Cette fonction retournera un mot initialement codé, décodé.
- function test(mot) . Cette fonction retournera un booleen pour tester si les caractères entrés par l'utilisateur sont corrects.
5. Codage affine
Codage
Pour coder un message, on procède comme précédemment : à chacune des 26 lettres de l'alphabet, on commence par lui associer un entier $n$ de l'ensemble
$\Omega = \{0~;~ 1~;~2~;~\ldots~;~24~;~ 25\}$.
Puis on associe à tout entier $n$ de $\Omega$ le reste de la division euclidienne de $(3n + 5)$ par 26 ; ce reste est alors associé à la lettre correspondante.
On admet que tous ces restes allant de 0 à 25 sont distincts.
Exemple : pour coder la lettre P on procède de la manière suivante :
- Étape 1 : on lui associe l'entier $n = 15$;
- Étape 2 : on calcule de $3\times n + 5 = 3 \times 15 + 5 = 50$;
- Étape 3 : le reste de la division de 50 par 26 est $24$ car $50 = 1\times 26 + 24$;
- Étape 4 : on associe $24$ à Y.
Ainsi la lettre P est codée par la lettre Y. Les étapes 2 et 3 sont appelées codage affine.
Décodage
Pour le décodage on procède de la même manière en associant à tout entier $n$ de $\Omega$ le reste de la division euclidienne de $(9n + 7)$ par 26 ; ce reste est alors associé à la lettre correspondante.
6. Codage Vigenère
Un système de cryptographie, difficile à briser, fut inventé au XVIe siècle par le français Vigenère.
Il consistait à écrire 25 alphabets
décalés par rapport à l’alphabet normal :
l’alphabet qui commence par B et finit par …YZA,
l’alphabet qui commence par C et finit par …ZAB ... etc.
Le codage va s’effectuer sur le principe du chiffre de César : on remplace la lettre d’origine par la lettre occupant la même place dans l’alphabet décalé.
Mais à la différence du chiffre de César, un même message va utiliser non un, mais plusieurs alphabets décalés.
Pour savoir
quels alphabets doivent être utilisés, et dans quel ordre, on utilise une clé.
Si cette clé est VIGENERE et le message " Il faut coder cette phrase, on procédera comme suit :
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
A &B &C &D &E &F &G &H & I&J &K &L &M&N &O &P &Q &R &S &T &U &V &W &X &Y &Z\\ \hline
0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12&13 &14 &15 &16 &17 &18 &19 &20 &21 &22 &23 &24 &25\\ \hline\hline
\end{array}$$
- La première lettre du message, I, est au rang 8 dans l’alphabet normal.
Elle doit être codée en utilisant l’alphabet commençant par la première lettre de la clé, V. Dans cet alphabet, la lettre de rang 8 est est le D. I devient donc D. - La deuxième lettre du message, L, est la lettre de rang 11 dans l’alphabet normal.
Elle doit être codée en utilisant l’alphabet commençant par la deuxième lettre de la clé, I. Dans cet alphabet, la lettre de rang 11 est le T. L devient donc T, etc. - Quand on arrive à la dernière lettre de la clé, on recommence à la première lettre de la clé.
Vous pouvez tester vos codages ici : Chiffre de Vigenère
Exemple :
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
\hline
Lettre1&I&L&F&A&U&T&C&O&D&E&R&C&E&T&T&E&P&H&R&A&S&E\\
\hline
Rang1&8&11&5&0&20&19&2&14&3&4&17&2&4&19&19&4&15&7&17&0&18&4\\
\hline
Clé&V&I&G&E&N&E&R&E&V&I&G&E&N&E&R&E&V&I&G&E&N&E\\
\hline
Rang&21&8&6&4&13&4&17&4&21&8&6&4&13&4&17&4&21&8&6&4&13&4\\
\hline
Rang2&3&19&11&4&7&23&19&18&24&12&23&6&17&23&10&8&10&15&23&4&5&8\\
\hline
Lettre2&D&T&L&E&H&X&T&S&Y&M&X&G&R&X&K&I&K&P&X&E&F&I\\
\hline
\end{array}$$
7. Codage de Hill
Codage
- Étape 1 : Chaque lettre du mot est remplacée par un entier en utilisant toujours le même tableau .
On obtient un couple d'entiers $\left(x_{1}~;~x_{2}\right)$ où $x_{1}$ correspond à la première lettre du mot et $x_{2}$ correspond à la deuxième lettre du mot.; - Étape 2 : $\left(x_{1}~;~x_{2}\right)$ est transformé en $\left(y_{1}~;~y_{2}\right)$ tel que : \[\left(S_{1}\right)\:\: \left\{\begin{array}{l} y_{1}=Reste\left[ \left( 11x_{1} + 3x_{2}\right) /26\right] \\ y_{2} =Reste \left[ \left( 7x_{1} + 4x_{2}\right)/26\right] \end{array}\right.\quad \text{avec}\: 0 \leqslant y_{1} \leqslant 25\:\: \text{et}\:\: 0 \leqslant y_{2} \leqslant 25.\]
- Étape 3 : $\left(y_{1}~;~y_{2}\right)$ est transformé en un mot de deux lettres en utilisant le tableau.
ou encore on obtiendra :
phrase =" Je suis malade" $ \Longrightarrow$ phrase_sans_espace = "JESUISMALADE" $\Longrightarrow$ phrase_codée = "HBYYMYCGRZTL"
Dans le cas d'un nombre impair de lettres, la drenière lettre n'est pas codée.
Décodage
Pour la procédure de décodage on reprend les trois étapes précédentes mais en utilisant un nouveau calcul
- Étape 1 : Chaque lettre du mot est remplacée par un entier en utilisant le tableau du dessus.
On obtient un couple d'entiers $\left(y_{1}~;~y_{2}\right)$ où $y_{1}$ correspond à la première lettre du mot et $y_{2}$ correspond à la deuxième lettre du mot. - Étape 2 : $\left(y_{1}~;~y_{2}\right)$ est transformé en $\left(x_{1}~;~x_{2}\right)$ tel que : \[\left(S_{3}\right)\:\: \left\{\begin{array}{l } x_{1}= Reste\left[ \left( 16y_{1} + y_{2}\right)/26 \right] \\ x_{2}=Reste\left[ \left( 11y_{1} + 5y_{2}\right) /26\right] \end{array}\right.\]
- Étape 3 : $\left(x_{1}~;~x_{2}\right)$ est transformé en un mot de deux lettres en utilisant le tableau.
8. Le carré magique
En mathématiques, un carré magique d’ordre n est composé de $n^2$ entiers strictement positifs, 1,2,3 .....$n^2$, écrits sous la forme
d’un tableau carré.
Ces nombres sont disposés de sorte que leurs sommes sur chaque rangée, sur chaque colonne et sur chaque diagonale principale soient égales.
On nomme alors constante magique (et parfois densité) la valeur de ces sommes.
Cette constante magique est égale à $ \dfrac{n\left(n^2+1 \right)}{2}$.
Exemple :
Carré magique d'ordre 3 : $$\begin{array}{|c|c|c|}
\hline
8&1&6\\
\hline
3&5&7\\
\hline
4&9&2\\
\hline
\end{array}.$$
Constante magique :$ \dfrac{3\times \left(3^2+1\right)}{2}=15$.
On souhaite construit des carrés magiques d'ordre impair.
Pour cela on pourra utiliser la méthode suivante :
- Placez un 1 au milieu de la première ligne
- Après avoir placé $k$ dans le carré en $(i,j)$ , placez $k+1$ dans le carré à droite et vers le haut,
soit en $(i+1,j-1)$ en défilant au-delà des bordures, c'est à dire que si la case dépasse la première ligne
(resp. la dernière colonne), la case sélectionnée est celle en dernière ligne (resp. en première colonne).
En cas d'occupation d'une case, la case suivante est recalculée sous la case courante.
Explication pour un carré d'ordre 3 :
Étape 1 : $\begin{array}{|c|c|c|}\hline
.&1&.\\\hline .&.&.\\\hline .&.&.\\\hline
\end{array}$
.
Étape 2 : $ \begin{array}{cccc}
\begin{array}{ccc}
~&~&(2)\end{array}\\
\begin{array}{|c|c|c|}\hline
.&1&.\\\hline .&.&.\\\hline .&.&.\\\hline
\end{array}&\Longrightarrow&
\begin{array}{|c|c|c|}\hline
.&1&.\\\hline .&.&.\\\hline .&.&2\\\hline
\end{array}&
\text{ On dépasse la première ligne, on met 2 à la dernière ligne.}
\end{array}$
.
Étape 3 : $ \begin{array}{ccccc}
\begin{array}{|c|c|c|}\hline
.&1&.\\\hline .&.&.\\\hline .&.&2\\\hline
\end{array}&
\hspace{-0.4cm}\begin{array}{c}
\\(3)\\\\
\end{array}
&\Longrightarrow&
\begin{array}{|c|c|c|}\hline
.&1&.\\\hline 3&.&.\\\hline .&.&2\\\hline
\end{array}&
\text{ On dépasse la troisième colonne , on met 3 à la première colonne.}
\end{array}$
.
Étape 4 : $ \begin{array}{ccccc}
\begin{array}{|c|c|c|}\hline
.&1&.\\\hline 3&.&.\\\hline .&.&2\\\hline
\end{array}&
\begin{array}{|c|c|c|}\hline
.&1&.\\\hline 3&.&.\\\hline 4&.&2\\\hline
\end{array}&
\text{La case est occupée par 1 on met 4 en dessous de la case courante.}
\end{array}$
.
Étape 5 :
$\begin{array}{|c|c|c|}\hline
.&1&.\\\hline 3&5&.\\\hline 4&.&2\\\hline
\end{array}$
.
Étape 6 :
$\begin{array}{|c|c|c|}\hline
.&1&6\\\hline 3&5&.\\\hline 4&.&2\\\hline
\end{array}$
.
Étape 7 :
$ \begin{array}{ccc}
\begin{array}{cccc}
~&~~~&~~~&~~~(7)\end{array}\\
\begin{array}{|c|c|c|}\hline
.&1&6\\\hline 3&5&.\\\hline 4&.&2\\\hline
\end{array}&\Longrightarrow&
\begin{array}{|c|c|c|}\hline
.&1&6\\\hline 3&5&7\\\hline 4&.&2\\\hline
\end{array}
\end{array}$.
On dépasse la première ligne, et la dernière colonne. 7 doit se trouver à la dernière ligne, première colonne.
Cette case est occupée par 4, on met 7 sous la case courante.
.
Étape 8 : $ \begin{array}{ccccc}
\begin{array}{|c|c|c|}\hline
.&1&6\\\hline 3&5&7\\\hline 4&.&2\\\hline
\end{array}&
\hspace{-0.4cm}\begin{array}{c}
(8)\\\\\\
\end{array}
&\Longrightarrow&
\begin{array}{|c|c|c|}\hline
8&1&6\\\hline 3&5&7\\\hline 4&.&2\\\hline
\end{array}&
\text{ On dépasse la troisième colonne , on met 8 à la première colonne.}
\end{array}$
.
Étape 9 : $ \begin{array}{ccccc}
\begin{array}{ccc}
~&(9)&\end{array}\\
\begin{array}{|c|c|c|}\hline
8&1&6\\\hline 3&5&7\\\hline 4&.&2\\\hline
\end{array}
&\Longrightarrow&
\begin{array}{|c|c|c|}\hline
8&1&6\\\hline 3&5&7\\\hline 4&9&2\\\hline
\end{array}&
\text{ On dépasse la première ligne, on met 9 à la dernière ligne.}
\end{array}$
Le script proposé permettra de générer un carré magique d'ordre impair.
9. MOTUS
MOTUS est un jeu où un l'on doit trouver un mot de six lettres en faisant au plus cinq propositions.
Au départ seulement la première lettre est donnée. Pour chaque proposition du candidat on regarde chaque lettre du mot proposé et
on distingue trois cas :
- la lettre se trouve dans le mot cherché et elle est au bon endroit, on la remplace en majuscule dans le mot qui s'affichera;
- la lettre se trouve dans le mot cherché mais pas bien située, on la remplace en minuscule dans le mot qui s'affichera;
- la lettre ne se trouve pas dans le mot cherché on la remplace par un point (.) dans le mot qui s'affichera; .
10. Jeu ciseau, pierre, papier
Le jeu ciseau, pierre, papier est le suivant : deux joueurs choisissent chacun une des trois possibilités puis confrontent leur choix. Le résultat est alors le suivant : égalité si les choix sont identiques, sinon le gagnant est obtenu selon les règles : le ciseau coupe le papier, le papier enveloppe la pierre, la pierre casse le ciseau.
Un des joueurs est la machine qui choisit ses coups au hasard avec une fonction hasard qui donne le résultat ciseau, pierre
ou papier aléatoirement.
Le jeu correspond à une suite de 5 parties simples qui s'enchaînent. A l'issue des 5 parties, on affichera le gagnant et le score.
11. Quiz
Ce quiz est un qcm où la machine choisit au hasard quatre questions parmi l'informatique, les maths, la physique et la svt.
L'utilisateur répond par A, B et C.
A l'issue des 4 questions, on affichera le score.
12. La numération Shadock
Outre la numération décimale (base 10) et la numération binaire (base 2), il existe entre autre la numération Shadock (base 4). Les Shadock sont des personnages dessinés apparus à la télévision dans les années 60.
Leur cerveau étant limité, ils ne connaissent que les chiffres 0, 1, 2 et 3 et les lisent respectivement : GA,BU, ZO et MEU.
On souhaite ici concevoir un programme de conversion qui consistera à :
- convertir un nombre décimal en un nombre Shadock : 34 $\; \Longrightarrow $ ZO GA ZO
Aide : méthode - convertir un nombre Shadock en un nombre décimal : BU GA MEU ZO $\;\Longrightarrow $ 78
Aide : méthode
Afin de vous familiariser avec leur numération, vous pouvez vous entraîner sur le site : Shadock
13. La conjecture de Goldbach
La conjecture de Goldbach dit que Tout nombre entier pair supérieur à 3 peut s’écrire comme la somme de deux nombres premiers..
4=2+2, 6=3+3, 8=3+5, 10= 3+7 ......etc
Vous pouvez consulter la vidéo : Sciences etonnantes
Ecrire un programme qui
- lit un nombre pair entre 4 et 10000 et propose sa décomposition en une somme de nombres premiers.
- lit un nombre pair $n$ entre 2 et 900 et propose tous les nombres premiers de 2 à 10000 ayant un écart de $n$ .