Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Algorithmes et mathématiques Exo7 Vidéo ■partie 1. Premiers pas avec Python Vid

Algorithmes et mathématiques Exo7 Vidéo ■partie 1. Premiers pas avec Python Vidéo ■partie 2. Ecriture des entiers Vidéo ■partie 3. Calculs de sinus, cosinus, tangente Vidéo ■partie 4. Les réels Vidéo ■partie 5. Arithmétique Algorithmes récursifs Vidéo ■partie 6. Polynômes Complexité d'un algorithme 1. Premiers pas avec Python Dans cette partie on vériﬁe d’abord que Python fonctionne, puis on introduira les boucles (for et while), le test if ... else ... et les fonctions. 1.1. Hello world ! Pour commencer testons si tout fonctionne! Travaux pratiques 1 1. Déﬁnir deux variables prenant les valeurs 3 et 6. 2. Calculer leur somme et leur produit. Voici à quoi cela ressemble : Algorithme . hello-world.py >>> a=3 >>> b=6 >>> somme = a+b >>> print(somme) 9 >>> # Les résultats >>> print("La somme est", somme) La somme est 9 >>> produit = a*b >>> print("Le produit est", produit) Le produit est 18 On retient les choses suivantes : – On affecte une valeur à une variable par le signe égal =. – On afﬁche un message avec la fonction print(). – Lorsque qu’une ligne contient un dièse #, tout ce qui suit est ignoré. Cela permet d’insérer des commentaires, ce qui est essentiel pour relire le code. 1 2 Dans la suite on omettra les symboles >>>. Voir plus de détails sur le fonctionnement en ﬁn de section. 1.2. Somme des cubes Travaux pratiques 2 1. Pour un entier n ﬁxé, programmer le calcul de la somme Sn = 13 +23 +33 +···+ n3. 2. Déﬁnir une fonction qui pour une valeur n renvoie la somme Σn = 1+2+3+···+ n. 3. Déﬁnir une fonction qui pour une valeur n renvoie Sn. 4. Vériﬁer, pour les premiers entiers, que Sn = (Σn)2. 1. Algorithme . somme-cubes.py (1) n = 10 somme = 0 for i in range(1,n+1) : somme = somme + i*i*i print(somme) Voici ce que l’on fait pour calculer Sn avec n = 10. – On affecte d’abord la valeur 0 à la variable somme, cela correspond à l’initialisation S0 = 0. – Nous avons déﬁni une boucle avec l’instruction for qui fait varier i entre 1 et n. – Nous calculons successivement S1, S2,. . . en utilisant la formule de récurrence Si = Si−1 + i3. Comme nous n’avons pas besoin de conserver toutes les valeurs des Si alors on garde le même nom pour toutes les sommes, à chaque étape on affecte à somme l’ancienne valeur de la somme plus i3 : somme = somme + i*i*i. – range(1,n+1) est l’ensemble des entiers {1,2,...,n}. C’est bien les entiers strictement inférieurs à n + 1. La raison est que range(n) désigne {0,1,2,...,n −1} qui contient n éléments. 2. Nous savons que Σn = 1 + 2 + 3 + ··· + n = n(n+1) 2 donc nous n’avons pas besoin de faire une boucle : Algorithme . somme-cubes.py (2) def somme_entiers(n) : return n*(n+1)/2 Une fonction en informatique est similaire à une fonction mathématique, c’est un objet qui prend en entrée des variables (dites variables formelles ou variables muettes, ici n) et retourne une valeur (un entier, une liste, une chaîne de caractères,... ici n(n+1) 2 ). 3. Voici la fonction qui retourne la somme des cubes : 3 Algorithme . somme-cubes.py (3) def somme_cubes(n) : somme = 0 for i in range(1,n+1) : somme = somme + i**3 return somme 4. Et enﬁn on vériﬁe que pour les premiers entiers Sn = ³ n(n+1) 2 ´2 , par exemple pour n = 12 : Algorithme . somme-cubes.py (4) n = 12 if somme_cubes(n) == (somme_entiers(n)**2) : print("Pour n=", n, "l'assertion est vraie.") else : print("L'assertion est fausse !") On retient : – Les puissances se calculent aussi avec ** : 52 s’écrit 5*5 ou 5**2, 53 s’écrit 5*5*5 ou 5**3,... – Une fonction se déﬁnit par def ma_fonction(variable) : et se termine par return resultat. – if condition : ... else : ... exécute le premier bloc d’instructions si la condition est vraie ; si la condition est fausse cela exécute l’autre bloc. – Exemple de conditions – a < b : a < b, – a <= b : a É b, – a == b : a = b, – a= b! : a ̸= b. – Attention ! Il est important de comprendre que a==b vaut soit vraie ou faux (on compare a et b) alors qu’avec a=b on affecte dans a la valeur de b. – Enﬁn en Python (contrairement aux autres langages) c’est l’indentation (les espaces en début de chaque ligne) qui détermine les blocs d’instructions. 1.3. Calcul de π au hasard Nous allons voir qu’il est possible de calculer les premières décimales de π par la méthode de Monte-Carlo, c’est à dire avec l’aide du hasard. On considère le carré de coté 1, le cercle de rayon 1 centré à l’origine, d’équation x2 + y2 = 1, et la portion de disque dans le carré (voir la ﬁgure). (0,0) (1,0) (0,1) 4 Travaux pratiques 3 1. Calculer l’aire du carré et de la portion de disque. 2. Pour un point (x, y) tiré au hasard dans le carré, quelle est la probabilité que le point soit en fait dans la portion de disque ? 3. Tirer un grand nombre de points au hasard, compter ceux qui sont dans la portion de disque. 4. En déduire les premières décimales de π. Voici le code : Algorithme . pi-hasard.py import random # Module qui génère des nombres aléatoires Tir = 0 # Numéro du tir NbTirDansLeDisque = 0 # Nombre de tirs dans le disque while (Tir < 1000) : Tir = Tir + 1 # On tire au hasard un point (x,y) dans [0,1] x [0,1] x = random.random() y = random.random() if (x*x+y*y <= 1) : # On est dans le disque NbTirDansLeDisque = NbTirDansLeDisque + 1 MonPi = 4*NbTirDansLeDisque / Tir print("Valeur expérimentale de Pi : %0.3f" %MonPi) Commentaires : – Un petit calcul prouve que l’aire de la portion de disque est π 4, l’aire du carré est 1. Donc la probabilité de tomber dans le disque est π 4. – Pour tirer un nombre au hasard on utilise une fonction random() qui renvoie un nombre réel de l’intervalle [0,1[. Bien sûr à chaque appel de la fonction random() le nombre obtenu est différent ! – Cette fonction n’est pas connue par défaut de Python, il faut lui indiquer le nom du module où elle se trouve. En début de ﬁchier on ajoute import random pour le module qui gère les tirages au hasard. Et pour indiquer qu’une fonction vient d’un module il faut l’appeler par module.fonction() donc ici random.random() (module et fonction portent ici le même nom !). – La boucle est while condition : ... Tant que la condition est vériﬁée les instructions de la boucle sont exécutées. Ici Tir est le compteur que l’on a initialisé à 0. Ensuite on commence à exécuter la boucle. Bien sûr la première chose que l’on fait dans la boucle est d’incrémenter le compteur Tir. On continue jusqu’à ce que l’on atteigne 999. Pour Tir= 1000 la condition n’est plus vraie et le bloc d’instructions du while n’est pas exécuté. On passe aux instructions suivantes pour afﬁcher le résultat. – À chaque tir on teste si on est dans la portion de disque ou pas à l’aide de l’inégalité x2+y2 É 1. 5 – Cette méthode n’est pas très efﬁcace, il faut beaucoup de tirs pour obtenir le deux premières décimales de π. 1.4. Un peu plus sur Python – Le plus surprenant avec Python c’est que c’est l’indentation qui détermine le début et la ﬁn d’un bloc d’instructions. Cela oblige à présenter très soigneusement le code. – Contrairement à d’autres langages on n’a pas besoin de déclarer le type de variable. Par exemple lorsque l’on initialise une variable par x=0, on n’a pas besoin de préciser si x est un entier ou un réel. – Nous travaillerons avec la version 3 (ou plus) de Python, que l’on appelle par python ou python3. Pour savoir si vous avez la bonne version tester la commande 4/3. Si la réponse est 1.3333... alors tout est ok. Par contre avec les versions 1 et 2 de Python la réponse est 1 (car il considérait que c’est quotient de la division euclidienne de deux entiers). – La première façon de lancer Python est en ligne de commande, on obtient alors l’invite >>> et on tape les commandes. – Mais le plus pratique est de sauvegarder ses commandes dans un ﬁchier et de faire un appel par python monfichier.py – Vous trouverez sans problème de l’aide et des tutoriels sur internet ! Mini-exercices 1. Soit le produit Pn = (1−1 2)×(1−1 3)×(1−1 4)×···×(1−1 n). Calculer une valeur approchée de Pn pour les premiers entiers n. 2. Que vaut la somme des entiers i qui apparaissent dans l’instruction for i in range(1,10). Idem pour for i in range(11). Idem pour for i in range(1,10,2). Idem uploads/Industriel/ ch-algo.pdf