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

→ **MyCalcs** profile · by **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 !

→ **MyCalcs** profile · by **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.

→ **MyCalcs** profile · by **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)

→ **MyCalcs** profile · by **noelnadal** » 18 Mar 2016, 23:56

Algorithmique de texte ? Compression de données ? Programmation dynamique ?

→ **MyCalcs** profile · by **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 ?

→ **MyCalcs** profile · by **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 !

→ **MyCalcs** profile · by **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é.