Trier des chaînes et questions d'ordre général sur l'algorithmique

Voici un algorithme que j'ai écrit hier dans le but d'utiliser le tri par selection pour trier un tableau de chaînes de caractères. Cette fonction doit servir à trouver l'indice de la chaîne qui se trouve en première position dans l'ordre alphabétique entre la case a et la case b du tableau.
D'abord je vous demande si c'est correct ensuite, est-ce que ça sert à quelque chose ? Parce que j'ai remarqué qu'en Pascal, par exemple, on peut comparer deux chaînes à l'aide d'un opérateur ">" ou "<".

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

fonction posmin(t:tab, a,b:entier):entier min := a pour i de a+1 à b faire ok := faux j := 0 répéter j := j+1 si (t[i][j]=t[min][j]) alors si j=long(t[min]) alors ok := vrai si long(t[min])>long(t[i]) alors min := i fsi   sinon ok := vrai si t[i][j]<t[min][j] alors min := i finsi jusqu'à ( ok = vrai ) ou ( j = long(t[min]) )   fin pour posmin:=min fin posmin   i est un compteur donc un entier, min étant la position du minimum est un entier ok est de type booléen

---

Puisque c'est ici qu'il y a des gens sympathiques et que c'est l'endroit idéal pour poser ses questions et qu'en ce moment je m'en pose pas mal... Je suis en bac -1 section Sciences de l'Informatique, la matière principale se nomme "Algorithmique et Programmation", on y apprend ce que je connais au nom d'algorithmique c'est à dire les boucles pour, répéter, les structures conditionnelles si, cas de, algorithmes de tri et de recherche... le tout en faisant des applications en Pascal, le seul langage qu'on apprend. Seulement, je me demande ce que c'est que l'algorithmique exactement. Ce que j'ai retenu de tout ce qu'on m'a dit c'est que c'est le langage en quelque sorte universel qu'on utilise pour programmer avant de passer à la traduction en un langage "compilable". La définition que je retiens ne me plaît pas beaucoup car je suis de plus en plus conscient de la différence qu'il y a entre les langages. Alors, je me dis qu'on ne peut peut-être pas utiliser le même algorithme dans deux différents langages. En d'autres termes, je ne suis pas en train d'apprendre LA programmation mais plutôt la programmation en Pascal. Si vous pouvez lever ce doute de mon esprit, je vous en serais très reconnaissant.
Merci.

tes questions sur l'algorithmie sont vastes...

D'abord , même en se limitant à Wikipédia, qui n'est pas une bible et encore moins un dictionnaire réel, la définition en est :

Citation:

---

Étude de la résolution de problèmes par la mise en œuvre de suites d'opérations élémentaires selon un processus défini aboutissant à une solution

---

Comme tu vois c'est vaste :aie:

En gros, ça regroupe tous les processus logiques que l'on peut trouver dans le monde touché par l'informatique (pour ce forum, mais ça peut être aussi dans les maths ou la physique pures), si possible exprimés soit en maths, soit en langage courant, mais pas en langage informatique, en évitant si possible les parties trop peu liées aux maths ou calculs (disons par exemple les choses comme demander le nom d'un fichier, ou afficher quelque chose).

C'est en ça que c'est universel : ce devrait être en mélange de langage courant et de maths, mais sans référence à un langage de programmation particulier.

Dans la pratique on s'adapte assez souvent, les langages n'étant pas trop éloignés les uns des autres en ce qui concerne les calculs de maths.

Dans ce sens, c'est bien de l'algorithmie, car on peut exprimer (même si c'est plus long) en phrases et symboles de maths la solution au problème, et donc c'est ensuite programmable dans n'importe quel langage.

Dans l'exemple que tu donnes, en fait, il y a un peu de mélange avec la syntaxe Pascal. Donc ce n'est pas exactement de l'algorithmie pure.

Mais pour ton problème "existentiel", même si tu apprends bien la programmation en Pascal, tu apprends cependant à formuler ton problème sous forme de texte, même si c'est un peu mélangé avec la syntaxe de Pascal. Et donc tu apprends quand même ce qui te servira pour n'importe quel langage plus tard ,quitte à avoir à changer quelques notations comme le := .

Enfin pour ton problème "technique", comme le Pascal est loin, il y des choses dont je ne suis pas sûr. Je ne sais plus si les tableaux commencent à 0 ou 1.
Mais je ferais de la sorte :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

min = Démarrer en position a   pour chaque i entre a+1 et b si 1er caractère de i < 1er caractère de min min = i sinon si 1er caractère de i = 1er caractère de min pour j = 1 jusqu'à plus petit(longueur i, longueur de min) si caractère de i,j < caractère de min,j min = i fin pour fin si fin pour fin si fin sinon fin pour

---

Tout d'abord merci d'avoir pris le mal de me répondre.

Citation:

---

même si tu apprends bien la programmation en Pascal, tu apprends cependant à formuler ton problème sous forme de texte, même si c'est un peu mélangé avec la syntaxe de Pascal

---

Nous ne sommes pas obligés, nous élèves, de formuler la réponse en texte.
Donc pour le moment, je ne suis pas réellement capable d'écrire un "vrai" algorithme qui serait traduisible en n'importe quel langage dans une seconde étape.
Dans les tests qu'on passe, on nous pose un problème de ce genre:
Remplissez un tableau T par n entiers positifs avec n>=2. L'utilisateur entre un nombre k, le programme doit afficher si k existe dans le tableau ou non.
1) Divisez le problème en modules.
2) Analysez et écrivez les algorithmes de la question 1).
3) Traduisez votre solution en Pascal.

C'est à nous faire croire qu'écrire un algorithme de cette manière signifie écrire une solution traduisible en n'importe quel langage de programmation. La preuve, on est amené à le traduire en Pascal !
L'analyse elle, consiste à écrire l'algorithme de bas en haut, chose ignoble insensée que je désapprouve. Mon professeur a accepté que je fasses une "spécification" qui est la solution en langage naturel. Même si ça me prend plus de temps à rédiger et à trouver les bons mots, je préfère ça que leur analyse qui n'a aucune raison d'être.

Citation:

---

quitte à avoir à changer quelques notations comme le :=

---

c'est vrai le := c'est du Pascal, en algorithmique l'opération d'affectation telle qu'elle est décrite dans mon livre, qui n'est ni une bible ni un coran, est représentée par une flèche vers la gauche, pointant la variable dont on veut changer la valeur.

Citation:

---

Je ne sais plus si les tableaux commencent à 0 ou 1.

---

à n'importe quelle valeur entière (ou plutôt scalaire puisqu'on peut utiliser des caractères) si j'ai bien compris mes cours, tout dépend de la déclaration
T : array[vd..vf] of type (vd : valeur de début)


Maintenant, si l'on compare la solution que tu as soumise à l'idée de ce qu'est l'algorithmique dans ma tête... Ta solution est un mélange de spécification et d'algorithmique. Dans mon livre, la boucle pour, de son nom structure itérative complète, a la syntaxe suivante :
Pour Cp de Vi à Vf faire
Instruction 1
Instruction 2
...
...
Instruction n
FinPour

Ce qui est différent de

Code:

---

pour chaque i entre a+1 et b

---

Laquelle est de l'algorithmique ?

Moi, j'ai soumis un algorithme (toujours suivant ce que je crois). Si c'était un examen j'aurais rédigé une spécification et cela aurait donnait ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Spécification de la fonction pos_min   Résultat : la position de la chaîne la mieux classée dans l'ordre alphabétique entre la case a et b d'un tableau de chaînes.   Traitement : Tant qu'on est pas sûr de quelle chaîne est la première entre les cases a et b du tableau, il faut parcourir tout le tableau (utilisation d'un boucle pour) ensuite comparer la chaîne supposée minimale avec l'élément du tableau en cours. Comparer deux chaînes signifie les comparer lettre par lettre de même rang j, jusqu'à pouvoir conclure laquelle est placée devant l'autre. Exemple : la lettre "b" quand on compare "abbe" et "abba" Ce qui signifie qu'on a deux cas : 1) la lettre comparée de rang j est la même -Soit c'est la dernière lettre de l'une des deux chaînes et là on peut conclure que la moins longue en nombre de caractère est plus petite -Soit ce n'est pas la dernière lettre, ce qui nous oblige à comparer la lettre de rang j+1 (donc pas de conclusion) 2) ou la lettre comparée de rang j est différente Là nous pouvons tout de suite conclure: -Soit la lettre est plus petite ; nous supposons alors que cette chaîne comparée est la chaîne minimale (en affectant i à posmin) -Soit la lettre est plus grande, nous ne changeons pas de supposition   Données : les positions de début et de fin a et b : entiers T : tab

---

Ensuite j'écris l'algorithme sans oublier le TDO, là où l'on déclare les objets, plus précisément, les variables locales dans une procédure ou une fonction.

Très étrange tout cela, qu'en pensez-vous ?

Citation:

---

Envoyé par katrena99

est-ce que ça sert à quelque chose ? Parce que j'ai remarqué qu'en Pascal, par exemple, on peut comparer deux chaînes à l'aide d'un opérateur ">" ou "<".

---

Je ne pense quand même pas qu'on peut également comparer des enregistrements avec les opérateurs '<' ou '>'. Donc comment vas tu faire pour trier un tableau d'enregistrements par exemple?

Citation:

---

je me demande ce que c'est que l'algorithmique exactement

---

C'est la science des algorithmes :) .

Citation:

---

Ce que j'ai retenu de tout ce qu'on m'a dit c'est que c'est le langage en quelque sorte universel qu'on utilise pour programmer avant de passer à la traduction en un langage "compilable".

---

Pas vrai. Ce langage dont tu parles est ce qu'on appelle un pseudo-language et il n'est utilisé qu'à des fins pédagogiques. Un algorithme est une méthode de résolution de problème et en principe chacun est libre de la formuler comme ca lui chante (en pseudo-langage par exemple :) ).

Citation:

---

En d'autres termes, je ne suis pas en train d'apprendre LA programmation mais plutôt la programmation en Pascal

---

En apprenant la programmation en Pascal, tu apprends la programmation :)

En effet, en algorithmique, tu apprend a formuler un probleme et une solution en pseudo-language destine a decrire ce qu'il faut faire pour resoudre le probleme avec un pseudo-language.

Le passage du pseudo-language a un language varie enormement dependant du language (VB6 et C# sera tres tres tres different).

En d'autres termes, l'algorithmique est tres proche des Mathematiques, alors que le programmation est plutot a part, proche de la logique (enfin ca depend du programmeur :mouarf: )

Citation:

---

En effet, en algorithmique, tu apprend a formuler un probleme et une solution en pseudo-language destine a decrire ce qu'il faut faire pour resoudre le probleme avec un pseudo-language.

---

Si c'est un pseudo-langage, pourquoi tient-on autant à ce qu'il soit respecté ? Dans un examen, une dérivation d'un mot-clé est considérée comme une erreur de syntaxe et c'est entre 1/2 et 1 pt de moins. N'est-ce pas quelque peu ridicule s'il s'agit d'un pseudo-langage ?

Merci à tous ceux qui ont répondu.

Citation:

---

Envoyé par katrena99

Si c'est un pseudo-langage, pourquoi tient-on autant à ce qu'il soit respecté ? Dans un examen, une dérivation d'un mot-clé est considérée comme une erreur de syntaxe et c'est entre 1/2 et 1 pt de moins. N'est-ce pas quelque peu ridicule s'il s'agit d'un pseudo-langage ?

Merci à tous ceux qui ont répondu.

---

Je suppose que c'est pour vous apprendre la rigueur .... :P

Citation:

---

Envoyé par katrena99

N'est-ce pas quelque peu ridicule s'il s'agit d'un pseudo-langage ?

---

Je suis 100% d'accord avec toi. Mais ...

Citation:

---

c'est pour vous apprendre la rigueur

---

;)

Et puis aussi c'est pas la meme matiere, en algo on juge la logique du resonnement et de la solution, en exam de programmation, on va te juger sur ta connaissance du language et des mots clefs.

Nous c'est la même matière, et avec un raisonnement très très tiré par les cheveux, on peut avoir aisément un 16 ou même un 17/20 à condition de respecter la syntaxe. Et tout cela sans que l'on nous demande de traduire en Pascal. En réalité, on teste nos facultés à apprendre les mots-clés ou plus généralement la syntaxe du pseudo-langage.
Mais au moins, dîtes-moi est-ce qu'au moins, grâce à mes professeurs, mon algorithme (plus haut) est facilement compréhensible ?

Dois-je en conclure que c'est non ?

ben....

:oops:

un peu, oui..

Disons que ta première formulation était presque correcte, à part les tableaux et les signes égal, et quelques broutilles.
La deuxième est carrément moins claire.... Ais c'est peut-être ça que te demande ton prof, j'en sais rien...

Inspires-toi de ce que j'ai mis... ;) (ça correspond un peu à ta première version, les signes particuliers en moins). Tu peux aussi remplacer le signe = par le mot égal....

J'ai pensé que la 2e version, en langage naturel, peut être comprise par des non-informaticiens. Ce n'est pas le cas ? Parce que je suis d'accord que lorsque l'algorithme n'est pas très compliqué, je préfère le lire plutôt que de lire la spécification. Seulement quand l'algorithme est compliqué, la spécification est très utile.

En fait, les cours d'algorithmie, j'ai toujours vu ca comme des cours pour "apprendre a penser". Rien a voir avec de la philo, je m'explique.
Vas dans la rue et demande a quelqu'un de trier un tableau, le plus probable, c'est qu'il va chercher le chiffre le plus petit (ou le premier mots par ordre alphabétique), le recopier quelque part, le barre du tableau initial et recommencer.
L'algorithmie sert a formaliser ce comportement, c'est a dire a le faire passer d'un traitement "intuitif" a un traitement "machine" ou tout est écrit. Avec un peu de pratique, on peut faire "tourner" l'algo dans sa tête, l'executer comme on le ferai avec un langage style pascal.

Ecrit un algo sous forme de math (ca, c'est typiquement un truc que je ne sais pas faire), de pseudo code, en francais, ou en pascal, ca reste de l'algo. Tu listes exhaustivements toutes les actions que l'ordi doit faire.

C'est la base de tout le reste. Après, chaque langage introduit ses propres notions. Faire un algorithme de tri en ocaml (Si je me souviens bien, ca doit être celui là ou on ne fait pas de while, juste des fonctions récursive (a vérifier)) est très different du même "algo" en pascal, mais les idées sous-jacente sont exactement les même a savoir par exemple "Aller lire la plus petite valeur, la stocker au bon endroit, et lire la plus petite valeur suivante".

Quand je disais qu'un cours d'algorithmie aprend a penser, c'est qu'un problème de prog nécessite un mode de pensé particulier, plus proche de la machine. Je sais pas si j'arrive bien a être clair...

Tes profs ralents parce que tu n'écrits pas ton pseudo-langage avec la bonne syntaxe, c'est parce que tu es dans un environement de cours. Ca apprend une certaine rigueur, par contre, si tu te ballade un peu sur les forums de prog, tu verras que quand quelqu'un donne un algo, c'est souvent un mélange de pseudo code / code tiré d'un ou plusieurs langage. Le but restant d'exprimer l'idée, le traitement que fait l'ordinateur.

Tu parles d'algorithme traductible dans n'importe quel langage, mais un programme écrit en pascal est traductible en n'importe quel langage, de même qu'un prog en ocaml, java ou c. Un programme est par définition un algorithme, appliqué a certaines contraintes (gestion de la mémoire, contrainte d'écriture, de langage) c'est vrai, mais quelque part, tout les programmes sont universels à la syntaxe près.

Bref pour résumer, a mon sens apprendre l'algorithmie, c'est aprendre a *penser* comme un ordinateur.
En esperant ne pas t'avoir définitivement embrouillé ^_^

Citation:

---

Envoyé par Rakken

...............
Bref pour résumer, a mon sens apprendre l'algorithmie, c'est aprendre a *penser* comme un ordinateur.
.....^_^

---

Euhh !!!

Dommage, j'étais presque d'accord avec toi, mais alors là c'est non...

Apprendre l'algorithmie est simplement apprendre à exprimer clairement la solution à un problème.

C'est la même chose qu'apprendre la grammaire sert à savoir comment construire une phrase (quelle que soit la langue) (avec éventuellement une légère nuance pour le chinois) pour pouvoir exprimer clairement tes idées.

La seule différence est que là les idées que tu veux retraduire sont la plupart du temps des raisonnements mathématiques ou mathématiquement exprimables.

Et c'est au contraire ne PAS penser comme un ordi (qui d'ailleurs ne pense pas et voit juste des courants éléctriques qui passent/passent pas en fonction des 0/1 qu'il lit).

Humm...
Oui et non... je crois que je vois ce qui te gène dans ma formulation. Tentons de faire plus clair.

Citation:

---

Apprendre l'algorithmie est simplement apprendre à exprimer clairement la solution à un problème

---

Je pense que ca va un poil plus loin que ca. Quand tu es face a un problème simple (mettons un tri de tableau, quel bel exemple ^_^) des solutions pour trier ton tableau, t'en a plein qui sont intuitive.
Quand je dis apprendre a "penser" comme un ordinateur, je veux parler d'une maniere bien particuliere de conceptualiser un problème.
C'est en gros la difference entre dire "Je prend le plus petit chiffre et le je recopie" et savoir que ca veut dire "je recopie le premier élément de mon tableau dans une variable "min", puis je parcours chaque case de mon tableau. Pour chaque case, si la valeur de la case est plus petite que "min", je recopie ma valeur dans "min".

J'ai eu l'occasion de me rendre compte au cours de mes études, notamment au début, que ce passage là n'est pas une "évidence" pour tout le monde. C'est apprendre cette facon la de penser que je voulais exprimer.

Et parce qu'il est bien vrai qu'un ordinateur ne pense pas, une ptite citation pour la route (si quelqu'un en connais l'origine, ca m'interesse ^^)
"Se demander si un ordinateur est intelligent et a peu près aussi stupide que de se demander si un sous-marin sait nager"