\documentclass[11pt]{article}

\usepackage[fleqn]{amsmath}

\usepackage[latin1]{inputenc}
\usepackage[french]{babel}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage[table]{xcolor}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[colorlinks=true,linkcolor=blue,bookmarksnumbered]{hyperref}
\usepackage{fancyhdr}
\usepackage{listings}

\setlength\textwidth{17cm} 
\setlength\oddsidemargin{-0.54cm} 
\setlength\topmargin{-1.24cm} 
\setlength\textheight{23.7cm} 
\setlength\headheight{0.55cm} 
\setlength\headsep{0.5cm} 

\newenvironment{encadrer}[1]{\noindent \textbf{#1 :} \par \begin{center} \begin{tabular}{|p{13cm}|} \hline}{\\ \hline \end{tabular} \bigskip \end{center}}
\newenvironment{sanscadre}[1]{\noindent \textbf{#1 :}\par  \noindent}{\bigskip\par}

\newenvironment{paragraphe}[1]{\noindent \textbf{#1 :}\par \noindent}{\bigskip\par}

\newenvironment{systemedeq}[4]{\left\{ \begin{array}{rcl} #1 & = & #2 \\ #3 & = & #4 \\ \end{array} \right.}


\newcommand{\defref}[2]{\hypertarget{#1}{\emph{\color{red}{#2}}}}
\newcommand{\faireref}[2]{\hyperlink{#1}{#2}}
\newcommand{\nouvitem}{\item[$\bullet$]}
\newcommand{\emphref}[1]{\emph{\color{red}{#1}}}

\newenvironment{Ex}[1]{\noindent \textbf{Exercice #1 :}\par}{\bigskip\par}
\newcommand{\pdfrowcolors}[1]{\rowcolors{1}{#1}{#1}}

\newenvironment{sanscadrec}[2]{\noindent \color{#2}{\textbf{#1 :}}\par \noindent}{\bigskip\color{black}\par}

\newenvironment{cadresimple}{\begin{tabular}{|p{15cm}|} \hline}{\\ \hline \end{tabular}\bigskip \par}
\newenvironment{fauxcadre}{\begin{tabular}{l}}{\\ \end{tabular}\bigskip \par}

\renewcommand{\footrulewidth}{0.4pt}

\title{Cours d'algorithmique et de programmation pour la classe de seconde}


\author{F.Gaudon}

\usepackage[french,lined,boxed]{algorithm2e}

%\ configuration package algorithm
\SetKw{Retour}{afficher}
\SetKwBlock{Traitement}{Début traitement}{Fin traitement.}
\SetKw{Var}{Variables}
\SetKw{stocker}{stocker}
\SetKw{dans}{dans}
\SetKw{allant}{allant de }
\SetKw{aBoucle}{ à }
\SetKw{saisir}{saisir}
\SetKw{afficher}{afficher}

\begin{document}
\pagestyle{fancy}
\fancyfoot[R]{\includegraphics[width=2cm]{88x31.png}}
\fancyfoot[C]{\thepage}
\fancyfoot[L]{\textit{\color{black}\url{http://mathsfg.net.free.fr}}}
\maketitle


\section{Distinction entre algorithmique et programmation}

\begin{encadrer}{Définition}
Un \emphref{algorithme} est une succession \emphref{d'instructions} (aussi appelés \emphref{commandes}) permettant la résolution d'un problème donné.
\end{encadrer}

\begin{sanscadre}{Remarque}
Le terme \og{}algorithme\fg{} vient du nom du mathématicien arabe du IX\up{e} siècle \emphref{Al Khwarizmi} qui écrivit une des premières méthodes systématiques de résolution de certaines équations.
\end{sanscadre}

\begin{sanscadre}{Exemple}
\texttt{Stocker dans b le carré de a ;}\\
\texttt{afficher b.}\\
L'algorithme précédent stocke dans \og{}une boîte\fg{} nommée $b$ le carré d'un nombre nommé $a$ et affiche la valeur contenue dans $b$.
\end{sanscadre}


\begin{encadrer}{Définition}
Un \emphref{Langage de programmation} est une ensemble d'instructions et de règles syntaxiques compréhensibles par un ordinateur et permettant de créer des algorithmes. Un \emphref{programme} est la traduction d'un algorithme dans le langage de programmation utilisé.
\end{encadrer}

\begin{sanscadre}{Exemples}
BASIC, PASCAL, C++, assembleur sont des langages de programmation.\\
En particulier, les calculatrices Texas Instrument et Casio mettent à disposition un langage de programmation provenant du langage BASIC mais avec des instructions plus limités.\\
Dans ce cours, nous utiliserons le langage de programmation \emphref{python}.\\
C'est un langage qui présentent les intérêts suivants 
\begin{itemize}
\nouvitem C'est un langage \emphref{libre}, c'est à dire que n'importe qui ayant les compétences techniques nécessaires peut l'adapter à ses besoins ou contribuer à le perfectionner ;
\nouvitem il est \emphref{multi-plateformes}, c'est à dire qu'un programme écrit en python fonctionnera aussi de la même manière sur des ordinateurs sous Windows, Linux, MAC OS, Android ou tout autre système d'exploitation ;
\nouvitem il fait partie des langages les plus utilisés dans le monde universitaire et dans le monde professionnel ;
\nouvitem il est réputé pour sa simplicité de programmation.
\nouvitem Les calculatrices récentes des marques les plus courantes (Texas Instrument, Casio et Numworks) permettent de programmer en python.
\end{itemize}
\end{sanscadre}

\begin{sanscadre}{Exemple}
Le programme suivant, que nous apprendrons à comprendre plus tard, est une écriture ou \emphref{implémentation} en python de l'algorithme de calcul de carré précédent :
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
b=a*a
print(b)
\end{lstlisting}
\end{sanscadre}

\begin{sanscadre}{Programmation en python en pratique}
\begin{itemize}
\nouvitem  L'édition d'un programme se fait dans un logiciel d'édition de texte (notepad, wordpad, gedit,...), ou dans un logiciel comprenant à la fois un \emphref{éditeur de texte} et un \emphref{interpréteur python}, ce que l'on appelle une distribution python (Edupython par exemple dont la fenêtre apparaît ci-dessous) :
 \begin{center}
 \includegraphics[width=12cm]{algoProgrammation.png}
 \end{center}
 On peut écrire le programme ligne par ligne dans la \emphref{console}, ou en entier dans \emphref{l'éditeur de programme}.
\nouvitem  Les instructions doivent être séparées par un retour à la ligne. Certains blocs d'instructions seront \emphref{indentés}, c'est à dire qu'ils devront être décalés par rapport à la marge.
\end{itemize}
\end{sanscadre}

\newpage

\section{Les variables, affectations}

\begin{encadrer}{Définition}
 On appelle variable tout emplacement de la mémoire de l'ordinateur ou de la calculatrice dans lequel on stocke une information qui peut être changée. On dit alors qu'on \emphref{affecte} une valeur à la variable. Une variable est donc constituée :
\begin{itemize}
 \nouvitem d'\emphref{un nom} qui permet de reconnaître où elle se situe dans la mémoire de l'ordinateur ou de la calculatrice ;
\nouvitem d'\emphref{une valeur} : le nombre ou plus généralement l'information stockée.
\end{itemize}
Afin que le logiciel du langage de programmation puisse calculer l'espace en mémoire nécessaire pour stocker les valeurs de la variables, on attribue aux variables un \emphref{type} : entier, flottant ($\approx$ décimal), caractère, chaîne de caractère,... .
\end{encadrer}


\begin{sanscadre}{Remarques}
Quelque soit le langage de programmation, un nom de variable doit respecter certaines contraintes :
\begin{itemize}
\nouvitem Les majuscules et les minuscules ne sont pas interchangeables : par exemple \og{}a\fg{} et \og{}A\fg{} ne désignent pas les mêmes variables ;
\nouvitem Un certain nombre de caractères spéciaux sont interdits, il est donc recommandé d'éviter d'utiliser des caractères spéciaux dans les noms de variables : par exemple, \og{}*\fg{} ne doit pas être utilisé dans un nom de variable (confusion possible avec l'opérateur de multiplication). Les espaces sont en outre interdits dans les noms de variables. Il est recommandé d'éviter les lettres accentuées. Les chiffres sont autorisés mais ils ne doivent pas être commencer le nom d'une variable ;
\nouvitem Les mots-clefs du langage de programmation ne peuvent pas être utilisés comme nom de variables : \og{}if\fg{} ou \og{}for\fg{} sont interdits par exemple.
\end{itemize}
\end{sanscadre}

\begin{sanscadre}{Exemple de syntaxe en algorithmique}
$a\leftarrow 3$ signifie que l'on affecte la valeur 3 à la variable $a$.
\end{sanscadre}

\begin{encadrer}{Déclaration des variables}
 Dans un algorithme ou un programme, on commence généralement par énoncer les variables qui seront employées et la nature des données que l'on affectera à la variable : nombres entiers, nombres décimaux, chaînes de caractères. On dit que l'on \og{}déclare\fg{} les variables.
\end{encadrer}

\begin{encadrer}{Premiers types de variables en python}
\begin{itemize}
\nouvitem \texttt{int} : entier relatif (\og{}integer\fg{} en anglais) ;
\nouvitem \texttt{float} : nombre à virgule flottante, $\approx$ décimal ou nombre réel ;
\nouvitem \texttt{bool} : booléen, variable ne pouvant prendre que les valeurs 0 ou 1, \texttt{True} ou \texttt{False} ;
\end{itemize}
La déclaration des types de variables n'est pas indispensable en langage python : l'interpréteur python attribue lui-même autant que possible, le type le plus adapté à la variable lors de la première utilisation. On peut connaître le type d'une variable en python en tapant dans la console \texttt{type(nomDeLaVariable)}.
\end{encadrer}



\begin{sanscadre}{Exemples [Programmation d'affectation en langage python]}
 Le programme suivant donne des exemples d'affectations de variables :
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
a=3	# On affecte la valeur 3 à la variable a
b=a+2 # On affecte la valeur 3+2 donc 5 à la variable b
b=b*b # On affecte la valeur 5*5 donc 25 à la variable b
c=7*b # On affecte la valeur 7*25 donc 150 à la variable c 
\end{lstlisting}
C'est une implémentation en python de l'algorithme suivant :
\begin{algorithm}
\Var{$a$, $b$, $c$ : nombres réels\\}
\Traitement{
$a\leftarrow 3$ ;\\
$b\leftarrow a+2$ ;\\
$b\leftarrow b*b$ ;\\
$c\leftarrow 7*b$ ;\\
}
\end{algorithm}
\end{sanscadre}

\begin{sanscadre}{Remarque}
Les textes qui suivent les symboles \# sont appelés des \emphref{commentaires} : ils sont ignorés par le langage python mais permettent d'expliquer le code.
 \end{sanscadre}

\newpage


\section{Fonctions}

\begin{encadrer}{Définition}
Une \emphref{fonction} en programmation est un bloc d'instructions qui a reçu un nom, dont le fonctionnement dépend d'un certain nombre de \emphref{paramètres} aussi appelés \emphref{arguments} et qui renvoie, éventuellement, un résultat.
\end{encadrer}

\begin{sanscadre}{Syntaxe en langage python}
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def nomDeLaFonction(ArgumentsSéparésParDesVirgules):
	instruction
	...
	instruction
	return résultatEventuel
\end{lstlisting}
\end{sanscadre}


\begin{sanscadre}{Exemples [Programmation de fonctions en langage python]}
\begin{itemize}
\nouvitem La fonction suivante renvoie le carré d'un nombre réel $a$ donné : 
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def calculCarre(a):
	return a*a
\end{lstlisting}
\nouvitem La fonction suivante renvoie le périmètre d'un rectangle de dimensions $L$ et $l$ données :
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def perimetre(l,L):
	p=2*L+2*l
	return p
\end{lstlisting}
\end{itemize}
Note : Pour pouvoir utiliser ces fonctions dans une distribution python (par exemple Edupython), les taper dans l'éditeur de programmes, les éxécuter, puis taper le nom de la fonction dans la console avec les paramètres : \texttt{calculCarre(5)} ou \texttt{perimetre(5,9)}.
\begin{center}
\includegraphics[width=12cm]{algoProgrammationImageFonctions.png}
\end{center}
\end{sanscadre}

\newpage

\section{Structures conditionnelles}

\subsection{Si..alors..sinon}

\begin{encadrer}{Définitions}
Ces instructions permettent de tester si une condition est vraie ou fausse et de poursuivre le programme d'une manière différente selon que la condition est vraie ou fausse.
\end{encadrer}

\begin{sanscadre}{Syntaxe en algorithmique}
\fbox{Si} \\
\texttt{condition}\\
\fbox{Alors} \\
\texttt{	instructions si condition vraie}\\
\fbox{Sinon}\\
\texttt{	instructions si condition fausse}\\
\fbox{FinSi}\\
\end{sanscadre}

\begin{sanscadre}{Syntaxe en langage python}
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
if condition :
	instruction
	...
	instruction
else:
	instruction
	...
	instruction
\end{lstlisting}
\end{sanscadre}

\begin{sanscadre}{Exemple [Programmation de conditions en langage python]}
La fonction suivante permet de tester si une température dépasse le seuil d'ébullition:
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def testEbullition(T):
	if T>=100:
		return True
	else:
		return False
\end{lstlisting}
Elle renvoie comme résultat un booléen c'est à dire une variable ne pouvant prendre que les valeurs \texttt{True} \og{}Vrai\fg{} ou \texttt{False} \og{}Faux\fg{}.
\end{sanscadre}

\newpage


\subsection{Opérateurs relationnels et logiques}

\begin{encadrer}{Définition}
Pour tester une condition on utilise les \emphref{opérateurs relationnels} suivants :
\begin{itemize}
 \nouvitem $a=b$ teste l'égalité de $a$ et de $b$ ;
\nouvitem $a<b$ teste si $a$ est strictement inférieur à $b$ ;
\nouvitem $a\leq b$ teste si $a$ est inférieur ou égal à $b$ ;
\nouvitem $a> b$ teste si $a$ est strictement supérieur à $b$ ;
\nouvitem $a\geq b$ teste si $a$ est supérieur ou égal à $b$ ;
\nouvitem $a\neq b$ teste si  $a$ est différent de $b$.
\end{itemize}

On utiliser ausi pour les conditions plus complexes les opérateurs logiques "et" ("AND"), "ou"("OR") et "non" ("not").
\end{encadrer}


\begin{sanscadre}{Syntaxe en langage python}
 \begin{itemize}
 \nouvitem \texttt{a==b} teste l'égalité de $a$ et de $b$ ;
\nouvitem \texttt{a<b} teste si $a$ est strictement inférieur à $b$ ;
\nouvitem \texttt{a<=b} teste si $a$ est inférieur ou égal à $b$ ;
\nouvitem \texttt{a>b} teste si $a$ est strictement supérieur à $b$ ;
\nouvitem \texttt{a>=b} teste si $a$ est supérieur ou égal à $b$ ;
\nouvitem \texttt{a!=b} teste si  $a$ est différent de $b$ ;
\nouvitem \texttt{condition1 \&\& condition2} qui peut aussi s'écrire \texttt{condition1 and condition2} teste si les deux conditions sont vraies simultanément ;
\nouvitem \texttt{condition1 || condition2} qui s'écrit aussi \texttt{condition1 or condition2} teste si l'une au moins des deux conditions est vraie ;
\nouvitem \texttt{!condition} teste si la négation de la condition est vraie.
 \end{itemize}
 \end{sanscadre}
 
\begin{sanscadre}{Exemple [Programmation de conditions en langage python]}
Le programme suivant teste si une personne vérifie les conditions pour se présenter à une élection municipale : la personne doit être majeure et éligible.
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def candidatMunicipales(age,eligibilite):
	if (age>=18) and eligibilite==True:
		return 'oui'
	else:
		return 'non'
\end{lstlisting}
On remarquera qu'ici, la fonction renvoie comme résultat une chaîne de caractère : \og{}oui\fg{} ou \og{}non\fg{}. On aurait pu renvoyer un booléen \texttt{True} ou \texttt{False} à la place.
\end{sanscadre}
 
\newpage

 \section{Boucles}
 
\subsection{Boucles bornées \og{}for\fg{}}

\begin{encadrer}{Définition}
 Ces instructions sont utilisées pour contrôler les boucles en incrémentant (augmentant) une variable lorsque l'on connaît le nombre de répétitions. La variable est augmentée d'une valeur de départ jusqu'à une valeur d'arrivée d'un pas donné (l'incrément).
\end{encadrer}

\begin{sanscadre}{Syntaxe algorithmique}
\fbox{Pour}\\
\texttt{variable}\\
\fbox{allant de}\\
\texttt{valeur de départ}\\
\fbox{à}\\
\texttt{valeur d'arrivée}\\
\fbox{faire}\\
\texttt{instructions}\\
\fbox{fin}
\end{sanscadre}
 
 \begin{sanscadre}{Syntaxe en langage python}
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
for nomDeLaVariableCompteur in range(valeurDeDépart,valeurArrivée+1):
	instruction
	...
	instruction
\end{lstlisting}
\end{sanscadre}

\begin{sanscadre}{Exemple [Programmation d'une boucle bornée en langage python]}
Le programme suivant permet d'obtenir la somme des n premiers entiers $1+2+...+n$ où $n$ est donné.
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def sommeEntiers(n):
	somme=0
	for k in range(0,n+1):
		somme=somme+k
	return somme
\end{lstlisting}
\end{sanscadre}

\newpage

\subsection{Boucles non bornées \og{}while\fg{}}


\begin{encadrer}{Définition}
 \'Exécute un groupe de commandes tant qu'une condition est vraie. On l'utilise donc lorsque l'on ne connaît pas à l'avance le nombre de répétitions. La condition est testée en début de boucle donc si la condition est vraie lorsqu'elle est testée en début de boucles, \emph{toutes} les instructions contenues à l'intérieur de la boucle sont effectuées.
\end{encadrer}
\begin{sanscadre}{Syntaxe}
\noindent \fbox{Tant que} \texttt{condition}\\
\texttt{instructions}\\
\fbox{faire}\\
\texttt{instructions}\\
\fbox{fin tant que}
\end{sanscadre}

\begin{sanscadre}{Syntaxe en langage python}
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
while condition:
	instruction
	...
	instruction
\end{lstlisting}

\end{sanscadre}

\begin{sanscadre}{Exemple [Programmation d'une boucle non bornée en python]}
Le programme suivant permet d'obtenir le nombre de multiplications par 2 nécessaires pour atteindre le nombre $n$ donné à partir du nombre 1 :
\begin{lstlisting}[language=python,frame=single,keywordstyle=\color{blue},numberstyle=\color{green},stringstyle=\color{orange},identifierstyle=\color{purple}]
def seuil(n):
	k=1
	i=0
	while (k<n):
		k=k*2
		i=i+1
	return i
\end{lstlisting}
\end{sanscadre}

\end{document}
