[Basic] Implémentation de quelques structures de données
Posté le 14/03/2016 22:22
Hey Casiofans !
J'ai pensé plusieurs fois à un tutoriel présentant certaines structures de données pratiques, car nombreux sur ce site ont appris l'informatique sur Internet et n'ont pas connaissance de celles-ci, ou ne savent simplement pas comment les implémenter. Je me suis donc mis à cette tâche, et ai rédigé un tutoriel d'une dizaine de pages, présentant les piles, les files et les graphes, avec leur implémentation en Basic et un exemple illustratif (code théorique + code en Basic). Les parties sont classés par difficulté croissante : la première est très accessible, la deuxième assez accessible, la troisième est plus compliquée.
J'ai rédigé ce tutoriel avec
LaTeX, qui permet de faire des documents très professionnels incluant formules mathématiques, graphes, etc (les publications, dans le monde de la recherche, sont écrites avec LaTeX).
Lien (pdf) :
Implémentation de quelques structures de données usuelles en Basic Casio
Table des matières :
Introduction
1 Les piles : First In, Last Out
1.1 Présentation
1.1.1 Définition
1.1.2 Exemple d'algorithme faisant intervenir une pile
1.2 Implémentation avec une List
2 Les files : First In, First Out
2.1 Présentation
2.1.1 Définition
2.1.2 Exemple d'algorithme faisant intervenir une file
2.2 Implémentation avec une List
3 Les graphes
3.1 Présentation
3.1.1 Exemple introductif
3.1.2 Généralités sur les graphes
3.1.3 Notion de matrice d'adjacence
3.1.4 Problème proposé
3.2 Implémentation par matrice d'adjacence
Conclusion
Copyleft
Pages Wikipédia reliées
Fichier joint
Citer : Posté le 15/03/2016 18:38 | #
Je suis étonné que personne n'ait réagi avant sur ce travail pertinent et exclusif, superbement réalisé !
Félicitations, c'est vraiment un tutoriel de qualité, et ça permet à ceux qui commencent la programmation avec le Basic de voir des structures de données un peu plus évoluées que celles de base proposées par la calculatrice.
Merci !
La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Citer : Posté le 15/03/2016 19:11 | #
Merci beaucoup pour ton retour !
Je crains que le tutoriel ne cible pas très large, car ces structures de données ne sont pas la priorité de quelqu'un qui apprend le Basic, mais si cela peut inspirer certains codeurs actifs, afin d'implémenter des algorithmes efficaces avec ces structures, c'est ça de gagné.
Avec la théorie des graphes, on résout des sudokus en temps polynomial, on fait des IA d'ennemis qui ne restent pas bloquées devant un mur, etc
Citer : Posté le 15/03/2016 20:24 | #
J'ai tout lu, c'est clair vraiment bravo, j'ai juste une remarque concernant l'algo pour les files :
PxlOn Y,X
1->D
2->F
{1,-1,i,-i}->List 2 While I != F
PxlOn Y,X
1->D
2->F
{1,-1,i,-i}->List 2 While [red]D[/red] != F
J'ai adoré la partie sur les graphs
Citer : Posté le 15/03/2016 21:06 | #
Merci pour le signalement de ces erreurs ! La première est une faute de frappe (même touche mais sans maj), et la deuxième c'est que j'ai changé le nom de la variable I en D et ai oublié un endroit.
Bref j'ai mis à jour le fichier !
Content que la partie sur les graphes soit appréciée aussi, j'ai hésité à la mettre mais me suis dit que c'était important, ça me sert très souvent, et en même temps ça m'a permis de tester le temps d'exécution d'un parcours en largeur sur calto, et j'ai été agréablement surpris (en testant sur Prizm qui plus est, ça doit être encore mieux sur G85).
Citer : Posté le 16/03/2016 09:53 | #
Tu l'as enfin sorti, merci ça va être super pratique.
Citer : Posté le 16/03/2016 18:06 | #
Je suis très agréablement surpris, c'est du super boulot !
La partie sur les graphes est particulièrement intéressante.
D'ailleurs, pensez-vous qu'il serait utile de pouvoir visualiser ce genre de documents directement sur PC (en les écrivant dans le langage du forum) en leur ajoutant des options d'exportation ? C'est tout à fait réalisable techniquement, à part sans doute les graphes, mais ceux-là on peut demander à LaTeX d'en générer les images à la volée.
Citer : Posté le 16/03/2016 18:33 | #
c'est vrai que de le voir direct sur PC serait très pratique, mais il faut laisser le pdf, car il est utile pour le consulter hors-conection.
Citer : Posté le 16/03/2016 20:55 | #
C'est vraiment ce genre de tutoriels dont on a besoin pour alimenter la v5
Écrire des tutos ne me déplaît pas, et je me suis souvent dit que de nombreux algos et notions algorithmiques mériteraient une petite vulgarisation (je pense sortir un tuto sur efficacité/complexité d'un programme quand j'aurai du temps, par exemple). Mais du coup ça sortirait souvent du cadre de la programmation Casio, je me tâte sur le support sur lequel publier les contenus de ce genre que je réaliserai quand j'aurai fini ma prépa.
Après, même sur Casio, il y a encore pas mal à faire, parce qu'on apprend aux gens le langage Basic et des astuces, mais pas comment bien programmer. Si je ne suis plus apte à faire des tutos sur le Basic lui-même, des tutos sur des notions de codage appliquées au Basic peuvent être utiles, et je commence à acquérir un bon niveau d'algorithmique.
D'ailleurs, pensez-vous qu'il serait utile de pouvoir visualiser ce genre de documents directement sur PC (en les écrivant dans le langage du forum) en leur ajoutant des options d'exportation ? C'est tout à fait réalisable techniquement, à part sans doute les graphes, mais ceux-là on peut demander à LaTeX d'en générer les images à la volée.
Les pdf cumulent beaucoup d'avantages : ouvrables dans le navigateur, ou hors-ligne sur n'importe quel appareil, imprimables, etc, alors que les tutos du site actuel ont le défaut de n'avoir pas la moindre portabilité : ils sont faits pour être affichés en BBcode avec les fonctionnalités du site. L'idée d'un éditeur avec des fonctions d'exportation est bonne, mais c'est un gros boulot pour un résultat moindre, au regard d'outils déjà existants. De plus, si perfectionné que soit notre éditeur, et même s'il incorpore un système permettant d'inclure des équations LaTeX, il ne remplacera pas les modules de LaTeX permettant diverses choses comme construire des graphes, de jolis tableaux, etc. Pour des tutos et astuces courts, un topic est pratique, mais pour des formats un peu plus long il apparaît peu adapté. J'ai fait un test, en postant un pdf et non un topic, vos avis sur le format m'intéressent donc.
D'ailleurs, petite remarque : si le rendu d'équations LaTeX m'apparaît une super idée pour la v5, je pense en revanche qu'il faut que leur rendu ne soit pas fait à la volée côté client, mais une fois côté serveur, lorsque le message est posté, parce que sur un forum que j'ai co-géré, on avait mis le rendu coté client à la base, et sur mobile c'était très long.
Citer : Posté le 16/03/2016 23:44 | #
Si on poste les tutos sous format PDF, il faut qu'on se mette d'accord sur un thème graphique, et surtout qu'on intègre un lecteur en ligne (sans téléchargement)
Ajouté le 16/03/2016 à 23:46 :
Mais apres reflexion c'est l'option qui me plait le moins. La fonction "exporter en pdf" me paraît bien plus adaptée. Et puis vu le boulot que ça demander la v5, d'un on est pas à ça près, de deux on peut déléguer à quelqu'un de motivé ça reste qu'un script Python indépendant du reste.
Citer : Posté le 17/03/2016 13:44 | #
Je comprends ton point de vue Louloux, et je suis d'accord que LaTeX est bien plus puissant. Bon, et bien on peut générer du HTML à partir de LaTeX non ? Et le lien de téléchargement renverrait sur l'export pdf généré ou non à la volée, selon la méthode de stockage en bdd.
Citer : Posté le 18/03/2016 19:57 | #
Il faudra continuer cette discussion sur des topics plus appropriés, c'est un aspect non négligeable de la v5, qui gagnera à développer les tutos plus que la v4.
Sinon, j'ai plusieurs propositions de tutos pour quand j'aurai du temps, dites-moi en toute honnêteté si vous les estimez utiles ou intéressants, ou pas du tout, et lesquels vous voudriez voir arriver en priorité :
Citer : Posté le 18/03/2016 20:05 | #
Dans l'ordre, je dirais :
– Algo de tri (appliqués aux matrices, genre tri des lignes selon une colonne)
– Union-find
– Graphes
– Arbres / tas
– Equa diff
– Algos classiques
– Résolution d'équations
Citer : Posté le 18/03/2016 20:05 | #
résolution numérique d'équations différentielles (méthodes d'Euler, Verlet, Runge-Kutta etc)
utilisations avancées des graphes (plus court chemin, arbre couvrant minimal, composantes connexes, etc)
implémentation d'une structure d'union-find
arbres / tas
Citer : Posté le 19/03/2016 12:28 | #
Je serais tenté de mettre ça comme ça (ordonnés par importance) :
→ résolution numérique d'équations différentielles (méthodes d'Euler, Verlet, Runge-Kutta etc) (et la méthode de Heun d'ailleurs ?)
→ utilisations avancées des graphes (plus court chemin, arbre couvrant minimal, composantes connexes, etc)
→ implémentation d'une structure d'union-find
→ arbres / tas
Pour le reste, les algos de tri (les intéressants étant essentiellement le shell, le quick et le merge je pense) et le pivot (j'imagine tu pensais à ça) sont pour moi des algos classiques donc je mettrais tout ensemble.
Tiens, je me rends compte que j'ai fait le même classement que Ninestars.
Citer : Posté le 19/03/2016 13:54 | #
(et la méthode de Heun d'ailleurs ?)
C'est un cas particulier de la méthode de Runge-Kutta d'ordre 2.
Pour le reste, les algos de tri (les intéressants étant essentiellement le shell, le quick et le merge je pense) et le pivot (j'imagine tu pensais à ça) sont pour moi des algos classiques donc je mettrais tout ensemble.
Hmm... je pensais leur faire un tuto juste pour eux, même si c'est vrai qu'ils comptent parmi les algos classiques.
Il y a pas mal à traiter :
Algo de tri (appliqués aux matrices, genre tri des lignes selon une colonne)
Je peux faire un paragraphe là-dessus mais pour présenter les différents algos je me bornerai à des List.
Citer : Posté le 19/03/2016 14:13 | #
Je ne pense pas qu'une liste exhaustive soit utile. Sur les quadratiques, un seul algo (type bulles) sera je pense intéressant, de toute façon on ne s'en sert presque jamais. Pour les linéarithmiques, pivot et fusion semblent les plus classiques, après pas la peine de tous les citer
Citer : Posté le 19/03/2016 14:20 | #
Je ne pense pas qu'une liste exhaustive soit utile.
Certes, et j'en suis encore loin
J'ai mis les grands classiques qu'il faut connaître pour sa culture informatique, après je verrai quand je ferai le tuto si je les mets ou non.
Le tri par paquets est cool aussi
Il est un peu plus chaud en Basic, mais ça peut être sympa de le mettre, en avertissant le lecteur.
Pour les linéarithmiques, pivot et fusion semblent les plus classiques, après pas la peine de tous les citer
Oui, le tri par tas est souvent un peu moins efficace, il pourra servir comme exemple dans un tuto sur les arbres/tas.
Citer : Posté le 20/03/2016 18:38 | #
En soit un tuto sur les tris n'a aucun intérêt si il ne permet pas de pousser un peu plus loin les possibilités du Basic. Je veux dire par là que ça sert pas à grand chose de dire comment trier une liste vu que y'a déjà la fonction associée. À l'inverse, c'est intéressant de pouvoir trier une matrices d'armes par prix, par niveau ou par puissance, selon ce que l'on veut.
Je prend ça en exemple rapidement hein.
Citer : Posté le 21/03/2016 20:17 | #
En soit un tuto sur les tris n'a aucun intérêt si il ne permet pas de pousser un peu plus loin les possibilités du Basic. Je veux dire par là que ça sert pas à grand chose de dire comment trier une liste vu que y'a déjà la fonction associée. À l'inverse, c'est intéressant de pouvoir trier une matrices d'armes par prix, par niveau ou par puissance, selon ce que l'on veut.
Pas faux. Je peux aussi imaginer de trier de manières dont la calculatrice est incapable, comme trier des complexes selon leur partie imaginaire, ou autre.
Après pour moi l'intérêt est plus algorithmique qu'utilitaire.
Citer : Posté le 21/03/2016 20:38 | #
Autant sur les graphes l'algorithimie doit être prédominante, voire seule, autant sur les tris on trouve ce genre de pages assez facilement : http://lwh.free.fr/pages/algo/tri/tri.htm