Etude de compléxité?

Version imprimable

23/05/2007, 10h15
scolopendra

Etude de compléxité?

Bonjour ,

mon probleme est le suivant :

j'ai un système qui reconnais des graphes( hors de mon controle)
et un programme a moi en java qui construit ces graphes

mon probleme c'est que le système consomme bcp en mémoire et en temps pour reconnaitre ces graphes. car ya un quota mémoire qui m' est reservé pas plus que 10Mo donc il ya des gens qui me dise qu'il faut que tu fasse une etude de complexité .

ma question comment faut il procéder et s'il ya des cours qui abordent le probleme je serais reconnaissant et merci
23/05/2007, 10h22
PRomu@ld

Citation:

j'ai un système qui reconnais des graphes( hors de mon controle)

Si tu ne contrôle pas ce système, je ne vois pas ce que tu vas pouvoir changer, même avec toutes les études possibles, tu n'amélioreras rien de ce coté là.
23/05/2007, 10h38
scolopendra

non si on peut amélioré la consomation mémoire en mettant à sa disposition les infos utile a chercher :

par exemple notre systeme fait la collection des nombres alleatoire stocké dans un fichier txt (1Go) et on sais que la plupart de ces nombre sont inutiles pour notre objectif ( par exemple dans le cas des adresses ip on veux que les ip statiques) donc le probleme c'est que le system va mettre du temps a chercher element par element au lieu d'aller directement vers la bonne information. donc c'est un peu dans ce genre la mon probleme
23/05/2007, 11h00
FrancisSourd

On peut étudier soit la complexité d'un algorithme, soit la complexité d'un problème.

Apparemment, là tu n'as pas de problème (au sens de problème théorique).

L'algorithme qui est lent semble être celui de reconnaissance de graphe. C'est donc lui qu'il faudrait étudier... mais si tu n'y as pas accès, cela ne va pas être facile!

Pour les graphes et la complexité, il y a un bon cours sur le site:
http://lapoire.developpez.com/algorithmique/graphes/

Pour ton problème, pourrais-tu nous dire
- la taille des graphes,
- le moyen de transférer le graphe du générateur au lecteur (fichier texte?)
- le codage du graphe lors de ce transfert (ce codage est-il totalement imposé)
23/05/2007, 11h04
FrancisSourd

Citation:

Envoyé par scolopendra

non si on peut amélioré la consomation mémoire en mettant à sa disposition les infos utile a chercher :

par exemple notre systeme fait la collection des nombres alleatoire stocké dans un fichier txt (1Go) et on sais que la plupart de ces nombre sont inutiles pour notre objectif ( par exemple dans le cas des adresses ip on veux que les ip statiques) donc le probleme c'est que le system va mettre du temps a chercher element par element au lieu d'aller directement vers la bonne information. donc c'est un peu dans ce genre la mon probleme

Effectivement, il faut transmettre le graphe minimal utile au programme qui le lit. Sans connaître le problème, c'est difficile de te dire ce qu'il faut éliminer mais on peut penser à enlever les noeuds isolés, à regrouper des noeuds équivalents, etc.
23/05/2007, 11h07
scolopendra

merci pour les explications,

l'architecture est la suivante :

flux ---> mise en forme ---->analyse et fltrage ---> reconnaissance

pour la taille des graphes est alléatoire cela dépend du flux d'entrée.

c'est un projet je travail au niveaux de l'analyse et le filtrage des données(graphes) donc il ya des API spécial pour la construction
et la concatenation des graphes que j'utilse directement.

Citation:

le moyen de transférer le graphe du générateur au lecteur (fichier texte?)
- le codage du graphe lors de ce transfert (ce codage est-il totalement imposé)

dans l API il ya un broadcaster qui transfertet pour le codage il'ya des classes spécifiques