Chapitre 8 : El ements d’algorithmique, illustrations arithm
1 1 Apprentissage de l’analyse d’un algorithme : division euclidienne a) Remarque : une des di cult es de lecture d’un algorithme en informatique par rapport aux math ematiques est qu’au cours du d eroulement d’un algorithme, une variable peut ^etre r ea ect ee et prendre successivement di erentes valeurs En info , on peut penser a la
Chapitre 7 : El ements d’analyse d’algorithmes Table des mati
La terminaison de l’algorithme est claire : la suite (r k)est une suite d’entiers naturels strictement d ecroissante jusqu’ a 0 Par d ef r N est le dernier reste non nul b) Algorithme informatique : Maths : La suite (r k) est une suite r ec d’ordre 2 : r k+1 est d e ni a partir de r k et r k−1
Brahim BESSAA - الموقع الأول للدراسة في
Les Structures de Contrôle (Conditionnelles – Itératives) Exercices Corrigés d’Algorithmique – 1ére Année MI 5 EXERCICE 1 Ecrire un algorithme qui demande un nombre à l’utilisateur, puis calcule et affiche le carré de ce nombre
Introduction - University of Bristol
In summary, to nd all solutions to (1) with jxj jyj jzj> p k, y6= zand jzj B, it su ces to solve the following system for each d2Z\(0; B) coprime to 3:
Manipuler la notion de variable informatique
Voici un algorithme Quelle sera la valeur affectée à C après l'exécution de l'algorithme ? On exécute l'algorithme suivant: A 3 Quelles sont les valeurs affectées à A et à B en fin d'exécution de l'algorithme? Quelle est la valeur affectée à A en exécutant l'algorithme suivant ? On exécute l'algorithme suivant : B 27 a
Initiation à lalgorithmique
L'ordinateur ne comprend que le langage informatique Par exemple, l'instruction Fais le calcul 4 + 7 se traduit en langage informatique par : 0010110110010011010011110 Ce langage informatique est appelé langage binaire Ce langage binaire est incompréhensible L'ordinateur ne parle pas l'anglais ou le français, et encore moins l'arabe
MATHS APPLIQUEES A LINFORMATIQUE - Introduction à la théorie
- un algorithme de calcul, - la structure d'un réseau routier ou informatique, - les relations affectives ou professionnelles entre individus, - des liens de causalité entre des événements, - etc La théorie des graphes est un outil très puissant dans l'analyse des problèmes De
Fiche 1 : Variables et affectations
Ecrire un algorithme permettant d’échanger les valeurs de deux variables A et B Exercice 1 7 Une variante du précédent : on dispose de trois variables A, B et C Ecrivez un algorithme transférant à B la valeur de A, à C la valeur de B et à A la valeur de C
Qcm mathemathique analyse algorithmes pdf
algorithme de Dieu, nombre dor, des problèmes Conversions en euro, analyse dune fiche de salaire, etc Corrigés sont détaillés, les réponses aux QCM justifiées Qcm Mathemathique -Analyse AlgorithmesVolume 1 La couverture les UFR de Mathématiques, Physique, Chimie, Informatique et STEP qcm mathématique – analyse algorithmes
[PDF] Maths argumenter
[PDF] Maths assé simple a comprendre d'après les autres
[PDF] Maths au secours aidez moi !!!!!!!!!!!!!!!!!!!!
[PDF] maths au travail segpa pdf
[PDF] Maths avec les égyptiens
[PDF] maths bac pro
[PDF] Maths besoin d'aide
[PDF] Maths besoin d'aide svp Pour calculer 35/8 svp
[PDF] maths besoin de verification merci
[PDF] Maths brevet
[PDF] maths bts cg
[PDF] Maths calcul
[PDF] maths calcul 5éme
[PDF] maths calcul besoin d'aide
Chapitre 7 : Elements d'analyse d'algorithmes
Table des matieres
1 Terminaison et correction : illustrations sur des algorithmes d'arithmetiques 1
1.1 Apprentissage de l'analyse d'un algorithme : division euclidienne . . . . . . . . . . . . 1
1.2 L'algorithme d'Euclide pour le p.g.c.d. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 La version soustractive de l'algorithme d'Euclide . . . . . . . . . . . . . . . . . . . . . 3
2 Introduction aux problemes de co^ut d'algorithme : complexite 4
2.1 Un concept mathematique important : la notationO(). . . . . . . . . . . . . . . . . . 4
2.2 Illustrations simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Illustration sur le probleme de l'evaluation d'un polyn^ome . . . . . . . . . . . . . . . . 5
2.4 Exemples d'algorithmes deja rencontres a co^ut logarithmique . . . . . . . . . . . . . . 5
2.4.1 L'exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.4.2 La recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4.3 Cas de l'algorithme d'Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1 Terminaison et correction : illustrations sur des algorithmes
d'arithmetiques1.1 Apprentissage de l'analyse d'un algorithme : division euclidienne
a)Remarque :une des dicultes de lecture d'un algorithme en informatique par rapport aux mathematiques est qu'au cours du deroulement d'un algorithme, une variable peut ^etre reaectee et prendre successivement dierentes valeurs. En info., on peut penser a la variablecomme a uncontenantet ala valeurcommeun contenu. Convention :Dans ces notes, on noteraxun nom de variable informatique etxlavaleur (ouxkles valeurs successives) stockee(s) dans la variable qui s'appellex. Cette diculte est aussi un avantage en terme de concision... quand on a bien compris... comme on espere le montrer ci-dessous. b)Un algorithme pour obtenir le reste de la division euclidienneOn se donne deux entiersaetbavecb>0. Le resultat de la division euclidienne est le couple(q;r)tel que seulementdeux variables informatiquesaetb. Au depart dansaetb, il y a les valeursaet bpour lesquelles on veut calculer la division euclidienne, mais l'algorithme modie la valeur de la variable informatiqueaet on va montrer qu'a la n, dansail y a le resterque l'on cherche. Voici l'algo. ecrit enPythonou les valeurs deaetbseront donc rentrees commearguments d'une fonction appeleereste,volontairement non documentee: def reste(a,b): while (a<0) or (a>=b): if a<0: a=a+b if a>=b: a=a-b return aComment juger de la validite de cet algorithme? Deux problemes bien distincts : ?terminaison: on doit ^etre s^ur que l'algorithme s'arr^ete au bout d'un nombre ni d'etapes, ?correction de l'algo.: on doit ^etre s^ur que l'algorithme fait ce qu'on veut, donc ici que la valeur renvoyee est bien celle du reste. 1 c)Le probleme de la terminaison : Pour etudier l'algorithme on notea0=a, etakla valeur de la variable informatiqueaapres lak-ieme etape. (M1) ici :on se place dans chacun des deux cas desifet on fait une analyse semblable a celle de la dem. mathematique. ?Sia0=a≥b, alorsa1=a0-bet si on prendkle maximum des entiers tels quea0-kb≥b alorsa0-(k+1)b1.2 L'algorithme d'Euclide pour le p.g.c.d.
a)Description mathematique(donnee dans le cours de maths) : on se donne deux nombres (a;b)et on denit une suite nie strictement decroissante d'entiers naturels(rk)k?⟦0;N⟧par r0=a,r1=bet pour toutk≥1, tant querk≠0, on denitrk+1comme le reste de la division
euclidienne derk-1parrk. La terminaison de l'algorithme est claire :la suite(rk)est une suite d'entiers naturels strictement decroissante jusqu'a 0. Par def.rNest ledernier reste non nul. b)Algorithme informatique : Maths :La suite(rk)est une suite rec. d'ordre 2 :rk+1est deni a partir derketrk-1. Traduction en info. :on a besoin d'une boucle qui modiedeux variables. EnPythonen utilisant l'operateur%pour le reste de la div. eucl. : def Euclide(a,b): b=abs(b)# pour se ramener a un b positif, ce qui ne change pas le pgcd while b>0: a,b=b,a%b return a Remarque :Dans un langage qui ne permet pas l'aectation en couple, on aura besoin d'une variable locale tampon pour faire l'echange. c)La correction de l'algorithme :pourquoi l'algo. renvoie-t-il pgcd(a,b)? La justication a ete donnee en cours de maths, et en fait, sans le dire, on a introduit un : Invariant de boucle : a chaque etape de la boucle le pgcd(a,b)est inchange. Au depart il vaut pgcd(a;b)et a la n, en notation maths, il vaut pgcd(rN;0)avecrNle dernier reste non nul.Rappel :pour tout entier, pgcd(;0)=.
1.3 La version soustractive de l'algorithme d'Euclide
Considerons l'algorithme implemente dans la fonctionPythonsuivante : def EuclideS(a,b): """calcul du pgcd par la methode des soustractions successives""" a=abs(a) b=abs(b) while (a!=0) and (b!=0): if a<=b: b=b-a elif bsonco^ut(on dit aussi la complexite) i.e. en combien d'etapes il se termine et le nombre d'operations
elementairesqu'il necessite.2.1 Un concept mathematique important : la notationO()
a)Denition (maths)Si(un)et(vn)sont deux suites reelles, on dit queun=O(vn)(sous- entendu quandn→+∞) ssi il existe un rangn0?Net une constanteA>0 tels que : Terminologie :Siun=O(vn), on dit que la suite(un)estdomineepar la suite(vn). Remarque :Siun=o(vn)alors a fortioriun=O(vn)mais la recip. est fausse.D'une maniere generale,sivn≂wnetun=O(vn)alorsun=O(wn).Dans l'exemple precedente, 4n2+120n+14566≂4n2d'ou la conclusionun=O(n2).
b)Inter^et en informatique :Souvent (mais pas toujours!) en informatique, ces constantes (comme le4devant le4n2ci-dessus-) , n'ont pas beaucoup d'inter^et. Bien s^ur on pourrait dire qu'un algo. enO(n)est aussi enO(n2)mais on essaiera toujours de donner la reponse la plus precise, la plus pertinente : il ne sert a rien de dire a quelqu'un qu'on va venir le voir dans moins d'un mois si on sait qu'on va venir demain..2.2 Illustrations simples
a)Quelle est la complexite des fonctions suivantes, en terme de nombres de multiplications*?Formuler aussi le resultat avec la notationO().
def table1(n): for i in range(11): print(i*n) def table2(n): for i in range(n): print(i*n) def table3(n): for i in range(n): 4 for j in range(n): print(i*j,end=" ") print() b) M^emes questions : en terme de nombres d'additions+ def sommeSimple(L): S=0 for i in range(len(L)):S=S+L[i]
return S def sommeDouble(n): S=0 for i in range(1,n+1): for j in range(i,n+1):S=S+i+j
return SEssayonssommeDouble1(10000). Commentaire?
2.3 Illustration sur le probleme de l'evaluation d'un polyn^ome
Pour se donner une fonction polynomialef?x↦n-1 k=0a kxk, il sut de se donner la liste desak. On considere donc notre fonction polynomiale donnee par une telle liste L. a) La methode la plus nave pour evaluerfen un pointxest alors certainement : def evaluer(L,x): S=0 for i in range(len(L)):S=S+L[i]*x**i
return S Quelle est la complexite de cette fonction, par rapport a la taillen=len(L)des donnees? b) Methode incontournable du point de vue informatique : ne pas recalculer lesxia chaque fois, mais reaecter en multipliant parx1 def evaluer2(L,x): S=0 monome=1 for i in range(len(L)):S=S+L[i]*monome # A l'etape i mon^ome vaut x**i
monome=monome*x # la il vaut x**(i+1) return S Quelle est la complexite de cette fonction, par rapport a la taillen=len(L)des donnees?2.4 Exemples d'algorithmes deja rencontres a co^ut logarithmique
2.4.1 L'exponentiation rapide
Complexite de l'exponentiation naive? Complexite de l'exp. rapide?1. pour chasser cette mauvaise habitude!
5