Études : Purdue University
|
Je trouve le tuto très bon, et très bien expliqué, bien que j'ai eu un peu de mal à comprendre la partie: Complexité dans le pire des cas
Je tiens aussi à dire qu'avant de lire ce tutoriel, je n'y connaissais rien en algorithmique, maintenant, j'ai l'impression de bien mieux comprendre 
Hop hop, next chapter !
|
Groupe : aigris
Groupe : Bannis
Ville : Chevilly-larue
Pays : France métropolitaine
Études : Université Paris XII
|
arcaon : je trouve ça débile, mais passons...
Un tutoriel qui continue bien, et c'est tant mieux. Cependant, je crains que certaines notions soient peu facilement assimilables à quelqu'un qui n'a pas beaucoup de connaissances en ce qui concerne les fonctions mathématiques...
|
Ville : Paris
Pays : France métropolitaine
Études : INSA Lyon
|
Bon, je vais être moins gentil que les autres.
Tout d'abord, j'ai beaucoup de mal de savoir que penser de ce tutoriel. J'ai à la fois l'impression qu'il va trop loin pour le débutant en math (pour celui qui est au collège début de lycée) et qu'il ne le va pas assez pour ceux qui ont des connaissances en math.
Correction de l'algorithme : Rien à redire, il présente ce qu'est un algorithme valide. Tu aurais tout de même pu dire qu'il existe des algorithmes NP-Complet pour lesquels on a pas prouvé leur validité et que l'on utilise malgré tout. Mais ce n'est qu'un détail et le rajouté ne serait que, histoire de dire au lecteur qu'ils existent.
Complexité : Explique très bien qu'il y a différents types d'entrés et différentes choses à optimiser (autre que le temps d'exécution). Il y a cependant quelque chose que je n'aime pas du tout dedans. Tu expliques qu'en fonction de la machines, deux personnes ne vont pas obtenir le même résultat (ce que je conçois), mais tu laisse sous-entendre dans l'explication qu'un mauvais algorithme pourrait être compensé par un ordinateur puissant, ce qui est une aberration. Je pense qu'il faudrait rajouter que cette impression de rapidité n'est qu'à première vue, ou n'est qu'une impression. Ainsi qu'un petit exemple qui montre en quoi un algorithme bien fait est beaucoup plus intéressant qu'une machine puissante.
Mesure 'asymptotique' : Rien à dire.
Notation "grand O" : Je pense qu'il faudrait que tu définisses grand O, de même qu'expliquer que ce n'est pas la seule mesure (à la fois le débutant ne comprend pas la notion de comparaison de fonction, à la fois il faudrait aller plus loin pour l'initié). Il faudrait parler des limites vers l'infini avec les bornes asymptotiquement approchés (grand théta), mais aussi borne inférieur asymptotique (grand oméga), borne supérieur asymptotique (grand O) et leurs relation. De même expliqué petit o de xxx et petit oméga de xxx pour qu'un zéro ayant lu ce tuto et lisant un autre tuto ou livre comprenne les notations.
Dans ce style, pour ton exemple, 2N²+3N+5 est aussi = O(N^3), et = O(N^4) etc..
Enfin, j'ai l'impression que tu parachutes le faite que 2N²+4N-543 = O(N²), ce qui est vrai, mais tu n'explique pas pourquoi on néglige les termes d'ordre plus petit.
Complexité en temps, complexité mémoire : Rien à redire, si ce n'est que l'exemple des deux algorithmes et de leurs temps d'exécution aiderai grandement à la compréhension de O(N) et O(N²) qui ne doit pas vouloir dire grand chose de concret pour le zéro.
Complexité dans le pire des cas : La je ne suis tout simplement pas d'accord. Tu dis que le pire des cas est toujours pris par le programmeur. C'est faux. Tout est question de probabilité, si le pire des cas donne des performances dramatique mais qu'il n'arrive que une fois sur 3 millions, alors que le cas arrivant le plus fréquemment donne d'excellente performance, on ne va pas s'occuper plus que ça du pire des cas. Même si le pire des cas est utilisé fréquemment, il arrive qu'il ne soit pas le cas pris en compte.
Et enfin mon petit exemple pour expliquer les différences entre algorithme efficace et machine efficaces, je ne trouve de meilleur exemple que celui du livre de Thomas H. Cormen "Introduction à l'algorithmique" :
Prenons deux ordinateurs A et B. A permet 1000 000 000 d'instructions secondes alors que B seulement 1000 000 (A donc 1000 fois plus rapide que B). Les deux machines doivent trier 1000 000 de nombres. A via une méthodes en O(N²) (tri par insertion), et B en O(N*log2(N)) (tri par fusion). Le programmeur de l'ordinateur A est un boss, il code en très bas niveau et permet une exécution en 2N² (pour N entrés, il faut 2N² instructions). Alors, que le programmeur de la machine B est une brèle codant en haut niveau et fait un temps d'exécution en 50N*log2(N). (Constante de A beaucoup plus petite que celle de B.)
Malgré que toutes les chances paraissent du coté de A, regardons le temps d'exécution pour 1000 000 d'entrés :
Pour l'ordinateur A : 2000 secondes
Pour l'ordinateur B : environ 100 secondes. Soit 20 fois plus rapide.
Cet exemple devient encore plus parlant avec 1000 000 000 d'entrées, car il faudrait alors 2 à 3 jours pour A et 20 minutes pour B.
Je trouve cet exemple tellement parlant pour montrer qu'un petit gain en complexité ici, O(N²) devenu O(N*log2(N)) devient un énorme gain pour les performances.
Je trouve que ça montre l'importance et l'efficacité de l'algorithmique.
|
dont ask to ask
Groupe : Anciens
|
Citation Bon, je vais être moins gentil que les autres.
Pas de problème, ce sont aussi des commentaires utiles.
CitationJ'ai à la fois l'impression qu'il va trop loin pour le débutant en math (pour celui qui est au collège début de lycée) et qu'il ne le va pas assez pour ceux qui ont des connaissances en math.
Comme tu l'as remarqué, on a un peu le cul entre deux chaises en raison de la diversité du public. Le but que je me suis fixé, c'est de faire comprendre le maximum de choses possibles au collégien (donc en évitant les maths là où ça n'est pas nécessaire), tout en essayant d'apprendre aussi des choses à celui qui est allé plus loin (c'est pour cela qu'il y a parfois des détails plus poussés).
CitationTu aurais tout de même pu dire qu'il existe des algorithmes NP-Complet pour lesquels on a pas prouvé leur validité et que l'on utilise malgré tout.
Que veux-tu dire par là ? Le fait d'être NP-complet est une propriété du problème, indépendamment des algorithmes que tu mets en oeuvre et de leur correction.
Peut-être que tu fais référence aux méthodes heuristiques qui en quelque sorte cherchent une solution "satisfaisante" au problème, sans trouver forcément "la meilleure possible". Ça revient à formuler le problème autrement (au lieu de "trouver le chemin qui minimise ...", on dira "trouver un chemin qui est proche à 10% du minimum théorique", par exemple), et on peut parfois encore prouver la correction de l'algorithme (quitte à passer sur des modes de raisonnement probabilistes), même si effectivement on se contente souvent de vérifier que ça marche "en pratique". Mais j'essaie ici de donner des bases solides pour des algorithmes courants (les webmasters ne rencontrent pas forcément des problèmes NP-complets tous les jours), pas de faire dans la dentelle, c'est une première partie introductive.
Citation
Notation "grand O" : Je pense qu'il faudrait que tu définisses grand O, de même qu'expliquer que ce n'est pas la seule mesure (à la fois le débutant ne comprend pas la notion de comparaison de fonction, à la fois il faudrait aller plus loin pour l'initié). Il faudrait parler des limites vers l'infini avec les bornes asymptotiquement approchés (grand théta), mais aussi borne inférieur asymptotique (grand oméga), borne supérieur asymptotique (grand O) et leurs relation. De même expliqué petit o de xxx et petit oméga de xxx pour qu'un zéro ayant lu ce tuto et lisant un autre tuto ou livre comprenne les notations.
Comme tu l'as dit toi-même, on s'adresse aussi à des collégiens/lycéens, l'analyse asymptotique n'est pas forcément une bonne idée d'entrée de jeu. J'ai prévu depuis longtemps d'approfondir les fondements techniques de la notation de Landau, ce sera à priori en quatrième partie, pas avant.
CitationEnfin, j'ai l'impression que tu parachutes le faite que 2N²+4N-543 = O(N²), ce qui est vrai, mais tu n'explique pas pourquoi on néglige les termes d'ordre plus petit.
Tout à fait, encore une fois j'évite de parler de maths. Je ne dis pas que c'est compliqué, mais il y a des gens qui peuvent se "bloquer" dès qu'on leur montre des maths qu'ils ne se connaissent pas, et le but n'est pas d'effrayer le lecteur.
Je pense que la notion de complexité algorithmique est une notion intuitive que l'on peut utiliser de manière naturelle dans la plupart des cas (je ne parle pas des problèmes ultra spécifiques où il faut ressortir l'outillage formel au complet). J'essaie de faire assimiler aux zéros une conception "naturelle" de la complexité : "ah, on parcours la liste une fois, donc c'est linéaire, O(N)", et pas une version trop mathématisée (pourquoi se faire chier avec des théorèmes sur des formules de récurrence quand un dessin suffit ?).
CitationComplexité en temps, complexité mémoire : Rien à redire, si ce n'est que l'exemple des deux algorithmes et de leurs temps d'exécution aiderai grandement à la compréhension de O(N) et O(N²) qui ne doit pas vouloir dire grand chose de concret pour le zéro.
C'est le but du chapitre sur les grenouilles.
CitationComplexité dans le pire des cas : La je ne suis tout simplement pas d'accord. L'analyse de la complexité du cas moyen est plus compliquée et donne naissance à des sophistications infinies (qu'est-ce que le cas moyen ? comment sont distribuées les entrées ? qu'est-ce qu'un "arbre binaire choisi au hasard" ?). J'évite d'en parler au maximum, bien qu'une analyse du QuickSort soit elle aussi prévue pour la quatrième partie, mais ça ne me réjouit pas. Pour l'instant tu devras te contenter de la complexité dans le pire des cas (qui reste, quoi que tu en penses, une très bonne mesure dans le cas général : un utilisateur d'un programme n'a rien à cirer d'une différence de 10 millisecondes dans le cas moyen, mais si un jour ton interface met soudain un quart d'heure à répondre, ça risque de ne pas lui plaire du tout).
CitationA via une méthodes en O(N²) (tri par insertion), et B en O(N*log2(N)) (tri par fusion). [...] Je trouve cet exemple tellement parlant pour montrer qu'un petit gain en complexité ici, O(N²) devenu O(N*log2(N)) devient un énorme gain pour les performances.
<lecteur mode="élève de seconde">log2 ? c'est quoi log2 ?</lecteur>
Une présentation ultra-massacrée du logarithme va arriver dans la deuxième partie (ce bout là est déjà écrit). Mais en parler maintenant, c'est mettre la charrue avant les boeufs. Tu n'auras pas droit à du O(2^N) non plus, car la mesure de la complexité des algorithmes exponentiels est trop compliquée pour une introduction. Il va falloir se contenter de la comparaison linéaire/quadratique.
C'est le but du chapitre sur les grenouilles.
|
Ville : Paris
Pays : France métropolitaine
Études : INSA Lyon
|
Maintenant que je sais que ton but est de données des connaissances en algorithmique au collégien, ça change tout.
En effet, la plupart des partie technique décrite ne servent plus.
Poue les problèmes NP-Complets, tu as devnié ce que je voulais dire, en effet, je me suis trompé lors de la rédaction. Je pense quand même que pour la science, tu pourrais expliqué qu'il n'y a pas d'algorithme efficaces pour résoudre ses problèmes. Ça montre que l'on ne sais pas résoudre parfaitement tout les problèmes avec des algorithmes.
Pour 2N²+4N-543 = O(N²), je pense dans ce cas, même si tu n'explique pas pourquoi, que tu devrais dire que l'on ne prend en compte que les termes de plus grand ordre (N² ici). Pour que, même sans comprendre, le collégien puisse l'appliquer.
En effet, j'avais oublier le chapitre sur les grenouilles. Peut être qu'une petite référence au grenouille serait utile dans ce cas. Pour expliqué que O(N) et O(N²) sont la version mathématiques des grenouilles.
Citation : BluestormL'analyse de la complexité du cas moyen est plus compliquée et donne naissance à des sophistications infinies (qu'est-ce que le cas moyen ? comment sont distribuées les entrées ? qu'est-ce qu'un "arbre binaire choisi au hasard" ?). J'évite d'en parler au maximum, bien qu'une analyse du QuickSort soit elle aussi prévue pour la quatrième partie, mais ça ne me réjouit pas. Pour l'instant tu devras te contenter de la complexité dans le pire des cas (qui reste, quoi que tu en penses, une très bonne mesure dans le cas général : un utilisateur d'un programme n'a rien à cirer d'une différence de 10 millisecondes dans le cas moyen, mais si un jour ton interface met soudain un quart d'heure à répondre, ça risque de ne pas lui plaire du tout).
Alors, pour cette partie je ne lacherai pas le beefteak. Tu as écris dans ton tuto :
Citation : Bluestormon considère toujours que l'entrée donnée est la "pire" possible pour notre algorithme.
Ce qui est faux, on ne considère pas toujours, on considère la plupart des fois. Je ne dis pas de détailler les autres méthodes, juste de les évoqués, car en effet, le cas moyen fait appelle a des notions poussé en probabilité. Enfin, pour reprendre ton exemple, l'utilisateur s'en fout d'une optimisation de 10 milliseconde dans le cas moyen si un jour son interface risque de prendre 15 minutes à répondre. Il risque en revanche de préféré une optimisation de 1 minutes sur le cas moyen, quitte à perdre 3 minutes sur le pire des cas (si celui ci n'arrive que rarement bien sûr).
Enfin, ne te méprend pas, je trouve ce tuto une très bonne initiative. En le lisant, je me demandais justement comment tu allais faire pour introduire l'algorithmique sur le site du zero. Je dois avoué que je trouve le résultat frappant, mais comme tout, il peut être amélioré.
|
dont ask to ask
Groupe : Anciens
|
Citation
Poue les problèmes NP-Complets, tu as devnié ce que je voulais dire, en effet, je me suis trompé lors de la rédaction. Je pense quand même que pour la science, tu pourrais expliqué qu'il n'y a pas d'algorithme efficaces pour résoudre ses problèmes. Ça montre que l'on ne sais pas résoudre parfaitement tout les problèmes avec des algorithmes.
Pour 2N²+4N-543 = O(N²), je pense dans ce cas, même si tu n'explique pas pourquoi, que tu devrais dire que l'on ne prend en compte que les termes de plus grand ordre (N² ici). Pour que, même sans comprendre, le collégien puisse l'appliquer.
Tu n'as pas tort. Je vais voir si je peux rajouter ça quelque part, sans alourdir un texte déjà un peu trop chargé.
CitationCe qui est faux, on ne considère pas toujours, on considère la plupart des fois. Je ne dis pas de détailler les autres méthodes, juste de les évoqués, car en effet, le cas moyen fait appelle a des notions poussé en probabilité
Tu as mal compris le paragraphe en question. Je veux dire que, dans ce tuto, quand je dis "complexité" sans préciser outre mesure, alors cela signifie "complexité dans le pire des cas", et donc c'est bien "toujours" la "pire" entrée possible que l'on considère.
Par ailleurs, il y a déjà une phrase à la fin de cette sous-partie qui rajoute précisément les précisions que tu demandes :
CitationIl existe des algorithmes dont le cas "moyen" et le cas le pire ont une complexité très différente. Dans ce cas, il est possible de faire des études plus approfondies, mais ce sujet plus délicat ne sera pas abordé pour l'instant.
Le fait que je ne me suis pas bien fait comprendre montre que la formulation mériterait d'être clarifiée à cet endroit là. Je vais voir ce que je peux faire, merci pour avoir soulevé le problème.
|
dont ask to ask
Groupe : Anciens
|
Voilà, les modifs que j'ai faites viennent d'être validées (avec en plus une correction ortho, gg Octal !). N'hésite pas à aller voir les passages qui te chagrinaient pour me dire si tu trouves ça mieux.
(Je crois que j'ai laissé de côté ta remarque sur les heuristiques; je ferai ça un autre jour)
|
Ville : Paris
Pays : France métropolitaine
Études : INSA Lyon
|
Je suis passer rapidement voir les passages. Ça m'a l'air très bien. Bonne chance pour la suite.
|
Études : Polytechnique
|
Sympathique comme tutoriel.
Je me demande bien comment tu vas faire au moment des algorithmes à complexité logarithmique car expliquer le log au zéro lambda...
Enfin bon courage en tout cas je suis très fan de l'initiative !
Cependant je pense que tu devrais expliciter carrément la définition (en français et sans aucun formalisme) du O, expliquer clairement que tu fous dedans les termes qui croissent moins vite pour approximer la fonction. Parce que l'idée du sac est pas mal mais c'est pas hyper clair ensuite.
Enfin je pinaille pas mal, beau boulot !
Foncez y !
|
intuitu personae
|
Bonjour,
Moi j'aurais bien vu également que soit précisée la notion de "concision" dans l'explication.
Il est, à mon avis, important pour un débutant de comprendre que la description de son algorithme doit être le plus court possible.
Gourou, tu deviendras...
|
dont ask to ask
Groupe : Anciens
|
L'idée de concision aurait plus sa place dans un tutoriel "comment coder clairement". C'est très intéressant mais ce n'est pas le but du présent tuto. De plus, le mentionner en deux mots serait assez inutile : c'est évident pour tout le monde qu'un truc court c'est mieux qu'un truc long, pour qu'une telle remarque apporte une valeur ajoutée il faut la développer, et à ce moment là on entre vite dans le hors sujet.
J'ai parfois été tenté d'écrire un tutoriel sur le "bon code". Je le ferai peut-être un jour, et j'espère que quelqu'un d'autre le fera avant moi, mais dans tous les cas ce n'est pas pour cette fois ci.
|
arcaon
Trouvez une formation
Suggestions
Facebook
Google+