cours 2020/21

Modérateur : xcasadmin

parisse
Messages : 5090
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

cours 2020/21

Message par parisse » ven. sept. 11, 2020 3:21 pm

Mercredi 9/9:
Diaporama https://www-fourier.univ-grenoble-alpes ... cours1.pdf
jusqu'a detection des erreurs non compris
+
debut d'ecriture en base

parisse
Messages : 5090
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2020/21

Message par parisse » mar. sept. 15, 2020 2:38 pm

Mardi 15/9:
Ecriture en base b: exemple en base 10, observation un nombre a 4 chiffres est entre 10^3 et 10^4.
Cas general: si a s'ecrit avec n+1 chiffres alors b^n<=a<=b^(n+1)-1<b^(n+1), justification avec suite geometrique. Renvoi au poly pour l'unicite de l'ecriture.
Existence de l'ecriture: algorithme, donne en langage naturel puis programme en Xcas.
Exemple 1602 en base 16.
Reciproque: algorithme de Horner, donne en langage naturel.
Nombre d'iterations=taille de l'entier. Mais calculer le cout n'est pas encore possible a cause des operations sur les grands entiers dans une iteration.
Exemple 0x642 retour en base 10

Necessite de savoir faire des operations sur les nombres ecrits en base pour pouvoir calculer avec des grands entiers.
Cas de + et -: comme les polynomes mais avec retenues, exemple en base 10 et 2. Cout max de la taille des 2 entiers, cout optimal car la taille obtenue est <=max(taille des 2 entiers)+1 (retenue eventuelle)
Cas de *: analogie avec les polynomes, mais il faut tenir compte des retenues. Pour les polynomes le cout est le produit du nombre de coefficients (* 1 multiplication + 1 addition).

parisse
Messages : 5090
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2020/21

Message par parisse » mer. sept. 16, 2020 4:41 pm

Mercredi 16/9 (cours 3/16)
* Exemple de multiplication en base 2 (11x13)
* nombre de chiffres de a*b=nombre de chiffres de a + nombre de chiffres de b ou -1, cout de l'algorithme produit du nombre de chiffres
* si a et b ont le meme nombre de chiffres n, cout propotionnel a n^2, taille du resultat 2*n. Si on multiplie le nombre de chiffres par 2, le temps de calcul est multiplie par 4.
Illustration avec MicroPython viewtopic.php?f=49&t=2543
Avec Xcas c'est plutot multiplie par 2, et avec CPython par 3. Il existe des algorithmes plus efficaces!
Idee de l'algorithme de Karatsuba sur les polynomes, utilise par CPython pour les entiers.
* A retenir absolument (voir § du poly)
* Division euclidienne: idee de la justification de l'algorithme de la potence. Exemple de division euclidienne en base 2.
Cout de a (n+1 chiffres) divise par b (m+1 chiffres) proportionnel a (n-m)*(m) (en fait c'est plutot (n-m+1)*(m+1)), cout maximal si m est proche de n/2.
* Cas des entiers relatifs: on se ramene aux entiers naturels avec des regles de signe.
* Def de divisibilite. Ne depend pas du signe -> on se ramene au cas des entiers positifs.
1 divise tout le monde, le seul diviseur de 1 est 1.
La divisibilite est une relation d'ordre (def de relation d'ordre donnee), mais partiel (contrairement a <= sur R, j'y reviendrai rapidement lors du prochain cours le 22/9).

parisse
Messages : 5090
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2020/21

Message par parisse » mar. sept. 22, 2020 2:14 pm

Mardi 22/9 (cours 4/16)
Def du PGCD pour 2 entiers naturels (a,b) different de (0,0) comme le plus grand element de l'intersection des listes des diviseurs de a et b.
Exemple avec 10 et 6, inefficace pour de grands entiers.
Propriete PGCD(a,b)=PGCD(b,a-b*q)

Algorithme d'Euclide
Exemple 245, 55
Algorithme en langage naturel recursif et iteratif, illustration sur machine.
Nombre d'etapes <=2*nombre de bits(b) car a une iteration soit le reste est <=b/2 soit le quotient suivant est 1 et le reste suivant est b-r<b/2.
Cout en O(n^2) admis (demo dans poly).
Illustration: le programme recursif atteint vite ses limites si on prend a et b deux nombres de Fibonacci successifs.

Algorithme d'Euclide etendu et identite de Bezout : 2 exemples (dont 245 et 55).
Definition des suites r_n,u_n, v_n et preuve de l'invariant de boucle r_n=u_n*a+v_n*b

parisse
Messages : 5090
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2020/21

Message par parisse » mer. sept. 23, 2020 4:04 pm

cours du 23/9 (5/16)
Euclide etendu: algorithme en langage naturel et une implementation avec Xcas en syntaxe Python

Divisibilite, PGCD et Bezout pour des entiers relatifs : il suffit d'ajuster les signes.

Def de nombres premiers entre eux, exemple 2,3 contre-exemple 6,15
Caracterisation par a*u+b*v=1
a/pgcd et b/pgcd sont premiers entre eux
a|bc et gcd(a,b)=1 => a|c
a|c et b|c et gcd(a,b)=1 => a*b |c

Resolution de a*x+b*y=c sur un exemple de a,b,c puis cas general: condition pour avoir des solutions PGCD(a,b) divise c, solution particuliere et solution generale.

Restes chinois: a,b premiers entre eux donnes, alpha et beta quelconque, il existe gamma tel que gamma-alpha divisible par a et gamma-beta divisible par b. Ensemble des solutions=solution particuliere+multiple de a*b
Exemple

parisse
Messages : 5090
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: cours 2020/21

Message par parisse » mar. sept. 29, 2020 4:14 pm

cours du 29/9 (6/16)
Definition de nombre premier: 2 diviseurs distincts 1 et lui-meme (1 n'est pas premier).
Prop: p premier, a entier, alors soit p divise a, soit a et p sont premiers entre eux
Prop: Si p premier divise un produit de facteurs, il divise l'un d'eux.
(il peut diviser les 2!) Attention l'hypothese p premier est essentielle. Exemple/contre-exemple

Theoreme: tout entier n>=2 admet une decomposition, unique a ordre pres, comme produit de nombre premiers.
Exemple 60
Prop: si d divise n alors les facteurs premiers de d sont des facteurs premiers de n avec une multiplicite inferieure
Exemple 60|600
Liste des diviseurs d'un entier dont on connait la factorisation, nombre de diviseurs.
Exemple 60
Le PGCD de 2 entiers est le produit des facteurs communs a la puissance le min des multiplicites.

Algorithme de factorisation naif
viewtopic.php?f=49&t=2556
Discussion sur le nombre d'iterations en sqrt(n) vs l'algo d'Euclide en ln(n)^2, pour des entiers ayant une cinquantaine de chiffres.

Les resultats arithmetiques sur les entiers peuvent se generaliser aux polynomes a coefficients reels, rationnels ou complexes. Survol rapide des proprietes d'un anneau euclidien (je n'ai pas eu le temps de montrer Euclide pour le pgcd de polynomes ni Bezout pour decomposer des fractions viewtopic.php?f=49&t=2554, je le ferai rapidement la prochaine fois)

Répondre