Projet:ENS Rennes algorithmique 2019

Les élèves du département mathématiques de l'ENS Rennes s'unissent pour améliorer certains articles Wikipédia relatifs à l'algorithmique.

Calendrier

3 ou 10 septembre : présentation du projet
jeudi 20 septembre : constitution des groupes et inscription
jeudi 27 septembre : séance Wikipédia (avoir choisi la/les pages à modifier + avoir réfléchi aux modifications à apporter en amont de la séance)
27 novembre : écrire ici ce que vous avez déjà fait (hors Wikipédia ou si vous avez programmé quelque chose, ou si vous avez lu quelque chose, ou si vous avez quelques dans votre brouillon Wikipédia) ; écrire ici ce que vous comptez faire jusqu'à la fin du projet
20 décembre : fin du projet

Attendu du projet

En amont : il faut lire une ou des sources (livres, articles de recherche). Voici quelques idées de tâches à réaliser :

Écrire des explications d'un ou de plusieurs algorithmes, et/ou un pseudo-code.
Écrire une démonstration pertinente.
Citer une ou des sources aux pages (livres, articles de recherche). Évitez les pages de cours pour les sources, sauf cas particulier.
Dessiner une ou des illustrations.
Implémenter un algorithme pour générer automatiquement un texte qui explique un exemple ; ou qui génère une illustration.

Ressources

Pour Wikipédia

Aide:Premiers pas

Aide pour LaTeX

Aide:Formules TeX

Pour créer des illustrations

Transformer des svg en png, par exemple, convert *.svg *.png

Transformer des png en gif animé

for number in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

do

convert draw$number.svg draw$number.png

done

convert \

-delay 50 \

$(for i in $(seq 1 2 23); do echo draw${i}.png; done) \

-loop 0 \

graham_animation.gif

https://gitlab.com/francois.schwarzentruber/graham/ : exemple d'un programme qui génère des images SVG

Idées de projets

Améliorer des pages autour de la factorisation des polynômes
Améliorer des pages autour du problème des mariages stables
Traduire https://en.wikipedia.org/wiki/Cartesian_tree
https://en.wikipedia.org/wiki/Scapegoat_tree
Améliorer les pages autour des tas (tas de Fibonacci, tas binomiaux etc.)
Traduire https://en.wikipedia.org/wiki/Heap%27s_algorithm ou d'autres algorithmes pour générer des permutations
K-moyennes : étudier l'algorithme d'approximation ?
Améliorer Méthode des k plus proches voisins
Algorithmes autour des triangulations (Triangulation de Delaunay, Graphe de Gabriel, etc.)
Rédiger des démonstrations de quelques résultats de complexité de Tri de Shell
Traduire la page https://en.wikipedia.org/wiki/Integer_sorting (tri de nombres entiers)
Traduire la page Algorithme d'Edmonds pour les couplages
Un algorithme de votre choix, qui vous plait, de la page https://en.wikipedia.org/wiki/List_of_algorithms mais qui n'existe pas ou peu en français
Traduire https://en.wikipedia.org/wiki/Cheney%27s_algorithm
Traduire https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
Traduire https://en.wikipedia.org/wiki/Lehmer%27s_GCD_algorithm (bref, aller plus loin que l'algorithme d'Euclide !)
Améliorer les pages sur les algorithmes de multiplication de nombres comme Algorithme Toom-Cook etc.

Pages à améliorer

Inscrivez la pages à améliorer et les noms d'utilisateur (pour ceux qui veulent rester anonymes, vous pouvez aussi utiliser un pseudonyme, par contre, je vous encourage fortement à créer un compte) ici selon le modèle qui suit.

<sujet>