Introduction générale
Dr. Mahfoud Houari
[Link]@[Link]
Université Abou-Bakr Belkaïd - Tlemcen
2023/2024
Introduction générale
Quelques paradigmes de programmation
Pourquoi ce cours ?
●
La suite du cours Algorithmique et structures de données
●
Ce qui est préalablement acquis :
1. Proposer des programmes naîfs (coûte que coûte) pour des problèmes
classiques (recherche, ajout, insertion, fusion,…).
2. La récursivité (un premier pas vers la conception algorithmique).
3. Définir et manipuler des structures de données (séquentielles et
hiérarchiques).
4. Quelques notions de complexité.
Introduction générale
Quelques paradigmes de programmation
Pourquoi ce cours ?
Votre bagage algorithmique doit être étendu :
1. En pratique, l’efficacité compte plus que la correction.
⇒ Apprendre à mesurer l’éfficacité d’un algorithme.
2. Le choix de la structure de données influence sur l’efficacité.
⇒ Maitriser le maximum de sructures de données.
3. Il y a d’autres méthodes de conception autre que la récursivité.
⇒ Voir les fameux paradigmes de conception d’algorithmes.
4. Les problèmes classiques n’offrent pas de job.
⇒ Étude de quelques problèmes complexes d’utilité réelle.
5. Classification des problèmes.
Introduction générale
Quelques paradigmes de programmation
Objectifs du cours en détails :
1. Arrêter de programmer naïvement :
⇒ Penser à l’efficacité et pas juste à la correction.
⇒ Suivre les étapes de conception d’algorithmes.
2. Savoir s'il existe un algorithme pour un problème donné :
⇒ Notion de décidabilité
⇒ Exemple : Le « problème de Correspondance de Post »
est indécidable.
Introduction générale
Quelques paradigmes de programmation
Objectifs du cours en détails :
3. Quel type de solution pour un problème donné ?
⇒ Solution correcte : la plus exacte possible
(est-ce possible tout le temps ?)
⇒ Solution efficace : la plus rapide possible.
(est-ce possible tout le temps ?)
Exemples :
●
Recherche dans une structure de données (Correcte, Efficace).
●
Faire des jointures multiples de tables relationnelles (C, E).
●
Établir un emploi du temps (C, E).
⇒ Bon algorithme » : compromis entre correction et efficacité.
(quelle mesure à sacrifier ?)
Introduction générale
Quelques paradigmes de programmation
Objectifs du cours en détails :
4. Analyser les performances théoriques et pratiques d’un
algorithme.
5. Classification des problèmes.
6. Méthodes de conception d'algorithmes :
Méthodes exhaustives
Diviser pour régner
Programmation dynamique
Algorithmes Gloutons
Branch and Bound
7. Savoir proposer des solutions approximatives.
Introduction générale
Quelques paradigmes de programmation
Plan du cours :
1. Efficacité & Optimalité
2. Analyse de complexité (noyau du module)
3. Diviser pour régner
4. Programmation dynamique
5. Algorithmes gloutons
6. Branch & Bound
7. Les classes de problèmes P, NP et NPC
8. Les algorithmes d'approximation
Notions élémentaires
Quelques paradigmes de programmation
Efficacité & Optimalité
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
●
Un algorithme est efficace s’il nécessite une quantité de
ressources raisonable par rapport au contexte.
●
L’éfficacité se calcule généralement en terme d’opérations
effectuées.
●
Un algorithme A est plus éfficace qu’un algorithm B si le
premier nécessite moins d’opérations que le deuxième.
●
Un algorithme est dit optimal si aucun autre algorithme est
plus éfficace que lui.
●
L’optimalité est gnéralement assurée pour les petits
problèmes.
●
L’éfficacité peut entraîner une perte de mémoire.
●
L’éfficacité peut entraîner une perte de correction
⇒ Solution approchée
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°01 :
Soit donné un tableau T composé de N entiers. Trouver les 03
plus grands entiers en T.
Solution :
void TGE(int[] T){
int p, d, t;
p = d = t = -1;
for(int i=0; i < [Link]; i++){ ⇒ Nombre d’opérations dépend de N.
if(T[i] > p){
⇒ Est-elle optimale ? Oui
t = d; d = p; p = T [i];
} else if(T[i] > d){
t = d; d = T[i];
} else if(T[i] > t){
t = T[i];
}
}
[Link]("Les trois plus grands éléments sont " + p +", " + d + " et "+ t);
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°02 :
Soit donné un tableau T composé de N entiers. Trouver
l’entier le plus dominant en T.
Solution 1 :
void ED_Sol_1(int[] T){
int ed, occ_ed = 0;
int ec, occ_ec;
int nbreComp = 0; ⇒ Nombre d’opérations dépend de N².
for(int i=0; i < [Link]; i++){
⇒ Est-elle optimale ? Non
ec = T[i], occ_ec = 1;
for(int j = i +1; j < [Link]; j++){
if(T[i] == T[j]) { occ_ec++; nbreComp++; }
}
if(occ_ec > occ_ed){ ed = ec, occ_ed = occ_ec; }
}
[Link]("L'élément dominant "+ed+" se répète " +occ_ed+" fois.");
[Link]("Nbre comparaisons = " + nbreComp);
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°02 :
Solution 2 :
void ED_Sol_2(int[] T){
int[[Link]] Vu;
for(int i=0; i < [Link]; i++) Vu[i] = T[i];
int ed, occ_ed = 0; ⇒ Nombre d’opérations dépend de N².
int ec, occ_ec;
int nbreComp = 0; ⇒ Plus éfficace que la première.
for(int i=0; i < [Link]; i++){
⇒ Est-elle optimale ? Non
if(Vu[i] != -1){
ec = T[i], occ_ec = 1; V[i] = -1 ;
for(int j = i +1; j < [Link]; j++){
if(T[i] == T[j]) { occ_ec++; nbreComp++; Vu[j] = -1 ; }
}
if(occ_ec > occ_ed){ ed = ec, occ_ed = occ_ec; }
}
}
[Link]("L'élément dominant "+ed+" se répète " +occ_ed+" fois.");
[Link]("Nbre comparaisons = " + nbreComp);
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°02 :
Solution 1 vs Solution 2 :
Public static void main(String [] args)
{
int[] T = {1,2,3,3,4,3, 5,5,6,5,3, 2,5,7,5,8,9,5,3,2,6,3,5};
ED_Sol_1(T);
ED_Sol_2(T);
}
Affichage du programme:
L'élément dominant est 5, il se répète 7 fois. Nbre comparaisons = 40.
L'élément dominant est 5, il se répète 7 fois. Nbre comparaisons = 14.
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°02 :
Solution 3 :
void ED_Sol_3(int[] T){ ⇒ Nombre d’opérations dépend
[Link](T); de [Link](N) + N.
int ed, occ_ed = 0; ⇒ Plus éfficace que les
int ec, occ_ec; précédentes.
for(int i=0; i < [Link]; i++){
ec = T[i], occ_ec = 1; ⇒ Est-elle optimale ? Non
int j = i+1;
while(j < [Link] && T[i] == T[j]){ occ_ec++; j++; }
if(occ_ec > occ_ed){
ed = ec, occ_ed = occ_ec;
}
i = j - 1;
}
[Link]("L'élément dominant "+ed+" se répète " +occ_ed+" fois.");
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°03 :
Soit donné un tableau T composé de N entiers. Trouver le sous
tableau continu de taille K dont la somme est maximale.
Solution 1 :
void STM_Sol_1(int[] T, int K){
int d, somme = 0;
int dc, sommeCourante;
for(int dc=0; dc < [Link] - K + 1; dc++){ ⇒ Nombre d’opérations
sommeCourante = T[dc]; dépend de N.K.
for(int j=1; j < K; j++){
⇒ Est-elle optimale ? Non
sommeCourante += T[dc + j];
}
if(sommeCourante > somme){
d = dc, somme = sommeCourante;
}
}
[Link]("Le sous-tableau commençe à "+d+". Sa somme est " + somme);
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°03 :
Soit donné un tableau T composé de N entiers. Trouver le sous
tableau contingu de taille K dont la somme est maximale.
Solution 2 (Window Sliding Technique):
void STM_Sol_2(int[] T, int K){ ⇒ Nombre d’opérations
int d = 0, somme = 0; dépend de N.
for(int i=0; i < K ; i++) somme += T[i]; ⇒ Est-elle optimale ? Oui
int dc = 0, finc = K - 1, sommeCourante=somme;
while (finc + 1 < [Link]){
sommeCourante = sommeCourante - T[dc] + T[finc + 1];
dc += 1; finc += 1 ;
if(sommeCourante > somme){
d = dc, somme = sommeCourante;
}
}
[Link]("Le sous-tableau commençe à "+d+". Sa somme est " + somme);
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°04 :
Calculer XN.
Solution 1 :
int Puissance_1(int X, int N){
if(N == 0) ⇒ Nombre de multiplications
return 1 ; = N – 1.
else if(N == 1)
return X ; ⇒ Nombre total d’opérations
else dépend de N.
return X * Puissance_1(X, N – 1) ; ⇒ Est-elle optimale ? Non
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°05 :
Calculer la somme d’éléments d’un tableau T de taille N.
Solution récursive 1 : ⇒ Nombre de sommes
//Au début : i = 0 dépend de N
int Somme_RNT(int[] T, int i){
if(i == [Link] - 1) ⇒ Est-elle optimale en
return T[i] ; terms de temps ? Oui
else ⇒ Est-elle optimale en
return T[i] + Somme_RNT(T, i + 1) ; terms de mémoire ? Non
}
Solution récursive 2 : ⇒ Nombre de sommes
//Au début : i = 0, s = 0 dépend de N
int Somme_RT(int[] T, int i, int s){
if(i == [Link]) ⇒ Est-elle optimale en
return s ; terms de temps ? Oui
else
return Somme_RT(T, i + 1, s + T[i]) ;
⇒ Est-elle optimale en
terms de mémoire ? Oui
}
Notions élémentaires – Efficacité & Optimalité
Quelques paradigmes de programmation
Problème n°05 :
Calculer la somme d’éléments d’un tableau T de taille N.
Synthèse :
●
Les deux méthodes réalisent le même nombre de sommes.
●
Somme_RNT nécessite une pile en mémoire pour stocker le
résultat de chaque appel récursif. Elle est appelée solution
récursive non-terminale.
●
Somme_RT nécessite de stocker uniquement le résultat du
dernier appel récursif. Elle est appelée solution récursive
terminale.
●
Une solution récursive non-terminale nécessite plus d’espace
mémoire que sa version itérative ou sa version terminale.
●
D’où, les méthodes itératives et récursives terminales sont plus
efficaces, en termes de mémoire, que les méthodes récursives non-
terminales.
Notions élémentaires – Classification des problèmes
Déterminer le type du problème avant de le résoudre.
Le problème en question admet-il une solution finie ?
Non Oui
Problème indécidable Problème décidable
Y a t-il une solution
⇒ Non considéré dans correcte & efficace ?
ce cours
⇒ Réduction du Oui Non
problème
Résolutions
Résolutions approchées ou
exactes heuristiques
Notions élémentaires – Classification des problèmes
Déterminer le type du problème avant de le résoudre.
Comment le savoir ?
● Problème facile : le nombre de cas à traiter est
polynomial.
⇒ Le temps d’exécution augmente lentement.
● Problème difficile : le nombre de cas à traiter est non-
polynomial.
⇒ Le temps d’exécution augmente exponentiellement.
Exemple : Pour un problème ayant la taille N=10
● N3 = 1000 cas à traiter.
● N ! = 3628800 cas à traiter.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (1):
● Soient donnés deux tableaux de tailles N et M (N > M),
tester si le deuxième est un sous-tableau du premier.
⇒ N – M cas à traiter nécessitant chacun M opérations
⇒ Problème facile.
● Tester si un tableau de taille N est non trié.
⇒ N – 1 cas à traiter nécessitant chacun 1 opération
⇒ Problème facile.
● Tester si un nombre N est premier.
⇒ N / 2 cas à traiter nécessitant chacun 02 opérations
⇒ Problème facile.
● Soit donnée une matrice carrée de taille N. Tester si elle est
symétrique.
⇒ N.(N - 1)/2 cas à traiter nécessitant chacun 01 opération
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (1):
● Soient donnés deux tableaux de tailles N et M (N > M),
tester si le deuxième est un sous-tableau du premier.
⇒ N – M cas à traiter nécessitant chacun M opérations
⇒ Problème facile.
● Tester si un tableau de taille N est non trié.
⇒ N – 1 cas à traiter nécessitant chacun 1 opération
⇒ Problème facile.
● Tester si un nombre N est premier.
⇒ N / 2 cas à traiter nécessitant chacun 02 opérations
⇒ Problème facile.
● Soit donnée une matrice carrée de taille N. Tester si elle est
symétrique.
⇒ N.(N - 1)/2 cas à traiter nécessitant chacun 01 opération
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (1):
● Soient donnés deux tableaux de tailles N et M (N > M),
tester si le deuxième est un sous-tableau du premier.
⇒ N – M cas à traiter nécessitant chacun M opérations
⇒ Problème facile.
● Tester si un tableau de taille N est non trié.
⇒ N – 1 cas à traiter nécessitant chacun 1 opération
⇒ Problème facile.
● Tester si un nombre N est premier.
⇒ N / 2 cas à traiter nécessitant chacun 02 opérations
⇒ Problème facile.
● Soit donnée une matrice carrée de taille N. Tester si elle est
symétrique.
⇒ N.(N - 1)/2 cas à traiter nécessitant chacun 01 opération
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (1):
● Soient donnés deux tableaux de tailles N et M (N > M),
tester si le deuxième est un sous-tableau du premier.
⇒ N – M cas à traiter nécessitant chacun M opérations
⇒ Problème facile.
● Tester si un tableau de taille N est non trié.
⇒ N – 1 cas à traiter nécessitant chacun 1 opération
⇒ Problème facile.
● Tester si un nombre N est premier.
⇒ N / 2 cas à traiter nécessitant chacun 02 opérations
⇒ Problème facile.
● Soit donnée une matrice carrée de taille N. Tester si elle est
symétrique.
⇒ N.(N - 1)/2 cas à traiter nécessitant chacun 01 opération
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (1):
● Soient donnés deux tableaux de tailles N et M (N > M),
tester si le deuxième est un sous-tableau du premier.
⇒ N – M cas à traiter nécessitant chacun M opérations
⇒ Problème facile.
● Tester si un tableau de taille N est non trié.
⇒ N – 1 cas à traiter nécessitant chacun 1 opération
⇒ Problème facile.
● Tester si un nombre N est premier.
⇒ N / 2 cas à traiter nécessitant chacun 02 opérations
⇒ Problème facile.
● Soit donnée une matrice carrée de taille N. Tester si elle est
symétrique.
⇒ N.(N - 1)/2 cas à traiter nécessitant chacun 01 opération
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (2):
● Soit donné un tableau T de taille N. Tester s’il y a K
éléments de T dont la somme est égale à S.
⇒ N!/(N – K)!.K! cas à traiter nécessitant chacun K-1
sommes.
⇒ Problème difficile.
● Soit donné un ensemble E composé de N pièces de
monnaies. Tester si E peut être divisé en deux sous-
ensembles ayant la même somme.
⇒ 2N cas à traiter nécessitant chacun N-1 sommes.
⇒ Problème difficile.
● Soit donné une matrice Sudoku de taille 9.9 et avec N cases
remplies par l’utilisateur. Tester si cette solution est
correcte.
⇒ N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (2):
● Soit donné un tableau T de taille N. Tester s’il y a K
éléments de T dont la somme est égale à S.
⇒ N!/(N – K)!.K! cas à traiter nécessitant chacun K-1
sommes.
⇒ Problème difficile.
● Soit donné un ensemble E composé de N pièces de
monnaies. Tester si E peut être divisé en deux sous-
ensembles ayant la même somme.
⇒ 2N cas à traiter nécessitant chacun N-1 sommes.
⇒ Problème difficile.
● Soit donné une matrice Sudoku de taille 9.9 et avec N cases
remplies par l’utilisateur. Tester si cette solution est
correcte.
⇒ N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (2):
● Soit donné un tableau T de taille N. Tester s’il y a K
éléments de T dont la somme est égale à S.
⇒ N!/(N – K)!.K! cas à traiter nécessitant chacun K-1
sommes.
⇒ Problème difficile.
● Soit donné un ensemble E composé de N pièces de
monnaies. Tester si E peut être divisé en deux sous-
ensembles ayant la même somme.
⇒ 2N cas à traiter nécessitant chacun N-1 sommes.
⇒ Problème difficile.
● Soit donné une matrice Sudoku de taille 9.9 et avec N cases
remplies par l’utilisateur. Tester si cette solution est
correcte.
⇒ N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (2):
● Soit donné un tableau T de taille N. Tester s’il y a K
éléments de T dont la somme est égale à S.
⇒ N!/(N – K)!.K! cas à traiter nécessitant chacun K-1
sommes.
⇒ Problème difficile.
● Soit donné un ensemble E composé de N pièces de
monnaies. Tester si E peut être divisé en deux sous-
ensembles ayant la même somme.
⇒ 2N cas à traiter nécessitant chacun N-1 sommes.
⇒ Problème difficile.
● Soit donné une matrice Sudoku de taille 9.9 et avec N cases
remplies par l’utilisateur. Tester si cette solution est
correcte.
⇒ N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème facile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (3):
● Trouver une solution pour une matrice Sudoku de taille 9.9
ayant N cases vides.
⇒ 9N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème difficile.
● En partant du RDC d’un immeuble composé de M étages, le
but est de déposer N personnes à des étages différents en
faisant le minimum de déplacements de l’ascenseur.
⇒ M cas à traiter nécessitant chacun N tests au maximum.
⇒ Problème facile.
● Que se passe-t-il si ni les N personnes ni l’ascenseur ne se
trouvent au RDC ?
⇒ N ! cas à traiter.
⇒ Problème difficile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (3):
● Trouver une solution pour une matrice Sudoku de taille 9.9
ayant N cases vides.
⇒ 9N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème difficile.
● En partant du RDC d’un immeuble composé de M étages, le
but est de déposer N personnes à des étages différents en
faisant le minimum de déplacements de l’ascenseur.
⇒ M cas à traiter nécessitant chacun N tests au maximum.
⇒ Problème facile.
● Que se passe-t-il si ni les N personnes ni l’ascenseur ne se
trouvent au RDC ?
⇒ N ! cas à traiter.
⇒ Problème difficile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (3):
● Trouver une solution pour une matrice Sudoku de taille 9.9
ayant N cases vides.
⇒ 9N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème difficile.
● En partant du RDC d’un immeuble composé de M étages, le
but est de déposer N personnes à des étages différents en
faisant le minimum de déplacements de l’ascenseur.
⇒ M cas à traiter nécessitant chacun N tests au maximum.
⇒ Problème facile.
● Que se passe-t-il si ni les N personnes ni l’ascenseur ne se
trouvent au RDC ?
⇒ N ! cas à traiter.
⇒ Problème difficile.
Notions élémentaires – Classification des problèmes
Exemples de problèmes décidables (3):
● Trouver une solution pour une matrice Sudoku de taille 9.9
ayant N cases vides.
⇒ 9N cas à traiter nécessitant chacun 8.3 comparaisons.
⇒ Problème difficile.
● En partant du RDC d’un immeuble composé de M étages, le
but est de déposer N personnes à des étages différents en
faisant le minimum de déplacements de l’ascenseur.
⇒ M cas à traiter nécessitant chacun N tests au maximum.
⇒ Problème facile.
● Que se passe-t-il si ni les N personnes ni l’ascenseur ne se
trouvent au RDC ?
⇒ N ! cas à traiter.
⇒ Problème difficile.