Algorithmique ou programmation au Lycée ?

Je me suis un peu penché sur la différence entre ALGORITHME et PROGRAMME. La différence importante que j'ai trouvé est qu'un programme fera la plus part du temps des calculs approchés, je laisse de côté le cas de XCas, tandis qu'en algorithmique les calculs sont exacts.

Cette distinction que tu fais ne me semble pas du tout pertinente. Je vois plutôt un programme comme l'implémentation d'un algorithme dans un langage de programmation.
Il y a bien sûr tout un tas d'algorithmes qui font des calculs approchés (comme l'algorithme de Héron), et des programmes qui font des calculs exacts (dans des systèmes de calcul formel, par exemple, pour inverser une matrice).

Non. Un programme contient, dans un langage particulier, l'implémentation de plusieurs algorithmes. Il peut très bien donner des résultats exacts, tout dépend de ce qu'on fait.

Au lycée on veut faire de l'algorithmique, pas de la programmation (i.e. pas s'embêter avec la syntaxe du C++ ou du Java, ni débugger un code source pendant longtemps). Plusieurs livres de seconde utilisent fort justement Algobox http://www.xm1math.net/algobox/ pour l'agorithmique, qui est remarquable.

> source pendant longtemps). Plusieurs livres de
> seconde utilisent fort justement Algobox

C'est mortel d'ennui ce truc, c'est de l'informatique du temps des pionniers, il manque que les cartes perforées Franchement, mais qu'est-ce qu'on fait d'intéressant avec une usine à gaz comme ça ? Je viens de regarder leur animation : 11 lignes de (pseudo) code laborieux pour faire la somme de nombre de 1 à 100. N'importe quel programme un peu substantiel sera infaisable tant le machin est lourd.

Dans les exemples, ils proposent une fonction de Syracuse, 24 lignes de code peu intuitif pour afficher les 101 premiers termes de la suite. La suite de Syracuse est un truc simple donc il est incompréhensible que le code produit ne soit pas simple et intuitif.


Voyons ce que cela donne en Python :

def f(x):
    if x%2==0:return x/2
    else: return 3*x+1
a=input()
print "0 ->", a
for i in range(1,101):
    b=f(a)
    print i, "->", b
    a=b

Je traduis pour ceux qui ne connaissent pas. D'abord, vous remarquez que le code est indenté. C'est non seulement volontaire mais obligatoire en Python: cela oblige à structurer son code en même temps que cela le rend plus lisible.
Python est tellement simple que c'est du pseudo code exécutable.

lignes 1 à 3 : on définit, comme en math, une fonction f qui prend une variable x (remarquer que le type de x n'est pas précisé).
Le code s'écrit ensuite comme l'algo s'énonce : si le reste de la division de x par 2 vaut 0 alors f(x) vaut la moitié de x, sinon f(x) vaut 3*x+1

ligne 4 : l'utilisateur du programme est invité à entrer un nombre (fonction input). Dans la suite du programme le nombre entré s'appelle a.

ligne 5 : on affiche (instruction print) 0 -> a où a est remplacé par sa valeur

lignes 6 à 9 : on parcours les entiers i avec 1<= i < 101 et à chaque entier
*) on calcule f(la valeur courante)
*) on affiche cette valeur avec l'indice correspondant
*) on met à jour la valeur courante.
Vous remarquerez à quel point la syntaxe est lisible dans l'en-tête de la boucle(for toto in ...) , on ne dirait pas autrement en langage mathématique

A mon avis une partie des élèves apprendraient ça relativement rapidement. Je dis "une partie" car il y a une part incompressible d'élèves complètement rétifs à ce genre de travail, et parmi ces élèves on en trouvera même qui sont d'un niveau correct en math.


AMHA, si la programmation doit marcher au lycée, il faut un support qui permettent de faire des choses ludiques (et en particulier graphiques). Python permet très facilement de faire cela.


EDIT Idem pour l'algorithme de génération du tableau de Pascal que je trouve beaucoup intuitif à écrire en Python :

n=input()
t=[[0 for i in range(n+1)] for j in range(n)]
for ligne in range(n):
    t[ligne][0]=1
    for colonne in range(1,ligne+1):
        t[ligne][colonne]=t[ligne-1][colonne]+t[ligne-1][colonne-1]
    for colonne in range(ligne+1) : 
        print t[ligne][colonne],
    print

Je commente en deux mots pour ceux qui seraient intéressés :

ligne 1 : on demande à l'utilisateur d'entrer n
ligne 2 : on crée un tableau rempli de 0.
ligne 3 à la fin : on affiche le tableau ligne par ligne.
ligne 4: chaque ligne du tableau commence par 1
lignes 5 et 6 : on remplit la ligne courante : chaque des termes est la somme des deux qui sont juste au-dessus
ligne 7 et 8 : on affiche les termes de la ligne courante côte-à-côte
ligne 9 : saut de ligne

J'enseigne l'algorithmique dans le supérieur depuis plusieurs années, c'est pour cela que je pense que les objectifs du programme de seconde tel qu'il est présenté sont très ambitieux, surtout qu'une bonne partie des enseignants ne sont pas sans doute pas très enthousiastes et que même si c'est le cas ils n'ont pas forcément le recul nécessaire pour faire une séance de TP et pouvoir répondre à 15 élèves simultanément bloqués sur un programme qui ne compile pas (sans parler de s'exécuter correctement). D'un autre coté, faire de l'algorithmique sans passer à l'étape programmation sur machine, c'est comme faire de l'anglais uniquement à l'écrit, c'est barbant, ça passe à coté d'un aspect très motivant : réussir à faire faire le programme à la machine, et ça empêche la possibilité de corriger des erreurs par interaction avec la machine. Donc pas facile, espérons qu'avec le temps, les collègues prendront leurs marques, que cet enseignement s'enracinera et sera jugé enrichissant.

Bonjour,

J'ai enseigné 19 ans l'algorithmique en prépa Hec, après avoir enseigné 19 ans
dans le Secondaire.

Pour moi l'algorithmique est la décomposition en tâches simples d'un calcul compliqué :
on veut résoudre une équation, mais on ne décortique pas l'addition; on le rédige en français.
Un programme est la transcription de l'algorithme dans le dialecte d'un instrument de calcul.

Je ne connais aucun argument qui permette de dire qu'un langage de programmation est
supérieur à un autre. L'essentiel est d'en connaitre un, de le pratiquer, d'en connaitre les
limites, et de vérifier les algorithmes qui sont des productions de la pensée.

Je me suis amusé jadis à batir des problèmes de maths dont la résolution nécessitait un
instrument de calcul : il fallait donc analyser le problème, bâtir un algorithme, l'exécuter
sur une machine pour obtenir enfin le résultat ; on quittait le cocon de la classe où tout
tombe juste. Ces problèmes ont été édités par Belin, mais on ne les trouve plus, aussi
en ai-je fait une version électronique :
http://www.lulu.com/product/ebook/algorithmique-pour-le-lyc%C3%A9e---tome-1/11270264?productTrackingContext=product_view/more_by_author/right/1

Bonne journée,
Daniel Saada
www.daniel-saada.eu

danielsaada écrivait:

> tombe juste. Ces problèmes ont été édités par
> Belin, mais on ne les trouve plus, aussi
> en ai-je fait une version électronique :
> http://www.lulu.com/product/ebook/algorithmique-po
> ur-le-lyc%C3%A9e---tome-1/11270264?productTracking
> Context=product_view/more_by_author/right/1


Ta médiocrité est affligeante.

c.candide a écrit:

Note que Python permet très facilement de dessiner avec turtle et/ou Tkinter.

Ou avec Pygame.

Pourquoi ? La notion de fonction est facile à coder.

Disons que ce que projetmbc voulait dire par "dessiner" n'est pas très clair, on peut y comprendre beaucoup de choses.

Au stade débutant, je fais dessiner mes élèves avec turtle, de façon à mieux s'approprier la logique des boucles. Quand c'est visuel, y a pas photo, les notions passent mieux.

Au moment où ils doivent réaliser leurs propres projets, c'est souvent pygame qu'ils choisissent, car c'est le meilleur raccourcis pour faire un jeu sans trop se fatiguer. Dans ce cas le dessin est une étape de décoration.

Arnaud K écrivait:

---

> Au stade débutant, je fais dessiner mes élèves
> avec turtle,

(...)

> Au moment où ils doivent réaliser leurs propres
> projets, c'est souvent pygame qu'ils choisissent,
> car c'est le meilleur raccourcis pour faire un jeu
> sans trop se fatiguer. Dans ce cas le dessin est
> une étape de décoration.


Bon, je comprends plus rien. Tu illustres les notions d'algorithmique en classe de seconde avec Python dans le cadre de tes cours de maths ? Je n'arrive pas à savoir qui fait quoi, parce que les uns font de l'algobox, les autres n'utilisent aucun logiciel sur ordinateur, d'autres font de la POO et d'autres encore font un projet en pygame donc le spectre est large.

VBScript écrivait:

---

>
> Je ne voudrais pas paraître lourd, mais la
> programmation graphique c'est facile aussi en
> VBScript :



Excellent langage pour écrire des virus, vos élèves vont adorer

X:-(

un algorithme non récursif

Vu le caractère antinomique entre les mots "algorithmes" et "non récursif", vaut mieux que tu précises exactement ce que tu entends pas "algo non récursif"???

oups, pardon Daniel, je viens de comprendre. J'avais lu le mot "récursif" dans le sens logique et je croyais que tu demandais un algorithme qui est par exemple récursivement énumérable et non de complémentaire récursivement énumérable en tant que fonction, etc... X:-(X:-(

En fait tu demandes une procédure qui n'effectue pas un appel à elle-même loooool

Tu la veux en quel langage?

Code en Python :

DEBUT=1
FIN=6

def next(mot, n):
    i=n-1
    while i>=0 and mot[ i]==FIN:
        i-=1
    if i==-1:
        return "pas de suivant"
    else:
        mot[ i]+=1
        mot[ i+1:]=[DEBUT]*(n-i-1)
        return mot

def afficher(mot):
    for i in range(len(mot)):print mot[ i],
    print

NB_JETS=2
mot=[DEBUT]*NB_JETS

while mot!="pas de suivant":
    afficher(mot)
    mot=next(mot, len(mot))

1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 2
2 3
2 4
2 5
2 6
3 1
3 2
3 3
3 4
3 5
3 6
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6

Tiens, quelqu'un sait l'écrire en Maple qu'on compare ?

[Sur le forum, il faut écrire '[ i' (avec une espace) sinon l'afficheur lit une bannière BBcode de mise en italique. AD]

à Daniel: la remarque que te faisait projetmbc, c'est que la "récursivité" (au sens informatique, appel de soi-même par une procédure) est "conservative". Tout programme peut être réécrit de manière équivalente (faire la même chose) sans.

Cependant, il faut penser aux types de données utilisées, sinon, ça peut vite, bien que possible, devenir une usine à gaz.

Preuve: a:=f(a) fait la même chose que la chose suivante:

let diag x y = y (x x f)
a:=diag diag f

(à condition de bien choisir l'ordre d'évaluation)

En effet, à l'exécution, ça donne:

a ":=" diag diag f ":=" f (diag diag f)

qui est de la forme a:=f(a)




Appliqué à ton exemple précis, tu veux une f telle que f n :=g(1,f (n-1)), g(2, f(n-1)), ... ,g(6,f(n-1))

donc pas tellement besoin de passer par la preuve générale. Il suffit d'itérer n-1 fois "R:=t(R)" où R est intialement la liste demandée pour n=1 et où t est tel que f n := t(f (n-1))

En pascal, tout dépend comment tu poses la question. Est-ce que tu veux comme contrainte qu'on ne dispose que de l'instruction "write", auquel cas ça devient un exercice différent et d'ailleurs apparatenant à un champ d'exercices amusants, puisque plus soumis à la preuve (les hypothèses "informatiques théoriques" ne sont pas vérifées).

Donc je reformule ta question sous la forme "pascal":

Soit la procédure:

procedure deploi (s:string; n:integer);
var i:interger;
begin
if n<2
then for i:=1 to 6 do begin write(s);write('-');writeln(i) end;
else for i:=1 to 6 do deploi(entierversstring(i) + s,n-1);
end;

Exercice: écrire une procédure non récursvie qui fait exactement la même chose sans se servir de type compliqués (tableaux, dévoiement de string, etc)

Dans la catégorie où on n'autorise que write et read, voici une procedure récursive (la plus simple du monde)

[color=#0000FF]procedure prouve (a:string; var t:string);
var u,v:sting;
begin
    writeln (a); writeln('pourquoi?')
    readln (r);
    if r='hypo' then 
        t:= ' axiome: ' + a + ';' 
    else
        prouve('si ' + r + ' alors ' + a,u);
    prouve(r,v);
    t:=u+v;
end;[/color]

Question: comment programmer une procédure exactement équivalente sans appel récursif et sans trop tricher sur les types de données utilisés ?

à pmbc: mouais "en pratique" l'injection naturelle de l'ensemble des tableaux dans $\N$ explose ou poil trop vite

erratum au moins un peu le format de L

hé hé, j'aime bien que ça commence à sentir la discussion de vestiaire, en ce moment c'est d'actualité.

Quand je lis ces histoires de "mégaoctets", pourquoi (je ne connais pas python) ne pas tout simplement ne pas programmer le "chronomètre" (j'entends par là une petite procedure qui fait passer de (3;2;6;1;6) à (3;2;6;2;1); etc; etc pour les n-uplet (5uplets dans l'exemple)?

Ca ne consomme aucune mémoire (à part le papier de l'imprimante ou le buffer de sortie) et il suffti de programmer une fonction qui donne la longueur du uplet pour l'arrêter là où il faut et afficher "sa partie" qu'il faut.

lol oui possible, je ne connais pas python, c'était pour caser ma blague sur les vestaires surtout ....

par chronomètre, j'entendais faire défiler l'un après l'autre les éléments de $\{1;2;..;6\}^n$ l'un après l'autre, classés dans l'ordre lexicographique.

looool, tu utilises la numérotation auquel nous étions habitués dans notre enfance, pour les programmes en basic (10;20;30...) ainsi que les "goto". Ralala, ça nous rajeunit pas.

Soit dit en passant, je ne peux, avec toi, que regretter les condamnations par les vertueux pédagogues de l'informatique de l'outil "goto". A ma connaissance, on ne le retrouve ni en caml, ni en pascal, ni en C.

Leur motif était la lisibilité et la "bonne tenue" du programme, mais tu viens de montrer que le "goto", in fine, c'est quand-même bien pratique dans les cas exotiques.

Alors je crois qu'il est vrai que le basic de notre enfance n'accepte pas les appels récursifs si je me souviens bien. C'est marrant, que de souvenir...

Et effectivement, voici une bonne raison de chercher des programmes sans appels récursifs: utiliser un langage qui ne les implémente pas (assembleur, basic, et..?)

Original exception was:
  File "mot_suivant_mathsnet.py", line 13
    results = [  for i in range(1, diceSize) ]
                   ^
SyntaxError: invalid syntax

[Même remarque le [ i] a disparu car interprété comme bannière de départ d'italique. AD]

Ah, OK merci, cela explique l'erreur de syntaxe que je croyais due à une histoire de version de Python. Bon, curieux quand même que la balise de code ne soit pas une balise verbatim.

[Tant qu'a faire des citations, faisons des citations exactes. AD]

> Ah, OK merci, cela explique l'erreur de syntaxe
> que je croyais due à une histoire de version de
> Python. Bon, curieux quand même que la balise de
> code ne soit pas une balise verbatim.
>
>[Tant qu'a faire des citations, faisons des citations exactes. smiling smiley AD]


Pas compris. Tu veux dire que j'ai inclus ton commentaire dans la balise de code, (ce qui est vrai en effet) ?


projetmbc écrivait:

---

> C'était le sens du "OU PRESQUE".

Et bien ce n'était pas clair. Je ne vois pas ce que veut dire utiliser la version 3.0 "ou presque". Sois tu utilises la version 3.0 soit tu l'utilises, ce n'est pas un continuum.



> nuance... Pour mémoire, dans le message qui
> précédait, on parlait de la version 2.6 de
> Python.

Non pas avant que j'en ai parlé moi-même, relis le fil. D'ailleurs, tu m'as fait croire que ton code plantait chez moi pour une question de version alors qu'il s'agissait d'une question d'interprétation du texte par le parseur du bbcode du site. Ce n'est pas une question de version, sinon ton print aurait été une fonction (c'est ainsi en Python 3.0) et pas une instruction comme en Python 2.6.


> Pas besoin d'être agressif, c'était une remarque
> en l'air. Je sais que l'équipe de France a presque
> perdu toute chance mais de là à être agressif avec
> tout le monde...
> Sérieusement, il n'y avait aucun sous-entendu dans
> ma remarque "En Python, il y a plus simple".

J'ai parfaitement compris ce que tu as dis. Je maintiens complètement ce que je dis même si je veux bien retirer la connotation agressive. En même temps, essaye d'être plus rigoureux dans ton expression.



>
> Pour ce qui est du code donné, il répondait à la
> question. Ceci fournit un algorithme non récursif,
> certes codé en Python, mais tel que présenté c'est
> un algorithme. Comme quoi programmation et
> algorithme ne sont pas deux concepts totalement
> identiques...


Absolument pas. Si je devais retranscrire à la main ton code, je passerais mon temps à recopier de longue liste sur du papier, il me faudrait une montagne de papier, c'est pour ça que je t'ai dit que ton code n'était pas écologique

La différence entre algorithme et programmation n'est pas là. Un algorithme doit évidemment tenir compte des opérations de lecture et d'écriture.



>
> > Ta méthode est très primaire : il suffit de
> stocker
> > en mémoire tous les résultats de n jets pour
> avoir
> > ceux correspondant à n+1 jets. Pas très
> > développement durable ton code.
>
> Ce n'était pas son propos...

Et bien il ne fallait pas dire qu'en "Python, on peut faire plus simple [que mon code]" puisque finalement tu me dis que nos algorithmes n'étaient pas comparables.



> Parler de performance et mémoire en Python, c'est
> un peu de la rigolade... Sans "wrappers" pour des
> codes en Fortran ou en C, Python serait
> inutilisable dans de vrais projets.


Faux encore. C'est juste une possibilité que le langage offre. Et si elle était obligatoire, crois-moi que le langage serait peu utilisé parce qu'il n'est pas trivial d'écrire une extension Python en C ou en C++, l'API étant relativement complexe. Les performances de Python sont excellentes pour ce qu'on lui demande de faire. Python sait gérer du graphisme directement sans passer par du C compilé. 99% des applications n'ont pas besoin de la vitesse du C.

Et de toute façon, le problème n'était pas là : ton code utilisait 900 Mo octet de RAM juste pour afficher4 millions de nombres alors que ça ne nécessite RIEN.


> Mais je le répète, sans aucune agressivité, je
> n'ai fait que donner un ALGORITHME immédiat à
> comprendre.

C'est un algorithme très maladroit car son instantiation (avec ou sans langage de programmation) est très contraignante.


>
> A quoi bon 2**22 jets... Cela frôle la mauvaise
> foi. En tout cas, tout ceci est bien rigolo.

Qu'un programme informatique soit amené à examiner une par une 4 millions d'instance est assez banal. Si tu enseignes ça à tes élèves, tu leur donnes de mauvais réflexes. Un algorithme, indépendamment des questions d'implémentation, doit tenir compte des opérations de lecture et d'écriture. Un bon programmeur cherche à éviter les opérations de copie, car une copie c'est couteux en exécution et en mémoire, exactement comme pour un humain (un élève qui recopie le cours au tableau ou qui est puni de 100 lignes).

>
> Performance dans quel cadre ? Pour quoi faire ?
>

Parce que dans la réalité, si je veux obtenir tous les coups de dés possibles, je n'ai pas besoin d'une ramette de papier de 500 pages. Et donc mon algorithme doit traduire la simplicité de la procédure.

> De toute façon, on s'éloigne totalement du sujet
> de ce post.

Non, pas tant que ça.