Sous-séquence Maximale

PROJET SI4/IFI

Description du problème

Étant donné une séquence Q de n nombres entiers (positifs ou négatifs), la sous-séquence maximale de Q est la suite contiguë d'éléments du tableau qui a la somme maximale parmi toutes les sous-séquences possibles.

Par exemple, pour le tableau Q suivant :

La séquence de somme maximale est

Remarque : Si il existe plusieurs sous séquences de même somme maximale, on prendra la première trouvée.

Il existe de nombreux façons de résoudre ce problème dont l'algorithme de Kadane qui le résout en O(N). Nous allons considérer une solution proposée par Perumalla et al. qui propose une variante parallèle.

Algorithme parallèle

Cet algorithme utilise le calcul du préfix parallèle sous deux formes. La première est le sum-prefix qui fait la somme des éléments comme vu en cours et en TP. La deuxième est le max-prefix qui trouve l'élément maximum parmi tous les précédents. Pour l'implémenter, il suffit de partir du code sum-prefix est de remplacer la somme par un max() et les 0 du tableau initial par l'élément neutre pour l'opération max()

Maximum subsequence :

Input : Q tableau de n entiers

Output : Sous séquence maximale

1. Calculer les sum-prefix de Q et les mettre dans un tableau PSUM
2. Calculer le sum-suffix de Q et les mettre dans un tableau SSUM
3. Calculer le max-suffix de PSUM et le mettre dans SMAX
4. Calculer le max-prefix de SSUM et le mettre dans PMAX
5. pour 1 <= i <= n faire en parallel
   1. Ms[i] = PMAX[i] - SSUM[i] + Q[i]
   2. Mp[i] = SMAX[i] - PSUM[i] + Q[i]
   3. M[i] = Ms[i] + Mp[i] - Q[i]
6. Trouver la valeur maximal dans M

Exemple

L'exemple suivant est tiré de l'article donné dans les références. Il faut bien le comprendre

Implémentation

Vous devez implémenter le calcul de la sous séquence maximale dans un unique fichier nom.c en respectant les contraintes suivantes

• Compilation sans warnings avec gcc -Wall .... -fopenmp -lm
• Lecture d'un fichier bien formé passé en paramètre sur la ligne de commande
  • ./nom fichier1
• Affichage de la somme maximale et du sous tableau trouvé, séparé par des espaces et terminé par un unique \n. Avec le tableau Q précédent, on aura l'affichage
  • 28 11 10 -6 4 9

Le fichier de données sera considéré comme toujours bien formé, i.e composé d'une suite d'entiers relatifs séparés par des espaces. Le tableau sera de taille n=2^m .

Tester votre solution

Vous pouvez tester votre solution grâce au fichier python3 contenu dans le zip en bas de la page. Placez votre fichier nom.c dans le répertoire src et exécutez

~/>python3 evaluate.py 

nom;True;True;False;Error

Ici la compilation (1ère colonne) s'est bien passée. Le premier test est True, donc c'est bon. Par contre le deuxième est False, c'est à dire que le résultat produit ne correspond pas à celui attendu. Enfin le dernier est Error, ce qui signifie que le programme s'est arrêté avant de produire un résultat ou a dépassé le timeout de 5 secondes.

Rendu

Le projet sera à rendre sur Jalon au plus tard le dimanche 1er avril à 23.00, sous forme d'un fichier zip contenant

• Un fichier nom.c compilable unique avec gcc -o nom -Wall -std=c99 nom.c -lm -fopenmp
• Un fichier readme.txt indiquant quelles méthodes sont parallélisées. Par example, le format suivant convient :
  • void prefixSum(....) : parallelisée
  • void affichage(...) : non parallelisée
  • .....

Évaluation

Les points suivants seront évalués

• Compilation sans erreur et warnings
• Exécution correcte sur un ensemble de datasets
• Degrés de parallélisme (chaque méthode des 6 étapes de l'algorithme doit être parallélisée).
• Vitesse d'exécution
  • Les programmes remplissant les points précédents auront leur vitesse d'exécution évaluée
  • Les 3 plus rapides auront un bonus de +2 points

L'évaluation étant semi-automatique, un programme produisant un résultat correcte mais mal formé (espaces, retour à la ligne ...) sera considéré comme faux.

Références

• Maximum subarray problem (wikipedia)
• Parallel Algorithms For Maximum Subsequence And Maximum Subarray (1995) by Kalyan Perumalla and Narsingh Deo (lien)