Remerciez-le!

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

- 1 - © 2014 - Gérard Lavau - http://lavau.pagesperso-orange.fr/index.htm Vous

- 1 - © 2014 - Gérard Lavau - http://lavau.pagesperso-orange.fr/index.htm Vous avez toute liberté pour télécharger, imprimer, photocopier ce cours et le diffuser gratuitement. Toute diffusion à titre onéreux ou utilisation commerciale est interdite sans accord de l'auteur. Si vous êtes le gestionnaire d'un site sur Internet, vous avez le droit de créer un lien de votre site vers mon site, à condition que ce lien soit accessible librement et gratuitement. Vous ne pouvez pas télécharger les fichiers de mon site pour les installer sur le vôtre. INFORMATIQUE 1ère année "Enfin, cher lecteur, [...] j'espère que la seule pensée à trouver une troisième méthode pour faire toutes les opérations arithmétiques, totalement nouvelle et qui n'a rien de commun avec les deux méthodes vulgaires de la plume et du jeton, recevra de toi quelque estime et qu'en approuvant le dessein que j'ai eu de te plaire en te soulageant, tu me sauras gré du soin que j'ai pris pour faire que toutes les opérations, qui par les précédentes méthodes sont pénibles, composées, longues et peu certaines, deviennent faciles, simples, promptes et assurées." PASCAL – La Machine Arithmétique. PLAN I : Algorithmes 1) Actions élémentaires 2) Affectations de variables 3) Instructions conditionnelles 4) Expressions booléennes 5) Instructions itératives 6) Exemples II : Types de données 1) Le stockage de l'information 2) Les variables de type simple 3) Les structures de données III : Questions diverses relatives aux algorithmes 1) Preuve d'un algorithme 2) Complexité d'un algorithme 3) Arrêt d'un algorithme IV : Bases de données 1) Attributs et schémas relationnels 2) Données et relations 3) Opérations sur la base de données 4) Exemples I : Algorithmes 1- Actions élémentaires Le mot algorithme provient du mathématicien arabe Al Khwarizmi, inventeur de l'algèbre, né durant le IXème siècle en Perse. Un algorithme est une suite finie d'instructions à appliquer dans un ordre déterminé dans le but de résoudre un problème donné. Chacun de nous applique les algorithmes appris dans l'enfance lorsqu'il calcule la somme de deux nombres, leur produit ou leur quotient. Les algorithmes, aussi complexes soient-ils, sont construits à partir d'actions élémentaires, essentiellement au nombre de trois : - 2 - • les affectations de variables • les instructions conditionnelles • les instructions itératives A cela, il faut ajouter les instructions de lecture des données et de sortie des résultats. Nous utiliserons une notation symbolique, adaptable à n'importe quel langage de programmation. Nous donnerons également des exemples de traduction syntaxique d'un algorithme en un programme utilisable sous Python, langage de programmation, Scilab, logiciel dédié au calcul numérique de données matricielles, tous deux utilisés en CPGE, Maple, logiciel de calcul formel, et Java, langage de programmation assez répandu en université. Mais ceci n'est pas un cours d'apprentissage d'un de ces langages ou logiciels, mais un cours généraliste sur les notions universelles rencontrées en informatique. Le lecteur peut également transcrire les algorithmes utilisés les plus simples sur sa calculatrice programmable ou en n'importe quel autre langage de programmation. 2- Affectations de variables L'affectation de variable permet d'attribuer des valeurs à des variables ou de changer ces valeurs. Les variables sont représentées par un nom, qui peut comporter plusieurs lettres. La plupart des langages de programmation modernes font la distinction entre majuscules et minuscules. Nous symboliserons l'affectation de variable de la façon suivante : Y ← 2 Y prend la valeur 2 X ← 2*Y+1 puis X la valeur 5 (* désigne le produit) X ← 3*X +2 puis X prend la valeur 17 Le membre de droite est une expression calculée par la machine, puis, une fois ce calcul effectué, le résultat est stocké dans la variable figurant dans le membre de gauche. Si le même nom figure dans les deux membres, cela signifie que la variable change de valeur au cours du calcul. Dans la dernière instruction ci-dessus, l'ancienne valeur 5 de X est définitivement perdue au cours de l'exécution du calcul et remplacée par la valeur 17. Affectation de variables En Python En Scilab Y = 2 X = 2*Y + 1 X = 3*X + 2 Y = 2 X = 2*Y + 1 X = 3*X + 2 En Maple En Java Y := 2; X := 2*Y + 1; X := 3*X + 2; Y = 2; X = 2*Y + 1; X = 3*X + 2; Le choix du symbole "=" en Python, Scilab et Java n'est pas très heureux, car l'instruction "←" ne désigne pas une égalité mathématique, mais une action visant à changer la valeur d'une variable. Le choix de ":=" dans Maple est de ce point de vue plus clair. - 3 - Le changement simultané de deux variables demande une certaine attention. Supposons qu'on dispose d'un couple (a, b) dont la valeur a été préalablement assignée et qu'on veuille changer la valeur de ce couple en (b, a + b). La commande suivante est incorrecte : a ← b b ← a + b car dans la deuxième instruction, la valeur de a figurant dans le membre de droite a été modifiée en celle de b dans la première instruction, ce qui a contribué à effacer la précédente valeur de a. A la fin du calcul, on a en fait remplacé le couple (a, b) par le couple (b, 2b). De même : b ← a + b a ← b donne la valeur correcte de b, mais recopie ensuite cette valeur dans a, de sorte que le couple (a, b) a été remplacé par le couple (a + b, a + b). Il convient d'utiliser une variable temporaire. Notons (a0, b0) la valeur initiale du couple (a, b). On indique en commentaire les valeurs de chaque variable au cours du calcul. Il est utile d'ajouter ce genre de commentaire dans un programme afin d'en prouver la validité. Les commentaires sont précédés d'un # en Python et Maple, d'un // en Scilab ou Java. tmp ← b # après cette instruction, tmp = b0, a = a0, b = b0 b ← a + b # après cette instruction, tmp = b0, a = a0, b = a0 + b0 a ← tmp # après cette instruction, tmp = b0, a = b0, b = a0 + b0 On a bien le résultat attendu. On aurait pu faire : tmp ← a # après cette instruction, tmp = a0, a = a0, b = b0 a ← b # après cette instruction, tmp = a0, a = b0, b = b0 b ← tmp + b # après cette instruction, tmp = a0, a = b0, b = a0 + b0 Dans les deux cas, c'est la variable dont on a stocké la valeur dans tmp qu'on modifie en premier. De même, si on veut permuter les valeurs de deux variables, on procèdera comme suit : tmp ← a # après cette instruction, tmp = a0, a = a0, b = b0 a ← b # après cette instruction, tmp = a0, a = b0, b = b0 b ← tmp # après cette instruction, tmp = a0, a = b0, b = a0 Signalons que Python dispose d'une option d'affectation simultanée des variables évitant l'utilisation de la variable tmp : a,b = b,a + b a,b = b,a 3- Instruction conditionnelle Nous écrirons cette instruction : si <Condition> alors <Bloc d'Instructions 1> sinon <Bloc d'Instructions 2> finsi <Bloc d'Instructions 1> désigne une ou plusieurs instructions à exécuter si <Condition> est vraie. <Bloc d'Instructions 2> désigne une ou plusieurs instructions à exécuter si <Condition> est fausse. Par exemple : si X >0 alors X ← X -1 sinon X ← X + 1 finsi Cette instructions retranche 1 à une variable X positive et ajoute 1 à une variable négative ou nulle. - 4 - Dans le cas où il n'y a pas de <Bloc d'Instructions 2> à exécuter, on mettra l'instruction conditionnelle sous la forme : si <Condition> alors <Blocs d'Instructions 1> finsi <Condition> est une expression booléenne pouvant prendre la valeur vraie (True) ou fausse (False), telle que X = 0, X > 0, X ≥ 0, X ≠ Y, X est un entier pair, etc... La façon de transcrire les expressions booléennes est propre à chaque langage. Par exemple, Les quatre conditions ci-dessus se traduisent par : Expressions booléennes En Python En Scilab X == 0 X > 0 X >=0 X != Y X%2 == 0 X == 0 X > 0 X >=0 X <> Y modulo(X,2) == 0 En Maple En Java X = 0 X > 0 X >=0 X <> Y X mod 2 == 0 X == 0 X > 0 X >=0 X != Y X%2 == 0 On notera l'utilisation d'un double symbole = = pour tester l'égalité de deux variables dans les langages Python, Scilab et Java puisque ces langages utilisent déjà le simple = pour l'affectation de variable. La façon de coder l'instruction conditionnelle et en particulier de signaler la fin de chaque bloc d'instructions, est également propre à chaque langage. En uploads/s3/ algo-1.pdf