Introduction à l’algorithmique et à la programmation en Python

Un algorithme est une séquence d’instructions non ambigüe. Il est destiné à être exécuté par une machine capable de comprendre ces instructions en vu de résoudre un problème.

Un algorithme prend une, aucune ou plusieurs entrées et renvoie une sortie. Les entrées sont les paramètres inconnus et variables du problème que l’on cherche à résoudre. La sortie est le résultat du calcul de l’algorithme, répondant au problème posé.

Un exemple d’algorithme pour ranger ses chaussettes propres.

Algorithme Rangement de chaussette
Entrées : Un ensemble de chaussettes propres \(\cal C\)
Sortie : Un tiroir de chausettes par paire et un bac de chaussettes solitaires

soit \(\cal T\) un tiroir vide, \(\cal B\) un bac vide
tant que il a une chaussette, \(c\) dans \(\cal T\) faire
\(~~~~\) si \(c\) a sa jumelle, \(c'\) dans \(\cal B\) alors
\(~~~~\) \(~~~~\) regrouper \(c\) et \(c'\) dans un paire \(p\)
\(~~~~\) \(~~~~\) ranger \(p\) dans \(\cal T\)
\(~~~~\) sinon
\(~~~~\) \(~~~~\) mettre \(c\) dans \(\cal B\)
\(~~~~\) fin du si
fin du tant que
renvoyer \(\cal T\) et \(\cal B\)

Un ordinateur est modélisé par une unité de calcul et une mémoire.
L’unité de calcul exécute les instructions d’un algorithme.
Les instructions une fois exécutée on pour but d’agir sur la mémoire de l’ordinateur.

Un programme informatique est une séquence d’instructions destinée à être exécutée par un ordinateur et écrite dans un langage de programmation, c’est à dire un langage qui peut être interprété par l’ordinateur.

L’opération consistant à passer d’un algorithme (abstrait) à un programme informatique (concret) s’appelle l’implémentation.

On utilisera le langage de programmation Python dans ce cours.
Voici une implémentation en Python de l’algorithme ci-dessus.

  def ranger_chaussettes(C) :
      T, B = {}, {}
      for c in C :
          c_paire = paire(c)
          if c_paire in B :
              B.remove(c_paire)
              T.append((c,c_paire))
          else :
              B.append(c)
      return (T,B)

L’objectif du cours d’informatique est double : - Savoir concevoir, analyser et valider un algorithme. - Savoir implémenter un algorithme et tester votre implémentation.

Objets : Les objets en Python constitue les données manipulables par les programmes. Les objets standars sont les entiers, les flottants (nombres réels), les booléens (vrai ou faux), les chaînes de caractère (texte). Respectivement en Python ils sont noté int, float, bool et str.

Les entiers s’écrivent naturellement en Python et supportent les opérations arithmétiques suivantes :

  10 + 2, 16 - 4, 3 * 4, 25 // 2, 112 % 25, 12 ** 12

Les nombres réels sont représentés par des objets de type flottant en Jupyter-Python.

On peut définir les objets flottant comme ceci :

  12.2, -12.5, 12.,  12.12e12, 12.12e-12

Les flottants supportent les mêmes opérations arithmétiques que les entiers.
À noter la différence de notation pour la division réelle.

  6. + 6., 6. + 6, 6 * 2., 25 / 2, 12. ** 2

Précision des flottants : 16 chiffres significatifs

  1234567890.12345678 - 1234567890.1234567

0.0

Une variable est un nom que l’on associe à un objet particulier.

  variable = 12

Le processus d’association d’une variable à un objet est appelé affectation.

  variable + 21

33

Lors de l’évaluation d’une expression la variable est remplacée par l’objet qui lui est associé

L’objet n’est pas modifié par l’opération précédente. La variable est donc toujours associée au même objet.

  variable

12

Lors d’une affectation, la partie droite de l’affectation est d’abord évaluée, puis le résultat est associée à la variable

L’implémentation d’un algorithme en Python prend la forme d’une fonction.
Comme en mathématique une fonction en python prend des paramètres qui sont les entrées de la fonction.
Comme en mathématique une fonction en python renvoie une sortie.

  def fonction(x,y) :
      return x * x + y * y

Les entrées de la fonction sont des variables qui ne sont pas associées à un objet un particulier lors de la définition de la fonction.

Lors de l’appel de la fonction les entrées sont définies et les inconnues seront associées au début de la fonction aux objets passés en entrée de la fonction.

  fonction(4,6)

52

  def autre_fonction(s : str, y : int) -> str :
      variable = s + ' - '
      variable = variable * (y - 1)
      variable = variable + s
      return variable

  autre_fonction("Nadine", 4)

Nadine - Nadine - Nadine - Nadine

if condition1 :
    # Block d'instruction 1
elif condition2 :
    # Block d'instruction 2
else :
    # Block d'instruction 3

Les blocs elif et else sont optionnels.
Les blocs elif peuvent être repétés autant de fois que voulu.

Les conditions booléennes peuvent être : la valeur d’une variable booléenne, le résultat d’une inégalité, la combinaison de conditions plus simples à l’aide des connecteurs logiques and, or et not.

Les objets booléens de base sont True et False. Les inégalités renvoie l’une de ces deux valeurs :

  1 < 2, 1 > 2, 1 <= 2, 1 >= 2, 1 == 2, 1 != 2

Il existe plusieurs types de boucles, mais toutes peuvent se ramener à la boucle tant que (while) décrite ci-dessous.

while condition :
    # Block d'instruction
    ...
#Suite du programme

La longueur d’une séquence s’obtient grâce à la fonction len.

  # Longueur
  len("Nadine"), len((1,2,3)), len([1,2,3,4,5]), len(range(12))

On peut créer une séquence vide. Sa longueur est 0.

  "", (), [], range(0)

On accède à chaque élément d’une séquence grâce à son indice. Le premier indice d’une séquence est 0 et le dernier est n-1 avec n la taille de la séquence.

  # Accès
  "Nadine"[0], (1,2,3)[2], [12.3,21.12,144.0][1], [0,0,0,1][2], range(2,4)[0], range(2,4)[1]

Attention L’accès doit être fait sur un indice entre 0 et n-1

  (1,2,3)[3]

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Input In [15], in <cell line: 1>()
----> 1 (1,2,3)[3]

IndexError: tuple index out of range

La concatenation consiste à mettre deux séquence l’une à la suite de l’autre.

  "Nadine" + "Cuisine", (4,2,3) + (4,5,6), [12,12,12] + [21,21,21]

Attention : La concatenation ne fonctionne pas sur les générateurs.

  range(2) + range(4)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Input In [17], in <cell line: 1>()
----> 1 range(2) + range(4)

TypeError: unsupported operand type(s) for +: 'range' and 'range'

La multiplication par un entier permet de concatener plusieurs fois la chaîne avec elle même.

  "Nadine"*3, (1,2) * 4, [0] * 12

  list("Nadine"), tuple("Nadine"), tuple([12,22,32]), list((12,22,32))

  list(range(2,20,5))

  str([1,2,5])

Beaucoup d’algorithmes s’appuie sur un parcours de la séquence.
Un parcours consiste à réaliser un block d’instructions sur chaque élément de la structure (ici la séquence).
L’ordre dans lequel sont visités les éléments peut varier selon le parcours.
Pour les séquences il s’agit surtout de parcourir selon les indices croissants (de \(0\) à \(n-1\)) ou décroissants (de \(n-1\) à \(0\)).

Les algorithmes de parcours de séquences se construisent avec une boucle tant que comme suit :

\(i \gets 0\)
\(n \gets \texttt{longueur}(S)\)
tant que i < n faire
\(~~~~\dots\) \(~~~~\) Instructions manipulants S[i]
\(~~~~\dots\) \(~~~~i \gets i+1\)
fin tant que

Un caractère est représenté par l’ordinateur par un nombre. Il existe différente manière d’associer un caractère à un nombre. C’est ce qu’on appelle l’encodage.

Le codage ASCII permet de coder 255 caractères. Le codage utf-8 permet d’en coder \(2^{21}\) et donc de coder d’autres alphabets que l’alphabet latin.

On peut déclarer une chaîne de caractère :

• entre guillemets doubles (peut contenir des guillemets simples) : "Nadine l'aristocrate"
• entre guillemets simples (peut contenir des guillemets doubles): 'Nadine le "vélociraptor"'

• entre guillemets triples (peut contenir des retours à la ligne):

    """
    Nadine l'aristocrate
    Nadine le "vélociraptor"
    """
  

Si besoin on peut échapper le caractère " pour l’insérer dans une chaîne de caractère.

  "Nad'i\"ne"

  print("Nad'i\"ne")

Un saut de ligne est représenté par le caractère spécial '\n'

  "Nadine" + "\n" + "Nadine"

  print("Nadine" + "\n" + "Nadine")

En Jupyter-Python on peut obtenir le code ASCII d’un caractère ou obtenir le caractère à partir de son code ASCII :

  ord('N'), ord('a'), ord('D'), chr(105), chr(78), chr(101), chr(9), chr(49), chr(50)

On peut vérifier en Python si une séquence est vide grâce au mot clé not.

not [], not (), not "", not range(0)

not [12,12], not (1), not "Nadine", not range(12)

On peut accéder en Python à un élément en précisant son indice S[i]. Si i est un nombre négatif, l’accès se fait à partir de la fin de la liste, i.e si \(S\) est une séquence de longueur \(n\) et \(k\) est un nombre positif :

\[S[-k] = S[n-k]\]

"Nadine"[-3], (1,2,3)[-1], [8,12,12,45,23,45][-6], range(12)[-1]

Les indices valides pour l’accès en Python sur une séquence \(S\) de taille \(n\) sont donc les indices :

\[-n, -(n-1), \dots, 0, \dots n-1\]

Une sous séquence d’une séquence \(S\) est une séquence \(T\) d’éléments consécutifs de \(S\).

Par exemple :

• [12,67,89] est une sous séquence de [1,4,7,12,67,89,67,90]
• (1,2) est une sous séquence de (1,2,3,4)
• "din" est une sous séquence de "Nadine"

• Une sous séquence d’une chaîne de caractères est appelée sous chaîne.
• La séquence vide et la séquence elle-même sont toujours des sous séquence d’une séquence.

Une séquence extraite d’une séquence \(S\) est une séquence \(T\) d’éléments de \(S\), ordonnés comme dans \(S\).

Par exemple :

• [4,12,89,67] est une séquence extraite de [1,4,7,12,67,89,67,90]
• (1,4) est une séquence extraite de (1,2,3,4)
• "aie" est une séquence extraite de "Nadine"

• Une sous séquence d’une séquence est une séquence extraite.

Les slices en Python permettent d’extraire une séquence depuis une séquence de base. Toutefois les extractions ne peuvent être faîtes que de manière régulières. Il est possible d’extraire une séquence en précisant :

• l’indice de départ de l’extraction, i,
• l’indice de fin de l’extraction, j,
• le pas qui sépare chaque éléments gardé dans l’extraction, p.

La syntaxe est la suivante :

S[i:j:p]

"NadineNadineNadine"[4:18:3], (1,2,3,4,5,6,7)[0:7:2]

[12,12,12,21,21,21][2:4:2], range(12)[2:5:2]

Voici quelques exemples intéressants :

"Nadine"[-1:-7:-1], (1,2,3,4,5,6,7,8,9)[7:1:-2]

[12,12,12,12][3:2:1], [12,21,12,21,12,21][2:-2:1]

A noter que :

• Dans \(S[i:j:p]\), \(S[i]\) est dans l’extraction, \(S[j]\) n’est pas dans l’extraction.
• \(S[i:i] = []\)
• \(S[i:j] = S[i:j:] = S[i:j:1]\)
• Si \(i\) est omis, il est considéré comme étant \(0\) :
  • \(S[:j:p] = S[0:j:p]\), \(S[:j] = S[0:j] = S[0:j:1]\)
• Si \(j\) est omis, il est considéré comme étant \(n\) la taille de la séquence :
  • \(S[i::p] = S[i:n:p]\), \(S[i:] = S[i:n] = S[0:n:1]\)
• On en déduit que \(S[:] = S[::] = S[0:n:1]\) est une copie de \(S\).

L’appartenance d’un élément à une séquence peut être testée par la condition suivante :

'c' in "Nadine", 4 in [12,12,4,4,6,4,9], 3 in (1,2,123), 12 in range(2,12,2)

L’appartenance à une séquence vide est toujours fausse :

'a' in "", 0 in []

Exemple :

def voyelle(c) :
    """
    Entrées : un caractère c
    Sortie : le code ascii de c ssi c est une voyelle, -1 sinon
    """
    code = -1
    if c in "AEIOUYaeiouy" :
        code = ord(c)
    return code

voyelle('N'), voyelle('a'), voyelle('d')

voyelle('i'), voyelle('n'), voyelle('e')

Le mot clé in permet de tester si une chaîne de caractère est une sous chaîne d’une autre. On dira que la sous chaîne appartient à l’autre chaîne.

'ab' in "Nadine", "ab" in "Baobab"

Attention cela ne fonctionne pas sur les autres séquences.

Exemple :

def nadine(s) :
    """
    Entrées : une chaîne s
    Sortie : "Nadine" si "Nadine est dans s sinon "Cuisine"
    """
    sortie = "Cuisine"
    if "Nadine" in s :
        sortie = "Nadine"
    return sortie

nadine("Baobab"), nadine("Nadine")

nadine("Nadine sous le Baobab"), nadine("Le Baobab sous Nadi...")

Les objets Python se séparent en deux catégories :

• les objets mutable peuvent être modifiés et évoluer dans l’exécution du programme.
• les objets immutables ne peuvent pas être modifiés et restent constant tout au long de l’exécution.

Les listes Python sont des objets mutables. On peut :

• modifier l’élément à un indice \(i\) donné : l[i] = x
• ajouter un élément à la fin de la liste : l.append(x)

• supprimer un élément à la fin de la liste et le renvoyer : x = l.pop()

  L = [1,2,3]
  L[1] = 12
  x = L.pop()
  L[0] = x
  L.append(144)
  L
  

  3

  12

  144

Les opérations ci-dessus sont des requis du programme. Il en existe d’autres :

• ajouter un élément dans la liste à l’index \(i\) : l.insert(i,x)
• supprimer un élément à l’indice \(i\) de la liste et le renvoyer : l.pop(i)

• modifier une sous-séquence de la liste : l[i:j] = l1

  L = [1,2,3,4,5]
  L.insert(1,12)
  x = L.pop(0)
  L[2:4] = [x*33,x*44,x*55,x*66]
  L
  

  12

  2

  33

  44

  55

  66

  5

La mutabilité concerne les objets et non pas les variables.

On peut modifier une variable associée à un objet immutable :

s = (1,2)
s = (2,3)
s

s = (1,2)
s[0] = 2
s[1] = 3

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Input In [48], in <cell line: 2>()
      1 s = (1,2)
----> 2 s[0] = 2
      3 s[1] = 3

TypeError: 'tuple' object does not support item assignment

Attention quand deux variables sont associées au même objet mutable.

l1 = [1,2,3]
l2 = [1,2,3] # l2 est associée à un objet différent de l1
l1[1] = 12
l1, l2

l1 = [1,2,3]
l2 = l1 # l2 est associée au même objet que l1
l1[1] = 12
l1, l2

Attention en particulier au cas des fonctions.

   def modif(l) :
       if not l :
           return None
       l[0] = 12
       return None

   t = [1,2,3]
   modif(t)
   t

Attention à la copie de liste. De la même manière que l1 = l2 associe à l1 et l2 le même objet, lors de la copie de liste l1[i] = l2[i] associe à l1[i] et l2[i] les mêmes objets :

l1 = [ [1,1,1], [2,2,2], [3,3,3] ]
l2 = [ None ] * 3
for i in range(3) :
    l2[i] = l1[i]
l1,l2

l1[0][1] = 12
l1,l2

l1.append(l1[1])
l1

l1[1][2] = 144
l1

Le résultat est le même pour l2.append(l1[i]), l2 = l2 + [ l1[i] ], l2 = [] + l1, l2 = [ l1[i] for i in range(3) ], l2 = l1[:], …

On retrouve ce même phénomène avec la multiplication :

l1 = [ [0,0,0] ] * 3
l1

l1[0][1] = 2
l1

def nouvelle_matrice(n,m) :
    """
    Entrées : n et m deux entiers positifs
    Sortie : une matrice n x m initialement vide (remplie de None)
    """
    t = []
    for i in range(n) :
        t.append([ None ] * m )
    return t

Une version courte pour la création de matrice avec un schéma de compréhension :

[ [ None ] * m for i in range(n) ]

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Input In [62], in <cell line: 1>()
----> 1 [ [ None ] * m for i in range(n) ]

NameError: name 'n' is not defined

Attention le code ci-dessous ne crée pas une matrice valide. c.f la section Mutabilité, Variable et Copie

t = [ [ None ] * m ] * n

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Input In [63], in <cell line: 1>()
----> 1 t = [ [ None ] * m ] * n

NameError: name 'm' is not defined

On peut accéder à l’élément à la ligne \(i\), colonne \(j\) de la matrice grâce à l’instruction m[i][j], accès à l’élément d’indice j de la liste à l’indice i de la matrice.

La ligne \(i\) de la matrice est accessible grâce à l’instruction m[i].

La colonne \(j\) est plus difficilement accessible. Il faut l’extraire de la matrice, par exemple avec le schéma de compréhension suivant :

# j fixé et n nombre de lignes
col = [ t[i][j] for i in range(n) ]

Les dimensions de la matrices sont obtenue comme ceci :

1. Nombre de ligne : len(t).
2. Si le nombre de ligne n’est pas nul, Nombre de colonne : len(t[0]).