Les matheux sont dans la place - pt=prout

[Cwningen]

Un max (s'il existe) est un cas particulier de sup.
Prenons le cas du degré d'un polynôme. C'est le max des k tq a_k est non nul (avec les notations usuelles), et c'est aussi le sup sur k. Si le polynôme est nul, tous les a_k sont nuls et on cherche le sup des k dans l'ensemble vide, donc -infini.

Je dirais plutôt qu'avec cette définition, le polynôme nul n'a pas de degré. Mais on peut en définir un par convention. Pour les comparaisons de degré, n'importe quel nombre négatif ferait l'affaire. Mais l'infini négatif permet d'écrire deg(0 × X) = deg(0) + deg(X) = -∞ + 1 = -∞ À moins que ce soit une conséquence de la convention sur les opérations répétées zéro fois et qu'au final ce soit toujours la même idée ?

[Shosuro Phil]

Le cas du degré des polynômes c'est encore un peu autre chose, parce que comme tu le fais remarquer, il y a une propriété supplémentaire (deg(PQ)=deg(P)+deg(Q)) que tu es bien content d'étendre; résultat la "valeur" que tu ajoutes tu as envie qu'elle soit absorbante pour l'addition, et c'est plus facile de dire que c'est -infini si tu veux ajouter une valeur X en posant X+a=a+X=X.

[Anonyme20240330]

salut,

j'ai une fonction linéaire de ce type :

Y = (A / B) * C

où B est la somme des valeurs de A , et C un nombre arbitraire.

donc par exemple, A est constitué de 100 valeurs entre 0 et 500, pour un total de B = 2225, et C = 3000

la fonction fait en sorte que le total des valeurs de Y soit égal à C.


j'essaye de faire en sorte que cette fonction ne soit plus linéaire et que la progression ralentisse avec l'augmentation de A.


ça me semble très simple à première vue mais... j'y arrive pas :emo:

faudrait multiplier ce résultat par un coefficient qui baisse avec l'augmentation de a, voire de a^n je pense?

[Shosuro Phil]

Si je lis bien, tu as un vecteur de valeurs A = (a1,a2,... an), de valeurs (positives?), B=a1+...+an, et C est fixe.

Par défaut tu prends yi = (ai/*C. Ça te forme (virtuellement) un vecteur Y=(y1,y2,...,yn), de même taille que A, et parfaitement proportionnel à A (c'est A*(C/).

Et tu voudrais former un vecteur Y', toujours de même taille que Y, mais qui favorise moins les grandes valeurs de A, toujours en étant de somme égale à C. J'ai bon? Mais tu voudrais quand même que, mettons, si ai>aj, on ait toujours y'i>y'j?

Il y a une myriade de façons de faire ça; la plus simple c'est de prendre une fonction (positive, croissante, mais concave) f, et de poser
y'i = f(ai) * C/B',
avec B'= f(a1)+f(a2)+...+f(an)

Par exemple avec f(x) qui serait la racine carrée (f(x)=racine(x)), ou (plus brutal) un logarithme (par exemple f(x)=ln(1+x) si tes valeurs de ai sont strictement positives).

[Anonyme20240330]

C'est exactement ça, oui

je n'avais pas pensé à la possibilité de repasser ça dans une 2e fonction.

j'étais justement en train d'expérimenter avec les logarithmes, qui donnent à peu près ce que je veux mais la progression initiale est un peu trop raide.

(c'est triste d'ailleurs, ça doit être du niveau 1ère S maximum et je n'y arrive pas)


merci pour les pistes !

[Shosuro Phil]

Le choix de la fonction va dépendre de ce que tu cherches à obtenir, et de à quel point les valeurs de départ sont très différentes, et à quel point certaines sont très grandes.

Le logarithme écrase fortement la progression, la racine carrée beaucoup moins.

[Enyss]

Je partirai sur une fonction de la forme

y = a* (a/amax)^(d-1) * C/B

Avec les paramètres d et amax que tu choisis en fonction de la tête de la fonction que tu veux obtenir. Un graphe interactif pour varier les paramètres ici :

https://www.geogebra.org/classic/nyyydupz

[Shosuro Phil]

Hmm, le paramètre amax ne fait rien (il change toutes les valeurs par le même facteur, donc il change B par le même facteur et au final ne change pas le vecteur normalisé). Donc ta proposition est équivalente à prendre f(x)=x^d, avec d à choisir.

Si on veut que la fonction soit croissante, il faut d>0. Et si on veut qu'elle soit concave (pour diminuer l'importance des grandes valeurs), il faut d<1. La racine carrée étant le cas d=1/2.

[Anonyme20240330]

Je partirai sur une fonction de la forme

y = a* (a/amax)^(d-1) * C/B

Avec les paramètres d et amax que tu choisis en fonction de la tête de la fonction que tu veux obtenir. Un graphe interactif pour varier les paramètres ici :

https://www.geogebra.org/classic/nyyydupz

génial ce truc, plus pratique que matplotlib

effectivement la courbe ressemble le plus à ce que je cherche quand d-1 = -1/2


Alors j'ai trouvé comment obtenir ce que je voulais -- l'équation ci-dessus ne respectait pas la contrainte d'avoir le total des valeurs de y n'excédant pas C :

y = a*(a/amax)**(-1/2)

y' = (y/sum(y)) * C


(bon c'est du python mais la syntaxe est compréhensible je pense, le ** c'est pour l'exposant)


merci à tous les deux

[Laya]

Je te confirme ** en python c'est l'exposant.

[Enyss]

Hmm, le paramètre amax ne fait rien (il change toutes les valeurs par le même facteur, donc il change B par le même facteur et au final ne change pas le vecteur normalisé). Donc ta proposition est équivalente à prendre f(x)=x^d, avec d à choisir.

J'aurai plutôt du écrire y = (x/amax)^d *b/c

Alors oui, tout ça c'est équivalent, mais ici amax est interprété graphiquement comme la compression/dilatation de la courbe de x^d sur l'axe des x, et b/c, comme la compression/dilatation sur l'axe des y. Tu perds cette interprétation en posant x^d * Cst

En particulier, le graphique interactif est beaucoup moins exploitable avec x^d *Cst et la variation directe de d et Cst

[Shosuro Phil]

Alors j'ai peut-être mal compris la question de départ, mais j'avais pris comme donnée qu'on voulait que le vecteur final se somme à 1. Quand on veut définir un tel vecteur, il suffit de dire "on va prendre chaque coordonnée proportionnelle à tant", et ça définit le vecteur d'une manière qui est telle que remplacer "tant" par "tant * A" ne change rien.

Je n'ai pas regardé le graphique, mais s'il illustre réellement le calcul de bout en bout (i.e. il montre des vecteurs, ou au moins des répartitions des coordonnées de vecteurs) ça doit se voir.

[Gobbopathe]

[Shosuro Phil]

Je vous partage ici une vidéo, que j'ai trouvée vraiment bien, sur une découverte mathématique très récente (2-3 mois): la première "tuile apériodique connexe".

(Cf message ci-dessous de Orhin, je sais pas faire des liens Youtube)

Il s'agit d'une forme géométrique qu'on a le droit de translater, tourner, et réfléchir (symétrie par rapport à un axe), dans le but de réaliser un pavage du plan tout entier - en prenant une infinité de copies, on peut recouvrir le plan tout entier, sans que les formes ne se chevauchent.

Et la grande particularité de cette tuile, c'est qu'un tel pavage existe, mais uniquement sous la forme d'un pavage apériodique - il n'existe aucun pavage avec cette même tuile qui soit obtenu en répétant par translation, à l'infini, le même motif.

On connaissait depuis les années 60 d'autres exemples d'ensembles de tuiles qui ne peuvent réaliser que des pavages apériodiques (alors qu'initialement on pensait que ça ne pouvait pas exister: que si un pavage apériodique existait, il en existait toujours un qui soit périodique), mais soit avec plusieurs tuiles (un des records était composé par l'assez fameux "pavage de Penrose"), soit avec une tuile qui n'est pas d'un seul tenant (pas "connexe"). Le résultat de cette année fait un peu de vagues (j'en ai entendu parler par plusieurs canaux indépendants, et il est déjà vulgarisé sur Youtube), et d'après un collègue de bureau qui est un peu un spécialiste du sujet (et qui le vulgarise déjà en lycée!), cet exemple a d'autres caractéristiques nouvelles.

Et en plus, la pièce est assez jolie je trouve.

[Orhin]

Le lien est incorrect mais vu la description, je suppose que tu parles de cette vidéo :

[Awake]

Salut, j'ai une questions vraiment simple, et je pense que je pourrais facilement trouver la solution seul, mais j'aimerais confirmation

Imaginons des codes d'activation à la steam, des combinaisons par exemple de (3 * 5) * 34 (toutes les lettres + chiffres sans le i ni le 1) : XXXXX-XXXXX-XXXXX.

Combien de codes différents possibles y a-t-il ? D'instinct, je dirais 15^34 soit environ 10^39, est-ce juste ?

Niveau probabilité, on est d'accord que même en générant des dizaines de millions de codes d'activation différents, il est virtuellement impossible d'en trouver un par hasard ?

[Praetor]

Plutôt 34^15, non?

[Laya]

Si je ne dis pas de bêtise tu as 34 possibilité pour chaque X donc 34^15 possibilité in fine.

Pour faire simple tu peux imaginer 2 XX avec juste des chiffres, ça fait 10 possibilités donc 10*10 = 10**2 = 100 (les chiffres de 00 à 99).

(j'espère que j'ai bien compris ce que tu voulais dire).

[Souly]

Je lis à la louche 500 millions de jeux vendus sur Steam par an. Simplifions en considérant qu'il s'agit d'autant de clés.
Depuis 10 ans (en vrai plus, mais les ventes ont explosées donc ça doit être une bonne approximation), ça nous fait 5*10^9 clés.
34^15 vaut environ 10^23, donc en devinant une clé au hasard, la probabilité de tomber sur une existante est d'au plus 1 sur 2*10^13.
Si tu génères 1 milliard de clé (et Steam gueulera bien avant quand tu essaieras de les ajouter à la chaîne), ça serait 1 chance sur 20 000.

Sauf que ça te ferait une belle jambe de tomber sur une clé déjà utilisée. Ce qui importe est en fait le nombre de clés générées et pas encore utilisées, et là, ça ne doit pas voler bien haut (quelques dizaines de millions à tout casser), réduisant notre proba à peau de chagrin.

Donc pour répondre à ta question : à mon avis, aucune chance.

[Shosuro Phil]

Imaginons des codes d'activation à la steam, des combinaisons par exemple de (3 * 5) * 34 (toutes les lettres + chiffres sans le i ni le 1) : XXXXX-XXXXX-XXXXX.

Combien de codes différents possibles y a-t-il ? D'instinct, je dirais 15^34 soit environ 10^39, est-ce juste ?

Tu as 15 caractères, et pour chaque caractère, 34 possibilités, donc au total 34^15, soit de l'ordre de 10^22 possibilités.

(Pour t'aider à trouver qui est l'exposant et qui est la base, imagine que tu n'as que des codes de 2 caractères pris parmi les lettres (26): ça donne 26^2=26*26=576 possibilités, et pas 2^26 (quelques dizaines de millions))

Niveau probabilité, on est d'accord que même en générant des dizaines de millions de codes d'activation différents, il est virtuellement impossible d'en trouver un par hasard ?

Il faut préciser la question.

Si ce que tu veux, c'est, en essayant des codes au pif, la probabilité de trouver le code précis d'un truc donné: chaque essai a une chance sur 10^22 de "réussir", et en faisant N essais tu as une probabilité d'environ N/10^22 de réussir (on oublie les répétitions). En gros: avec une machine puissante qui ferait 1 milliard d'essais par seconde (surpuissante: je ne compte pas de temps de faire une requête à un serveur pour savoir si on a gagné), il faudrait de l'ordre de 10^12 secondes pour avoir une chance sur 10 de gagner. Et 10^12 secondes, c'est environ 30.000 ans. Donc oui, c'est essentiellement impossible.

Si ce que tu veux dire c'est que parmi les 10^22 codes il y en a un certain nombre qui sont "bons", et que tu veux savoir quelles sont tes chances, en faisant des essais au hasard, de tomber sur un "bon" code... ben il manque un paramètre critique, qui est le nombre de "bons" codes. Typiquement dans ce genre de situation, les "bons" codes c'est pas les codes qui ont été vendus légitimement, il y a une caractéristique cachée qui fait que certains codes sont considérés comme valides et les autres ne sont pas valides; et quand tu achètes un code, le serveur à l'autre bout génère un code valide (il a un algorithme qui lui permet de ne générer que des codes valides).

Pour prendre un exemple concret (et qui, tel quel, ne marcherait pas car trop facile à repérer): imagine que, sur les 15 caractères, la règle pour constituer un code valide soit que les 7 derniers caractères soient exactement les 7 premiers, dans l'ordre inverse, auxquels on a ajouté le 8e (modulo 34: on attribue à chaque caractère une valeur entre 0 et 33 et on fait les calculs modulo 34). Par exemple (je prends du modulo 10 pour que ce soit plus simple):

01234-56732-1098 serait un code légal
(les 7 derniers chiffres, 321098, sont obtenus en renversant les 7 premiers, soit 654321, et en ajoutant le 8e, soit 7, à chaque chiffre, et en ramenant entre 0 et 9 chaque résultat)
mais si tu changes 1 chiffre quel qu'il soit, ça donne un code non valide.

Dans mon exemple, il n'y a plus que 10^8 codes valides (34^8 si on prenait 34 caractères et pas 10, soit de l'ordre de 10^12; soit, parmi les 10^22 codes possibles, une proportion de 1/10^10, qui est le paramètre important. Si on te laisse tester mille codes à la seconde, compte 10^7 secondes, soit de l'ordre de 4 mois.

(Correction: mise en forme)

[FMP-thE_mAd]

D'autant que les clés sont sans doute générées quand on achète la clé, pas avant. Je vois mal une bibliothèque de clés quelque part dans Steam.

Donc, si tu génères une clé au pif, tu as virtuellement aucune chance de générer une clé valide ET qui n'existe pas encore puisque justement... elle n'existe pas encore dans Steam

[Praetor]

Ils en génèrent par blocs pour les fournir aux éditeurs et revendeurs tiers.

[FMP-thE_mAd]

Ah oui exact.

[Awake]

J'en reviens pas de m'être planté là dessus. Merci beaucoup pour les corrections.

Effectivement ma seconde question n'était pas claire, pour la reformuler :

Toujours en utilisant ce type de codes en 34 ^ (3 * 5). Imaginons qu'il y ait 50 000 codes d'activation, générés complètement aléatoirement, qui n'ai pas été encore réclamés, donc valides. Même en laissant une personne tester des centaines de millions de codes (disons 100 000 codes à l'heure, ce qui demanderais une belle infrastructure de la part du hacker, qui lui coûterais bcp plus cher que d'activer un truc ), on est virtuellement en sécurité ?

[Shosuro Phil]

Même en laissant une personne tester des centaines de millions de codes (disons 100 000 codes à l'heure, ce qui demanderais une belle infrastructure de la part du hacker, qui lui coûterais bcp plus cher que d'activer un truc ), on est virtuellement en sécurité ?

Pour la faire courte: oui, totalement. Cf le calcul précédent. En gros si (nombre de codes non encore activés) * (nombre d'essais) est minuscule comparé à (nombre de codes possibles), c'est le cas.

Et tu peux faire le calcul en puissances de 10, à ce stade. 50.000 codes: allez, je te l'arrondis à 10^ 5. 100.000 codes à l'heure: arrondissons à 10^6, je suis généreux. Le produit fait 10^11, soit, par rapport aux 10^22 codes, un ratio de 10^11. 10^11 heures, ça doit faire quelques millions d'années.

[Anonyme20240202]

https://www.quora.com/Is-it-possible...teal-the-coins

[Awake]

Pour la faire courte: oui, totalement. Cf le calcul précédent. En gros si (nombre de codes non encore activés) * (nombre d'essais) est minuscule comparé à (nombre de codes possibles), c'est le cas.

Et tu peux faire le calcul en puissances de 10, à ce stade. 50.000 codes: allez, je te l'arrondis à 10^ 5. 100.000 codes à l'heure: arrondissons à 10^6, je suis généreux. Le produit fait 10^11, soit, par rapport aux 10^22 codes, un ratio de 10^11. 10^11 heures, ça doit faire quelques millions d'années.

11 407 955,3 années d'après Google Merci Shosuro ! Difficile les maths, je paie mon arrêt de scolarité, 20 ans plus tard.

[Shosuro Phil]

C'est pas des maths, c'est de la physique de tête. Un jour c'est 10^5 secondes, une année c'est 10^3 jours (3 ans c'est 10^3 jours si tu veux vraiment être précis).

Et 2^10 = 10^3 (ça c'est de l'informatique), pour quand les choses sont exprimées en base 2 et pour faire des conversions de base.

[BentheXIII]

Howdy,

j'ai une question de barbare à poser à vous autres lettrés des maths : une histoire d'implémentation d'optimisation convexe avec contraintes inégalités.

Le problème en question est assez simple: trouver X* défini comme suit

X* = argmin(J)  s.t J(X) =   c.T X

sujet à

• [A] X = b, [A] est (6 x n)
• [G]X <= h, [G] est (2 n x n )

J'ai suivi l'approche décrite dans ce traité d'optimisation (à partir de la page 615). L'approche retenue fait appel à une fonction 'l' dite 'log barrier' qui vient avantageusement remplacer les contraintes inégalités dans une fonction de coût modifiée, de la forme

J(X|t) =  t * c.T X + l(X|[G],h)

l est de la forme

l(X|[G],h) = - sum (log ( h_i - g_i.TX )

L'introduction de la log barrier permet donc de remplacer les inégalités initiales par une pénalité supplémentaire dans la fonction de coût, qui s'optimise alors presque comme un problème égalité classique : on fixe une valeur de t , on optimise J(X,t), on augmente t et on recommence. L'augmentation de t permet de 'raidir' la pente de la fonction de coût au voisinage des bornes de faisabilité du domaine.

La structure du problème est par ailleurs aidante, dans la mesure où [G] est le stacking de deux matrices proportionnelles à l'identité, et c un vecteur de 1.

J'ai implémenté cet algorithme, mais je ne suis pas satisfait par sa performance et sa robustesse numérique. J'ai constaté que si un nombre non négligeable de composantes de X s'approchent des bornes d'activation des contraintes d'egalité (à epsilon prêt), la matrice hessienne (la dérivée seconde de la fonction de coût) explose, ce qui me laisse perplexe quant à l'exactitude de l'incrément à X alors calculé. D'une manière générale, l'algorithme 'cale' alors, car la régularisation de dX ( on calcule X = X + alpha * dX avec alpha permettant de s'assurer que X satisfait au contraintes inégalités) amène à alpha = 0.

J'ai considéré implémenter un nouvel algorithme, celui ci basé sur la formulation dite 'primal/dual' comme il en est fait état à la section "11.7 Primal-dual interior-point methods" , mais j'ai l'impression que le système linéaire à résoudre est énorme (quelque chose comme n + 6 + 2n , contre seulement 6 avec la méthode log-barrier. Par ailleurs, la matrice du membre de gauche à l'équation (11.54) n'est pas symmétrique et nécessite donc une décomposition LU pour pouvoir résoudre le système, plutôt qu'une décomposition de Cholesky comme celle mise en oeuvre dans le cas de la log-barrier. Le combo dimension plus importante + perte de la symmétrie me fait donc un peu peur.

Bref, si je résume les deux méthodes

Log-barrier :

• Pros :
  • Implémentée (bawi)
  • ne nécessite que l'inversion d'un système 6x6 symmétrique
  • Marche 'souvent' ...
  
  
• Cons
  • ... mais pas tout le temps (activations simultanées de plusieurs contraintes inégalités qui met le dawa numérique)
  • doublement itérative (besoin de choisir t, de résoudre un premier problème et d'itérer)

Primal-dual :

• Pros
  • Simple itération
  • Plus stable numériquement du fait de l'absence de 1 / epsilon au carré dans le système linéaire à inverser
  • supposément plus rapide à converger que la log-barrier method
  
  
• Cons
  • Système linéaire à inverser de grande dimension (6 + n + 2n) que la log barrier method et non symmétrique
  • pas implémentée
  
  

J'aimerais pouvoir avoir un retour de praticien.nes de l'optimisation convexe avant de pouvoir me jeter dans l'implémentation de la méthode primal/dual, et d'éventuelles assurances sur sa mise en oeuvre.

Ai-je oublié qu'il me faut pouvoir implémenter ça en pur C ? Merci !

[Laya]

Alors je ne suis pas aussi matheux que toi mais j'aurais fait la méthode de la descente de gradient expliqué page 466 que tu peux raffiner en la rendant stochastique si les calculs sont trop long, mais je suis probablement un bourrin.