UNITÉ 1 : FONDAMENTAUX DE L'ALGORITHME

Structure

1.0 Objectifs
1.1 Introduction à l'algorithme
1.2 Propriétés de l'algorithme
1.3 Notations algorithmiques
1.4 Conception et développement d'un algorithme
1.5 Quelques exemples simples
1.6 Summary
1.7 Keywords
1.8 Réponses pour vérifier vos progrès
1.9 Exercices de fin d'unité et réponses
1. 10 lectures suggérées

1.0 OBJECTIVES

À la fin de cette unité, vous serez capable de

•Fondamentaux des algorithmes ainsi que la notation.

Les différentes propriétés d'un algorithme.
•Comment écrire un algorithme ou un pseudo-code pour un problème quelconque.
Algorithmes pour une variété de problèmes.

1.1 Introduction à l'algorithme :

Un algorithme, nommé d'après le mathématicien persan du neuvième siècle al-Khowarizmi, est

simplement un ensemble de règles utilisées pour effectuer des calculs, soit à la main, soit plus couramment
Même l'ancien grec a utilisé un algorithme qui est communément connu sous le nom de
L'algorithme d'Euclide pour calculer le plus grand commun diviseur (pgcd) de deux nombres.

Un algorithme est un outil pour résoudre un problème donné. Avant d'écrire un programme pour résoudre
le problème donné, un bon programmeur conçoit d'abord et écrit l'algorithme concerné,
l'analyse, le perfectionne autant de fois que nécessaire et parvient à la forme finale 'efficace'
cela fonctionne bien pour toutes les données d'entrée valides et résout le problème dans le plus court délai possible
temps, en utilisant un espace mémoire minimum.

Définition d'algorithme : L'algorithme est défini comme un ensemble d'éléments non ambigus.
des instructions se produisant dans une séquence spécifique et un tel algorithme devrait produire
sortie pour un ensemble donné d'entrées dans un temps fini.

1
L'exigence de base est que l'énoncé du problème doit être très clair.
car certains concepts peuvent être clairs pour quelqu'un et ne pas l'être pour un autre.
Par exemple, calculer les racines d'une équation quadratique peut être clair pour les personnes qui
savoir sur les mathématiques, mais cela peut être flou pour quelqu'un qui ne l'est pas.

Un bon algorithme est comme un couteau bien affûté - il fait exactement ce qu'il est censé faire avec un
quantité minimale d'effort appliqué. Utiliser le mauvais algorithme pour résoudre un problème est comme
essayer de couper un steak avec un tournevis. Vous obtenez un résultat, mais vous y auriez passé
plus d'efforts que nécessaire.

Tout algorithme devrait se composer des éléments suivants :

L'éventail des entrées pour lesquelles un algorithme fonctionne parfaitement.

2. Output : The algorithm should always produce correct results and it should halt.
3. Une séquence finie d'instructions qui transforme l'entrée donnée en la sortie désirée
output (Algorithm + Programming lanuage)

En général, l'algorithme sera écrit en énoncés simples en anglais accompagnés de simples

expressions mathématiques. La définition d'un algorithme peut être illustrée en utilisant le
figure 1.1

Entrée
↓
Problème -- Algorithme Ordinateur Sortie

( Fig 1.1 Notion de l'Algorithme )

Toute méthode systématique pour calculer le résultat a peut être considérée comme un algorithme.
Par exemple, les méthodes que nous apprenons à l'école pour additionner, multiplier, diviser
Les nombres peuvent être considérés comme des algorithmes. En regardant les étapes spécifiées, nous pouvons
atteindre le résultat sans même réfléchir. Même une recette de cuisine peut être considérée
comme un algorithme si les étapes :
1. Décrivez précisément comment préparer un certain plat.
2. Décrivez la qualité exacte à utiliser.
3. Détails des instructions concernant quels articles ajouter ensuite à quel moment ? Combien de temps pour
cuisiner ?

1.2 Propriétés des algorithmes :

Chaque algorithme doit satisfaire certaines propriétés. Les différentes propriétés ou

les caractéristiques d'un algorithme sont :
1. Precise and unambiguous (Definiteness) :An algorithm must be simple, precise
et sans ambiguïté c'est-à-dire qu'il ne devrait y avoir aucune ambiguïté (doute) dans les instructions
ou des déclarations spécifiées pour résoudre un problème. Chaque instruction utilisée dans le
L'algorithme doit être clair et sans ambiguïté.

2
 2. Plage des entrées : La plage des entrées pour lesquelles l'algorithme produit le résultat souhaité
le résultat doit être spécifié.
3. Maintenir l'ordre : Les instructions à chaque étape d'un algorithme sont I
ordre spécifié c'est-à-dire qu'ils seront exécutés dans l'ordre (c'est-à-dire l'un après l'autre). Le
les instructions ne peuvent pas être écrites dans un ordre aléatoire.
4. Fini et correct : Ils doivent résoudre le problème en un certain nombre fini d'étapes.
et produire le résultat approprié. La plage d'entrée pour laquelle l'algorithme
fonctionne parfaitement devrait être précisé.
5. Résiliation : l'algorithme ecac devrait se terminer.
6. Plusieurs algorithmes peuvent exister pour résoudre un problème donné et la vitesse d'exécution de
chaque algorithme peut être différent. (par exemple, pour trier divers algorithmes de tri à bulles)
tri, le tri par insertion peut être utilisé).
Un algorithme peut être représenté de plusieurs manières différentes.
8. Un algorithme pour un problème donné peut être basé sur des idées très différentes (par exemple,
Pour trier, plusieurs méthodes existent, telles que le tri à bulles, le tri par insertion, le tri par base, etc.
et peuvent avoir des vitesses d'exécution différentes.

1.3 Notations algorithmiques

Les notations suivantes sont généralement utilisées lors de l'écriture de tout algorithme.
1. Write the word algorithm and write what is the main objective of the algorithm.
Par exemple,
Algorithme Aire_du_cercle
2. Puis une brève description de ce qui est réalisé à l'aide de l'algorithme ainsi que le
Les entrées de l'algorithme doivent être fournies. Par exemple,
Description : “The algorithm computes the area of circle using the input value
radius
3. Chaque instruction devrait être dans une étape séparée et le numéro d'étape doit être
ce qui est accompli à chaque étape doit être décrit brièvement et a
à être enfermé dans les crochets (que nous appelons commentaire). Pour
exemple, pour trouver la surface d'un cercle, nous pouvons écrire :
Étape 2 : [ Trouver la superficie du cercle ]
Zone 3,142*rayon*rayon.
4. Après que toutes les opérations sont terminées, l'algorithme doit être arrêté, ce qui indique
la fin logique de l'algorithme. Par exemple, la dernière étape de l'algorithme sera
être
Step4: [Finished]
sortie.

1.4 Conception et développement d'un algorithme

Les étapes fondamentales pour résoudre tout problème donné qui conduit à l'achèvement
le développement d'un algorithme, sont les suivants :

3
 1. Énoncé du problème.
2. Développement d'un modèle mathématique
3. Conception de l'algorithme
4. Mise en œuvre
5. Analyse de l'algorithme pour sa complexité temporelle et spatiale
6. Test et débogage de programme
7. Documentation.

1. Énoncé du problème.
Avant d'essayer de résoudre un problème donné, nous devons comprendre précisément le
déclaration de l'algorithme. Il y a encore plusieurs façons de le faire. Nous pouvons lister tous les
exigences de spécification logicielle et essayez de poser plusieurs questions et d'obtenir le
réponses. Cela nous aiderait à comprendre le problème plus clairement et à éliminer tout
ambiguïté.

2. Développement d'un modèle mathématique

Ayant compris le problème, la prochaine étape est de chercher un modèle mathématique,

lequel est le mieux adapté au problème donné. C'est une étape très importante dans l'ensemble
processus de solution et cela devrait être pensé de manière considérable. En fait, le choix de la
le modèle a encore un long chemin à parcourir dans le processus de développement.
Nous devons penser à
quel modèle mathématique est le mieux adapté à un problème donné ?
- Y a-t-il des modèles qui ont déjà été sélectionnés pour résoudre un problème qui
ressemblerait à l'actuel?

3. Conception de l'algorithme

Comme nous sommes à l'aise avec la spécification et le modèle du problème à ce stade,

nous pouvons passer à l'écriture d'un algorithme.

4. Mise en œuvre

À cette étape, des structures de données appropriées doivent être sélectionnées et codées dans un langage cible.
Le choix d'une langue cible est une étape très importante pour réduire les complexités impliquées.
en codage.

5. Analyse de l'algorithme pour sa complexité temporelle et spatiale

Nous utiliserons, dans cette section, un certain nombre de termes comme complexité, analyse, efficacité,
etc. Tous ces termes se réfèrent à la performance d'un programme. Notre travail ne peut pas s'arrêter une fois
nous écrivons l'algorithme et le codons en C, C++ ou Java. Nous devrions nous inquiéter de
espace3 et les exigences de timeing aussi. Pourquoi ? Il y a plusieurs raisons à cela et donc nous
commençons par la complexité temporelle.
En termes simples, la complexité temporelle d'un programme est la quantité de temps informatique dont il a besoin pour
exécuter un programme.

4
La complexité spatiale d'un programme est la quantité de mémoire nécessaire pour exécuter un programme.

6. Test et débogage de programmes

Après avoir implémenté l'algorithme dans un langage spécifique, il est maintenant temps de l'exécuter. Après
l'exécution du programme devrait produire le résultat souhaité. Le test ne concerne rien à propos de la
vérification du programme pour sa justesse c'est-à-dire si la sortie du programme est
correct ou pas. En utilisant différentes valeurs d'entrée, on peut vérifier si la sortie désirée est
obtenu ou non. Toute erreur logique peut être identifiée par des tests de programme. En général
Le débogage fait partie des tests. De nombreux outils de débogage existent pour tester.
programme pour sa correction.

7. Documentation

Notez que la documentation n'est pas la dernière étape. La documentation devrait exister pour
comprendre le problème jusqu'à ce qu'il soit testé et débogué. Pendant la conception et
La phase d'implémentation, la documentation est très utile. Pour comprendre la conception ou
code, des commentaires appropriés doivent être donnés. Autant que possible, le programme doit être autonome.
documenté. Ainsi, l'utilisation de noms de variables appropriés et de structures de données joue un rôle très important
rôle lors de la documentation. Il est très difficile de lire et de comprendre la logique des autres et
La documentation permet aux individus de comprendre les programmes écrits par
les autres personnes.

1.5 Quelques exemples simples

[Link] pour trouver le PGCD de deux nombres. (Algorithme d'Euclide).

ALGORITHME : pgcd(m,n)
//But : Trouver le PGCD de deux nombres
//Description : This algorithm computes the GCD of two non-negative and non-zero
valeurs acceptées comme paramètres.
Deux valeurs non négatives et non nulles m et n
PGCD de m et n

Étape 1 : si n = 0, retourner m et s'arrêter

Étape 2 : Divisez m par n et assignez le reste à r.

Étape 3 : Assignez la valeur de n à m et la valeur de r à n

Étape 4 : Allez à l'étape 1.

2. Algorithme pour trouver le PGCD de deux nombres. (Méthode de vérification des entiers consécutifs).

5
 ALGORITHME : pgcd(m,n)
//But : Trouver le PGCD de deux nombres
Cet algorithme calcule le PGCD de deux nombres non négatifs et non nuls.
valeurs acceptées comme paramètres.
Deux valeurs non négatives et non nulles m et n
PGCD de m et n

Étape 1 : [trouver le minimum de m et n]

r min(m,n);
Étape 2 : [trouver le pgcd en vérifiant les entiers consécutifs]
Tant que(1)
si (m mod r = 0 et n mod r = 0)
casser;
fin tant que
Étape 3 : retourner r.

3. Algorithme pour trouver le PGCD de deux nombres. (Méthode de soustraction répétée)

ALGORITHME : pgcd(m,n)
//Purpose :To find the GCD of two numbers
//Description : This algorithm computes the GCD of two non-negative and non-zero
valeurs acceptées comme paramètres.
Deux valeurs non négatives et non nulles m et n
PGCD de m et n

Step1 : [If one of the two numbers is zero, return non-negative number a the GCD]
si (m=0) retourne n;

si (n=0) retourner m;
Étape 2 : [Répétez l'étape 2 tant que m et n sont différents]
Tant que (m!=n)
si(m>n)
m m-n;
sinon n n-m;
fin si
fin tandis que
Étape 3 : [terminé : retourner le PGCD comme sortie]
retourner m;

Remarque : Le même problème peut être résolu de plusieurs manières (par exemple, Algorithme 1, 2 et 3).

6
4. Algorithme pour générer des nombres premiers en utilisant la méthode du crible d'Ératosthène. (Pseudo
code)

ALGORITHME SIEVE_PRIME(n)
//But : Générer des nombres premiers entre 2 et n
//Description :This algorithm generates prime numbers using sieve method
Un entier positif n >= 2
Nombres premiers <= n

Étape 1 : [ Générer la liste des entiers de 2 à n ]

pour p 2 à n faire
a[p] p
fin pour
Étape 2 : [Éliminer les multiples de p entre 2 et n]
pour p 2 à √n faire
si (a[p] != 0 )
je p*p
tandis que ( i <= n )
a[i] 0
je je + p
fin tant que
fin si
fin pour
Étape 3 : [Obtenez les nombres premiers en copiant les éléments non nuls]
m 0
pour p 2 à n faire
si (a[p] != 0 )
b[m] a[p];
m m+1
fin si
fin pour
Step 4: [Output the prime numbers between 2 to n ]
pour i 0 à m-1
write b[i]
fin pour
Étape 5 : [Terminé]
Sortie

[Link] pour trouver le nombre de chiffres dans une représentation binaire d'un donné
entier décimal
Algorithme : Binaire(n)
//But : Compter le nombre de chiffres dans une représentation binaire d'un donné
entier décimal.
n : un entier décimal positif.

7
 //Output :Number of digits in a binary representation of a given positive decimal
entier.

Comptez 1;
Tant que ( n > 1)
Comptez Compter + 1
n n/2
fin de boucle
retourner le compte

Vérifiez vos progrès

Qu'est-ce qu'un algorithme ? Expliquer la notion d'algorithme ?

2. Quelles sont les différentes propriétés d'un algorithme ?
3. Expliquer la procédure de génération des nombres premiers en utilisant la méthode "Crible d'Ératosthène".
ératosthène et écrire l'algorithme pour cela.
4. Expliquer les étapes impliquées dans la conception et le développement d'un algorithme.

1.6 SUMMARY

•Algorithme : Un algorithme est une séquence d'instructions non ambiguës pour

résoudre un problème dans un temps fini. Une entrée dans un algorithme spécifie un
instance du problème que l'algorithme résout.
•L'algorithme peut être spécifié dans un langage naturel ou un pseudo-code ; ils peuvent aussi
être mis en œuvre sous forme de programmes informatiques.
Un bon algorithme est généralement le résultat d'efforts répétés et de retravaux.
•Le même problème peut souvent être résolu par plusieurs algorithmes. Par exemple, trois
des algorithmes ont été donnés pour calculer le plus grand commun diviseur de deux
entiers : l'algorithme d'Euclide, l'algorithme de vérification des entiers consécutifs, et
soustraction répétée.

1.7 KEYWORDS

Algorithme : C'est une séquence d'instructions claires pour résoudre un problème de manière finie.
durée.
Complexité temporelle : C'est le temps nécessaire pour exécuter un programme.
Complexité spatiale : C'est la quantité de mémoire nécessaire pour exécuter un programme.

1.8 RÉPONSES POUR VÉRIFIER VOTRE PROGRÈS

1. 1.1
2. 1.2

8
 3.1.5(4thalgorithme)
4. 1.4

EXERCICES ET RÉPONSES UNIT-EBD

1. Trouvez le pgcd(31415,14142) en appliquant l'algorithme d'Euclide.

2. Que fait l'algorithme d'Euclide pour une paire de nombres dont le premier nombre
est plus petit que le deuxième ? Quel est le plus grand nombre de fois que cela peut
se produire pendant l'exécution de l'algorithme sur une telle entrée ?
3. Écrivez un algorithme pour trouver le pgcd de deux nombres en utilisant la soustraction répétée
méthode. Trouvez le pgcd(36,171) en utilisant la soustraction répétée
4. Écrivez un algorithme pour trouver le nombre de chiffres dans une représentation binaire d'un
donné un entier décimal. Tracez-le pour l'entrée 255.
Réponses : VOIR

1.5 (1stalgorithme
2. 1.5 (1stalgorithme) [ Indice : trouvez le pgcd(12,24) ]
3. 1.5 (3rd algorithme
4. 1.5 (5thalgorithme

1.9 SUGGESTED READINGS

[Link] à la conception et à l'analyse des algorithmes par Anany Levitin

[Link], Alfred V., "La conception et l'analyse des algorithmes informatiques".
3. Analyse et conception d'algorithmes par A M Padma Reddy.

9
 MODULE-1, UNITÉ 2 ANALYSE DE L'EFFICACITÉ DES ALGORITHMES

Structure
1.0 Objectifs
1.1 Introduction à l'algorithme
1.2 Propriétés de l'algorithme
1.3 Notations algorithmiques
1.4 Conception et développement d'un algorithme
1.5 Quelques exemples simples
1.6 Summary
1.7 Keywords
1.8 Réponses pour vérifier vos progrès
1.9 Exercices de fin d'unité et réponses
1. 10 lectures suggérées

1.0 OBJECTIFS
À la fin de cette unité, vous serez capable de

Efficacité d'un algorithme.

Complexité spatiale.
Complexité temporelle.
Mesure de la performance
Besoin de complexité temporelle
Efficacités dans le pire des cas, le meilleur des cas et le cas moyen.
•Notations asymptotiques.
Grand-O (O)
Grand-Omega (Ω)
Grand-Thêta (θ)
•Complexités pratiques.
Analyse des algorithmes itératifs.
Analyse des algorithmes récursifs.

1.1 INTRODUCTION
Deux façons importantes de caractériser l'efficacité d'un algorithme sont son espace
complexité et complexité temporelle. La complexité temporelle d'un algorithme concerne la détermination
une expression du nombre d'étapes nécessaires en fonction de la taille du problème. Puisque le
la mesure du nombre de pas est quelque peu grossière, on ne vise pas à obtenir un pas exact
compter. Au lieu de cela, on essaie seulement d'obtenir des bornes asymptotiques sur le nombre d'étapes. Asymptotique
l'analyse utilise la notation O (Grand Oh). Deux autres constructions de notation utilisées par
les informaticiens dans l'analyse des algorithmes sont la notation Θ (Theta majuscule) et Ω (Omega majuscule)
Notation Omeg

10
1.2 Complexité spatiale
La complexité spatiale d'un programme est la quantité de mémoire qui peut être nécessaire pour s'exécuter.
un programme.
La mémoire principale d'un ordinateur est une ressource importante pour le bon
exécution d'un programme. Sans une mémoire suffisante, soit le programme fonctionne
lentement ou peut ne pas fonctionner complètement. Par conséquent, l'exigence exacte en mémoire pour un
le programme doit être en avance.
2. Lorsque nous concevons un programme, nous devons veiller à ce que les besoins en mémoire soient maintenus au minimum.
minimum afin que même les ordinateurs avec moins de mémoire puissent exécuter le programme.
De nos jours, les systèmes d'exploitation s'occupent de l'utilisation efficace de la mémoire.
basé sur le concept de mémoire virtuelle ou de liaison et de chargement dynamique.

1.2.1 Analyse de la complexité spatiale

Les composants suivants sont importants pour calculer les exigences en matière d'espace :
Espace d'instructions
C'est l'espace nécessaire pour stocker le code machine généré par le compilateur.
Généralement, le code objet sera placé dans le segment de code.

Espace de données
L'espace nécessaire pour les constantes, les variables statiques, les variables intermédiaires, dynamiques
variables etc. Ceci n'est rien d'autre que l'espace segment de données.

Espace de pile
Pour stocker l'adresse de retour, les valeurs de retour, etc. Pour stocker ces détails, un segment de pile
sera utilisé.

1.2.2 Comment calculer la complexité spatiale ?

Avant de passer à un exemple spécifique, nous devons comprendre l'importance de la

la taille de l'entrée, c'est-à-dire n. en général, chaque problème sera associé à n. cela peut faire référence
à

Nombre de villes - dans le problème du voyageur de commerce.

•Nombre d'éléments – dans le problème de tri et de recherche.
•Nombre de villes – problème de coloration de la carte.
•Nombre d'objets – problème du sac à dos.
Lorsqu'un problème est indépendant de n, alors l'espace de données occupé par le
l'algorithme/le programme peut être considéré comme zéro. Commençons par quelques problèmes simples
qui sont de type itératif.

EXEMPLE : 1. Trouver la moyenne de trois nombres.

Vide principal()
{
int a,b,c,moyenne;
scanf("%d %d%d", a, b, c);

11
moyenne=(a+b+c)/3;
printf("la moyenne est=%d", avg);
}

Programme pour illustrer la complexité spatiale.

Étant donné que a, b, c et avg sont toutes des variables entières, l'espace occupé par elles est
=4*sizeof(int)
=4*2octets
=8bytes
L'espace occupé par la constante 3 est = 1*2 octets.
Ainsi, l'espace total est = 8 + 2 = 10 octets.

1.3 Complexité temporelle

C'est le temps qu'un programme ou un algorithme prend pour s'exécuter. C'est-à-dire à quelle vitesse un
l'algorithme s'exécute. Notez que le temps pris par un programme pour la compilation n'est pas inclus dans
le calcul.
Normalement, les chercheurs accordent plus d'attention à l'efficacité temporelle qu'à l'efficacité spatiale.
Parce que gérer les problèmes de mémoire est plus facile que le temps.

1.4 NOTATIONS ASYMPTOTIQUES

Deux façons importantes de caractériser l'efficacité d'un algorithme sont son espace
complexité et complexité temporelle. La complexité temporelle d'un algorithme concerne la détermination
une expression du nombre d'étapes nécessaires en fonction de la taille du problème. Puisque le
la mesure du nombre de pas est quelque peu approximative, on ne vise pas à obtenir un nombre de pas exact
compter. Au lieu de cela, on essaie seulement d'obtenir des limites asymptotiques sur le nombre d'étapes. Asymptotique
l'analyse utilise la notation O (Grand Oh). Deux autres constructions notationnelles utilisées par
Les scientifiques informatiques dans l'analyse des algorithmes sont la notation Θ (Big Theta) et Ω (Big Omega)
Notation Oméga.
L'évaluation de la performance d'un algorithme est obtenue en totalisant le nombre de
occurrences de chaque opération lors de l'exécution de l'algorithme. La performance d'un
L'algorithme est évalué en fonction de la taille de l'entrée n et doit être considéré modulo a.
constante multiplicative.

Les notations suivantes sont des notations couramment utilisées dans l'analyse de la performance et servent à
caractériser la complexité d'un algorithme.

Notation Θ (même ordre)

Cette notation limite une fonction à des facteurs constants. On dit que f(n) = Θ(g(n)) si cela
il existe des constantes positives0,c1etc2de sorte que à droite de n0the value off(n) always lies

12
entre1g(n) et c2g(n) inclus.

Dans la notation ensembliste, nous écrivons comme suit :

Θ(g(n)) = {f(n) : il existe des constantes positives c1,c1, etn0tel que 0 ≤ c1g(n) ≤ f(n)
≤c2g(n) pour tout n ≥ n0}

On dit que isg(n) est une borne asymptotiquement serrée pour f(n).

Graphiquement, pour toutes les valeurs de n à droite de n0la valeur de f(n) se situe à ou au-dessus de c1g(n)
et à ou en dessous2g(n). En d'autres termes, pour tout n ≥ n0la fonction f(n) est égale à g(n) à
dans un facteur constant. Nous disons que g(n) est une limite asymptotiquement serrée pour f(n).

Dans la terminologie des ensembles, f(n) est dit être un membre de l'ensemble Θ(g(n)) de fonctions. Dans d'autres
mots, parce que O(g(n)) est un ensemble, nous pourrions écrire

f(n)∈Θ(g(n))

pour indiquer que f(n) est un membre de Θ(g(n)). Au lieu de cela, nous écrivons

f(n) = Θ(g(n))

pour exprimer la même notation.

Historiquement, cette notation est "f(n) = Θ(g(n))" bien que l'idée que f(n) soit égal à
quelque chose appelé Θ(g(n)) est trompeur.

Exemple:n2/2 − 2n= (n2), avec1= 1/4,c2= 1/2, etn0= 8.

Notation O (Bornes Supérieures)

13
Cette notation donne une borne supérieure pour une fonction avec un facteur constant. Nous
writef(n) = O(g(n)) s'il existe des constantes positives n0 et tel que à droite de n0, le
La valeur off(n) se situe toujours sur ou en dessous de g(n).

Dans la notation ensembliste, nous écrivons comme suit : Pour une fonction donnée g(n), l'ensemble des fonctions

Ο(g(n)) = {f(n) : il existe des constantes positives c et n}0tel que 0 ≤ f(n) ≤ c g(n) pour
tout n ≥ n0}

Nous disons que la fonction g(n) est une borne supérieure asymptotique pour la fonction f(n). Nous utilisons
La notation O pour donner une borne supérieure à une fonction, à un facteur constant près.

Graphiquement, pour toutes les valeurs de n à droite de n0, la valeur de la fonction f(n) est sur ou
en dessous de g(n). Nous écrivons f(n) = O(g(n)) pour indiquer qu'une fonction f(n) est un membre de l'ensemble
Ο(g(n)) c'est-à-dire

f(n)∈Ο(g(n))

Notez que f(n) = Θ(g(n)) implique que f(n) = Ο(g(n)), puisque la notation Θ est une notation plus forte.
que la notation O.

Exemple : 2n2= O(n3), avecc= 1 etn0= 2.

De manière équivalente, nous pouvons également définir fis d'ordre gas comme suit :

Si f(n) et g(n) sont des fonctions définies sur les entiers positifs, alors f(n) est Ο(g(n)) si et seulement si
uniquement s'il y a ac > 0 et ann0> 0 tel que

|f(n)| ≤ |g(n)| pour tout n ≥ n0

14
Note historique : La notation a été introduite en 1892 par le mathématicien allemand Paul
Bachman.

Notation Ω (Borne Inférieure)

Cette notation donne une borne inférieure pour une fonction à un facteur constant près. Nous écrivons f(n)
= Ω(g(n)) s'il existe des constantes positives n0et tel que à droite de n0, la valeur
off(n) est toujours en dessous ou au-dessus de g(n).

Dans la notation ensembliste, nous écrivons comme suit : Pour une fonction donnée g(n), l'ensemble des fonctions

Ω(g(n)) = {f(n) : il existe des constantes positives c et n0tel que 0 ≤ c g(n) ≤ f(n) pour
tout n ≥ n0}

Nous disons que la fonction g(n) est une borne inférieure asymptotique pour la fonction f(n).

L'intuition derrière la notation Ω est montrée ci-dessus.

Exemple : √n = (lgn), avec c = 1 et n0= 16.

1.4.1 Analyse d'algorithmes

La complexité d'un algorithme est une fonction g(n) qui donne la limite supérieure de la
nombre d'opérations (ou temps d'exécution) effectuées par un algorithme lorsque la taille de l'entrée est.

Il existe deux interprétations de la borne supérieure.

Complexité du pire des cas

Le temps d'exécution pour une entrée de taille donnée sera inférieur à la borne supérieure.
sauf peut-être pour certaines valeurs de l'entrée où le maximum est atteint.

15
 Complexité de cas moyen
Le temps d'exécution pour une entrée de taille donnée sera le nombre moyen de
opérations sur tous les cas de problème pour une taille donnée.

Parce que, il est assez difficile d'estimer le comportement statistique de l'entrée, la plupart des
le temps nous contentons d'un comportement de pire cas. La plupart du temps, la complexité
ofg(n) est approché par sa famille o(f(n)) où f(n) est l'un des suivants
fonctions.n(complexité linéaire), logn(complexité logarithmique),nunoù a ≥ 2
(complexité polynomiale),an(complexité exponentielle).

1.4.2 Optimalité

Une fois la complexité d'un algorithme estimée, la question se pose de savoir si cela
un algorithme est optimal. Un algorithme pour un problème donné est optimal si sa complexité
atteint la borne inférieure de tous les algorithmes résolvant ce problème. Par exemple, tout
l'algorithme résolvant le problème de "l'intersection de n segments" s'exécutera à
le moindres2des opérations dans le pire des cas même si cela ne fait rien d'autre que d'imprimer la sortie. Cela est
abrégé en disant que le problème a Ω(n2) complexité. Si l'on trouve un O(n2)
algorithme qui résout ce problème, il sera optimal et de complexité Θ(n2).

1.5 Complexités Pratiques

La théorie de la complexité computationnelle est une branche de lathéorie de

calculdansinformatique théoriqueetmathématiquesqui se concentre sur
classifiantproblèmes computationnelsselon leur difficulté inhérente. Dans ce contexte,
un problème computationnel est compris comme une tâche qui est en principe susceptible d'être
résolu par un ordinateur (ce qui signifie essentiellement que le problème peut être formulé par un ensemble de)
instructions mathématiques). De manière informelle, un problème computationnel consiste en un problème
instances et solutions à ces cas de problème. Par exemple,test de primalitéest le
problème de déterminer si un numéro donné estprimeor not. The instances of this
les problèmes sontnombres naturels, et la solution à une instance est oui ou non basée sur
si le nombre est premier ou non.

Un problème est considéré comme intrinsèquement difficile si sa solution nécessite des ressources significatives,
quels que soient les algorithmes utilisés. La théorie formalise cette intuition en introduisant
mathématiquemodèles de calculto study these problems and quantifying the amount
des ressources nécessaires pour les résoudre, telles que le temps et le stockage. D'autres mesures de complexité
sont également utilisés, tels que le montant de la communication (utilisé danscommunication
complexité), le nombre de portesdans un circuit (utilisé danscomplexité de circuit) et le numéro
de processeurs (utilisés danscalcul parallèleL'un des rôles de la complexité computationnelle
la théorie consiste à déterminer les limites pratiques de ce queordinateurspeut et ne peut pas faire.

16
Des domaines étroitement liés en informatique théorique sontanalyse de
algorithmesetthéorie de la calculabilitéUne distinction clé entre l'analyse des algorithmes
et la théorie de la complexité computationnelle est que la première est consacrée à l'analyse de la
quantité de ressources nécessaires à un algorithme particulier pour résoudre un problème, tandis que le
la lettre pose une question plus générale sur tous les algorithmes possibles qui pourraient être utilisés pour
Résoudre le même problème. Plus précisément, il essaie de classifier les problèmes qui peuvent ou ne peuvent pas être
résolu avec des ressources correctement restreintes. En retour, imposer des restrictions sur le
les ressources disponibles sont ce qui distingue la complexité computationnelle de la calculabilité
theory: the latter theory asks what kind of problems can, in principle, be solved
algorithmiquement.
1.5.1 Problèmes de fonction

Aproblème de fonctionest un problème computationnel où une seule sortie (d'unfonction totale)

est attendu pour chaque entrée, mais la sortie est plus complexe que celle d'undécision
problème, c'est-à-dire, ce n'est pas juste oui ou non. Des exemples notables incluent le vendeur itinérant
problèmeet leproblème de factorisation entière.
Il est tentant de penser que la notion de problèmes de fonction est beaucoup plus riche que la notion
des problèmes de décision. Cependant, ce n'est pas vraiment le cas, car les problèmes de fonction peuvent être
reformuler en problèmes de décision. Par exemple, lemultiplicationde deux entiers peut être
exprimé comme l'ensemble des triplets (a,b,c) tels que la relation a×b=cholds. Décider
le fait de savoir si un triplet donné est membre de cet ensemble correspond à la résolution du problème de

multiplier deux nombres.

1.5.2 Mesurer la taille d'une instance
Pour mesurer la difficulté de résoudre un problème computationnel, on peut souhaiter voir comment
combien de temps le meilleur algorithme nécessite pour résoudre le problème. Cependant, le temps d'exécution
peut, en général, dépendre de l'instance. En particulier, les instances plus grandes nécessiteront plus
temps pour résoudre. Ainsi, le temps nécessaire pour résoudre un problème (ou l'espace requis, ou tout
la mesure de la complexité) est calculée comme une fonction de la taille de l'instance. Ceci est
généralement considéré comme la taille de l'entrée en bits. La théorie de la complexité s'intéresse à la manière dont
les algorithmes évoluent avec une augmentation de la taille de l'entrée. Par exemple, dans le problème de la recherche de

si un graphe est connexe, combien de temps supplémentaire cela prend-il pour résoudre un problème pour un
un graphe avec 2n sommets par rapport au temps pris pour un graphe avec n sommets?

Si la taille d'entrée est n, le temps pris peut être exprimé comme une fonction de n. Étant donné que le temps
prises sur différentes entrées de même taille peuvent être différentes, le temps dans le pire des cas
La complexité T(n) est définie comme le temps maximum pris pour tous les entrées de taille n. Si T(n)
est un polynôme en n, alors l'algorithme est dit être unpolynôme
[Link] thèse de Cobhamdit qu'un problème peut être résolu avec un montant raisonnable

17
de ressources si elle admet un algorithme en temps polynomial.

1.6 Mesure de performance des algorithmes simples

[Link] la complexité temporelle des algorithmes suivants
a.)Algorithme :simple
pour (i=0; i<=n*n; i++)
pour (j=i+1; j<i; j++)
si(i<j){
sum++;}

Solfor (i=1; i<=n*n; i++) Exécuté n*n fois

pour (j=0; j<i; j++) Exécuté <= n*n fois
somme++; O(1)
Temps d'exécution : O(n4)

2. Algorithme pour la multiplication de matrices

Algorithme matmul(a[0…n-1],b[0..n-1])
deux matrices n par n

matrice c=ab

Pour moi 0 à n-1 faire

Pour j 0 à n-1 faire

C[I,j] 0
Pour k de 0 à n-1 faire

C[I,j] c[I,j]+a[I,k]+b[k,j]
Rendre c
n1n1n1
La complexité temporelle de cet algorithme est donnée par M(n)= 1 =n3
je=0j =0k =0

[Link] pour l'unicité des éléments

Algorithm : uniquelement(a[].n)

//input : n – number of elements and a- an array consisting of n elements

Pour i 0 à n-2 faire

18
Pour i i+1 à n-1 faire
Si(a[i]=a[j])
Retourner 0;

Fin si
Retourner 1;
n -2n -1
Efficacité dans le pire des cas : ∑ ∑1 = n(n−1) / 2<=n2
je=0j =j e +1

T(n)€O(n2)
Efficacité dans le meilleur des cas : si a[0]=a[1], alors l'opération de base ne sera exécutée qu'une seule fois.

Donc t(n) ∈ Ω(1)

Remarque : Pour résoudre l'efficacité temporelle des algorithmes non récursifs, utilisez la formule
result=upper bound-lower bound+1 in each summation.

Vérifiez vos progrès

1. Expliquer le concept de complexité spatiale

2. Que signifie la complexité temporelle ? Pourquoi est-elle nécessaire ?

3. écrivez une note sur les notations asymptotiques.

4. Trouvez la complexité temporelle de l'algorithme de multiplication de matrices.

SUMMARY:
Complexité spatiale : La complexité spatiale d'un programme est la quantité de mémoire qui peut
être obligé d'exécuter un programme.
Complexité temporelle : c'est le temps nécessaire pour exécuter un programme.

Notations asymptotiques – représentation de la complexité temporelle dans l'une des notations (grande

oh, grand oméga, grand thêta).

1.5 KEYWORDS
Opération de base – une opération qui est exécutée un plus grand nombre de fois dans le programme
(partie logique). Généralement présente dans la boucle la plus interne (partie) de l'algorithme/programme.

19
1.6 RÉPONSES POUR VÉRIFIER VOTRE PROGRÈS

1. 1.2
2. 1.3
3. 1.4
4. 1.6
1.7 EXERCICES DE FIN D'UNITÉ ET RÉPONSES
1. Trouvez la complexité temporelle de l'algorithme de transposition d'une matrice

2. Write a note on best case, average case , worst case in a program with example

VOIR
1. 1.4
2. 1.3

1.8SUGGESTED READINGS
1. Introduction à la conception et à l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
3. Analyse et conception d'algorithmes par Padma Reddy

4. Even, Shimon., "Algorithmes de Graphes", Presse de Sciences Informatiques.

20
 MODULE-1,UNIT 3 ALGORITHMES ANALYSE ET RÉSOLUTION
RÉCURRENCES

Structure
1.0 Objectifs
1.1 Analyse des structures de contrôle

1.2 Utiliser un baromètre

1.3 Analyse de cas moyen

1.4 Analyse amortie
1,5 Résoudre des récurrences

1,6 Summary
1.7 Mots clés
1.8 Réponses pour vérifier vos progrès
1,9 Exercices de fin d'unité et réponses

1.10 Suggested readings

2.0 OBJECTIVES
À la fin de cette unité, vous serez en mesure de
•Résoudre des problèmes de chargement de conteneurs et de sac à dos.

•Trouvez les chemins les plus courts en utilisant l'algorithme de Prim et l'algorithme de Kruskal.

•Identifier la différence entre l'arbre de graphe et l'arbre couvrant minimal.

2.1 INTRODUCTION

Un outil essentiel pour concevoir un algorithme efficace et adapté est l' "Analyse de
Algorithmes. Il n'y a pas de formule magique, c'est simplement une question de jugement, d'intuition et
expérience. Néanmoins, voici quelques techniques de base qui sont souvent utiles, telles que
savoir comment gérer les structures de contrôle et
équations récursives.

1.2 Analyser les structures de contrôle

Analyse des structures de contrôle : L'analyse des algorithmes se déroule finalement de l'intérieur
D'abord, déterminez le temps requis par chaque instruction, puis combinez.

21
ces dents selon les systèmes de contrôle qui combinent les instructions dans le
programme.

1.2.1. Séquençage :

Soit P1 et P2 deux fragments d'un algorithme. Ils peuvent être une seule instruction. Ils
peut être des instructions simples ou des sous-algorithmes compliqués. Soit t1 et t2 les temps
pris par P1 et P2. t1 et t2 peuvent dépendre de divers paramètres, tels que l'instance
La règle de séquençage dit que le temps nécessaire pour calculer « P1 et P2 » est simplement t1.
+ t2. Par la règle du maximum, ce temps est dans q(max(t1, t2)). Malgré sa simplicité, appliquer
cette règle est parfois moins évidente qu'elle n'y paraît. Il pourrait arriver que l'un des
Les paramètres qui contrôlent t2 dépendent des résultats du calcul effectué P1.

1.2.2. Boucles « Pour » :

Ce sont les boucles les plus faciles à analyser. Pour i 1 à m fait P(i) Par une convention que nous allons adopter :
m=0 signifie que P(i) n'est pas exécuté du tout, (ce n'est pas une erreur). P(i) pourrait dépendre de la taille. De
Bien sûr, le cas le plus simple est quand cela ne le fait pas. Soit t le temps nécessaire pour calculer P(i) et
le temps total requis est l=mt. En général, cette approche est adéquate, mais il y a un potentiel
pitfall: We didn’t consider the time for the “loop control”. After all our for loops is
abrégé pour une boucle while comme suit.

je 1
tant que i <= m faire
P(i)
je i + 1
Dans les pires situations, il est raisonnable de compter le test i £ m au coût unitaire et le même
chose avec les instructions i ¬i + 1 et les opérations de séquençage « aller à » implicites dans le
while loop. Let “c” be the upper bound on the time required by each of the operations:
l <= c pour i ¬1
(m+1)c tests i £ m
+ exécution mt de P(i)
+ exécution mc de i j + 1
+ opérations de séquençage mc
l <= (t+3c)m+2c
Ce temps est clairement borné par en bas par mt. Si c est négligeable par rapport à t, notre précédent
estime que l est à peu près égal à mt est justifié. L'analyse de la boucle for est plus
intéressant lorsque le temps t(i) requis pour P(i) dépend de I et/ou également de la taille
n.
Alors : pour i De 1 à m, P(i) prend un temps donné par, t(i) (ignorant le temps pris par
le contrôle de la boucle).

Exemple : Algorithme pour la multiplication de matrices

22
Algorithme matmul(a[0…n-1],b[0..n-1])

deux matrices n par n

matrice c=ab

Pour moi 0 à n-1 faire

Pour j 0 à n-1 faire

C[I,j] 0

Pour k 0 à n-1 faire

C[I,j] c[I,j]+a[I,k]+b[k,j]
Retourner c
n1n1n1
La complexité temporelle de cet algorithme est donnée par M(n) = 1 €θ(n3)
je=0j =0k =0

1.2.3 Appels Récursifs :

L'analyse des algorithmes récursifs est straightforward jusqu'à un certain point. Simple
L'inspection de l'algorithme donne souvent lieu à une équation de récurrence qui "imite" le
flux de contrôle dans l'algorithme. Techniques générales sur la façon de résoudre ou comment transformer
l'équation en équations non récursives plus simples sera vue plus tard.

1.2.4 Boucles “While” et “Repeat” :

Ces deux types de boucles sont généralement plus difficiles à analyser que les boucles « for » car il y a
aucun moyen évident a priori de savoir combien de fois nous devrons faire le tour de la boucle.
La technique standard pour analyser ces boucles est de trouver une fonction des variables
impliqué où la valeur diminue à chaque tour. Pour déterminer combien de fois le
la boucle est répétée, cependant, nous devons mieux comprendre comment la valeur de cette fonction
diminue. Une approche alternative à l'analyse des boucles "while" consiste à traiter
comme des algorithmes récursifs. Nous illustrons les deux techniques avec le même exemple, Le
L'analyse des boucles "repeat" est effectuée de la même manière.

1.3 Utiliser un baromètre

1.4 Exemples supplémentaires

a. Algorithme pour trouver la somme des éléments d'un tableau
algorithme somme(a,n)

23
 {
s=0.0;
pour I=1 à n faire
s= s+a[I];
renvoie s;
}
Les instances de problème pour cet algorithme sont caractérisées par n, le
number of elements to be summed. The space needed d by ‘n’ is one
mot, car il est de type entier.
•The space needed by ‘a’a is the space needed by variables of type
tableau de nombres à virgule flottante.
Ceci est au moins 'n' mots, puisque 'a' doit être suffisamment grand pour contenir le 'n'
éléments à additionner.
•Ainsi, nous obtenons S somme(n)>=(n+s)
[ n pour a[], un pour chaque n, I a& s ]

Time Complexity:

Le temps T(p) pris par un programme P est la somme du temps de compilation

et le temps d'exécution

Le temps de compilation ne dépend pas des caractéristiques de l'instance. Nous aussi

peut supposer qu'un programme compilé sera exécuté plusieurs fois sans
recompilation. Ce temps d'exécution est désigné par tp (caractéristiques de l'instance).

Le nombre d'étapes attribuées à n'importe quelle déclaration de problème dépend du type

de déclaration.

Par exemple, des commentaires 0 étapes.

Instructions d'assignation 1 étapes.
Ce qui n'implique aucun appel à d'autres algorithmes

Instruction interactive telle que pour, tandis que et répéter-jusqu'à Contrôlez une partie de le
déclaration.

1. Nous introduisons une variable, count, dans l'instruction du programme pour incrémenter count.
avec une valeur initiale de 0. Déclaration pour incrémenter le compteur du montant approprié est
introduit dans le programme.
Ceci est fait afin que chaque fois qu'une instruction dans le programme original soit
Le compteur d'exécutions est incrémenté par le nombre d'étapes de cette instruction.

Algorithme :

Algorithme somme(a,n)
{
s = 0,0;

24
 compte = compte + 1;
pour I=1 à n faire
{
compte = compte + 1;
s=s+a[I];
compte=compte+1;
}
count=count+1;
count=count+1;
retourner s;
}

S'il n'y a zéro au départ, alors il sera de 2n+3 à la terminaison. Donc chaque
l'invocation de la somme exécute un total de 2n + 3 étapes.
La deuxième méthode pour déterminer le nombre d'étapes d'un algorithme consiste à construire un
table dans laquelle nous listons le nombre total de pas contribué par chaque déclaration.

Tout d'abord, déterminez le nombre d'étapes par exécution (s/e) de l'instruction et

le nombre total de fois (c'est-à-dire, la fréquence) que chaque déclaration est exécutée.
En combinant ces deux quantités, la contribution totale de toutes les déclarations, le
le nombre d'étapes pour l'ensemble de l'algorithme est obtenu.

Déclaration S/e Frequency Total

1. Algorithme Somme(a,n) 0 - 0
2.{ 0 - 0
3. S=0.0; 1 1 1
4. pour I=1 à n faire 1 n+1 n+1
5. s=s+a[I]; 1 n n
6. retourner s; 1 1 1
7. } 0 - 0

Total 2n+3

1.5 ANALYSE DU CAS MOYEN

•La plupart du temps, l'analyse des cas moyens est effectuée dans un plus ou moins
hypothèse réaliste selon laquelle toutes les instances d'une taille donnée sont également probables.
•Pour les problèmes de tri, il est simple de supposer également que tous les éléments à trier
sorted are distinct.
•Supposons que nous avons 'n' éléments distincts à trier par insertion et tous les n!
Les permutations de ces éléments sont également probables.

25
 Pour déterminer le temps pris en moyenne par l'algorithme, nous pourrions ajouter le
temps nécessaires pour trier chacune des permutations possibles, puis diviser par n!
la réponse ainsi obtenue.
Une approche alternative, plus facile dans ce cas, consiste à analyser directement le temps
requis par l'algorithme, raisonnant de manière probabiliste au fur et à mesure que nous avançons.

•Pour tout I,2 Je n, considérer le sous-tableau, T[1....i].

Le rang partiel de T[I] est défini comme la position qu'il occuperait si le sous
le tableau a été trié.
•Par exemple, le rang partiel de T[4] dans [3,6,2,5,1,7,4] est 3 car T[1….4]
une fois trié est [2,3,5,6].
•Il est clair que le rang partiel de T[I] ne dépend pas de l'ordre de l'élément dans
•Sous tableau T[1…I-1].

Analyse

Meilleur cas : Cette analyse se limite à l'entrée, autre que la taille. Ce qui en résulte est le plus rapide.
temps d'exécution possible
Pire scénario : Cette analyse se limite à l'entrée, en dehors de la taille. Ce qui entraîne les plus rapides.
temps d'exécution possible
Cas moyen : Ce type d'analyse aboutit à un temps d'exécution moyen pour chaque type de
entrée.
La complexité : La complexité se réfère au taux auquel le temps de stockage croît en fonction
de la taille du problème
Analyse asymptotique : Exprimer la complexité en termes de sa relation à la connaissance
fonction. Ce type d'analyse est appelé analyse asymptotique.
Notation asymptotique :
Grand 'oh' : la fonction f(n)=O(g(n)) si et seulement s'il existe des constantes positives c et n₀ telles que
f(n)≤c*g(n) pour tout n, n ≥ no.
Omega : la fonction f(n)=Ω(g(n)) s'il existe des constantes positives c et n0 telles que
f(n) ≥ c*g(n) pour tout n, n ≥ no.
Theta : la fonction f(n) = ө(g(n)) s'il existe des constantes positives c1, c2 et n0 telles que
c1 g(n) ≤ f(n) ≤ c2 g(n) pour tout n, n ≥ no.
1.6 Analyse amortie
DansinformatiqueL'analyse amortie est une méthode deanalyser des algorithmescela
considère l'ensemble de la séquence des opérations du programme. Il permet d'établir
d'un bornage dans le pire des cas pour la performance d'un algorithme, indépendamment des entrées par
en regardant toutes les opérations. Au cœur de la méthode se trouve l'idée que, tandis que certaines
les opérations peuvent être extrêmement coûteuses en ressources, elles ne peuvent pas se produire à un niveau suffisamment élevé
fréquence pour alourdir l'ensemble du programme en raison du nombre d'opérations moins coûteuses
dépasseront de loin les coûteux à long terme, "remboursant" le programme sur un
nombre d'itérations. C'est particulièrement utile car cela garantit le pire des cas
performance tout en tenant compte de l'ensemble des opérations dans un algorithme.
Il existe généralement trois méthodes pour effectuer une analyse amortie : l'agrégat
méthode, la méthode comptable et la méthode potentielle. Chacune d'elles donne le même
réponses, et leur différence d'utilisation est principalement circonstancielle et due à l'individu
préférence.

26
 . L'analyse agrégée détermine la limite supérieure T(n) sur le coût total d'un
séquence d'opérations, puis calcule le coût moyen d'être T(n) / n.
. Leméthode comptable détermine le coût individuel de chaque opération,
combinant son temps d'exécution immédiat et son influence sur le temps d'exécution de
opérations futures. En général, de nombreuses opérations de courte durée accumulent une "dette" de
un état défavorable en petites incréments, tandis que de rares opérations prolongées le diminuent
drastiquement.
. Leméthode potentielleest comme la méthode comptable, mais surcharges les opérations
tôt pour compenser les sous-charges plus tard.

Comme un exemple simple, dans une mise en œuvre spécifique de latableau dynamique, nous doublons la taille
du tableau chaque fois qu'il se remplit. À cause de cela, une réallocation du tableau peut être nécessaire, et dans le
dans le pire des cas, une insertion peut nécessiterO(n).
Cependant, une séquence de n insertions peut toujours être
fait en O(n) temps, car le reste des insertions se fait en temps constant, donc les insertions peuvent
être complété en O(n) temps. Le temps amorti par opération est donc O(n) /n= O(1).
Une autre façon de voir cela est de penser à une séquence de n opérations. Il y a 2 possibilités.
opérations : une insertion régulière qui nécessite un temps constant c pour être effectuée (supposons c = 1), et un
doublement de tableau qui nécessite un temps O(j) (où j<n et est la taille du tableau au moment de l)
doublage). Clairement, le temps nécessaire pour effectuer ces opérations est inférieur au temps nécessaire pour effectuer n
insertions régulières en plus du nombre de doublages de tableau qui auraient eu lieu dans le
séquence originale de n opérations. Il n'y a autant de doubles de tableau dans la séquence que
il y a des puissances de 2 entre 0 et n (lg(n)). Par conséquent, le coût d'une séquence de n opérations est
strictement inférieur à l'expression ci-dessous :

Le temps amorti par opération est la limite de temps du pire des cas sur une série de n opérations.
divisé par n. Le temps amorti par opération est donc
O(3n) /n= O(n) /n= O(1).

1.7 Récursion :

La récursivité peut avoir les définitions suivantes :

-The nested repetition of identical algorithm is recursion.
C'est une technique de définition d'un objet/processus par lui-même.
La récursion est un processus par lequel une fonction s'appelle elle-même de manière répétée jusqu'à ce qu'une condition spécifique soit remplie.

la condition a été satisfaite.

La récursivité peut avoir les définitions suivantes :
La répétition imbriquée d'un algorithme identique est la récursion.
La récursion est un processus par lequel une fonction s'appelle elle-même à plusieurs reprises jusqu'à ce qu'une condition spécifiée soit remplie.

la condition a été satisfaite.

1.7.1 Quand utiliser la récursivité :

27
 La récursion peut être utilisée pour des calculs répétitifs où chaque action est énoncée.
en termes de résultats précédents. Il y a deux conditions qui doivent être satisfaites par tout
procédure récursive.

Chaque fois qu'une fonction s'appelle elle-même, elle devrait se rapprocher de la solution.
2. Il doit y avoir un critère de décision pour arrêter le processus.

Lors de la prise de décision sur le choix d'écrire un algorithme en mode récursif ou non récursif
forme, il est toujours conseillé de considérer une structure arborescente pour le problème. Si la structure est
simple alors utilisez la forme non récursive. Si l'arbre paraît assez touffu, avec peu de duplication
de tâches, alors la récursion est appropriée.

L'algorithme de récursion pour trouver le facteur d'un nombre est donné ci-dessous,

Algorithm: factorial-recursion
n, le nombre dont il faut trouver la factorielle.
f, la factorielle de n
Méthode : si(n=0)
f=1
sinon
f=fact n! * n
si fin
l'algorithme se termine.

La procédure générale pour tout algorithme récursif est la suivante :

1. Sauvegarder les paramètres, les variables locales et les adresses de retour.

2. Si le critère d'arrêt est atteint, effectuez le calcul final et allez à l'étape 3.
sinon effectuez les calculs finaux et allez à l'étape 1

3. Restaurez les paramètres les plus récemment sauvegardés, la variable locale et l'adresse de retour et
aller à la dernière adresse de retour.

28
1.7.2 Itération contre Récursion :

Inconvénients des algorithmes récursifs :

1. De nombreux langages de programmation ne supportent pas la récursion ; donc, la récursive

Une fonction mathématique est implémentée en utilisant des méthodes itératives.
2. Bien que les fonctions mathématiques puissent être facilement mises en œuvre en utilisant la récursion, il
est toujours au détriment du temps d'exécution et de l'espace mémoire. Par exemple, le
L'arbre de récursion pour générer 6 nombres dans une série de Fibonacci est donné.
dans la fig 2.5. Une série de Fibonacci est de la forme 0,1,1,2,3,5,8,13,…etc, où le troisième
le nombre est la somme des deux nombres précédents et ainsi de suite. On peut le remarquer à partir de
fig 2.5 que, f(n-2) est calculé deux fois, f(n-3) est calculé trois fois, f(n-4) est
calculé 5 fois.
3. Une procédure récursive peut être appelée de l'intérieur ou de l'extérieur d'elle-même et pour garantir sa
Pour un fonctionnement correct, il doit enregistrer dans un certain ordre les adresses de retour afin que, un
le retour à l'emplacement approprié se produira lorsque le retour à une instruction d'appel sera
fait.
4. Les programmes récursifs nécessitent considérablement plus de stockage et prendront plus de temps.

1.7.3 Inconvénients des méthodes itératives :

•Des fonctions mathématiques telles que la factorielle et la génération de la série de Fibonacci peuvent être
facile à mettre en œuvre en utilisant la récursion plutôt que l'itération.

Dans les techniques itératives, la boucle de déclaration est très nécessaire.

La récursion est une approche descendante pour résoudre des problèmes. Elle divise le problème en morceaux.
ou sélectionne une étape clé, reportant le reste.
L'itération est plutôt une approche ascendante. Elle commence par ce qui est connu et à partir de cela.
construit la solution étape par étape. La fonction itérative utilise évidemment du temps qui est
O(n) alors qu'une fonction récursive a une complexité temporelle exponentielle.
Il est toujours vrai que la récursion peut être remplacée par l'itération et les piles. Il est également vrai que
stack can be replaced by a recursive program with no stack.

29
1.7.4 SOLVING RECURRENCES :-( Happen again (or) repeatedly)

•Le dernier pas indispensable lors de l'analyse d'un algorithme est souvent de résoudre un
équation de récurrence.
Avec un peu d'expérience et d'intention, la plupart des récurrences peuvent être résolues par
rajeunissement intelligent.
Cependant, il existe une technique puissante qui peut être utilisée pour résoudre certains
classes de récurrence presque automatiquement.
•C'est un sujet principal de cette section, la technique de l'équation caractéristique.

1. Travail de devinette intelligent :

Cette approche se déroule généralement en 4 étapes.

1. Calculez les premières valeurs de la récurrence

2. Recherchez la régularité.
3. Devinez une forme générale appropriée.
4. Et enfin prouver par induction mathématique (peut-être une induction constructive).

(Fibonacci) Considérez la récurrence.

n si n=0 ou n=1
fn=
fn-1+ fn-2 autrement

Nous réécrivons la récurrence comme,

fn– fn-1– fn-2 =0.

Le polynôme caractéristique est,

x2– x – 1 = 0.

The roots are,

-(-1) ± √((-1)2 + 4)
x = ------------------------
2

1 ±√ (1 + 4)
= ----------------
2

1 ± √5
= ----------
2

30
 1+√5 1 - √5
r1= --------- et r2= ---------
2 2

La solution générale est,

fn= C1r1n+ C2r2n

quand n=0, f0 = C1+ C2= 0

quand n=1, f1= C1r1+ C2r2= 1

C1+ C2= 0 (1)

C1r1+ C2r2= 1 (2)

À partir de l'équation (1)

C1= -C2

Substituer C1dans l'équation (2)

-C2r1+ C2r2= 1
C2[r2– r1] = 1

Substituer r1et r2valeurs

1 - √5 1 - √5
C2--------- ---------
- = 1
2 2
1 – √5 – 1 – √5
C2--------------------- = 1
2

-C2* 2√5
-------------- = 1
2

– √5C2= 1

C1= 1/√5 C2-1/√5

Ainsi,
n n
1 1 + √5 -1 1 - √5
fn= ---- --------- + ---- --------
√5 2 √5 2
n n
1 1 + √5 1 – √5
= ------------- - ---------

31
 √5 2 2

3. Récurrence inhomogène :

La solution d'une récurrence linéaire avec des coefficients constants devient plus difficile.
lorsque la récurrence n'est pas homogène, c'est-à-dire lorsque la combinaison linéaire n'est pas
égal à zéro.
* Considérez la récurrence suivante
un0tn+ un1tn-1+ … + akt n-k= bnp(n)
* Le côté gauche est le même qu'avant (homogène), mais du côté droit
nous avons bnp(n), où,
b est une constante
p(n) est un polynôme en ‘n’ de degré ‘d’.

Example(1) :

Considérez la récurrence,
tn - 2tn-1= 3n (A)

Dans ce cas, b=3, p(n) = 1, degré = 0.

Le polynôme caractéristique est,

(x - 2)(x - 3) = 0

Les racines sont, r1= 2, r2= 3

La solution générale,
tn= C1r1n+ C2r2n
tn= C12n+ C23n (1)

quand n=0, C1+ C2= t0 (2)

lorsque n=1, 2C1+ 3C2= t1 (3)

sub n=1 dans l'équation (A)

t1- 2t0= 3
t1= 3 + 2t0

substituer t1dans l'équation(3),

(2) * 2 2C1+ 2C2= 2t0

2C1+ 3C2= (3 + 2t0)
-------------------------------
-C2= -3
C2= 3

Sous C2= 3 dans l'équation (2)

32
 C1+ C2= t0
C1+ 3 = t0
C1= t0 – 3

Donc tn= (t0-3)2n+ 3. 3n

= Max[O[(t0- 3) 2n] , O[3.3n]]
= Max[O(2n), O(3n] constantes
= O[3n]

Exemple : 2. Résoudre la relation de récurrence suivante

x(n)=x(n-1)+5 pour n>1 , x(1)=0
Solution : La relation de récurrence ci-dessus peut être écrite comme indiqué ci-dessous
x(n)={ x(n-1)+5 si n>1
0 si n=1}
considérer la relation quand n>1
x(n)=x(n-1)+5 -------a
Remplacer n par n-1 dans l'équation a
x(n)=x(n-2)+5+5
Remplacez n par n-2 dans l'équation a
x(n)= x(n-2)+5+5+5
x(n) = x(n-2) + 3*5
………………….
…………………..
Enfin x(n)=x[n-(n-1)]+(n-1)*5
= x(1)+(n-1)*5
=0 +(n-1)*5
x(n)=5(n-1)

4. Changement de variables :
* Il est parfois possible de résoudre des récurrences plus compliquées en faisant un
changement de variable.
* Dans l'exemple suivant, nous écrivons T(n) pour le terme d'une récurrence générale,
et tjepour le terme d'une nouvelle récurrence obtenue à partir de la première par un changement de
variable.

(1)
Considérez la récurrence,

1 , si n=1
T(n) =
3T(n/2) + n, si ‘n’ est une puissance de 2, n > 1

Reconsidérez la récurrence que nous avons résolue par des conjectures intelligentes dans le précédent
section, mais seulement dans le cas où ‘n’ est une puissance de 2

33
 1
T(n) =
3T(n/2) + n

* Nous remplaçons 'n' par 2je.

Cela est réalisé en introduisant une nouvelle récurrence tje, défini par tje= T(2je)
* Cette transformation est utile parce que n/2 devient (2je)/2 = 2i-1
En d'autres termes, notre récurrence originale dans laquelle T(n) est définie comme une fonction de
T(n/2) a cédé la place à une où tjeest défini comme une fonction de ti-1, précisément
le type de récurrence que nous avons appris à résoudre.
tje= T(2je) = 3T(2i-1) + 2je
tje= 3tje-1+ 2je
tje– 3ti-1= 2i (A)

Dans ce cas,
b = 2, p(n) = 1, degree = 0

Donc, l'équation caractéristique,

(x - 3)(x - 2) = 0

Les racines sont, r1 = 3, r2 = 2.

L'équation générale,
tn= C1r1je+ C2r2je
sous. r1& r2: tn= 3nC1+ C22n
tn= C13je+ C22je

Nous utilisons le fait que, T(2je) = tje& donc T(n) = tlogn quand n = 2jeobtenir
T(n) = C1. 3log n2+ C2. 2log n2
T(n) = C1. nlog 32+ C2.n [i = logn]
Lorsque 'n' est une puissance de 2, ce qui est suffisant pour conclure que,

T(n) = O(nlog3'n' est une puissance de 2

Vérifiez vos progrès

1. Expliquez comment analyser les différentes structures de contrôle des algorithmes.

2. Écrivez une note sur l'analyse des cas moyens.

3. Écrivez un algorithme récursif pour générer la série de Fibonacci et construisez le

relation de récurrence et résoudre.
4. Résoudre la relation de récurrence suivante x(n)=x(n-1)+5 pour n>1, x(1)=0.

34
 Résumé :
Analyse des structures de contrôle : L'analyse des algorithmes progresse finalement par l'intérieur
Déterminez d'abord le temps requis par chaque instruction, puis combinez.
ces temps selon les systèmes de contrôle qui combinent les instructions dans le
programme.
La récursivité peut être utilisée pour des calculs répétitifs dans lesquels chaque action est exprimée en termes de

du résultat précédent.
Résoudre des récurrences en utilisant les étapes suivantes : Calculez les premières valeurs de la
récurrence. Cherchez une régularité. Devinez une forme générale appropriée et enfin prouvez par
induction mathématique (peut-être induction constructive).

1.7 KEYWORDS
1. Grands symboles 'oh', Oméga et Thêta de la notation asymptotique.

1.8 RÉPONSES POUR VÉRIFIER VOTRE PROGRÈS

1. 1.1
2. 1.5
3. 1.7
4. 1.7
1.7 EXERCICES ET RÉPONSES À LA FIN DE L'UNITÉ

3. Écrivez une note sur l'analyse amortie.

4.résoudre la relation de récurrence x(n)=x(n-1)*n si n>0 où x(0)=1
VOIR
1. 1.6
2. 1.7

1.9 LECTURES SUGGÉRÉES

1. Introduction au design et à l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
3. Analyse et conception d'algorithmes par Padma Reddy

4. Même, Shimon., "Algorithmes de Graphes", Presse de Sciences Informatiques.

35
 MODULE-1,UNITÉ 4 RECHERCHE ET TRIS
Structure
1.0 Objectifs
1.1 Algorithmes de recherche
Recherche linéaire
Recherche binaire
1.2 sorting
Tri par sélection
Tri par insertion
Tri à bulles
1.3 Summary
1.4 Keywords
1.5 Réponses pour vérifier vos progrès
1.6 Exercices de fin d'unité et réponses
1.7 Lectures suggérées

3.0 OBJECTIFS
À la fin de cette unité, vous serez capable de

Savoir chercher de différentes manières

•Identifier quelle technique de recherche est meilleure
•Faire le tri de différentes manières, par exemple le tri par insertion, le tri par sélection
Mesure de performance des techniques de recherche et de tri.

3.1 ALGORITHMES DE RECHERCHE

Supposons que nous ayons un fichier séquentiel et que nous souhaitions récupérer un élément correspondant.
avec la clé 'k', alors, nous devons chercher dans tout le fichier depuis le début jusqu'à la fin pour
vérifiez si l'élément correspondant à k est présent dans le fichier ou non.
Il existe plusieurs algorithmes de recherche complexes pour servir à la recherche.
Les méthodes de recherche linéaire et de recherche binaire sont des méthodes relativement simples de
recherche.

1.1.1 Recherche séquentielle : (Recherche linéaire)

Dans cette méthode, nous commençons à chercher depuis le début de la liste et examinons chaque
élément jusqu'à la fin de la liste. Si l'élément souhaité est trouvé, nous arrêtons la recherche et
renvoie l'index de cet élément. Si l'élément n'est pas trouvé et que la liste est épuisée, le
la recherche renvoie une valeur nulle.

Dans le pire des cas, l'élément n'est pas trouvé ou l'élément de recherche est le dernier (nth) élément.
Pour les deux situations, nous devons examiner tous les n éléments du tableau, donc l'ordre de grandeur

36
ou la complexité de la recherche séquentielle est n. c'est-à-dire, O(n). Le temps d'exécution pour cela
l'algorithme est proportionnel à n c'est-à-dire que l'algorithme s'exécute en temps linéaire.

L'algorithme pour la recherche séquentielle est le suivant,

Algorithme : recherche séquentielle

A, vecteur de n éléments K, élément de recherche
j –indice de k
i=1
Tant que(i<=n)
{
si(A[i]=k)
{
recherche réussie
k est à l'emplacement i
sortir();
}
sinon
i++
si fin
tandis que fin
écrire (recherche infructueuse);
l'algorithme se termine.

1.1.2 Recherche binaire :

La méthode de recherche binaire est également une méthode relativement simple. Pour cette méthode, il est
necessary to have the vector in an alphabetical or numerically increasing order. A search
pour un article particulier avec X ressemble à la recherche d'un mot dans le dictionnaire. Le
approximate mid entry is located and its key value is examined. If the mid value is
plus grand que X, alors la liste est coupée à (mid-1)themplacement. Maintenant la liste devient
réduit à la moitié de la liste originale. L'entrée du milieu de la liste réduite à gauche est examinée dans un
manière similaire. Cette procédure est répétée jusqu'à ce que l'élément soit trouvé ou que la liste n'ait plus
éléments. D'autre part, si la valeur médiane est inférieure à X, alors la liste est tronquée.
à (mid+1)themplacement. L'entrée du milieu de la liste réduite à droite est examinée et le
la procédure se poursuit jusqu'à ce que la clé désirée soit trouvée ou que l'intervalle de recherche soit épuisé.

L'algorithme de recherche binaire est le suivant,

Algorithme : recherche binaire

Input: A, vector of n elements K, search element
Sortie : faible - index de k
low=1,high=n
Tant que(low<=high-1)
{
mid=(low+high)/2

37
si(k<a[mid])
haut=moyen
sinon
bas=milieu
if end
}
tandis que la fin

si(k=A[bas])
{
recherche réussie
k est à l'emplacement bas
exit();
}
sinon
écrire (recherche infructueuse);
si fin;
l'algorithme se termine.

1.2 Tri

Plusieurs algorithmes sont présentés, y compris le tri par insertion, le tri Shell et le tri rapide.
Le tri par insertion est la méthode la plus simple et ne nécessite aucun stockage supplémentaire.
Le tri Shell est une simple modification qui améliore considérablement les performances.

1.2.1 TRI_PAR_SELECTION

Le tri par sélection est l'une des techniques de tri les plus simples et fonctionne très bien pour les petits
files. Furthermore, despite its evident "naïve approach "Selection sort has a quite
application importante car chaque élément est en réalité déplacé au maximum une fois, le tri par section est un
méthode de choix pour trier des fichiers avec de très grands objets (enregistrements) et de petites clés.

Voici un exemple étape par étape pour illustrer l'algorithme de tri par sélection à l'aide de nombres :
Tableau original :
6354927
1ère passe -> 2 3 5 4 9 6 7 (2 et 6 ont été échangés)
2ème passage -> 2 3 4 5 9 6 7 (4 et 5 ont été échangés)
3ème passage -> 2 3 4 5 6 9 7 (6 et 9 ont été échangés)
4ème passage -> 2 3 4 5 6 7 9 (7 et 9 ont été échangés)
5ème passage -> 2 3 4 5 6 7 9 (pas d'échange)
6e passage -> 2 3 4 5 6 7 9 (aucun échange)

38
Remarque : Il y avait 7 clés dans la liste et donc 6 passages étaient nécessaires. Cependant, seulement 4.
des échanges ont eu lieu.

Algorithme : Tri par sélection

pour i ← 1 à n-1 faire

minj←i;
minx← A[i]
pour j ← i + 1 à n faire
Si A[j] < min x alors
minj←j
minx← A[j]
A[minj] ← A[i]
A[i] ← minx

Le pire des cas se produit si le tableau est déjà trié dans l'ordre décroissant. Néanmoins,
le temps requis par l'algorithme de tri par sélection n'est pas très sensible à l'ordre original de
le tableau à trier : le test "siA[j] < min x" est exécuté exactement le même nombre de
les fois dans chaque cas. La variation dans le temps est uniquement due au nombre de fois que le "alors"
La partie (c'est-à-dire, minj←j; minx←A[j]) de ce test est exécutée.

Le tri par sélection passe la majeure partie de son temps à essayer de trouver l'élément minimum dans le
partie "non triée" du tableau. Cela montre clairement la similitude entre le tri par sélection et
Le tri à bulles. Le tri à bulles "sélectionne" les éléments restants maximum à chaque étape, mais
gaspille un peu d'effort à donner un ordre à la partie « non triée » du tableau. Le tri par sélection est
quadratique à la fois dans le pire et le cas moyen, et nécessite aucune mémoire supplémentaire.

39
Pour chaque i de 1 à n-1, il y a un échange et n-i comparisons, donc il y a un total
d'échanges ofn-1 et (n-1) + (n-2) + . . . + 2 + 1 = n(n-1)/2 comparaisons. Ces
les observations tiennent peu importe quelles sont les données d'entrée. Dans le pire des cas, cela pourrait être
quadratique, mais dans le cas moyen, cette quantité est O(nlogn).

1.2.2 Insertion Sort

Si les premiers objets sont déjà triés, un objet non trié peut être inséré dans le trié.
placé au bon endroit. Cela s'appelle le tri par insertion. Un algorithme considère les éléments un
à un moment donné, en insérant chacun à sa place appropriée parmi ceux déjà considérés (en gardant
les triés). Le tri par insertion est un exemple d'algorithme incrémental ; il construit le
séquence triée un nombre à la fois. C'est peut-être le plus simple exemple de la
technique d'insertion incrémentale, où nous construisons une structure compliquée sur n éléments en
d'abord en le construisant sur n − 1 éléments puis en apportant les modifications nécessaires pour corriger les choses dans
ajouter le dernier élément. Les séquences données sont généralement stockées dans des tableaux. Nous faisons également référence à
des numéros comme clés. Avec chaque clé, il peut y avoir des informations supplémentaires, connues sous le nom de satellite

données. [Notez que "les données satellite" ne proviennent pas nécessairement d'un satellite !]

Algorithme : Tri par insertion

Cela fonctionne comme vous pourriez trier une main de cartes à jouer :

1. Nous commençons avec une main gauche vide [tableau trié] et les cartes face cachée sur le
table [tableau non trié].
2. Ensuite, retirez une carte [clé] à la fois de la table [tableau non trié] et insérez-la
dans la bonne position dans la main gauche [tableau trié].
3. Pour trouver la position correcte pour la carte, nous la comparons avec chacune des cartes.
déjà dans la main, de droite à gauche.

Notez qu'à tout moment, les cartes tenues dans la main gauche sont triées, et ces cartes étaient
à l'origine les cartes du dessus de la pile sur la table.

Pseudo code

Nous utilisons une procédure INSERTION_SORT. Elle prend comme paramètres un tableau A[1..n] et le
longueur du tableau. Le tableau A est trié sur place : les nombres sont réarrangés à l'intérieur
le tableau, avec au maximum un nombre constant en dehors du tableau à tout moment.

TRI_PAR_INSÉRTION (A)

40
 [Link] ← 2Àlongueur[A]FAIRE

2. clé ←A[j]

3. {Mettre A[j] dans la séquence triée A[1 . .j− 1]}

4.i←j− 1
5. TANT QUE i > 0 et A[i] > clé
6. DOA[i+1] ← A[i]
7. i←i− 1
8.A[i + 1] ← clé

La figure suivante (extrait de CLRS) montre le fonctionnement de l'INSERTION-SORT sur

le tableau A= (5, 2, 4, 6, 1, 3). Chaque partie montre ce qui se passe pour une itération particulière
avec la valeur de jindiquée. jindexes la "carte actuelle" étant insérée dans la main.

Lisez la figure ligne par ligne. Les éléments à gauche de A[j] qui sont supérieurs à A[j] se déplacent.
one position to the right, andA[j] moves into the evacuated position.

Analyse

Puisque le temps d'exécution d'un algorithme sur une entrée particulière est le nombre d'étapes
exécuté, nous devons définir le "pas" indépendamment de la machine. Nous disons qu'une déclaration qui
prendcje étapes à exécuter et les temps d'exécution contribuentjeau temps de course total de
l'algorithme. Pour calculer le temps d'exécution, T(n), nous additionnons les produits du coût et
colonne des temps [voir CLRS page 26]. C'est-à-dire que le temps d'exécution de l'algorithme est la somme
des temps d'exécution pour chaque instruction exécutée. Donc, nous avons

T(n) = c1n+c2(n− 1) + 0 (n− 1) +c4(n− 1) +c5∑2 ≤j≤ n(tj )

+c6∑2 ≤j≤ n(tj− 1) +c7∑2 ≤j≤ n(tj- 1) +c8(n− 1)

Dans l'équation ci-dessus, nous avons supposé quejsois le nombre de fois que la boucle while (à la ligne
5) est exécuté pour cette valeur de j. Notez que la valeur de j varie de 2 à (n− 1). Nous avons

41
 T(n) = c1n+c2(n− 1) + c4(n− 1) +c5∑2 ≤j≤ n(tj+c6∑2 ≤j≤ n(tj- 1)
+c7∑2 ≤ j≤ n(tj- 1) +c8 (n− 1) Équation (1)

Meilleur des cas

Le meilleur cas se produit si le tableau est déjà trié. Pour chaque j = 2, 3, ..., n, nous trouvons
thatA[i] inférieur ou égal à la clé lorsque ihad sa valeur initiale de (j− 1). En d'autres termes,
quandi=j−1, trouvez toujours la cléA[i] lors de la première fois que la boucle WHILE est exécutée.

Donc,j= 1 pour j = 2, 3, ..., n et le temps d'exécution dans le meilleur cas peut être calculé en utilisant
l'équation (1) comme suit :

T(n) =c1n+c2 (n− 1) +c4(n− 1) +c5∑2 ≤ j≤ n(1) +c6∑2 ≤j≤ n(1 − 1) + c7∑2 ≤j≤ n(1
- 1) +c8(n− 1)

T(n) =c1n+c2(n− 1) +c4(n− 1) +c5(n− 1) +c8(n− 1)

T(n) =(c1+c2+c4+c5+c8)n+ (c2+c4+c5+c8)

Ce temps d'exécution peut être exprimé comme an + b pour des constantes a et b qui dépendent de
déclaration des coûtsje. Par conséquent, T(n) est une fonction linéaire de n.

Le fait marquant ici est que la boucle while à la ligne 5 s'est exécutée une seule fois pour chaque j.
que se passe-t-il si le tableau arrayA est déjà trié.

T(n) = an + b = O(n)

C'est une fonction linéaire de n.

Pire cas

Le pire des cas se produit si le tableau est trié dans l'ordre inverse c'est-à-dire, dans l'ordre décroissant.
dans l'ordre inverse, nous constatons toujours que A[i] est supérieur à la clé dans le test de la boucle while.
Donc, nous devons comparer chaque élément A[j] avec chaque élément de l'ensemble trié.
sous-tableauA[1 ..j− 1] et sotj=jforj= 2, 3, ...,n. De manière équivalente, nous pouvons dire que puisque le
la boucle while sort parce qu'elle atteint 0, il y a un test supplémentaire après (j - 1) tests.
Donc,j=jforj= 2, 3, ..., n et le temps d'exécution dans le pire des cas peut être calculé en utilisant
l'équation (1) comme suit :

T(n) =c1n+c2(n− 1) +c4(n− 1) +c5∑2 ≤j≤ n(j) +c6∑2 ≤ j≤ n(j− 1)

+c7∑2 ≤j≤ n(j− 1) + c8(n− 1)

Et en utilisant les sommations dans CLRS à la page 27, nous avons

42
 T(n) = c1n+c2(n− 1) +c4(n− 1) +c5∑2 ≤j≤ n[n(n+1)/2 + 1]
+c6∑2 ≤ j≤ n[n(n− 1)/2] +c7∑2 ≤j≤ n[n(n− 1)/2] + c8(n− 1)

T(n) = (c5/2 +c6/2 +c7/2)n2+ (c1+c2+c4+c5/2 −c6/2 −c7/2

+c8)n− (c2+c4+c5+c8)

Ce temps d'exécution peut être exprimé comme (an2+bn+c) pour les constantes a, b et c qui encore
dépendre de l'état des coûtsjePar conséquent, T(n) est une fonction quadratique de n.

Ici, le point essentiel est que le pire des cas se produit lorsque la ligne 5 est exécutée j fois pour chaque j.
Cela peut se produire si arrayA commence dans l'ordre inverse

T(n) =an2+bn+c= O(n2)

C'est une fonction quadratique de n.

Le graphique montre alors2complexité du tri par insertion.

Analyse du pire cas et du cas moyen

Nous nous concentrons généralement sur la recherche du temps d'exécution dans le pire des cas : le temps d'exécution le plus long.
pour toute taille d'entrée n. Les raisons de ce choix sont les suivantes :

Le temps d'exécution dans le pire des cas donne une limite supérieure garantie sur le temps d'exécution.

pour tout input. C'est-à-dire que la borne supérieure nous garantit que l'algorithme va
ne prends jamais plus de temps.
•Pour certains algorithmes, le pire des cas se produit souvent. Par exemple, lors de la recherche,

le pire des cas se produit souvent lorsque l'objet recherché n'est pas présent, et
les recherches d'articles absents peuvent être fréquentes.
•Pourquoi ne pas analyser le cas moyen ? Car il est souvent aussi mauvais que le pire.
cas.

Exemple : Supposons que nous choisissions aléatoirement des nombres comme entrée pour l'insertion
trier.

43
En moyenne, la clé dans A[j] est inférieure à la moitié des éléments dans A[1 .. j− 1] et elle est supérieure
que l'autre moitié. Cela implique qu'en moyenne, la boucle while doit regarder à mi-chemin à travers
le sous-tableau trié A[1 ..j− 1] pour décider où placer la clé. Cela signifie quej=j/2.

Bien que le temps d'exécution moyen soit d'environ la moitié du temps d'exécution dans le pire des cas
temps, c'est toujours une fonction quadratique de n.

Stabilité

Puisque plusieurs clés avec la même valeur sont placées dans le tableau trié dans le même ordre
comme ils apparaissent dans le tableau d'entrée, le tri par insertion est stable.

Mémoire supplémentaire

Cet algorithme ne nécessite pas de mémoire supplémentaire.

Pour le tri par insertion, nous disons que le temps d'exécution dans le pire des cas est θ( n2), et le meilleur des cas
le temps d'exécution est θ(n).
Le tri par insertion n'utilise pas de mémoire supplémentaire, il trie directement dans l'espace.

Le temps de tri par insertion dépend de l'ordre d'origine d'une entrée. Il prend un
temps en Ω(n ) dans le pire des cas, malgré le fait qu'un temps dans l'ordre de nis
2

suffisant pour résoudre de grands instances dans lesquelles les éléments sont déjà triés.

1.2.2 Bubble sort

Le tri à bulles, également connu sous le nom de tri descendant, est un tri simplealgorithme
de tricela fonctionne par
parcourant de manière répétée la liste à trier, en comparant chaque paire d'éléments adjacents
etéchangeeux s'ils sont dans le mauvais ordre. Le passage à travers la liste est répété
jusqu'à ce qu'aucun échange ne soit nécessaire, ce qui indique que la liste est triée. L'algorithme obtient son
nom de la façon dont les éléments plus petits « remontent » en haut de la liste. Parce qu'il n'utilise que
comparaisons pour opérer sur des éléments, c'est untri par comparaison.

Prenons le tableau de nombres "5 1 4 2 8", et trions le tableau du plus petit nombre au plus grand.
le plus grand nombre utilisant l'algorithme de tri à bulles. À chaque étape, les éléments écrits en gras sont
être comparé.
Première Passation :

(5 14 2 8) (1 54 2 8), Ici, l'algorithme compare les deux premiers éléments et les échange.
eux.
( 15 42 8 ) ( 14 52 8 ), Échanger car 5 > 4
( 1 45 28 ) ( 1 42 58 ), Échanger car 5 > 2
( 1 4 25 8) ( 1 4 25 8), Maintenant, puisque ces éléments sont déjà dans l'ordre (8 > 5),
l'algorithme ne les échange pas.
Deuxième passage :
(1 42 5 8 ) (1 42 5 8 )

44
( 14 25 8 ) ( 12 45 8 ), Échangez puisque 4 > 2
( 1 24 58 ) ( 1 24 58 )
( 1 2 45 8) ( 1 2 45 8)
Maintenant, le tableau est déjà trié, mais notre algorithme ne sait pas s'il est terminé. Le
l'algorithme a besoin d'un seul passage sans échange pour savoir s'il est trié.
Troisième passage :

(1 24 5 8 ) (1 24 5 8)
( 12 45 8 ) ( 12 45 8 )
( 1 24 58 ) ( 1 24 58 )
( 1 2 45 8) ( 1 2 45 8)
Enfin, le tableau est trié et l'algorithme peut se terminer.

Algorithme : bubbleSort( A : liste d'éléments triables )

n = longueur(A)
pour j 1 à n-1 faire
pour i <- 0 à n-j-1 faire
si A[i] >= A[i+1] alors
échanger(A[i], A[i+1])
fin si
fin pour
fin pour

Analyse :
Complexité temporelle t(n)=
n -1 n − j -1 n -1 n -1

∑ ∑1 = ∑n − j −1 − 0 +1 = ∑
j =1 je=0 j =1 =1
n − j = (n −1) + (n − 2) + ... + 3 + 2 +1 = n(n+!)/2
j

Donc, la complexité temporelle du tri à bulles = θ(n2).

Vérifiez vos progrès

1. Écrivez un algorithme pour la recherche séquentielle et suivez-le pour l'entrée { 1,9,2,4,6,8}.

2. Écrire un algorithme pour le tri à bulles et le tri par sélection. Appliquez-le à l'ensemble suivant.
nombres { 5,8,3, 2,1,9}. Trouvez la complexité temporelle de tous ces algorithmes.
3. Écrivez un algorithme pour le tri par insertion Appliquez-le à cet ensemble de nombres
{ 6,8,3, 6,1,9}. Find the time complexity .

1.3 SUMMARY:

45
 Le tri : C'est le processus de classement des éléments dans un ordre croissant ou décroissant.
manière. Exemple tri par insertion, tri à bulles, tri par sélection, etc.
Recherche : c'est un processus pour trouver l'élément parmi un ensemble de n éléments. Exemple
recherche linéaire, recherche binaire.

1.9 KEYWORDS
Recherche binaire : recherche d'un élément par la technique de diviser pour régner.

1.10 ANSWERS TO CHECK YOUR PROGRESS

1. 1
2. 1.2.1 & 1.2.3
3. 1.2.2
1.7 EXERCICES ET RÉPONSES DE FIN D'UNITÉ
5. Appliquer l'algorithme de tri par insertion pour l'ensemble A L G O R I T H M afin de le trier.

ordre croissant.
Appliquer L'algorithme de recherche binaire pour rechercher 'G' dans l'ensemble A B C F H Z X.

Answers: SEE
1. 1.1
2. 1.2

1.10 LECTURES SUGGÉRÉES

1. Introduction à La conception et l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
3. Analyse et conception des algorithmes par Padma Reddy

4. Even, Shimon., "Algorithmes de graphes", Presse de science informatique.

46
 MODULE-3,UNIT 2: : DIVIDE AND CONQUER

Structure
2.0 Objectifs
1.1 Introduction
1.2 Structure générale de Diviser pour régner
1.3 Applications trouvant le minimum et le maximum
1.4 Équations de récurrence
1,6 Résumé
1.7 Mots-clés
1.8 Réponses pour vérifier vos progrès
1.9 Exercices de fin d'unité et réponses

1.10 Suggested readings

4.0 OBJECTIFS
À la fin de cette unité, vous serez en mesure de
Trouvez comment appliquer la méthode diviser pour régner

Trouvez la complexité temporelle des algorithmes de diviser pour régner.

•Identification des relations de récurrence pour l'algorithme

•Savoir résoudre des relations de récurrence

4.1 INTRODUCTION

La méthode de conception d'algorithmes par division et conquête est la méthode la mieux connue de
Résoudre un problème. Maintenant, voyons "Qu'est-ce que la technique de diviser pour régner ? Que signifie cela ?"
plan général selon lequel ces algorithmes fonctionnent ?

Définition : Diviser pour régner est une technique descendante pour concevoir des algorithmes qui
consiste à diviser le problème en sous-problèmes plus petits en espérant que les solutions des
les sous-problèmes sont plus faciles à trouver. Les solutions de tous les petits problèmes sont ensuite combinées
pour obtenir une solution au problème original.
La technique de diviser pour régner pour résoudre un problème implique trois étapes.
Chaque niveau de la récursion :
•.Diviser : Le problème est divisé en plusieurs sous-problèmes

47
 •.Conquérir : Les sous-problèmes sont conquis en les résolvant de manière récursive. Si le
Les sous-problèmes sont plus petits en taille, le problème peut être résolu de manière directe.
méthode
•.Combiner : Les solutions des sous-problèmes sont combinées pour obtenir la solution pour
le problème plus vaste.

1.1.1 Le théorème du maître pour résoudre la relation de récurrence

The master theorem concerns recurrence relations of the form:

Dans l'application à l'analyse d'un algorithme récursif, les constantes et la fonction

prendre la signification suivante :

. nis la taille du problème.

. est le nombre de sous-problèmes dans la récursivité.
. n/bis la taille de chaque sous-problème. (Ici, on suppose que tous
les sous-problèmes sont essentiellement de la même taille.

. f(n) est le coût du travail effectué en dehors des appels récursifs, ce qui
includes the cost of dividing the problem and the cost of merging the solutions to
les sous-problèmes.

Il est possible de déterminer une borne asymptotique serrée dans ces trois cas :
T(n)= { θ(nd) si a < d
b
θ(nd logn) si a=bd
θ(ndlogn) si a>bd}
Remarque : Ici, d est la puissance de n dans f(n).

4.2 MAXIMUM ET MINIMUM

•Considérons un autre problème simple qui peut être résolu par la méthode de diviser pour régner.
technique de conquête.

Le problème consiste à trouver les éléments maximum et minimum dans un ensemble de 'n' éléments.

En analysant la complexité temporelle de cet algorithme, nous nous concentrons à nouveau sur
le nombre de comparaisons d'éléments.

48
•Plus important encore, lorsque les éléments dans a[1:n] sont des polynômes, des vecteurs, très
de grands nombres, ou des chaînes de caractères, le coût d'une comparaison d'éléments est beaucoup
plus élevé que le coût des autres opérations.

Ainsi, le temps est principalement déterminé par le coût total de la comparaison des éléments.

1. Algorithme droit MaxMin(a,n,max,min)

2. // définir max comme le maximum et min comme le minimum de a[1:n]
3. {
4. max:=min:=a[1];
5. pour i:=2 à n faire
6. {
7. si(a[I]>max) alors max:=a[I];
8. si(a[I]<min) alors min:=a[I];
9. }
10. }

Algorithme : Maximum et Minimum simples

•Le MaxMin direct nécessite 2(n-1) comparaisons d'éléments dans le meilleur, l'average et le pire
cas.

Une amélioration immédiate est possible en réalisant que la comparaison a[I]<min

est nécessaire seulement lorsque a[i]>max est faux.

•Par conséquent, nous pouvons remplacer le contenu de la boucle for par,

Si(a[I]>max) alors max:=a[I];
Sinon si (a[I]<min) alors min:=a[I];

•Le meilleur cas se produit lorsque les éléments sont en ordre croissant.
Le nombre de comparaisons d'éléments est (n-1).

Le pire cas se produit lorsque les éléments sont dans un ordre décroissant.
La comparaison du nombre d'éléments est 2(n-1)

Le nombre moyen de comparaisons d'éléments est inférieur à 2(n-1)

En moyenne, un [I] est supérieur à la moitié du maximum du temps, et donc, le nombre moyen de
la comparaison est 3n/2-1.

Un algorithme de diviser pour régner pour ce problème procéderait comme suit :

Soit P=(n, a[I] ,……,a[j]) une instance arbitraire du problème.

Ici, 'n' est le nombre d'éléments dans la liste (a[I],….,a[j]) et nous sommes intéressés par

49
 trouver le maximum et le minimum de la liste.

Si la liste a plus de 2 éléments, P doit être divisé en instances plus petites.

Par exemple, nous pourrions diviser 'P' en 2 instances, P1=([n/2],a[1],

……..a[n/2]) & P2= (n-[n/2],a[[n/2]+1],…..,a[n])

Après avoir divisé 'P' en 2 sous-problèmes plus petits, nous pouvons les résoudre par
invoquer de manière récursive le même algorithme de diviser pour régner.

Algorithme : Trouver récursivement le maximum et le minimum en utilisant la division et

technique de conquête

1. Algorithme MaxMin (I,j,max,min)

//a[1:n] est un tableau global, paramètres I et j
3. //sont des entiers, 1<=I<=j<=n. L'effet est de
4. //définir max et min sur la plus grande et la plus petite valeur
5. //dans a[I:j], respectivement.
6.
7. si(I=j) alors max:= min:= a[I];
8. sinon si (I=j-1) alors // Un autre cas de petit(p)
9. {
10. if (a[I]<a[j]) then
11. {
12. max:=a[j];
13. min:=a[I];
14. }
15. sinon
16. {
17. max := a[I];
18. min:=a[j];
19. }
20. }
21. sinon
22.
23. // si P n'est pas petit, divisez P en sous-problèmes.
24. // trouver où diviser l'ensemblemilieu:=[(I+j)/2];
25. //résoudre les sous-problèmes
26. MaxMin(I,mid,[Link]);
27. MaxMin(mid+1,j,max1,min1);
28. //combiner la solution
29. si (max<max1) alors max=max1;
30. si(min>min1) alors min = min1;
31. }
32. }

50
 •La procédure est initialement invoquée par la déclaration,
MaxMin(1,n,x,y)
Supposons que nous simulions MaxMin sur les 9 éléments suivants

A: [1] [2] [3] [4] [5] [6] [7] [8] [9]

22 13 -5 -8 15 60 17 31 47
Une bonne façon de suivre les appels récursifs est de construire un arbre en ajoutant un nœud.
chaque fois qu'un nouvel appel est effectué.

Pour cet algorithme, chaque nœud a 4 éléments d'information : I, j, max et imin.

•En examinant la fig : nous voyons que le nœud racine contient 1 et 9 comme les valeurs de I et j
correspondant à l'appel initial à MaxMin.
Cette exécution produit 2 nouveaux appels à MaxMin, où I et j ont les valeurs 1, 5
& 6, 9 respectivement & ainsi diviser l'ensemble en 2 sous-ensembles d'environ la même
taille.
•Depuis l'arbre, nous pouvons immédiatement voir que la profondeur maximale de la récursion est de 4.
(y compris le 1 appel) st

Les numéros inclus dans le coin supérieur gauche de chaque nœud représentent l'ordre dans lequel
max et min se voient attribuer des valeurs.

Nombre de comparaison d'éléments :

•Si T(n) représente ce nombre, alors la relation de récurrence résultante est

T(n)={ T([n/2]+T[n/2]+2 n>2

1 SI n=2
0 SI n=1

Lorsque 'n' est une puissance de 2, n=2^k pour un entier positif 'k', alors
T(n) = 2T(n/2) +2
= 2(2T(n/4)+2)+2
= 4T(n/4)+4+2
*
*
= 2^k-1T(2)+
= 2^k-1+2^k-2
= 2^k/2+2^k-2
= n/2+n-2
(n+2n)/2)-2

T(n)=(3n/2)-2

*Notez que (3n/3)-3 est la moyenne optimale et le pire des cas en termes de nombre de comparaisons lorsque 'n'
est une puissance de 2.

51
4.3 RÉSOLUTION D'ÉQUATIONS RÉCURRENTES

Nous résolvons souvent des équations de récurrence en analysant la complexité des algorithmes, des circuits, et
d'autres cas similaires.

1.3.1 Équation de récurrence homogène

Une équation de récurrence homogène est écrite comme :
un0tn+ un1tn-1 + . . . . +aktn-k = 0.

Solution technique :
Étape 1 : Établir une équation caractéristique correspondante :
un0xn+ a1x(n-1) + …. + ak x(n-k) = 0,
x(n-k) [a0xk+ un1x(k-1) + … +ak] = 0,

a0xk + un1xk-1 + . . . . + ak= 0 [ pour x =/= 0]

Étape 2 : Résoudre l'équation caractéristique comme une équation polynomiale. Disons que les racines réelles sont
r1, r2, . . . . , rk. Notez qu'il y a k solutions pour l'équation polynomiale d'ordre k.

Étape 3 : La solution générale de l'équation de récurrence originale est :

tn=∑i=1cjek rjen

Étape 4 : En utilisant des conditions initiales (si disponibles), résolvez pour les coefficients dans l'équation ci-dessus.
afin de trouver la solution particulière.
Exemple 1 :
Résoudre l'équation de récurrence tn- 3tn-1- 4tn-2= 0, pour n >= 2. {Initial condition:
t0=0, t1=1}

Équation caractéristique : xn- 3x(n-1) - 4x(n-2) = 0,

Ou, x(n-2) [x2–3x –4] = 0,
Ou, x2– 3x – 4 = 0,
Ou, x2+ x - 4x - 4 = 0
Ou, x(x+1) –4(x+1) = 0
Ou, (x+1)(x-4) = 0
Par conséquent, les racines sont, x = -1, 4.

Donc, la solution générale de l'équation de récurrence donnée est :

tn= c1(-1)n+ c2(4n)

Utiliser t0= c1+ c2= 0, et t1= -c1+ 4c2= 1. [Remarque, nous avons besoin de deux conditions initiales pour deux
coefficients.]

Sove pour c1et c2,

c1= -(1/5), c2 = (1/5).

52
So, the particular solution is:
tn= (1/5)[4n- (-1)n] = Θ(4n)

1.3.2 Équation de récurrence inhomogène

a0tn+ un1tn-1 + . . . . +aktn-k = bnp(n), où b est un

constant et p(n) est un polynôme d'ordre n.

Solution technique :

Étape 0 : Homogénéiser l'équation donnée à une récurrence homogène équivalente

forme d'équation.

Les étapes 1 à 3 (ou 4) sont les mêmes que dans le cas de la résolution de récurrences homogènes.
équation.

Exemple 2 :

tn- 2tn-1= 3n. [Remarque, il s'agit d'un cas particulier avec p(n) =1, polynôme d'ordre 0, et
il n'y a pas de condition initiale - donc nous obtenons seulement la solution générale.

Transformer avec n->n+1 :

tn+1 – 2tn= 3n+1 Éq(1).

Multipliez l'équation originale par 3 des deux côtés :

3tn- 6tn-1 = 3n+1 Éqn(2).

Soustrayez l'Éqn(2) de l'Éqn(1) :

tn+1 - 5tn+ 6tn-1 = 0, c'est une équation de récurrence homogène qui est équivalente à la
équation inhomogène donnée.

Équation caractéristique : x2- 5 x + 6 = 0.

Quelle est (x-2)(x-3) = 0.

Donc, les racines sont x = 2, 3.

La solution générale de l'équation de récurrence donnée est :

tn= c1(2n) + c2(3n) = Θ(3n)

L'homogénéisation peut nécessiter plusieurs étapes.

Exemple 3 :

tn- 2tn-1 = n

53
Alors, tn+1 - 2tn= n+1
Soustrayant la première équation (donnée) de la dernière équation,
tn+1 - 3tn+ 2tn-1 = 1
Pas encore une équation homogène. Deuxième étape de l'homogénéisation,
tn+2 – 3tn+1 + 2tn= 1
Soustrayez encore une fois,
tn+2 – 4tn+1 + 5tn- 2tn-1 = 0

Maintenant, il s'agit d'une équation de récurrence homogène et on peut la résoudre de la manière habituelle.

1.3.3 Résolution des équations de récurrence à l'aide du théorème maître

Un type spécial d'équation de récurrence qui est fréquemment rencontré dans les algorithmes.
analyses
T(n) = aT(n/b) + cnje, pour un entier constant i, et des constantes de coefficients a et c.
Trois cas :
a = bje, la solution est T(n) = O(njejournalbn);

a > bje, la solution est T(n) = O(nlog_b a);

a < bjela solution est T(n) = O(nje);

Exemple - Multiplication de matrices (algorithme de Strassen)

Considérez le problème du calcul du produit de deux matrices. C'est-à-dire, donné deux

matrices, AetB, calculez le matrice , les éléments de qui sont
donner par

La section montre que l'implémentation directe de l'équation résultats dans un

temps d'exécution. Dans cette section, nous montrons que l'utilisation d'une stratégie de diviser pour régner conduit à
dans un temps d'exécution asymptotiquement légèrement meilleur.

Pour implémenter un algorithme de diviser pour régner, nous devons décomposer le problème donné en
plusieurs sous-problèmes qui sont similaires à l'original. Dans ce cas, nous considérons chacun de
le matrices en tant que matrice, dont les éléments sont sous-matrices.
Ainsi, la multiplication matricielle originale, peut être écrit comme

54
où chaque , et est un matrice.

À partir de l'équation nous comprenons que les sous-matrices résultantes peuvent être calculées comme suit :

Ici, les symboles + et sont considérés comme représentant l'addition et la multiplication (respectivement)

de matrices.

Afin de calculer l'original la multiplication des matrices que nous devons calculer

huit produits matriciels (diviser) suivis de quatre somme de matrices

(conquérir). Puisque l'addition matricielle est unopération, le temps total d'exécution pour le
L'opération de multiplication est donnée par la récurrence :

Remarquez que l'équation est une instance de la récurrence générale donnée dans l'équation.
cas,a=8,b=2, et k=2. Nous pouvons obtenir la solution directement à partir de l'équation.

Puisque , le temps d'exécution total est Mais ça non

mieux que l'original, algorithme direct !

Heureusement, il s'avère que l'une des huit multiplications matricielles est redondante.
Considérez la série suivante de sept matrices:

55
Chaque équation ci-dessus a seulement une multiplication. Dix additions et sept multiplications.
sont nécessaires pour calculer à travers. Donné à travers , nous pouvons calculer le
les éléments de la matrice produit Cas sont les suivants :

En tout, cette approche nécessite sept multiplications de matrices et

18 ajouts. Par conséquent, le temps d'exécution dans le pire des cas est donné par ce qui suit
recurrence:

Comme ci-dessus, Équation est une instance de la récurrence générale donnée dans l'Équation . et
nous obtenons la solution directement à partir de l'équation. Dans ce cas, a=7, b=2 et k=2.

Donc, et le temps de course total est (Utilisez le théorème du maître)

Remarque Par conséquent, le temps d'exécution de la méthode de diviser pour régner

la stratégie de multiplication des matrices est qui est mieux (asymptotiquement) que le
approche directe.

Exemple 2 : Résoudre l'équation de récurrence t(n)=3t(n/2)+1 où t(1)=1

Solution : C'est de la forme :

56
Où a=3, b=2 et f(n)=nd= 10

Donc d=0
Ici a > bdD'où la solution est o(nlog3 2 )

T(n)=o(nlog32) = o(3logn 2)

Vérifiez vos progrès

1. Expliquez le processus de diviser pour régner.
2. Utiliser une approche de diviser pour régner pour écrire un algorithme permettant de trouver le minimum et

maximum dans le tableau.

3. État Master’s theprem.

1.4 RÉSUMÉ
Diviser pour régner : est une technique générale de conception d'algorithmes qui résout un problème en

instance en la divisant en plusieurs instances plus petites (idéalement de taille égale), en résolvant chacune

d'eux de manière récursive, puis en combinant leurs solutions pour obtenir une solution à l'original
instance du problème. De nombreux algorithmes efficaces sont basés sur cette technique, bien que
il peut être à la fois inapplicable et inférieur à des solutions algorithmiques plus simples.

L'efficacité temporelle T(n) de nombreuses techniques de diviser pour régner satisfait à l'équation

T(n)=aT(n/b)+f(n). Le théorème maître établit l'ordre de croissance de ceci

solution de l'équation.
L'algorithme de Strassen n'a besoin que de sept multiplications pour multiplier deux matrices 2 par 2 mais

requiert plus d'ajouts qu'un algorithme basé sur la définition. En explorant la séparation et
technique de conquête, cet algorithme peut multiplier deux matrices n par n en environ n2,807

multiplications.

VOIR
1. 1.1
2. 1.2
3. 1.1

57
 1.11 KEYWORDS
1 θ – Notation asymptotique
2. Théorème de Master – pour résoudre les relations de récurrence de diviser pour régner de manière spécifique
forme.
3. Forme homogène et inhomogène – ce sont des formes d'équations de récurrence.

1.12 RÉPONSES POUR VÉRIFIER VOTRE PROGRÈS

1. 1.2
2. 1.2
3. 1.3
4. 1.4
1.7 EXERCICES DE FIN D'UNITÉ ET RÉPONSES
7. Multipliez deux matrices a={1,2,3,4} et b={1,2,3,4} en utilisant l'algorithme de Strassen.

8. Discutez de l'efficacité d'un algorithme pour trouver le minimum et le maximum dans

le tableau.
9. Discutez des différentes manières de résoudre les équations de récurrence et le temps

complexités.
VOIR
1. 1.3
2. 1.2
3. 1.3
1.11 LECTURES SUGGÉRÉES
1. Introduction à La conception et l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
3. . Analyse et conception d'algorithmes par Padma Reddy

58
 MODULE-3, UNITÉ 2 : TRI

Structure
3.0 Objectifs
1.1 Introduction
1.2 Tri par fusion

1.3 Tri rapide

1.4 Recherche binaire

1,6 Résumé
1,7 Mots clés
1.8 Réponses pour vérifier vos progrès
1.9 Exercices de fin d'unité et réponses

1.10 Suggested readings

5,0 OBJECTIFS
À la fin de cette unité, vous serez capable de

Identifier les différents types de tri

Trouvez la complexité temporelle d'un algorithme de tri

•Différents cas de l'algorithme (pire, meilleur, cas moyen)

•Identifier quel tri est meilleur et pourquoi?
•Identify why binary search and its time complexity

5.1 INTRODUCTION

59
DansinformatiqueUn algorithme de tri est unalgorithmecela met des éléments d'unlistedans un
certaincommandeLes ordres les plus utilisés sont l'ordre numérique etordre lexicographique.
Efficacetriest important pour optimiser l'utilisation d'autres algorithmes (commechercher
and fusionneralgorithmes) qui nécessitent des listes triées pour fonctionner correctement ; Plus formellement, le
la sortie doit satisfaire à deux conditions :

1. La sortie est en ordre non décroissant (chaque élément n'est pas plus petit que le
élément précédent selon le désirécommande totale);
2. La sortie est unpermutation, ou réorganisation, de l'entrée.

Les deux techniques de tri qui suivent de près la méthode de diviser pour régner sont
Tri par fusion
•Tri rapide (tri par échange de partition)

5.2 TRI FUSION

Conceptuellement, un tri par fusion fonctionne comme suit

1. Si la liste a une longueur de 0 ou 1, alors elle est déjà triée. Sinon :

2. Divisez la liste non triée en deux sous-listes d'environ la moitié de la taille.
3. Trier chaque sous-liste récursivementen réappliquant le tri par fusion.
[Link] deux sous-listes à nouveau dans une liste triée.

Voyons maintenant "Quelles sont les étapes du tri par fusion ?" Les différentes étapes qui sont
involved while sorting using merge sort are shown below:
. Divide:Divide the given array consisting ofnelements into two parts of nl2
Recherche d'éléments
Conquérir : Trier la partie gauche du tableau et la partie droite du tableau de manière récursive
utiliser le tri par fusion...
Combinez : Fusionnez la partie gauche triée et la partie droite triée pour obtenir un seul trié.
tableau.
L'opération clé dans le tri par fusion est de combiner la partie gauche triée et la partie droite triée.
partir en un seul tableau trié. Ce processus de fusion de deux vecteurs triés en un seul
un vecteur trié est appelé fusion simple. La seule condition nécessaire pour ce problème est que
les deux tableaux doivent être triés. Maintenant, voyons "Comment concevoir un algorithme de fusion simple ?"

Design:Suppose we have two sorted vectors A and B withmandnelements

respectivement. La procédure suivante est utilisée pour fusionner ces deux vecteurs triés :
Comparez le ième élément du vecteur A avec le jème élément du vecteur B et copiez l'élément le moindre dans le kème.
position du vecteur résultant C (avec 0 comme valeur initiale pour les variables i, j et k).
Le code équivalent peut être écrit comme indiqué ci-dessous :

60
si ( A[i] < B[j] ) alors
C[k] A[i]
k k + l, i i+l
// Copier l'élément le plus bas de A vers C

// Pointer au prochain élément dans C et A

( Fig 2.1 Exemple pour le tri fusion)

Algorithme SimpleMerge(A, bas, milieu, haut)

//But : Fusionner deux tableaux triés où le premier tableau va de bas à moyen et //le
le second commence à partir de mid+1 jusqu'à high.

//Input: A is a sorted from the index positionlowtomid

// A est trié de la position d'index mid+1 à high
A est trié de l'index bas à l'index haut.
je bas, j milieu+l, k bas
tant que (i <= mid et j <= high)
si ( A[i] < A[j] ) alors
C[k] A[i] //Copier le plus bas élément de la première partie de A vers C
je i + 1 //Pointer au prochain élément dans la partie gauche de A
k k+1 //Pointer vers l'élément suivant en C

61
sinon
C[k] A[j]
j j+l
k k + 1;
fin si
fin tant que
// Copier l'élément le plus bas de la deuxième partie de A vers C
// Pointer vers l'élément suivant dans la deuxième partie de A
// Pointer au prochain élément en C
tandis que (i <= milieu) Copiez les éléments restants de la partie gauche de A vers C
C[k] A[i]
k k+l , i i+l
fin alors
tandis que (j <= high) //Copier les éléments restants de la partie droite de A vers C
C[k] A[j]
k k+l; j j+l
fin tant que
for i = low to high
a[i] c[i] Copier les éléments du vecteur C dans le vecteur A
fin pour

//Fin de l'algorithme

Une fois la fusion terminée, nous pouvons facilement trier les nombres par ordre croissant en utilisant
tri par fusion. Iflowandhighsont les limites inférieure et supérieure dans un tableau, le général
La procédure pour trier les éléments en utilisant le tri par fusion est montrée ci-dessous :

si ( bas < haut)

. Diviser le tableau en parties égales
. Trier la partie gauche du tableau de manière récursive
. Trier la partie droite du tableau de manière récursive
. Fusionnez la partie gauche et la partie droite.
fin si
L'algorithme complet pour trier les numéros en utilisant le tri par fusion est montré ci-dessous :

AlgorithmeTriFusion(A, bas, haut)

//But: Trier les éléments du tableau entre la limite inférieure et la limite supérieure
A est un vecteur non trié avec bas et haut comme limite inférieure et limite supérieure
//Output: A is a sorted vector
si(low < high)
milieu (bas + haut)/2 Divisez le tableau en parties égales

62
 TriFusion (a, bas, milieu) // Trier la partie gauche du tableau,

Triage par fusion (a, mid + 1, haut) // Trier la partie droite du tableau

SimpleMerge(a, bas, milieu, haut) Fusionner la partie gauche et la partie droite

Fin si

Analyse : Il est clair d'après l'algorithme que l'instance du problème est divisée en deux
parts égales.
Si le temps pour les opérations de fusion est proportionnel à 'n', alors le temps de calcul pour
Le tri par fusion est décrit par la relation de récurrence.

T(n) = { a n=1,'a' une constante

2T(n/2)+cn n>1, 'c' est une constante.

Quand 'n' est une puissance de 2, n= 2^k, nous pouvons résoudre cette équation par successives.
substitution.
T(n) = 2(2T(n/4) + cn/2) + cn
= 4T(n/4)+2cn
= 4(2T(n/8)+cn/4)+2cn
*
*
= 2^k T(1)+kCn.
= an + cn log n.

Il est facile de voir que si s^k<n<=2^k+1, alors T(n)<=T(2^k+1). Par conséquent,

T(n)=O(n log n)

Avantages
L'algorithme de tri par fusion est un algorithme stable.
Il peut être appliqué à des fichiers de toute taille.

Inconvénients
L'algorithme utilise un espace supplémentaire proportionnel à N. Donc, l'algorithme n'est pas en place.
Il utilise plus de mémoire sur la pile à cause de la récursion.

5,3 TRI RAPIDE

L'approche de diviser pour régner peut être utilisée pour parvenir à un tri efficace.
méthode différente du tri par fusion.

63
 Dans le tri par fusion, le fichier a[1:n] a été divisé en son point médian en sous-tableaux qui
ont été triés indépendamment et ensuite fusionnés.

Dans le tri rapide, la division en 2 sous-tableaux est effectuée de manière à ce que les sous-tableaux triés
ne doit pas être fusionné plus tard.

Cela est accompli en réorganisant les éléments dans a[1:n] de sorte que a[I] <= a[j] pour
tous les i entre 1 et n et tous les j entre (m+1) et n pour un certain m, 1<=m<=n.

Ainsi, les éléments de a[1:m] et a[m+1:n] peuvent être triés indépendamment.

Aucune fusion n'est nécessaire. Ce réarrangement est appelé partitionnement.

La fonction de partition de l'algorithme accomplit une partition en place de la

éléments de a[m:p-1]

On suppose que a[p]>=a[m] et que a[m] est l'élément de partition. Si m=1 &
p-1=n, alors a[n+1] doit être défini et doit être supérieur ou égal à tout
éléments dans a[1:n]

• L'hypothèse que a[m] est l'élément de partition n'est que pour des raisons de commodité, d'autres
les choix pour l'élément de partitionnement que le premier élément de l'ensemble sont meilleurs dans
pratique.

La fonction d'interchange (a,I,j) échange a[I] avec a[j].

[Link] {1, 12, 5, 26, 7, 14, 3, 7, 2} en utilisant le tri rapide.

64
Algorithme : Partitionner le tableau a[m:p-1] autour de a[m]

1. Algorithme Partition(a,m,p)
2. //dans a[m],a[m+1],…..,a[p-1] les éléments
3. // sont réorganisés de manière à ce que si
4. //initialement t=a[m], puis après l'achèvement
5. //a[q]=t pour quelque q entre m et
6. //p-1,a[k]<=t pour m<=k<q, et
7. //a[k]>=t pour q<k<p. q est retourné
8. //Définir a[p]=infini.
9. {
10. v=a[m];I=m;j=p;
11. répéter
12.

65
 13. répéter
14. I=I+1;
15. jusqu'à(a[I]>=v);
16. répéter
17. j=j-1;
18. jusqu'à(a[j]<=v);
19. si (I < j) alors interchanger(a, I, j);
20. }jusqu'à(I>=j);
21. a[m]=a[j]; a[j]=v;
22. retourner j;
23. }

1. Échange d'algorithme(a,I,j)
//Échanger a[I] avec a[j]
3. {
4. p=a[I];
5. a[I]=a[j];
a[j]=p;
7. }

Algorithme Quicksort(p, q)
//Trier les éléments a[p],….a[q] qui résident
//est le tableau global a[1:n] dans l'ordre croissant
3. //ordre; a[n+1] est considéré comme défini
4. // et doit être >= tous les éléments dans a[1:n]
5. {
6. si(p<q) alors // S'il y a plus d'un élément
7.
8. // diviser p en 2 sous-problèmes
9. j=partition(a,p,q+1);
//’j’ est la position de l'élément de partition.
11. //résoudre les sous-problèmes.
12. tri rapide(p,j-1);
13. quicksort(j+1,q);
14. //Il n'est pas nécessaire de combiner la solution.
15. }
16. }

Conception :
Le tri rapide est basé sur le principe de "Diviser pour régner". Le tri rapide fonctionne
très bien sur un grand ensemble de données. Maintenant, voyons "Quelles sont les étapes
impliqué dans le tri rapide ? Les différentes étapes qui sont impliquées lors du tri avec quick
les sort sont affichés ci-dessous :

Étape 1 : Diviser le tableau en deux sous-tableaux :

66
 Left part Élément pivot Partie droite
A[0]A[1]….A[K-1] A[K] A[K+1]A[K+2]…..A[N-1]

Étape 2 : Conquérir : Triez la partie gauche du tableau A[O]A[l]...A[k-l] de manière récursive.

Trier la partie droite du tableau A[k+l] A[k+2] A[kn-l] de manière récursive

Pour simplifier le design, supposons qu'une très grande valeur soit stockée à la fin de la
tableau. Cela est réalisé en stockant 00 dans a[n]. À part a, bas et haut, l'autre
les variables utilisées sont :
i: La valeur initiale de l'index i est faible c'est-à-dire, i la valeur initiale de l'index j est un
plus que haut c'est-à-dire, j élevé
.pivot:a[low]is treated as the pivot element.
La procédure générale pour partitionner le tableau est montrée ci-dessous :
. Continue à incrémenter les index tant que pivot a[i]. Ceci est réalisé à l'aide de la
statement:
est-ce que je i + 1 tant que (pivot >= a[i]);
.. Une fois que la condition ci-dessus échoue, continuez à décrémenter l'index tant que pivotS a[j]
Ceci est réalisé en utilisant l'énoncé :
faire j +- j - 1 tant que (pivot >= a[i]);
Une fois la condition ci-dessus échouée, si i est inférieur à j, échangez a[i] avec a[j] et répétez tout.
le processus ci-dessus tant que i <= j.

Performance du tri rapide

Le temps d'exécution du tri rapide dépend de la façon dont la partition est équilibrée ou non équilibrée.
which in turn depends on which elements of an array to be sorted are used for
partitionnement. Une très bonne partition divise un tableau en deux tableaux de taille égale. Une mauvaise
d'autre part, divise un tableau en deux tableaux de tailles très différentes.
la pire partition ne place qu'un seul élément dans un tableau et tous les autres éléments dans l'autre
tableau. Si le partitionnement est équilibré, le tri rapide fonctionne asymptotiquement aussi vite que le tri par fusion.
trier. D'autre part, si le partitionnement est déséquilibré, le tri rapide fonctionne asymptotiquement
aussi lent que le tri par insertion.

Meilleur cas

La meilleure chose qui pourrait arriver dans le tri rapide serait que chaque étape de partitionnement
divise exactement le tableau en deux. En d'autres termes, le meilleur est d'être la médiane des clés dans
A[p. .r] chaque fois que la procédure 'Partition' est appelée. La procédure 'Partition' divise toujours
le tableau à trier en deux tableaux de taille égale.

Si la procédure 'Partition' produit deux régions de taille n/2, la relation de récurrence est
alors

67
T(n)=T(n/2)+T(n/2)+(n)
= 2T(n/2) + (n)

Et du cas 2 du théorème maître

T(n) = (nlgn)

Pire des cas :

Soit T(n) le temps de pire cas pour le tri rapide sur une taille d'entrée n. Nous avons une relation de récurrence

T(n) = max1≤q≤n-1(T(q) + T(n-q)) + (n) --------- 1

whereqruns de 1 ton-1, puisque la partition produit deux régions, chacune ayant une taille de
au moins 1.

Maintenant, nous devinons que T(n) ≤ cn2pour une certaine constante c.

En substituant notre hypothèse dans l'équation 1. Nous obtenons

T(n) = max1≤q≤n-1(cq2) +c(n-q2)) + (n)

=cmax (q2+ (n-q)2) + (n)

Puisque la seconde dérivée de l'expression q2+ (n-q)2par rapport à q est positif.

Par conséquent, l'expression atteint un maximum sur l'intervalle 1 ≤ q ≤ n - 1 à l'un des
points de terminaison. Cela donne le maximum lié (q2+ (n-q)2)) 1 + (n-1)2 =n2+ 2(n-1).

En continuant notre évaluation de T(n), nous obtenons

T(n) ≤c[n2- 2(n-1)] + (n)

=cn2- 2c(n-1) + (n)

Puisque nous pouvons choisir la constante de sorte que le terme 2c(n-1) domine le terme (n), nous
avoir

T(n) ≤ cn2

Ainsi, le temps d'exécution dans le pire des cas du tri rapide est T(n) = (n2).

68
Analyse de cas moyen

Si la division induite par RANDOMIZED_PARTITION met une fraction constante d'éléments

d'un côté de la partition, alors l'arbre de récurrence a une profondeur (lgn) et (n) le travail est
effectué à (lgn) de ces niveaux. C'est un argument intuitif sur pourquoi le cas moyen
le temps d'exécution de RANDOMIZED_QUICKSORT est (nlgn).

LetT(n) désigne le temps moyen nécessaire pour trier un tableau de n éléments. Un appel à
RAPIDITE_QUICKSORT avec un tableau de 1 élément prend un temps constant, donc nous avons
T(1) = (1).

Après la séparation, RANDOMIZED_QUICKSORT s'appelle lui-même pour trier deux sous-tableaux. Le

le temps moyen pour trier un tableau A[1 . .q] est T[q] et le temps moyen pour trier un tableau
A[q+1 . .n] est T[n-q]. Nous avons

T(n) = 1/n(T(1) +T(n-1) +n-1∑q=1T(q) + T(n-q))) + (n) 1

Nous savons d'après l'analyse du pire des cas

T(1)=(1) et T(n-1)=O(n2)
n-1
T(n) = 1/n( (1) +O(n2)) + 1/n ∑q=1 (r(q) +T(n-q)) + (n)
= 1/n n-1∑q=1(T(q) + T(n-q)) + (n) ------- 2
n-1
= 1/n[2 ∑k=1(T(k)] + (n)
= 2/nn-1∑k=1(T(k) + (n) --------- 3

Résoudre la récurrence ci-dessus en utilisant la méthode de substitution. Supposer inductivement que T(n) ≤

anlgn+bpour certaines constantesa> 0 etb> 0.

Si nous pouvons choisir 'a' et 'b' suffisamment grands pour que nlgn + b > T(1). Alors pour n > 1, nous avons

n-1
T(n) ≥ ∑k=1 2/n (aklgk + b) + (n)
= 2a/nn-1∑k=1klgk -1/8(n2) + 2b/n(n-1) + (n) ------- 4

À ce stade, nous affirmons que

n-1
∑klgk
k=1 ≤ 1/2 n2lgn -1/8(n2)
Insérez cette affirmation dans l'équation 4 ci-dessus et nous obtenons

69
 T(n) ≤ 2a/n[1/2n2lgn- 1/8(n2] + 2/n b(n-1) + (n)
≤ anlgn-an/4 + 2b + (n)

In the above equation, we see that (n) +bandan/4 sont des polynômes et nous sommes certainement
peut choisir 'a' assez grand pour que an/4 domine (n) + b.

Nous concluons que le temps d'exécution moyen de QUICKSORT est (nlg(n)).

Conclusion :

Le tri rapide est un algorithme de tri en place dont le temps d'exécution dans le pire des cas est (n2) et
le temps d'exécution prévu est de (nlgn) où les constantes cachées dans (nlgn) sont petites.

5.4 RECHERCHE BINAIRE

Suppose we are given a number of integers stored in an array A, and we want to locate a
un entier cible spécifique K dans ce tableau. Si nous n'avons aucune information sur la façon dont le
les entiers sont organisés dans le tableau, nous devons examiner séquentiellement chaque élément de la
tableau. Cela est connu sous le nom de recherche linéaire et aurait une complexité temporelle de O(n) dans le
pire scénario. Cependant, si les éléments du tableau sont ordonnés, disons par ordre croissant
ordre, et nous souhaitons déterminer la position d'un entier cible K dans le tableau, nous n'avons pas besoin de
effectuer une recherche séquentielle sur l'ensemble du tableau. Nous pouvons effectuer une recherche plus rapide en utilisant le
Méthode de recherche binaire.

L'idée de base est de commencer par un examen de l'élément du milieu du tableau.

fera naître 3 situations possibles :
Si cela correspond à la cible K, alors la recherche peut se terminer avec succès, en affichant le
indice de l'élément dans le tableau.
D'autre part, si K < A[middle], alors la recherche peut être limitée aux éléments à gauche de
A[milieu]. Tous les éléments à droite du milieu peuvent être ignorés.
S'il s'avère que K > A[milieu], alors la recherche ultérieure est limitée aux éléments à droite.
de A[milieu].
If all elements are exhausted and the target is not found in the array, then the method
retourne une valeur spéciale telle que -1.
Voici une version de la fonction de recherche binaire :

70
Algorithme : RechercheBinaire (int A[ ], int n, int K)
{
L=0, Milieu, R=n-1;
tant que (L<=R)
{
Mid = (L + R) / 2;
si ( K==A[Milieu] )
retourner Mid;
sinon si ( K > A[Milieu] )
L = Milieu + 1;
sinon
R = Mid - 1 ;
}
retourner -1 ;
}
Analyse de la recherche binaire

Meilleur cas : Le meilleur cas se produit lorsque l'élément à rechercher est présent au milieu de
le tableau. Donc, le nombre total de comparaisons nécessaires sera 1. Par conséquent, le temps
la complexité de la recherche binaire dans le meilleur des cas est donnée par Tbest(n)=Ω(1).
Pire scénario : Ce cas se produit lorsque la clé à rechercher se trouve soit à la première position.
ou à la dernière position dans le tableau. Dans de telles situations, le nombre maximum d'éléments
des comparaisons sont nécessaires et la complexité temporelle est donnée par
T(n)={ 1 si n=1
T(n/2) + 1 sinon
Considérez, t(n)=t(n/2)+1
Cette relation de récurrence peut être résolue en utilisant une substitution répétée comme indiqué ci-dessous :
t(n)=t(n/2)+1 remplacer n par n/2
t(n)=1+1+t(n/2 ) 2

t(n)=1+2+t(n/23) remplacer n par n/2

…………..
…………..
En général, t(n)=i+t(n/2)je) Enfin pour obtenir la condition initiale t(1), laissez 2je= n
t(n)=i+t(1) où t(1)=0
t(n)=i Nous avons n=2JePrenez le logarithme des deux côtés
i*log2 = log2n
i= log2n
Donc, la complexité temporelle est donnée par Tavg(n) € (log2n)

Avantages de la recherche binaire

•Technique simple
•Technique de recherche très efficace

Inconvénients de la recherche binaire

Le tableau doit être trié.

71
 Vérifiez vos progrès
Qu'est-ce qu'un tri ?
2. Écrivez un algorithme pour le tri par fusion ? Expliquez son fonctionnement.

3. Écrivez un algorithme pour le tri rapide ? Calculez son meilleur cas, son pire cas et son cas moyen.
complexité temporelle.

4. Expliquez le fonctionnement de la recherche binaire avec un exemple ? Écrivez un algorithme et son temps.

complexité.

5.5 RÉSUMÉ

Le tri par fusion est un algorithme de diviser pour régner. Il fonctionne en divisant un tableau en deux
moitiés, en les triant récursivement, puis en fusionnant les deux moitiés triées pour obtenir le
tableau original trié. L'efficacité temporelle de l'algorithme est la même dans tous les cas c'est-à-dire θ(nlogn).

Le tri rapide est un algorithme de diviser pour régner qui fonctionne en partitionnant son entrée.
éléments selon leur valeur par rapport à un élément pré-sélectionné. Le tri rapide est
remarqué pour son efficacité supérieure parmi les algorithmes nlogn pour le tri des ordres aléatoires
des tableaux mais aussi pour l'efficacité quadratique dans le pire des cas.

La recherche binaire est un algorithme o(logn) pour la recherche dans des tableaux triés. C'est un exemple typique de
une application de la technique de diviser pour régner car elle doit résoudre juste un
problème de moitié de la taille à chacune de ses itérations.

RÉPONSES POUR VÉRIFIER VOS PROGRÈS

1. 1.1
2. 1.2
3. 1.3
4. 1.4
EXERCICES ET RÉPONSES DE FIN D'UNITÉ
10. a.) Quel est le plus grand nombre de comparaisons de clés effectuées par la recherche binaire lors de la recherche

pour une clé dans le tableau suivant ?

{ 3,14,27,31,39,42,55,70,74,81,85,93,98 }
b) Listez toutes les clés de ce tableau qui nécessiteront le plus grand nombre de clés
comparaisons lorsqu'elles sont recherchées par recherche binaire.

11. Appliquez le tri rapide à la liste A N A L Y S I S dans l'ordre alphabétique.

72
 12. Appliquez l'algorithme de tri fusion pour trier A L G O R I T H M par ordre alphabétique ? Est-ce
Le tri par fusion est-il un algorithme stable ?

Réponses : VOIR
1.4
2. 1.3
3. 1.2
5.6 LECTURES SUGGÉRÉES
1. Introduction à la conception et à l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan

73
 MODULE-3, UNITÉ 3 : TECHNIQUE AVARE

Structure
4.0 Objectifs
1.1 Introduction
1.1.1 Concept de méthode gloutonne

1,2 Problèmes d'optimisation

1.3 Résumé
1,4 Mots-clés
1.5 Réponses pour vérifier vos progrès
1.6 Exercices de fin d'unité et réponses

1.7 Suggested readings

6.0 OBJECTIFS
À la fin de cette unité, vous serez capable de
Trouvez comment appliquer la technique gloutonne

•Identifier s'il faut résoudre le problème en utilisant la technique gloutonne

Savoir comment trouver le plus court chemin à partir d'une seule source

•Construire un arbre de Huffman et générer le code de Huffman.

6.1 INTRODUCTION

Les algorithmes gloutons sont simples et directs. Ils sont myopes dans leur
approche dans le sens où ils prennent des décisions sur la base des informations à disposition sans
s'inquiéter des effets que ces décisions pourraient avoir à l'avenir. Ils sont faciles à inventer,
facile à mettre en œuvre et la plupart du temps assez efficace. De nombreux problèmes ne peuvent pas être résolus
correctement par approche gloutonne. Les algorithmes gloutons sont utilisés pour résoudre des problèmes d'optimisation

74
1.1.1 Concept de la méthode gloutonne

L'algorithme glouton fonctionne en prenant la décision qui semble la plus prometteuse à tout moment.
moment; il ne reconsidère jamais cette décision, quelle que soit la situation qui pourrait survenir ensuite.

Comme exemple, considérons le problème de "Faire de la monnaie".

Les pièces disponibles sont :

•dollars (100 centimes)

25 cents
dimes (10 cents)
•nickels (5 cents)
•pennies (1 cent)

Problème : Faire un change d'un montant donné en utilisant le moins de billets possible.
pièces.

Algorithme informel

Commencez avec rien.

•à chaque étape sans dépasser le montant donné.
ajoutez le plus grand aux pièces déjà choisies.

Algorithme formel

Faites un changement pour n unités en utilisant le moins de pièces possible.

FAIRE-CHANGE(n) {

C ← {100, 25, 10, 5, 1} //constants

S ← {}; // Ensemble qui contient la solution

Sum ← 0

Tant que somme != n

75
x=élément le plus grand dans l'ensemble C tel que somme+x <= n

s'il n'y a pas un tel article alors

Aucune solution

S ← S{valeurdex}
somme ← somme+x
RETOUR S }

Example : Make a change for 2.89 (289 cents) here n = 2.89 and the solution contains 2
dollars, 3 quarts, 1 dix et 4 centimes. L'algorithme est avare car à chaque étape
il choisit la plus grande pièce sans se soucier des conséquences. De plus, il ne
change d'avis dans le sens où, une fois qu'une pièce a été incluse dans l'ensemble de solutions, elle
reste là.

1.1.2 Caractéristiques et fonctionnalités des problèmes résolus par les algorithmes gloutons

Pour construire la solution de manière optimale. L'algorithme maintient deux ensembles. L'un contient
articles choisis et l'autre contient des articles rejetés.

L'algorithme glouton se compose de quatre (4) fonctions.

Une fonction qui vérifie si l'ensemble d'articles choisi fournit une solution.
2. Une fonction qui vérifie la faisabilité d'un ensemble.
3. La fonction de sélection indique lequel des candidats est le plus prometteur.
4. Une fonction objectif, qui n'apparaît pas explicitement, donne la valeur d'un
solution.

Algorithme glouton de structure

•Au départ, l'ensemble des éléments choisis est vide c'est-à-dire, l'ensemble des solutions.

•À chaque étape
Un élément sera ajouté à un ensemble de solutions en utilisant une fonction de sélection.

si l'ensemble n'était plus réalisable

. rejeter les éléments en cours d'examen (et ne jamais les considérer à nouveau).
SINON SI l'ensemble est toujours faisable ALORS

. ajoutez l'élément actuel.

76
 1.1.3 Définitions de la faisabilité

Un ensemble réalisable (de candidats) est prometteur s'il peut être étendu pour produire non seulement un
solution, mais une solution optimale au problème. En particulier, l'ensemble vide est
toujours prometteur pourquoi ? (parce qu'une solution optimale existe toujours)

Contrairement à la programmation dynamique, qui résout les sous-problèmes de bas en haut, une approche gloutonne

la stratégie progresse généralement de manière descendante, faisant un choix avide après l'autre
un autre, réduisant chaque problème à un plus petit.

Propriété de choix avide

La « propriété du choix glouton » et « la structure optimale » sont deux ingrédients dans le

problème qui mène à une stratégie avide.

Propriété du choix avide

Il est dit qu'une solution globalement optimale peut être atteinte en faisant un choix localement optimal.
choix.

6.2 PROBLÈMES D'OPTIMISATION

1.2.1 Codes de Huffman

Le code de Huffman est une technique de compression de données. L'algorithme avide de Huffman examine
l'occurrence de chaque caractère et sa représentation sous forme de chaîne binaire de manière optimale.

Exemple

Supposons que nous avons des données composées de 100 000 caractères que nous voulons compresser. Le
les caractères dans les données apparaissent avec les fréquences suivantes.

a b c d e f
Frequency 45,000 13,000 12,000 16,000 9,000 5,000

77
Considérez le problème de concevoir un "code de caractères binaire" dans lequel chaque caractère est
représenté par une chaîne binaire unique.

Code de longueur fixe

Dans un code à longueur fixe, il faut 3 bits pour représenter six (6) caractères.

a b c d e f
Fréquence 45,000 13,000 12,000 16,000 9,000 5,000
Longueur Fixe
000 001 010 011 100 101
code

Cette méthode nécessite 3 000 000 bits pour coder l'intégralité du fichier.

Comment obtenons-nous 3000 000 ?

•Le nombre total de caractères est de 45 000 + 13 000 + 12 000 + 16 000 + 9 000 +
5 000 = 1 000 000.
•Chaque caractère se voit attribuer un code de 3 bits => 3 * 1000 000 = 3000 000 bits.

Conclusion

Le code à longueur fixe nécessite 300 000 bits tandis que le code variable nécessite 224 000 bits.

Économie d'environ 25 %.

Codes de préfixe

In which no codeword is a prefix of other codeword. The reason prefix codes are
désirable est qu'ils soient simplement encodés (compression) et décodés.

Pouvons-nous faire mieux ?

Un code de longueur variable peut faire mieux en attribuant des mots de code courts aux caractères fréquents et
caractères peu fréquents mots de code longs.

a b c d e f
Fréquence 45,000 13,000 12,000 16,000 9,000 5,000
Longueur Fixe
0 101 100 111 1101 1100
code

78
Character 'a' are 45,000
chaque caractère 'a' assigné un code de 1 bit.
1 * 45 000 = 45 000 bits.

Les caractères (b, c, d) sont 13 000 + 12 000 + 16 000 = 41 000

chaque caractère se voit attribuer un code de 3 bits
3 * 41 000 = 123 000 bits

Les caractères (e, f) sont 9 000 + 5 000 = 14 000

chaque caractère se voit attribuer un code de 4 bits.
4 * 14 000 = 56 000 bits.

Cela implique que le total des bits est : 45 000 + 123 000 + 56 000 = 224 000 bits

Encodage : Concaténez les mots de code représentant chaque caractère du fichier.

Encodage de chaîne
THÉ 10 00 010
MER 011 00 010
DIX 10 00 110

ExampleFrom variable-length codes table, we code the3-character file abc as:

un b c
0.101.100 =
0 101 100
0101100

Décodage

Puisqu'aucun mot de code n'est le préfixe d'un autre, le mot de code qui commence un fichier encodé est
sans équivoque.

79
Pour décoder (revenir au caractère original), retirez-le du fichier encodé et
analyser de manière répétée.
Par exemple, dans le tableau "codeurs à longueur variable", la chaîne 001011101 se décompose de manière unique.
en 0.0.101.1101, qui se décode en toaabe.

La représentation du "processus de décodage" est un arbre binaire, dont les feuilles sont des caractères. Nous
interpret the binary codeword for a character as path from the root to that character,
où 0 signifie "aller à l'enfant gauche" et 1 signifie "aller à l'enfant droit". Notez qu'un
Le code optimal pour un fichier est toujours représenté par un arbre binaire complet.

1.2.2 L'algorithme de Dijkstra (algorithme du plus court chemin à source unique)

L'algorithme de Dijkstra résout le problème du chemin le plus court à partir d'une source unique lorsque toutes les arêtes ont
poids non négatifs. C'est un algorithme glouton. L'algorithme commence au sommet source, s, il
croît un arbre, T, qui couvre finalement tous les sommets accessibles depuis S. Les sommets sont ajoutés à
T dans l'ordre de distance, c'est-à-dire d'abord S, puis le sommet le plus proche de S, puis le suivant le plus proche, et ainsi de suite.
La mise en œuvre suivante suppose que le graphe G est représenté par une matrice d'adjacence.

Énoncé du problème : Trouver la distance la plus courte d'une source unique à différents
villes.

Algorithme : DIJKSTRA (G, w, s)

1. INITIALISER SOURCE UNIQUE (G, s)

2. S ← { } // S contiendra finalement les sommets des poids de chemin les plus courts finaux
de s
3. Initialiser la file de priorité Q c'est-à-dire, Q ← V[G]
4. tant que la file de priorité Q n'est pas vide faites
5. u ← EXTRAIRE_MIN(Q) // Extraire le nouveau sommet
6. S ← S {u}
// Effectuer une relaxation pour chaque sommet adjacent à u
7. pour chaque sommet v dans Adj[u] faire
8. Détendez (u,v,w)

Example: Step by Step operation of Dijkstra algorithm.

Étape 1. Étant donné le graphe initial G=(V, E). Tous les nœuds ont un coût infini sauf le
noeud source, s, qui a 0 coût.

80
Étape 2. Tout d'abord, nous choisissons le nœud qui est le plus proche du nœud source, s. Nous initialisons d[s]
à 0. Ajoutez-le à S. Détendez tous les nœuds adjacents à la source, s. Mettez à jour le prédécesseur (voir la flèche rouge
dans le diagramme ci-dessous) pour tous les nœuds mis à jour.

Étape 3. Choisissez le nœud le plus proche, x. Détendez tous les nœuds adjacents au nœud x. Mettez à jour
predecessors for nodes u, v and y (again notice red arrows in diagram below).

Étape 4. Maintenant, le nœud y est le nœud le plus proche, donc ajoutez-le à S. Détendez le nœud v et ajustez-le.
prédécesseur (les flèches rouges se souviennent !).

81
Étape 5. Maintenant, nous avons le nœud u qui est le plus proche. Choisissez ce nœud et ajustez son voisin.
nœud v.

Étape 6. Enfin, ajoutez le nœud v. La liste des prédécesseurs définit maintenant le chemin le plus court de chaque
nœud vers le nœud source, s.

82
Analyse

Comme l'algorithme de Prim, l'algorithme de Dijkstra s'exécute en O(|E|lg|V|) temps.

Vérifiez vos progrès

1. Expliquez la méthode gloutonne de résolution de problèmes avec un exemple.

2. Écrivez une note sur le codage de Huffman.

3. Écrivez un algorithme pour le chemin le plus court à source unique en utilisant la technique gloutonne.

avec l'exemple.

1.3 SUMMARY
La technique gloutonne suggère de construire une solution à un problème d'optimisation.
à travers une séquence d'étapes, chacune développant une solution partiellement construite obtenue ainsi

jusqu'à ce qu'une solution complète au problème soit atteinte. À chaque étape, le choix fait
doit être réalisable, localement optimal et irrévocable.
L'algorithme de Dijkstra résout le problème du chemin le plus court à partir d'une source unique en trouvant le plus court.

chemins d'un sommet donné (la source) vers tous les autres sommets d'un graphe pondéré ou
digraph.
Le code de Huffman est un schéma d'encodage optimal à longueur variable, sans préfixe, qui assigne des bits.

chaîne en caractères en fonction de leurs fréquences dans un texte donné. Cela est réalisé par un
construction avide d'un arbre binaire dont les arêtes sont étiquetées avec des 0 et des 1.

1.4KEYWORDS
1 Technique gloutonne – C'est une méthode (approche) de résolution de problèmes.

2. L'arbre de Huffman - C'est un arbre binaire généré par l'algorithme de Huffman ayant un enfant gauche.
poids de l'arête comme 0 et poids de l'enfant droit comme 1.

1.5RÉPONSES POUR VÉRIFIER VOTRE PROGRÈS

1. 1.1

83
 2. 1.2
3. 1.2
1.6 UNIT-END EXERCISES AND ANSWERS
1.a. Compare l'encodage à longueur fixe avec l'encodage à longueur variable
b. Prouvez que l'encodage à longueur variable est meilleur que l'encodage à longueur fixe.
c. Est-ce que l'encodage Huffman peut être utilisé pour la compression de données, défendez votre

répondre avec l'exemple.

2. Discutez de la façon dont l'algorithme de Dijkstra appartient à la technique gloutonne avec l'exemple.

Réponses : VOIR
1. 1.3
2. 1.3
1.7 SUGGESTED READINGS
1. Introduction à La conception et l'analyse des algorithmes par Anany Levitin
2. Analyse et conception des algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
Analyse et conception d'algorithmes par Padma Reddy

84
 MODULE-3, UNITÉ 3 : APPLICATIONS DE LA MÉTHODE GLOUTONNE

Structure
5.0 Objectifs
1.1 Introduction
1.2 Problème de chargement de conteneur

1.3 Problème du sac à dos 0/1

1.4 Algorithmes d'arbre couvrant de coût minimum

1,6 Résumé
1.7 Mots-clés
1.8 Réponses pour vérifier vos progrès
1,9 Exercices et réponses de fin d'unité

1.10 Suggested readings

7.0 OBJECTIVES
À la fin de cette unité, vous serez capable de
Résoudre des problèmes de chargement de conteneurs et de sac à dos.

Trouvez les chemins les plus courts en utilisant les algorithmes de Prim et de Kruskal.

•Identifier la différence entre un arbre de graphe et un arbre couvrant de poids minimum.

7.1 INTRODUCTION

La méthode gloutonne est la technique la plus simple conçue.

Comme le nom l'indique, ils ont une approche à court terme dans leur prise de décision.
la base des informations immédiatement à portée de main sans se soucier de
effect these decision may have in the future.

DÉFINITION :
Un problème avec N entrées aura certaines contraintes. Tous les sous-ensembles qui satisfont ces contraintes.
les contraintes sont appelées une solution réalisable.
Une solution réalisable qui peut soit maximiser, soit minimiser une fonction d'objectif donnée.
est appelé une solution optimale.

7,2 PROBLÈME DE CHARGEMENT DE CONTENEUR

85
 Le problème de chargement de conteneurs est presque similaire au problème du sac à dos et aussi
semblable à un autre problème intéressant appelé problème de rangement. Le chargement de conteneurs
est énoncé comme suit :

Nous avons des conteneurs de taille égale à charger sur le cargo et en retour, le cargo doit
être chargé sur le navire. Chaque conteneur a un poids, wi et la cargaison a un maximum
capacité de c unités. L'objectif de ce problème est de charger le navire avec un maximum
nombre de conteneurs. Soit xi une variable, prenant les valeurs 0 ou 1. Un 1 indique que
Un 1 signifie que le conteneur doit être chargé et un 0 signifie qu'il ne doit pas l'être.
Formellement, nous pouvons définir le problème comme suit,

Maximiser
Soumis aux contraintes, de i=1 à n, [Link]<= C

Stratégie avide
Dans ce problème, heureusement, nous n'avons pas le profit qui doit être considéré pour
contraintes. Comme l'objectif est de charger le maximum de conteneurs, le
la stratégie avide que nous utilisons est :
Inclure les conteneurs de la plus basse à la plus haute (c'est-à-dire par ordre croissant de poids)
poids afin que nous puissions empiler plus de conteneurs.
Example
Considérez un chargement de conteneurs avec n=7,
{w1,w2,w3,w4,w5,w6,w7}={90,190,40,80,140,40,40,10} and C=300.
Sol : Lorsque les conteneurs sont disposés dans l'ordre croissant de leur poids, nous
get {w1,w2,w3,w4,w5,w6,w7}={ 10, 40, 40,80,90,140,190}
{ 1, 1, 1, 1, 1, 0, 0 }
Par conséquent, la solution est {1,0,1,1,0,1,1}
Nombre total de conteneurs=5
Poids total=260

7.3 PROBLÈME DU SAC À DOS

Un voleur qui cambriole un magasin et peut porter un poids maximal de w dans leur
sac à dos. Il y a n articles et ithpoids de l'article wjeet vaut vjedollars. Quels articles
que doit prendre un voleur ?

86
Il y a deux versions du problème

Problème du sac à dos fractionnaire

La configuration est la même, mais le voleur peut prendre des fractions d'objets, ce qui signifie que les objets peuvent être
cassé en morceaux plus petits afin que le voleur puisse décider de ne transporter qu'une fraction de xjedes articles
où 0 ≤ xje≤ 1.

Exposer la propriété du choix avare.

. L'algorithme glouton existe.

Exhiber la propriété de sous-structure optimale.

. ?????

problème du sac à dos 0-1

La configuration est la même, mais les objets ne peuvent pas être divisés en morceaux plus petits, donc le voleur peut
décidez soit de prendre un article soit de le laisser (choix binaire), mais vous ne pouvez pas en prendre une fraction de
un article.

Exhibez l'absence de propriété de choix avide.

. Aucun algorithme glouton n'existe.

Exhiber la propriété de sous-structure optimale.

. Il n'existe qu'un algorithme de programmation dynamique.

1.3.1 Problème du sac à dos 0-1 utilisant la programmation dynamique

Nous avons n objets et un sac ou un sac avec une capacité M. L'objet I a un

poids Wi où I varie de 1 à N.
Le problème est que nous devons remplir le sac avec l'aide de N objets et le résultat
le profit doit être maximal.
Formellement, le problème peut être énoncé comme
Maximiser xipi soumis à XiWi<=M
Où Xi est la fraction de l'objet et elle se situe entre 0 et 1.
Il y a tellement de façons de résoudre ce problème, ce qui donnera de nombreuses solutions réalisables.
solution pour laquelle nous devons trouver la solution optimale.
•Mais dans cet algorithme, il ne générera qu'une seule solution qui sera
faisable ainsi que optimale.
•First, we find the profit & weight rates of each and every object and sort it
selon l'ordre descendant des ratios.

87
 •Sélectionnez un objet avec le plus haut ratio p/w et vérifiez si sa hauteur est inférieure à
la capacité du sac.
Si c'est le cas, placez 1 unité du premier objet et diminuez la capacité du sac de
poids de l'objet que vous avez placé.
Répétez les étapes ci-dessus jusqu'à ce que la capacité du sac devienne inférieure au poids.
de l'objet que vous avez sélectionné. Dans ce cas, placez une fraction de l'objet et
come out of the loop.
•Chaque fois que vous sélectionnez.

La formulation la plus courante du problème est le problème du sac à dos 0-1, qui
limite le nombrejede copies de chaque type d'article à zéro ou un. Mathématiquement, le
Le problème du sac à dos 0-1 peut être formulé comme :

. maximiser

. sous réserve de

Le problème du sac à dos borné restreint le nombre xjede copies de chaque type d'article à
une valeur entière maximalejeMathématiquement, le problème du sac à dos borné peut être
formulé comme :

. maximiser

. sous réserve de

Algorithme : Sac à dos(n,m,w,p,v)

n - nombre d'objets à sélectionner
m- capacité du sac à dos
w - poids de tous les objets
p- profits de tous les objets
v- la solution optimale pour le nombre d'objets sélectionnés avec spécifié
capacité restante

Pour i 0 à n faire
Pour j de 0 à m faire
Si(i=0 ou j=0)
v[i,j]=0

88
 Sinon si(w[i]>j)
v[i,j]=v[i-1,j]
sinon
v[i,j]=max(v[i-1,j],v[i-1,j-w[i]]+p[i])
fin si
fin pour
fin pour

Algorithme : objetselectionné(n,m,w,v,x)

n – nombre d'objets à sélectionner

m - capacité du sac à dos
w – poids de tous les objets
p- profits de tous les objets

//Output : x- the information of objects selected and not selected

Pour i 0 à n-1 faire

X[i]=0
Fin pour
I=n; j=m
Tant que (i != 0 et j != 0)
{
If(v[I,j] != v[i-1,j])
{ x[i]=1; j=j-w[i] }
}
i=i-1
}
Pour i 1 à n faire
Si(x[i]=1)
objet que j'ai sélectionné
Fin si
Fin pour

Exemple :
Étant donné certains articles, remplissez le sac à dos pour obtenir la valeur totale maximale. Chaque article a
un certain poids et une certaine valeur. Le poids total que nous pouvons porter n'est pas supérieur à un certain fixe
numéro W. Nous devons donc considérer les poids des articles ainsi que
leur valeur.
Item #Weight Value
1 2 12
2 1 10 La capacité maximale est c'est-à-dire M=5
3 3 20
4 2 15

89
Solution : le profit optimal obtenu est de 37 en sélectionnant les objets 1, 2 et 4.

1.4 ALGORITHME D'ARBRE COUVRANT DE COÛT MINIMUM

Un arbre couvrant d'un graphe est tout arbre qui inclut chaque sommet du graphe.
Formellement, un arbre couvrant d'un graphe G est un sous-graphe de G qui est un arbre et contient tous les
les sommets de G. Une arête d'un arbre couvrant est appelée une branche ; une arête dans le graphe qui est
ce qui n'est pas dans l'arbre couvrant s'appelle un accord. Nous construisons un arbre couvrant chaque fois que nous le souhaitons

trouver un moyen simple, bon marché et pourtant efficace de connecter un ensemble de terminaux (ordinateurs,
cités, usines, etc.). Les arbres couvrants sont importants pour les raisons suivantes.

Arbre couvrant minimal

Un arbre couvrant de poids minimal (MST) d'un graphe pondéré G est un arbre couvrant de G dont
edges sum is minimum weight. In other words, a MST is a tree formed from a subset of
les arêtes dans un graphe non orienté donné, avec deux propriétés :

• il couvre le graphique, c'est-à-dire qu'il inclut chaque

sommet du graphique.
• c'est un minimum, c'est-à-dire, le poids total de tous
les bords sont aussi bas que possible.

Soit G=(V, E) un graphe connexe et non orienté où V est un ensemble de sommets (noeuds) et E
est l'ensemble des arêtes. Chaque arête a une longueur donnée non négative.

1 ALGORITHME DE PRIMS :

Cet algorithme a d'abord été proposé par Jarnik, mais est généralement attribué à Prim. Il commence par
un sommet arbitraire (racine) et à chaque étape, ajouter une nouvelle branche (arête) à l'arbre déjà
construit ; l'algorithme s'arrête lorsque tous les sommets du graphe ont été atteints.

90
Cette stratégie est avide dans le sens où à chaque étape, l'arbre couvrant partiel est
augmenté d'un bord qui est le plus petit parmi tous les bords adjacents possibles.

Exemple :

Commencez par un sommet arbitraire (racine). À chaque étape, ajoutez une nouvelle branche (arête) au
l'arbre déjà construit ; l'algorithme s'arrête lorsque tous les sommets du graphe ont été
atteint.

Algorithmprims(e,cost,n,t)

Soit (k,l) un arc de coût minimum dans E;

Mincost :=cost[k,l];

T[1,1]:=k; t[1,2]:=l;

Pour I:=1 à n faire

Si (coût[i,l] < coût[i,k]) alors près[i] := l;

Sinon près[i] := k;
Près[k]:=près[l]:=0;
Pour i:=2 à n-1 faire
{
Soit j un indice tel que near[j]≠0 et
Coût[j,près[j]] est minimum;
T[i,1]:=j; t[i,2]:=near[j];
Mincost:=mincost+ Coût[j,près[j]];

91
 Près[j]:=0;
Pour k:=0 à n faire
Si près((near[k]≠0) et (Cost[k,near[k]]>cost[k,j])) alors
Proche[k]:=j;
}
Return mincost;

L'algorithme de Prim commencera avec un arbre qui n'inclut qu'une arête de coût minimum.
de G.
•Ensuite, les arêtes sont ajoutées à l'arbre une par une. La prochaine arête (i,j) à être ajoutée dans
tel que I est un sommet inclus dans l'arbre, j est un sommet non encore inclus, et le coût
de (i,j), cost[i,j] est minimum parmi tous les arêtes.
•Le fonctionnement de Prim sera expliqué par le diagramme suivant

Step 1: Étape 2 :

Étape 3 : Étape 4 :

Étape 5 : Étape 6 :

92
 Analyse :

L'algorithme passe la majeure partie de son temps à trouver la plus petite arête. Donc, le temps du
l'algorithme dépend essentiellement de la façon dont nous recherchons cette arête.
Méthode simple
Il suffit de trouver la plus petite arête en recherchant dans la liste d'adjacence des sommets dans V. Dans ce
case, each iteration costs O(m) time, yielding a total running time of O(mn).

2. L'ALGORITHME DE KRUSKAL :

Dans l'algorithme de Kruskal, la fonction de sélection choisit les arêtes par ordre croissant de
longueur sans se soucier trop de leur connexion aux arêtes précédemment choisies,
sauf qu'ils ne forment jamais de cycle. Le résultat est une forêt d'arbres qui croît jusqu'à ce que tout le
Les arbres dans une forêt (tous les composants) fusionnent en un seul arbre.

• Dans cet algorithme, un arbre couvrant de coût minimal 'T' est construit bord à bord.
• Les arêtes sont considérées pour inclusion dans 'T' par ordre croissant de leur coût.

Une arête est incluse dans 'T' si elle ne forme pas de cycle avec une arête déjà présente dans T.
•To find the minimum cost spanning tree the edge are inserted to tree in increasing
ordre de leur coût

Algorithme :
Algorithme kruskal(E,cost,n,t)
//E un ensemble d'arêtes dans G a 'n' sommets.
//coût[u,v] coût de l'arête (u,v).t ensemble de branches dans un arbre couvrant de coût minimum
// le premier coût est retourné.
{
pour i=1 à n faire parent[I]=-1;
I=0;mincost=0.0;
Tant que((I<n-1) et (tas non vide)) faire
{
j=find(n);

93
k=trouver(v);
si(j n'est pas égal à k) alors
{
i=i+1
t[i,1]=u;
t[i,2]=v;
mincost=mincost+coût[u,v];
union(j,k);
}
}
si(i non égal n-1) alors écrire("Pas d'arbre couvrant")
sinon retourner le coût minimum;
}
Analyse
La complexité temporelle de l'algorithme de l'arbre couvrant de coût minimum dans le pire des cas est
O(|E|log|E|),
où E est l'ensemble des arêtes de G.

Exemple : Fonctionnement étape par étape de l'algorithme de Kruskal.

Étape 1. Dans le graphique, l'arc(g, h) est le plus court. Soit le sommet g soit le sommet h pourrait être
représentatif. Choisissons arbitrairement le sommet g.

Étape 2. L'arête (c, i) crée le deuxième arbre. Choisissez le sommet c comme représentant pour
deuxième arbre.

94
Étape 3. L'arête (g, g) est la prochaine arête la plus courte. Ajouter cette arête et choisir le sommet g comme

représentant.

Étape 4. L'arête (a, b) crée un troisième arbre.

Étape 5. Ajouter l'arête (c, f) et fusionner les deux arbres. Le sommet c est choisi comme représentant.

Étape 6. L'arête (g, i) est la suivante la moins chère, mais si nous ajoutons cette arête, un cycle se formerait.

créé. Le sommet c est le représentant des deux.

Étape 7. Au lieu de cela, ajoutez l'arête (c, d).

95
Étape 8. Si nous ajoutons l'arête (h, i), l'arête (h, i) créerait un cycle.

Étape 9. Au lieu d'ajouter l'arête (h, i), ajoutez l'arête (a, h).

Étape 10. Encore une fois, si nous ajoutons l'arête (b, c), cela créerait un cycle. Ajoutez plutôt l'arête (d, e) pour

complétez l'arbre couvrant. Dans cet arbre couvrant, tous les arbres sont reliés et le sommet c est seul
représentant.

96
 Vérifiez vos progrès

1. Expliquez le problème de chargement de conteneurs avec un exemple

2. Discutez du problème du sac à dos 0/1 avec un exemple

3. Écrivez l'algorithme de Prim pour la génération d'un arbre couvrant minimal ? Expliquez-le avec le

exemple.
4. Écrivez l'algorithme de Kruskal pour la génération d'un arbre couvrant minimal. Expliquez-le avec le

exemple.

SUMMARY:
Le problème de chargement de conteneurs consiste à remplir un plus grand nombre de conteneurs dans le bateau soumis à

certaines contraintes spécifiées.

Le problème du sac à dos consiste à sélectionner des objets parmi n objets qui génèrent plus de profit et

dans lequel la somme du poids des objets sélectionnés ne doit pas dépasser le poids du sac à dos.

Prims et Kruskal sont les deux algorithmes pour générer des arbres couvrants de poids minimum. Donc que
on peut facilement parcourir l'ensemble du graphe avec moins de coût.

1.13 KEYWORDS
1 Arbre de recouvrement minimal – c'est un arbre qui consiste en tous les sommets du graphe avec très

peu de nombres de coins et aussi le poids total de l'arbre couvrant est minimum.

1.14 RÉPONSES POUR VÉRIFIER VOTRE PROGRESSION

1. 1.2
2. 1.3
3. 1.4(1)
4. 1.4(2)
1.7 EXERCICES ET RÉPONSES DE FIN D'UNITÉ

13. List out the difference between Prim’s algorithm and Kruskal’s algorithm.
14. Comparez le problème de chargement de conteneurs avec le problème du sac à dos

Réponses : VOIR
1. 1.4 (1 et 2)

97
 2. 1.2 & 1.3

1.12 LECTURES SUGGÉRÉES

1. Introduction à la conception et à l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
3. Analyse et conception d'algorithmes par Padma Reddy

4. Même, Shimon., "Algorithmes de graphes", Presses de science informatique.

98
 MODULE-4, UNITÉ 1 INTRODUCTION AUX GRAPHES

Structure
1.0 Objectifs
1.1 Graphes en tant que structures de données

1.2 Graph representation

Matrice d'adjacence
Liste d'adjacence
1.3 Parcours en profondeur (DFS)
1.4 Summary
1.5 Keywords
1.6 Réponses pour vérifier vos progrès
1.7 Exercices de fin d'unité et réponses
1.8 Suggested readings

8.0 OBJECTIVES
À la fin de cette unité, vous serez capable de

Représentez le graphe dans un ordinateur en utilisant une matrice d'adjacence ou une liste d'adjacence.
type de liste.
•Identifiez quelle méthode de représentation graphique est meilleure et quand.
•Parcourir le graphe en utilisant le parcours DFS et sa complexité temporelle.

8.1 GRAPHIQUES EN TANT QUE STRUCTURE DE DONNÉES

1.1.1 Introduction au graphique :

Les graphes sont des structures largement utilisées en informatique et dans différents domaines de l'informatique.

applications. Nous ne disons pas structure de données ici et voyons la différence. Les graphes signifient
stocker et analyser les métadonnées, les connexions, qui sont présentes dans les données. Par exemple,

considérez les villes de votre pays. Le réseau routier qui les relie peut être
représenté sous forme de graphique puis analysé. Nous pouvons examiner si une ville peut être atteinte
d'un autre ou trouver le chemin le plus court entre deux villes.

Tout d'abord, nous introduisons quelques définitions sur les graphes. Ensuite, nous allons montrer,
comment les graphes sont représentés à l'intérieur d'un ordinateur. Ensuite, vous pouvez vous tourner vers le graphe de base

algorithmes.

Il y a deux ensembles d'objets importants, qui spécifient le graphe et sa structure. Le premier ensemble
isV,which is calledvertex-set. In the example with road network cities are vertices.

99
Chaque sommet peut être représenté par un cercle avec le numéro du sommet à l'intérieur.

sommets

Le prochain ensemble important est E, qui est appelé l'ensemble des arêtes. E est un sous-ensemble de V x V. Simplement

en parlant, chaque arête relie deux sommets, y compris le cas où un sommet est
connecté à lui-même (un tel arête est appelé une boucle). Tous les graphes sont divisés en deux grands
groupes : graphes orientés et non orientés. La différence est que les arêtes dans les graphes orientés,
les arcs appelés, ont une direction. Ces types de graphiques ont beaucoup en commun avec chacun
d'autres, mais des différences significatives sont également présentes. Nous allons accentuer quel type de
les graphes sont considérés dans la description d'algorithme particulière. Une arête peut être dessinée comme un

ligne. Si un graphique est orienté, chaque ligne a une flèche.

graphe non orienté graphe dirigé

Maintenant, nous présentons quelques définitions de base des graphes.

Séquence de sommets, de sorte qu'il y a une arête de chaque sommet au suivant dans
La séquence est appelée chemin. Le premier sommet du chemin est appelé le sommet de départ ; le dernier
le sommet dans le chemin est appelé le sommet terminal. Si les sommets de départ et d'arrivée sont les mêmes,
Un chemin est appelé cycle. Un chemin est appelé simple s'il inclut chaque sommet une seule fois.
Un cycle est appelé simple s'il inclut chaque sommet, sauf celui de départ (de fin), uniquement.
Une fois. Voyons des exemples de chemin et de cycle.

100
chemin (simple) cycle (simple)

La dernière définition que nous donnons ici est celle d'un graphe pondéré. Un graphe est appelé pondéré, si chaque

L'arête est associée à un nombre réel, appelé poids de l'arête. Par exemple, dans la route
exemple de réseau, le poids de chaque route peut être sa longueur ou le temps minimal nécessaire pour

avancez.

graphe pondéré

1.2 Représentation des graphiques

Il existe plusieurs manières possibles de représenter un graphe dans l'ordinateur. Nous allons
discuter de deux d'entre eux : matrice d'adjacence et liste d'adjacence.

a) Matrice d'adjacence

Chaque cellule aijd'une matrice d'adjacence contient 0, s'il y a une arête entre le i-ème et le j-ème

101
sommets, et1autrement. Avant de discuter des avantages et des inconvénients de ceci
kind of representation, let us see an example.

Le graphe présenté par exemple est non orienté. Cela signifie que sa matrice d'adjacence est
symétrique. En effet, dans un graphe non orienté, s'il y a une arête (2, 5), alors il y a aussi une
arête (5, 2). C'est aussi la raison pour laquelle il y a deux cellules pour chaque arête dans le
échantillon. Les boucles, si elles sont autorisées dans un graphe, correspondent aux éléments diagonaux de
une matrice d'adjacence.

Avantages. La matrice d'adjacence est très pratique à utiliser. Ajouter (supprimer) un

une arête peut être effectuée en temps O(1), le même temps est requis pour vérifier s'il y a une arête
entre deux sommets. De plus, il est très simple à programmer et dans tous nos tutoriels sur les graphes
nous allons travailler avec ce type de représentation.

Inconvénients.

La matrice d'adjacence consomme une énorme quantité de mémoire pour stocker de grands graphes.
Tous les graphes peuvent être divisés en deux catégories, les graphes clairsemés et les graphes denses. Clairsemé
les ones ne contiennent pas beaucoup de bords (le nombre de bords est beaucoup moins, que le carré de
nombre de sommets, |E| << |V| 2). D'autre part, les graphes denses contiennent
nombre d'arêtes comparable au carré du nombre de sommets. Adjacence
matrix is optimal for dense graphs, but for sparse ones it is superfluous.
Le prochain inconvénient de la matrice d'adjacence est que dans de nombreux algorithmes, vous devez

connaitre les arêtes, adjacentes au sommet actuel. Pour dessiner de telles informations
à partir de la matrice d'adjacence, vous devez parcourir la ligne correspondante, qui
résultats en complexité O(|V|). Pour des algorithmes comme DFS ou basés sur cela, l'utilisation de
la matrice d'adjacence entraîne une complexité globale de O(|V|) 2), tandis que cela peut être
réduit à O(|V| + |E|), lors de l'utilisation d'une liste d'adjacence.
Le dernier inconvénient, nous voulons attirer votre attention, est que l'adjacence
La matrice nécessite de gros efforts pour ajouter/retirer un sommet. Dans le cas où un graphe est

102
 utilisé uniquement pour l'analyse, ce n'est pas nécessaire, mais si vous voulez construire complètement
structure dynamique, l'utilisation de la matrice d'adjacence la rend assez lente pour les grands graphes.

Pour résumer, la matrice d'adjacence est une bonne solution pour les graphes denses, ce qui implique d'avoir
nombre constant de sommets.

b.) Liste de complément

Ce type de représentation graphique est l'une des alternatives à la matrice d'adjacence.

nécessite moins de mémoire et, dans certaines situations, peut même surpasser
matrice d'adjacence. Pour chaque sommet, la liste d'adjacence stocke une liste de sommets, qui sont
adjacent au courant. Voyons un exemple.

1 4
2 4 5
3 5
4 2 5

Graphique Liste d'adjacence

Les avantages. La liste adjacente nous permet de stocker le graphe de manière plus compacte que
matrice d'adjacence, mais la différence diminue à mesure qu'un graphe devient plus dense. Suivant
L'avantage est que la liste d'adjacence permet d'obtenir la liste des sommets adjacents en O(1) temps,
ce qui est un grand avantage pour certains algorithmes.

Inconvénients.

Ajouter/retirer une arête à/depuis la liste d'adjacence n'est pas aussi facile qu'avec l'adjacence.
matrice. Cela nécessite, en moyenne, O(|E| / |V|) temps, ce qui peut donner un résultat cubique.
complexité pour les graphes denses d'ajouter toutes les arêtes.
•Vérifiez si une arête entre deux sommets peut être effectuée en O(|E| / |V|) lorsque
liste de sommets adjacents est désordonnée ou O(log2(|E| / |V|)) lorsqu'il est trié. Ceci
l'opération reste assez bon marché.

103
 La liste adjacente ne nous permet pas de faire une implémentation efficace, si dynamiquement
un changement du nombre de sommets est nécessaire. L'ajout d'un nouveau sommet peut être effectué en O(V),
mais la suppression entraîne une complexité O(E).

Conclusion : La liste d'adjacence est une bonne solution pour les graphes clairsemés et nous permet de changer.
nombre de sommets plus efficacement, que si on utilise une matrice d'adjacence. Mais il y a encore
meilleures solutions pour stocker des graphes entièrement dynamiques.

1.3 Algorithmes associés aux graphes et leurs complexités temporelles

1.3.1 Recherche en profondeur (DFS) pour les graphes non orientés

La recherche en profondeur, ou DFS, est une méthode pour traverser le graphe. Au départ, elle...
permet de visiter uniquement les sommets du graphe, mais il existe des centaines d'algorithmes pour les graphes,
qui sont basés sur la recherche en profondeur. Par conséquent, comprendre les principes de la recherche en profondeur est
assez important d'aller de l'avant dans la théorie des graphes. Le principe de l'algorithme est
assez simple : avancer (en profondeur) tant qu'il y a une telle possibilité, sinon
revenir sur ses pas.

Algorithme
Algorithme : Parcours DFS(G)
//Implémenter un parcours en profondeur d'un graphe
//Input : Graph G=<V,E>
Graph G avec ses sommets marqués par des entiers consécutifs dans l'ordre où ils ont
a été rencontré en premier par le parcours DFS
Marquez chaque sommet dans V avec 0 comme marque d'« inexploré »
Compter 0
Pour chaque sommet v dans V faire
Si v est marqué avec 0
dfs(v)
//fin de la traversée DFS

Routine
dfs (v)
//visite de manière récursive tous les sommets non visités connectés au sommet v et leur attribue le
//nombres dans l'ordre dans lequel ils sont rencontrés via la variable globale count
Comptez Compter+1
Mark v with Count
Pour chaque sommet w dans V adjacent à v faire

104
 Si w est marqué avec 0
Dfs(w)
//fin dfs

Dans le DFS, chaque sommet a trois couleurs possibles représentant son état :

blanc : le sommet n'est pas visité ;

gris : le sommet est en cours ;

DFS a terminé de traiter le sommet.

NB. Pour la plupart des algorithmes, la classification booléenne non visitée / visitée est largement suffisante, mais

nous montrons le cas général ici.

Au départ, tous les sommets sont blancs (non visités). DFS commence dans un sommet arbitraire et s'exécute comme

suit:

1. Marquer les sommets en gris (visités).

2. Pour chaque arête (u, v), où u est blanc, exécutez une recherche en profondeur pour u de manière récursive.
3. Marquez les sommets en noir et revenez à l'élément parent.

Exemple : Parcourez un graphe montré ci-dessous, en utilisant DFS. Commencez à partir d'un sommet avec

numéro 1.

Graphique source.

105
Marquez un sommet1 en gris.

Il y a une arête (1, 4) et le sommet 4 n'est pas visité.

Va là-bas.

Marquez le sommet4 en gris.

106
Il y a une arête (4, 2) et le sommet a2 n'est pas visité.
Va là-bas.

Marquez le sommet2 en gris.

Il y a une arête (2, 5) et un sommet 5 est non visité.

Va là-bas.

107
Marquez le sommet5 en gris.

Il y a une arête (5, 3) et un sommet 3 est non visité.

Va là-bas.

Marquez le sommet 3 en gris.

108
Il n'y a aucun moyen d'aller du sommet3. Marquez-le
en noir et revenir au sommet5.

Il y a une arête (5, 4), mais le sommet 4 est gris.

Il n'y a aucun moyen d'aller du sommet 5. Marquez-le.

comme noir et revenir au sommet2.

109
Il n'y a plus de bords, adjacents à
vertex2. Marquez-le en noir et revenez à la
sommet4.

Il y a une arête (4, 5), mais le sommet 5 est noir.

Il n'y a plus de bords, adjacents au

vertex4. Marquez-le en noir et revenez à la
sommet1

110
 Il n'y a plus de bords, adjacents au
vertex1. Marquez-le en noir. La DFS est terminée.

Comme vous pouvez le voir dans l'exemple, DFS ne parcourt pas toutes les arêtes. Les sommets et
Les arêtes, que la recherche en profondeur a visitées, forment un arbre. Cet arbre contient tous les sommets de

le graphe (s'il est connexe) et est appelé arbre couvrant du graphe. Cet arbre exactement
correspond à des appels récursifs de DFS.

Si un graphe est déconnecté, DFS ne visitera pas tous ses sommets. Pour des détails, voir la recherche
algorithme des composants connexes

Analyse de la complexité

Supposons que le graphe soit connexe. La recherche en profondeur visite chaque sommet du graphe et
vérifie chaque arête de son bord. Par conséquent, la complexité de DFS est O(V + E). Comme c'était
comme mentionné précédemment, si une matrice d'adjacence est utilisée pour une représentation de graphe, alors tout

les arêtes, adjacentes à un sommet ne peuvent pas être trouvées efficacement, ce qui entraîne O(V2) complexité.

Vérifiez vos progrès

1. Écrivez un algorithme pour le parcours DFS et analysez sa complexité.

2. Quelles sont les différentes manières de représenter un graphe ? Expliquez-le avec un exemple.
3. Quels sont les avantages et les inconvénients de la matrice d'adjacence et de la liste d'adjacence

méthode de représentation du graphe.

1.4 SUMMARY:
Le graphe peut être représenté de deux manières, c'est-à-dire par matrice d'adjacence et par méthode de liste d'adjacence.

111
 La matrice d'adjacence est une bonne solution pour les graphes denses et la liste d'adjacence est bonne pour

graphe clairsemé.
La recherche en profondeur (DFS) est un algorithme pour parcourir ou rechercher un arbre, une structure d'arbre,

ou graphique. On commence à la racine (en sélectionnant un nœud comme racine dans le cas du graphique) et
explore aussi loin que possible le long de chaque branche avant de revenir en arrière.

1.15 KEYWORDS
Un graphe : un graphe est une représentation abstraite d'un ensemble d'objets où certaines paires de
les objets sont connectés par des liens. Les objets interconnectés sont représentés par
des abstractions mathématiques appelées sommets, et les liens qui connectent certains paires de
Les sommets sont appelés arêtes.
Un digraphe est un graphe avec des directions sur ses arêtes.

1,16 RÉPONSES POUR VÉRIFIER VOTRE PROGRÈS

1. 1.3.1
2. 1.2.
3. 1.2
1.7 EXERCICES ET RÉPONSES DE FIN D'UNITÉ
15. Appliquer un parcours DFS pour un graphe ayant une matrice d'adjacence

Matrice 1
16. a.) Écrivez le graphique équivalent pour la matrice ci-dessus (c'est-à-dire matrice1).

b.) Représentez la matrice1 sous forme de liste d'adjacence.

[Link] a note on path , weighted graph, cycle, loop.

VOIR

112
 1. 1.3.1
2. 1.2
3. 1.1

1.13 SUGGESTED READINGS

1. Introduction à La conception et l'analyse des algorithmes par Anany Levitin
2. Analyse et conception d'algorithmes avec C/C++ - 3rdédition par le Prof. Nandagopalan
3. Analyse et conception d'algorithmes par Padma Reddy

4. Even, Shimon., "Algorithmes de Graphes", Presse de l'informatique.

5. Data structures, Algorithms and applications in C++ -2ndédition, Par Sartaj Sahni.

113
114