ALGO2: projet.
Présentation d'un algorithme ou d'une structure de données non vu(e) en cours

Planning ALGO2 projet 11 avril 2013

• 5 pages maximum au format pdf pour le rapport à rendre le 9 avril 12h. Le rapport contient au moins la présentation du problème et un point particulier que vous souhaitez développer. Le nom de fichier du rapport sera sous la forme nom1_nom2_nom3_nom4_rapport.pdf
• Présentation au format pdf à envoyer par mail à Arnaud Jobin et François Schwarzentruber au plus tard 11 avril 9h. Le nom de fichier de la présentation sera sous la forme nom1_nom2_nom3_nom4_presentation.pdf
• Soutenance : 20 minutes (strict !) de présentation + 5 minutes de questions (et 5 minutes de battement)

Salle I60, 10h15 - 12h15, 11 avril 2013

10h15
Jules Brochard, Pierre Moreau, Victor Roussanaly, Raphael Struk
Approximation d'une variante du voyageur de commerce

10h45
Nathanaël Cheriere, Mathias Fleury, Siargey Kachanovich, Amélie Royer
Utilisation de polyominos pour obtenir des diagrammes de Venn d'aire minimale

11h15
Maxime Audinot, Pierre Donat-Bouillud, Corentin Louboutin
Optimisation par essaims particulaires

11h45
Antoine Chatalic, Corentin Hardy, Lucas Seguinot, Frédéric Valet
Arbres de Steiner

Salle B02B-E108, 14h - 16h, 11 avril 2013

14h
Paul Geniet, Victor Durand, Arnaud Poinas, Benjamin Arnaud
Algorithme des k-means

14h30
Augustin Moinat, Thibault Poiret, Camille Labourie
Algorithme de Fortune (diagramme de Voronoï)

15h
Claude Stolze, Alix Trieu, Thomas Saliou, Thibauld Ehret
Algorithme d'Ukkonen (construction d'arbres suffixes)

15h30
Lucas Galton et Baptiste Tessiau
Arbre rouge et noir

Déroulement du projet

Ce projet s'effectue par par groupe de quatre. Chaque quadrinôme (ce terme est un abus de langage) doit

• Choisir un algorithme (une liste ci-dessous peut le guider) ou une structure de données.
• S'inscrire sur cette page wiki pour former les quadrinômes
• Étudier l'algorithme en utilisant la littérature et Internet.
• Préparer un exposé de 12 minutes sur l'algorithme.
• Présenter l'exposé lors d'une soutenance orale de 15 minutes. Vous aurez à votre disposition un vidéo-projecteur, et si besoin est, un PC portable. Il est également possible de faire l'exposé au tableau. Dans ce cas, l'algorithme étudié peut être donné sur un support papier à l'ensemble du public afin de gagner du temps sur la présentation.
• Il faudra rendre un rapport de 5 pages, qui présente l'algorithme et des idées générales (contexte, intérêt, correction, terminaison, complexité, etc.). Vous détaillez ensuite un point (correction, terminaison, complexité) que vous jugez important.
• La soutenance est durant la dernière séance de TD.

Contenu technique

Vous devez identifier et présenter clairement les éléments suivants :

• Le contexte applicatif (s'il y a)
• Le problème algorithmique
• L'algorithme qui résout ce problème
• Les grands principes utilisés dans cet algorithme
• Choix de structures de données
• Analyse de complexité
• Vos sources d'informations.

Quelques conseils

• Avant de choisir définitivement un algorithme trouvez-le sur le web pour évaluer sa difficulté et son intérêt.
• Après avoir compris et étudié l'algorithme, prenez votre temps pour préparer la présentation.
• Soyez très pédagogiques. Quelqu'un qui ne connaît pas l'algorithme doit le comprendre en suivant votre exposé.
• Soyez équitables dans la répartition du travail et de la présentation au sein de votre trinôme. Vous serez aussi évalués sur ce point.
• Il n'est pas demandé de programmer l'algorithme.
• Si vous souhaitez, vous pouvez donner dans votre exposé toute autre information pertinente : histoire du problème et de l'algorithme, applications etc. C'est conseillé si votre algorithme est facile.
• Si vous avez vraiment besoin d'un papier de recherche disponible sur un site payant d'éditeur, contactez Arnaud et François par courriel.

Liste non exhaustive de sujets possibles

A vous de choisir l'algorithme ou la structure de données que vous souhaitez présenter. Voici quelques idées de sujets que vous pouvez étudier.

Des classiques non vus en cours

1. Un des algorithme polynomiaux pour la programmation linéaire (méthode de l'élipsoide par exemple)
2. Triangulation de Delaunay, Voronoi, etc.
3. Algorithme polynomial pour tester la primalité
4. Techniques récentes sur SAT
5. Algèbre linéaire
6. Algorithme du texte (Knuth-Morris-Pratt par exemple)
7. Arbres rouges et noirs
8. Tas binomiaux
9. Treaps
10. Algorithme pour calculer un couplage maximum (algorithme d'Edmonds etc.)
11. Union-find (analyse avec la fonction d'Ackermann)
12. Algorithme de Boyer-Moore (recherche de sous-chaîne)
13. Arbre de Steiner

Autres idées

1. Sélection du k-ième élément dans un ensemble.
2. Flot maximum dans un graphe (d'autres algorithmes)
3. Routage randomisé dans un hypercube
4. Générateur pseudo-aléatoire.
5. Plannifications
6. Algorithmes récents d'approximation pour le problème du voyageur de commerce
7. Algorithmes de compression
8. D'autres algorithmes géométriques
9. Algorithmes génétiques et recherche tabou