π
<-
Chat plein-écran
[^]

Tuto sur l'implémentation de piles, files, graphes en Basic

Nouveautés, projets, mises à jour.

Tuto sur l'implémentation de piles, files, graphes en Basic

Message non lude louloux » 14 Mar 2016, 22:37

Salut à tous !

J'ai pensé plusieurs fois à un tutoriel présentant certaines structures de données pratiques, car nombreux sur Planète Casio et TI Planet 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).

Si cela vous intéresse, vous pouvez retrouver ce tutoriel sur Planète Casio.

Ce qui est valable en Basic Casio l'est aussi en TI Basic, donc n'hésitez pas à lire le tutoriel même si vous n'êtes pas familier avec le Basic Casio, en vous intéressant aux méthodes, les langages Basic Casio et TI étant proches.

Merci de votre intérêt !
Ancien administrateur de Planète Casio.
Avatar de l’utilisateur
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 32.6%
 
Messages: 18
Inscription: 20 Mai 2012, 14:48
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INSA

Re: Tuto sur l'implémentation de piles, files, graphes en Ba

Message non lude Bisam » 16 Mar 2016, 23:31

C'est très bon pour les piles et les files (même s'il faudrait préciser que leur implémentation en Basic n'est pas idéale car le temps d'accès de l'empilage/dépilage ou de l'enfilage/défilage n'est pas constant comme il devrait l'être).

En revanche, je te trouve un peu succinct sur les graphes. Je pense qu'il faudrait au minimum parler des algorithmes permettant de passer d'une liste d'arêtes à la matrice d'adjacence et vice-versa, et du coup présenter aussi un algorithme pour lequel la liste des arêtes est plus intéressante que la matrice d'adjacence.
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Tuto sur l'implémentation de piles, files, graphes en Ba

Message non lude louloux » 18 Mar 2016, 22:29

Merci d'avoir pris le temps de me lire et de me faire un retour !

Je pense que tu te trompes sur le temps mis par les différentes opérations sur les piles et les files : les opérations d'empilage, dépilage, enfilage et défilage sont bien en temps constant. L'accès et la modification dans les List du Basic, qui sont en fait des tableaux, est en temps constant. J'ai chronométré ça moi-même en faisant accès/modification d'une case aux indices 10, 100 et 999 d'une List dans une boucle For, et je ne trouve aucune différence. Sur Prizm non-overclockée, il faut compter 20ms par accès à une case d'une List (ce doit être plus rapide sur G75/85/95 donc).

J'ai été en effet succinct avec les graphes... Je projette de faire, une fois mes concours passés, un tutoriel bien plus complet sur la théorie des graphes.
La représentation par liste d'arêtes est à ma connaissance très rarement utilisée en informatique (pour l'algo de Kruskal, avec une liste triée, certes), même si elle se fait assez bien avec trois List.
La représentation par listes de successeurs est, elle, très peu adaptée à la calto, il faut faire avec des matrices de complexes, chaque ligne représentant la liste des successeurs du sommet, avec a+ib pour une arête vers a de poids b, et 0 pour signaler la fin de la liste. En revanche elle peut être efficace pour certains algos, si tant est que le graphe contienne un nombre d'arêtes petit devant le carré du nombre de noeuds.

Je présenterai donc éventuellement ces autres représentations et des exemples appropriés dans mon tuto sur les graphes.


J'ai soumis sur Planète Casio plusieurs idées pour les tutos que je ferai quand j'aurai plus de temps, dites-moi lesquels vous intéresseraient le plus :
- 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)
Ancien administrateur de Planète Casio.
Avatar de l’utilisateur
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 32.6%
 
Messages: 18
Inscription: 20 Mai 2012, 14:48
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INSA

Re: Tuto sur l'implémentation de piles, files, graphes en Ba

Message non lude noelnadal » 18 Mar 2016, 23:56

Algorithmique de texte ? Compression de données ? Programmation dynamique ? :P
Avatar de l’utilisateur
noelnadalEcrivain
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Prochain niv.: 34.9%
 
Messages: 2252
Images: 0
Inscription: 10 Mar 2011, 00:00
Localisation: France, Melun (77)
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INRIA Paris
Twitter/X: nadalnoel
Facebook: noel.nadal1
GitHub: noelnadal

Re: Tuto sur l'implémentation de piles, files, graphes en Ba

Message non lude louloux » 19 Mar 2016, 14:11

Programmation dynamique : oui c'est une bonne idée. Dans pas mal de cas ça rejoint ce que je ferai sur la théorie des graphes, mais je peux faire un petit tuto sur le concept, l'utilisation des files et piles pour faire de la prog dynamique en Basic, etc. Ou alors je peux faire un tuto plus orienté C/C++, adressé à ceux qui codent des add-ins. Si ça peut leur servir à mettre des IA moins connes dans leurs jeux (parce que les add-ins sont en très grande partie des jeux hein) :)

Compression de données : sur calculatrice, ça me semble compliqué et inadapté. Paradoxalement, ce support fait partie de ceux qui demandent le plus d'économies d'espace disque, et celui qui se prête le moins à faire de la compression de données, en Basic tout du moins. En C/C++, pourquoi pas, mais j'ai peur de ne pas intéresser grand-monde, et ça devient vite compliqué.

Algorithmique du texte : intéressant, mais le Basic est bien trop limité pour faire des trucs intéressants dans ce domaine, et ses applications manquent sur calto.

Après, j'ai songé à faire des tutos de banalisation en algo, hors du domaine des caltos, donc il y aurait à faire là-dedans, pourquoi pas ?
Ancien administrateur de Planète Casio.
Avatar de l’utilisateur
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 32.6%
 
Messages: 18
Inscription: 20 Mai 2012, 14:48
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INSA

Re: Tuto sur l'implémentation de piles, files, graphes en Ba

Message non lude Bisam » 21 Mar 2016, 09:19

louloux a écrit:Je pense que tu te trompes sur le temps mis par les différentes opérations sur les piles et les files : les opérations d'empilage, dépilage, enfilage et défilage sont bien en temps constant. L'accès et la modification dans les List du Basic, qui sont en fait des tableaux, est en temps constant. J'ai chronométré ça moi-même en faisant accès/modification d'une case aux indices 10, 100 et 999 d'une List dans une boucle For, et je ne trouve aucune différence. Sur Prizm non-overclockée, il faut compter 20ms par accès à une case d'une List (ce doit être plus rapide sur G75/85/95 donc).

Tant mieux si Casio a bien fait les choses !!
Chez TI, les listes sont... des listes. Du coup, le temps d'accès est (grosso-modo) proportionnel à l'indice de la case... et comme je connais mieux les TI que les Casio, j'ai pensé (à tort, apparemment) que c'était la même chose.

Pour ce qui est des autres présentations, je pense que la récursivité et la programmation dynamique sont de très bons thèmes et permettent d'aborder beaucoup de choses.

En revanche, le calcul numérique... sur une calculette... ça ne me paraît pas servir à grand chose !
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Tuto sur l'implémentation de piles, files, graphes en Ba

Message non lude louloux » 21 Mar 2016, 19:25

Bisam a écrit:Chez TI, les listes sont... des listes. Du coup, le temps d'accès est (grosso-modo) proportionnel à l'indice de la case...

Ouch, ça ne doit pas être pratique, avec des efficacités comme ça... J'imagine qu'en plus elles ont une utilisation de tableaux plus que de listes (au sens de listes chaînées comme en Caml j'entends, pas les listes de Python qui sont en fait des tableaux dynamiques).


Bisam a écrit:En revanche, le calcul numérique... sur une calculette... ça ne me paraît pas servir à grand chose !

Effectivement, ça ne concernerait que les prépas... Même si ça a l'avantage de se faire assez efficacement sur calto. En tout cas je ne le réaliserai pas en priorité.
Ancien administrateur de Planète Casio.
Avatar de l’utilisateur
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Prochain niv.: 32.6%
 
Messages: 18
Inscription: 20 Mai 2012, 14:48
Localisation: France
Genre: Homme
Calculatrice(s):
MyCalcs profile
Classe: INSA


Retourner vers Actualités

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 8 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
2321 utilisateurs:
>2304 invités
>12 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)