Université de Yaoundé I University of Yaounde I
Faculté des Sciences Faculty of Science
Département d’Informatique
INF242, Syntaxe de Python, 12 Avril 2024
Docteur MESSI NGUELÉ Thomas, Chargé de Cours
TP1 : Tris et recherche
1. Écrire une fonction python qui fait la recherche d’un élement dans un liste d’éléments.
La fonction retourne l’index de l’élement lorsqu’il est présent et -1 sinon.
2. Écrire des fonctions qui permettent de faire les tris suivants : tri insertion, tri bulles, tri
fusion, tri bitonique.
3. Écrire une fonction qui permet de faire la recherche dichotomique.
4. Écrire une fonction main qui permet de tester toutes ces fonctions.
TP2 : Résolution des Systèmes Linéaires Dans cet exercice, on voudrait réaliser un
outil permettant de faire la résolution des systèmes linéaires. On suppose qu’une matrice est
représentée comme un tableau à deux dimensions. Votre code sera dans un fichier nommé
premierNom_matricule_systeme_lineaire.py.
1. Stockage des éléments. Écrire une fonction qui demande à l’utilisateur le nombre de
ligne n et le nombre de colonne m d’une matrice et ensuite stocke les élements de cette
matrice en les lisant à partir du clavier.
2. Nature d’une matrice. Écrire fonction qui détermine la nature d’une matrice :
(a) triangulaire supérieure,
(b) triangulaire inférieure,
(c) diagonale
(d) ou quelconque.
3. Affichage des éléments.
(a) Écrire une fonction permettant d’afficher ligne par ligne les élements d’une matrice en
respectant bien sa nature (triangualire supérieure, triangulaire inférieure, diagonale,
quelconque).
(b) Écrire une fonction qui étant donnés une matrice A et un vecteur b renseignés par
l’utilisateur affiche le système sous la forme AX=b.
4. Élimination de Gauss. Dans l’algorithme de Gauss pour résoudre un système linéaire
Ax = b, on commence par transformer ce système linéaire en un système triangulaire
équivalent, par combinaison de lignes. Ensuite on résout le système triangulaire supé-
rieur. Dans la suite on suppose, pour simplifier les notations, que b correspond à la
(n + 1)eme colonne de A.
(a) Compléter l’algorithme d’élimination ci-dessous en supposant qu’il n’y a pas de pivot
nul :
INF242 Page 1/4 Syntaxe de Python, Avril 2024
Pour k := ... à ... faire
{Elimination de ak+1,k,... , ank en utilisant akk }
Pour i := ... à ... faire
{Elimination de ai,k }
début
...
Pour j := ... à ... faire ...
fin
(b) Écrire une fonction permettant de réaliser l’algorithme d’élimination présenté à la
question 4a
5. Résolution du système.
(a) Compléter l’algorithme ci-dessous pour la résolution d’un système triangulaire obtenu
à la question précédente.
xn := ... ;
Pour i := ... à ... faire
{Calcul de xi }
début
xi := ... ;
Pour j := ... à ... faire xi := xi - ... ;
xi := ... ;
fin
(b) Écrire les autres fonctions permettant de resoudre le systhème dans le cas où la
matrice est :
i. triangulaire inférieure (se servir de l’algorithme à la question 5a),
ii. triangulaire supérieure,
iii. diagonale.
6. main. Écrire un main permettant à l’utilisateur de résoudre un système linéaire. Le
programme commencera par déterminer la nature de la matrice :
(a) Dans le cas où la matrice entrée par l’utilisateur est une matrice particulière (diago-
nale, triangulaire supérieure ou triangulaire inférieure) le système sera directement
resolu en se servant de l’une des méthodes de la question 5.
(b) Dans le cas où la matrice entrée par l’utilisateur est une matrice quelconque, le
programme fera d’abord l’élimination de Gauss décrite à la question 4 avant de
resoudre le système en se servant de l’une des méthodes de la question 5.
Le programme rappellera alors à l’utilisateur le système à resoudre (par appel de la
méthode de la question 3b) avant d’afficher le résultat.
TP3 : Expressions bien formées. On voudrait écrire un programme permettant de dire
si les expressions constituées de parenthèses, de crochets et d’accolades sont bien formées :
l’algorithme parcourt la chaine et détermine s’il y a équilibre (et dans un bon ordre) entre les
parenthèses ouvrantes "(" et fermantes ")", crochets ouvrants "[" et fermants "]", accolades
ouvrantes "{" et fermantes "}".
Exemple :
— L’expression (1 + 2)) + 3 est mal formée car il y a une parenthèse fermante de plus.
— L’expression {[(1 + 2) + 3] + 13} est bien formée.
INF242 Page 2/4 Syntaxe de Python, Avril 2024
Votre code sera dans un fichier nommé premierNom_matricule_verification_expressions.py.
1. Principe de résolution. Dire (sur papier et en au plus 5 lines) comment un tel pro-
gramme peut être écrit en se servant de la structure de données pile.
2. Structure de données.
(a) Proposer une structure de données pile permettant de résoudre le problème ainsi
posé. On suppose que la pile est implémentée avec un tableau.
(b) Donner les primitives de base permettant de manipuler cette pile (initialisation, tester
que la pile est vide, tester que la pile est pleine, empiler, dépiler).
3. Programme de vérification.
(a) Écrire (sur papier) l’algorithme permettant de vérifier les expressions bien formées.
(b) Écrire la fonction python correspondant à cet algorithme. (Diviser cet algorithme en
plusieurs sous-fonctions ou sous-procédures si nécessaire).
(c) Écrire le programme principale qui lit l’expression (chaine de caractères) entrée par
l’utilisateur et vérifie si elle est bien formée.
TP4 : Comptage des chaines de caractères. L’objectif de ce TP est de compter le nombre
d’occurence d’une chaine dans un texte.
1. Rappeler le schéma général d’un algorithme de recherche
2. (a) Rappeler l’algorithme de base pour la recherche d’une valeur Val dans un vecteur
V(1..n)
(b) Écrire cet algorithme en Python
3. Montrer que la comparaison pour savoir si deux vecteurs V(1..n) et W(1..n) sont égaux,
est un problème de recherche que l’on précisera
4. (a) Donner l’algorithme de la question 3
(b) Écrire cet algorithme en python
5. Lorsque les éléments de V et W sont tirés au hasard, quel est le nombre de comparaisons
de l’algorithme de la question 3 :
(a) Dans le cas le plus favorable (au sens du nombre de comparaisons) ?
(b) Dans le cas le plus défavorable (au sens du nombre de comparaisons) ?
(c) En moyenne (au sens du nombre de comparaisons) ?
6. (a) Donner l’algorithme de recherche des occurrences du mot M(1..m) dans un texte
T(1..t), avec t > m. N.B. On pourra invoquer un algorithme déjà présenté
(b) Écrire cet algorithme en Python
7. Lorsque les éléments de T(1..t) et M(1..m) sont tirés au hasard, quel est le nombre de
comparaisons de l’algorithme de la question 6 :
(a) Dans le cas le plus favorable ?
(b) Dans le cas le plus défavorable ?
(c) En moyenne ?
8. Expliquer le principe de solution du problème de la question 6 à l’aide d’un automate
9. Qu’espère-t-on avec cette approche par automate ?
10. Quel est le coût supplémentaire à payer pour mettre en œuvre cette solution ?
11. Quelle est la condition pour que ce coût soit acceptable ?
12. Donner l’automate pour le cas particulier où le mot est ‘aabbaab’ et T est un texte sur
l’alphabet {a,b}.
INF242 Page 3/4 Syntaxe de Python, Avril 2024
Consignes : Le TP sera réalisé en langage Python. On vous demande d’écrire deux versions de
la fonction qui calcule le nombre d’occurence d’un mot dans un texte (avec automate et sans au-
tomate). Votre code sera dans un fichier nommé premierNom_matricule_comptage_chaines.py.
................ Bon Courage ! ...............
INF242 Page 4/4 Syntaxe de Python, Avril 2024
