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[modifier | modifier le code]

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[modifier | modifier le code]

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 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[modifier | modifier le code]

Pour wikipedia[modifier | modifier le code]

Aide:Premiers pas

Aide pour LaTEX[modifier | modifier le code]

Aide:Formules TeX

Pour créer des illustrations[modifier | modifier le code]

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[modifier | modifier le code]

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.

Coloration de graphe[modifier | modifier le code]

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[modifier | modifier le code]

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

Tas (informatique)[modifier | modifier le code]

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)

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é)
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.

Suggestions[modifier | modifier le code]

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

Problème des mariages stables[modifier | modifier le code]

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 $\textstyle n^{2}$ .
  - 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.

Suggestions[modifier | modifier le code]

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.

Arbre binaire de recherche[modifier | modifier le code]

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
Leodaures (d · c · b)
MajSup (d · c · b)

Prévu, source et mise en forme

Tri de Shell[modifier | modifier le code]

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[modifier | modifier le code]

Plutôt un pseudo-code non ? Comme cela, on ne favorise pas un langage particulier. Il faut expliquer un peu le pseudo-code. Expliquer que tri_gap c'est le tri insertion sur ... (dire quoi) etc.
La figure "Tri de Shell barres de couleur de l'algorithme" est compliqué à comprendre : il faut une explication. Ou alors, la supprimer ?
Ajouter les applications mentionnées sur la page anglaise ?
Dans l'introduction, il est dit que le tri de Shell n'est pas stable. Qu'est ce que cela veut dire ? Il faut l'expliquer, je pense.

arbre B[modifier | modifier le code]

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)
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
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"

Suggestions[modifier | modifier le code]

Pas besoin d'un programme Python. Par contre, vous pouvez mettre votre code sur votre page web, et mettre une référence (j'imagine que ce code sert à créer les illustrations ?).
L'article utilise n (dans O(log n) dans la section Insertion) et N (à la fin) pour parler du nombre d'éléments dans la structure. Il faut uniformiser les notations. Attention, n est aussi utilisé dans les n-noeuds !
Qu'entendez-vous par "(en moyenne)" dans la phrase "Avec les B-arbres, la complexité en temps de l'insertion d'un élément est (en moyenne) de O(log n)." ? L'insertion n'est-elle pas en O(log N) où N est le nombre total de clefs, tout le temps ?

Expression régulière[modifier | modifier le code]

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
ajout d'une sous-partie sur la complexité en temps sur la page de l'algorithme de Thompson
Algorithme de McNaughton et Yamada : ajout d'un exemple + étude de l'importance de la numérotation des états dans les 2 exemples + pseudo-code.
construction de Glushkov: ajout de trois parties: "Complexité en temps (par étapes)" , "Preuve de terminaison (par étapes)" et "Comparaison avec l'algorithme de Thompson". (Les trois parties ont été rédigées par Wolf5198)

Suggestions[modifier | modifier le code]

Pour l'exemple sur la page de l'algorithme de Thompson, attention c'est brouillon. Certains ":" sont précédé d'un espace, d'autres non. Attention, dans ce n'est pas $c*$ mais $c^{*}$ . Quid d'un tableau qui montre les étapes ?
Attention " les automates reconnaissant les lettres "a", "b" et "c":" est une phrase vague. 1) Un automate reconnait des mots pas des lettres. C'est maladroit de confondre un mot à une lettre et un lettre dans ce contexte. 2) Le point important est qu'ils reconnaissent exactement que les mots a (resp. b, c) (un automate pourrait reconnaitre d'autres mots par ailleurs).
Dans vos textes, vous allez souvent à la ligne. Il faut rédiger des paragraphes. Aussi, évitez les phrases vagues comme "la complexité est celle du calcul d'une fermeture transitive". Du coup, c'est combien ? " déjà définis sur Wikipédia"... où ? dans la section d'avant ?
Il faut aussi des références pour les démonstrations que vous avez ajoutées.
Il faut plus rédiger. Le résultat de wikipedia doit ressembler à un texte d'une encyclopédie. J'imagine que "4- Suppression des indices en O(n)" est le titre de l'étape numéro 4 dans O(n) dans l'article construction de Glushkov. Il vaut mieux, soit retirer le titre, soit le garder mais ajouter une phrase après qui explique plus.

Algorithme de Las Vegas[modifier | modifier le code]

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[modifier | modifier le code]

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).
La section "Existence d'une stratégie optimale pour les algorithmes de Las Vegas" est pertinente. Merci. Par contre, sa rédaction peut être améliorée car là, en lisant ce paragraphe, on ne sait pas où la section veut en venir. Je propose d'éviter les citations dans le titre de la section. Wikipedia est une encyclopédie et pas un cours. N'hésitez donc pas à écrire des phrases comme "Michel Luby^[1] explique...".

R-arbre[modifier | modifier le code]

TheSpaceSheep
Eraz97

Idées de pages à modifier, mais non attribuées à des étudiants[modifier | modifier le code]

Structures de données élémentaires (liste chaînée, etc.)

Problème du sac à dos

Lempel-Ziv-Welch

D'autres idées de pages sont les bienvenues.