Projet:ENS Rennes algorithmique 2018
Les élèves du département mathématiques de l'ENS Rennes s'unissent pour améliorer certains articles wikipedia relatifs à l'algorithmique.
Calendrier
- 11 septembre : présentation du projet
- jeudi 20 septembre : constitution des groupes et inscription
- jeudi 27 septembre : séance wikipedia (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 wikipedia ou si vous avez programmé quelque chose, ou si vous avez lu quelque chose, ou si vous avez quelques dans votre brouillon wikipedia) ; écrire ici ce que vous comptez faire jusqu'à la fin du projet
- 17 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). Evitez les pages de cours pour les sources, sauf cas particulier.
- Dessiner un 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 wikipedia
Aide pour LaTEX
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
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.
- Sophie Jaffard
- Thomas Bouchet
- Modifications publiées : algorithme glouton, de 2-coloriage, de Wigderson, leurs corrections, et des GIF pour illustrer l'algorithme de Wigderson.
Suggestions
- pour 2-coloration, parler de parcours en largeur + une source (Cormen ?!).
- Pour l'algo de Wigderson, quid de rajouter, en plus de la source du sujet de concours, un article, un autre livre qui en parle ? Il faut citer la source primaire https://dl.acm.org/citation.cfm?id=2158
- Pour l'algo de Wigderson, il manque un peu de contexte. Est-il utilisé en pratique ? Pour quelles applications ? Est-ce que ça suffit pour ces applications d'avoir une coloration avec comme seule spécification "\sqrt{n} couleurs au plus" ?
- Quid de créer un article wikipedia dédié à l'algo de Wigderson ?
- L'algo de Wigderson a été améliorée ici https://dl.acm.org/citation.cfm?doid=176584.176586
- Antoine Dequay
- Modifications publiées :
- Modifications à apporter à la définition (rappel sur le stockage d'un tas dans un tableau et ajout d'un peu de rigueur). (Terminé)
- Remodelage du site : Création de sous sections pour la section "Primitives". (Terminé)
- Travail dans la section "Primitives" : Implémentation en Pseudo-code et en Python des opérations principales sur les tas. (Terminé)
- Ajout de la section "Références", liées au texte déjà écrit sur le site. (3 références pour l'instant)
- Modifications publiées :
- Michaël Mabelle
- Modifications à publier (encore en cours d'écriture sur ordinateur) :
- Création d'un gif animé qui construit un arbre, à insérer dans la sous section "Construction" de la section "Primitives". (Terminé)
- Création d'un gif animé qui supprime un élément d'un arbre, à insérer dans la sous section "Suppression de la section "Primitives". (Terminé)
- Modifications à publier (encore en cours d'écriture sur ordinateur) :
- LeeChiwee
- Modifications à publier (encore sur brouillon, ou en cours de rédaction sur ordinateur) :
- Remodelage du site : Création de sections "Comparaison des complexités", "Applications" et "Implémentation".
- Rédaction des paragraphes correspondants aux deux dernières sections. (Terminé)
- Ajout de références concernant les sections modifiées ci-dessus.
- Modifications à publier (encore sur brouillon, ou en cours de rédaction sur ordinateur) :
Suggestions
Je pense que le texte introductif est trop long. Il mentionne des détails d'implémentation (représentation de l'arbre dans un tableau) qui ne sont pas essentiels dans l'introduction. Peut-être, on peut mentionner le tri par tas dans l'introduction ? C'est modifié en ce sens !
Pour le code source python, pourquoi pas. Mais je pense qu'un pseudo-code est plus lisible par tous et aussi on ne prend pas partie pour un langage particulier. Plutôt que de perdre les programmes python, j'ai mis les deux..
- tmede876
- Modifications apportées :
- Modification de l'organisation de la page web.
- Ajout des lignes "Entrée", "Sortie" et de la dernière ligne dans le pseudo-code.
- Ecriture des démonstrations formelles dans les sous-sections Tout le monde finit par être en couple et Les mariages sont stables.
- Ecriture de la sous-section Le nombre d’itérations de la boucle de l’algorithme est d’au plus .
- Ajout des sous-sections Chaque homme est engagé avec sa partenaire préférée et Chaque femme est engagée avec son partenaire le moins aimé.
- Ajout de quelques définitions afin de rendre plus rigoureuses les démonstrations.
- Ajout de référence pour les démonstrations.
- Ajout d'un exemple d'implémentation de l'algorithme de Gale-Shapley en langage Java, avec description et explication de cet exemple.
- Modifications apportées :
Suggestions
- Ne pas oublier les ordres de préférences dans l'entrée de l'algorithme. Pour les démonstrations, vous pouvez citer le livre de Kleinberg et Tardos (c'est le premier problème qu'ils traitent dans leur livre d'algorithmique).
- Pour la section implémentation, normalement, on ne met pas de code source sur wikipedia (considéré comme non encyclopédique, pourquoi Java ? etc.). Je propose de laisser le code source pour l'instant et de le présenter comme une implémentation en O(n^2). Aussi, je pense qu'il faille mettre ce point dans une autre section car ça n'a rien à voir avec les mentions des librairies Python, etc. qui elles sont vraiment de nature encyclopédique, c'est-à-dire des librairies reconnues et établies dans l'écosystème Python etc.
- Modifications prévues :
- ajout de l'algorithme de suppression (Leoens)
- illustrations (Leoens)
- liens vers les pages plus spécifiques (qui manquaient notoirement ...)
- algorithme de tri explicité
- applications (files d'attente)
- algorithme de verification
- possibilité d'ajout de sections portant sur les types d'arbres décrits dans les autres définitions et description des propriétés de ces types d'arbres binaires
- Qlarde (d · c · b)
- Modifications publiées
- Ajout de l'algorithme de recherche d'un élément
- Ajout de l'algorithme insérer un élément
- Explication de la procédure d'ajout à la racine
- Ajout de la section de présentation de l'ABR autres définitions
- Modifications publiées
- Leodaures (d · c · b)
- MajSup (d · c · b)
Prévu, source et mise en forme
- MKNono
- superpinguoin974
- Issa-Dabo
Modifications effectuées :
Ajout du gif animé du tri de Shell et du tableau de complexité de la page anglaise.
Modifications à venir :
Ajout d'un pseudo-code ou code python.
Suggestion
Plutôt un pseudo-code non ? Comme cela, on ne favorise pas un langage particulier.
- Twentycents
- Modifications publiées :
- Image du B-arbre reprise depuis le wikipédia anglais, et ajout d'un en-tête l'accompagnant.
- Ajout des complexités pour les 3 opérations (et ajout d'une 3e remarque sur l'avantage en terme de complexité des B-arbres par rapport aux arbres classiques)
- Modifications publiées :
- nathanaelwiki
- Modifications publiées :
- Ajout d'un gif présentant un exemple d'insertion dans un B arbre
- Ajout de la section "En pratique" pour clarifier les notations et les définitions dans le cas des arbres B d'ordre L
- Ajout prévu : une implémentation d'un B arbre avec insertion et suppression en langage python
- Modifications publiées :
- Vmalot
- Modifications publiées :
- Ajout en LaTeX de la démonstration pour la majoration de la hauteur dans le pire des cas
- Ajout de la section "implémentation"
- Modifications publiées :
- Wolf5198
- Tiramiphage
- VecteurHM
A faire :
- Ajouter et illustrer les algorithmes de Thompson, Glushkov, McNaughton-Yamada.
Référence utilisée :
- Elements de théorie des automates, Jacques Sakarovitch
Modifications publiées:
- ajout d'une partie "exemple" dans la page de l'algorithme de Thompson
- ChristLangrenez
Modifications apportées :
- Modification de la définition
- Ajout de l'exemple du tri rapide randomisé, pseudo-code et mise en place de deux exemples avec des gifs
- écriture d'un code python
Modifcations ultérieures :
- Lecture de l'article de Michel Luby (Optimal Speedup of Las Vegas) et ajout sur la page
Suggestions
Expliquer mieux (et avec une source à un livre et/ou un article de vulgarisation) pourquoi l'exemple du tri rapide est pertinent. Votre ajout est bien : je pensais plutôt pertinent dans l'article "Algorithme de Las Vegas". Le tri rapide est l'exemple donné dans le livre Computers Ltd: What They REALLY Can't Do de David Harel (p. 130).
- TheSpaceSheep
- Eraz97
Idées de pages à modifier, mais non attribuées à des étudiants
Structures de données élémentaires (liste chaînée, etc.)
D'autres idées de pages sont les bienvenues.