Discussion :

[Zavonen]

J'hésite à m'immiscer dans une discussion proche où les gens contribuent, 'travaillent' sérieusement. J'ai peur d'être pris pour un provocateur, l'avocat du diable et de me faire lyncher. Je souhaiterais donc m'exprimer sur une discussion parallèle où chacun pourrait donner son point de vue pour et contre sans qu'on puisse faire état de "péché contre l'esprit".

[millie]

Est-ce par rapport à ce forum http://www.developpez.net/forums/sho...d.php?t=221060 ?

Qu'est ce que tu entends pas harmoniser les notations ? Le thread parlait surtout d'harmoniser au sein du site. Est-ce la même chose pour toi ? Ou parles-tu d'une harmonisation mondiale ?

[Zavonen]

Est-ce par rapport à ce forum http://www.developpez.net/forums/sho...d.php?t=221060 ?

Qu'est ce que tu entends pas harmoniser les notations ? Le thread parlait surtout d'harmoniser au sein du site. Est-ce la même chose pour toi ? Ou parles-tu d'une harmonisation mondiale ?

Pas du tout, je souhaite mettre en doute la démarche même consistant à instituer une normalisation pour la description des algorithmes, au niveau du site ou à quelque niveau supérieur.

[millie]

Ce que je dis ne regarde que moi.

Pour le site de DVP (et la FAQ) : c'est une bonne idée d'uniformiser les notations. Par exemple, dans la FAQ, si l'on passe d'un algorithme à un autre, avec pas du tout la même notation, ce n'est pas très sympas (surtout pour les débutants). Ce serait un peu comme écrire un cours avec des notations qui changent un peu tout le tps (une fois x<-v pour l'affectation, une autre foix x:=v).

A un niveau supérieur, je pense également que ce n'est pas vraiment bien de normaliser la notation. Un algorithme c'est juste une suite d'instructions compréhensibles par l'homme et permettant de résoudre un problème. Donc, si une notation est compréhensible, je ne vois pas pourquoi en favoriser une par rapport à une autre.

[PRomu@ld]

J'ai peur d'être pris pour un provocateur, l'avocat du diable et de me faire lyncher.

non, ca n'arrivera pas, notre précédente discussion fortement nourrie avait le mérite d'être constructive et argumentée, je n'ai vu aucune provocation et je ne t'ai pas considéré comme l'avocat du diable ...

Pas du tout, je souhaite mettre en doute la démarche même consistant à instituer une normalisation pour la description des algorithmes, au niveau du site ou à quelque niveau supérieur

Peux-tu développer s'il te plais ? Que voudrais-tu remettre en cause ?

Je ne vais pas répèter ce qu'à dis millie, l'essentiel est là : je voulais qu'on uniformise (et pas normaliser, nous n'avons pas de telles prétentions ...) les façons d'écrires les algos que ça soit dans les articles, la faq ou la page source. Le but recherché était de faciliter la lecture et la compréhension.

J'hésite à m'immiscer dans une discussion proche où les gens contribuent, 'travaillent' sérieusement.

Le thread est ouvert à tous

[Zavonen]

Peux-tu développer s'il te plais ? Que voudrais-tu remettre en cause ?

Je ne vais pas répèter ce qu'à dis millie, l'essentiel est là : je voulais qu'on uniformise (et pas normaliser, nous n'avons pas de telles prétentions ...) les façons d'écrires les algos que ça soit dans les articles, la faq ou la page source. Le but recherché était de faciliter la lecture et la compréhension.

Votre démarche, que je résume ainsi: "Que tout le monde parle la même langue", est naturelle. En outre elle est récurrente dans le domaine de l'informatique théorique, et elle n'a de mon point de vue, jamais été fructueuse.
Il se trouve que je suis, comme on dit aujourd'hui un "senior". C'est un état présentant plus d'inconvénients que d'avantages, mais qui me permet simplement de parler de choses que j'ai vécues. Il ne s'agit pas de connaissances livresques. Cela dit, comme disent les chinois: "L'expérience est une lanterne que l'on porte dans le dos et qui n'éclaire que le chemin parcouru. Je n'essaierai donc pas de jouer au "vieux sage" et si possible, encore moins au "vieux con".
Au fait !
La première tentative que j'ai vécue, en matière d'uniformisation d'algorithmes (je situe cela, grosso modo pendant les 70) a été les "flow-charts", qu'on avait traduit par "organigrammes décisionnels" ou quelque chose comme ça. Vous devez quand même avoir entendu parler de ces jolis arbres avec boucles et tout et tout. Très décoratifs en vérité, et très envahissants. On en rit aujourd'hui, mais il fut un temps où, c'était la règle, on devait présenter tout traitement automatique de l'information sous cette forme. Je clos ici cette parenthèse historique, simplement pour illustrer que ce qui fut presque une religion, peut devenir après quelques décennies un sujet de plaisanteries.
L'éclosion des langages informatiques (début des sixties) correspond à la volonté de faire abstraction du matériel. On gagne donc un degré de liberté. Dès cette époque, on poursuit un premier mythe "Le mythe du langage universel". Le premier à avoir ce but avoué fut le PL1 d'IBM qui voulait faire la synthèse des deux ténors du marché qu'étaient à l'époque Fortran et Cobol. Puis il y eu ALGOL. ALGOL marque d'ailleurs une étape dans l'évolution des langages, il y a l'avant et l'après ALGOL. ALGOL est toujours le père spirituel d'une famille de langages essentiellement procéduraux, (PASCAL, ADA, pour ce citer que les plus connus, et d'autres aujourd'hui disparus LSE, etc...). ALGOL est aussi le père spirituel de la plupart des pseudo codes utilisés aujourd'hui pour la description d'algorithmes. La poursuite de ce mythe n'a d'ailleurs jamais vraiment cessé.
Très tôt les enseignants en algorithmique (c'est de mon point de vue une branche des maths applis) qui jusque là et depuis des millénaires exprimaient, avec un certain succès, leurs idées dans un langage naturel, sont tentés soit d'adopter purement et simplement un langage de programmation (confondant ainsi un algorithme et son implémentation) où d'inventer un formalisme à mi- chemin entre le langage naturel et les langages de programmation. La multiplication des langages, les renforce dans cette conviction de la nécessité de cette démarche. On voit donc fleurir les pseudo-codes (qui ne sont pour moi que des avatars d'algol), cette démarche continue aujourd'hui et toutes les tentatives d'unification, bien intentionnées, sont là pour le prouver, y compris au sein de ce forum.
Je développerai plus tard mon point de vue, selon lequel cette démarche est stérile, pour plusieurs raisons:
Le développement d'un formalisme fait immédiatemment retomber dans le piège des langages de programmation.
Cette démarche ne permet pas de prendre en compte, les nouveaux concepts et les nouvelles techniques de programmation.
Il faut faire le grand écart entre des abstractions mathématiques et leur piètres représentations dans la plupart des langages. Ce qui fait que de très beaux algos sont tout bonnement non implémentables. J'essaierai d'illustrer ce point par la suite avec des exemples simples.
C'est tout pour aujourd'hui.
Merci de réserver à mon initiative un accueil a priori non hostile.

[Zavonen]

Juste une petite mise au point avant de commencer:

Nous ne sommes pas des piliers du forum. D'ailleurs cette phrase est à double sens ...

Même avec beaucoup d'imagination, je ne vois pas quel peut être le sens 'caché'... Pour moi "pilier = qui soutient" point barre. Je me base uniquement sur le nombre de posts affiché pour affirmer que vous soutenez le forum.
Revenons à nos moutons. L'algorithmique, n'est pas (et n'a jamais été) une science "française". La contribution de nos chercheurs est marginale (à preuve, combien d'algos contemporains portent des noms "bien de chez nous"). Je n'en trouve aucun ... La raison est certainement complexe car les français réussisent bien dans d'autres domaines scientifiques. Elle est peut être culturelle, nos compatriotes sont trop tournés vers la théorie et ils manquent de sens pratique.
Voyons donc ce que font les américains dans leurs plus prestigieuses universités:
Commençons par le fameux M.I.T. Je cite l'ouvrage de référence "Introduction to algorithms" de Thomas Cormen, Charles Leiserson et Ronal Rivest. Ce bouquin est traduit en français sous le titre "Intoduction à l'algorithmique". C'est un pavé de plus de 1000 pages paru chez Dunod en 1994. Vous pouvez ajouter ce titre à votre biblio s'il n'y figure déjà.
Les auteurs ont choisi d'utiliser un pseudo code. Pour ce qui concerne la définiton du pseudo-code l'affaire est disons 'torchée' en un paragraphe d'une page (en 8 points) intitulé "Conventions concernant le pseudo-code. Je pourrais, si vous n'avez pas le document sous la main, vous envoyer un scan. Et ils ajoutent: "Parfois la méthode la plus claire est le langage naturel, ne vous étonnez donc pas de voir une phrase en français insérée dans une section de code 'réel' ". On ne peut pas faire plus souple.
Voyons maintenant Princeton.
Robert Sedgewick, directeur du département info, comme bon nombre de ces collègues (Patrick Henri Winston et autres) préfère utiliser un langage support, et il a choisi le 'C' parce que très populaire dans la communauté des programmeurs. Il a donc écrit "Algorithmes en langage C", un autre bouquin très intéressant également traduit chez Inter-Editions (Addison Wesley Europe), et que vous pouvez aussi ajouter à la biblio si ce n'est fait. Le langage C évolue, qu'à cela ne tienne, le même auteur publie "Algorithmes en C++" où il tire partie des nouvelles possibilités pour rendre les choses plus claires. Naturellement Sedgewick, comme il précise lui-même, refuse d'exploiter les particularités du 'C'. On peut donc utiliser un langage support pour peu qu'on refuse d'entrer dans les spécialisations et de publier du code optimisé, presque toujours parfaitement illisible.
En résumé, les Etatsuniens n'ont pas peur de coder directement dans un langage réel, et quand ils décident de s'en affranchir ils le font de façon très 'light'.
A méditer ...

[Zavonen]

Ce concept apparaît à la fin des 70 et favorise l'apparition des langages dits "orientés objets".
(Voir l'article de millie 'forum Q/R à intégrer dans les FAQ'.) La plupart des langages modernes appartiennent à cette famille, mais ils gardent un aspect procédural car ils sont en fait des hybrides résultant de la migration des langages classiques par addition d'une "couche objet" (C++, Java, C#, Python, Object Pascal, etc…).
L'algorithmique peut elle ignorer cette tendance ?
En programmation procédurale classique on pense en termes de traitement, de boucles imbriquées, de tests d'affectations, etc…En P.O.O. on pense en termes d'objets (de types de données).
Que prévoient les pseudo codes classiques ?
Généralement la possibilité de construire des types structurés par agrégation de types primitifs (record ou struct). La notion de "méthode" n'existe pas, mais on peut parfaitement se contenter d'écrire des fonctions spécialisées manipulant les structures.
Quels objets sont indispensables en algorithmique contemporaine?
Tous les types de collections (tableaux dynamiques, dictionnaires, etc..)
Tous les types de données dynamiques (listes, arbres ec….)
Dynasets pour l'accès aux B.D.
J'en passe !!!
Que faire pour décrire un algorithme 'moderne' utilisant ces concepts?
La méthode classique: Redéfinir les listes chaînées et les méthodes (ajouter un élément en tête, en queue, le retirer, etc…). Une fois de plus on réinvente la roue !
Ou alors adopter une hiérarchie de classes existante:
MFC pour les copains de Bill
wxwidgets (multi-plateformes, multi-langages – ex wxwindows)
Où encore les objets java prêts à l'emploi.
Au choix !
Quel formalisme choisir ?
C'est à mon avis le vrai nouveau défi pour le formalisme de type 'pseudo-code', mais les initiatives sont bien peu nombreuses.
Voici, quelles sont, à mon avis les vraies questions.
Il est préférable de réfléchir dans cette direction plutôt que de choisir entre trois notations concurrentes pour l'affectation ou bien de décider si on doit souligner les mots clefs ou bien les écrire en gras ou en capitales.

[millie]

Ce concept apparaît à la fin des 70 et favorise l'apparition des langages dits "orientés objets".
(Voir l'article de millie 'forum Q/R à intégrer dans les FAQ'.) La plupart des langages modernes appartiennent à cette famille, mais ils gardent un aspect procédural car ils sont en fait des hybrides résultant de la migration des langages classiques par addition d'une "couche objet" (C++, Java, C#, Python, Object Pascal, etc…).

Pour moi, la notion de type abstrait est à peu près équivalent à la notion d'objets (le polymorphisme et l'héritage étant moins bien perçu pour les types abstraits). Au passage, on peut faire de la programmation objet en C et de la programmation non objet en C++ grâce à cet approche.

Les types abstraits sont encore plus puissants, car on peut les définir sans avoir de code (un peu comme les interface en java) mais sont définis quand même (en utilisant les axiomes, ou même des mots en français).

Maintenant, rien n'empeche d'écrire les opérations du type sous la forme de méthodes, mais ceci implique de choisir une notation (notation pointée à la java, ou notation à la smalltalk). Mais il peut souvent suffir de l'indiquer, ce n'est pas vraiment problèmatique.

J'ai déjà vu du pseudo-code qui utilise des types abstraits (avec une notation objet), sans forcement à avoir à définir le code de l'objet.

En programmation procédurale classique on pense en termes de traitement, de boucles imbriquées, de tests d'affectations, etc…En P.O.O. on pense en termes d'objets (de types de données).
Que prévoient les pseudo codes classiques ?
Généralement la possibilité de construire des types structurés
par agrégation de types primitifs (record ou struct).

Normalement, un type absrait ne va pas être défini par son code. C'est une implémentation POSSIBLE pour un langage procédural/objet qui est proposé.

Quels objets sont indispensables en algorithmique contemporaine?
Tous les types de collections (tableaux dynamiques, dictionnaires, etc..)
Tous les types de données dynamiques (listes, arbres ec….)
Dynasets pour l'accès aux B.D.
J'en passe !!!
Que faire pour décrire un algorithme 'moderne' utilisant ces concepts?
La méthode classique: Redéfinir les listes chaînées et les méthodes (ajouter un élément en tête, en queue, le retirer, etc…). Une fois de plus on réinvente la roue !

Ici, on a affaire à des types abstraits. Ca ne sert à rien de les définir par du code. On peut aller plus loin que ça, on peut même dire que ça ne sert à rien de les définir par des axiomes, on peut juste l'expliquer par des mots français. Ca sera à la personne qui souhaitera effectivement implanter son algorithme dans un langage qui devra déterminer une implémentation (objet, fonctionnel ou procédural).

Détacher l'implémentation permet de s'abstraire de problème secondaire lié à un problème particulier. Tout ceci dans le but de simplifier au maximum la compréhension de la manière de résoudre un problème.

Par exemple, un code de Promu@ld sur les arbres :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
BFS( T : T_Tree )
 
     F : File
 
     SI T different de l'arbre vide ALORS
          F.Ajouter( T )
     FIN SI
 
     TANT QUE F est non vide FAIRE
 
          X <- F.Extraire()
 
          -- On peut effectuer une action sur X ici.
 
          Si X.Left() est différent de l'arbre vide ALORS
               F.Ajouter( X.Left() )
          SI X.Right() est différent de l'arbre vide ALORS
               F.Ajouter( X.Right() )
          FIN SI
     FIN TANT QUE

On utilise l'arbre en terme d'objet ici.

Maintenant, écrire sous la forme, c'est un peu pareil :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
BFS( T : T_Tree )
 
     F : Ensemble
 
     SI T different de l'arbre vide ALORS
          ajouter(F, T )
     FIN SI
 
     TANT QUE F est non vide FAIRE
 
          X <- extraire(F)
 
          -- On peut effectuer une action sur X ici.
 
          Si gauche(X) est différent de l'arbre vide ALORS
               ajouter(F, gauche(X) )
          SI droite(X) est différent de l'arbre vide ALORS
               ajouter(F, droite(X) )
          FIN SI
     FIN TANT QUE

[PRomu@ld]

C'est à mon avis le vrai nouveau défi pour le formalisme de type 'pseudo-code', mais les initiatives sont bien peu nombreuses.

A mon avis, il va faudrait adopter une notation par formalisme de programmation.

Pour tous les langages dérivés du lambda-calcul, il faudrait avoir une notation qui fasse principalement ressortir les définitions de fonctions et leurs applications.

Pour les langages dérivés des machines de turing (et machine RAM), il faudrait avoir un formalisme qui mette en oeuvre les itérations, affectation/lecture.

Mais cependant, ceci est vraiment bas-niveau (trop d'instructions proches du paradigme de programmation).

Il faut alors adopter des notation qui mettent en oeuvres des techniques plus évoluée. On aura alors les TAD, la Prog Objet (quoique je ne ferai pas de distinction aussi poussée entre TAD et OO)

Mais alors, on va parfois allez peut-être trop loin dans les notation qui vont alors ressembler à s'y méprendre aux langages.

Je pense qu'il faut donc limiter le pseudo-code jusqu'à une certaine limite et peut-être à un paradigme de programmation.

Mais il faut faire attention à ne pas prendre le problème à l'envers : ce ne sont pas les langages qui doivent "modeler" le pseudo-code.