Plan de match

Modèle de rapport de lab: après le 24 février 2004.

Évaluation: 5 mars 2004.

Date de remise: 12 mars 2004.

Semaine du 20 au 27: faire varier le M en insérant le tri simple, les baromètres doivent s'additionner. Construire une boucle qui fait varier la variable m ( 10, 20, 100 ). Optimisation du pivot, quicksort: 1 ou 2 heures. Copie/Paste, change le pivot, ... Faire la boucle de test sur les trois nouveaux algorithmes. Point 3: Comment générer le fichier de clés de recherche? Excel!!! ou Code? Au début, faire avec 20 éléments (à bras). Décrire dans le rapport avec un petit nombre de tests. Minimum de théorie.

Semaine 27 au 5: analyse sérieuse avec les équations. Conclusions: Heuristiques et temps de calculs amortis: optimisation avec les données. Heuristiques: processus non déterministes, pas certain d'avoir la bonne réponse. Deviner selon la probabilité d'avoir la bonne réponse. Demande plus d'essais (de "je pense que"). Pas de "je suis certain". Discussion...

Séparation des tâches

Yan

• 2004/02/24: Bâtir la structure du répertoire (dans le compte à Éric)
• 2004/02/24: Création du fichier référence.txt dans le répertoire "rapport". Il permet d'ajouter nos références lorsqu'on travail.
• 2004/02/24: Copie de l'énoncé du laboratoire #2 dans le répertoire "énoncé".
• 2004/02/24: Restructuration des menus (pour les stress tests).
• Présentement j'ai un bug de perte de mémoire dans l'appel d'une fonction????

Notes

Comment peut-on améliorer les algorithmes selons les tests effectués
À faire: Trois analyses sur les algorithmes déjà fait.
Baromètre sur: comparaison, mémoire, affectation
Répondre à trois questions:
 - Optimiser quicksort et heapsort
   - Faire le quicksort (coûtQS(n))
   - Trouver un algorithme simple plus efficace lorsque le quicksort trie un nombre n de données
   - Le coûtQS deviendrait = coutQS(N-k*m) + coutTriSimple( m ) * k  // ou k = nombre de fois
   - Trouver pour quelle taille de m le quicksort est plus rapide ( coûtTriSimple = Insertion)
   - Sur 10 éléments par exemples
   - Plus rapide lorsque m est ordonnées (insertion)
  - Le faire pour le quicksort et le heapsort
 - Choix du pivot pour le quicksort
   - Faire l'analyse avec trois pivots (meilleur cas, moyen cas, pire cas) : graphique
 - Comparer RedBlack/Splay
   - Splay Tree emmene les noeuds à la racine. Illustrer la rapidité du Splay Tree en modifiant les clés de recherches.
   - Générer des fichiers de recherches avec des clés de recherche non uniformes.
   - Générer les données (ensembles non-uniformes) dans excels (intervalle de confiance)
   - Théoriquement et pratiquement