Contenu | Rechercher | Menus

Annonce

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

À propos de l'équipe du forum.

#26 Le 12/03/2016, à 16:44

claudius01

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonjour,

msg21 a écrit :

...
Bien que l'algorithme est polynomiale ( un O(n^4)) ?

Je n'ai pas été vérifier le n^4 mais déjà par avec un tri à bulles qui a une complexité moyenne en O(n²), cela signifie que si l'on double la taille du tableau à trier, on mettra quatre fois plus de temps pour le trier. Le tri à bulles s'exécute en temps polynomial et n'est pas utilisé au profit d'un tri dichotomique ;-)

Ici on, si est bien en n^4, je vous laisse évaluer le temps d’exécution qui, pour moi, est très lent bien que de la classe polynomiale...

NB: Et on n'a pas parlé encore des ressources système nécessaires...

Edit: Cf. 7.1  Complexité des algorithmes avec:

Les algorithmes usuels peuvent être classés en un certain nombre de grandes classes de complexité.

    o Les algorithmes sous-linéaires, dont la complexité est en général en O(logn). C'est le cas de la recherche d'un élément dans un ensemble ordonné fini de cardinal n.

    o Les algorithmes linéaires en complexité O(n) ou en O(nlog n) sont considérés comme rapides, comme l'évaluation de la valeur d'une expression composée de n symboles ou les algorithmes optimaux de tri.

    o Plus lents sont les algorithmes de complexité située entre O(n2) et O(n3), c'est le cas de la multiplication des matrices et du parcours dans les graphes.

    o Au delà, les algorithmes polynomiaux en O(nk) pour k > 3 sont considérés comme lents, sans parler des algorithmes exponentiels (dont la complexité est supérieure à tout polynôme en n) que l'on s'accorde à dire impraticables dès que la taille des données est supérieure à quelques dizaines d'unités.

Dernière modification par claudius01 (Le 12/03/2016, à 16:49)

Hors ligne

#27 Le 12/03/2016, à 19:49

LeoMajor

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

bonsoir,
j'ai juste modifié le print, et importé time

 cat -n /tmp/test.python 
     1  #!/usr/bin/env python3
     2  import time
     3  start = time.time()
     4  from scipy import *
     5  import numpy as np
...
    61  for k in range(0,n**2) : #ici
    62
    63          print(k, time.time() - start)

plutôt rapide au début, et ensuite de plus en plus lent

python /tmp/test.py
[[20, 0]]
(0, 0.06447696685791016)
(1, 0.0645589828491211)
(2, 0.06468486785888672)
(3, 0.0649259090423584)
(4, 0.06535005569458008)
(5, 0.06629586219787598)
(6, 0.06795597076416016)
(7, 0.07121992111206055)
(8, 0.07785797119140625)
(9, 0.0924069881439209)
(10, 0.12042593955993652)
(11, 0.17933106422424316)
(12, 0.30527591705322266)
(13, 0.6023209095001221)
(14, 1.2983930110931396)
(15, 3.2356529235839844)
(16, 9.010117053985596)
(17, 28.07929801940918)
(18, 117.16273283958435)
(19, 593.5556809902191)
(20, 2522.5827820301056)
(21, 10201.715741872787)
...

Dernière modification par LeoMajor (Le 12/03/2016, à 19:50)

Hors ligne

#28 Le 13/03/2016, à 02:46

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Du progrès jusqu'au 16

Dernière modification par msg21 (Le 16/03/2016, à 08:22)

Hors ligne

#29 Le 13/03/2016, à 09:39

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Est-il possible d'avoir une description de l'algorithme ? Que doit-il faire ?


Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#30 Le 13/03/2016, à 11:47

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Est-il possible d'avoir une description de l'algorithme ? Que doit-il faire ?

c'est un peu long à détailler..

Hors ligne

#31 Le 13/03/2016, à 12:08

grigouille

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Éventuellement, tu peux nous donner du code latex pour nous expliquer.

Après, je me demande pourquoi la variable d est un dictionnaire.


Debian (xfce) 12
HP LaserJet M1132 MFP

Hors ligne

#32 Le 13/03/2016, à 13:04

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

grigouille a écrit :

Éventuellement, tu peux nous donner du code latex pour nous expliquer.

Après, je me demande pourquoi la variable d est un dictionnaire.

Vous pouvez voir ce lien, et télécharger le document où j'y ai  expliqué mes idées :

dépôt des hal

Et n’hésiter pas d'améliorer l'algorithme si vous avez bien compris la théorie.

Merci


Par ailleurs, connaissez vous des liens pour les tests de codes en ligne , car mon ordi est fatigué?

Dernière modification par msg21 (Le 13/03/2016, à 13:20)

Hors ligne

#33 Le 13/03/2016, à 16:09

claudius01

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonjour,

msg21 a écrit :

...
Par ailleurs, connaissez vous des liens pour les tests de codes en ligne , car mon ordi est fatigué?

Vu ce que tu demandes comme puissance, je pense qu'il te faut t'orienter vers des services de cloud computing comme Google Cloud Platform et/ou Plates-formes AWS de Amazon en attendant d'investir dans un Calculateur Quantique (je pense que cela va te changer la vie ;-)

Dernière modification par claudius01 (Le 13/03/2016, à 16:59)

Hors ligne

#34 Le 13/03/2016, à 22:37

claudius01

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonsoir msg21 et tous

Intéressant tout cela...

Je lis dans le document "Le problème de l'Hamiltonien..." Algorithmes quantiques, cycles hamiltoniens et la k-coloration des graphes par M Sghiar - §4 Conclusion:

Ayant montré l’existence d’un algorithme polynomiale pour résoudre les problèmes du voyageur de commerce et le problème de la k-coloration, il s’avère claire qu’on a bel et bien P=NP.

Certes, mais alors que dire de l'importance et implications de P=NP:

Trouver un algorithme qui résout un problème NP-complet, comme le problème du voyageur de commerce, en temps polynomial suffirait à démontrer que P=NP, ce serait alors toute une série de problèmes très importants qui se trouveraient résolus (et, dans un même temps, les systèmes de cryptographie à clé publique seraient cassés). Même sans exhiber un algorithme, une preuve pourrait donner des indices précieux pour construire un tel algorithme...

Précision: Malgré la simplicité de son énoncé [Problème du voyageur de commerce], il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte rapidement dans tous les cas. Plus précisément, on ne connait pas d'algorithme en temps polynomial, et sa version décisionnelle (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes et qui termine dans la ville de départ ?) est un problème NP-complet, ce qui est un indice de sa difficulté.

@msg21: Tu te rends compte de ce que tu écris (Sic: Ayant montré l’existence d’un algorithme polynomiale pour résoudre les problèmes du voyageur de commerce et ...) ou alors je n'ai strictement rien compris ... ce qui est bien possible ?!..

NB: Si tu es dans le vrai, ce que je te souhaite, je comprends mieux maintenant pourquoi tu recherches des ressources humaines et matérielles pour continuer à vérifier cette preuve. Si le cas, met le paquet (cf. mon précédent post #33).

A suivre...

Dernière modification par claudius01 (Le 14/03/2016, à 09:47)

Hors ligne

#35 Le 14/03/2016, à 20:39

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Merci claudius 01  pour votre intérêt pour le sujet....

à suivre....

Hors ligne

#36 Le 14/03/2016, à 21:50

claudius01

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonsoir msg21 et à tous,

De rien et je ne manquerai pas de te suivre sur ce problème ouvert P = NP de l'Institut de mathématiques Clay car, je cite:

... le seul problème de la liste potentiellement accessible aux non-spécialistes, dans la mesure où sa description est accessible et une idée simple pourrait suffire à le résoudre.

Allez, si je peux contribuer à ta réussite avec mon niveau d'amateur curieux, je ne te demanderai que ... 1% du prix ;-)

Hors ligne

#37 Le 14/03/2016, à 22:49

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

claudius01 a écrit :

Bonsoir msg21 et à tous,

De rien et je ne manquerai pas de te suivre sur ce problème ouvert P = NP de l'Institut de mathématiques Clay car, je cite:

... le seul problème de la liste potentiellement accessible aux non-spécialistes, dans la mesure où sa description est accessible et une idée simple pourrait suffire à le résoudre.

Allez, si je peux contribuer à ta réussite avec mon niveau d'amateur curieux, je ne te demanderai que ... 1% du prix ;-)


Bonne nouvelle : le journal a accepté sa publication : ....

Dernière modification par msg21 (Le 15/03/2016, à 09:28)

Hors ligne

#38 Le 15/03/2016, à 11:57

claudius01

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonjour msg21 et à tous,

msg21 a écrit :

Bonne nouvelle : le journal a accepté sa publication : ....

Content pour toi msg21 et Bonne Journée ...

A suivre...

Hors ligne

#39 Le 23/03/2016, à 20:44

msg21

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

claudius01 a écrit :

Bonjour msg21 et à tous,

msg21 a écrit :

Bonne nouvelle : le journal a accepté sa publication : ....

Content pour toi msg21 et Bonne Journée ...

A suivre...

Merci,

Voici le lien de sa publication : Pioneer journal of mathematics and mathematical sciences, Pioneer scientific publisher, 2016, 17 (1),
http://www.pspchv.com/Abstract-PJMMS/pd … 0PJMMS.pdf


<http://www.pspchv.com/content_1_PJMMS_v … sus-1.html>

Une notice : https://hal.archives-ouvertes.fr/hal-01288408



cher claudius :

Le plus surprenant est ça :



Resté ouvert il y a156 ans, le fameux problème de l'hypothèse de Riemann était un casse tête pour les mathématiciens : Sa preuve est ici :
http://www.pspchv.com/Abstract-PJANTA/p … 201-31.pdf


http://www.pspchv.com/content_PJNTA-vol … s-1-2.html

See also :

https://hal.archives-ouvertes.fr/view/i … cZq8.gmail

Dernière modification par msg21 (Le 23/03/2016, à 21:10)

Hors ligne

#40 Le 23/03/2016, à 22:02

claudius01

Re : RESOLU ET PUBLIE Test d'un code python (SVP)

Bonsoir msg21 et à tous,

Grand Merci, mais c'est une mine d'or ces publications ... je regarde en espérant que mon niveau permettre d’apprécier la beauté de la chose ;-)

Merci encore, A+
--
Claudius

Hors ligne