Crible naïf et complexité — Les-mathematiques.net The most powerful custom community solution in the world

Crible naïf et complexité

J'ai écrit un petit programme simple et sans doute peu efficace qui fait un crible naïf pour les nombres premiers. Voilà : 

def Nombres(n): #liste des entiers de 2 à n
L=[]
for k in range(2,n+1):
L.append(k)
return L

def Crible(n):
L=Nombres(n)
i=0
while i<len(L):
k=i+1
while k<len(L):
if L[k]%L[i]==0:
L.remove(L[k])
else:
k=k+1
i=i+1
return L
En version courte : je pars du premier indice $i=0$ d'une liste $L$=Nombres($n$), puis pour tous les indices $k \geqslant i+1$ suivants, je regarde un par un si c'est un multiple. Si c'en est un, je l'enlève et je recommence (l'élément suivant étant maintenant à l'indice où je viens de supprimer le précédent nombre testé), sinon je passe au suivant, et quand je suis au bout de la liste j'incrémente $i$ de $1$ et je recommence. C'est vraiment comme Eratosthène à la main.
J'aimerais calculer la complexité de mon algorithme. Donc trouver un $O(f(n))$ du nombre d'opérations que prend Crible($n$). Je ne sais pas exactement comment on calcule ça, je me doute qu'il y a $n$ opérations pour créer Nombres($n$), $n$ opérations d'incrémentation de $i$... mais les choses comme retirer un élément d'une liste, je ne sais pas du tout. Donc comment on fait pour calculer ça ?
Une question subsidiaire qui m'intéresserait est celui du temps réel d'exécution du programme. J'ai testé, avec $n=10.000$ ça prend une seconde, $20.000$ à peine plus mais il n'affiche plus le résultat dans Shell (j'ai un "squeezed text"), avec $n=100.000$ ça a pris un peu plus de temps mais c'est encore sous 40 secondes... et mon ordinateur n'est pas particulièrement puissant. Donc la question serait, si l'on connait la fréquence du processeur (et j'imagine aussi le nombre de coeurs/threads), la quantité de RAM disponible, etc, et le $O(f(n))$ d'un programme, peut-on déterminer la durée réelle d'exécution d'un programme sur une machine donnée ?

Réponses

  • Modifié (July 2023)
    Ce sont des questions compliquées si tu veux des réponses très précises. En pratique, ce qui nous intéresse pour ce genre d'algorithmes, c'est le nombre d'opérations basiques que tu demandes de faire à la machine. En général on considère que l'opération basique est l'addition en binaire puisque c'est ainsi que les entiers sont stockés en mémoire dans l'ordinateur. Les autres opérations du style ajouter un élément dans une liste ou comparer deux nombres sont considérées comme négligeables en termes de coût.
    Je n'ai pas le temps de beaucoup développer ce soir, mais tu peux chercher à montrer que l'addition de $m$ et $n$ coûte (au plus) $O(\log(\max(m, n))$, leur multiplication coûte (au plus, naïvement) $O(\log(\max(m, n))^2)$. A la louche, une méthode à la Ératosthène coûte $O(\sqrt n)$, ce qui est exponentiel en $\log n$, la taille de $n$ dans la mémoire de l'ordinateur et est donc catastrophique.
  • dpdp
    Modifié (July 2023)
    Il est tard je ne vais donc pas prendre le temps de détailler des masses ce coup-ci, mais simplement deux choses :
    1. Prend l'habitude de chercher tes algorithmes sur Wikipédia anglais pour deux raison : ils donnent souvent une version en pseudo-code, utile pour apprendre à implémenter soi-même et ils détaillent pas mal de choses, notamment les complexités. Sans compter qu'ils ouvrent des portes avec les "voir aussi" mettant en liens d'autres algos related. Dans le cas qui nous intéresse ici tu peux faire un petit tour sur la crible d'Ératostène https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    2. Si tu veux tester tes petits programmes et algorithmes (je te comprends, je fais pareil pendant des heures c'est amusant :)) un très bon programme gratuit pour cela c'est hyperfine. Il y en a sans doute d'autres mais c'est mon petit préféré. :)
    「少年はみんな 明日の勇者ぁ〜!」
  • LEGLEG
    Modifié (July 2023)
    Bonjour

    Comment on insert un programme Python ? je n'ai pas trouvé les balises code ...? 
    car j'ai essayé avec : format et code ... ça ne donne rien ...? 
  • Après avoir cliqué sur le menu déroulant et sur "code", on voit apparaître une ligne de couleur... mais il est difficile d'insérer un code déjà tapé.
    Le plus facile est alors de cliquer sur le symbole à droite pour basculer en mode HTML, et d'insérer son code entre les balises <code> et </code> avant éventuellement de rebasculer en mode "normal".
    L'affichage de l'éditeur n'a pas exactement les mêmes couleurs que l'aperçu ou le post, mais ça ne change rien.
  • LEGLEG
    Modifié (July 2023)
    Ça ne donne rien , J'ai donc tapé les balises code :
    <code>
    et j'ai inséré le programme entre ces deux balises
     </code> 
    sans résultat ...

    Donc si cela peut donner une idée à @Homo Topi je pense insérer le fichier pdf du petit programme crible Ératosthène (variante modulo 30)
  • @LEG tu vois là où tu as les options gras, italique, barré etc sur cette page ? A gauche du smiley, le symbole bizarre, tu choisis "Code". Tu copies-colles ton code, ensuite tuy bascules en HTML avec le truc "</>" tout à droite, et il faut enlever quelques morceaux pour que ça se présente bien. Tu effaces class="CodeBlock",<code> et </code> et ça se présente joliment !

    @Poirot après avoir testé mon code avec $n=100.000$ (40 secondes) et $n=200.000$ (2 minutes 20), j'ai essayé avec $n=1.000.000$ et j'ai interrompu l'exécution après 18 minutes. Effectivement, c'est terriblement lent. J'ai codé mon truc en 15 minutes (le temps de trouver comment formuler le truc qui déconnait) sans faire le moindre effort sur l'optimisation, et j'ai vu tout de suite les effets ! Je retiens que les calculs de complexité prennent en compte en premier lieu les calculs. Je ne sais pas vraiment comment un ordinateur stocke et traite les informations, je ne sais pas pourquoi ajouter/supprimer/déplacer un élément dans une liste en Python serait négligeable parce que je n'ai aucune idée comment l'ordinateur le fait. Mais ne te prends pas la peine de développer une explication juste pour ça, parce que des "manipulations de base" en Python (comme là sur les listes) il doit y en avoir des milliers, donc on n'en finira jamais. Il me faut un cours sur les calculs de complexité, de préférence basé sur du Python, j'irai voir ce que je trouve.

    @dp je prends note !
  • LEGLEG
    Modifié (July 2023)
    import os
    from math import*
    def main():
        k = 3
        Pi = [7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89]
        limite = int(input("Quelle valeur limite pour k ?"))
        while k <= limite:
            ss = 30*k
            s = int(sqrt(ss))
            Pp = [31,29,23,19,17,13,11,7]
            Ptemp = []
            reste = []
            r = 0
            i = 0
    
            #Selection des 1ers
            while Pi[i] <= s:
                Ptemp.append(Pi[i])
                i = i+1
    
            #calcul des restes de bases
            lenPtemp = len(Ptemp)
            j = 0
            for i in range(lenPtemp):
                r = ss%Ptemp[i]
                if r <= 31:
                    reste.append([])
                    reste[j].append(r)
                    j = j+1
    
            #completion du tableau de reste
            lenreste = len(reste)
            for i in range(lenreste):
                j = 0
                while reste[i][j] <= 31-Ptemp[i]:
                    reste[i].append(reste[i][j]+Ptemp[i])
                    j = j+1
    
            #calcul des nombres 1ers
            lenPp = len(Pp)
            for i in range(lenPp):
                ok = 1
                for j in range(lenreste):
                    lenrestei = len(reste[j])
                    for l in range(lenrestei):
                        if reste[j][l] == Pp[i]:
                            ok = 0
                if ok == 1:
                    Pi.append(ss-Pp[i])
            k = k+1
        print("Nombres premiers:",Pi)
    main()
    os.system("pause")
    
  • Ok @Homo Topi Lorsque tu va exécuter Python , tu tapes la valeur de k? à la demande (par ex k? 30 000 cela va cribler jusqu'à la limite 900 000 = 30*30 000 , en un peu moins de 5 secondes ...
  • Oui, c'est évident qu'on peut faire des codes plus optimisés que le mien, mon but là n'était pas encore de faire un truc optimal. Je regarderai comment fonctionne ton code en détail plus tard, ça va me prendre du temps à déchiffrer.
  • LEGLEG
    Modifié (July 2023)
    Oui , j'ai bien compris ton but ...
    ces deux programmes on été fait par mon petit fils , il y a quelque temps...
    le deuxième ci dessous extrait les nombres premiers de n à 2n.
    import math
    
    def eratostene(n):
    	m = (n-1) // 2
    	b = [True]*m
    	i = 0
    	p = 3
    	premiers = [2]
    	while p*p < n:
    		if b[i]:
    			premiers.append(p)
    			j = 2*i*i + 6*i + 3
    			while j < m:
    				b[j] = False
    				j = j + 2*i + 3
    		i += 1
    		p += 2
    	while i < m:
    		if b[i]:
    			premiers.append(p)
    		i += 1
    		p += 2
    	return premiers
    
    def compteInfN(liste, n):
    	lenListe = len(liste)
    	compte = 0
    	for i in range(0, lenListe):
    		if(liste[i] >= n):
    			compte += 1
    	return compte
    
    def premiersNa2N(n):
    	liste = eratostene(2*n)
    	compte = compteInfN(liste, n)
    	print("> On prend N = "+str(n)+" , donc 2N = "+str(2*n))
    	print("> "+str(n)+" / log("+str(2*n)+") = "+str(n/math.log(2*n)))
    	print("> On compte "+str(compte)+" nombres premiers entre "+str(n)+" et "+str(2*n))
    	print("> Voici la liste des nombres premiers entre "+str(n)+" et "+str(2*n)+" :")
    	print(liste[len(liste)-compte:])
    
    n = int(input("Donnez la valeur de N : "))
    premiersNa2N(n)
    input()
  • Modifié (July 2023)
    Attention, les listes Python ne sont pas des listes mais des tableaux (un peu spéciaux en plus). Donc évite de prendre Python comme exemple pour les listes (et pour les calculs de complexité en général). Essaie plutôt de travailler en pseudo-code en algo, c'est plus compréhensible et universel, et cela évite les erreurs dues aux spécificités d'un langage de prog.
    Si tu cherches des bouquins d'algorithmique et complexité, il y a le Cormen qui est assez exhaustif et facile d'accès (mais attention, certaines preuves sont fausses, dont la plupart avec des probas). Sinon, si tu arrives à attraper un cours de L1/sup sur le sujet, ça fera très bien le boulot !
    Quand tu prends un tableau Python (ce que tu appelles "liste"), les informations sont stockées les unes après les autres dans la mémoire de ton ordi. Quand tu retires un élément du tableau, cela décale tout ce qu'il y a derrière donc ça peut faire très mal.
    Pour étudier la complexité d'un algo, commence par des cas simples avec des boucles Pour. Ici, tu as fait une boucle Pour déguisée en boucle Tant que, ce n'est pas le plus simple. Tu aurais pu plus simplement écrire "for i in range(0,len(L))" qui est plus lisible.
    Ici, pour $i,k$ fixés, tu fais un nombre constant d'opérations d'où une complexité en $O(1)$.
    Pour $i$ fixé, tu fais donc $\sum\limits_{k=i+1}^n O(1) = O(n-i)$ opérations pour ta boucle intérieure.
    Pour la totalité de ton algo, ta complexité est de $\sum\limits_{i = 0}^n O(n-i) = O(n^2)$, il est donc normal que ton algo mette un temps monstrueux à répondre.
  • Modifié (July 2023)

    https://chat.openai.com/share/55b8cfac-0ef4-48d9-9747-d62717f240d7
    Pour ce qui est des cours Python, voici selon moi la meilleure chaine Youtube sur le sujet (une playlist de la chaine Docstring).

  • Je reviens sur la vidéo d'introduction du cours Python de Docstring, où il est question de l'utilisation de Jupyter Notebook pour la rédaction et l'exécution de code Python. Cette vidéo date de 2 ans et beaucoup de choses ont changé depuis (je ne parle pas de Python lui-même mais des environnements de développement). Personnellement, j'utilise l'extension "Jupyter Notebook" de Visual Studio Code, qui permet non seulement de taper le code Python mais également de l'exécuter en pressant tout simplement Ctrl+Entrée. De plus, contrairement à ce qui est dit dans la vidéo, Jupyter Notebook prend en compte la détection des erreurs présentes dans le code, comme en témoigne cette capture d'écran :

    image

    Le Jupyter Notebook affiche également le temps d'exécution du code, ce qui est très appréciable (ici 0.1s).

  • Modifié (July 2023)
    Heuristique a dit :
    Ici, tu as fait une boucle Pour déguisée en boucle Tant que, ce n'est pas le plus simple. Tu aurais pu plus simplement écrire "for i in range(0,len(L))" qui est plus lisible.
    J'ai essayé plein de trucs avec un for et ça déconnait à chaque fois, j'ai ragé et mis un while :D 
    Au départ je voulais juste avoir un code pour essayer d'en calculer la complexité. Mon code est affreusement peu optimisé, pas seulement au niveau du Python mais juste mathématiquement, mais pour essayer de calculer la complexité ça suffit. On m'a donné plein de pistes pour essayer d'améliorer ce que j'ai fait, et plein de choses à lire, donc... y a du boulot !
    Et, oui, je cherche plus quelque chose du style "cours de L1 en PDF" qu'un bouquin complet, je ne suis pas assez passionné de prog' (pour l'instant, au moins) pour que ça vaille le coup, je pense que je ne le lirai pas en détail si c'est trop long. Mon but c'est de savoir calculer la complexité d'un code simple, un code comme ce qu'on demande aux oraux de CAPES/Agreg, la mise en application des maths que j'ai apprises à la fac, sans que ça vole particulièrement haut non plus.
    @Wilfrid sans raconter ma life, j'ai pris un certain dégoût pour les environnement "tiers" de dev Python, je ne promets pas que je vais regarder Jupyter Notebook. J'ai un truc qui marche, dont je sais me servir, on m'en a déjà conseillé 15 différents dans le passé et ça m'avait plus embrouillé qu'autre chose, donc, je reste dans ma zone de confort en général. Si c'est juste pour les durées d'exécution réelles du code, ce n'est pas aussi important que ça pour moi, c'est juste une question que je me suis posée comme ça parce que j'apprends sur le tas.
  • Attention, Cormen ne parle jamais de prog, ou peu, c'est juste de l'algorithmique.
    En cherchant sur mon moteur de recherche préféré, je suis tombé sur les diapos de cours d'un prof de l'Université d'Aix-Marseille en pièce jointe. J'ai regardé rapidement et cela me semble bien fait. Une fois le cours lu, le meilleur moyen de se familiariser avec la complexité, c'est encore de s'entraîner à la calculer. En info, c'est un réflexe exigé : dès que tu écris un algo, il faut prouver sa terminaison, sa correction et calculer sa complexité.
  • Homo Topi a dit :
    Et, oui, je cherche plus quelque chose du style "cours de L1 en PDF" qu'un bouquin complet, je ne suis pas assez passionné de prog' (pour l'instant, au moins) pour que ça vaille le coup, je pense que je ne le lirai pas en détail si c'est trop long.
    https://info-llg.fr/ ?
    「少年はみんな 明日の勇者ぁ〜!」
  • Moult lecture ! Je ne refuse jamais. Le plus dur c'est de réussir à tout lire :D
  • Les diapos du prof d'Aix-Marseille comme le poly de LLG sont relativement courts et normalement assez abordables, ça devrait bien se passer !
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!