ROYAUME DU MAROC

UNIVERSITE HASSAN PREMIER

INSTITUT DES SCIENCES DU SPORT _SETTAT

Module 04 : ALgorithmique et Programmation

Orientée Objets

Chapitre 01: Introduction à l’algorithmique

Pr. Iman EL MIR

[email protected]

AU: 2024/2025
Peu d’histoire
• Mathématicien, géographe, astrologue et astronome musulman
arabe dont les écrits ont permis l'introduction de l'algèbre en
Europe.

• L’ origine du mot « algorithme » est lié au nom d’AlKhwarizmi, qui

a vécu au 9ème siécle, était membre d’un académie des sciences à
Bagdad.

• Ce savant arabe a publié plusieurs méthodes pour le calcul effectif

de racines d’une équation du second degré et grâce à lui les
chiffres arabes ont pu se diffuser en occident.
Un algorithme doit :

• être simple à comprendre, à mettre en oeuvre et à mettre

au point ;
• mettre intelligement à contribution les ressources de
l’ordinateur, et plus précisément, il doit s’exécuter
rapidement.
Définitions
• Un algorithme = Description précise des opérations à faire pour résoudre un
problème (suite d’instructions).
• Procédure de calcul bien définie qui prend en entrée une valeur, ou un ensemble de
valeurs et qui donne en sortie une valeur, ou un ensemble de valeurs.

• Un bon algorithme =
• Un algorithme correct : i.e. pour chaque instance en entrée, l’algorithme se termine en
produisant la bonne sortie ⇒ Savoir prouver un algorithme
• Un algorithme efficace : mesure de la durée que met un algorithme pour produire un résultat
⇒ Savoir analyser la complexité d’un algorithme : i.e. détermination de l’espace mémoire et
du temps d’exécution nécessaire à la résolution du problème.
• Pour un problème donné, plusieurs algorithmes ou aucun sont possibles.
• Un algorithme se termine en un temps fini.
Analyse d’un algorithme
q Simplicité et intelligibilité de l’algorithme
q Efficacité de l’algorithme :

§ Temps d’exécution
§ Occupation de la mémoire
§ Quantité de trafic généré sur un réseau
§ Quantité de données déplacées sur le disque
Complexité d’un algorithme

Deux types de compléxité :

• En espace : Quelle quantité de place en mémoire va t-on

utiliser ?
• En temps : Combien d’opérations va t-on effectuer ?
Propriétés d’un algorithme
Un algorithme doit:
– avoir un nombre fini d’étapes,
– avoir un nombre fini d’opérations par étape,
– se terminer après un nombre fini d’opérations,
– fournir un résultat.

Chaque opération doit être:

– définie rigoureusement et sans ambiguïté
– effective, c.-à-d. réalisable par une machine
Le comportement d'un algorithme est déterministe
Définition

Un algorithme est une méthode de résolution d’un problème

en un temps fini, décrite dans un langage suffisamment
précis pour être traduisible aisément et sans ambiguïté en
une suite d’instructions compréhensibles par une machine.
Un algorithme n’est pas un programme!

• L’algorithme décrit une méthode qui sera ensuite

implémentée dans un langage de programmation.

• Un algorithme peut être implémenté par une ou plusieurs

fonctions ;

• Une fonction peut exécuter plusieurs algorithmes;

• Un programme peut contenir plusieurs algorithmes ou
fournir un résultat nécessaire à l’exécution d’un autre
algorithme ;
Mesurer le temps d’exécution
• Le temps d’exécution dépend de l’entrée : par exemple dans le cas
d’un algorithme de tri, si le tableau est déja trié.
• On cherche une fonction T(n) représentant le temps d’exécution
d’un algorithme en fonction de la taille de l’entrée n (nombre
d’élements constituant l’entrée, nombre de bits nécessaire à la
représentation de l’entrée,...)
• L e ca lcu l ex a ct ét a n t s o u v e n t i m p o s s i b l e à a p p r é h e n d e r
exactement,on s’intéresse aux :
• Meilleur des cas
• Pire de cas
Ecriture algorithmique
• Savoir expliquer comment faire un travail sans la moindre
ambiguïté.

L’écriture algorithmique : un travail de programmation

ayant une vision universelle :
• Un algorithme ne dépend pas du langage dans lequel il est
implanté, ni de la machine qui va exécuter le programme
correspondant.
Algorithmique
L’algorithmique désigne la discipline qui étudie les
algorithmes et leurs applications en informatique

Une bonne connaissance de l’algorithmique permet

d’écrire des algorithmes exacts et efficaces.
Les 3 étapes d’un algorithme
o Les entrées (les données du problème)
o Le traitement
oLes sorties (l’affichage des résultats)

Les entrées : Il s’agit de repérer les données nécessaires à la résolution du problème.

Le traitement : Il s’agit de déterminer toutes les étapes des traitements à faire et

donc des "instructions" à delopper pour arriver aux résultats.

Les sorties : les résultats obtenus peuvent être affichés sur l’écran, ou imprimés sur
papier, ou bien encore conservés dans un fichier.
Types d’instructions
• Un programme informatique est formé de quatre types
d’instructions considérées comme des briques de base :

§ Les affectations de variables

§ Les lectures et/ou les écritures
§ Les tests
§ Les boucles
Structure d’un algorithme
Un algorithme informatique doit suivre les règles suivantes :

• Il est composé d’une entête et d’un corps :

• l’entête, qui spécifie :le nom de l’algorithme (Nom : )
son utilité (Rôle : )

Les données “en entrée” : les éléments qui sont

indispensables à son bon fonctionnement (Entrée : )
Structure d’un algorithme
les données “en sortie” : les éléments calculés, produits, par
l’algorithme (Sortie : )

les données locales à l’algorithme et indispensables

(Déclaration :)
le corps, qui est composé :
§ du mot clé début
§ d’une suite d’instructions
§ du mot clé fin
• On peut considérer un algorithme comme une machine qui
va prendre en entrée la description d’un problème et une
instance de ce problème, c’est-à-dire des données, et qui
fournira en sortie une solution à l’instance du problème
examiné :

Problème Données

Algorithme

Résultat
Exemple
Assistant de navigation GPS :

— Problème : Trouver un chemin le plus court possible entre

ces deux villes dans le réseau donné ;
— une instance du problème serait un triplet avec des valeurs
spécifiques; par exemple :

“départ = casa, arrivée = Bouskoura, réseau =réseau routier”.

Exemple
• Problème: Recherche d’itinéraire
• Données: les données sur lesquelles on travaille.(exemple :
une ville de départ, une ville d’arrivée, et un réseau routier).

• Question: le problème à résoudre.

Exemple : quel est le plus court chemin dans le réseau donné
entre les villes données ?
Algorithme
• Deux aspects intéressants en algorithmique :
• correct, il donne toujours la bonne réponse quelles que
soient les données d’entrée ; et
• efficace, économe en temps de calcul et en ressources.
• Les algorithmes construisent des solutions intermédiaires
pas à pas, en suivant une succession d’étapes qui finissent
par mener à une solution définitive.
Temps d’exécution
Un algorithme soit correct, mais aussi efficace, c’est-à-dire :

• rapide en termes de temps d’exécution

• économe en ressources : espace de stockage, mémoire.
Temps d’exécution
• Evaluer l’efficacité d’un algorithme sans l’implémenter et indépendamment de
l’architecture de la machine.
• Les règles pour calculer le temps d’exécution d’un algorithme :

— chaque instruction basique (affectation d’une variable, comparaison, +, −, ∗ ,

/, . . .) consomme une unité de temps ;
— chaque itération d’une boucle rajoute le nombre d’unités de temps
consommées dans le corps de cette boucle ;
— chaque appel de fonction rajoute le nombre d’unités de temps consommées
dans cette fonction;
— pour avoir le nombre d’opérations effectuées par l’algorithme, on additionne le
tout.
la complexité d’un algorithme
• On peut calculer la complexité d’un algorithme, mais
également celle d’un problème.

• La complexité d’un problème est celle du meilleur

algorithme connu pour le résoudre, et ce critère peut
également être utilisé pour classer les problèmes plutôt
que les algorithmes :

• un problème de complexité polynomiale est considéré “facile” ;

• complexité non-polynomiale est considérée “difficile”.
Exemple : « PageRank » de Google
• Il s’agit d’un ensemble d’algorithmes utilisés par Google
pour déterminer l’importance des documents indexés par
son moteur de recherche web.

• Ainsi, lorsqu’un internaute effectue une recherche sur

Google, il constitue l’un des éléments qui déterminent
l’ordre d’affichage des résultats.

• Le PageRank constitue sans aucun doute l’algorithme le

plus utilisé dans le monde.
Exemple : Timeline de Facebook

• Le contenu que Facebook affiche sur le fil d’actualité des

utilisateurs est choisi par un ensemble d’algorithmes.

• Ces algorithmes décident du contenu à afficher en fonction

de divers paramètres.
• Par exemple, les goûts personnels de l’utilisateur, ses
réactions à des contenus précédemment publiés et bien
d’autres encore.
Exemple : Round Robin (Tourniquet)

• Il s’agit d’un algorithme très utilisé dans le domaine de

l’informatique. En effet, il permet aux ordinateurs de
déterminer les tâches qu’ils doivent effectuer en premier.

• En règle générale, cet algorithme détermine le temps que

le processeur va consacrer à chaque tâche en cours.
Sous-problèmes / Sous-solutions optimales

• Il est donc important d’être capable d’identifier des

problèmes ou des sous-tâches qui ressemblent à des
problèmes qu’on a déjà résolus, voire de réutiliser des
algorithmes connus comme des “boîtes noires”.

• Une méthode simple et efficace pour résoudre les

problèmes auxquels on est confrontés est de les découper
en sous-problèmes et de répéter ce procédé jusqu’à ce que
les sous-problèmes obtenus soient suffisamment simples à
résoudre.
Paradigmes de l’algorithme
• Les paradigmes de l'algorithmique sont des approches
générales pour concevoir des algorithmes.
• Ils fournissent des cadres ou des modèles pour résoudre
une grande variété de problèmes. Voici les principaux
paradigmes :
Paradigmes de l’algorithme
• Diviser pour régner: Ce paradigme consiste à diviser un problème
en sous-problèmes plus petits et plus faciles à résoudre, puis à
combiner les solutions pour obtenir une solution globale.
• Dichotomie
• Tri par fusion

• Programmation dynamique : Cette méthode est utilisée lorsque le

problème a une structure récursive, mais où les sous-problèmes
se chevauchent. Elle consiste à résoudre chaque sous-problème
une seule fois, puis à stocker les solutions pour éviter de
recalculer les résultats.
• Nombres de Fibonacci
Paradigmes de l’algorithme
• Le glouton consiste à prendre des décisions locales optimales à
chaque étape dans l'espoir d'obtenir une solution optimale globale.
Il ne garantit pas toujours la solution optimale, mais fonctionne
bien pour certains problèmes.
• L'algorithme de Dijkstra pour les plus courts chemins.

• Le Retour sur trace (Backtracking) :il s'agit d'un paradigme utilisé

pour résoudre des problèmes combinatoires en essayant toutes
les solutions possibles. Lorsqu'une solution potentielle est
identifiée comme non valide, l'algorithme revient en arrière et
essaie une autre solution.
• La recherche exhaustive dans les arbres de décision.
 Paradigmes de l’algorithme
• Branch and Bound (Élagage et bornage) : Ce paradigme est utilisé pour résoudre
des problèmes d'optimisation. Il explore les solutions possibles de manière
systématique et écarte (ou élague) les branches de l'arbre de recherche qui ne
peuvent pas mener à une solution optimale.
Exemples : problèmes de planification.

• Algorithmes probabilistes et aléatoires : Certains algorithmes utilisent des

décisions aléatoires pour résoudre des problèmes avec une grande probabilité
d’obtenir une bonne solution. Ces algorithmes sont utiles lorsqu’une solution
déterministe est trop lente ou complexe
Exemples : Algorithme de Monte Carlo.

• Ces paradigmes sont des outils puissants pour les concepteurs d'algorithmes, car
ils permettent de trouver des solutions efficaces pour une grande diversité de
problèmes en informatique.
Diviser pour régner
Le diviser pour régner est une méthode algorithmique basée sur le principe suivant :

• On prend un problème (généralement complexe à résoudre), on divise ce problème

en une multitude de petits problèmes, l'idée étant que les "petits problèmes"
seront plus simples à résoudre que le problème original. Une fois les petits
problèmes résolus, on recombine les "petits problèmes résolus" afin d'obtenir la
solution du problème de départ.
Le paradigme "diviser pour régner" repose donc sur 3 étapes :

• DIVISER : le problème d'origine est divisé en un certain nombre de sous-problèmes

• RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à
résoudre que le problème d'origine)
• COMBINER : les solutions des sous-problèmes sont combinées afin d'obtenir la
solution du problème d'origine.
Diviser pour régner

Problème 1 Solution 1

Problème Problème 2 Solution 2 Solution

Problème 3 Solution 3

Diviser combiner
Régner
Exemple : La recherche dichotomique
• La recherche dichotomique est un des premiers exemples
d’algorithme efficace suivant la stratégie “diviser pour régner” que
l’on couvre dans les cours d’algorithmique.

Si la séquence dans laquelle on veut trouver un élément est triée, on

peut appliquer la stratégie suivante :
• diviser : on divise l’intervalle de recherche en deux parties égales (à
un élément près);
• régner : on effectue la recherche récursivement dans une seule des
deux sous-parties en fonction de la valeur de l’élément recherché et
du pivot sélectionné;
• combiner : le résultat est la combinaison du résultat de la recherche
dans les deux parties.
La recherche dichotomique
L : tableau d'entiers trié tant que NON trv ET deb ⩽ fin :
mil : nombre entier mil ← partie_entière((deb+fin)/2)
si L[mil] == v :
fin : nombre entier trv ← VRAI
deb : nombre entier sinon :
si v > L[mil] :
v : nombre entier // la valeur deb ← mil+1
recherchée
sinon :
trv : booléen fin ← mil-1

fin si
trv ← FAUX
deb ← 1 fin si
fin ← longueur(L) fin tant que
Exemple
5 7 12 14 23 27 35 40 41 45

Valeur a chercher : X= 35
Produit des matrices

Soient A = (aij ) et B = (bij ) deux matrices carrées de taille n × n.

• La multiplication de A et B est définie par C = A × B

avec :
�
��� = � .�
1 �� ��
Multiplication des matrices
Algorithme : produit_matrices( A, B : Matrice; m, n, p : Entier; C : Matrice)

Variable i, j, k : Entier
Variable somme : Réel

Début
Pour i <- 1 à m Faire
Pour j <- 1 à p Faire
somme <- 0.0
Pour k <- 1 à n Faire
somme <- somme+ A[i,k] × B[k , j]
Fin Pour
C[i , j] <- somme
FinPour
FinPour
Fin
Programmation dynamique
• Le mot Programmer s'entend ici sous le sens Planifier, Prévoir.

• Il n'y aucun lien avec le mot "coder".

La stratégie de la programmation dynamique est utilisée

lorsqu'on veut résoudre un problème dont les sous-problèmes sont
interdépendants.
Principe
• La stratégie de la programmation dynamique consiste à planifier
l'ordre de résolution des différents résultats intermédiaires pour
ne jamais refaire deux fois la même chose.

• A chaque fois qu'une sous-solution est trouvée, on l'enregistre

dans une mémoire-cache de façon à pouvoir utiliser à nouveau
directement le résultat lors de la résolution d'un autre sous-
problème.

• On ne parle pas de mémorisation mais de mémoïsation car les

résultats intermédiaires ne seront en mémoire que le temps du
calcul.
Conception d’algorithmes de programmation
dynamique
L’élaboration d’algorithmes de programmation dynamique requiert de mettre en
évidence une structure de sous-problèmes dont on peut exploiter les solutions
optimales, de manière à pouvoir en déduire une première ébauche récursive dont on
supprime ensuite les appels récursifs par des lectures et écritures dans une table de
résultats intermédiaires.
On applique donc en général la stratégie suivante :
1. caractériser la structure d’une solution optimale;
2. définir la valeur d’une solution optimale récursivement, ce qui donne lieu à
l’écriture d’une équation de programmation dynamique ;
3. écrire l’algorithme correspondant sous forme récursive, et enfin
4. remplacer les appels récursifs par un stockage ou une consultation des valeurs
calculées; bien souvent, on se rend ensuite compte qu’il est possible d’optimiser
la consommation en mémoire.
Exemple : Fonction Fibonacci
• Un algorithme récursif est multiple si l’un des cas qu’il distingue se résout
avec plusieurs appels récursifs.

• Exemple : La suite de Fibonacci est un bon exemple de récursivité multiple.

U0 = U1 = 1 et Un = Un-1 + Un-2, pour n ≥ 2

int Fibonacci(int n){
if ((n==0)||(n==1)) return (1);
else return (Fibonacci(n-1)+Fibonacci(n-2));
}
Algorithme naîf
Algorithme : FIBONACCI_v1(n)

• Entrées : un naturel n.
• Sortie : le nème nombre de Fibonacci.
si n ≤ 1 alors renvoyer n;
renvoyer FIBONACCI_V1(n −1) + FIBONACCI_V1(n −2);
Avec principe de la programmation
dynamique
Algorithme: FIBONACCI_V2(n)
Entrées : un naturel n.
Sortie : le nème nombre de Fibonacci.

si n ≤ 1 alors renvoyer n;
valeurs ← tableau(n +1, 0);
valeurs[0] ← 0;
valeurs[1] ← 1;
pour chaque i allant de 2 à n faire
valeurs[i] ← valeurs[i −1] + valeurs[i −2];
renvoyer valeurs[n];
 Exemple

On met en mémoire chaque sous-solution dès qu'on l'arbre du calcul naïf sans stockage des résultats
l'obtient.
=>une fois que f(3) aura été calculée une première
fois, il suffira d'aller relire le résultat plutôt que de
relancer le vrai calcul.
Applications en domaine du sport
• Les paradigmes de l'algorithmique peuvent être appliqués
aux sciences du sport de manière intéressante, notamment
pour résoudre des problèmes liés à la performance des
athlètes, à l'optimisation de la stratégie sportive, ou à
l'analyse des données de performance.
Exemple 1: Diviser pour régner
Ce paradigme peut être utilisé pour analyser des
performances sportives en divisant un match ou une
compétition en sous-parties plus simples.

• Par exemple, pour analyser une course d'endurance, on

peut diviser la course en segments (par exemple, des
intervalles de temps ou de distance), et analyser la
performance de l'athlète dans chaque segment
indépendamment, avant de les combiner pour obtenir une
vue d’ensemble.
Exemple 2: Programmation dynamique

Ce paradigme peut être appliqué dans l’optimisation des

plans d’entraînement, où certaines étapes se chevauchent
et où des solutions optimales doivent être mémorisées.

• Par exemple, dans la planification de la progression d’un

athlète sur plusieurs mois, un programme dynamique
pourrait stocker les résultats d'entraînements antérieurs
pour ajuster le programme futur en fonction de la
récupération et des performances antérieures.
Exemple 3: Glouton
Un algorithme glouton peut être utilisé pour optimiser une
stratégie sportive en prenant des décisions locales
immédiates.

• Par exemple, lors d’un match de football, un algorithme

glouton pourrait être utilisé pour choisir la meilleure action
à court terme (comme passer ou tirer) en se basant sur la
position actuelle du ballon, sans nécessairement garantir la
meilleure stratégie à long terme.
Exemple 3 : Retour sur trace
Le retour sur trace peut être appliqué pour explorer
différentes stratégies lors d’un match ou d’une compétition.
Si une stratégie ne fonctionne pas, l'algorithme revient à une
étape précédente et essaie une autre approche.

• Par exemple, dans l’analyse des stratégies de défense dans

un match de basket-ball, on peut tester plusieurs
configurations de défense et revenir en arrière en cas
d’échec.
Exemple 4 : algorithmes probabilistes

Les algorithmes probabilistes sont utiles lorsqu’il y a de

l’incertitude dans les événements sportifs, comme dans les
paris sportifs ou la simulation de performances futures.

• Par exemple, une simulation de Monte Carlo pourrait être

utilisée pour prédire le résultat d'un match de football en
prenant en compte plusieurs facteurs comme la forme des
joueurs, les conditions météorologiques, etc.
Langages de programmation
• Ensembles de mots clefs et de règles pour former des
phrases pouvant être traduites par la machine (binaire).

Plusieurs niveaux :
• Langages de bas niveau : instructions élémentaires très
proches de la machine (ex : Assembleur )
• Langages de haut niveau : instructions plus abstraites (C,
C++, Perl, Java, Python).
Paradigmes de programmation
• Procédural
• Fonctionnel
• Logique
• événementielle
• concurrente
• Orienté objet
Programmation procédurale
• Déclaration de procédures accomplissant des tâches spcifiques nécessaires au
programme. Les étapes sont expliquées ligne par ligne, et l’instruction atomique
est l’affectation de variables. Le programme est exécuté.
• Elle consiste à donner des instructions à l'ordinateur pour qu'il effectue des actions
dans un ordre précis, en modifiant l'état du programme au fur et à mesure.

Caractéristiques :
• Basée sur des instructions séquentielles.
• Utilisation de variables pour stocker l’état du programme.
• Changement de l'état du programme par des affectations, des boucles et des
conditions.
Exemples : FORTRAN,C,PASCAL
Programmation fonctionnelle
Langage d’utilisation et de developpement de fonctions. Tout
programme est construit par fonctions, retournant un résultat en
sortie et prenant en entrée la sortie d’autres fonctions. Le
programme est évalué.

Diviser un problème complexe en sous problèmes

• Récursivité

Exemples
CAML, LISP, ...
Programmation logique
• Langage déductif utilisant des règles et des faits. Un moteur
d’inférence permet de donner le résultat.

• Le programme est une théorie axiomatique à partir de laquelle on

infère (démonstrations logiques/mathématiques) les résultats.

Exemple
PROLOG
programmation événementielle
• La programmation événementielle repose sur la gestion
des événements déclenchés par l'utilisateur ou par le
système.
• Elle est courante dans le développement d'interfaces
graphiques, où les actions comme un clic de souris ou une
pression de touche déclenchent des événements.
Programmation parallèle et concurrente
• La programmation parallèle et concurrente est utilisée pour
exécuter plusieurs calculs ou tâches simultanément. Elle
est courante dans les systèmes multi-cœurs et les
applications nécessitant une haute performance.

Caractéristiques :
• Division du travail en unités qui peuvent s'exécuter en
parallèle.
• Gestion des threads, processus ou tâches simultanées.
• Coordination des ressources partagées et des
synchronisations.
Programmation orientée-objet
• Basée sur le principe que des choses peuvent avoir des points communs, des
similarités en elles-mêmes ou en leur façon d’agir.
• La programmation orientée objet est basée sur la modélisation du problème sous
forme d'objets. Chaque objet est une instance d'une classe et combine à la fois des
données (attributs) et des méthodes (comportements).

• On conçoit des fabriques (classes) qui servent à construire des composants

(objets).
• Les classes contiennent des données(attributs) et des actions (méthodes).

Exemples
C++, JAVA