π
<-
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

Unread postby 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.
User avatar
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 32.6%
 
Posts: 18
Joined: 20 May 2012, 14:48
Location: France
Gender: Male
Calculator(s):
Class: INSA

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

Unread postby 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.
User avatar
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 48.2%
 
Posts: 5468
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

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

Unread postby 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.
User avatar
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 32.6%
 
Posts: 18
Joined: 20 May 2012, 14:48
Location: France
Gender: Male
Calculator(s):
Class: INSA

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

Unread postby noelnadal » 18 Mar 2016, 23:56

Algorithmique de texte ? Compression de données ? Programmation dynamique ? :P
User avatar
noelnadalEcrivain
Niveau 17: GM (Grand Maître des calculatrices)
Niveau 17: GM (Grand Maître des calculatrices)
Level up: 15.4%
 
Posts: 2195
Images: 0
Joined: 10 Mar 2011, 00:00
Location: France, L'Haÿ-les-Roses (94)
Gender: Male
Calculator(s):
Class: lycée
Twitter: nadalnoel
Facebook: noel.nadal1

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

Unread postby 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.
User avatar
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 32.6%
 
Posts: 18
Joined: 20 May 2012, 14:48
Location: France
Gender: Male
Calculator(s):
Class: INSA

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

Unread postby Bisam » 21 Mar 2016, 09:19

louloux wrote: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 !
User avatar
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Level up: 48.2%
 
Posts: 5468
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender: Male
Calculator(s):

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

Unread postby louloux » 21 Mar 2016, 19:25

Bisam wrote: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 wrote: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.
User avatar
loulouxPartenaire
Niveau 9: IC (Compteur Infatigable)
Niveau 9: IC (Compteur Infatigable)
Level up: 32.6%
 
Posts: 18
Joined: 20 May 2012, 14:48
Location: France
Gender: Male
Calculator(s):
Class: INSA


Return to Actualités

Who is online

Users browsing this forum: No registered users and 2 guests

-
Search
-
Featured topics
L'OS 5.5 de la TI-83 Premium CE / 84 Plus CE supprime l'assembleur - la plupart des jeux et certains programme ne fonctionneront plus
Omega, le fork étendant les capacités de ta NumWorks, même en mode examen !
Découvre les nouvelles fonctionnalités en Python de l'OS 5.5 pour la 83PCE/84+C-T Python Edition
Comparaisons des meilleurs prix pour acheter sa calculatrice !
1234
-
Donations / Premium
For more contests, prizes, reviews, helping us pay the server and domains...

Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partner and ad
Notre partenaire Jarrety 
-
Stats.
425 utilisateurs:
>413 invités
>8 membres
>4 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)