# Algorithmique impérative/Version imprimable

* Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
* Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
* Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.
Une version à jour et éditable de ce livre est disponible sur Wikilivres, une bibliothèque de livres pédagogiques, à l'URL : https://fr.wikibooks.org/wiki/Algorithmique_imp%C3%A9rative
Problème à régler : il faut trouver un moyen de distinguer les trois parties principales, or il n'y a pas de niveau au dessus de = titre =

# Avant-propos
## Introduction

« Les ordinateurs sont inutiles, ils ne savent que donner des réponses. » (Pablo Picasso).

## À qui s'adresse ce livre ?

Ce livre s'adresse aux étudiants démarrant une formation autour de l'informatique théorique, c'est à dire principalement dans un cadre universitaire, en début de premier cycle.
Ce livre n'a pas pour objectif d'enseigner la programmation vite fait bien fait, à des lecteurs qui voudraient obtenir des résultat rapidement. Si vous souhaitez apprendre à programmer et être vite opérationnel, la présente lecture vous ennuiera et ne vous mènera pas là où vous voulez aller. Nous vous recommandons particulièrement de vous tourner vers un ouvrage tel que « Programmation Python » qui devrait parfaitement convenir.

## Conseils de lecture

Selon vos motivations, vous n'aborderez pas le sujet de la même façon :

### aux étudiants débutant une licence universitaire en informatique

    il s'agit ici d'aborder les fondations du savoir que vous allez acquérir tout au long de votre cursus. Ne le négligez à aucun prix (au niveau international, on peut parler des formations en Computer sciences)

### aux étudiants débutant une formation d'ingénieur ou une préparation aux écoles d'ingénieurs

    pour ces étudiants : l'importance de notre sujet dépend de la proximité de la formation avec l'informatique.

### aux étudiants universitaires des formations scientifiques "pures"

    mathématiciens, physiciens, chimistes, biologistes... : vous aborderez peut-être ce sujet comme première approche de l'informatique. Il ne vous sera pas familier de prime abord mais c'est néanmoins un sujet scientifique qui ne devrait donc pas vous dérouter étant donné votre bagage mathématique. Il y a sûrement des étudiants en informatique sur votre lieu de formation (UFR, faculté...) : profitez de leur caractère habituellement accueillant ; vous pourrez sûrement trouver des étudiants informaticiens qui seront ravis de vous aider. Si vous avez accès à une bibliothèque universitaire, elle contient sûrement des ouvrages qui peuvent vous servir. Conseil : certains problèmes posés seront peut-être trop « matheux » pour vous. Travaillez plutôt les exercices proposés dans votre formation qui traiteront de notions plus familières.

### aux linguistes

    vous allez surement être rebutés par ces lectures bien éloignées de votre littérature habituelle. Néanmoins, sachez qu'il n'y a que peu de prérequis à cette étude et que vos « faibles » acquis mathématiques (disons de niveau baccalauréat Série L pour la France) seront suffisants. Conseil : jetez un œil aux premiers problèmes posés mais ne vous souciez pas des suivants trop « matheux » pour vous. Attachez-vous cependant à bien comprendre ce nouveau langage, sa syntaxe et sa sémantique en insistant sur la partie « Théorie de l'algorithmique impérative ».

### aux étudiants de formations professionalisantes BTS, DUT en rapport direct avec l'informatique

    vous allez en fait apprendre un (plusieurs ?) langage(s) impératif(s) dans votre formation. Cependant, vous allez surtout aborder l'aspect « pratique » des choses. Ce wikilivre vous permettra de prendre de la hauteur par rapport à vos programmes et de les voir de façon plus abstraite. Concrètement, vous utiliserez votre langage au mieux parce que vous verrez mieux les simplifications possibles : cela allégera d'autant votre travail. Conseil : ne vous concentrez pas trop sur la syntaxe du langage théorique qui sera présenté dans cette ouvrage (vous aurez tôt fait de l'oublier). En effet, vous apprendrez sûrement un ou plusieurs langages dans votre formation (apprenez-les bien, car buter sur des questions de syntaxe est aussi tragique que buter sur des fautes de français au cours d'une dissertation de philosophie). Concentrez-vous donc plutôt sur l'aspect algorithmique des problèmes : comment cela se déroule, comment obtient-on le résultat (...simplement) sans vous soucier du langage que nous allons utiliser. Prenez quand même le temps de faire le parallèle entre les deux langages : cela ne devrait pas prendre trop de temps ni être trop difficile, étant donné que les langages reprennent des concepts les uns aux autres (concepts que nous avons généralisés ici dans notre langage théorique : les similitudes devraient être assez flagrantes).

## À propos de cet ouvrage

L'algorithmique impérative est souvent la première forme d'algorithmique que l'on aborde car elle est la plus intuitive. C'est en fait l'abstraction des concepts propres aux langages de programmation impératifs. L'étude de l'algorithmique impérative permet donc d'aborder les langages typiquement impératifs d'une façon plus rigoureuse.
Afin d'aborder le sujet de façon complète, ce document se compose de trois parties :
* Une partie théorique qui présente les divers aspects de l'algorithmique impérative et la façon de les exploiter.
* Une partie sur les outils de travail de l'algorithmicien.
* Des problématiques concrètes, une analyse simple puis approfondie du problème et de ses solutions.

## Petit historique

Comme dans tout cours scientifique qui se respecte, il serait judicieux de contextualiser ce que nous allons aborder dans cet ouvrage. L'étude étant assez fastidieuse, nous allons la réduire au strict minimum. Surtout pour une science si jeune et si vieille à la fois. Ce que nous abordons exploite des concepts dont le plus récent est la Programmation structurée, concept d'Edsger Dijkstra qui publia à ce sujet en 1968. La justesse de ses conclusions rendit la programmation structurée populaire dès 1970. Bien qu'aujourd'hui de nouveaux concepts soient apparus, les conclusions d'Edsger Dijkstra n'ont jamais été remises en cause et ces principes sont encore en œuvre dans les langages de programmation actuels. Nous voici satisfaits pour la partie humaine, quitte à ne retenir qu'une date et un nom, en voici de bons.
Pour la partie technique maintenant, le langage de programmation Pascal, que nous aborderons tout au long de l'ouvrage, a été développé par Niklaus Wirth dans les années 1970 pour suivre dans les faits les théories de Dijkstra. Il a été créé avant tout, à des fins pédagogiques, afin d'éviter d'enseigner la programmation structurée avec un langage de l'époque, qui ne respecterait pas ces concept alors nouveaux. Pour l'anecdote, vous vous en doutiez sûrement, ce nom a été choisi en hommage au mathématicien français Blaise Pascal.
Désolé d'avoir fait si court, nous vous invitons à lire les articles Programmation impérative et Pascal sur Wikipédia.

# Qu'est ce qu'un algorithme impératif
## Première approche

On peut faire le parallèle entre un algorithme et une recette de cuisine. La recette donne les indications nécessaires pour transformer, étape par étape, des ingrédients de départ en un plat prêt à servir. En suivant la recette, le cuisinier en transpose le texte en actions concrètes. Il en va de même pour l'algorithme : une fois qu'on l'a écrit, on le donne à l'ordinateur qui va le suivre étape par étape, cette fois-ci pour transformer des données de départ en données d'arrivée : les résultats.
Attention toutefois, ce parallèle donne une idée générale mais cache quelques subtilités. En effet, si le cuisinier peut faire deux choses en même temps (faire cuire quelque chose au four pendant qu'il épluche autre chose), l'ordinateur, lui, ne fait qu'une seule chose à la fois.
L'objectif de ce livre est donc d'apprendre à écrire des recettes qu'un ordinateur pourra comprendre. Cela implique le respect des règles d'un langage que nous allons apprendre. Nous pourrons ainsi écrire des recettes qui seront en fait des méthodes pour résoudre des problèmes ou calculer des résultats. L'ordinateur pourra alors suivre la recette et donner les résultats, après avoir effectué tous les calculs (fastidieux) à votre place. Un objectif concret est tout simplement de pouvoir assigner à un ordinateur une tâche trop rébarbative pour en débarrasser un humain.

## Définition

Tout d'abord, un algorithme impératif est une séquence d'actions. C'est une séquence car les actions s'effectuent les unes après les autres et non en même temps.
Un algorithme a une fonction, un objectif. Pour cela, il transforme des entrées (aucune, une ou plusieurs) en sorties (une ou plusieurs) : vous lui entrez des données, il vous en sort d'autres.
Distinction algorithme / programme : de l'algorithme découle un programme informatique que l'on peut exécuter sur une machine. Le programme informatique est une traduction de l'algorithme dans un langage de programmation (par exemple Pascal). On peut créer plusieurs programmes informatiques différents à partir d'un même algorithme car chaque langage de programmation a ses particularités. On peut donc dire que l'algorithme est théorique, il est l'abstraction du programme informatique.
Par exemple, l'algorithme par lequel on entre deux nombres entiers et qui donne en sortie la somme de ces deux nombres a pour objectif de faciliter le calcul des sommes de deux nombres, opérations qui peuvent être fastidieuses à faire de tête pour un humain.
Il y a dans la vie courante de nombreux exemples d'algorithmes impératifs qui nous donnent des marches à suivre (mathématiques, recettes de cuisine, ...).
Un algorithme complet, pris ci-dessous comme exemple, donne une idée simple de ce qu'on pourra produire à la fin de l'étude de l'algorithmique impérative. Tous les concepts mis en œuvre dans cet algorithme sont expliqués plus loin, ne vous inquiétez donc pas si certains aspects vous échappent pour l'instant.
Cet algorithme calcule et affiche le périmètre, l'aire et le volume du cercle ou de la sphère dont le rayon est donné par l'utilisateur :
À la fin de l'apprentissage proposé dans ce livre, vous serez à même de créer ce genre d'algorithme et d'autres bien plus complexes.

# Les types, les opérateurs et les expressions

Nous entrons maintenant dans le vif du sujet. Cette première partie est plutôt abstraite et une fois que vous l'aurez étudiée, peut entrainer une sensation de confusion sans application pratique concrète. À cet effet, vous trouverez en fin de document une partie « Ce qu'il faut retenir ». Lors de votre première lecture, n'essayez pas de comprendre mais plutôt d'admettre. Une seconde lecture vous permettra d'avoir une vue d'ensemble et de constater qu'en fait, tout se tient.

## Première approche

Un type est la façon de comprendre la signification d'une donnée. Prenons la donnée 4 : elle peut être de type entier (de valeur 4 : 3+1), de type caractère (le caractère "4"), est-ce un réel... ?
Un opérateur transforme des données. Par exemple, la somme est un opérateur qui transforme des données en une autre donnée. Il convient de se demander sur quel(s) type(s) un opérateur fonctionne. Par exemple, la somme de deux données de type "entier" est de type "entier". On peut donc supposer que la somme de deux données de type "réel" sera de type "réel" (rassurez-vous : ce sera le cas). Qu'en est-il de la somme de deux données de type "caractère" et de la somme d'une donnée de type "réel" et d'une autre de type "entier" ?
Une expression est une combinaison d'opérateur et de données. Par exemple "4+3" est une expression comportant un opérateur et deux données de type "entier". Toutes les expressions ont une valeur, "4+3" a la valeur 7 ; 7 est une donnée de type "entier".
Nous avons donc trois notions différentes, mais liées entre elles par des règles que nous allons voir.

## Spécification

Chaque type a donc son ensemble de valeurs possibles et des opérateurs qui lui sont propres. Par exemple, le type entier qui peut prendre des valeurs telles que 10 ou 12345...
Les opérateurs sont des fonctions mathématiques et à ce titre, ils ont un espace de départ et un espace d'arrivée. Cette propriété s'étend aux opérateurs puisque chaque opérateur à un ou plusieurs types de départ (fonction à une ou plusieurs variables) et un type d'arrivée.
Prenons la fonction mathématique « somme ». On pourrait noter : somme : ℕ² → ℕ : x,y → x+y. De la même façon, l'opérateur somme ajoute deux données de type "entier" et renvoie un "entier". Remarquez que "a+b" est une notation de somme(a,b).
Pour chaque opérateur que vous découvrez ou utilisez, demandez-vous toujours quels sont les types de départ et d'arrivée. Beaucoup d'erreurs sont dues à des opérateurs mal utilisés.
Une expression est donc une suite d'opérateurs et de données qui doit respecter les règles imposées par l'usage des opérateurs.
Dans notre cours nous allons introduire cinq types, les plus couramment utilisés en informatique :
* entier
* réel
* caractère
* chaîne de caractères
* booléen
Ce(s) dernier(s) vous est (sont) probablement étrangers : ne vous inquiétez pas, nous allons y revenir.

## Les entiers et les réels

Voici deux types fidèles à leur définition mathématique.
Les opérateurs sur les entiers sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division entière. Un dernier opérateur est l'opérateur mod, donnant le reste de la division entière. Tous ces opérateurs prennent deux données de type "entier" pour en renvoyer une autre du même type. (Rappel : a = (a / b)*b + a mod b)
Les opérateurs sur les réels sont "+", "-" "*" "/", respectivement la somme, la différence, la multiplication et la division. Tous ces opérateurs prennent deux données de type "réel" pour en renvoyer une autre du même type.
Il convient de se demander ce qu'il se passe quand on considère l'expression "a+b" avec a entier et b réel. Cela est censé ne jamais arriver. Néanmoins, on pourra considérer que l'entier se transforme en réel avant l'opération.

## Les caractères et les chaînes de caractères

Un caractère est tout simplement une lettre, un chiffre ou un symbole : par exemple, "1", "a", "A", "|" sont des caractères.
Aucun opérateur n'existe sur les caractères, ayant un caractère pour résultat. Dans certains langages de programmation, il peut exister des opérateurs pour ajouter un caractère à une chaîne de caractères.
Une chaîne de caractères est une suite de caractères telle que décrite précédemment. "1", "1abc" (par exemple) sont des chaînes de caractères. À noter que "" est une chaîne de caractères (la seule comportant 0 caractère).
Il n'existe qu'un seul opérateur sur les chaînes. Il s'agit de l'opérateur de concaténation qu'on notera "+". La concaténation revient à mettre la seconde chaîne à la suite de la première.
Par exemple "abc"+"def" est équivalente a "abcdef". Remarquez que l'opérateur de concaténation, même s'il est noté "+", n'est pas commutatif comme l'est la somme, nous n'avons évidemment pas a+b=b+a.
Attention, par la suite, à ne pas confondre 1+2 qui est l'entier de valeur 3 avec "1"+"2" qui est la concaténation des chaînes "1" et "2" qui vaut "12" (et sûrement pas "3").
Il n'existe pas de convention pour désigner l'opérateur de concaténation. Nous pourrons également utiliser la notation ".".
Bien que cela ne doive pas arriver, nous pouvons considérer que l'opération de concaténation effectuée sur des caractères fonctionne et donne une chaîne de caractères.

## Introduction à l'arithmétique booléenne

En informatique on introduit un nouveau type un peu moins familier : le booléen. Au même titre que les entiers ou les réels : un booléen peut prendre un ensemble de valeurs et possède ses propres opérateurs.
Il n'est donné ici que quelques explications (nécessaires et suffisantes pour la suite du cours) sur le booléen. Il existe cependant toute une algèbre permettant de travailler sur les booléens. Un complément essentiel de ce cours d'algorithmique impérative est l'étude de l'algèbre de Boole.

### Première approche

En mathématiques, les entiers ont été invités pour dénombrer, les réels pour représenter les distances, les volumes, etc... Le booléen a également pour utilité de représenter le réel. Il sert à représenter la véracité, c'est à dire à déclarer si une chose est vraie ou fausse.
L'ensemble des valeurs possibles d'un booléen est de deux (!). Ces deux valeurs sont notées VRAI et FAUX.
Voici deux exemples comportant des informations représentées par des booléens :
Premier exemple : Supposons que E soit en ensemble qui contient les éléments a, b, c et d.
* L'information cardinal de E est une information qui peut être représentée par un entier (ici 4).
* L'information b appartient à E est une information qui peut être représentée par un booléen (ici VRAI).
* L'information e appartient à E est une information qui peut être représentée par un booléen (ici FAUX).
* L'information 'E comporte au moins 2 éléments est une information qui peut être représentée par un booléen (ici VRAI).
Second exemple : Prenons l'ascenseur d'un immeuble.
* L'information nombre de personnes dans l'ascenseur peut être représentée par un entier.
* L'information il y a au moins une personne dans l'ascenseur peut être représentée par un booléen.
* L'information l'ascenseur est au premier étage peut être représentée par un booléen.
* etc.
Vous voyez donc qu'un booléen peut servir à représenter une multitude d'informations différentes mais ne remplace pas les entiers, les réels ou tout autre type. Chaque type à un usage et il convient d'user du booléen a bon escient tout comme on ne représente pas une distance avec un entier ou un dénombrement avec un réel.

### Opérateurs booléens

Au même titre que pour les autres types, il existe des opérateurs sur les booléen. Nous avons vu que la somme était un opérateur qui prenait deux entiers et renvoyait un résultat de type entier également. Il en va de même pour les booléen.
| Opérateur | noté | Type des paramètres | Type du résultat | Valeur du résultat | Exemple | Remarque |
| négation | non ou ¬ | un booléen | un booléen | Si VRAI alors FAUX. Si FAUX alors VRAI | non(VRAI) a pour résultat FAUX non(FAUX) a pour résultat VRAI | non est une fonction mathématique dite réciproque : non(non(truc)) vaut truc. |
| conjonction | et | deux booléens | un booléen | Le résultat vaut VRAI seulement si les deux paramètres sont VRAI. FAUX sinon. | VRAI et VRAI a pour résultat VRAI VRAI et FAUX a pour résultat FAUX | On pourra aussi dire "Pour que le résultat soit VRAI il faut que tous les paramètres soient VRAI". |
| disjonction | ou | deux booléens | un booléen | Le résultat vaut VRAI si au moins un des deux paramètres est VRAI. FAUX si tous les paramètres sont FAUX | VRAI ou VRAI a pour résultat VRAI VRAI ou FAUX a pour résultat VRAI | |
Vous en serez déjà arrivé à ces conclusions : si b est un booléen,
* b et FAUX vaut FAUX quel que soit b
* b ou VRAI vaut VRAI quel que soit b
Ces opérateurs peuvent bien sûr former des expressions. Quelques exemples :
* non(non(FAUX)) vaut FAUX
* ((VRAI et FAUX) ou VRAI) vaut VRAI
La négation est prioritaire sur la conjonction. La conjonction est prioritaire sur la disjonction.

## Tableau récapitulatif

Tableau récapitulatif des types et de leurs opérateurs :
| Type | Ensemble de valeurs | Opérateurs |
| Entier | ℕ | + (somme), - (différence), * (multiplication), / (division entière) |
| Réel | ℝ | + (somme), - (différence), * (multiplication), / (division) |
| Booléen | {VRAI ; FAUX} | ¬ (négation), et (conjonction), ou (disjontion) |
| Caractère | | |
| Chaîne de caractères | | Concaténation |

## Ce qu'il faut retenir

Ce chapitre est abstrait et ne donne rien de concret. N'apprenez pas par cœur, tout ceci se tient et est assez cohérent par rapport à ce que vous avez appris sur les mathématiques. Voici ce qui doit retenir votre attention :
* Retenez les noms des différents types et de leurs opérateurs en retenant bien quel opérateur fait quoi et avec quoi. Vous devriez pouvoir reconstruire de tête le tableau récapitulatif (encore une fois, vous ne devriez pas avoir à l'apprendre, vous devriez pouvoir le déduire des types).
* Retenez que les booléen, les caractères et les chaînes de caractères et leurs opérateurs fonctionnent exactement de la même façon que les entiers et les réels. Ce sont des types, qui ont un ensemble de valeurs possibles et des opérateurs spécifiques. On peut écrire des expressions à condition de respecter certaines règles.
* Essayez de voir un peu comment on manipule cette arithmétique booléenne qui, comme l'arithmétique entière, vous permet de calculer des expressions et d'en simplifier d'autres. Remarquez que cette arithmétique est plus simple puisque vous n'avez que deux valeurs possibles (c'est peu par rapport à l'infinité d'entiers...).
* Vous pouvez déjà faire les exercices sur ce chapitre. Si vous avez su les résoudre sans relire ce cours.

# Les constantes, les variables

Dans un algorithme, il faut stocker les données à traiter. Certaines de ces données sont connues et ne varieront pas tout le long de l'algorithme : il s'agit des constantes. D'autres données peuvent être inconnues (elle seront fonction du choix de l'utilisateur, ou du temps...) ou susceptibles d'évoluer au cours de l'algorithme : il s'agit des variables.

## Les variables

Toutes les variables ont un type. Dans chaque algorithme, toutes les variables et leurs types sont explicitées dans le lexique. On dit que la variable est déclarée.
D'un point de vue mathématique, la déclaration revient à l'expression "Soit ... un ...".
Le lexique est noté comme suit :

### Un exemple

Dans cet exemple, nous avons cinq variables.
Du point de vue mathématique, on aurait pu énoncer "Soit n un entier", "Soit 1 un réel", "Soit vrai ou faux booléen", etc.

## Les constantes

De la même façon, les constantes sont déclarées dans une partie Constantes de cette façon :

### Un exemple

À priori, on peut considérer que PI ne risque pas de changer de valeur pendant un algorithme. On peut donc déclarer PI en tant que constante.
Une seule constante est déclarée.

# Les instructions, les blocs d'instructions

Nous avons vu qu'un algorithme est une séquence d'instructions ; de quoi s'agit-il exactement ? Les instructions sont les actions devant être effectuées par l'algorithme. Elle peuvent requérir que l'on précise certaines informations.

## Deux instructions de base

Voici expliquées deux instructions que l'on retrouvera très fréquemment dans des algorithmes. Il s'agit des instructions Afficher et Lire.

### Afficher

Afficher permet d'afficher des données à l'écran et ainsi de communiquer avec l'utilisateur. Pour cette instruction, on doit préciser une expression qui sera évaluée avant d'être affichée.
Quelques exemples :
Ce programme affiche :
Si l'algorithme contient
Le programme
affiche

### Lire

La fonction Lire permet de demander à l'utilisateur de fournir des informations. Chaque information donnée par l'utilisateur est stockée dans une variable (attention au type !). Vous précisez cette variable dans les parenthèses.
Un exemple : nous réalisons un algorithme qui demande à l'utilisateur d'entrer son âge. Tout d'abord il apparaîtra dans le lexique :
Pour demander l'âge :

## Les blocs d'instructions

Souvent, l'exécution d'une seule instruction ne suffit pas pour faire un algorithme complet. Nous pouvons faire en sorte que plusieurs instructions soient considérées comme une seule. Pour cela, il faut créer un bloc d'instructions. Partout où l'on peut mettre une instruction, on peut mettre un bloc d'instructions.
Concrètement, on procède ainsi : les instructions sont séparées par un saut de ligne ou par ;. Le bloc d'instruction est précédé de Début et suivi de Fin.
Un exemple :
Une autre notation, courante dans les langages de programmation, est plus courte. Les instructions formant un bloc sont entre { et }.

# L'assignation

L'assignation est une instruction qui consiste à inscrire dans une variable une valeur calculée depuis une expression. Attention : la nouvelle valeur affectée « écrase » la précédente.
C'est donc la deuxième façon que nous apprenons de donner une valeur à une variable. La première était d'utiliser l'instruction Lire qui permet de demander la valeur à l'utilisateur. On peut dire que l'instruction Lire est une forme particulière d'affectation.
Pour effectuer une assignation, on utilise l'instruction Assigner. On précise entre parenthèses la variable affectée ainsi que l'expression de la valeur de l'affectation.
On pourra également noter l'affectation ← ou :=. Ce symbole peut être énoncé « prend pour valeur ». Attention toutefois à ne pas la noter = bien que certains langages utilisent cette notation. Ce serait un dangereux raccourci de pensée avec les mathématiques (voir la mise en garde ci-dessous).
Un exemple : voici notre lexique
On assigne n :
À partir de maintenant la variable n vaut 12. Ainsi, l'instruction
provoquera l'affichage suivant :
Dans la suite du cours, nous utiliserons la notation ←, moins lourde.

## Mise en garde sur le parallèle avec les mathématiques

Au moment de l'affectation, la valeur affecté est évaluée, c'est-à-dire calculée, les constantes et les variables sont donc remplacées par leurs valeurs respectives.
Exemple : dans le lexique nous avons :
c conserve sa valeur tant qu'elle n'a pas été affectée, le changement de la valeur de b n'affecte pas la valeur de c.
Certains seraient tentés de noter l'affectation avec l'opérateur "=", elle est d'ailleurs notée ainsi dans le langage de programmation C. C'est pourtant une erreur vis-à-vis du sens mathématique de ce symbole. En effet, cette expression :
est tout à fait correcte en informatique si on considère l'affectation notée ainsi ; cela revient à incrémenter x. Mais du point de vue mathématique c'est une aberration. Voyons cela en appliquant une résolution d'équation du premier degré :
$x=x+1$
par soustraction de x dans les deux membres :
$x-x=1$
donc
$0=1$
En revanche, l'affectation notée := est valide en mathématique comme en informatique. En prenant cette convention, tout le monde est content...

# Les exécutions conditionnelles

Vous savez que les instructions s'exécutent les unes après les autres. C'est intéressant mais insuffisant pour élaborer des algorithmes complexes. En effet, nous pourrions avoir besoin d'exécuter certaines instructions seulement dans un certain contexte. Les structures permettant d'imposer la succession des instructions sont appelées structures de contrôles. L'exécution conditionnelle, que nous allons voir ici, est la plus simple de ces structures de contrôles.

## SI...ALORS...

L'exécution conditionnelle permet de n'exécuter une instruction que si une certaine condition est remplie. La syntaxe est la suivante :
* condition est une expression booléenne. L'instruction n'est exécutée que si cette l'expression booléenne est évaluée à VRAI. Si condition est évaluée à FAUX aucune instruction n'est exécutée. Dans les deux cas, le programme poursuit son exécution par ce qui se trouve après le FINSI.
* instruction est une instruction normale. Vous pouvez bien sûr exécuter plusieurs instructions : il suffit pour cela d'un bloc d'instructions.

### Exemples

Cet extrait d'algorithme n'a aucun intérêt. S'il est effacé du programme, on obtient un programme équivalent.
Cet extrait d'algorithme n'a aucun intérêt. Il aurait évidemment suffit d'écrire :

## ...SINON

Il est possible de préciser une instruction à exécuter si la condition n'est pas vérifiée, c'est-à-dire si elle est évaluée à FAUX. Il suffit pour cela d'ajouter une partie SINON entre ALORS et FINSI. Cette partie SINON n'est pas toujours utile, elle est donc facultative.

### Exemples
## Une équivalence utile

Remarquez que ces deux blocs conditionnels sont équivalents :

# Les structures itératives

Les structures de contrôle itératives permettent d'exécuter plusieurs fois de suite une ou plusieurs instructions. Il en existe trois distinctes.

## Structure POUR

La structure POUR permet d'exécuter une instruction un nombre connu de fois. Voici la syntaxe :
i est l'identifiant d'une variable (qui doit bien sûr être déclarée). deb et fin sont deux expressions de même type que i : ce sont les valeurs entre lesquelles i va parcourir l'ensemble des valeurs intermédiaires.
La structure s'exécute de la façon suivante :
* i est affecté à la valeur de deb (i←deb)
* si i est différent de fin alors on exécute instruction
* incrémenter i (i←i+1)
* revenir au point 2
Il est évident que pour que le programme fonctionne deb<fin.

### Exemples
#### Dix itérations

Ce programme va afficher :

## Structure TANTQUE

condition est une expression booléenne, comme dans la structure SI condition ALORS...
Cette structure est exécutée comme suit :
* si condition est vraie : exécuter instruction sinon, continuer après FINTANTQUE
* reprendre au point 1

### La boucle infinie

Il est possible grâce à cette structure de créer une boucle infinie :

### Une boucle POUR

Il est possible de simuler une boucle POUR à l'aide d'un TANTQUE

### Exemples
## Structure REPETER

condition est une expression booléenne.
Cette structure s'exécute comme suit :
* exécuter instruction
* si condition est vrai : continuer au point 3 sinon, reprendre au point 1
* exécuter ce qui suit le JUSQU'A

### La boucle infinie

Il est possible grâce à cette structure de créer une boucle infinie :

### Une boucle POUR

Il est possible de simuler une boucle POUR à l'aide d'un REPETER

### Exemples
## Comment déterminer la structure à utiliser ?

Le choix de la structure de contrôle se fait en fonction du nombre d'itérations à effectuer :
* si le nombre d'itérations est déterminé à l'avance, une boucle POUR est la plus appropriée,
* sinon :
** si la condition de boucle ne peut être évaluée avant la première itération, ou si au moins une itération doit être exécutée, la boucle REPETER est la plus appropriée,
** sinon la boucle TANT QUE est la plus appropriée.

# Les tableaux
## Première approche

Le tableau est un nouveau type. Il contient un ensemble d'éléments indicés par des entiers ; on peut donc utiliser des variables tableaux.
Nous n'étudierons que les tableaux à une dimension également appelés vecteurs.

## Spécification

Les tableaux sont déclarés comme suit :
* tab est l'identifiant de la variable tableau
* DEBUT est un entier : l'indice du premier élément du tableau, généralement 0 ou 1.
* FIN est un entier : l'indice du dernier élément, cela peut être un entier fixé ou, plus intéressant, une constante déclarée.
* On a évidemment FIN > DEBUT
* TYPE est le type de chacun des éléments du tableau.
Par exemple, un tableau d'entiers de 10 cases
On accède au ième du tableau comme suit
* i est un entier qui doit évidemment être compris entre DEBUT et FIN (précisés dans la déclaration de tab)
* la variable tab[i] est donc du type TYPE (précisé dans la déclaration de tab)

## Utilisation

La tableau est utilisé lorsqu'il faut stocker des suites de variables de même rôle. Par exemple, les notes d'un groupe d'étudiants en algorithmique impérative.
La structure POUR se prête très bien au parcours d'un tableau. En supposant le tableau tab déclarer comme suit :
Il suffit pour afficher ses éléments de

# Les procédures et les fonctions
## Première approche

Les procédures et les fonctions sont des sous-programmes qui permettent une réutilisation du code plus facile. En effet, si par exemple on code l'algorithme de calcul de T.V.A. et qu'on l'utilise à divers endroits du programme, plutôt que de recopier le code à chaque fois, il est préférable de créer un sous-programme de calcul. La recopie a toutefois les inconvénients suivants :
* La recopie du code s'accompagne souvent d'un changement des noms de variables, voire de la valeur de certains paramètres,
* Chaque copie du code augmente la taille des programmes source et compilé,
* La maintenance est plus difficile : s'il faut modifier l'algorithme, il faut modifier toutes les copies sans en oublier une seule.
L'utilisation d'un sous-programme évite tous ces problèmes :
* Les sous-programmes utilisent des variables locales et des paramètres formels, c'est-à-dire qu'on leur passe les valeurs (voire les variables, par adresse ou référence) qu'ils doivent utiliser.
* L'algorithme n'est codé qu'une seule fois, ce qui n'augmente pas la taille du programme.
* La maintenance est facilitée par le point précédent : s'il faut modifier l'algorithme, la modification n'a lieu qu'en un seul endroit.

## Procédure et fonction : quelle différence ?

Une procédure traite les informations qu'on lui passe, mais ne retourne, en général, aucun résultat. En général, cette procédure a un effet de bord.
Une fonction traite les informations qu'on lui passe, et retourne un résultat. Si la fonction n'a aucun effet de bord, on peut la comparer à une fonction mathématique.

### Effet de bord

    un sous-programme avec effet de bord modifie l'état global de l'application. En général, appeler deux fois un même sous-programme avec effet de bord en lui passant les mêmes paramètres ne produit pas le même résultat.

# Le type enregistrement
## Première approche

L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type, c'est-à-dire un type qui contient d'autres variables de types déjà définis.

## Spécification

On déclare un nouveau type dans la partie Types comme suit :
on peut ensuite déclarer normalement les variables de ce nouveau type :
Pour accéder à une sous-valeur de la variable, nous utiliserons l'expression :
Cette expression est du type de identifiant_sous_valeur.

### Exemple

Supposons que nous voulions un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :
Supposons maintenant que nous avons le lexique suivant :
Si nous assignons :
Le projet sur les dates propose un travail complet sur le sujet.

## Utilisation

Cela n'est pas obligatoire en algorithmique impérative, mais pour travailler sur un nouveau type , il convient de définir quelques fonctions élémentaires pour créer une variable à partir de ses sous-valeurs. Remarquez que les types de paramètres seront semblables aux types des sous-variables de nouveau type (exception faite dans le cas de sous-valeurs par défaut...).

### Exemple

Pour reprendre notre exemple, nous pourrions créer une fonction :

# L'algorithme au final : vue d'ensemble

Au final, l'algorithme se compose de la façon suivante :
* Algorithme suivi du nom de l'algorithme
* De la déclaration des procédures et des fonctions
* De la déclaration des constantes de l'algorithme principal
* De la déclaration des variables de l'algorithme principal
* De l'algorithme principal

# Exercices
## Types, expressions et opérateurs
### Questions théoriques

* Citez des exemples de types
* Donnez un opérateur polymorphe
* Écrire un programme qui saisit trois nombres dans un ordre donné et les fait sortir dans l'ordre inverse d'entrée.
Solutions :
* booléen, entier, réel, caractère, chaîne de caractères
* + (polymorphe car fonctionne avec des entiers et des réels)

### Types et valeurs

Donner le type des expressions suivantes et leur valeur
* 0
* 1+2
* 0.0+1.0
* "a"
* "a"."b"="b"
* "a"."b"
Donner le type de a et de l'expression :
* a+1
* a."b"
* a=1.0

#### Solutions

* entier : 0
* entier : 3
* réel : 1.0
* caractère : "a"
* booléen : FAUX
* chaîne de caractères : "ab"
Questions avec la variable a :
* entier ; a entier
* chaîne de caractères : a caractère ou chaîne de caractères
* booléen : a réel

### Calcul booléen

Quelle est la valeur de ces expressions booléennes ?
* non(VRAI)
* VRAI et FAUX
* FAUX ou FAUX
* VRAI et VRAI
* non(FAUX ou VRAI)
* FAUX et ((VRAI et VRAI) ou (VRAI et (FAUX ou (VRAI et FAUX)))))
* VRAI ou (VRAI et (FAUX ou ((FAUX et VRAI) ou VRAI)))
a et b sont des booléens, simplifier les expressions :
* non(non(a))
* non(non(non(b)))
* faux ou a
* faux et a
* vrai et a
* vrai ou a
* a et non(a)
* a ou non(a)
* non(a=b) et (a=b)

#### Solutions

* FAUX
* FAUX
* FAUX
* VRAI
* FAUX
* Il suffit de lire "FAUX et ..." au début de l'expression pour savoir tout de suite le résultat. Quel que soit ce qu'il y avait après le et cela aurait été FAUX.
* De même, il suffit de lire "VRAI ou ..." au début de l'expression pour savoir tout de suite le résultat : peu importe ce qu'il y a après le ou, cela aurait été VRAI
Simplifications :
* a
* non(b)
* a
* faux
* a
* vrai
* faux
* vrai
* faux

## Condition

Donner un extrait d'algorithme équivalent à celui-ci sans utiliser de sinon :

### Solution
## Boucles
### 13 à 47

Donner une boucle qui affiche les entiers de 13 à 47
Solution:

### de 5 en 5

Donner une boucle affichant les entiers de 5 en 5 et de 5 à 100
Solutions :
Remarque : ces algorithmes fonctionnent tous mais certains sont plus efficaces que d'autres. Cette réflexion est laissée au lecteur.

## Tableaux

Selon la déclaration suivante
Le tableau contient 11 éléments.

## Procédures et fonctions

Écrire des fonctions en procédures, des procédures en fonctions.

# La rédaction d'un algorithme

Lorsqu'on rédige un algorithme, il faut toujours garder à l'esprit qu'il doit pouvoir être lu et compris par quelqu'un d'autre. Au fur et à mesure de la pratique, les rédacteurs ont dégagé quelques principes dont les plus simples sont expliqués ici. Il convient de respecter ces principes d'une façon rigoureuse.
Remarque pour les étudiants : il est parfaitement admis que le respect de ces règles de rédaction soit pris en compte dans la note finale. Quand vous écrivez une dissertation, il convient de respecter la grammaire et l'orthographe même si ce n'est pas ce qui doit être évalué, il en est de même ici.

## Indenter son code

L'indentation d'une ligne est l'espace qui la sépare de la marge gauche.

### Problème

Considérons l'algorithme (incomplet) suivant :
Voici le même algorithme mais sans l'indentation :
Il est déjà moins évident de comprendre le fonctionnement de l'algorithme. Ce dernier est toutefois plus abordable que :
et pourquoi pas...

### Comment faire

Pour bien indenter, considérez les blocs et mettez au même niveau le début du bloc et la fin du bloc. Par exemple, un fin devrait se trouver au même niveau que son début : on devrait l'apercevoir immédiatement étant donné que tout ce qu'il y a entre les deux devrait se trouver un niveau d'indentation plus loin.
Procédez ainsi avec
* SI...FINSI
* TANTQUE...FTQ
* REPETER...JUSQU'A
* POUR...FP
De même : placez les alors et les sinon au même niveau.
Vous pouvez transformer ces règles, l'important étant de les fixer et de s'y tenir. Il existe plusieurs façons d'indenter et chaque auteur a ses préférences.

## Utiliser des identifiants pertinents

Pour choisir un identifiant de variable ou de fonction, souvenez-vous qu'il doit remplir deux utilités principales
* décrire son rôle (sans toutefois remplacer le commentaire en déclaration)
* distinguer des autres (ne pas se retrouver avec deux fonctions calculer_nombre et calculer_nb, quotient et division...)
Évitez :
* de répéter le type de la variable dans son identifiant (entier_n, chaine_départ)
* les conventions utilisées en maths (n ou x ne suffisent pas pour décrire le rôle d'un entier/réel)
Pensez également aux conventions, notamment :
* i (j, k...) comme variable de boucle
* utiliser un préfixe pour signaler les variables entrées du programme qui seront données par l'utilisateur.

## Commenter utile

Il ne faut pas décrire ce que vous faites mais pourquoi vous le faites
Pour cet algorithme le commentaire :
* (* il y a 24 heures dans une journée donc 24 instructions *) est pertinent. Plus particulièrement, le commentaire répond à la question "pourquoi 24 et pas 25 ?".
* (* i va de 1 à 24 *) n'est pas pertinent. Il ne répond pas à la question "pourquoi 24 et pas 23 ?".
Servez-vous également des commentaires pour indiquer ce que vous supposez : les conditions dans lesquelles votre algorithme fonctionne.

# Travaux pratiques, tester un algorithme sur une machine

« Tester un programme peut montrer la présence de bugs, pas leur absence ». (Edsger Dijkstra : Notes On Structured Programming, 1970)
Le langage de programmation le plus simple permettant d'implémenter directement un algorithme impératif par simple traduction de celui-ci est le langage Pascal, qui a été développé dans cette optique. Ainsi, un travail pratique qui peut accompagner l'apprentissage peut être simplement d'expérimenter des programmes en les recopiant et en visionnant le résultat en situation, sur une machine.

## Prérequis
### Prérequis cognitif

* l'algorithmique impérative, il est évidemment nécessaire d'avoir créé des algorithmes avant de vouloir les mettre sur une machine.
* Utilisation simple de l'ordinateur (édition de texte).

### Prérequis logiciels

Un éditeur de texte : le plus simple suffit. Toutefois, il existe des éditeurs de texte qui facilitent l'édition d'un code source. On les appelle les éditeurs de code-source. En plus du simple éditeur de texte, ils proposent les fonctionnalités suivantes :
* Coloration syntaxique
* Complétion automatique des mots clés
* Numérotation des lignes (vous verrez que c'est indispensable : en effet, si le compilateur trouve une erreur dans votre code source, il vous indiquera le numéro de la ligne où elle se trouve)
* Aide à l'indentation
Quelques éditeurs de code source : Notepad++ (Windows), TextMate (Mac OS), SciTE (Windows et Linux) pour les plus abordables mais aussi emacs, vi (voir la catégorie éditeur de texte sur Wikipédia pour une liste exhaustive).
Un compilateur Pascal : Free Pascal est bon, libre, gratuit et fonctionne sûrement sur votre plateforme.
Un terminal, pour lancer et tester vos programmes. Vous pouvez utiliser un terminal classique sous Linux et Mac OS X. Sous Windows, cela s'appelle « Ligne de commande DOS ».
Il existe des logiciels qui réunissent toutes ces fonctionnalités : éditeur de code + compilateur + terminal. On les appelle les environnements de développement, certains sont complexes mais il en existe de très simples qui vous permettent de compiler le code et de lancer le programme simplement en appuyant sur un bouton. Geany (Linux) est parfait à notre niveau.
Note aux étudiants : votre salle de Travaux Pratiques sera sûrement équipée, votre enseignant vous indiquera comment accéder à tout ça.

### Prérequis matériels

Un ordinateur, n'importe lequel et de n'importe quelle architecture (PC ou Mac), du moment que les prérequis logiciels sont respectés.

## Les limites de l'ordinateur

Un ordinateur est une machine finie (par curiosité, vous pouvez voir la notion d'automate fini). De ce fait on ne peut pas tout calculer en un temps fini. Votre algorithme peut être bon mais ne pas fonctionner sur ordinateur. La finitude se voit aussi dans les grandeurs. Vous ne pouvez pas manipuler des nombres aussi grand que vous voulez. Les technologies ont leur limite. Cependant, les ordinateurs d'aujourd'hui sont assez développés pour que vous ayez une assez grande marge de manœuvre.

### Problème de la valeur entière maximale

Petit TP : faites un algorithme qui prend une valeur entière, l'augmente et l'affiche sans cesse et observez à partir de quand le programme commence à donner des valeurs incohérentes.
En Pascal par exemple : l'entier maximal représentable est contenu dans la constante MAXINT (qui vaut 32 767). Cela a pour effet d'avoir 32 767 + 1 = -32 768.
Note hors-sujet : pour comprendre pourquoi ce problème se pose : voir la partie codage des entiers signés dans le cours d'architecture des ordinateurs.

#### Éviter ce problème

Si vous êtes confronté au problème : essayez de changer votre algorithme en privilégiant les calculs approchant les 0. Voici un exemple plus clair : a et b sont deux entiers entre 5 000 et 10 000 avec a > b
peut ne pas fonctionner car on a dépassé 32 767. Par contre,
peut fonctionner car on n'a pas dépassé 32 767.

## Comment programme-t-on ?

Vous avez donc votre algorithme, comme vous êtes doué(e) : vous êtes sûr(e) qu'il fonctionne, cependant vous voulez le vérifier in situ sur un ordinateur. Voici les étapes (toutes expliquées ci-après) à suivre pour obtenir votre programme informatique :
* Traduire l'algorithme en Pascal : cette étape peut se faire sur papier, au brouillon. Comme c'est simple et rapide on peut traduire en même temps qu'on fait l'étape suivante.
* Recopier la traduction (le code source) dans un éditeur de texte.
* Compiler le code source pour le transformer en programme machine (ou binaire).
Le compilateur a engendré un programme, il ne vous reste qu'à l'exécuter pour vous en servir ou le tester.

## Traduire l'algorithme en Pascal

Pascal ayant été prévu dans cette optique, il est très facile de convertir un algorithme (sur papier) en un programme exécutable (fichier texte sur un ordinateur). Voici un exemple de traduction afin de vous montrer que la ressemblance est réelle et que la traduction est facile. Cet exemple reprend l'algorithme donné dans le chapitre d'introduction.
Voici l'algorithme :
et le code source en langage Pascal
Pour traduire n'importe quel algorithme dans le langage Pascal, il suffit de respecter un certain nombre de règles de syntaxe simples. Tout ceci est développé dans le guide de traduction en Pascal.
Pour ce qui est de l'indentation : utiliser la caractère de tabulation prévu pour et surtout pas d'espaces. Il s'agit de la touche à gauche de la touche A (clavier AZERTY) ou de la touche Q (en clavier QWERTY). Il est possible que vous trouviez ce caractère trop large, un bon éditeur permet de régler cette largeur en donnant la taille souhaitée en largeurs de caractères, par exemple donner 4 comme valeur fera que les tabulations ont une largeur de 4 caractères si vous utiliser une police mono-espacée (ce qui doit être le cas dans un éditeur de code). Dans le cas contraire, c'est la taille du caractère d'espacement qui est considérée (dans notre exemple, la tabulation aura la même largeur que 4 espaces). Par défaut la taille des tabulations est de 8, nous vous recommandons 2,3 ou 4 à régler selon que me nombre des niveaux d'indentations est très élevé ou plus modéré. À noter qu'on peut essayer avec un réglage à 4 puis décrémenter a posteriori si besoin est.

## Avant l'exécution, la compilation

Étape (que beaucoup trouvent la plus agréable, allez savoir pourquoi...) où il n'y a rien à faire puisque le compilateur se débrouille tout seul. Il vous suffit de lui demander de compiler votre code source. Nous n'allons pas décrire ici toutes les façons de faire car il y en a de multiples : cela dépend de vos choix logiciels. (si vous êtes étudiant, votre responsable de TP est censé vous expliquer tout ça).
Lancez la compilation, deux issues sont possibles :
Premier cas : la compilation échoue. Ne paniquez pas car rien n'est joué ! C'est très courant, même les informaticiens qui ont 20 ans de métier font encore parfois des erreurs. La plupart des compilateurs vous diront pourquoi ils refusent de compiler, ils vous indiqueront même où se situe l'erreur (ligne du code source) voire, dans certains cas, ils vous donnerons l'erreur et la correction à faire. Retournez éditer votre code source et corrigez l'erreur. Vous verrez que la plupart du temps il s'agit de fautes d'inattention (des '=' à la place des ':=', d'oublis de points-virgules en fin d'instructions, etc). Relancez la compilation. Parfois il faut recompiler vingt fois avant d'arriver à finir la compilation (c'est fou ce qu'il peut y avoir comme point-virgules...).
Second cas : la compilation fonctionne. Le compilateur vous indique qu'il a réussi. Vous devriez avoir maintenant à côté de votre fichier source un exécutable.

## Exécuter le programme

Là encore, il existe tellement de possibilités de faire que nous ne les expliquerons pas ici. Assurez-vous de connaître un moyen d'arrêter un programme récalcitrant. (les étudiants se tourneront encore une fois vers leur enseignants de TP).
Pour tester votre programme, entrez des valeurs comme si vous l'utilisiez. Essayez de tester "toutes" les combinaisons en faisait des essais représentatifs. à expliciter...

### Un problème ?

Voici les erreurs que vous pourriez constater en exécutant votre programme et des pistes pour les résoudre :
| Erreur d'exécution | Où chercher l'erreur |
| Le programme boucle sans fin | Assurez-vous que le programme boucle sans fin en attendant un temps assez long pour en être sûr (certains calculs peuvent être très longs) ou que le programme indique qu'il s'est arrêté car il ne peut plus continuer à consommer autant. Si le programme boucle effectivement sans fin : vous avez dans votre code source une boucle répéter ou tant que dont la condition n'est jamais atteinte. Vérifiez que vous avez une instruction qui fait tendre la ou les variables d'arrêt vers le cas d'arrêt (par exemple, n'avez-vous pas oublié d'incrémenter le i ?). |
| Le programme ne donne pas les bons résultats (un « bogue ») | Vérifiez votre code source (oubli d'une instruction ?). Il est très peu probable que l'ordinateur fasse des erreurs de calculs donc si vous êtes sûr de votre code source : c'est peut-être votre algorithme qui est faux (retour à la case départ :. Si votre algorithme est bon alors faites un déboguage. |
| Le programme donne des résultats complètement hors de propos (comme une opération sur deux chiffres donnant = 29876 ???) | Votre programme traite de trop grands nombres et vous avez dépassé les limites de Pascal. |
| erreur de segmentation (ou « segfault ») | arg :( |
| Vous n'avez touché à rien (promis) et pourtant ça fonctionnait tout-à-l'heure" (problème le plus courant : confirmé par nombre de professeurs...) | le problème ne vient pas de l'ordinateur qui, lui, n'est pas de mauvaise foi ;) |

#### Le déboguage

Il existe des logiciels débogueurs dont c'est le rôle, cependant nous allons expliquer la démarche « manuelle » ici. Le déboguage manuel a pour but de déceler les bogues récalcitrants qu'on a cherchés pendant des heures en mettant à contribution les collègues. Il faut comprendre par là que ce doit être un (ultime) recours et non une pratique courante. Pédagogiquement, il est préférable, pour votre apprentissage, que vous trouviez l'erreur en raisonnant et en relisant attentivement votre code source ou en revérifiant votre algorithme.
Si vous décidez malgré tout de vous lancer dans ce processus fastidieux, pénible et coûteux en temps, si plus personne ne peut vous en dissuader, voici la situation et sa solution :
Vous avez donc relu votre code source 15 fois, revérifié votre algorithme 15 fois, demandé à vos collègues qui n'ont rien pu vous dire, même votre professeur a laissé tomber et pourtant il subsiste, le bogue. Introuvable, à la fois nulle part et partout. Si vous n'en dormez plus, voilà la solution.
Le déboguage (ou debugging) consiste à afficher ce que votre programme fait en arrière plan. Concrètement, cela revient à placer des « afficher » partout dans votre code. Chaque Affichage doit être unique, de sorte que dès que vous voyez une ligne en particulier vous devez pouvoir retrouver la ligne de code ayant produit cet affichage.
Exemple, considérons le programme suivant :
Créons un autre fichier .pas contenant la version déboguage du code précédant :
L'idée étant que à chaque étape, vous pouvez vérifier que toutes les données sont valides. En suivant l'exécution avec ce qui s'affiche vous devriez voir à partir de quand l'erreur se produit.

## Exemple complet

Dans cette partie, nous allons voir un cycle de programmation complet.
Comme environnement de travail, on a choisi de travailler sur le système d'exploitation Ubuntu pour PC. On utilisera gedit comme éditeur de texte et le compilateur Free Pascal car tous deux sont disponibles sur Ubuntu.
Nous allons implémenter l'algorithme suivant :
Il s'agit de l'algorithme demandant deux nombres et les inversant avant de les afficher (inutile mais c'est un exemple). Traduisons-le :
On recopie la traduction dans gedit, puis on enregistre dans un fichier inversion.pas :
Remarquez que gedit colorie le code de façon à le rendre plus lisible (on parle de coloration syntaxique).
Passons à la compilation : on a ouvert un terminal et taper la commande
Le terminal affiche alors :
Les 15 lignes ont bien été compilées (ligne 6), le compilateur à créé un binaire inversion. Testons-le : dans le terminal, on donne la commande ./inversion pour lancer le programme.
Le programme se lance. Voici un test :
On a entré nos deux nombres : notre programme va nous donner le résultat.
Notre programme semble fonctionner. Les deux nombres ont bien été inversés. L'expérience est concluante, cependant, voyons ce qu'il se passe si on atteint les limites du codage des entiers.
Testons avec deux grands nombres :
Le programme nous indique les résultats 5123 et -30969. Notre programme, comme tous les programmes a donc ses limites même si notre algorithme est bon.

# Guide de traduction Pascal

Voici un guide de traduction d'un algorithme impératif en Pascal.

## Le Squelette

Pour le squelette de l'algorithme :
On traduit ainsi :

## Commentaires

Les commentaires notés
s'écrivent de la même façon

## Types

Voici l'équivalence des types
| type | Pascal |
| booléen | bool |
| entier | integer |
| réel | real |
| caractère | char |
| chaîne de caractères | string |
* Les valeurs booléennes sont true et false.
* Les parties entière et décimale d'un réel sont séparées par un point et non une virgule.
* les chaînes sont déclarées entre deux apostrophes ' pour échapper un caractère on le double.
Exemple sur ce dernier point : pour inclure une apostrophe dans une chaîne,
affiche

## Constantes et variables

Les constantes et les variables ont des identifiants qui doivent respectées une syntaxe précise.
* l'identifiant ne peut comporter que des caractères alpha-numériques (de A à Z, de a à z et de 0 à 9) et des tirets-bas ou underscore : _.
* le premier caractère est une lettre.
les variables sont déclarées dans le Lexique du programme délimité par sa partie Var. Chaque déclaration est de la forme
Ainsi le lexique
se traduit
Les accents ne sont généralement pas acceptés par les compilateurs Pascal.
Les identifiants des constantes respectent les mêmes règles. Par convention, on préférera les noter en majuscules. La déclaration d'une constante a pour syntaxe
Ceci
s'écrit en pascal :

## Instructions et blocs d'instructions

Pour exécuter une instruction (assignation, appel de fonction ou procédure) il suffit de l'écrire. Les paramètres sont précisés entre parenthèses et séparés par des virgules.
Les bloc d'instructions débutent par un begin et se terminent par un end. Les instructions du bloc sont séparées par des point-virgules. On gardera la convention algorithmique préférant une instruction par ligne.
Voici une ligne comportant une instruction unique :
Voici un bloc de k d'instructions :
Remarquez qu'aucun point-virgule ne ponctue la dernière instruction. En effet le ';' est un séparateur : il sépare les instructions entre elles. Il n'y a donc pas de point-virgule après la dernière instruction, pas plus qu'il n'y en a avant la première. Cela explique également pourquoi lorsqu'on écrit une seule instruction, elle n'est pas suivie d'un point-virgule.
Il est souvent affirmé à tort que « toutes les instructions se terminent par un point-virgule ». Ce n'est pas tout à fait vrai, comme nous venons de le voir. Cependant, cette croyance répandue a été prise en considération par les développeurs des compilateurs qui ignorent cette erreur.
Il convient de remarquer que le programme principal est un bloc d'instructions ponctué d'un point, ni plus ni moins.

## Lecture et Écriture (affichage)

L'affichage s'effectue à l'aide de la procédure write. Elle peut prendre de un à plusieurs paramètres de n'importe quel type de base. Elle affiche tous les paramètres les uns après les autres (résultat identique à celui d'une concaténation).
Il existe une variante de write ayant la même spécification mais effectuant un retour à la ligne à la fin : il s'agit de la procédure writeln. On peut également appeler la procédure writln sans préciser de paramètres, cela effectue un retour à la ligne.
La lecture se fait à l'aide de la fonction read qui prend en paramètre l'identifiant de la variable qui sera assignée.
readln est indentique à read mais fait un retour à la ligne une fois la donnée lue.
Exemple
affiche
alors que
affiche

## Assignation

L'assignation est une instruction et à ce titre elle doit respecter les règles sur les instructions (points-virgules...)
L'opérateur d'assignation est := (et non = qui est le test d'égalité)
La syntaxe de l'assignation est (espaces facultatifs) :
Il va sans dire que le type de l'expression doit être compatible avec celui de la variable assignée.

## Exécution conditionnelle

On rappelle qu'une exécution conditionnelle est une instruction. Elle ne comporte pas de point-virgule sauf si elle est à l'intérieur d'un bloc. On suppose ici que l'instruction est au sein d'un bloc.
donne
S'il y a plusieurs instructions, on utilise un bloc :
Avec une instruction à exécuter quand la condition est fausse (sinon) :
se traduit
De même on peut utiliser des blocs :

## Structures itératives

Une boucle à compteur
donne
On peut toujours utiliser un bloc comme instruction pour grouper plusieurs instructions à exécuter :
De même, une boucle répétée jusqu'à ce qu'une condition soit vraie (testée après chaque itération) :
et une boucle répétée tant qu'une condition est vraie (testée avant chaque itération) :

## Tableaux

donne :
Par exemple un tableau de 10 entiers, indicé de 1 à 10 :

## Le type enregistrement

donne
Exemple :

# Inverser deux variables
## Problèmatique

Nous disposons de deux entiers a et b. Nous voulons intervertir ces deux nombres. À la fin du programme : la valeur de a sera égale à celle de b lors du lancement du programme et inversement : b sera égal au a initial.
Exemple : au début du programme nous posons a=2 et b=3. À la fin du programme nous aurons a=3 et b=2.

## Solutions

Voici deux solutions acceptables :

## Remarque

Ces deux solutions présentent en fait une notion clé de l'informatique : étudions nos deux solutions de plus près :
Simplifions le fonctionnement d'une machine au maximum : supposons
* Qu'il faut utiliser une unité de mémoire pour stoker une variable en mémoire
* Qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.
Temps de calcul requis par chaque algorithme :
* Pour inversion_stockage : 3 unités de temps (3 assignations)
* Pour inversion_calcul : 6 unités de temps (3 assignations + 1 somme + 2 différences)
Mémoire requise par chaque algorithme :
* Pour inversion_stockage : 3 unités de mémoire (a, b et temps)
* Pour inversion_calcul : 2 unités de mémoire (a et b)
On a donc que
* inversion_stockage prend plus de mémoire mais moins de temps de calcul que inversion_calcul
* inversion_calcul prend plus de temps de calcul mais moins de mémoire que inversion_stockage
Et c'est là un concept généralisable :
D'une façon générale, vous pouvez faire des algorithmes plus rapides en utilisant plus de mémoire et des algorithmes utilisant moins de ressources mémoire mais qui seront plus lents.
Attention cependant, cela ne veut surtout pas dire qu'aucun algorithme n'est améliorable sans perte de ressources en calcul ou en mémoire. Bien au contraire, vous devez toujours essayer d'être le plus efficace possible.
Ce constat ne permet pas de dire si un des algorithmes est plus efficace que l'autre : notre analyse a été trop simplifiée pour cela. En effet, nous n'avons pas considéré que :
* la mise en mémoire peut aussi prendre un temps non négligeable ;
* peut-être que les calculs de sommes et de différences sont très coûteux en temps ;
* peut-être que le processeur est assez avancé technologiquement pour effectuer un premier calcul et en commencer un deuxième avant d'avoir obtenu le premier résultat ;
* l'algorithme pourrait utiliser des réels, et, en général, les calculs sur les réels sont plus longs que sur les entiers.
Vous contesterez, avec raison, que sur cet exemple, aujourd'hui nos ordinateurs sont parfaitement capables d'exécuter ces deux programmes en un temps record et qu'on ne distinguera pas la différence suivant qu'on utilise l'un ou l'autre. C'est vrai, mais vous négligez que peut-être :
* ce programme sera exécuté sur une machine minuscule, une micro-puce de quelques millimètres dans laquelle on n'a pu mettre que très peu de mémoire et un minuscule processeur ;
* ce programme doit pouvoir être exécuté simultanément des milliers de fois sur la même machine ;
* ce programme ne sera pas exécuté plusieurs fois en même temps mais des milliers de fois, les unes après les autres, et que le programme ayant besoin d'inverser des milliers de valeurs à la suite doit pouvoir donner un résultat dans la seconde...
En réalité, n'importe quel compilateur décent, depuis les années 80, va optimiser bien au delà de ce que le programmeur moyen aura le courage de faire. Par exemple sur l'échange : utiliser deux registres au lieu d'une variable supplémentaire (R1 := A; R2 := B; A := R2; B:= R1) si les données tiennent dans un mot machine, ou utiliser les instructions spécialisées du processeur d'échange de deux zones en mémoire. En écrivant la forme la plus simple d'échange, le compilateur reconnaitra (parce qu'on lui a inculqué un certain nombre de recettes) de quoi il s'agit, et fabriquera le meilleur code possible. Le temps consacré à de la micro-optimisation est en général une perte sèche, il est de loin préférable de la consacrer à une bonne conception, et à l'utilisation d'algorithmes efficaces.

# Un menu de sélection simple

Ce problème traite de la création d'une interface graphique rudimentaire dans un environnement textuel (un terminal).

## Problématique

Nous supposons que nous avons déclaré 3 procédures dont les identifiants sont les suivants (peu nous importe ce qu'elles font : le sujet n'est pas ici)
* Procedure_A
* Procedure_B
* Procedure_C
Vous devez créer le programme principal permettant à l'utilisateur de choisir laquelle des trois il veut lancer. Le programme doit avoir les fonctionnalités suivantes :
* Une fois que la procédure choisie par l'utilisateur a été exécutée, le menu est de nouveau proposé.
* L'utilisateur doit pouvoir quitter le programme depuis le menu.
* Le programme doit expliquer à l'utilisateur comment utiliser le programme.
* (optionnel) on suppose que l'utilisateur est distrait et qu'il peut ne pas donner une bonne réponse. Gérez ce cas.

## Première analyse

Voici quelques idées directrices formant une première analyse de la problématique. Chacun de ces points seront analysés dans la section suivante.
* ...permettant à l'utilisateur de choisir... : l'utilisateur doit intervenir. Il va falloir faire intervenir un Lire afin qu'il puisse nous donner son choix.
* ...laquelle des trois... :
* ...le menu est de nouveau proposé : il s'agit d'une répétition.
* ...quitter le programme depuis le menu : une autre possibilité. En fait, l'utilisateur aura le choix entre quatre possibilités : A, B, C ou quitter.
* ...expliquer à l'utilisateur comment utiliser le programme' : on affichera les instructions avec Afficher.

## Analyse approfondie

Voici les réflexions qu'il faut mener sur les questions clés du problèmes.

### Gérer le choix de l'utilisateur

Nous allons représenter le choix de l'utilisateur par un entier. Finalement, l'utilisateur à quatre possibilités pour le menu (entre parenthèse : l'entier que nous allons y associer) :
* Exécuter la procédure A (1)
* Exécuter la procédure B (2)
* Exécuter la procédure C (3)
* Quitter (0)
Nous allons donc lui poser la question "Que voulez vous faire ?", il répondra par un entier en fonction duquel on fera un SÉLECTIONNER.
(optionnel) l'utilisation d'une chaîne de caractères nous permettra de contrôler l'erreur si l'utilisateur entre autre chose que 1,2,3 ou 0. Si on utilise un entier et que l'utilisateur entre "truc" il va y avoir un problème (sur une machine, le programme se bloquera...).

### L'utilisateur retrouve le menu

Pour que l'utilisateur retombe sur le menu, il va falloir utiliser une structure itérative, mais laquelle ? Petite réflexion :
* À priori, on ne sait pas combien de fois l'utilisateur va exécuter une procédure. Cela exclut le POUR.
* REPETER ou TANTQUE ? Le menu va s'afficher au moins une fois ce qui nous laisse penser qu'un REPETER est plus approprié. De plus la situation est bien décrite par la phrase "Afficher le menu jusqu'à ce qu'il choisisse de quitter", ce qui conforme notre choix. Nous utiliserons donc un REPETER.

## Solution finale
# Somme des n premiers entiers
## Problématique

Écrire un algorithme sous forme d'une fonction qui calcule la somme des premiers entiers jusqu'à n inclus, n étant passé en paramètre.
Exemple : somme(5) calculera 1+2+3+4+5 et renverra donc 15

## Solution

Voici une première réponse acceptable :
Pourquoi partir de 0 et pas 1 ? Cela sert tout simplement à gérer le cas n=0. Cela ne change rien pour les autres cas puisque (en reprenant l'exemple de la problématique) somme(5) va calculer 0+1+2+3+4+5, c'est à dire 1+2+3+4+5 (=15).
Cependant, la boucle peut partir de 1 si elle ne s’exécute pas pour n=0. Dans ce cas, la somme sera 0 (valeur initiale de la variable somme).

## Remarque

Essayons une analyse un peu plus mathématique du problème :
En fait notre fonction calcule pour n : $\sum _{i=0}^{n}i$. L'étude des séries nous apprend que
$\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}$.
On peut en déduire que la fonction peut s'écrire
Ce qui d'une part est plus simple mais également, comme nous allons le voir, plus efficace.
Simplifions le fonctionnement d'une machine au maximum : supposons qu'il faut une unité de temps au processeur pour effectuer un calcul et qu'une opération entière et l'assignation consistent toutes en 1 calcul.
Supposons que nous voulions calculer somme(1000) : Avec somme : nous allons effectuer :
* 1000 incrémentation de i
* 1000 sommes somme+i
* 1000 assignation
Soit au moins 3000 calculs.
Avec somme_directe : nous allons effectuer
* une somme : n+1
* une multiplication n*(n+1)
* une division par 2
Soit 3 calculs.
Conclusion : 3000 calculs pour le premier algorithme, 3 calculs pour le second. La différence entre les deux : le mathématicien qui doit se retrouver en chaque algorithmicien.
Et dire que de nombreux étudiants en informatique sont souvent étonnés de la présence importante de mathématiques durant leur cursus...
(pour info : Wikilivres propose des cours de mathématiques...)

# PGCD de deux nombres
## Problématique

Écrire un algorithme donnant le Plus Grand Commun Diviseur (PGCD) de deux nombres donnés par l'utilisateur. On supposera que l'utilisateur ne donne que des entiers strictement supérieurs à zéro.
Il faudra écrire une fonction, prenant en entrée deux entiers strictement positifs et renvoyant leur PGCD. L'algorithme principal y fera appel.
Question subsidiaire : on considérera que l'utilisateur peut entrer n'importe quels entiers. Tenez-en compte pour que l'algorithme ne commette pas d'erreur et qu'il informe l'utilisateur.

## Aide

Il faut avoir étudié ce problème d'algèbre pour avoir la solution. Elle consiste à appliquer l'algorithme d'Euclide.

## Solution

Pas vraiment de difficulté pour l'algorithme principal. La difficulté étant la fonction implémentant l'algorithme d'Euclide. Le jeu d'assignation à répéter jusqu'à obtenir un reste nul est difficile à visualiser.
Question subsidiaire : il y a trois événements à contrôler :
* Le cas où u=v=0 et où le PGCD n'existe pas et il faut arrêter le programme (ligne 22)
* Le cas où u ou v (ou les deux) est négatif est il faut prendre son opposé (lignes 24 et 25)
Pour la solution sans la question subsidiaire : ôter les lignes 21 à 26 et la 28 de la solution proposée.

# Trier un tableau
## Problématique

Voici un problème fondamental d'informatique.
Supposons qu'il soit déclaré tab, un tableau.
Pour écrire le programme on prendra la déclaration suivante
Pour simplifier le problème, vous pourrez considérer que T = entier.
Note : sachez toutefois que les opérateurs <, <=, >, >= sont génériques et permettent de comparer toutes données tant qu'elles font partie du même ensemble ordonné (Par exemple : l'alphabet).
Question subsidiaire : considérez le cas particulier où les éléments sont distincts. L'algorithme fonctionne-t-il ?

## Solution

Il est tout d'abord important de savoir qu'il existe de nombreuses façon de procéder. Pour connaitre ces algorithmes de tri, élément important de la culture de tout algorithmicien, nous vous invitons à consulter l'article « Algorithme de tri » sur Wikipédia ainsi que les articles sur les différents algorithmes de tri existants.
Pour vous corriger : vérifiez que votre algorithme ne tombe pas sur une erreur courante en supposant que tous les entiers sont distincts. En effet, il est facile de faire un algorithme qui, voulant inverser deux éléments pour les remettre en ordre, boucle sans fin en voulant inverser sans fin : lorsqu'il tombe sur deux éléments égaux.

### Une solution "simple"

Le tri par sélection est un des plus simples algorithmes de tri. Il consiste à rechercher le plus petit (ou le plus grand) élément du tableau et de le placer à sa place définitive : au début (ou à la fin du tableau). Une fois un tel élément placé à sa place définitive, on recommence avec le reste du tableau. Lorsqu'on place un élément, on n'écrase pas ce qui était là (on perdrait un élément du tableau) mais on le déplace à la position qu'on vient de libérer (ce qui revient à faire une permutation).

#### Une implémentation testable en Pascal

Voici un exemple d'exécution :

# Rechercher un élément dans un tableau
## Problèmatique

Supposons que nous avons déclaré un tableau tab d'entiers comme suit :
Supposons que ce tableau est rempli d'entiers inconnus mais triés dans l'ordre croissant.
Proposez un algorithme qui, étant donné un entier indiqué par l'utilisateur, trouve son indice dans le tableau. On supposera que l'entier indiqué par l'utilisateur est effectivement dans le tableau.

## Aide

Vous remarquerez que ce problème s'apparente au problème de recherche d'un mot dans le dictionnaire. Pensez donc à la méthode que vous employez dans cette situation...

## Solutions
### Solutions moyennes

Voici une solution, qui n'est pas celle attendue. L'algorithme parcourt le tableau du début à la fin et compare l'élément à l'entier indiqué par l'utilisateur. Il s'arrête lorsqu'il est trouvé. Remarquez que la faiblesse de cette algorithme provient du fait qu'il fonctionne même quand le tableau n'est pas trié, il n'exploite donc pas cet avantage trop important pour être négligé.
L'algorithme suivant fonctionne mais à le défaut de continuer à parcourir le tableau même quand l'élément a été trouvé.

### Solution attendue

Voici enfin la solution attendue. Vous étiez peut-être arrivé à cette déduction seul ou en consultant l'aide mais vous avez compris que ce problème s'apparente à celui de la recherche dans un dictionnaire. En effet, on cherche un mot dans un ensemble de mots inconnus mais triés.
Si vous avez déjà cherché un mot dans le dictionnaire, vous avez certainement remarqué que lire le premier, regarder si c'est celui qu'on cherche, puis passer au suivant, et ainsi de suite n'est pas la solution la plus efficace...
La solution est donc l'algorithme de recherche dichotomique (du grec « dichotomie » : « couper en deux »). On ouvre le dictionnaire au milieu et un prend un mot au hasard, si le mot qu'on cherche est avant, recommence avec la première moitié du dictionnaire, s'il est après, avec la deuxième moitié. Dans la bonne moitié on prend un mot au milieu, etc...

#### Traduction en Pascal

Voilà sa traduction en Pascal, le tableau étant rempli à la main :

# Jeu du Tas de billes
## Problématique

On cherche à implémenter un jeu dont voici les règles :
Règles du jeu :
* On commence avec un tas de billes, le jeu se joue à deux,
* Les joueurs jouent l'un après l'autre,
* Chaque joueur, à son tour, peut retirer une, deux, ou trois billes du tas,
* Le joueur qui prend la dernière bille a perdu.
En plus d'implémenter le mécanisme du jeu, on veillera à respecter les consignes suivantes :
* Au lancement, le programme rappelle les règles du jeu énoncées ci-dessus.
* Le contenu du tas de départ est demandé au lancement. Si le nombre donné est 0 ou moins, on prend un nombre aléatoire entre 10 et 30 et on l'annonce.
* Les deux joueurs entreront leurs noms en début de partie.
* À chaque tour, le programme rappelle à qui est le tour, en appelant les joueurs par leurs noms. Pour qu'on voie que le tour à passé, l'affichage est vidé des informations et saisies du tour précédent.
* À chaque tour, le programme rappelle combien il reste de billes dans le tas et donne une représentation graphique s'il reste moins de 30 billes (afficher sur une seule ligne un '.' par bille restante fera amplement l'affaire).
* Le programme gère les tentatives de triche et rappelle les règles si nécessaire.
* À la fin du jeu, le gagnant est désigné par son nom.

## Solution

Trouver un algorithme pour ce jeu n'est pas aussi évident qu'il y parait.

### Implémentation en Pascal
# Quiz
## Problématique

On cherche à implémenter un programme qui, étant donnée une base de données de questions et de réponses correspondantes posent les questions et demande la réponse à un joueur. Le programme comptabilise les bonnes réponses et donne le score final. Le nombre de questions à poser est demandé au début de la partie, si le nombre donné est nul ou négatif, on choisit un nombre aléatoire entre un et le nombre de questions dans la base de données.
Les réponses seront soit
* vrai/faux
* une réponse en toutes lettres
* une réponse sous forme de nombre
Il est demandé d'implémenter seulement une de ces trois possibilités.
* À chaque question, le score actuel et le nombre de questions restantes est affiché
* On ne demande pas que le programme ne pose pas deux fois la même question au cours d'une même partie, réfléchir tout de même à un moyen de faire cela.

### Données

On suppose ces tableaux remplis, bien évidement la réponse à la question questions[i] est réponses[i]. T est booléen, integer, ou chaine : à vous de choisir et d'assumer ce choix dans l'algorithme.

## Solution
### Implémentation en Pascal

L'auteur vous demande de l'excuser pour la piètre qualité du contenu de la base de données...

# Solutions d'un polynômes
## Problématique

On souhaite réaliser un programme qui donne les solutions d'un polynôme dont les coefficients sont donnés par l'utilisateur. On peut aborder le problème selon des difficultés croissantes :
* Résoudre dans ℝ les polynômes du premier degré
* Résoudre dans ℝ les polynômes du second degré
* Résoudre dans ℂ les polynômes du second degré

# Écarts entre les éléments d'un tableau
## Problématique

Donner un algorithme qui, étant donné un tableau d'entiers, trouve le plus petit écart entre deux éléments.
Exemples :
* [1|10|4|6] : 6-4 = 2
* [1|10] : 10-1 = 9
* [5|5] : 5-5 = 0
Donner un algorithme qui, étant donné un tableau d'entiers, trouve le plus grand écart entre deux éléments.

## Solution
### Une implémentation testable en Pascal

Exemple de résultat produit par le programme :

# L'algorithmique impérative, et après ? perspective sur la suite des évènements...

Cette partie introduit un ensemble de sujets d'ouverture possibles pour la poursuite de l'apprentissage.

## Algorithmique

Comme nous l'avons vu, notamment sur le problème du tri des tableaux, il existe de multiples algorithmes connus dont l'étude est intéressante pour la culture de l'algorithmicien.
C'est l'objet du wikilivre Programmation Algorithmique.

## Calculabilité et complexité

Vous allez sûrement vous poser cette question un jour : Peut-on écrire un algorithme qui... ?. Grande question, nos ordinateurs d'aujourd'hui dérivent de la Machine de Turing. Toute une branche des mathématiques est dédiée au problème de la Calculabilité.
Au fil des remarques dans les problèmes posés,nous avons abordé la notion d'efficacité d'un algorithme. Notamment dans le problème sur la somme des n premiers entiers où nous avons clairement constaté qu'il existait deux façons d'obtenir un résultat : l'une prenant beaucoup plus de ressources (en temps et en mémoire) que l'autre. Eh bien ce concept est formalisé : il est possible d'évaluer grâce aux mathématiques si un algorithme est plus efficace qu'un autre. Il s'agit de la complexité
Finalement, il s'agit de répondre à deux questions : peut-on obtenir un résultat en un temps fini (calculabilité) ? et si oui, dans quel ordre de grandeur de temps (complexité) ?

## Algorithmique fonctionnelle

Nous avons étudié l'algorithmique impérative : cette précision est effectivement nécessaire. Une autre algorithmique existe. Elle pose d'autres bases de départ, d'autres concepts. Elle est plus complexe à apprendre et à comprendre que l'algorithmique impérative mais la puissance de ses axiomes permet d'éviter de nombreux problèmes.
Cet exemple exploite le concept de la récursion, fondamental dans cette algorithmique.
| Algorithme itératif (impératif) | Algorithme récursif (fonctionnel) |
| Fonction factorielle(n : entier) Lexique i : entier (* variable de boucle *) résultat : entier (* le résultat final qu'on retournera *) Début si i=0 alors résultat←1 sinon début résultat←1 (* on initialise le résultat *) pour i de 2 à n résultat←résultat*i finpour fin finsi Fin | Fonction factorielle(n : entier) Début si n<=1 alors 1 sinon n*factorielle(n-1) Fin |
C'est un bon complément et une bonne suite à l'apprentissage de l'algorithmique impérative.

## Structures de données

Nous n'avons jusqu'ici utilisé qu'une structure de données, le tableau. Cette structure de données pose un problème : elle occupe la mémoire en fonction de sa déclaration. Ce qui signifie que si on ignore combien l'utilisateur va nécessiter d'indice, il va falloir réserver le tableau le plus grand possible afin d'être sûr qu'il puisse contenir autant d'éléments que l'utilisateur souhaitera. Il serait plus judicieux de réserver l'espace au fur et à mesure de la demande. C'est ce que l'on appelle le gestion dynamique de la mémoire (par opposition à statique).
Nous avons également vu qu'un tableau est générique : c'est-à-dire qu'au moment de sa déclaration, nous pouvons dire que tous ses éléments sont d'un type donné et choisir ce type.
Nous avons vu que les tableaux sont homogènes : c'est-à-dire qu'un tableau donné ne peut contenir qu'un seul type d'élément (celui précisé dans la déclaration du tableau). Nous pourrions avoir besoin d'un tableau dont certains éléments seraient des entiers, d'autres des chaînes, d'autres encore des booléens. Il s'agit là de la problématique de l'hétérogénéité.
Note : attention à ne pas confondre la notion de généricité avec celle d'hétérogénéité. La première désigne la capacité à contenir des éléments d'un même type que l'on peut choisir en le fixant au moment de la déclaration. La seconde désigne la capacité à contenir des éléments de types différents.
Supposons maintenant que nous devions utiliser des formes d'information qui ne font pas partie de type de bases : les listes, les matrices, les rationnels, les arbres, l'ADN, la couleur, etc. Comment créer les éléments nécessaires au stockage de telle information quand un simple tableau ou un simple enregistrement ne suffisent plus ?
Dynamicité, généricité, hétérogénéité et la création de nouveau types non-élémentaires sont autant de problèmes traités dans le wikilivre Structures de données.

## Théorie des langages

La langage algorithmique est composé de règles de syntaxe bien précises dont la raison peut paraître obscure. Les langages de programmation ont également de nombreuses règles d'écriture. Qu'est ce qui détermine qu'un langage peut être compris par un ordinateur ? Pourquoi ne peut-on pas tout simplement écrire nos algorithmes en français littéral ?
C'est l'objet de la théorie des langages.

## Architecture des ordinateurs

Nos algorithmes sont implémentés dans un langage informatique puis compilés pour être transformés en un fichier binaire exécutable. Pourquoi le binaire ? Comment l'ordinateur peut-il simplement avec l'électricité stocker des données et effectuer des opération sur celles-ci ? Que fait exactement le compilateur ? Pourquoi un binaire compilé pour Linux ne fonctionne pas sous Windows ?
Une infinité de questions peut se poser sur le fonctionnement de l'ordinateur au-delà de l'écran. Il s'agit de l'Architecture des ordinateurs

## Correction des algorithmes

De la même façon que pour la calculabilité et la complexité, une branche des mathématiques permet de prouver qu'un algorithme fonctionne. Il s'agit de la logique de Hoare

## Conclusion

Il existe une multitude de domaines d'extension et de connaissances qui touchent à l'informatique en plus de l'algorithmique impérative. La plupart sont liées aux mathématiques. Chacune de ces matières suscitera plus ou moins votre curiosité...

# Ressources externes : bibliographie, liens...
## Bibliographie

* (français) Daniel Canevet - L'algorithmique et le Pascal - Collection Informatique et communication, Éditions Paris : Delagrave - 1992 - 95 pages - (ISBN 2-206-00698-7)
* (français) Claude Delannoy - Initiation à la programmation - Éditions Eyrolles - 1997 - 192 pages - (ISBN 2-212-08983-X)

## Wikilivres

* Programmation Pascal

## Sur la Wikiversité

* Introduction générale à la programmation. Certaines notions exposées dans ce module dépassent le cadre du présent ouvrage.
* Algorithmique
* Langage Pascal

## Sur Wikipédia

* le langage Pascal

## Liens externes

* Le projet Euler propose une collection de problèmes mathématiques à résoudre à l'aide de l'informatique et notamment de l'algorithmique impérative. Attention, il s'agit là de problèmes bien plus difficiles que ceux qui ont été abordés ici. Le site étant de surcroît en anglais, il est donc à réserver aux courageux.
* Pascal sur developpez.com
* France-IOI : site francophone sur les Olympiades Internationales d'Informatique