Informatique et Programmation Python Extraits choisis du ...gabrel/DOCUMENTS/... · Plan du cours 1 Algorithmes et programmation : principaux concepts et instructions élémentaires

Informatique et Programmation Python 1

CPES1

2019-2020

1. Extraits choisis du cours d’Informatique de L1 MIE conçu avec E. Lazard, M. Manouvrier

CPES1 Informatique 2019-2020 1 / 73

Plan du cours

1 Algorithmes et programmation : principaux concepts etinstructions élémentaires

2 Définition et appels de fonction3 Structures de données séquentielles : chaines de caractères et

listes4 Tuples, dictionnaires et tris5 Analyse d’algorithmes et premières notions de complexité : le cas

des algorithmes de recherche


Chapitre 1 - Algorithmes, variables et types

1.1 Algorithmes et programmation : principaux concepts1.2. Valeurs, types et variables1.3. Instructions élémentaires

1.3.1 Affectation et expression1.3.2 Lecture et écriture

1.4. Instructions conditionnelles1.5. Instructions répétitives


Exemple :

FIGURE – f (x) = x3 − 1


ASCII = American Standard Code for InformationInterchange

FIGURE – Table ascii


Algorithme qui détermine si une équation du second degré,ax2 + bx + c = 0, n’admet aucune solution réelle :

ALGOVARIABLESa TYPE NOMBREb TYPE NOMBREc TYPE NOMBREd TYPE NOMBREDEBUT

ECRIRE "Quel est le paramètre a?"LIRE aECRIRE "Quel est le paramètre b?"LIRE bECRIRE "Quel est le paramètre c?"LIRE cd <- b*b - 4*a*cECRIRE "Le discriminant est égal à : ", dSI (d<0) ALORS

DEBUTECRIRE "L’équation n’admet aucune racine réelle"

FINFIN


Reprise de l’exemple du transparent 6 avec un SINON :

ALGOVARIABLESa, b, c, d TYPE NOMBREDEBUT

ECRIRE "Quel est le paramètre a?"LIRE aECRIRE "Quel est le paramètre b?"LIRE bECRIRE "Quel est le paramètre c?"LIRE cd <- b*b - 4*a*cECRIRE "Le discriminant est égal à : ", dSI (d<0) ALORS

DEBUTECRIRE "Le discrimant est négatif"ECRIRE "L’équation n’admet aucune racine réelle"

FINSINON

DEBUTECRIRE "L’équation admet au moins une racine réelle"

FINFIN


ALGOVARIABLESa TYPE NOMBREDEBUT

ECRIRE "Quel est le paramètre a?"LIRE aSI (a!=0) ALORS

DEBUTSI (a%2==0) ALORS

DEBUTECRIRE "C’est un nombre pair"SI (a>0) ALORS

DEBUTECRIRE "et positif"

FINFIN

FINSINON

DEBUTECRIRE "Il est nul"

FINFIN


Traduction de l’exemple du transparent 6 en Python :

a = float(input("Donner le paramètre a : "))b = float(input("Donner le paramètre b : "))c = float(input("Donner le paramètre c : "))d = b*b - 4*a*cprint("Le discriminant est égal à : ", d)if d < 0:

print("Votre équation n’admet aucune racine réelle")

Autre exemple : Que se passe-t-il lors de l’exécution duprogramme ci-dessous pour x = 4 ?

x = int(input("Donner l’inconnue x positive ou nulle : "))if x >= 10:

print("x n’est pas constitué d’un unique chiffre")print("parce qu’il est plus grand que 10")


Traduction de l’exemple du transparent 7 en Python :

a = float(input("Donner le paramètre a : "))b = float(input("Donner le paramètre b : "))c = float(input("Donner le paramètre c : "))d = b*b - 4*a*cprint("Le discriminant est égal à : ", d)if d < 0:

print("Le discrimant est négatif.")print("Votre équation n’admet aucune racine réelle")

else:print("Votre équation admet au moins une racine réelle")


Que fait le programme Python suivant?

if True:print("Tout juste")

else:print("Pas bon")


a = float(input("Donner le paramètre a : "))b = float(input("Donner le paramètre b : "))c = float(input("Donner le paramètre c : "))d = b*b - 4*a*cif d < 0:

print("L’équation n’admet aucune racine réelle")elif d == 0:

print("L’équation admet une unique racine réelle")else:

print("L’équation admet deux racines réelles distinctes")


Exercice : Dans l’algorithme ci-dessous, le texte de "message2" peut-ilêtre plus explicite quant à la parité et au signe de a ?

ALGOVARIABLESa TYPE NOMBREDEBUT

ECRIRE "Quel est le paramètre a?"LIRE aSI (a>0 ET a%2==0) ALORS

DEBUTECRIRE "C’est un nombre pair positif"

FINSINON

DEBUTSI a%2==0 ALORS

DEBUTECRIRE "message2"

FINFIN

FIN


Instruction TANT_QUE

Exemple 1 : Algorithme affichant les entiers de 1 à 10

ALGOVARIABLESx TYPE NOMBREDEBUTx <- 1TANT_QUE (x<=10) FAIREDEBUTECRIRE xx <- x+1

FINFIN


Exemple 2 : Que fait cet algorithme?

ALGOVARIABLESn TYPE NOMBREDEBUTlire nTANT_QUE n >= 0 FAIREDEBUTECRIRE nn <- n-1

FINFIN


Exemple 3 : On veut connaître le plus petit entier n tel que2n ≥ 10 000.

Compléter les lignes 2 et 3 de l’algorithme ci-dessous pour qu’ilréponde au problème.

ALGOVARIABLESn TYPE NOMBREDEBUT1 n <- 12 TANT_QUE (2**n ???? ) FAIRE

DEBUT3 n <- ????

FIN4 ECRIRE nFIN

Ex. repris de http://www.xm1math.net/algobox/exemples/dichotomie.html


Instruction while en Python

Exemple 4 : Programme Python affichant les entiers de 1 à 10

n = 1while n <= 10:

print(n)n = n + 1


Exemple 5 : que se passe-t-il ?

n = 1while n <= 10:

print(n)n = n + 1

Exemple 6 : que se passe-t-il ?

n = 1while True:

print(n)


L’instruction break

Exemple 7 : Lecture au clavier de 10 valeurs >0 et affichage de leursomme

Stratégie 1 pour gérer les erreurs de saisie : interrompre la lecture enutilisant l’instruction break

cpt = 0somme = 0while cpt < 10:

x = int(input())if x <= 0:

print("Erreur de saisie")break

somme += xcpt += 1

if cpt < 10:print("Erreur de saisie")

else:print("La somme des 10 valeurs lues est :", somme)

Instruction non autorisée en algorithmiqueCPES1 Informatique 2019-2020 19 / 73

L’instruction continue

Stratégie 2 pour gérer les erreurs de saisie : poursuivre la lecturejusqu’à obtenir 10 valeurs >0 en utilisant l’instruction continue



continuesomme += xcpt += 1

print("La somme des 10 valeurs lues est :", somme)

Instruction non autorisée en algorithmique


Réécriture de la stratégie 1 p. 19 sans instruction break



print("Erreur de saisie")cpt = 10

else :somme += xcpt += 1

if x <= 0:print("Erreur de saisie")

else:print("La somme des 10 valeurs lues est :", somme)


Réécriture de la stratégie 2 p. 20 sans l’instruction continue


x = int(input())if x > 0:

somme += xcpt += 1

print("La somme des 10 valeurs lues est :", somme)


Plan du cours

Chapitre 2 - Fonctions2.1 Introduction2.2 Utiliser des fonctions appartenant à des modules2.3 Fonctions en pseudo-code

DéfinitionAppel

2.4 Fonctions en PythonDéfinitionAppelStructure d’un programme PythonPortée des variables en Python


Exemples de fonctions déjà utilisées en Python

1 nom = input()

2 nom = input("Saisir votre nom")

3 ch = "Saisir votre nom"

nom = input(ch)

4 print("Nom:", nom, "Prénom:", prenom, note)


Utiliser des fonctions appartenant à des modules

Exemple : Utiliser la fonction sqrt du module mathimport mathx = math.sqrt(4)

1 importer le module math (les fonctions et constantes du modulepeuvent alors être appelées - elles sont accessibles !)

2 appeler la fonction sqrt du module math en lui donnantl’argument 4 pour calculer sa racine carrée. La valeur renvoyéeest référencé par la variable x.


Les modules Python

Modules = bibliothèques contenant des fonctions qu’il est possibled’appeler.

math : contient des fonctions et constantes mathématiques debase (sin, cos, exp, logarithme, racine carrée, puissance, π...) ;os : contient des fonctions et constantes permettant d’interagiravec le système d’exploitation ;random : contient des fonctions et constantes permettant degénérer des nombres aléatoires ;time : permet d’accéder à l’heure de l’ordinateur et aux fonctionsgérant le temps ;numpy : algèbre linéaire, calcul numérique ;matplotlib : représentation graphique.


Utiliser les modules Python : 1ère méthode

1 import nomModule2 help(nomModule) pour obtenir de l’aide sur un module3 dir(nomModule) pour connaître la liste des

fonctions/méthodes/constantes incluses dans un module4 nomModule.nomFonction(...) pour appeler n’importe

laquelle des fonctions incluses dans ce module

Renommer un moduleimport numpy as np


Utiliser les modules Python : 2eme méthode

Exemplefrom random import randintrandint(2,19)

permet d’importer une fonction particulière d’un module.

Pour importer toutes les fonctions d’un modulefrom nomModule import *

Attention si, avec cette méthode, on importe des fonctions portant lemême nom provenant de modules différents, c’est la dernière fonctiondu dernier module importé qui sera alors la seule accessible.


Exercice : déterminer les nombres parfaits <= n

ALGOVARIABLESn TYPE NOMBRE

DEBUTLIRE nTANT_QUE (n>1) FAIREDEBUTSI (sommeDiviseurs(n)==n) ALORS

DEBUTECRIRE n

FINn <- n-1

FINFIN

ou en Python :

n = int(input())while n > 1:

if sommeDiviseurs(n) == n:print(n)

n = n - 1


Exemple : la fonction sommeDiviseurs

FONCTION sommeDiviseurs(e TYPE NOMBRE) TYPE NOMBREVARIABLES_LOCALESsomme, d TYPE NOMBRE

DEBUTd <- 1somme <- 0TANT_QUE (d<e) FAIREDEBUT

SI ((e%d)==0) ALORSDEBUT

somme <- somme+dFIN

d <- d+1FIN

RENVOYER sommeFIN


Exercice

Ecrire une fonction prenant en argument une année et qui teste sil’année est bissextile : la fonction doit renvoyer une valeur booléenneVRAI si l’année est bissextile et FAUX sinon.


La fonction bissextile en pseudo-code

FONCTION bissextile(annee TYPE NOMBRE) TYPE BOOLEENVARIABLES_LOCALES

b1, b2 TYPE booleenDEBUT

b1 <- (annee%4 == 0) and (annee%100 != 0)b2 <- annee%400 == 0RENVOYER b1 or b2

FIN


Appel de fonction

Exemple de fonction :

FONCTION carre(v TYPE NOMBRE) TYPE NOMBREDEBUT

RENVOYER v*vFIN

Exemples d’appel de la fonction carre() :

c <- carre(2)ECRIRE carre(2)SI carre(2)==6 ALORS DEBUT ... FIN


La fonction bissextile en Python

def bissextile(annee):b1 = (annee%4 == 0) and (annee%100 != 0)b2 = annee%400 == 0return b1 or b2


Analyser les fonctions suivantes

def afficheBonjour():print(’Le résultat est Bonjour’)

def affiche(v):print("Le résultat est", v)

def concat(ch1,ch2):return ch1+ch2

def resteEtQuotient(num,denom):return num%denom, num//denom


Exemple : calcul de l’image de x sur 2*x + 1

def imageV1(x):return 2*x+1

def imageV2(x):print(2*x+1)

Pour afficher le résultat à l’écran, quelle instruction appelante?

imageV1(3)print(imageV1(3))imageV2(3)print(imageV2(3))

Evaluer les expressions suivantes :

7 == imageV1(3)7 == imageV2(3)

Combien vaut v?

v = imageV1(3)v = imageV2(3)


Exemple : Fonction sans instruction return

>>> def g(x): print(2*x+1)

>>> print(g(3))7 # affichage dans fonctionNone # affichage de la valeur renvoyée

>>> g(3) == None7 # affichage dans fonctionTrue # g(3) est remplacée par sa "valeur"


Ce qu’il ne faut pas faire !

Exemple : redéfinition de la fonction print()

def print():return True

print(’bonjour’)

Traceback (most recent call last):File "<console>", line 1, in <module>

TypeError: print() takes 0 positional arguments but 1 was given


Exemple

def incrementerEntier(n):n = n + 1return n

m = 5print(’Valeur retour :’,incrementerEntier(m))print("Valeur de m :", m)

affiche

Valeur retour : 6Valeur de m : 5


Structure d’un programme Python

Contrainte : Entête d’une fonction doit avoir été lue par l’interpréteuravant d’être appelée !

Conventionimport ....

def fonction1(...) :...



BlocInstructions = Programme principal


Appels croisés :

def f1(x):if x==0:

print(1)f2(0)

else:print(2)f2(1)

def f2(x):if x==0:

print(3)f1(1)

else:print(4)

f1(0) # affiche 1 3 2 4

def f1(x):if x==0:

print(1)f2(0)

else:print(2)f2(1)

f1(0) # erreur d’exécution

def f2(x):if x==0:

print(3)f1(1)

else:print(4)


Portée des variables en Python

2 types de variables dans un programme Python :Variables locales à une fonctionVariables globales, accessibles depuis n’importe quel point ducode


Exemple

def f(x):res = 2 * x + 1return res

print(f(3))

L’instruction print(res) peut-elle s’exécuter correctement dans leprogramme principal ?


Exemple avec 2 variables locales de même nom

def f(x):res = 2 * x + 1return res

def g(x):res = 5 * x + 3return res

print(f(3))print(g(3))


Accès à une variable globale dans une fonction

Exemple :

def image(x):res = a * x + breturn res

a = 2b = 1print(image(3))


Priorité aux variables locales

def imageV2(x):a = 5b = 10res = a * x + breturn res

a = 2b = 1print(imageV2(3))print(a, b)


Impossible de modifier une variable globale dans unefonction

def h():vg = vg + 1return vg + 1

vg = 1print(h())print(vg)


... à moins d’utiliser le mot-clé global

Exemple :

def hV2():global vgvg = vg + 1return vg + 1

vg = 1print(hV2())print(vg)


Conseil : Utiliser les arguments pour modifier unevariable globale

def hV3(v):v = v + 1return v, vg + 1

vg = 1vg, val_retour = hV3(vg)print(val_retour)print(vg)


La trace d’appels : Traceback

def a():b()

def b():c()

def c():erreur()

a()

Traceback (most recent call last):File "tb.py", line 10, in <module>a()

File "tb.py", line 2, in ab()

File "tb.py", line 5, in bc()

File "tb.py", line 8, in cerror()

NameError: global name ’erreur’is not defined


Chaînes de caractères : Opérateur d’extraction

Quels seront les affichages?

>>> ch = ’Python’>>> print(ch[1:3])

>>> print(ch[2:2])

>>> print(ch[:4])

>>> print(ch[4:])

>>> print(ch[4:3])

>>> print(ch[::-1])


Chaînes de caractères : Opérateur de concaténation


>>> ch = ’Python’ + ’ pour tous’>>> print(ch)

>>> ch1 = ’Python’>>> ch2 = ’ pour tous’>>> ch = ch1 + ch2>>> print(ch)

>>> ch = ’p’ + ch[1:]>>> print(ch)


Chaînes de caractères : Opérateurs de duplication etd’appartenance


>>> ch = ’bon’>>> ch = ch*2>>> print(ch)

>>> print(’on’ in ch)

>>> print(’ont’ in ch)


Chaînes de caractères : Fonctions natives

len(ch) avec ch de type str renvoie le nombre de caractèresconstituant chlen(’La\nvie’) renvoie 6

car \n constitue un seul caractère qui représente le passage à lalignechr(i), avec i une valeur de type int, renvoie le caractèrecodé par la valeur iord(car), avec car une valeur de type str de longueur 1,renvoie la valeur de codage du caractère car

eval(ch), avec ch de type str, renvoie la valeur retournée parl’expression décrite par cheval(’5+7’) renvoie 12 de type int


Exercices

1 L’expression chr(ord(’A’) + 32) est-elle correcte?2 Quelle valeur est renvoyée?3 Après avoir exécutée ce bloc d’instructionschaine = ’’for c in ’ABCDEFGHIJKLMNOPQRSTUVWXYZ’:

chaine = chaine + chr(ord(c) + 32)

4 quelle valeur référence la variable chaine?5 quelle valeur est renvoyée par cette expressionchaine == eval(’chaine’)


Instruction POUR, séquence et tableau enpseudo-code

Instruction répétitive POUR

Pour répéter un nombre de fois fixé à l’avance un bloc d’instructionsdonné, on utilise une boucle POUR

POUR var ALLANT_DE val_debut A val_finDEBUTBloc d’instructionsFIN

var est une variable de type nombre (à déclarer)val_debut et val_fin sont des valeurs entières.Nombre d’itérations = val_fin - val_debut + 1Première itération : var reçoit val_debut, bloc d’instructions estexécuté puis var est automatiquement incrémentée de 1. Quandvar atteint la valeur val_fin, dernière itération !interdit de modifier la valeur de var dans le bloc d’instructions


La boucle POUR

Algorithme en pseudo-code affichant le carré de tous les entiersde 1 jusqu’à 10 :

ALGOVARIABLESi TYPE NOMBREcarre TYPE NOMBREDEBUT

POUR i ALLANT_DE 1 A 10DEBUT

carre <- i*iECRIRE carre

FINFIN


Séquences et tableaux

SéquenceSuite finie ordonnée de valeurs S = a1, . . . ,ap, . . . ,an

Longueur de SNombre n de valeurs contenues dans la séquence S (si n = 0 on diraque la séquence est vide)

Pour stocker ces n valeurs, on ne devra pas déclarer/initialiser nvariables distinctes. On va créer une et une seule variable quiréférencera ces n valeurs => nouveau type de données tableau


Type de données tableau à une dimension

Stocker une séquence S = a1, . . . ,ap, . . . ,an dans une variable detype tableau appelée T :

a1 a2 . . . ap . . . an

T [0] T [1] . . . T [p − 1] . . . T [n − 1]

Déclaration d’un tableau à une dimension en pseudo-code : 2étapes

1 déclarer une variable de type TABLEAU

2 dans le corps de l’algorithme, utiliser la fonction CREER_TABLEAUpour créer le tableau en spécifiant sa taille


Créer un tableau à une dimension

1 Déclaration du tableau et du type des valeurs de la séquenceVARIABLET TYPE TABLEAU DE NOMBREn TYPE NOMBRE...

2 Appel à la fonction CREER_TABLEAU dans l’algorithmeDEBUT...LIRE nT <- CREER_TABLEAU(n)...FIN


Accéder à une valeur stockée dans un tableau à unedimension

T[i] permet d’accéder à la valeur stockée à l’indice i du tableauunidimensionnel T, avec i compris entre 0 et n - 1

RemarqueOn peut créer des tableaux contenant des valeurs de tout type :TABLEAU de CHAINES, TABLEAU de BOOLEEN....


Stocker une séquence de n nombres dans un tableauà une dimension

VARIABLET TYPE TABLEAU DE NOMBREn, ind TYPE NOMBREDEBUTLIRE nT <- CREER_TABLEAU(n)ind <- 0TANT_QUE ind < n FAIRE

DEBUTLIRE T[ind]ind <- ind + 1FIN

FIN


Stocker une séquence de n nombres dans un tableauà une dimension avec une boucle POUR

VARIABLET TYPE TABLEAU DE NOMBREn, ind TYPE NOMBREDEBUTLIRE nT <- CREER_TABLEAU(n)POUR ind ALLANT de 0 à n-1

DEBUTLIRE T[ind]FIN

FIN


Opérateurs sur les tableaux : insertion

InsertionAjouter une valeur v à l’indice p-1. OBLIGE à décaler vers la droitetoutes les valeurs stockées précédemment de T[p-1] à T[n-1] (et ilfaut que le tableau soit suffisamment grand !)

a1 a2 . . . v ap . . . an . . .

T [0] T [1] . . . T [p − 1] T [p] . . . T [n]


Opérateurs sur les tableaux : insertion

Déclaration de tableaux SUFFISAMMENT GRAND :

VARIABLET TYPE TABLEAU DE NOMBREn TYPE NOMBREdim TYPE NOMBRE...

DEBUT...LIRE ndim <- n * 2T <- CREER_TABLEAU(dim)

taille : fonction qui retourne la dimension du tableau


Insérer v à l’indice p-1 de T

POUR i allant de 0 à n-pDEBUTT[n-i] <- T[n-i-1]FIN

T[p-1] <- v#mettre à jour la longueur de la séquencen <- n + 1


Opérateurs sur les tableaux : suppression

SuppressionSupprimer la valeur à l’indice p-1. OBLIGE à décaler vers la gauchetoutes les valeurs stockées précédemment de T[p] à T[n-1]

a1 a2 . . . ap+1 . . . an

T [0] T [1] . . . T [p − 1] . . . T [n − 2] T [n − 1]


Supprimer la valeur à l’indice p-1 de T

POUR i allant de p-1 à n-2DEBUTT[i] <- T[i+1]FIN

#mettre à jour la longueur de la séquencen <- n - 1

# pour afficher les valeurs stockées dans le tableauPOUR i allant de 0 à n-1

DEBUTECRIRE T[i]FIN


Quid d’une valeur de type str?

une valeur de type str est une séquencemais une valeur de type str n’est pas stockée dans un tableau(on ne peut pas appliquer les opérateurs classiques : une valeurde type str est non modifiable)dans langages de programmation courants, le type tableau existe,pas en Python !


Tableau à deux dimensions

T [0][0] T [0][1] . . . T [0][j] . . . T [0][m − 1]. . . . . . . . . . . . . . . . . .

T [i][0] T [i][1] . . . T [i][j] . . . T [i][m − 1]. . . . . . . . . . . . . . . . . .

T [n − 1][0] T [n − 1][1] . . . T [n − 1][j] . . . T [n − 1][m − 1]

Déclaration d’un tableau à deux dimensions en pseudo-code :

VARIABLET TYPE TABLEAU DE NOMBREn, m TYPE NOMBREDEBUTLIRE nLIRE mT <- CREER_TABLEAU(n, m)FIN


Initialiser un tableau à 2 dimensions

VARIABLET TYPE TABLEAU DE NOMBREn, m, i, j TYPE NOMBREDEBUTLIRE nLIRE mT <- CREER_TABLEAU(n, m)POUR i ALLANT_DE 0 A n-1

DEBUTPOUR j ALLANT_DE 0 A m-1

DEBUTLIRE T[i][j]FIN

FIN


Algorithme en pseudo-code permettant de remplacer chaquenombre d’un tableau par son cube :

ALGOVARIABLESi, taille TYPE NOMBREcube TYPE NOMBRET TYPE TABLEAU DE NOMBREDEBUT

LIRE tailleT <- CREER_TABLEAU(taille)POUR i ALLANT DE 0 A (taille-1)

DEBUTLIRE T[i]

FINPOUR i ALLANT_DE 0 A (taille-1)

DEBUTcube <- T[i]*T[i]*T[i]T[i] <- cube

FINFIN


Exercice

Écrire en pseudo-code un algorithme qui demande à l’utilisateur deremplir un tableau de chaînes de caractères (en lui demandant aupréalable sa taille), lui demande ensuite un élément x , puis déterminela dernière position (entre 1 et n) de cet élément dans le tableau.


Documents

Informatique et Programmation Python Extraits choisis du ...gabrel/DOCUMENTS/... · Plan du cours 1 Algorithmes et programmation : principaux concepts et instructions élémentaires