Ce projet a été effectué en troisième année du CMI Informatique à l'UFR SFA Université de Poitiers dans le cadre de l'enseignement Algorithmique et programmation.
Ce projet a été développé en binôme sous Ubuntu avec GNU Emacs et le mode Tuareg.
Pour lancer le projet, il faut installer opam.
Une fois opam installé il faudra télécharger une des versions d'OCaml présent dans le dossier "code/libraries. Pour cela, lancez les commandes (sous linux) :
$ opam install 4.11.1
$ opam switch 4.11.1
$ eval $(opam env)Une fois ces commandes exéxutées vous avez la version 4.11.1 d'OCaml et vous pourez tester les programmes "code/ABR.ml" et "code/AVL.ml" en prenant soins de charger la commande :
#directory "libraries/4.11.1/";;L'exemple ci-dessus est valable pour la version 4.11.1 mais vous pouvez le répéter avec une des autres versions disponible avec le mêmes commandes an changeant juste "4.11.1" par la version que vous souhaitez.
- Types sommes et structures arborescentes
- Arbre binaire de recherche
- Arbre AVL
- Algorithme récursif sur les arbres
- Construction
- Parcours
- Ajout/suppresion
- Recherche
- Optimisation des structures et des algorithmes
- Compléxité en O(log(n)) pour les l'ajout/suppression/recherche dans un arbre AVL
- Stockage du déséquillibre dans chaque noeuds d'un arbre AVL
Nous avons obtenu la note de 19/20.
This project was carried out in the third year of the CMI Informatique at the University of Poitiers as part of the Algorithms and programming teaching programme.
This project was developed in pairs under Ubuntu with GNU Emacs and Tuareg mode.
To launch the project, opam must be installed.
Once opam is installed you will need to download one of the versions of OCaml present in the folder "code/libraries. For that, launch the commands (under linux):
$ opam install 4.11.1
$ opam switch 4.11.1
$ eval $(opam env)Once these commands are executed you have OCaml version 4.11.1 and you can test the programs "code/ABR.ml" and "code/AVL.ml" by taking care to load the command :
#directory "libraries/4.11.1/";;The above example is valid for version 4.11.1 but you can repeat it with one of the other versions available with the same commands by just changing "4.11.1" to the version you want.
- Tagged union and tree structures
- Binary search tree
- AVL tree
- Recursive algorithm on trees
- Construction
- Tree traversal
- Addition/deletion
- Search
- Optimisation of structures and algorithms
- Complexity in O(log(n)) for add/delete/search in an AVL tree
- Storage of the balance factors in each node of an AVL tree
We obtained a score of 19/20.