Discussion :

[sidahmed]

Bonjour,
je voudrais savoir quels sont les cours et documents que vous recommandez pour enseigner un module d'algorithmique ?
Merci d'avance, cordi@lement.

[PRomu@ld]

En fait, l'algorithmique est assez large et possède plusieurs niveaux, parce qu'entre les structures de données simples (pile,files,arbres,graphes,...), leurs algorithmes classiques et les domaines plus pointus de l'algorithmique il y a du chemin, commence par bien définir le niveau (ce que tu veux que les gens sachent à la fin du module), après les documents sont innombrables,

tu peux en trouver quelques-uns ici :

http://algo.developpez.com/cours/

Sinon, tu peux toujours te baser sur des livres :

http://algo.developpez.com/livres/

Surtout le premier, introduction à l'algorithmique qui est une très bonne référence.

[sidahmed]

Bonjour, merci.
Moi, je vise, pour le moment, l'algorithmique niveau 1, c.-à-d les structures de données simples (liste, pile, file, arbre, graphe), méthodes de hachages, complexité des algorithmes, ...etc.
À bientôt.

[FR119492]

Salut.

Il y a chez nous un dicton qui dit: "C'est en forgeant qu'on devient forgeron!"
Alors, fais de l'algorithmique appliquée pendant 20 ou 30 ans. ensuite, pour l'enseigner, ça viendra tout seul, tes cours seront passionnants parce que tu sauras, d'expérience personnelle, de quoi tu parles tu n'auras plus besoin de bouquin, tes étudiants seront enthousiasmés. Et je sais de quoi je parle!

Bonne chance malgré tout.
Jean-Marc Blanc

[sidahmed]

Bonsoir,

Salut.

Il y a chez nous un dicton qui dit: "C'est en forgeant qu'on devient forgeron!"
Alors, fais de l'algorithmique appliquée pendant 20 ou 30 ans. ensuite, pour l'enseigner, ça viendra tout seul, tes cours seront passionnants parce que tu sauras, d'expérience personnelle, de quoi tu parles tu n'auras plus besoin de bouquin, tes étudiants seront enthousiasmés. Et je sais de quoi je parle!

Bonne chance malgré tout.
Jean-Marc Blanc

tout ce que vous venez de dire est vrai, cependant j'ai besoin de vos conseils pour bien débuter ma carrière d'enseignant, merci.

Cordialement.

[FR119492]

Encore une remarque, et peut-être quelques pistes.

Tout d'abord le terme "algorithmique" recouvre deux (ou plus) concepts qui n'ont pas grand-chose en commun.

1) En ce qui concerne les algorithmes de tri, etc., je n'ai pas de compétences particulières. Toutefois, je te recommande de voir si tu trouves ton bonheur dans le livre de Donald Knuth: "The Art of Computer Crogramming".

2) Ma spécialité est plutôt l'algorithmique numérique appliquée au métier de l'ingénieur. Pour ça, la référence est "Numerical Recipes". J'envisage de consacrer une partie de ma retraite à publier quelque chose, mais pour le moment ce n'est encore qu'un rève.

Bonne chance
Jean-Marc Blanc

[PRomu@ld]

1) En ce qui concerne les algorithmes de tri, etc., je n'ai pas de compétences particulières. Toutefois, je te recommande de voir si tu trouves ton bonheur dans le livre de Donald Knuth: "The Art of Computer Crogramming".

C'est une mauvaise idée, quand bien même tu pourrais trouver toutes les informations, son approche est bien trop compliquée pour être utilisé comme premier livre et/ou comme support de cours.

A mon avis, celui-ci est bien meilleur :

http://algo.developpez.com/livres/#L2100039229

Il est complet (quasiment tout ce que tu auras à enseigner est dedans), et a une approche beaucoup plus didactique que le Knuth.

Après, oui, après plusieurs années d'études, le knuth peut être intéressant mais pas pour l'enseignement.

[Elboras]

Je me pose une question,
ton boulot doit juste s'en tenir a des cours d'algo ?

Car pour moi le meilleur moyen que les eleves comprennent bien les algos et les maitrises bien et de faire des applications pour chaque concept.

En effet les cours d'algorithmie sont tres interressant, mais je vois encore trop d'eleve qui ont fait pas mal de cours d'algos mais tres peu applique dans une problematique complete, ce qui est dommage au niveau de l'entreprise car ces personnes ne sont pas tout a fait adapte.

Personnelement j'essayerais de leur faire appliquer certains conceptes dans un langage comme le C ou le Pascal.

[alex_pi]

Bonjour,
je voudrais savoir quels sont les cours et documents que vous recommandez pour enseigner un module d'algorithmique ?
Merci d'avance, cordi@lement.

Si je puis juste me permettre, il semble que tu n'as pas donné une information pourtant très importante : quelle est l'audiance de tes cours. En effet, l'approche sera radicalement différente selon que tu enseignes à des étudiants ayant un fort background en mathématiques théoriques, ou à des étudiants en première année de MIAS, même s'ils n'ont dans les deux cas jamais réellement fait d'informatique avant. De même, le choix du langage d'implémentation sera très différents selon le contexte, allant du pseudo code au C, en passant pas caml (probablement light) ou peut être Pascal (mais pourquoi donc ? :-\). Puis le choix du langage entrainera d'ailleurs certain choix pour les algo enseignés. On présentera plus volontier l'algo de tri fusion dans le cadre d'un langage fonctionnel que dans celui d'un langage impératif.
Bref, le fait que ce soit des débutants en algorithmique ne donne pas toute l'information nécessaire aux choix de l'approche.

[PRomu@ld]

Le niveau est donné :

Moi, je vise, pour le moment, l'algorithmique niveau 1, c.-à-d les structures de données simples (liste, pile, file, arbre, graphe), méthodes de hachages, complexité des algorithmiques, ...etc.

Pour ce qui est du langage, personne n'en a parlé et ça n'a rien à faire ici.

[Elboras]

Le niveau est donné :



Pour ce qui est du langage, personne n'en a parlé et ça n'a rien à faire ici.

Si j'en ai parle, enfin pas d'un choix de langage, ici ce n'est pas notre soucis.
mais du faite qu'il est toujours bon de faire des petites application pour que les etudiants impriment bien les concepts, apres peut etre que des personnes vont etre completement en desaccord avec moi sur ce sujet et proneront plutot de rester tres theorique, je ne sais pas

[pseudocode]

Si j'en ai parle, enfin pas d'un choix de langage, ici ce n'est pas notre soucis.
mais du faite qu'il est toujours bon de faire des petites application pour que les etudiants impriment bien les concepts, apres peut etre que des personnes vont etre completement en desaccord avec moi sur ce sujet et proneront plutot de rester tres theorique, je ne sais pas

Ca ne me dérange pas qu'il y est un peu de code pour expliquer un algo. La seule chose c'est qu'il ne faut pas utiliser des optimsations spécifiquez au langage lors de l'implementation.

C'est parfois difficile de ne pas employer "telle fonction" ou "telle structure" spécifique au langage, tellement ca semble naturel (les cast en C, la STL en C++, les generics en Java, ...).

[alex_pi]

Le niveau est donné :

Moi, je vise, pour le moment, l'algorithmique niveau 1, c.-à-d les structures de données simples (liste, pile, file, arbre, graphe), méthodes de hachages, complexité des algorithmiques, ...etc.

Je ne suis pas d'accord. Ce qui a été donné, c'est le niveau en algorithmique, qui n'a rien à voir avec le niveau des étudiants. Je ne pense pas que l'on enseigne la notion de complexité de la même façon a des étudiants maitrisant parfaitement la notion de limite et même d'équivalence entre fonctions (puisque les notation O et o sont utilisés en math) qu'à des étudiants venant d'avoir leur bacho. S'adapter à son auditoire est ce qui manque à un très grand nombre d'enseignant.

Pour ce qui est du langage, personne n'en a parlé et ça n'a rien à faire ici.

Tu dois bien exprimer ton algo d'une façon où d'une autre à un moment donné. Alors que ce soit en pseudo code ou en caml-light, il y a des fois où globalement il n'y a que la langue qui change, Mais la version caml-light pourra être exécuté. Pour certains étudiants, entre s'entendre dire "une complexité exponentielle ne pourra jamais être acceptable" et tester l'implémentation naïve de la fonction de fibonnacci contre son implémentation en log(n), il y a une grosse différence pédagogique. Donc je pense que se poser la question d'un choix de langage n'a pas rien à faire ici

[PRomu@ld]

Le niveau était ici :

algorithmique niveau 1

Le niveau du cours induisait un peu le niveau des élèves. Ici, les élèves auront un niveau relativement faible en terme d'algorithmique (débutant ou tout juste initiés). Pour ce qui est de la notion de limite, la notation en algorithmique (grand O, ...) ne la pousse pas très loin et devrait donc être accessible à tous les bacheliers scientifiques (ou alors le niveau du bac aurait bien changé).

Tu dois bien exprimer ton algo d'une façon où d'une autre à un moment donné. Alors que ce soit en pseudo code ou en caml-light, il y a des fois où globalement il n'y a que la langue qui change, Mais la version caml-light pourra être exécuté.

Pour certains étudiants, entre s'entendre dire "une complexité exponentielle ne pourra jamais être acceptable" et tester l'implémentation naïve de la fonction de fibonnacci contre son implémentation en log(n), il y a une grosse différence pédagogique. Donc je pense que se poser la question d'un choix de langage n'a pas rien à faire ici

En fait si tu as un algo en log(n), quelque soit le langage qui implémentera cet algorithme la complexité restera la même. Perdre les étudiants dans des considérations de langage n'est pas une mauvaise chose (j'ai déjà entendu des étudiants dire qu'un algo avait une meilleure complexité parce qu'il était écrit en C, c'est dire).

Leur montrer dans la pratique ce que peut représenter la complexité soit en temps, soit en espace et ce qui est acceptable pour nos machines actuelles peut être intéressant mais ça ne relève pas d'un cours d'algorithmique pure (mais plus d'un cours d'algorithmique et programmation).

De plus pour comprendre ce qu'est une pile, a mon avis pas besoin de langage de programmation, ça devait être séparé du cours d'algo. Ensuite reste à la charge des étudiants d'implémenter les algorithmes dans le langage qu'il souhaite.

[sidahmed]

Merci pour vos références anglophones, cordialement.

[Jedai]

J'aurai tendance à être assez d'accord avec PRomu@ld pour dire que le Cormen est plus adapté que le Knuth "Art of Computer Programming" à l'apprentissage de l'algorithmique. "Numerical Recipe" ne semble pas être non plus ce dont tu as besoin (si tu enseignes surtout les structures de données et les bases de l'algorithmique).

Le Cormen est vraiment idéal dans ton optique, jettes-y un coup d'oeil, tu ne le regretteras pas !

Par contre je ne suis pas tout à fait d'accord pour dire que le langage enseigné n'a aucune espèce d'importance : qu'il soit enseigné dans le même cours (à éviter je pense) ou en parallèle dans un/des autre(s) cours, le choix de ce langage va influencer l'ordre d'introduction des algorithmes et des structures de données à mon avis.

--
Jedaï

[LLB]

Complètement d'accord avec Jedai.

Le Cormen est bien plus clair que le Knuth (qui n'est pas très accessible aux débutants).

Et le choix du langage a son importance. On se fiche de savoir si c'est C++, Java, Delphi ou C#. Mais entre une orientation fonctionnelle et une orientation impérative (sans parler des autres paradigmes encore plus éloignés), ça change un peu.

En fait si tu as un algo en log(n), quelque soit le langage qui implémentera cet algorithme la complexité restera la même.

Souvent, oui. Mais pas forcément : ça dépend des opérations de base que propose le langage et même des optimisations gérées par le compilateur. Par exemple, optimiser la récursion terminale réduit la complexité spatiale de l'algorithme. Écris le même algo en C et en Sed et compare la complexité (à la fois en temps et en espace). C'est un exemple un peu extrême, mais c'est pour montrer que ça peut jouer. Ou encore : connaitre la longueur d'une chaine peut être en O(1) ou en O(n) suivant l'implémentation derrière ; du coup, appeler la fonction length dans une boucle peut être plus ou moins couteux.

Mais surtout : en fonction du langage et du paradigme choisis, on privilégiera un algo plutôt qu'un autre. La factorielle et le Fibonacci pourront être écrits en récursif ou en itératif. De même pour les tris, selon le langage que l'on a en tête, on présentera un algo plutôt qu'un autre, comme l'a dit alex_pi.

Donc, il faut avoir un langage en tête. Bien sûr, il faut éviter de faire le cours spécifiquement pour ce langage et essayer de présenter les principes généraux.

[PRomu@ld]

Et le choix du langage a son importance. On se fiche de savoir si c'est C++, Java, Delphi ou C#. Mais entre une orientation fonctionnelle et une orientation impérative (sans parler des autres paradigmes encore plus éloignés), ça change un peu.

Ca n'est pas une question de langage, c'est le paradigme de programmation qui compte, je l'ai déjà dit.

Écris le même algo en C et en Sed et compare la complexité (à la fois en temps et en espace).

Voilà un exemple précis de ce qui ne va pas, si c'est le même algorithme, c'est la même complexité ! Le temps n'a aucune espèce d'importance. C'est justement pour cette raison que l'on ne doit pas trop mêler la programmation(implémentation) de l'algorithmique.

Ou encore : connaitre la longueur d'une chaine peut être en O(1) ou en O(n) suivant l'implémentation derrière ;

Non . Ca n'est pas le même algorithme qui sera utilisé, il n'y a pas de comparaison possible. L'implémentation ne change pas la complexité de l'algorithme. En O(n) tu parcours la chaîne et en O(1) tu ne fait que lire un champ d'une structure.

[LLB]

Ca n'est pas une question de langage, c'est le paradigme de programmation qui compte, je l'ai déjà dit.

Ah ? Je ne l'ai pas vu...

Voilà un exemple précis de ce qui ne va pas, si c'est le même algorithme, c'est la même complexité ! Le temps n'a aucune espèce d'importance. C'est justement pour cette raison que l'on ne doit pas trop mêler la programmation(implémentation) de l'algorithmique.

Et l'exemple de la récursion terminale (et il y a plein d'autres optimisations du même genre) ? Si le compilateur l'optimise, ça modifie l'algorithme ? (après, tout dépend de ce que l'on entend exactement par algorithme)
Il y a plein d'algos que l'on peut écrire en O(n) en C et qui ne peuvent pas être écrits en O(n) en Sed, juste parce que les outils de base ne sont pas les mêmes (par exemple, faire une addition). Mais d'accord, ce n'est pas le même paradigme.

Ca n'est pas le même algorithme qui sera utilisé, il n'y a pas de comparaison possible. L'implémentation ne change pas la complexité de l'algorithme. En O(n) tu parcours la chaîne et en O(1) tu ne fait que lire un champ d'une structure.

Je ne parle pas de l'algo de length, je te parle d'un algo qui utilise length. Length est une brique de base dans beaucoup de langages, mais de son implémentation peut dépendre la complexité de l'algo qui l'utilise.
"Pour i de 1 à la longueur de s, afficher le ième caractère de s." Une implémentation naïve dans certains langages pourra donner une complexité quadratique. On a besoin de connaitre le langage associé au cours : comment se calcule la longueur d'une chaine ? et est-ce que la boucle for recalcule la condition d'arrêt à chaque itération ou pas ? De plus, en fonction du langage choisi, les indices d'un tableau commencent à 0 ou à 1 (et ça peut être bien d'utiliser la même convention dans le cours d'algo et dans l'implémentation plus tard).

Et la manipulation de structures de données infinies ? Certains algos tournent bien en Haskell, alors qu'ils provoquent une boucle infinie dans d'autres langages.

Code :

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

1
2
3
soit a, l'ensemble des entiers de 1 à n (n > 3)
soit b = l'ensemble composé des 2 * i, pour tout i appartenant à a
renvoyer le 3e élément de b

Quelle est la complexité de cet algo ? Implémente-le naïvement en C et en Haskell et compare.

[alex_pi]

Code :

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

1
2
3
soit a, l'ensemble des entiers de 1 à n (n > 3)
soit b = l'ensemble composé des 2 * i, pour tout i appartenant à a
renvoyer le 3e élément de b

Quelle est la complexité de cet algo ? Implémente-le naïvement en C et en Haskell et compare.

Euh, 6 ? :-\