Aller au contenu


Photo

Mini-projet d'algorithmique avancée

Python Programmation dynamique récursivité complexité algorithmique algorithmes gloutons

  • Veuillez vous connecter pour répondre
15 réponses à ce sujet

#1 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 270 messages
  • LocationTours (37)

Posté 25 mars 2016 - 05:19

Bonjour,

 

Ce fil de discussion est créé pour que vous puissiez échanger autour de votre mini-projet d'algorithmique avancée. Il concerne la programmation en Python de divers algorithmes permettant d'équilibrer les espaces lors de la composition d'un texte.

Vous avez plus de deux semaines pleines pour réaliser vos codes, par groupes de deux étudiants. Je vous renvoie à la première partie du sujet pour tous les détails à ce propos.

 

Bon courage à vous !



#2 Benjamin LABASTIE

Benjamin LABASTIE

    Member

  • Étudiant
  • PipPip
  • 184 messages
  • LocationCaen
  • Cursus:M.Sc.1

Posté 29 mars 2016 - 10:30

Bonjour,

 

 

"Le but est de répartir tous les mots de notre texte sur différentes lignes afin de minimiser le « coût » des espaces additionnelles."

 

Question bête peut-être, mais est-ce que l'ordre des mots importe du coup ?


                  Benjamin LABASTIE
              M.Sc.1 Campus de CAEN

UXDcvH9.png


#3 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 270 messages
  • LocationTours (37)

Posté 29 mars 2016 - 10:45

Bonjour Benjamin,

 

il n'y a pas de questions bêtes. Ceci dit quand on veut mettre en forme un texte, on souhaite quand même pouvoir le lire sans trop de difficultés. Conserver l'ordre des mots me paraît donc nécessaire.  :)



#4 Benjamin LABASTIE

Benjamin LABASTIE

    Member

  • Étudiant
  • PipPip
  • 184 messages
  • LocationCaen
  • Cursus:M.Sc.1

Posté 29 mars 2016 - 10:54

D'accord, merci de votre réponse  :)


                  Benjamin LABASTIE
              M.Sc.1 Campus de CAEN

UXDcvH9.png


#5 Antoine SIMONIN

Antoine SIMONIN

    Newbie

  • Members
  • Pip
  • 3 messages

Posté 05 avril 2016 - 10:51

Bonjour,

Je voulais savoir si quelqu'un avait compris le calcul des coûts et pourrais éventuellement me l'expliquer? 

Ma méthode de calcul est la suivante:

les cases de textes représentent une suite d'entier: 1234... et les espaces additionnels de fin de ligne prennent la valeur de la case en question ce qui donne : exmple 1 = 4+5+6+12=27 exemple 2 = 9+10+11+12 = 42
Cordialement.



#6 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 270 messages
  • LocationTours (37)

Posté 05 avril 2016 - 11:06

Bonjour Antoine,

 

Peux-tu préciser ta question car elle me semble un peu floue... De quels exemples parles-tu ?



#7 Antoine SIMONIN

Antoine SIMONIN

    Newbie

  • Members
  • Pip
  • 3 messages

Posté 05 avril 2016 - 11:10

Bonjour,

 

Je veux parler de l'exemple dans le premier paragraphe "Dans l’exemple précédent, la première répartition avait donc un coût de 28 et la seconde de 64. Ce qui confirme bien notre impression de meilleur équilibrage de la première répartition."

Je ne comprend pas vos résultats?
Merci pour votre réponse si rapide !
Cordialement .



#8 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 270 messages
  • LocationTours (37)

Posté 05 avril 2016 - 11:16

Comme mentionné dans le sujet les coûts se calculent sur toutes les lignes sauf la dernière.

 

Dans le premier exemple, il y a 3 espaces additionnelles à la fin de la première ligne et 1 à la fin de la seconde. Comme l'on additionne les cubes du nombre d'espaces additionnelles de chaque ligne, on obtient 33 + 13 = 28.

 

Dans le second exemple, il n'y a pas d'espaces additionnelles à la fin de la première ligne et 4 à la fin de la seconde. On obtient donc 03 + 43 = 64.

 

Dans les deux cas on s'était fixé un nombre de caractères maximal par ligne égal à 6.



#9 Antoine SIMONIN

Antoine SIMONIN

    Newbie

  • Members
  • Pip
  • 3 messages

Posté 05 avril 2016 - 11:21

C'est compris. Merci pour vos réponses.

Je vous souhaite une bonne journée.

Cordialement Antoine SIMONIN.



#10 Thierry MADKAUD

Thierry MADKAUD

    Newbie

  • Étudiant
  • Pip
  • 1 messages
  • Cursus:B.Sc.

Posté 06 avril 2016 - 11:55

Bonjour,

 

Le mini-projet d'algorithmique avancée peut-il se faire en C++ ?



#11 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 270 messages
  • LocationTours (37)

Posté 06 avril 2016 - 01:05

Bonjour Thierry,

 

Non, le langage choisi pour ce mini-projet est le Python.



#12 Benjamin LABASTIE

Benjamin LABASTIE

    Member

  • Étudiant
  • PipPip
  • 184 messages
  • LocationCaen
  • Cursus:M.Sc.1

Posté 07 avril 2016 - 10:15

Rebonjour,

 

 

Dans votre mail vous aviez indiqué :

 

 

 

Ce projet donnera lieu à une soutenance lors de la semaine du 11 avril 2016. Je reviendrais vers vous courant avril pour vous en expliquer le déroulement. Pour l'instant concentrez vous sur la réalisation de votre code.

 

 

Allez-vous nous préciser le contenu du support de présentation ou puis-je dès à présent commencer à le réaliser ?


                  Benjamin LABASTIE
              M.Sc.1 Campus de CAEN

UXDcvH9.png


#13 Laurent GODEFROY

Laurent GODEFROY

    Member

  • Full Professors
  • 270 messages
  • LocationTours (37)

Posté 08 avril 2016 - 09:03

Bonjour Benjamin,

 

Je viens d'envoyer un mail à ce sujet. Désolé pour le léger retard.



#14 Benjamin LABASTIE

Benjamin LABASTIE

    Member

  • Étudiant
  • PipPip
  • 184 messages
  • LocationCaen
  • Cursus:M.Sc.1

Posté 08 avril 2016 - 09:08

Je viens de voir merci beaucoup.  :)


                  Benjamin LABASTIE
              M.Sc.1 Campus de CAEN

UXDcvH9.png


#15 Jayson GALANTE

Jayson GALANTE

    Member

  • Members
  • PipPip
  • 14 messages

Posté 08 avril 2016 - 08:20

Bonsoir,

Je souhaiterais savoir s'il on doit commencer par la fin  ou par le début de la matrice des couts pour le bottom-up?

Merci d'avance



#16 Benjamin LABASTIE

Benjamin LABASTIE

    Member

  • Étudiant
  • PipPip
  • 184 messages
  • LocationCaen
  • Cursus:M.Sc.1

Posté 09 avril 2016 - 11:06

Je me permets de te répondre, car vu qu'on est en week-end tu n'auras une réponse de Monsieur GODEFROY qu'après le rendu du projet.

 

Comme indiqué dans le cours :


 

Deux approches possibles :

 

Une approche itérativeBottom Up :
On résout d’abord les sous problèmes de la plus “petite taille”.
Puis ceux de la tailled’au dessus”.
etc.
Jusqu’à ceux de la taille cherchée.

 

La matrice des coûts cost[i][j] comprenant le coût des mots i à j, on devine aisément où se trouvent les problèmes de petites tailles. 


                  Benjamin LABASTIE
              M.Sc.1 Campus de CAEN

UXDcvH9.png






Aussi étiqueté avec au moins un de ces mots-clés : Python, Programmation dynamique, récursivité, complexité algorithmique, algorithmes gloutons

0 utilisateur(s) li(sen)t ce sujet

0 membre(s), 0 invité(s), 0 utilisateur(s) anonyme(s)