Cours, Chapitre d'Informatique de niveau CPGE

Tpautrel

Description

Algorithmique tronc commun
Cours, Chapitre en Informatique (2012) pour CPGE 1 MPSI

Sujets

• Ressource
• ressources pédagogiques
• École
• Lycée
• exercices
• Cours
• Devoir scolaire
• Devoir surveillé
• Annales

Informations

• Publié par: ressources-pour-le-superieur
• Nombre de lectures: 3 139
• Langue: Français

Extrait

Plan de cours

1

2

3

4

5

6

7

8

9

GÉnÉralitÉs

Cours d’algorithmique

Les variables 2.1 GÉnÉralitÉs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Les types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Affectation des variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

EntrÉes et sorties

Les tableaux

OpÉrations 5.1 OpÉrations numÉriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 OpÉrations alphanumÉriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Structures conditionnelles 6.1 Conditions simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Les tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Conditions composÉes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Tests imbriquÉs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Structures itÉratives, boucles 7.1 Les bouclesPOUR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 La boucleTANT QUE. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .

Les fonctions 8.1 GÉnÉralitÉs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Variables locales / globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Fonctions rÉcursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Algorithmes À connaitre 9.1 Calcul d’un terme d’une suite rÉcurrente . . . . . . . . . . . . . . . . . . 9.1.1 D’ordre 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.2 D’ordre 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2 ArithmÉtique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.1 Reste et quotient de la division euclidienne deaparb. . . . . . 9.2.2 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.3 Les coefficients de BÉzout . . . . . . . . . . . . . . . . . . . . . . 9.3 Calcul d’une somme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4 Calcul den!. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5 Trouver le maximum d’un tableau . . . . . . . . . . . . . . . . . . . . . 9.6 DÉcomposition d’un nombrexen basea. . . . . . . . . . . . . . . . . . 9.7 L’exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

2

2 2 2 3

3

3

3 3 4

4 4 4 4 5

5 5 6

6 6 6 7

7 7 7 7 8 8 8 8 8 9 9 9 9

1

9.7.1 9.7.2

MÉthode 1: "En force" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . MÉthode 2 (version rÉcursive): "En finesse" . . . . . . . . . . . . . . . . . . . .

GÉnÉralitÉs

DÉfinition

Un algorithme est une suitefinie, non ambigud’opÉrations.

9 9

RemarqueEn pratique, il faut diffÉrencier l’algorithme lui-mme de sa transcription dans un lan- gage de programmation.

2

2.1

Les variables

GÉnÉralitÉs

DÉfinition

Remarque

On appellevariableun emplacement dÉdiÉ dans la mÉmoire d’un ordinateur.

Les variables sont les "endroits" oÙ l’on stocke les objets avec lesquels on travaille.

ExemplePour Écrire un programme de calcul de la somme de deux nombres, on peut utiliser trois variables: deux pour les donnÉes initiales et une pour le rÉsultat.

2.2

Les types

DÉfinition

Letypede variable dÉpend de la nature de l’objet que l’on stocke dedans.

Les diffÉrents types que nous utiliserons seront:

1. les nombres entiers

2. les nombres flottants: approximations dÉcimales des nombres rÉels

3. les nombres complexes

4. les chaïnes de caractÈres: succession de caractÈres alphanumÉriques

5. les tableaux uni ou bi dimensionnels dont chacune des cases est traitÉe comme une variable

6. le typeboolÉen: une variable boolÉenne ne peut prendre que deux valeurs:

Remarques

TRUEouFALSE.

•Pour diffÉrencier la chaine de caractÈres 23 du nombre 23, on met des guillemets autour des chaïnes de caractÈres: on Écrira donc "23".

•En pseudo-En pratique, au dÉbut d’un programme, il faut dÉfinir les variables avec des types. code, on Écrira:de(s) (la) variable(s) : typeVariables: nom . 2

3

Exemple

[ position de la case ] ]peut aussi Écrire un. On

=

valeur.

En Mathematica, on note:Nom de la variable

Affecterune variable signifiespÉcifier la valeur qu’elle contient.

En pseudo-code, on Écrira: Nom de la variable←valeur.

2.3

DÉfinition

Affectation des variables

En pseudo-codeEcriture (nom de la variable) En MathematicaPrint [ nom de la variable]

En pseudo-codede la variable)Lire (nom En MathematicaNom de la variable = chets une chaïnes de caractÈres.

•Pour que l’ordinateur demande une valeur pour l’affecter À une variable, on notera:

Les tableaux

t: tableau [ taille du tableau] de

RemarqueOn fait rÉfÉrence À une case par :t [ tableau en donnant ses ÉlÉments entre accolades.

EntrÉes et sorties

{ 1 , - 1, 3 } + {2, 7, 4 } donne {3, 6, 7 } dansMathematica.

(type de case)

]peut mettre entre les cro-. On

On dÉclare les tableaux enpseudo-codede la maniÈre suivante:

DÉfinition

4

On ne les dÉclare pas enMathematica.

Variables:

Interactions ordinateur/utilisateur de base

5.1 OpÉrations numÉriques On dispose des opÉrations "classiques": addition, multiplication, division, ÉlÉvation À la puissance. Certaines de ces opÉrations s’Étendent aux tableaux.

5

OpÉrations

Input [

•Pour que l’ordinateur affiche le contenu d’une variable, on Écrira:

3

DiffÉrents opÉrateurs de comparaison:

F F F

Exemples

V F F

F V F

•=(enpseudo-code) ou= =(enMathematica)

•<, >, <= , >=

• 6=enpseudo-codeou! =enMathematica

DÉfinition

(connecteur)

ConnecteurET

(Condition 1)

oÙ les conditions sont simples ou composÉes.

Le but dune structure conditionnelle est de faire faire diffÉrentes actions À l’ordinateur en fonction du rÉsultat d’une condition.

Conditions simples

Conditions composÉes

5.2 OpÉrations alphanumÉriques La seule opÉration est laconcatÉnationqui consiste À coller bout À bout les chaïnes de caractÈres considÉrÉes. On la note souvent < >. Elle n’est pas commutative.

(Condition 2)

(opÉrateur de comparaison)

,

En MathematicaIf [ Condition non]

instruction si condition rÉalisÉ

6.2 Les tests RÉdaction

(valeur ou variable).

instruction si

En pseudo-codeSi (condition) alors: Instructions FinSi

Structures conditionnelles

6.1

DÉfinition

Condition 1 V Condition 2 V Conditions 1ETCondition 2 V 4

6.3

Unecondition composÉeest de la forme:

Les connecteurs sont:ETetOUdÉfinis À partir des tables de vÉritÉs suivantes:

(valeur ou variable)

Unecondition simpleest de la forme:

6

ConnecteurOU

NÉgation

Condition 1 Condition 2 Conditions 1OUCondition 2

V V V

V F V

F V V

F F F

On peut aussi utiliser lanÉgation, dont la table de vÉritÉ est:

Condition Non(Condition)

V F

F V

6.4 Tests imbriquÉs Quand on veut sÉparerplus de deux issues, on a deux possibilitÉs: lestests "À plats"ou lestests imbriquÉs.

Exemple

On veut tester si une variablexest strictement supÉrieure À 2, infÉrieure À 2 ou Égale À 2.

" A plat": Six >2, alors: Instructions A FinSi Six= 2, alors: Instructions B FinSi Six <2, alors : Instructions C FinSi

ImbriquÉs: Six >2, alors: Instructions A Sinon Six= 2, alors: Instructions C Sinon Instructions C FinSi FinSi

7

Structures itÉratives, boucles

Le but des structures itÉratives est de faire faire plusieurs instructions À la fois À l’ordinateur. •Si on saita priorile nombre de passage dans la boucle, on optera pour une bouclePOUR.

•Dans le cas contraire, on fait une boucle TANT QUE.

7.1 Les bouclesPOUR En pseudo-codeOn Écrira: Pouriallant de (valeur initiale) À (valeur finale), faire: Instructions FinPour Notons que la bouclePOURincrÉments toute seule l’indexi.

En MathematicaOn Écrira: Do[ instructions, {i,i min ,i max }]

5

ExemplesLes cas fondamentaux de calcul de termes d’une suite rÉcurrente, d’une somme, den!, trouver le maximum d’un tableau doivent tre parfaitement maïtrisÉs.

7.2 La boucleTANT QUE UtilisationOn fait des bouclesTANT QUEpour faire des boucles dont on ne sait pasa priori combien de passages on va faire.

ExempleSi on a un tableautde 10 000 cases d’entiers et que l’on cherche si le nombre 3 est dans le tableau, on n’aura peut-tre pas besoin d’aller regarder tous les nombres du tableau. On fait alors une boucleTANT QUErÉdigÉe de la maniÈre suivante:

En pseudo-code: Tant que Condition faire: Instructions FinTant

En Mathematica: While [ Condition , Instructions

]

RemarqueLes bouclesPOURpeuvent s’Écrire comme des bouclesTANT QUEen Écrivant que: i←1 Tant quei≤n, faire: Instructions i←i+ 1 FinTant

8

Les fonctions

8.1 GÉnÉralitÉs Les langages de programmation possÈdent des fonctions intÉgrÉes, par exempleSin [ ] , Do [ ] , Solve [ ]but ici est de pouvoir en dÉfinir.. Le

DÉfinitionComme en MathÉmatiques, les fonctions ont des "objets" en entrÉe, appelÉs paramÈtreset affiche un objet (qui peut tre diffÉrent de la nature de celui entrÉ) en retour. EnMathematica, on Écrira:

Nom [x _ , y _ , ....

Exemples

8.2

]

:

=

(Instructions

;

f [x _ ] : = x + 1crÉe la fonctionf:x7→x+ 1.

Variables locales / globales

6

rÉsultat retournÉ ).

9

7

Algorithmes À connaitre

9.1 Calcul d’un terme d’une suite rÉcurrente 9.1.1 D’ordre 1 Soit(u n )dÉfinie par :u 0 = 5, u n+1 = 5u n −2∀n∈Nveut calculer. On u m .

•On peut aussi travailler avec desvariables locales(et c’est recommandÉ), qui n’existent que dans la fonction. On peut les dÉfinir dansMathematicaavec la fonctionModule [ ].

•On peut travailler avec desvariables globales, qui existent au niveau du programme en entier et aussi dans les fonctions.

f[ n _ ] : = Module [ {u = 0, v = 1, w = 2, z }, Do [z = u + v+ w , u = v, v = z, w = z , {i, 1, n } ] ; u ]

On appellefonction rÉcursiveune fonction qui peut s’appeler elle-mme.

ExempleOn peut ainsi dÉfinir la fonction factorielle en utilisant une variable locale: fact [ n _ ] : = Module [ { p = 1 }, Do [ p = p * i,i,1, n}];p].

9.1.2 D’ordre 2 On donne la suite(u n )dÉfinie par:u 0 = 0, u 1 =−1, u 2 = 1,∀n∈N, u n+3 =u n+2 +u n+1 +u n . On veut calculeru n .

DÉfinition

Exemple

factrec[ n _ ] :

Dans tout ce qui suit, les algorithmes sont codÉs enMathematica

DÉfinition

suite[n _] : = Module[ {n, u = 5 }, Do[ u = 5 * u - 2, { i, 1, m } ]; u ]

On peut vouloir qu’une fonction modifie les variables globales: cela s’appelle leseffets

= If [ n = = 0 , 1 , n?factrec [n - 1 ]]

On peut programmer la fonction factorielle de faÇon rÉcursive de la maniÈre suivante:

8.3

Remarque de bords.

Fonctions rÉcursives

9.2 ArithmÉtique 9.2.1 Reste et quotient de la division euclidienne deaparb

Reste:reste[a _, b _ ] : (n -b) ]

= Module [ {n = 0 }, While [ n≤a, n = n + b ]; a -

Quotient:Quotient[a _, b _ ] : = Module [{r = 0, q = 0 }, While [r≤a, r = r + b; q = q + 1 ]; q - 1 ]

9.2.2 Algorithme d’Euclide PrincipeSoientaetbOn note PGCD dedeux entiers naturels. aet deb, le plus grand diviseur commun de ces deux nombres. En principe, on fait les divisions euclidiennes successives en remplaÇantaparbetbparr, reste de la division euclidienne deaparbarrive toujours À. On b= 0et le PGCD est le dernier reste non nul.

En version itÉrative= Module [ { x = a, y = b },pgcd[ a _, b _ ]: While [y !=0, z = y; y = Mod[x,y]: x = z ]; x ]

En version rÉcursive

pgcdrec [a _, b _] :

9.2.3 Les coefficients de BÉzout On rappelle le thÉorÈme suivant:

ThÉorÈme

= If [b == 0, a, pgcdrec[b, Mod[a,b]]]

2 2 Soient(a, b)∈Nexiste. Il (u, v)∈Ztel que:

au+bv=P GCD(a, b)

0 0 bezout[a _, b _]:= Module [a0 =a, b0 =b, u0 = 1, v0 = 0, u1 = 0, v1 = 1, q, r, u , v} [b0! = 0, q=Quotient[a0, b0]; r=M od[a0, b0]; a0 =b0; b0 =r; 0 u=u0−q∗u1; 0 v=v0−qv1; u0 = u1; v0 = v1 ; u1 = u’; v1 = v’ ]; {u0, v0 } ]

9.3 Calcul d’une somme On veut calculer:

n X √ 2 (k+k) k=0 8

Somme[ n _] : ]; S ]

9.4

9.5

Calcul den!

ˆ = Module [{S = 0 }, Do [S = S + (i 2 + Sqrt[i] ) , {i, 0, n }

factorielle [ n _ ] :

= Module [ { p = 1 }, Do[p = p * i, {i, 1, n } ]; p]

Trouver le maximum d’un tableau

maxtab[l _] : Do [If [ l [[i]] > u ]

= Module [ { n = Length[l], u = l [[1]] }, u, u = l[[i]] ], {i, 3, n } ];

9.6 DÉcomposition d’un nombrexen basea PrincipeOn part avecx. On fait la division euclidienne dexpara:x=aq+r,0≤r≤a. Alors rest le chiffre des unitÉs dexen basearecommence ensuite tant que. On q6= 0avecq.

decomposition[ x _ , a _ ]: = Module [ {y = x , l = { }, r, q }, While[y ! = 0, r = Mod[y, a]; q = Quotient [y, a ]; l = Prepend [l, r ]; y = q ]; l ]

9.7 L’exponentiation rapide 9.7.1 MÉthode 1: "En force"

9.7.2

puiss [x _, n _ ] :

= Module [ {p =1}, Do[p = p * x, {n } ]; p]

MÉthode 2 (version rÉcursive): "En finesse"

exporapide[ x_ , n _ ] : = If[n = = 0, 1, If [Mod[n,2] = = 0, exporapide [x * x, n/2], exporapide[x, n-1]]

9