Bonjour,
je voudrais savoir quels sont les cours et documents que vous recommandez pour enseigner un module d'algorithmique ?
Merci d'avance, cordi@lement.
Version imprimable
Bonjour,
je voudrais savoir quels sont les cours et documents que vous recommandez pour enseigner un module d'algorithmique ?
Merci d'avance, cordi@lement.
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.
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.
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
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
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.Citation:
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".
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.
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.
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.
Le niveau est donné :
Pour ce qui est du langage, personne n'en a parlé et ça n'a rien à faire ici.Citation:
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.
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, ...).
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.
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 iciCitation:
Pour ce qui est du langage, personne n'en a parlé et ça n'a rien à faire ici.
Le niveau était ici :
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é).Citation:
Envoyé par sidahmed
Citation:
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é.
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).Citation:
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
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.
Merci pour vos références anglophones, cordialement.
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 ! 8-)
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ï
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.
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.Citation:
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.
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.
Ca n'est pas une question de langage, c'est le paradigme de programmation qui compte, je l'ai déjà dit.Citation:
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.
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.Citation:
Écris le même algo en C et en Sed et compare la complexité (à la fois en temps et en espace).
Non :evilred:. 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.Citation:
Ou encore : connaitre la longueur d'une chaine peut être en O(1) ou en O(n) suivant l'implémentation derrière ;
Ah ? Je ne l'ai pas vu...
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.
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.
Quelle est la complexité de cet algo ? Implémente-le naïvement en C et en Haskell et compare.Code:
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
Ca dépend : en suivant l'algo à la lettre, la version C sera en O(n) et Haskell O(1).
On a dit naïvement ! Ici l'exemple est simpliste donc passer à l'algorithme intelligent en C est immédiat, mais l'intérêt de l'évaluation paresseuse est surtout dans une meilleure modularité : a peut provenir de n'importe quel API et être n'importe quelle liste, infinie ou non, si l'API a été bien programmée et qu'il est possible de générer a paresseusement, il te suffit de faire :
pour obtenir le 3ème élément de b sans avoir à calculer tout a (et même sans effectuer réellement les deux premières multiplications de b), alors que faire la même chose génériquement (quel que soit la provenance de a) en C relève de la haute voltige.Code:let b = map (*2) a in b !! 2
--
Jedaï
Non plus, tu ne fais que développer ton algorithme récursif en un algorithme itératif. Tu économises l'espace de la pile (et est plus rapide en pratique puisque exit les empilements) et ça n'est pas le même algorithme. Mais là on en revient à une légende urbaine qui est qu'un algorithme récursif a une complexité plus élevé qu'un algorithme itératif. C'est faux. Dans la pratique c'est souvent plus rapide mais en terme algorithmique entre un algo récursif en théta(n) et le même en itératif en theta(n), il n'y a aucune différence.Citation:
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)
Ca n'est pas une question de langage, en algorithmique, tu te fixes un certain nombre d'opérations en O(1) ensuite tu construis les autres en utilisant ces opérations atomiques, tu peux suivant les cas avoir des fonctions en O(1) (comme la longueur de la chaîne), le tout est de le préciser lorsque l'on développe un algorithme. On peut très bien travailler sans avoir à se fixer un langage.Citation:
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.
Déjà d'une part, tu mélanges les paradigmes de programmation, et donc les algorithmes sous jacents. Mais dans la théorie, rien ne t'interdit de manipuler les structures infinies en C, pour peut que tu te définisses des modules adéquats. Certes, il va être plus long de faire du lambda-calcul en C qu'en OCaml, car les outils mis à dispositions ne sont pas adaptés. De plus, les paradigmes de programmation ne sont pas les mêmes.Citation:
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.
Mais je le dit et je le répète, le tout est de se placer dans un paradigme de programmation (itératif, fonctionnel, logique, ...) de bien énoncer ce qui est possible de ce qui ne l'est pas, de se fixer les opérations atomiques et celles qui ne le sont pas et on peut s'abstraire des langages de programmation. (c'est ce que fait knuth dans le TAOCP).
OK, c'est pour ça que j'avais ajouté la parenthèse. Tu considères donc que, non seulement un algorithme peut être implémenté de plusieurs façons, mais aussi qu'un seul code peut implémenter plusieurs algorithmes distincts (selon les optimisations du compilateur). Soit.
??!
Tous les compilateurs décents optimisent la récursion terminale... Et je n'ai jamais sous-entendu que la récursivité était lente.
C'est précisément ce que je disais.
Il faut définir les briques de base (qui varient selon les langages).
Cela revient quasiment à réinventer un langage.
Il faut spécifier toutes les opérations (et ces opérations varient selon les langages). Plutôt que d'imaginer quelque chose ex nihilo, je conseillais d'avoir un langage en tête.
Je recite une de tes phrases :
Et je maintiens : pas seulement le paradigme, mais aussi l'ensemble des opérations atomiques. Et pour choisir ces opérations atomiques, il est judicieux d'avoir en tête le langage que les étudiants apprendront. Comme quoi, le choix du langage a sa place ici. Selon que le langage à étudier sera C, Caml ou Haskell, les opérations atomiques varieront beaucoup. Il ne faut pas nécessairement reprendre intégralement le langage, mais il faut l'avoir en tête lors du choix des opérations atomiques.Citation:
Ca n'est pas une question de langage, c'est le paradigme de programmation qui compte, je l'ai déjà dit.
Salut,
Mon intervention ne vise qu'à expliquer ce que j'ai eu, mais j'ai trouvé le système intéressant...
Pour l'algorithmie de base, le prof a commencé par nous présenter (succintement) le flowchart, en insistant sur le fait qu'il est important de "subdiviser" les opérations trop complexes.
Quand il en est arrivé au problème des boucles et des tests (donc tres vite, on a utilisé le flowchart pendant... le deuxième cours (3heures/cours) à peu pres :P), il nous a sorti un petit cas, pas bien méchant pourtant, qui montre à quel point il est possible de se retrouver avec un "plat de spagetti" quelque peu indigeste, et a embrayé sur le nassi-shneiderman.
Il a alors commencer à parler, à peu pres dans l'ordre, de tableaux, de structures de données (et je parle ici réellement des structure: une personne qui a un nom, un prénom et un age :D) qu'il nous a habitués à utiliser sous forme de tableaux avant d'évoluer vers les structures plus complexes (piles, files, listes simplement chainées/doublement chainées/circulaires, arbres binaires, graphes, tables de hashage)
Les notions de tri et de récursivité sont apparues "naturellement" au moment où l'on avait les bases pour les comprendre (et parfois avec un peu de retard :P) ;)
Il a fini par nous parler du jackson pour tout ce qui est de la gestion des ruptures...
Il y avait, l'un dans l'autre, 10 à 15 % de théorie et tout le reste était de la pratique.
La plus grande partie du temps, il nous donnais quelques exercices à résoudre, nous laissait le temps de les faire et nous demandait de les présenter au tableau.
Il n'hésitait pas à reprendre l'algo point par point pour nous en montrer le bien ou le mal fondé (je commence: a vaut 1 b vaut 0, je rentre dans la boucle, je fais ceci, je fais cela, est-ce que a vaut 2 ben non, il vaut un, je retourne dans la boucle, ...)
Si quelqu'un n'arrivais pas à "percuter" sur un principe, il essayais de l'expliquer autrement.
Maintenant, c'étaient effectivement bien plus les "principes de bases" que l'ensemble des algorithmes régulièrement utilisés... Mais, selon le temps que va durer ton cours (ici, je parle d'un module de 120 heures, réparti sur 4 mois à peu près) rien ne t'empêche d'attaquer des algo plus particuliers.
Les exemples qu'il nous donnait en exercices étaient "relativement" simples au début (effectuer un tirage du lotto et trier les numéros sortis) et sont évidemment devenus plus complexes au fur et à mesure ;)
Nous avions l'occasion de passer sur ordinateur de temps en temps pour essayer de mettre les algorithmes créés en oeuvre en C, bien que le prof ait toujours regretté que ce ne soit pas un autre langage ;)
Une dernière précision: il s'agissait de cours du soir, et de ce fait, la notion de discipline était suffisamment souple pour lui permettre de rendre son cours intéressant, quitte à faire de temps en temps l'"imbécile".
De manière générale,retiens que si tu arrive à faire vivre ton cours (sans aller jusqu'à perdre tout crédit vis à vis des élèves), tu auras sans doute déjà fait le plus gros du chemin ;):D
Une UE d'université fait 54 heures, ton module fait donc deux fois et demi la durée de ce qui se fait dans une université. Cette durée plutôt longue, permet d'expliquer peut-être pourquoi tu as eu autant de pratique. Ca n'est pas toujours le cas et il faudra adapter au contexte. Parfois, on ne peut que présenter globalement les choses et laisser au soin des élèves d'approfondir. (tout dépend de leur niveau bien entendu).Citation:
(ici, je parle d'un module de 120 heures, réparti sur 4 mois à peu près
C'est bien pour cela que j'ai donné autant de précisions...
Je me rend bien compte que le temps de cours et le niveau de base ont leur importance, mais ça permet au moins de se faire un idée, et, finalement, la part de théorie reste relativement faible (évidemment, sur 20 on ne saura peut être pas faire autre chose :P) si on arrive à structurer correctement le cours ;)
Finalement, une fois que l'on a vu les tests (vrai faux et à choix multiples) les trois sortes de boucles et la récursivité, la théorie pour ce qui reste se limite, en gros à expliquer pourquoi on parle de pile au lieu de file, et à expliquer qu'il faut... l'acces à l'élément précédent et à l'élément suivant dans une liste doublement chainée :D
J'aime bien l'euphémisme. L'algorithmique est un domaine relativement large, la théorie est conséquente. A mon avis, le plus important n'est pas tant de savoir les choses, mais de savoir les appliquer aux problèmes que l'on peut avoir.Citation:
la théorie pour ce qui reste se limite, en gros à expliquer pourquoi on parle de pile au lieu de file, et à expliquer qu'il faut...
Et pourtant...
Je suis bien d'accord qu'il n'y a pas que les piles, mais:
Une fois que tu as fait comprendre le principe d'une pile, et, surtout, du LIFO (ou du FILO, je ne sais jamais :oops:) qui y est rattaché, que tu explique que c'est à utiliser quand tu est face à un problème pour lequel le dernier élément inséré est le premier à partir, le reste ne fait appel qu'à ce qu'on peut appeler "le guden spiel und gefund" (bien joué, bien senti)...
Et le mieux, c'est encore de fournir des exercices qui permettent de se rendre compte que "ici, utiliser une pile est intéressant car ca rentre dans le principe"...
Et bien ! 120h de cours pour finir avec les piles... Et les tas binomiaux, les graphes, les tables de hachages, ... C'est que du vent tout ça ? (Et je reste dans le basique là)
Alors effectivement il y avait peu de théorie dans ton cours, et beaucoup de pratique, reste à voir quel est l'objectif ! Et le niveau des élèves, j'insiste une fois encore puisqu'on n'enseigne pas de la même façon à des admis à un concours difficile ou à des 1ères années d'universités.
--
Jedaï
Tu as visiblement très mal interprété ce que j'ai écrit...
Bien sur, il n'y a pas que les piles, mais...
Quel que soit le concept expliqué, la théorie se résume souvent à répondre à 5 questions.
- Quoi :question:
- Pourquoi :question:
- Comment :question:
- Quels risques :question:
- Comment les éviter :question:
Chacune de ces réponses tient, en gros, sur une ligne, et au total, cela ne prend peut être que 5 à 10 minutes à exposer :P
Après viennent bien sûr la "démonstration" de l'utilité/de l'utilisation, avec les exemples et les contres exemples, les cas "peau de bananes" et les "pieges à c:aie:"...
Si je parlais des piles, c'est, tout simplement, parce que c'est la première chose qui me soit venue à l'esprit... mais le principe reste identique pour tous les autres concepts ;)