INF7440 Conception et analyse d’algorithmes :
Introduction
Paradigme = “Modèle théorique de pensée qui oriente la recherche et la réflexion scientifique”
(Le Petit Larousse 1997)
Paradigme de programmation ≈ Façon d’aborder un problème de programmation, généralement
Slide 1 à l’aide d’un type de langage qui supporte bien certains mécanismes d’abstractions
• Paradigme procédurale ⇒ procédures et sous-routines
• Paradigme orienté objets ⇒ classe d’objets
• Paradigme fonctionnel ⇒ valeurs et fonctions (mathématiques)
Paradigme comme façon de voir le monde
“Quand le seul outil qu’on connait est le marteau, on voit des clous partout! ”
Soit l’algorithme suivant (maximum parmi une série de nombres) :
PROCEDURE max( s: sequence{integer}; i, j: nat ): integer
# PRECONDITION
# i <= j & i IN domain(s) & j IN domain(s)
DEBUT
max <- s[i]
POUR k <- i+1 A j FAIRE
SI s[k] > max ALORS
max <- s[k]
FIN Quel sera le temps d’exécution pour une
Slide 2
FIN séquence s de longueur n?
RETOURNER( max ) Plus précisément, quelle est la complexité
FIN asymptotique de cet algorithme?
Question : Est-il possible de faire mieux, c’est-à-dire d’obtenir un temps d’exécution qui soit
inférieur à O(n) pour une séquence de longueur n = 2k ? Si oui, comment?
1
Solution alternative :
PROCEDURE max( s: sequence{integer}; i, j: nat ): integer
# PRECONDITION
# i <= j & i IN domain(s) & j IN domain(s)
DEBUT
SI i = j ALORS
RETOURNER( s[i] )
SINON
Slide 3 m <- (i+j) / 2
max1 <- max( s[i..m] )
max2 <- max( s[m+1..j] )
SI max1 > max2 ALORS
RETOURNER( max1 )
SINON
RETOURNER( max2 ) Question : Quel sera le temps d’exécution
FIN de cette algorithme pour une séquence s de
FIN longueur n (n = 2k )?
FIN
Sortons maintenant du cadre habituel où tout s’exécute de façon séquentielle.
Supposons que les appels de fonction se fassent en parallèle.
PROCEDURE max( s: sequence{integer}; i, j: nat ): integer
DEBUT
SI i = j ALORS
RETOURNER( s[i] )
SINON
m <- (i+j) / 2
Slide 4 EN PARALLELE
max1 <- max( s[i..m] )
max2 <- max( s[m+1..j] )
FIN
SI max1 > max2 ALORS
RETOURNER( max1 )
SINON
RETOURNER( max2 ) Question : Quel sera alors le temps
FIN d’exécution, en fonction de n = 2k ?
FIN
FIN
2
Autre exemple : trouver la fin d’une liste chaı̂née
Soit une liste chainée séquentielle (voir figure au tableau).
Supposons que chaque noeud de la liste soit sur un processeur différent.
Supposons que chaque noeud possède un pointeur vers le noeud suivant.
Slide 5
Question : Quelle sera la complexité asymptotique du temps d’exécution pour que chaque
pointeur suivant indique le dernier élément de la liste?
Soit l’algorithme suivant :
TANTQUE il existe un noeud tel que suivant != null
ET suivant->suivant != null FAIRE
POUR chacun des processeurs EN PARALLELE FAIRE
SI (suivant != null) ET (suivant->suivant != null) ALORS
tmp <- suivant->suivant
Slide 6 suivant <- tmp
FIN
FIN
FIN
Question : Quelle est alors la complexité asymptotique du temps d’exécution, pour une liste de
longueur n = 2k ?
3
Introduction à la programmation concurrente et parallèle
Ce qu’est la programmation concurrente et parallèle
Programme séquentiel
= programme défini par une séquence d’actions
⇒ une instruction après l’autre
= Un processus, une tâche, un thread
Slide 7
thread = fil d’exécution
Programme concurrent
= programme qui contient plusieurs processus (ou thread s) qui coopèrent
Coopération ⇒ Communication, échange d’information
Deux principales façons de communiquer :
• Par l’intermédiaire de variables partagées
• Par l’échange de messages et de signaux
Slide 8
Niveau matériel (hardware)
Différentes classes de matériel
• Machine uniprocesseur : boı̂te contenant un seul processeur
• Multi-processeurs : boı̂te contenant plusieurs processeurs
– Communication via un bus
• Multi-ordinateurs : plusieurs boı̂tes inter-connectées
– Communication via un réseau
4
Différents types d’applications concurrentes
Application multi-contextes (multi-threaded ) = contient plusieurs thread s
Note importante : On considère généralement un thread comme étant un processus léger
(lightweight thread )
Slide 9
Utilisations : Pour mieux organiser/structurer une application (plus grande modularité)
• Système d’exploitation multi-tâches
• Fureteurs multi-tâches
• Interface personnes-machines vs. application
• ...
Application parallèle = chaque processus s’exécute sur son propre processeur
Utilisations : Pour résoudre plus rapidement un problème ou pour résoudre un problème plus
gros
• Prévisions météorologiques
Slide 10
• Prospection minière
• Physique moderne
• Bio-informatique (génomique)
• ...
5
Application distribuée = les processus communiquent entre eux par l’intermédiaire d’un réseau
(⇒ délais plus longs)
Utilisations :
Slide 11
• Serveurs de fichiers
• Accès à distance à des banques de données
Emphase du cours INF7440 :
Slide 12 Conception et analyse des algorithmes
séquentiels et parallèles