UP | HOME

Projet : partition d'entiers avec R

Table des matières

Principe du projet

Le but de ce projet est de participer à une compétition par équipes autour de la résolution du problème de partition. Le projet s'organise autour des trois axes suivants :

  1. Algorithmique : étude du problème de partition et de ses algorithmes de résolution (notes de cours).
  2. Programmation : implémentation correcte d'un ou plusieurs de ses algorithmes.
  3. Gestion de projet : introduction d'une méthode rigoureuse et d'outils modernes (package partition).

La note de projet comptera pour 60% de la note finale déterminée par les résultats de la compétition et une soutenance orale.

Déroulement du projet

Le projet comporte quatres jalons qui sont notés sur un total 31 points plus des points bonus.

Inscription

DEADLINE: <2016-10-07 ven. 23:55>

Une équipe est composée d'au plus 3 étudiants. Le formulaire d'inscription est disponible ici.

Qualifications (Version 0)

DEADLINE: <2016-11-07 lun. 23:55>

Les têtes de série de la compétition seront déterminées à l'issue des qualifications.

Tâche Pts Code
Conforme aux spécifications .5 S0
Compilation et chargement réussi du code .5 C0
Succès aux tests préliminaires 1 T0
Victoire d'un match-test contre un algorithme glouton 2 V0
TOTAL 4  

Compétition de solveurs (Version 1)

DEADLINE: <2016-12-05 lun. 12:00> SCHEDULED: <2016-12-06 mar. 15:15>

Les équipes sont engagées dans à tournoi à double élimination. Les points sont attribués selon le classement final dans le tournoi.

Le vainqueur d'un match est le premier joueur avec deux courses victorieuses. Une course correspond à un appel de la fonction PartRace du package partition développé pour ce projet. Le résultat d'une course est un classement des participants où les égalités sont possibles.

Tâche Pts Code
Est conforme, compile, et passe les tests 1 SCT
Victoire d'un match-test contre un algorithme glouton 1 V1
Victoire d'un match-test contre un meilleur glouton 2 V2
Participation au tournoi 1 PT
Classement du tournoi 12 CT
Victoire d'un match de gala contre les profs (bonus) 3 VG
TOTAL 17+3  
  • Règlement d'un match
    • Un bug pendant une course est éliminatoire, le joueur perd le match.
    • Les égalités ne sont pas comptabilisées.
    • Les joueurs choisissent à tour de rôle le nouveau jeu d'instances utilisé pour la course. Le gagnant d'un tirage au sort commence.

Soutenance orale

SCHEDULED: <2016-12-06 mar. 13:05>

Les équipes doivent être présentes au complet au début du jury. La soutenance orale en français dure 8 minutes, suivie d'une séance de questions (4 minutes).

Tâche Pts Code
Évaluation des professeurs 7 EP
Évaluation des participants 3 EE
Bonus anglais 1 BA
Bonus nouveau 1 BN
TOTAL 10+2  
  • Planning des soutenances
    Horaire Amphi            
    9h00-10h30 Phy 1 LEquipe21 SKV TeamRocket ElPsyCongroo ChequeEnBois LesLegendR
    11h00-12h30 Phy 1 uRhs BDM LesReds FioRoxPOWER TeamSheytan GTA
    13h00-14h30 M LaTripletteGagnante LionsRT ZizouTeam LesNinfomanes LesNouveaux ProjectSmiley

Bonus et Malus

Des bonus et des malus peuvent être attribués pendant le projet. Ils s'appliquent à la note finale sur 20.

Tâche Code
Bonus B
Malus M

Rendu du projet   KEY

Les versions 0 et 1 du projet seront rendues dans une boîte de dépôt JALON sous la forme d'une archive ZIP contenant :

  • Un fichier texte README comprenant le nom de l'équipe (TeamName), ses membres (noms et numéros d'étudiants) et quelques informations jugées essentielles.
  • La présentation (au plus 12 diapositives) au format PDF nommé TeamName.pdf (version 1 uniquement).
  • Un fichier de code source nommé TeamName.R respectant les spécifications.

Attention, une erreur lors de l'exécution de la commande source('TeamName.R') entraîne une disqualification.

Ces instructions doivent impérativement être respectées.

Spécifications   KEY

Une équipe TeamName fournit un fichier TeamName.R contenant une fonction TeamName(sizes) qui prend en argument un vecteur d'entiers positifs. La fonction résout la version optimisation du problème de partition et renvoie un vecteur logique d'indices représentant une partition (la meilleure possible). Ce vecteur logique d'indices doit avoir la même longueur que le vecteur d'entiers en entrée. Autrement, le résultat sera considéré invalide.

Le fichier TeamName.R ne doit contenir qu'une seule fonction et aucune autre instruction. Cependant, Des fonctions auxiliaires peuvent être définies dans la fonction principale. Par ailleurs, la fonction ne doit rien afficher (print, cat, …).

Attention, il est primordial que votre solveur puisse participer aux matches/courses. Une course correspond à un appel de la fonction PartRace du package partition développé pour ce projet. La fonction PartRace appelle la fonction race du package race qui exécute une course pour la sélection empirique du meilleur. Il existe des notes de cours à propos du package race. Les équipes peuvent contribuer au développement du package partition en proposant des corrections de bug, des améliorations ou de nouvelles fonctions.

Vous ne devez pas seulement écrire du code, vous devez également le COMMENTER, faire attention aux NOMS des fonctions et des variables que vous utilisez (choisissez des noms EXPLICITES) La qualité et la lisibilité du code seront prises en compte.
Dans ce projet, nous adopterons les recommandations de google pour coder en R.

Attention, Une équipe doit demander une autorisation pour utiliser un package ou une extension.

Évaluation du projet

Equipe etu1 etu2 etu3 Note/20 S0 C0 T0 V0 SCT V1 V2 PT CT VG EP EE BN B M
BDM by506127 dg502433 mm607262 14 0.5 0.5 0.5 0.5 1 1 0 1 9   5 1.5 1    
ChequeEnBois cj503937 as412741 rm505280 10.5 0.25 0 0.5 0 0.5 0.5 0 1 6 0.5 4.5 2.5      
ElPsyCongroo dt411921 gl504436 rt500892 19.5 0.5 0.25 0.5 0 0.25 1 1.5 1 12 3 7 3      
FioRoxPOWER pf402134 jr506436 NA 11 0.25 0.25 0.5 0 0 0 0 1 7   6.5 1.5      
GTA ct502678 ng407922 gl505046 0                              
LaTripletteGagnante ma501325 er402540 tj510287 4.5 0.25 0.5 0.5 1 0.25 0.25 0 0     3.5 0.5      
LEquipe21 mn407471 lr513114 aj612792 16.5 0.5 0.5 0.5 1 1 1 1 1 10 0.5 6 1.5 1    
LesLegendR ga405946 pa100963 sm308786 2.5 0.25 0.25 0 0 1 0 0 0     1.5 0.5      
LesNinfomanes hc506416 dl500593 ln501446 6.5 0.25 0.25 0.5 0 0.25 0 0 0     6.5 2.5      
LesNouveaux ml610140 nm605493 bm608749 9.5 0.25 0.5 0 0 0.25 0.25 0 1 8   3.5 3 1   -2
LesReds ra501649 eg406896 bh506742 14.5 0.5 0.5 0.5 0 0.5 0.25 0 1 8   6 3 1 1  
LionsRT fr507253 bt506698 cs610000 14.5 0.25 0.5 0.5 0.5 1 0 0 1 11 1 3.5 2 1    
ProjectSmiley aa504011 bt503254 am501829 4.5               1 6   4 1     -3
SKV av502395 vs502662 bk506202 16.5 0.25 0.5 0.5 1 0.5 1 1 1 11 1 5 2.5      
TeamRocket cm506616 nm609672 va506304 9 0.25 0.5 0.5 0.5 0.5 0 0 1 7   2 1 1    
TeamSheytan mo608769 bs610691 hk608773 2.5 0.25 0.5 0 0 0.25 0.25 0 0     3 2.5     -2
uRhs lp404690 dl503057 gy507016 18 0.25 0.5 0.5 1 1 1 1.5 1 9 3 6.5 1.5   0.5  
ZizouTeam da400662 cl401373 rz308280 10.5 0.25 0.5 0.5 0 0.25 0.25 0 1 7 0.5 4.5 1.5      

Note Finale (/20)

Le calcul de votre note finale sur 20 est open source !

## teams est le tableau détaillé d'évaluation
## On calcule la note sur 20 sans les bonus
exclude <- colnames(teams) %in% c("Equipe", "etu1", "etu2", "etu3", "Note.20", "B", "M")
x <- teams[,!exclude]
x [ is.na(x) ] <- 0
x <- rowSums(x)
## L'évaluation est sur 31 points
x <- round((40 * x)/31, 0)/2
## On ajoute les bonus/malus
y <- teams[,c("B", "M")]
y [ is.na(y) ] <- 0
x <- x + rowSums(y)
## On affiche les résultats
y <- order(x, decreasing = TRUE)
df <- data.frame( Equipe = teams$Equipe[y], Note = x[y])

Quelques Conseils en vrac

Vérification et évaluation de votre solveur

Il est également essentiel de TESTER chacun des programmes que vous faites, de développer des tests pour le vérifier. Vous devez faire part d'un esprit critique. Faire des tests à l'intérieur d'un programme peut également vous aider à trouver vous-même votre erreur lorsqu'un programme ne fonctionne pas: pensez-y ! Ici, nous cherchons vérifier la correction de votre algorithme et évaluer ses performances.

  1. Un générateur aléatoire d'instances ainsi qu'un générateur d'instances difficiles sont fournis.
  2. Un jeu d'instances résolues optimalement est fourni pour évaluer la qualité de vos solutions.
  3. Un algorithme résolvant optimalement les petites instances est fourni.
  4. Il existe un algorithme glouton pour résoudre optimalement les instances constituées des nombres de 1 à n multipliés par une constante. Vous pouvez ainsi générer des instances faciles dont la taille et la précision varient.

Travailler sur un vecteur trié d'entiers

La plupart des algorithmes offriront de meilleures performances en triant les entiers.

sizes <- c(13, 11, 8, 20, 20, 11, 16, 17, 4, 13)
perm <- order(sizes, decreasing = TRUE)
sortedSizes <- sizes[perm]
print(perm)
print(sortedSizes)
[1]  4  5  8  7  1 10  2  6  3  9
[1] 20 20 17 16 13 13 11 11  8  4

Ces algorithmes calculent donc une partition du vecteur trié (une permutation du vecteur original).

sortedPart <- rep(c(TRUE,FALSE), each = 5)
print(sortedPart)
print(sortedSizes[sortedPart])
[1]  TRUE  TRUE  TRUE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE
[1] 20 20 17 16 13

Mais, les spécifications exigent de renvoyer une partition du vecteur non trié. Il faut inverser la permutation triant le vecteur.

part <- logical(10)
part[perm] <- sortedPart
print(part)
print(sizes[part])
[1]  TRUE FALSE FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE
[1] 13 20 20 16 17

Soutenance orale

Lors de cette soutenance, vous devez présenter le travail effectué.

Voici quelques conseils.

  • La soutenance sert à convaincre le jury de la qualité de votre travail.
  • Ne prenez la parole que lorsqu'on vous la donne. Attendez le signal du jury pour commencer, dites bonjour, présentez vous.
  • Répétez votre présentation avant, ne dépassez pas le timing. Il vaut mieux faire moins que trop.
  • Chaque diapositive ne doit contenir qu'une information importante. Pour chaque diapositive, demandez vous quel est le message que vous voulez faire passer. Si vous n'en trouvez pas, la diapositive ne sert à rien.
  • Numérotez vos transparents sous la forme n/total pour que le jury sache où vous en êtes de votre présentation.
  • Pendant la séance de questions, ne coupez pas la parole au jury ou à vos camarades. Vos réponses doivent être concises.

Created: 2017-08-02 mer. 12:08