Seuls les membres ayant 30 points peuvent parler sur le chat.

Forum Casio - Vos tutoriels et astuces


Index du Forum » Vos tutoriels et astuces » [Basic] Implémentation de quelques structures de données
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

[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


Pages : 1, 2Suivante
Ne0tuxHors ligneMembre d'honneurPoints: 3274 Défis: 261 Message

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 !
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

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
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

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 :
X=iY->List 1[1]
PxlOn Y,X
1->D
2->F
{1,-1,i,-i}->List 2 While I != F
Je pense qu'il y a 2 erreurs
X[red]+[/red]iY->List 1[1]
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
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

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).
HackcellEn ligneMembrePoints: 1140 Défis: 6 Message

Citer : Posté le 16/03/2016 09:53 | #


Tu l'as enfin sorti, merci ça va être super pratique.
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
LephenixnoirEn ligneAdministrateurPoints: 15785 Défis: 136 Message

Citer : Posté le 16/03/2016 18:06 | #


Je suis très agréablement surpris, c'est du super boulot ! Franchement il nous en faut d'autres des comme ça. C'est vraiment ce genre de tutoriels dont on a besoin pour alimenter la v5

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.
HackcellEn ligneMembrePoints: 1140 Défis: 6 Message

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.
I usually spend meow time cosplaying as a diligent student...
So it can get pretty stressful.
That's exactly why PC is such a happy place for meow to be ⭐
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

Citer : Posté le 16/03/2016 20:55 | #


Lephenixnoir a écrit :
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.


Lephenixnoir a écrit :
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.
Dark stormEn ligneMembre d'honneurPoints: 10828 Défis: 176 Message

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.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
LephenixnoirEn ligneAdministrateurPoints: 15785 Défis: 136 Message

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.
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

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é :

algorithmes de tri
quelques algos classiques (dichotomie, etc)
résolution de systèmes d'équations (avec les matrices)
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

autre ? (préciser)
Dark stormEn ligneMembre d'honneurPoints: 10828 Défis: 176 Message

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
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
NinestarsHors ligneMembrePoints: 2253 Défis: 22 Message

Citer : Posté le 18/03/2016 20:05 | #


Louloux a écrit :
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
Ces 4 là m'intéressent, les autres non.
LephenixnoirEn ligneAdministrateurPoints: 15785 Défis: 136 Message

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.
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

Citer : Posté le 19/03/2016 13:54 | #


Lephenixnoir a écrit :
(et la méthode de Heun d'ailleurs ?)

C'est un cas particulier de la méthode de Runge-Kutta d'ordre 2.

Lephenixnoir a écrit :
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 :
notions générales : stabilité, tri en place
tris faciles en O(n²) : insertion, sélection, [tri à bulles ?]
tris efficaces en O(n log n) : pivot, fusion, [tri par tas ?]
tris particuliers en O(n) : éléments dans un intervalle [|a, b|], [tri par paquets ?]


Dark storm a écrit :
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.
LephenixnoirEn ligneAdministrateurPoints: 15785 Défis: 136 Message

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 Le tri par paquets est cool aussi. Dans l'ensemble, je pense que quatre algos sont déjà pas mal (suffisamment maintenant que j'y pense pour faire un tuto à eux tous seuls).
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

Citer : Posté le 19/03/2016 14:20 | #


Lephenixnoir a écrit :
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.

Lephenixnoir a écrit :
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.

Lephenixnoir a écrit :
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.
Dark stormEn ligneMembre d'honneurPoints: 10828 Défis: 176 Message

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.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
LoulouxHors ligneAncien administrateurPoints: 7035 Défis: 61 Message

Citer : Posté le 21/03/2016 20:17 | #


Dark storm a écrit :
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.
Dark stormEn ligneMembre d'honneurPoints: 10828 Défis: 176 Message

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
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Páranÿe quetë Quendya
Pages : 1, 2Suivante

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2019 | Il y a 78 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd