Directives TP Algorithmique et Programmation

Le cours est organisé en 10 chapitres. La dernière version de mes notes a été victime d’une attaque.
Des fautes ont été parsemées dans les notes et dans le code proposé dans les dites notes. Je n’ai
donc pas remis cette version des notes aux étudiants. Je leur ai plutôt demandé de s’appuyer sur les
notes de l’année académique passée. Axel, le CP fournira cette version de notes à monsieur Mobisa.

Le chapitre premier est une introduction générale du cours. Le chapitre 2 donne un rappel de
python. Le chapitre 3 introduit les fondements mathématiques de l’algorithmique. Le chapitre 4
parle de la récursivité qui est un concept clé en algorithmique. Le chapitre 5 aborde les tableaux
comme structures des données de base. Le chapitre 6 présente les structures de données piles et
files d’attentes. Le chapitre 7 aborde les structures de données listes chainées. Les chapitres 8 et 9
qui portent sur les arbres et les graphes n’ont pas été abordés au cours de cette année académique.
Le chapitre 10 présente les conclusions et perspectives du cours.

Au cours des TP, les activités porteront sur les concepts de programmation, la révision de Python,
les fondements mathématiques de l’algorithmique, la conception et l’évaluation des algorithmes,
ainsi que la conception et la mise au point des structures des données.
 Fiche 1: Les concepts de Programmation et la révision de Python

Avant de démarrer concrètement cette partie des travaux pratiques, il faut s’assurer que chaque
étudiant a installé sur son ordinateur un Environnement de Développement Intégré (EDI). Moi
j’utilise IDLE, mais chaque étudiant peut utiliser l’EDI qui lui convient. Le seul inconvénient est qu’il
ne pourra recevoir de l’aide que sur l’EDI maitrisé par monsieur Mobisa. Il y a lieu que monsieur
Mobisa convienne d'un arrangement à ce propos avec les étudiants qui comptent sur son aide à ce
sujet. Quelques EDIs usuels: IDLE, PYCHARM, SUBLIME TEXT, ATOM, VISUAL STUDIO CODE, THONNY,
SPYDER, VIM, ….

Il faudra expliquer les concepts d'assembleur, d'interpréteur et de compilateur et situer Python par
rapport à ces concepts.

Il faudra également faire un tour d'horizon de Python et Expliquer chacun de concepts suivants: Les
variables, les objets, les fonctions, les classes, les méthodes, les structures de contrôles, les boucles,
les séquences (list, tuple, str, dict, ...), les fichiers, les exceptions, les modules, les opérateurs et leur
surcharge, et les structures de données.

Tout ce qui précède se fait en deux heures maximum.

Projet 1.

1. Ecrire une classe de base valable pour toute forme géométrique. Pour chaque forme géométrique
nous nous intéressons au calcul du périmètre et de la surface.

2. Ecrire trois classes qui héritent de la classe de base :

 La classe des rectangles

 La classe des cercles
 La classe des triangles

3. Dans la réalisation du projet, vous commencerez par donner un diagramme de classes en "Unified
Modeling Language (UML)". Ensuite vous passez à l'implémentation des classes reprises dans votre
diagramme.

4. Nous voudrions maintenant avoir une classe des carrés et une classe des triangles rectangles.
Comment le faire ? Mettez à jour le diagramme des classes du projet et implémentez ces deux
nouvelles classes si cela est nécessaire.

5. Ecrire une classe qui exploite les classes des formes géométriques pour fournir le périmètre et la
surface d’une forme géométrique (bien évidemment l’on se limite à celles traitées dans le cadre de
notre projet).

6. Combien de classes avez-vous développées dans le cadre de ce projet? Est-ce que le nombre de
classes est le minimum possible? Justifiez votre réponse.

7. Organisez les classes développées en un module et mettez en place une batterie tests pour ce
module.

8. En dehors de l’héritage, quel autre concept de la technologie orientée objet pourriez-vous utiliser
pour réaliser le projet depuis son point de départ? Refaites le projet conformément à cet autre
concept. Vous commencerez par fournir un diagramme de classes UML pour cette deuxième
conception avant de passer à son implémentation.
9. Vous disposez de deux implémentations différentes du projet. Evaluez le temps d’exécution des
différentes méthodes dans les deux cas. S’appuyer ici sur la notation asymptotique pour comparer
les temps d’exécution des différentes méthodes.

10. Si vous deviez choisir entre les deux solutions laquelle choisiriez-vous ? Justifier votre réponse.

Le travail relatif aux questions 1 à 10 se fait sous la supervision de l'assistant et avec son aide. Il se
fait en 8 heures maximum.

Devoir (Le devoir devra être fait par les étudiants eux-mêmes sans l'aide de l'assistant)

Les étudiants s’organisent en groupes. Trois étudiants maximum par groupe.

Ils rédigent un document "pdf" présentant les réponses apportées aux différentes questions posées
dans ce projet et transmettent le fichier par courrier électronique à monsieur Mobisa et à moi. Dans
la mesure ou il y a trois étudiants par groupe, les étudiants devront opérer des choix ou fusionner
leurs propositions de réponse pour ne retenir dans le document de devoir que la meilleure solution
(prémisses du travail en équipe). La liste des groupes doit nous être également transmise. Monsieur
Mobisa fixera les délais de transmission.

Courriers électroniques de l'assistant et du Professeur

gaelmobisa@gmail.com; paul.olamba@unikin.ac.cd; paul_olamba_kalonda@yahoo.com;

Il se pourrait que monsieur Mobisa vous indique une plateforme sur laquelle vous pourrez créer
votre compte et y loger vos programmes et autres données. Dans ce cas chaque étudiant aura son
compte et chaque groupe de trois étudiants aura un compte de groupe. Il ne sera pas nécessaire
d'envoyer les devoirs par courriers électronique, il suffira juste de les déposer sur votre compte de
groupe.

Bon travail
 Fiche 2: Les fondements mathématiques de l’algorithmique et l’évaluation des algorithmes

Répondre aux questions suivantes (révision de la matière):

1. Qu'est-ce qu'un algorithme?

2. Qu'est-ce qu'un algorithme efficace?

3. Que pouvez-vous dire à propos de l'efficacité d'un algorithme?

4. Citer quelques unes des techniques de conception d'un algorithme?

5. Commentez en quelques phrases les techniques de conception des algorithmes suivantes: la

méthode de la force brute, la méthode gloutonne, la méthode du diviser pour régner, la méthode
probabiliste, la méthode de la programmation dynamique.

6. Qu'est-ce qu'un pseudo-code? Qu'est-ce qu'un ordinogramme? De quelle autre façon peut-on
présenter un algorithme?

7. Pour quelles raisons une équipe de développeurs de logiciels choisit-elle de représenter les
algorithmes par du pseudo-code, des organigrammes ou des bouts de code.

8. En général pour un problème donné, on peut développer plusieurs algorithmes. Comment

identifier le meilleur algorithme de cet ensemble?

8. En quoi consiste l'analyse d'un algorithme?

9. Quelles sont les deux méthodes d'analyse d'un algorithme?

10. Quels sont les inconvénients de la méthode expérimentale?

11. En quoi consiste la méthode des opérations primitives?

12. Qu'est-ce que la complexité d'un algorithme?

13. En quoi consiste la notation asymptotique?

14. Quelles sont les fonctions qui apparaissent le plus lors de l'analyse théorique des algorithmes?

15. Quel est l'algorithme le plus efficace parmi un ensemble d'algorithmes permettant de résoudre
un problème

16. Pour évaluer expérimentalement un algorithme on doit l'implémenter et lui fournir des entrées
différentes question de mesurer le temps d'exécution correspondant à chaque entrée. C'est en
dessinant la courbe du temps d'exécution en fonction de la taille de l'entrée que l'on peut identifier
la fonction correspondant à l'évolution du temps d'exécution en fonction de la taille d'entrée. La
notion de la taille d'une entrée est très importante. Pourriez-vous la définir en quelques mots et
donner quelques exemples de taille d'entrée pour des problèmes simples.

17. Dans l'analyse d'un algorithme on distingue généralement le cas le plus défavorable, le cas le plus
favorable et le cas moyen (probabiliste). Expliquez en quoi consiste chaque cas. Pourquoi le cas le
plus défavorable a une importance particulière?

18. Définir en quelques mots le concept de récursivité.

19. En quoi consistent la récursivité linéaire, la récursivité binaire et la récursivité multiple.

20. De quelle façon un problème récursif doit-il pouvoir se définir? Donnez un exemple.

Quelques exercices

1. Le nombre d'opérations primitives exécutées par les algorithmes A et B est (50 n log n) et (45 n 2),
respectivement. Déterminez n0 tel que A soit meilleur que B, pour tout n ≥ n0.

2. Le nombre d'opérations primitives exécutées par les algorithmes A et B est (140 n 2) et

(29 n3), respectivement. Déterminez n0 tel que A soit meilleur que B pour tout n ≥ n0. Utiliser Matlab
ou Excel pour montrer les évolutions des temps d'exécution des algorithmes A et B dans un
graphique.

3. Montrer que les deux énoncés suivants sont équivalents :

(a) Le temps d'exécution de l'algorithme A est toujours O(f(n)).
(b) Dans le pire des cas, le temps d'exécution de l'algorithme A est O(f(n)).

4. Montrer que si d(n) vaut O(f(n)), alors (a x d(n)) vaut O(f(n)), pour toute constante
a > 0.

5. Montrer que si d(n) vaut O(f(n)) et e(n) vaut O(g(n)), alors le produit d(n)e(n)
est O(f(n)g(n)).

6. Montrer que si d(n) vaut O(f(n)) et e(n) vaut O(g(n)), alors d(n)+e(n) vaut
O(f(n)+g(n)).

7. Montrer que si d(n) est O(f(n)) et e(n) est O(g(n)), alors d(n)−e(n) n'est pas
nécessairement O(f(n)−g(n)).

8. Montrer que si d(n) est O(f(n)) et f (n) est O(g(n)), alors d(n) est O(g(n)).

9. Étant donné une séquence de n éléments S, l'algorithme D appelle l'algorithme E sur chaque
élément S[i]. L'algorithme E s'exécute en un temps O(i) lorsqu'il est appelé sur l'élément
S[i]. Quel est le pire temps d'exécution de l'algorithme D?

10. Alphonse et Bob se disputent à propos de leurs algorithmes. Alphonse revendique le fait que son
algorithme de temps d’exécution O(n log n) est toujours plus rapide que l'algorithme de temps
d'exécution O(n2) de Bob. Pour régler la question, ils effectuent une série d'expériences. À la
consternation d'Alphonse, ils découvrent que si n < 100, l'algorithme de temps O(n 2) s'exécute plus
rapidement, et que c'est uniquement lorsque n ≥ 100 que le temps O(n log n) est meilleur. Expliquez
comment cela est possible.

11. Concevoir un algorithme récursif permettant de trouver l'élément maximal d'une séquence
d'entiers. Implémenter cet algorithme et mesurer son temps d'exécution. Utiliser Matlab ou Excel
pour "fitter" les points expérimentaux et obtenir la fonction associée au temps d'exécution. Calculer
par la méthode des opérations primitives le temps d'exécution de l'algorithme. Comparer les deux
résultats.

12. Concevoir un algorithme récursif qui permet de trouver le minimum et le maximum d'une
séquence de nombres sans utiliser de boucle.

13. Concevoir un algorithme récursif permettant de déterminer si une chaine de caractères contient
plus de voyelles que de consonnes.

N.B.
Lors de la mise au point des tests d'un module. Chaque classe doit être testée. Dans une classe
toutes les méthodes doivent être testées. Dans une méthode chaque ligne de code doit être testée.
Dans chaque classe chaque ligne de code doit être testée. Lorsque plusieurs scenarios entrent en jeu,
tenté de tester tous les scenarios, au minimum testez les scenarios les plus importants.

Le travail repris ci-dessus se fait sous la supervision de l'assistant et avec son aide. Il se fait en 10
heures maximum.

Devoir

Les groupes d'étudiants créés précédemment travaillent et consignent les réponses des exercices de
1 à 13 dans un document "pdf" qu'ils déposent sur leur compte ou qu'ils transmettent par courrier
électronique à l'assistant et au Prof., selon la méthode qui a été utilisée dans la première partie.
 Fiche 3: Les structures des données.

1. Qu'est-ce qu'une structure de données?

2. Enumérez les structures de données que nous avons abordé dans ce cours?

3. Quelle est la procédure de base de conception d'une structure de donnée?

4. Qu'est-ce qu'une interface?

5. Qu'est-ce qu'un tableau?

6. Qu'est-ce qu'un tableau de références?

7. Qu'est-ce qu'un tableau compact?

8. Qu'est qu'un tableau dynamique?

9. Comparer les tableaux compacts, les tableaux de références et les tableaux dynamiques. Utilisez
une feuille Excel ou un tableau MS Word pour clarifier la comparaison.

10. Définir une pile (stack en anglais)

11. Définir une file d'attente (queue en anglais)

12. Définir une liste chainée simple, une liste chainée circulaire, une liste doublement chainée.

13. Soit ci-dessous l'interface d'une pile (stack) S.

Méthode : Objectif
S.push(e) : Ajoute l'élément <e> au top de la pile (stack) S
S.pop() : Retire l'élément qui se trouve sur le top de la
pile (stack) S et renvoie la référence de cet
élément à l'appelant. Une erreur se produit si la
pile () est vide.
S.top() : Retourne la référence de l'élément se trouvant
sur le top de la pile (stack) sans le retirer de la
pile (stack). Une erreur se produit si la pile
(stack) est vide.
S.is_empty() : Retourne True si la pile (stack) ne contient pas
d'élément.
len(S) : Retourne le nombre d'éléments dans la pile
(stack)
Remplacez les points d'interrogation par le contenu approprié dans le tableau ci-dessous.

Opération Valeur Retournée Contenu de la pile

(stack)
S.push(5) - [5]
len(S) 1 ????
S.push(10) - [5,10]
???????? - [5, 10, 12]
S.pop() 12 [5, 10]
S.is_empty() False [5, 10]
?????? 10 [5]
S.pop() 5 []
len(S) 0 []
S.pop() error []
S.push(2) - ????
S.push(8) - [2, 8]
S.push(98) - [2, 8, 98]
?????? 98 [2, 8]

14. Ci-dessous l'interface d'une file d'attente F:

Méthode : Objectif
F.enqueue(e) : Ajoute l'élément <e> à l'arrière de la file
d'attente F
F.dequeue() : Retire l'élément qui se trouve sur l'avant de la
file d'attente F. Retourne l'élément retirer a
l'appelant. Une erreur se produit si la file
d'attente est vide.
F.first() : Retourne la référence de l'élément se trouvant a
l'avant de la file d'attente sans de le retirer de la
dite file d'attente (queue). Une erreur se produit
si la file d'attente (queue) est vide.
F.is_empty() : Retourne True si la file d'attente (queue) ne
contient pas d'élément.
len(F) : Retourne le nombre d'élément dans la file
d'attente (queue)
Remplacez les points d'interrogation par le contenu approprié dans le tableau ci-dessous.

Opération Valeur Retournée Contenu de la file

d'attente
F.enqueue(9) - [9]
F.dequeue() 9 ????
len(F) 0 []
???????? - [10]
F.first() 10 [10]
F.is_empty() False [10]
?????? - [10,5]
S.dequeue() 10 [5]
len(S) 1 [5]
F.enqueue(15) - [5,15]
F.first() 5 ????
F.dequeue() 5 [15]
F.is_empty() False [15]
?????? 98 [15, 98]
Projet

Réunir toutes les classes développées dans le cadre de l'étude des structures des données dans un
seul module. Si certaines classes ont été implémentées deux fois ou plus, assurez-vous qu'elles
n'aient plus qu'une seule implémentation dans le module et qu'elles fournissent leurs services à
toutes les classes du module qui en ont besoin.

1. Présentez la liste des classes et fonctions étudiées au cours de l'examen des structures des
données.
2. Assurez-vous que le code de chaque classe ou fonction tourne correctement. Rédigez le résumé
des objectifs et des résultats obtenus pour chaque classe et fonction.
3. Réunir toutes les classes et toutes les fonctions dans un seul module.
4. Si une classe ou une fonction est implémentée plus d'une fois, supprimez les implémentations
redondantes et gardez une seule implémentation. Assurer vous que la classe ou la fonction ainsi
réorganisée fournit les services requis à toutes les classes et fonctions qui en ont besoin.
5. En vous appuyant sur la "docstring" et sur les autres recommandations de Python à propos de la
documentation, écrire un tutorial qui explique le module, ses objectifs, son contenu et indique
comment utiliser chacun de ses éléments.
6. Ecrire une batterie de tests pour le module. Expliquez le processus suivi dans la mise au point de
ces tests.

Ci-dessous la liste de classes et fonctions développées (assurez vous que je n'en ai pas oublié ou
omis volontairement):

CircularQueue.py
LinkedDeque.py
_DoublyLinked_Base.py
ArrayStack.py
ArrayQueue.py
LinkedStack.py
LinkedQueue.py
is_matched_html.py
is_matched.py
reverse_file.py
DynamicArraySizeEvaluation.py

Le travail se fait sous la supervision de l'assistant et avec son aide. Il se fait en 10 heures maximum.

Ce projet sera remis comme devoir (suivre les instructions des deux premiers devoirs).

Les étudiants prennent une semaine pour tout revoir et viennent avec les questions qui seront
posées à l'assistant et à leurs collègues. La séance se passe en 2 heures.

Si vous avez des remarques et/ou des suggestions vous pouvez me les transmettre par courrier
électronique.

Paul Olamba