Ca dépend : en suivant l'algo à la lettre, la version C sera en O(n) et Haskell O(1).
Version imprimable
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 :Citation:
Envoyé par alex_pi
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.Citation:
Envoyé par PRomu@ld
??!Citation:
Envoyé par PRomu@ld
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.Citation:
Envoyé par PRomu@ld
Il faut définir les briques de base (qui varient selon les langages).
Cela revient quasiment à réinventer un langage.Citation:
Envoyé par PRomu@ld
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...Citation:
Envoyé par PRomu@ld
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 ;)