\documentclass[12pt,french]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{babel}
\usepackage{fourier}
\usepackage{textcomp}
\usepackage{array}
\usepackage[table]{xcolor}
\usepackage{multicol}
\usepackage{tikz}
	\usetikzlibrary{calc}
\usepackage[vmargin=2cm]{geometry}
\usepackage[colorlinks=true]{hyperref}
\usepackage{listingsutf8}
	\lstset{%
		inputencoding=utf8,
		language=Python,%
		upquote=true,
        commentstyle=\color{gray},
		columns=fullflexible,%
		keywordstyle=\color{red},%
		basicstyle=\ttfamily,%
		%morekeywords={},%
		%texcsstyle=*\color{blue},%
		%moretexcs={},%
		frame=single,%
		backgroundcolor=\color{gray!25},%
		breaklines=true,%
		literate=
    		{é}{{\'e}}{1}%
    		{è}{{\`e}}{1}%
    		{à}{{\`a}}{1}%
    		{â}{{\^a}}{1}%%%
    		{ç}{{\c{c}}}{1}%
    		{œ}{{\oe}}{1}%
    		{ù}{{\`u}}{1}%
    		{É}{{\'E}}{1}%
    		{È}{{\`E}}{1}%
    		{À}{{\`A}}{1}%
    		{Ç}{{\c{C}}}{1}%
    		{Œ}{{\OE}}{1}%
    		{Ê}{{\^E}}{1}%
    		{ê}{{\^e}}{1}%
    		{î}{{\^i}}{1}%
    		{ï}{{\"i}}{1}%%%
    		{ô}{{\^o}}{1}%
    		{û}{{\^u}}{1}}
\title{NSI -- Sujets 0}
\author{\href{https://www.mathweb.fr}{Stéphane Pasquet (mathweb.fr)}}
\date{\today}
\setlength{\parindent}{0pt}

% ----------------

\def\d{0.1}

\newsavebox\sol
\newenvironment{solution}
{%
\begin{lrbox}{\sol}
\begin{minipage}{\linewidth}
}
{
\end{minipage}
\end{lrbox}
\fcolorbox{black}{gray!10}{ \usebox{\sol} }
}
\begin{document}
\maketitle

\section*{Thème « Types et valeurs de base »}

\begin{enumerate}
\item Combien d'entiers positifs ou nuls peut-on représenter en machine sur 32 bits ?

\begin{enumerate}
\begin{multicols}{4}
\item $2^{32}-1$
\item $2^{32}$
\item $2\times32$
\item $32^2$
\end{multicols}
\end{enumerate}

\begin{solution}
\textbf{Réponse b.} En effet, un bit peut représenter 2 états : 0 ou 1. Donc sur 2 bits, on peut représenter $2\times2=2^2$ nombres, etc. Sur une machine de 32 bits, il y a donc $2^{32}$ possibilités de nombres.
\end{solution}

% ------------------->  Q1.2

\item Les entiers positifs ou nuls dont l'écriture en base 16 (hexadécimal) est constituée par un 1 suivi de 0 (par exemple 1, 10, 100, 1000, etc.) sont :

\begin{enumerate}
\begin{multicols}{2}
\item les puissances de 2
\item les puissances de 8
\item les puissances de 10
\item les puissances de 16
\end{multicols}
\end{enumerate}

\begin{solution}
\textbf{Réponse d.} En effet, en hexadécimal, un nombre s'écrivant sous la forme $\overline{x_nx_{n-1}\cdots x_1x_0}$ est égal, en base 10, à $\displaystyle\sum_{k=0}^nx_k\times16^k$. 

Ainsi, si $x_{n-1}=x_{n-2}=\cdots=x_0=0$ et $x_n=1$, ce nombre est égal à $16^n$. C'est donc une puissance de 16.
\end{solution}

% ------------------->  Q1.3

\item Dans le programme ci-dessous, qui prend en entrée un entier naturel non nul et renvoie son écriture binaire, remplacer les pointillés par l'opérateur qui convient.

\begin{lstlisting}
def cascade(n):
	chiffres = ''
	while n != 0:
		chiffres = str(n ... 2) + chiffres
		n = n // 2
	return chiffres
\end{lstlisting}

\begin{enumerate}
\begin{multicols}{4}
\item //
\item +
\item *
\item \%
\end{multicols}
\end{enumerate}

\begin{solution}
\textbf{Réponse d.} En effet, l'écriture binaire d'un entier s'obtient à partir de divisions euclidiennes successives par 2 en prenant leurs \textit{restes}, obtenus à l'aide de l'opérateur \%. Rappelons que \og a\% b \fg{} représente le reste dans la division euclidienne de $a$ par $b$.
\end{solution}
\end{enumerate}

\section*{Thème « Types construits »}

\begin{enumerate}
\item On définit un tableau \texttt{t} rempli de 0 en langage Python. Ce tableau est une liste de listes, toutes les sous-listes ayant le même nombre d'éléments.
\begin{lstlisting}
t = [ [0, 0, ... , 0],
      [0, 0, ... , 0],
      ...
      [0, 0, ... , 0] ]
\end{lstlisting}

On appelle \texttt{h} le nombre de listes contenus dans \texttt{t} et \texttt{n} le nombre d'éléments appartenant à ces listes. Parmi les propositions suivantes, laquelle permet de calculer \texttt{h} et \texttt{n} ?

\begin{enumerate}
\item \texttt{h, n = len(t[0]), len(t)}
\item \texttt{h, e = len(t[0]), len(t[1])}
\item \texttt{h, e = len(t), len(t[0])}
\item \texttt{h, e = len(t[1]), len(t[0])}
\end{enumerate}

\begin{solution}
\textbf{Réponse c.} En effet, \texttt{len(t)} représente le nombre d'éléments du tableau \texttt{t}, c'est-à-dire ici le nombre de listes dans \texttt{t}. De plus, \texttt{len(t[0]} représente le nombre d'éléments de \texttt{t[0]}.
\end{solution}

% ------------------->  Q2.2

\item On considère le code suivant :
\begin{lstlisting}
def f(t):
	for i in range(len(t)//2):
		t[i] , t[-i-1] = t[-i-1] , t[i]
\end{lstlisting}

Après les lignes suivantes :
\begin{lstlisting}
t = [2,3,4,5,7,8]
f(l)
\end{lstlisting}

quelle est la valeur de \texttt{t} ?

\begin{enumerate}
\item \texttt{[2,3,4,5,7,8]}
\item \texttt{[5,7,8,2,3,4]}
\item \texttt{[8,7,5,4,3,2]}
\item \texttt{[4,3,2,8,7,5]}
\end{enumerate}

\begin{solution}
\textbf{Réponse c.} En effet, l'instruction \texttt{for i in range(len(t)//2)} stipule que l'on parcourt la moitié de la liste \texttt{t}. Pour chaque valeur de \texttt{i}, on intervertit les valeurs de \texttt{t[i]} et \texttt{t[-i-1]}. Par exemple, pour \texttt{i=0}, \texttt{t[0]} et \texttt{t[-1]} sont intervertis, c'est-à-dire le premier et dernier élément de la liste \texttt{t}. Ici, \texttt{len(t)//2=3} donc \texttt{i} prend les valeurs 0, 1 et 2. On aura donc successivement:
\begin{itemize}
\item Avant l'entrée dans la boucle : \texttt{t = [2,3,4,5,7,8]}
\item Pour $i=0$ : \texttt{t = [8,3,4,5,7,2]}
\item Pour $i=1$ : \texttt{t = [8,7,4,5,3,2]}
\item Pour $i=2$ : \texttt{t = [8,7,5,4,3,2]}
\end{itemize}
\end{solution}

% ------------------->  Q2.3

\item On dispose d'un tableau d'entiers, ordonné en ordre croissant. On désire connaître le nombre de valeurs distinctes contenues dans ce tableau.
Quelle est la fonction qui \textbf{ne convient pas} ?

\begin{enumerate}
\item \begin{minipage}{\textwidth}
\begin{lstlisting}
def compte(t):
	cpt = 1
	for i in range(1,len(t)):
		if t[i] != t[i-1]:
			cpt = cpt + 1
	return cpt
\end{lstlisting}
\end{minipage}

\item \begin{minipage}{\textwidth}
\begin{lstlisting}
def compte(t):
	cpt = 1
	for i in range(0,len(t)-1):
		cpt = cpt + int(t[i] != t[i+1])
	return cpt
\end{lstlisting}
\end{minipage}

\item \begin{minipage}{\textwidth}
\begin{lstlisting}
def compte(t):
	cpt = 0
	for i in range(0,len(t)-1):
		cpt = cpt + int(t[i] != t[i+1])
	return cpt
\end{lstlisting}
\end{minipage}

\item \begin{minipage}{\textwidth}
\begin{lstlisting}
def compte(t):
	cpt = 0
	for i in range(0,len(t)-1):
		if t[i] != t[i+1]:
			cpt = cpt + 1
	return cpt+1
\end{lstlisting}
\end{minipage}
\end{enumerate}

\begin{solution}
\textbf{Réponse c.} En effet, ce programme ressemble à celui proposé en (b), à ceci près que l'initialisation de la variable \texttt{cpt} n'est pas la même. Le programme ne convenant pas est donc (b) ou (c).

L'instruction \texttt{int(t[i] != t[i+1])} renvoie \og 1 \fg{} si la différence est vérifiée, et \og 0 \fg{} si les deux valeurs sont égales. Si on prend l'exemple de\linebreak\texttt{t = [1,2,2,3]}, on a (avec le programme (c):
\begin{itemize}
\item Avant l'entrée dans la boucle : \texttt{cpt = 0}
\item Pour $i = 0$ : \texttt{cpt = cpt + 1 = 0 + 1 = 1}
\item Pour $i = 1$ : \texttt{cpt = cpt + 0 = 1 + 0 = 1}
\item Pour $i = 2$ : \texttt{cpt = cpt + 1 = 1 + 1 = 2}
\end{itemize}
Ainsi, au lieu de retourner \og 3 \fg{}  (car dans cet exemple, il y a 3 nombres distincts), le programme retourne 2.
\end{solution}
\end{enumerate}

\section*{Thème « Traitement de données en tables »}

\begin{enumerate}
\item On dispose d'une liste de triplets :
\begin{lstlisting}
t = [ 	(1,12,250),
	 (1,12,251), 
	 (2,12,250),
	 (2,13,250), 
	 (2,11,250), 
	 (1,12,249) ]
\end{lstlisting}

On trie cette liste par ordre croissant des valeurs du second éléments des triplets. En cas d'égalité, on trie par ordre croissant du troisième champ. Si les champs 2 et 3 sont égaux, on trie par ordre croissant du premier champ. Après ce tri, quel est le contenu de la liste \texttt{t} ?

\begin{enumerate}
\item \texttt{[ (1,12,249),\\ (1,12,250),\\ (1,12,251),\\ (2,11,250),\\ (2,12,250),\\ (2,13,250) ]}
\item \texttt{[ (2,11,250),\\ (1,12,249),\\ (1,12,250),\\ (2,12,250),\\ (1,12,251),\\ (2,13,250) ]}
\item \texttt{[ (2,11,250),\\ (1,12,249),\\ (1,12,250),\\ (1,12,251),\\ (2,12,250),\\ (2,13,250) ]}
\item \texttt{[ (1,12,249),\\ (2,11,250),\\ (1,12,250),\\ (2,12,250),\\ (2,13,250),\\ (1,12,251) ]}
\end{enumerate}

\begin{solution}
\textbf{Réponse b.} Il suffit ici de respecter les consignes de tris. On commence par prendre le triplet dont le 2\ieme{} nombre est le plus petit -- donc \texttt{(2,11,250)} -- puis on passe au suivant : il y a 4 possibilités car 4 triplets comporte \og 12 \fg{} en 2\ieme{} position; on trie alors selon le 3\ieme{} nombre. Il y a 2 triplets ayant \og 250 \fg{} comme 3\ieme{} nombre donc on tris en fonction du 1\ier{} pour ces deux triplets.
\end{solution}


\item À partir de fichiers remplis à l'aide de formulaires en ligne, on dispose d'un tableau \texttt{t1} de numéros de client, nom, âge, ville et d'un tableau \texttt{t2} de numéros de commande, numéros de client, prix :
\begin{lstlisting}
t1 = [ [3,"Pierre",25,"Ambérieu"], 
       [5,"Gaspe",45,"Lagnieu"], 
       [98,"Abraham",75,"Meximieux"],
       [24,"Zoé",34,"Lyon"] ]
       
t2 = [ [1287,5,1025], [13245,98,234], 
       [23,5,42],[10001,24,53] ]
\end{lstlisting}

Que devient \texttt{t1} après l'exécution du code suivant :
\begin{lstlisting}
for i in range(len(t1)): 
	for c in [ com for com in t2 if com[1]==t1[i][0] ]:
		t1[i].append( (c[0], c[2]) )
\end{lstlisting}

\begin{enumerate}
\item \bgroup\ttfamily
[ [5, 'Gaspe', 45, 'Lagnieu', (1287, 1025), (23, 42)]

[98, 'Abraham', 75, 'Meximieux', (13245, 234)]

[24, 'Zoé', 34, 'Lyon', (10001, 53)] ]
\egroup

\item \bgroup\ttfamily
[ [3, 'Pierre', 25, 'Ambérieu']

[5, 'Gaspe', 45, 'Lagnieu', (1287, 1025), (23, 42)]

[98, 'Abraham', 75, 'Meximieux', (13245, 234)]

[24, 'Zoé', 34, 'Lyon', (10001, 53)] ]
\egroup

\item \bgroup\ttfamily
[ [3, 'Pierre', 25, 'Ambérieu', (1287, 1025)]

[5, 'Gaspe', 45, 'Lagnieu', (13245, 234)]

[98, 'Abraham', 75, 'Meximieux', (23, 42)]

[24, 'Zoé', 34, 'Lyon', (10001, 53)] ]
\egroup

\item \bgroup\ttfamily
[ [3, 'Pierre', 25, 'Ambérieu']

[5, 'Gaspe', 45, 'Lagnieu']

[98, 'Abraham', 75, 'Meximieux']

[24, 'Zoé', 34, 'Lyon'] ]
\egroup
\end{enumerate}

\begin{solution}
\textbf{Réponse b.} Il faut avant tout comprendre l'instruction :
\begin{lstlisting}
for c in [ com for com in t2 if com[1]==t1[i][0] ]:
\end{lstlisting}

Ici, \texttt{com} représente une entrée de \texttt{t2} sous la condition que \texttt{com[1]} soit égal à \texttt{t1[i][0]}. Il faut donc que le 2\ieme{} nombre de l'élément de \texttt{t2} coïncide avec le numéro client dans l'entrée de \texttt{t1}. Sous cette unique condition, on ajoute à l'entrée de \texttt{t1} les 1\ier{} et derniers nombres de l'entrée de \texttt{t2}. Concrètement, 
\begin{itemize}
\item pour $i=0$, on parcourt \texttt{t2} jusqu'à ce que le 2\ieme{} nombre de l'élément de \texttt{t2} soit 3. Comme il n'y en a pas, on n'ajoute rien.
\item Pour $i=1$, on parcourt \texttt{t2} jusqu'à rencontrer \og 5 \fg{} en 2\ieme{} nombre : il y a 2 triplets qui correspondent donc en ajoute deux fois un couple : (1287,1025) et (23,42).
\item etc.
\end{itemize}
\end{solution}

\item On considère le programme suivant :
\begin{lstlisting}
def maxi(tab):
	"""
	tab est une liste de couples (nom, note)
	où nom est de type str
	et où note est un entier entre 0 et 20.
	"""
	m = tab[0]
	for x in tab:
		if x[1] >= m[1]:
			m = x
	return m

L = [('Adrien', 17), ('Barnabé', 17), ('Casimir', 17),
     ('Dorian', 17), ('Emilien', 16), ('Fabien', 16)]
\end{lstlisting}

Quelle est la valeur de maxi(L) ?

\begin{enumerate}
\item \texttt{('Adrien',17)}
\item \texttt{('Dorian',17)}
\item \texttt{('Fabien',16)}
\item \texttt{('Emilien',16)}
\end{enumerate}

\begin{solution}
\textbf{Réponse b.} Exécutons pas à pas le programme:
\begin{center}
\begin{tabular}{|*3{>{\ttfamily}c|}}
\hline\rowcolor{gray!80!blue}
x  & x[1] >= m[1] & Valeur de m\\
\hline
&  & ('Adrien',17)\\
\hline
('Adrien',17) & Vrai & ('Adrien',17)\\
\hline
('Barnabé',17) & Vrai & ('Barnabé',17)\\
\hline
('Casimir',17) & Vrai & ('Casimir',17)\\
\hline
('Dorian',17) & Vrai & ('Dorian',17)\\
\hline
('Emilien',16) & Faux & ('Dorian',17)\\
\hline
('Fabien',16) & Faux & ('Dorian',17)\\
\hline
\end{tabular}
\end{center}
\end{solution}
\end{enumerate}

\section*{Thème « Interaction Homme-machine sur le web »}

\begin{enumerate}
\item Après avoir saisi dans son navigateur l'URL de son forum favori, Clotilde reçoit comme réponse du serveur une erreur « 404 ». Une seule des réponses suivantes ne correspond pas à cette situation, laquelle ?

\begin{enumerate}
\item Une panne de sa connexion internet
\item Une mise à jour du serveur qu'elle consulte
\item Une erreur de saisie de sa part
\item Un changement de titre du forum qu'elle consulte
\end{enumerate}

\begin{solution}
\textbf{Réponse a.} En effet, l'erreur \og 404 \fg signifie que la page n'a pas été trouvée... et cela suppose que la connexion internet est bonne.
\end{solution}

\item Saisir l'URL \textit{http://monsite.com/monprogramme.py?id=25} dans la barre d'adresse du navigateur \textbf{ne permet à coup sûr pas} :

\begin{enumerate}
\item de télécharger un programme Python
\item d'exécuter un programme Python sur le serveur
\item d'exécuter un programme Python sur le client
\item d'afficher une page html
\end{enumerate}


\begin{solution}
\textbf{Réponse c.} En effet, si un exécuteur Python n'est pas présent sur le serveur, taper cette URL aura pour effet de télécharger le programme (réponse a) ou de l'afficher dans le navigateur (réponse d). En revanche, si le serveur est doté d'un exécuteur Python, le fait de saisir l'URL aura pour effet de le lancer... mais côté serveur (réponse b), pas côté client.
\end{solution}


\item Un élément \texttt{form} d'une page HTML contient un élément \textit{button} de type \textit{submit}. Un clic sur ce bouton :

\begin{enumerate}
\item envoie les données du formulaire vers la page définie par l'attribut action de l'élément \texttt{form}
\item efface les données entrées par l'utilisateur dans le formulaire
\item envoie les données du formulaire vers la page définie par l'attribut \textit{method} de l'élément \texttt{form}
\item ne fait rien si un script javascript n'est pas associé au bouton
\end{enumerate}

\begin{solution}
\textbf{Réponse a.} C'est le principe des boutons de type \textit{submit}.
\end{solution}
\end{enumerate}

\section*{Thème « Architectures matérielles et systèmes d'exploitation »}

\begin{enumerate}
\item Parmi les affirmations suivantes, laquelle est vraie ?

\begin{enumerate}
\item La mémoire RAM est une mémoire accessible en lecture seulement
\item La mémoire RAM est une mémoire accessible en écriture seulement
\item La mémoire RAM est une mémoire accessible en lecture et en écriture
\item La mémoire RAM permet de stocker des données après extinction de la machine
\end{enumerate}

\begin{solution}
\textbf{Réponse c.} La mémoire RAM (Random Access Machine) sert à stocker le programme à exécuter ainsi que ses données. Elle est donc accessible en lecteur ET écriture, mais elle se vide à chaque extinction du système. Elle ne doit pas être confondue avec la \textit{mémoire vive}, qui se présente souvent sous forme de barrette dans un ordinateur.
\end{solution}

\newpage

\item À partir du dossier \verb+~+\texttt{/Doc/QCM}, quelle commande permet de rejoindre le dossier \verb+~+\texttt{/.Hack/Reponses} ?

\begin{enumerate}
\item \texttt{cd ../../.Hack/Reponses}
\item \texttt{cd .Hack/Reponses}
\item \texttt{cd /}\verb+~+\texttt{/.Hack/Reponses}
\item \texttt{cd /.Hack/Reponses}
\end{enumerate}

\begin{solution}
\textbf{Réponse a.} En effet, \texttt{cd ../} permet de remonter l'arborescence d'un niveau (donc après l'exécution de cette commande, on se trouve dans le répertoire \verb+~+\texttt{/Doc/}). Donc avec \texttt{cd ../../}, on remonte de 2 niveaux et on se trouve dans \verb+~+\texttt{/}. Il suffit ensuite d'insérer le chemin du répertoire dans lequel on veut se déplacer.
\end{solution}

\item Que permet la commande \textit{ping} lancé sur ce poste ?

\begin{enumerate}
\item de vérifier que l'on a accès à internet
\item de connaître l'adresse Ethernet d'une autre machine
\item de tester l'accessibilité d'une autre machine à travers un réseau IP
\item de saturer le réseau avec des requêtes ICMP
\end{enumerate}

\begin{solution}
\textbf{Réponse c.} Par exemple, \texttt{ping www.monsite.com} permet d 'obtenir des résultats du type :

\bgroup
\ttfamily
Envoi d'une requête 'ping' sur monsite.com

[2001:41d0:1:1b00:213:186:33:19] avec 32 octets de données:                  

Réponse de 2001:41d0:1:1b00:213:186:33:19 : temps=45 ms                                                              

Réponse de 2001:41d0:1:1b00:213:186:33:19 : temps=101 ms                                                               

Réponse de 2001:41d0:1:1b00:213:186:33:19 : temps=165 ms

Réponse de 2001:41d0:1:1b00:213:186:33:19 : temps=231 ms

Statistiques Ping pour 2001:41d0:1:1b00:213:186:33:19:

\qquad Paquets : envoyés = 4, reçus = 4, perdus = 0 (perte 0\%),

Durée approximative des boucles en millisecondes :

\qquad Minimum = 45ms, Maximum = 231ms, Moyenne = 135ms   
\egroup
\end{solution}
\end{enumerate}

\newpage

\section*{Thème « Langages et programmation »}

\begin{enumerate}
\item $a$ et $m$ étant des entiers strictement positifs, la fonction suivante calcule $a^m$ :
\begin{lstlisting}
def puissance(a,m):
	p = 1
	n = 0
	while n < m:
		p = p * a
		#
		n = n + 1
	return p
\end{lstlisting}

À la ligne marquée d'un \#, on a :

\begin{multicols}{4}
\begin{enumerate}
\item $p = a^n$
\item $p=a^{n-1}$
\item $p=a^{n+1}$
\item $p=a^m$
\end{enumerate}
\end{multicols}

\begin{solution}
\textbf{Réponse c}. Il suffit de voir ce qui se passe pas à pas:
\begin{center}
\begin{tabular}{|>{\ttfamily}c|>{\ttfamily\columncolor{orange!50}}c|>{\ttfamily}c|}
\hline\rowcolor{gray!80!blue}
n < m & p & n  \\
\hline
 & 1 & 0\\
 \hline
Vrai & a & 1\\
\hline
Vrai & a*a & 2\\
\hline
Etc. &  & \\
\hline
\end{tabular}
\end{center}
La colonne orange indique la valeur de \texttt{p} au niveau de la la ligne marquée d'un \#. On voit que pour $n=0$, $p=a$. Pour $n=1$, $p=a^2$.
L'exposant de $a$ est égal à $n+1$.
\end{solution}

\item Voici une fonction Python de recherche d'un maximum :
\begin{lstlisting}
def maxi(t):
	m = -1
	for k in range(len(t)):
		if t[k] > m:
			m = t[k]
	return m
\end{lstlisting}

Avec quelle précondition sur la liste \texttt{t} la postcondition « \texttt{m} est un élément maximum de la liste \texttt{t} » n'est-elle pas assurée ?

\begin{enumerate}
\item Tout élément de \texttt{t} est un entier positif ou nul
\item Tout élément de \texttt{t} est un entier supérieur ou égal à $-2$
\item Tout élément de \texttt{t} est un entier supérieur ou égal à $-1$
\item Tout élément de \texttt{t} est un entier strictement supérieur à $-2$
\end{enumerate}

\begin{solution}
\textbf{Réponse b.} En effet, on initialise la variable \texttt{m} à $-1$ et par suite, on effectue des tests de supériorité par rapport à \texttt{m}. Si \texttt{t} est une liste uniquement composée de $-2$, par exemple \texttt{t = [-2,-2,-2]}, alors ce programme ne fonctionne pas.
\end{solution}

\newpage

\item La fonction \texttt{indice}\verb+_+\texttt{maxi} ci-dessous doit rechercher l'indice de la valeur maximale présente dans une liste de nombres et le renvoyer.

Dans le cas où cette valeur maximale est présente plusieurs fois, c'est le plus petit de ces indices qui doit être renvoyé.
\begin{lstlisting}
def indice_maxi(liste):
	valeur_max = liste[0]
	indice = 0
	for i in range(len(liste)):
		if liste[i] > valeur_max:
			indice = i
	return indice
\end{lstlisting}

Cette fonction a mal été programmée. On souhaite mettre en évidence son incorrection par un test bien choisi. Quelle valeur de test mettra l'erreur en évidence ?

\begin{multicols}{2}
\begin{enumerate}
\item \texttt{[ 1, 2, 3, 4 ]}
\item \texttt{[ 4, 3, 2, 1 ]}
\item \texttt{[ 1, 3, 3, 2 ]}
\item \texttt{[ 1, 1, 1, 1 ]}
\end{enumerate}
\end{multicols}

\begin{solution}
\textbf{Réponse c.} Les listes des propositions (a) et (b) sont soit croissante, soit décroissante, ce qui ne permet pas de mettre en relief une anomalie. Quant à la liste de la proposition (d), elle est constante donc là encore, on ne détecte pas l'anomalie. Si on exécute le programme de la proposition (c), on a :
\begin{center}
\begin{tabular}{|>{\ttfamily}c|>{\ttfamily}c|>{\ttfamily\columncolor{orange!50}}c|}
\hline\rowcolor{gray!80!blue}
i & liste[i] > valeur\verb+_+max & indice  \\
\hline
0 & 1 > 1 : faux & 0\\
\hline
1 & 3 > 1 : vrai & 1\\
\hline
2 & 3 > 1 : vrai & 2\\
\hline
3 & 2 > 1 : vrai & 3\\
\hline
\end{tabular}
\end{center}
Le programme retourne donc \og 3 \fg... ce qui est faux.
\end{solution}
\end{enumerate}

\section*{Thème « Algorithmique »}

\begin{enumerate}
\item \texttt{A} désignant un entier, lequel des codes suivants ne termine pas ?

\begin{multicols}{2}
\begin{enumerate}
\item \begin{minipage}{0.4\textwidth}
\begin{lstlisting}
i = A + 1
while i < A:
	i = i-1
\end{lstlisting}
\end{minipage}

\item \begin{minipage}{0.4\textwidth}
\begin{lstlisting}
i = A + 1
while i < A:
	i = i + 1
\end{lstlisting}
\end{minipage}

\item \begin{minipage}{0.4\textwidth}
\begin{lstlisting}
i = A - 1
while i < A:
	i = i - 1
\end{lstlisting}
\end{minipage}

\item \begin{minipage}{0.4\textwidth}
\begin{lstlisting}
i = A - 1
while i < A:
	i = i + 1
\end{lstlisting}
\end{minipage}
\end{enumerate}
\end{multicols}

\begin{solution}
\textbf{Réponse c.} En effet, dans ce code, on initialise \texttt{i} à \texttt{A-1} donc $i<A$. On entre donc dans la boucle et \texttt{i} diminue de 1. Donc $i<A$ encore une fois... On reste donc dans la boucle tout le temps car \texttt{i} sera toujours plus petit que \texttt{A}.
\end{solution}

\item On considère la fonction suivante :
\begin{lstlisting}
def f(t,i):
	im = i
	m = t[i]
	for k in range(i+1, len(t)):
		if t[k] < m:
			im, m = k, t[k]
	return im
\end{lstlisting}

Que vaut l'expression \texttt{f([ 7, 3, 1, 8, 19, 9, 3, 5 ], 0)} ?

\begin{multicols}{4}
\begin{enumerate}
\item 1
\item 2
\item 3
\item 4
\end{enumerate}
\end{multicols}

\begin{solution}
\textbf{Réponse b.} Exécutons pas à pas ce code :
\begin{center}
\begin{tabular}{|>{\ttfamily}c|>{\ttfamily}c|>{\ttfamily}c|>{\ttfamily}c|}
\hline\rowcolor{gray!80!blue}
k & t[k] < m  & im & m  \\
\hline
 &  & 0 & 7\\
\hline
1 & 3 < 7 : vrai & 1 & 3\\
\hline
2 & 1 < 3 : vrai & 2 & 3\\
\hline
3 & 8 < 3 : faux & 2 & 3\\
\hline
4 & 19 < 3 : faux & 2 & 3\\
\hline
\multicolumn{4}{|l|}{etc.}\\
\hline
\end{tabular}
\end{center}
On recherche donc ici l'indice du premier minimum de la liste.
\end{solution}

\item Dans le quadrillage ci-dessous, 14 points sont dessinés, dont 7 de la classe C1, avec des ronds noirs , et 7 de la classe C2, avec des losanges.


\begin{center}
\begin{tikzpicture}
\draw[gray,dashed] (0,0) grid (8,6);
\foreach \x/\y in { 1/1,
					1/2,
					1/4,
					2/1,
					3/1,
					3/3,
					3/4}
{
\fill (\x,\y) circle (2pt);
}

\foreach \x/\y in { 4/1, 4/2, 4/4, 5/1, 6/2, 7/2, 7/3}
{
\draw[very thick] ($(\x,\y)+(0,\d)$)--($(\x,\y)+(-\d,0)$)--($(\x,\y)+(0,-\d)$)--($(\x,\y)+(\d,0)$)--($(\x,\y)+(0,\d)$);
}
\draw[red,very thick] (3.9,4.9)--(4.1,5.1);
\draw[red,very thick] (3.9,5.1)--(4.1,4.9);
\node[red,above right] at (4,5) {A};
\end{tikzpicture}
\end{center}
On introduit un nouveau point A, dont on cherche la classe à l'aide d'un algorithme des k plus proches voisins pour la distance géométrique habituelle, en faisant varier la valeur de k parmi 1, 3 et 5.
Quelle est la bonne réponse (sous la forme d'un triplet de classes pour le triplet (1,3,5) des valeurs de k) ?

\begin{multicols}{2}
\begin{enumerate}
\item C1, C2, C3
\item C2, C1, C2
\item C2, C2, C2
\item C2, C1, C1
\end{enumerate}
\end{multicols}

\begin{solution}
\textbf{Réponse d.} En effet, 
\begin{itemize}
\item pour $k=1$, le point le plus proche de A est le losange qui est juste en-dessous; donc la classe est C2.
\item pour $k=3$, on cherche les 3 points les plus proches de A : il y a un triangle et deux cercles; la classe prédominante est donc C1.
\item pour $k=5$, il y a 3 cercles et 2 triangles :

\medskip

\begin{center}
\begin{tikzpicture}
\draw[gray,dashed] (0,0) grid (8,6);
\foreach \x/\y in { 1/1,
					1/2,
					1/4,
					2/1,
					3/1,
					3/3,
					3/4}
{
\fill (\x,\y) circle (2pt);
}

\foreach \x/\y in { 4/1, 4/2, 4/4, 5/1, 6/2, 7/2, 7/3}
{
\draw[very thick] ($(\x,\y)+(0,\d)$)--($(\x,\y)+(-\d,0)$)--($(\x,\y)+(0,-\d)$)--($(\x,\y)+(\d,0)$)--($(\x,\y)+(0,\d)$);
}
\draw[red,very thick] (3.9,4.9)--(4.1,5.1);
\draw[red,very thick] (3.9,5.1)--(4.1,4.9);
\node[red,above right] at (4,5) {A};
\clip (0,0) rectangle (8,6);
\draw[thick,orange] (4,5) circle (3.2cm);
\end{tikzpicture}
\end{center}

La classe prédominante est donc C1.
\end{itemize}
\end{solution}
\end{enumerate}

\bigskip

Ce sujet est fourni à titre d'exemple par l'\'Education Nationale.

L'épreuve finale de 1\iere{} NSI (pour les élèves ne souhaitant pas garder cette spécialité en Terminale) ne ressemblera pas nécessairement trait pour trait à ce sujet, mais sera tout de même composée de QCM de ce type.

Le corrigé est de l'auteur de ce document.
\end{document}