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

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.

Coloration de graphe

• Sophie Jaffard
• Thomas Bouchet

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 ?

Tas (informatique)

• Antoine Dequay
  • Modifications à publier (encore sur brouillon papier, ou en cours de rédaction sur ordinateur) :
    • Modifications à apporter à la définition (rappel sur le stockage d'un tas dans un tableau et ajout d'un peu de rigueur).
    • Travail dans la section "Primitives" : Implémentation en python des différentes opérations sur les tas.
    • Ajout de la section "Références", liées au texte déjà écrit sur le site.

• 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".
    • 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".
    • Rédaction d'un paragraphe et création d'un tableau comparatif pour la future section "Comparaison des complexités".
• LeeChiwee
  • Modifications à publier (encore sur brouillon, ou en cours de rédaction sur ordinateur) :
    • Remodelage du site : Création de sous sections pour la section "Primitives", et des sections "Comparaison des complexités", "Applications" et "Implémentation".
    • Rédaction des paragraphes correspondants aux deux dernières sections.
    • Ajout de références concernant les sections modifiées ci-dessus.

Problème des mariages stables

• tmede876
  • Modifications apportées :
    • 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}$.

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

Arbre binaire de recherche

• Qlarde (d · c · b)
• Leodaures (d · c · b)
• MajSup (d · c · b)

Tri de Shell

• MKNono
• superpinguoin974
• Issa-Dabo

arbre B

• 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 de la section "implémentation"
    • Ajout de la section "En pratique" pour clarifier les notations et les définitions dans le cas des arbres B d'ordre L
• Vmalot
  • Modifications publiées :
    • Ajout en LaTeX de la démonstration pour la majoration de la hauteur dans le pire des cas

Expression régulière

• Wolf5198
• Tiramiphage
• VecteurHM

Algorithme de Las Vegas

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

R-arbre

• TheSpaceSheep
• Eraz97

Idées de pages à modifier, mais non attribuées à des étudiants

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.