La méthode de la force brute est une approche directe pour résoudre

problème, généralement basé directement sur l'énoncé du problème et les définitions des concepts qu'il utilise.

Un algorithme de force brute pour résoudre un problème de recherche général est appelé recherche séquentielle. Cet algorithme compare simplement les éléments d'une liste donnée à la clé de recherche tour à tour jusqu'à ce qu'un élément avec la valeur de clé spécifiée soit trouvé (recherche réussie) ou que la liste entière soit examinée mais que l'élément requis ne soit pas trouvé (échec de la recherche). Souvent, une simple astuce supplémentaire est utilisée : si vous ajoutez la clé de recherche à la fin de la liste, la recherche réussira définitivement, par conséquent, vous pouvez supprimer la vérification de l'achèvement de la liste à chaque itération de l'algorithme. Ce qui suit est le pseudocode d'une telle version améliorée ; les données d'entrée sont supposées être sous la forme d'un tableau.

Si la liste d'origine est triée, une autre amélioration peut être utilisée : la recherche dans une telle liste peut être arrêtée dès qu'un élément est rencontré qui n'est pas inférieur à la clé de recherche. La recherche séquentielle offre une excellente illustration de l'approche par force brute, avec ses forces (simplicité) et ses faiblesses (faible efficacité) caractéristiques.

Il est bien évident que le temps d'exécution de cet algorithme peut varier largement pour une même liste de taille n. lorsque la liste ne contient pas l'élément souhaité ou lorsque l'élément est situé en dernier dans la liste, l'algorithme effectuera le plus grand nombre d'opérations de comparaison de clé avec tous les n éléments de la liste : C(n) = n.

1.2. Algorithme de Rabin.

L'algorithme de Rabin est une modification de l'algorithme linéaire, il est basé sur une idée très simple :

« Imaginons que dans le mot A, dont la longueur est m, nous recherchions un motif X de longueur n. Découpons une "fenêtre" de taille n et déplaçons-la le long du mot d'entrée. Nous voulons savoir si le mot dans la "boîte" correspond au modèle donné. Comparer des lettres pendant longtemps. Au lieu de cela, nous fixons une fonction numérique sur des mots de longueur n, puis le problème se réduira à comparer des nombres, ce qui est sans doute plus rapide. Si les valeurs de cette fonction sur le mot dans la "fenêtre" et sur l'échantillon sont différentes, il n'y a pas de correspondance. Ce n'est que si les valeurs sont identiques qu'il est nécessaire de vérifier successivement une correspondance lettre par lettre.

Cet algorithme effectue un passage linéaire à travers la ligne (n pas) et un passage linéaire à travers tout le texte (m pas), donc le temps d'exécution total est O(n+m). Dans le même temps, nous ne prenons pas en compte la complexité temporelle du calcul de la fonction de hachage, car l'essence de l'algorithme est que cette fonction est si facilement calculée que son fonctionnement n'affecte pas le fonctionnement global de l'algorithme.

L'algorithme de Rabin et l'algorithme de recherche séquentielle sont les algorithmes les moins coûteux en main-d'œuvre, ils conviennent donc à la résolution d'une certaine classe de problèmes. Cependant, ces algorithmes ne sont pas les plus optimaux.

1.3. Algorithme de Knuth-Morris-Pratt (kmp).

La méthode KMP utilise le prétraitement de la chaîne requise, à savoir : sur sa base, une fonction de préfixe est créée. Dans ce cas, l'idée suivante est utilisée : si le préfixe (alias suffixe) d'une chaîne de longueur i est plus long qu'un caractère, alors c'est aussi le préfixe d'une sous-chaîne de longueur i-1. Ainsi, nous vérifions le préfixe de la sous-chaîne précédente, s'il ne correspond pas, puis le préfixe de son préfixe, et ainsi de suite. Ce faisant, nous trouvons le plus grand préfixe souhaité. La question suivante à laquelle il faut répondre est : pourquoi le temps d'exécution de la procédure est-il linéaire, car il a une boucle imbriquée ? Eh bien, premièrement, l'affectation de la fonction de préfixe se produit exactement m fois, le reste du temps, la variable k change. Par conséquent, le temps d'exécution total du programme est O(n+m), c'est-à-dire un temps linéaire.

Et fonction suivante: function show(pos, path, w, h) ( var canvas = document.getElementById("canID"); // récupère l'objet canvas var ctx = canvas.getContext("2d"); // il a une propriété de contexte dessin var x0 = 10, y0 = 10 ; // la position du coin supérieur gauche de la carte canvas.width = w+2*x0 ; canvas.height = h+2*y0 ; // redimensionne le canevas (légèrement plus grand que w x h) ctx .beginPath(); // commence à dessiner une polyligne ctx.moveTo(x0+pos.x,y0+pos.y)// passe à la 0ème ville pour(var i=1; i Un exemple de le résultat de l'appel de la fonction est affiché à droite. La signification des commandes de dessin doit être claire à partir de leur nom et des commentaires dans le code.Tout d'abord, une polyligne fermée (le chemin d'un voyageur de commerce) est dessinée.Ensuite, les cercles des villes et en haut d'entre eux les numéros de ville.Travailler avec un fossé en JavaScript est quelque peu fastidieux et à l'avenir, nous utiliserons la classe dessiner, ce qui simplifie ce travail et vous permet en même temps d'obtenir des images au format svg.

Buste dans la minuterie

La mise en œuvre de l'algorithme de recherche pour trouver le chemin le plus court dans le temporisateur n'est pas difficile. Pour stocker le meilleur chemin dans un tableau minWay, écrire une fonction pour copier les valeurs des éléments du tableau src dans un tableau dés:

Function copy(des, src) ( if(des.length !== src.length) des = new Array(src.length); for(var i=0; i

J'ai un problème mathématique que je résous par essais et erreurs (je pense que cela s'appelle la force brute) et le programme fonctionne bien lorsqu'il y a plusieurs paramètres, mais à mesure que de plus en plus de variables/données sont ajoutées, l'exécution prend de plus en plus de temps.

Mon problème est que même si le prototype fonctionne, il est utile pour des milliers de variables et de grands ensembles de données ; donc, je me demande si les algorithmes de force brute peuvent être mis à l'échelle. Comment puis-je aborder la mise à l'échelle ?

3 réponses

En règle générale, vous pouvez quantifier la capacité d'un algorithme à évoluer en utilisant une notation de sortie large pour analyser son taux de croissance. Lorsque vous dites que votre algorithme fonctionne sous "force brute", il n'est pas clair dans quelle mesure il évoluera. Si votre solution de "force brute" fonctionne en listant tous les sous-ensembles ou combinaisons possibles de l'ensemble de données, alors elle ne sera presque certainement pas mise à l'échelle (elle aura une complexité asymptotique de O(2n) ou O(n!), respectivement). Si votre solution de force brute fonctionne en trouvant toutes les paires d'éléments et en les testant, elle peut assez bien évoluer (O(n 2)). Cependant, sans Informations Complémentaires comment votre algorithme fonctionne est difficile à dire.

Par définition, les algorithmes de force brute sont stupides. Vous serez beaucoup mieux avec un algorithme plus intelligent (si vous en avez un). Un meilleur algorithme réduira le travail à faire, espérons-le dans la mesure où vous pourrez le faire sans nécessiter de "mise à l'échelle" sur plusieurs machines.

Quel que soit l'algorithme, il arrive un moment où la quantité de données ou la puissance de traitement requise est si importante que vous devez utiliser quelque chose comme Hadoop. Mais généralement, nous parlons vraiment de données volumineuses ici. Vous pouvez déjà faire beaucoup avec un seul PC de nos jours.

L'algorithme de résolution de ce problème est proche du processus que nous étudions pour la division mathématique manuelle, ainsi que pour la conversion d'une base décimale à une autre base, comme octale ou hexadécimale, sauf qu'une seule solution canonique est considérée dans les deux exemples.

Pour vous assurer que la récursivité se termine, il est important d'ordonner le tableau de données. Pour être efficace et limiter le nombre de récursions, il est également important de commencer avec des valeurs de données plus élevées.

Concrètement, voici l'implémentation récursive de Java pour ce problème - avec une copie du vecteur de résultat coeff pour chaque récursivité, comme prévu en théorie.

Importer java.util.Arrays ; public class Solver ( public static void main(String args) ( int target_sum = 100; // pré-requis : valeurs triées !! int data = new int ( 5, 10, 20, 25, 40, 50 ); / / vecteur de résultat, init à 0 int coeff = new int; Arrays.fill(coeff, 0); partialSum(data.length - 1, target_sum, coeff, data); ) private static void printResult(int coeff, int data) ( for ( int i = coeff.length - 1; i >= 0; i--) ( if (coeff[i] > 0) ( System.out.print(data[i] + " * " + coeff[i] + " "); ) ) System.out.println(); ) private static void partialSum(int k, int sum, int coeff, int data) ( int x_k = data[k]; for (int c = sum / x_k ; c >= 0; c--) ( coeff[k] = c; if (c * x_k == sum) ( printResult(coeff, data); continue; ) else if (k > 0) ( // résultat contextuel in parameters , local to method scope int newcoeff = Arrays.copyOf(coeff, coeff.length); partialSum(k - 1, sum - c * x_k, newcoeff, data); // for loop on "c" continue avec le précédent teneur en coeff ) ) ) )

Mais maintenant, ce code est dans un cas particulier : dernier test la valeur de chaque coefficient est 0, donc aucune copie n'est nécessaire.

Comme estimation de la complexité, nous pouvons utiliser la profondeur maximale des appels récursifs comme data.length * min(( data )) . Bien sûr, il n'évoluera pas bien et la mémoire de trace de la pile (option -Xss JVM) sera le facteur limitant. Le code peut échouer avec une erreur pour un grand ensemble de données.

Pour éviter ces défauts, le processus "terminer" est utile. Elle consiste à remplacer la pile d'appel de méthode par une pile de programme pour stocker le contexte d'exécution pour un traitement ultérieur. Voici le code pour cela :

Importer java.util.Arrays ; import java.util.ArrayDeque ; importer java.util.Queue ; public class NonRecursive ( // pré-requis : valeurs triées !! private static final int data = new int ( 5, 10, 20, 25, 40, 50 ); // Contexte pour stocker un calcul intermédiaire ou une classe statique de solution Context ( int k; int sum; int coeff; Context(int k, int sum, int coeff) ( this.k = k; this.sum = sum; this.coeff = coeff; ) ) private static void printResult(int coeff ) ( for (int i = coeff.length - 1; i >= 0; i--) ( if (coeff[i] > 0) ( System.out.print(data[i] + " * " + coeff[ i] + " "); ) ) System.out.println(); ) public static void main(String args) ( int target_sum = 100; // vecteur de résultat, init à 0 int coeff = new int; Arrays.fill( coeff, 0); // file d'attente avec les contextes à traiter Queue contextes = new ArrayDeque (); // contexte initial contexts.add(new Context(data.length - 1, target_sum, coeff)); while(!contexts.isEmpty()) ( Contexte actuel = contexts.poll(); int x_k = data; for (int c = current.sum / x_k; c >= 0; c--) ( current.coeff = c ;int newcoeff = Arrays.copyOf(current.coeff, current.coeff.length); if (c * x_k == current.sum) ( printResult(newcoeff); continue; ) else if (current.k > 0) ( contexts .add(nouveau contexte(current.k - 1, current.sum - c * x_k, newcoeff)); ) ) ) ) )

De mon point de vue, il est difficile d'être plus efficace en une seule exécution d'un thread - le mécanisme de pile nécessite désormais des copies du tableau coeff.

La recherche d'une sous-chaîne dans une chaîne s'effectue selon un motif donné, c'est-à-dire une séquence de caractères dont la longueur ne dépasse pas la longueur de la chaîne d'origine. La tâche de la recherche est de déterminer si une chaîne contient un modèle donné et d'indiquer l'emplacement (index) dans la chaîne si une correspondance est trouvée.

L'algorithme de force brute est le plus simple et le plus lent et consiste à vérifier toutes les positions du texte pour voir si elles correspondent au début du motif. Si le début du motif correspond, alors la lettre suivante dans le motif et dans le texte est comparée, et ainsi de suite, la réponse la plus simple et la plus lente est donnée, qu'il y ait ou non un tel élément sans spécifier l'index est déjà trié par correspondance non complète du motif ou différence dans la lettre suivante.

int BFSearch(car*s, car*p)

for (int i = 1; strlen(s) - strlen(p); i++)

pour (int j = 1; strlen(p); j++)

si (p[j] != s)

si (j = strlen(p))

La fonction BFSearch recherche la sous-chaîne p dans la chaîne s et renvoie l'index du premier caractère de la sous-chaîne, ou 0 si la sous-chaîne est introuvable. Bien qu'en général cette méthode, comme la plupart des méthodes de force brute, soit inefficace, dans certaines situations, elle est tout à fait acceptable.

Le plus rapide parmi les algorithmes usage général, conçu pour rechercher une sous-chaîne dans une chaîne, est l'algorithme Boyer-Moore, développé par deux scientifiques - Boyer (Robert S. Boyer) et Moore (J. Strother Moore), dont l'essence est la suivante.

Algorithme de Boyer-Moore

La version la plus simple de l'algorithme de Boyer-Moore comprend les étapes suivantes. Lors de la première étape, une table des déplacements pour l'échantillon souhaité est construite. Le processus de construction de la table sera décrit ci-dessous. Ensuite, le début de la chaîne et le motif sont combinés et le test commence à partir du dernier caractère du motif. Si le dernier caractère du motif et le caractère de la chaîne qui lui correspond dans la superposition ne correspondent pas, le motif est décalé par rapport à la chaîne de la valeur obtenue à partir de la table des décalages, et la comparaison est effectuée à nouveau, à partir du dernier caractère du motif. Si les caractères correspondent, l'avant-dernier caractère du modèle est comparé, et ainsi de suite. Si tous les caractères de l'échantillon correspondent aux caractères superposés de la chaîne, la sous-chaîne a été trouvée et la recherche est terminée. Si un caractère (pas le dernier) du motif ne correspond pas au caractère correspondant de la chaîne, nous décalons le motif d'un caractère vers la droite et recommençons à partir du dernier caractère. L'algorithme entier est exécuté jusqu'à ce qu'une occurrence du motif souhaité soit trouvée ou que la fin de la chaîne soit atteinte.

La valeur de décalage en cas de discordance du dernier caractère est calculée selon la règle : le décalage du motif doit être minimal, afin de ne pas rater l'occurrence du motif dans la chaîne. Si le caractère de chaîne donné apparaît dans le modèle, le modèle est décalé de sorte que le caractère de chaîne corresponde à l'occurrence la plus à droite de ce caractère dans le modèle. Si le motif ne contient pas du tout ce caractère, alors le motif est décalé d'une quantité égale à sa longueur, de sorte que le premier caractère du motif se superpose au caractère suivant de la chaîne qui a été testée.

La valeur de décalage pour chaque caractère de modèle dépend uniquement de l'ordre des caractères dans le modèle, il est donc pratique de calculer les décalages à l'avance et de les stocker sous forme de tableau unidimensionnel, où chaque caractère de l'alphabet correspond à un décalage relatif jusqu'au dernier caractère du motif. Expliquons tout ce qui précède exemple simple. Soit un ensemble de cinq caractères : a, b, c, d, e et vous devez trouver une occurrence du motif "abbad" dans la chaîne "abeccacbadbabbad". Les schémas suivants illustrent toutes les étapes de l'exécution de l'algorithme :

Table de décalage pour le motif "abbad".

Lancement de la recherche. Le dernier caractère du modèle ne correspond pas au caractère de chaîne superposé. Décaler l'échantillon vers la droite de 5 positions :

Trois caractères du motif correspondaient, mais pas le quatrième. Décalez le motif vers la droite d'une position :

Le dernier caractère ne correspond pas non plus au caractère de la chaîne. Conformément au tableau des déplacements, on décale l'échantillon de 2 positions :

Encore une fois, on décale l'échantillon de 2 positions :

Maintenant, conformément au tableau, nous décalons l'échantillon d'une position et nous obtenons l'occurrence souhaitée de l'échantillon :

Nous implémentons l'algorithme spécifié. Tout d'abord, le type de données "table de décalage" doit être défini. Pour une table de codes de 256 caractères, la définition de la structure ressemblerait à ceci :

BMTable MakeBMTable(char *p)

pour (i = 0; je<= 255; i++) bmt->bmtarr[i] = strlen(p);

pour (i = strlen(p); je<= 1; i--)

si (bmt->bmtarr] == strlen(p))

bmt->bmtarr] = strlen(p)-i ;

Écrivons maintenant une fonction qui effectue la recherche.

int BMSearch(int startpos, car *s, car *p)

pos = startpos + lp - 1 ;

tandis que (pos< strlen(s))

si (p != s) pos = pos + bmt->bmtarr] ;

pour (i = lp - 1; je<= 1; i--)

si (p[i] != s)

retour(pos - lp + 1);

La fonction BMSearch renvoie la position du premier caractère de la première occurrence du motif p dans la chaîne s. Si la séquence p dans s n'est pas trouvée, la fonction renvoie 0. Le paramètre startpos vous permet de spécifier la position dans la chaîne s à partir de laquelle commencer la recherche. Cela peut être utile si vous voulez trouver toutes les occurrences de p dans s. Pour rechercher depuis le tout début de la chaîne, définissez startpos sur 1. Si le résultat de la recherche est différent de zéro, alors pour trouver la prochaine occurrence de p dans s, définissez startpos sur "le résultat précédent plus la longueur du motif".

Recherche binaire (binaire)

La recherche binaire est utilisée lorsque le tableau recherché est déjà trié.

Les variables lb et ub contiennent, respectivement, les limites gauche et droite du segment de tableau où se trouve l'élément souhaité. La recherche commence toujours par l'étude de l'élément médian du segment. Si la valeur souhaitée est inférieure à l'élément du milieu, vous devez passer à la recherche dans la moitié supérieure du segment, où tous les éléments sont inférieurs à celui qui vient d'être coché. En d'autres termes, la valeur de ub devient (m - 1) et la moitié du tableau d'origine est vérifiée à l'itération suivante. Ainsi, à la suite de chaque vérification, la zone de recherche est réduite de moitié. Par exemple, s'il y a 100 numéros dans le tableau, après la première itération, la zone de recherche est réduite à 50 numéros, après le deuxième à 25, après le troisième à 13, après le quatrième à 7, etc. Si la longueur du tableau est n, alors environ log 2 n comparaisons suffisent pour rechercher des éléments dans le tableau.

Méthodes de développement d'algorithmes n Méthode de la force brute ("frontale") n Méthode de décomposition n Méthode de réduction de la taille du problème n Méthode de transformation n Programmation dynamique n Méthodes gloutonnes n Méthodes de réduction de la recherche n … © Pavlovskaya T. A. (SPb NRU ITMO) 1

Approche par force brute n Une approche directe de la résolution d'un problème, généralement basée directement sur l'énoncé du problème et les définitions des concepts utilisés par celui-ci facile à utiliser n Produit rarement des algorithmes beaux et efficaces n Le coût de développement d'un algorithme plus efficace peut être inacceptable si seulement quelques cas de problème doivent être résolus n Peut être utile pour résoudre de petits cas de problème. n Peut servir de mesure pour déterminer l'efficacité d'autres algorithmes © Pavlovskaya T. A. (SPb NRU ITMO) 3

n Exemple : tri par sélection et tri par bulles 28 -5 ©Pavlovskaya T. A. (St. Petersburg NRU ITMO) 16 0 29 3 -4 56 4

L'énumération exhaustive est une approche par force brute des problèmes combinatoires. Il suppose : n la génération de tous les éléments possibles à partir de la zone de définition du problème n la sélection de ceux qui satisfont aux contraintes imposées par la condition du problème n la recherche de l'élément souhaité (par exemple, l'optimisation de la valeur de la fonction objectif du problème). Exemples : Le problème du voyageur de commerce : trouver le chemin le plus court à travers Considérer tous les sous-ensembles ensemble donné sur n objets donnés à N villes, pour que chaque ville soit visitée, ne calculez le poids total de chacune d'entre elles pour déterminer l'admissibilité, qu'une seule fois et la destination finale est celle d'origine. choisissez parmi le sous-ensemble autorisé avec le poids maximum. n Obtenir tous les itinéraires possibles, générant tous les problèmes de sac à dos : étant donné N éléments de poids donné et coûtant un sac à dos pouvant supporter le poids W. Charger un sac à dos de permutations de n - 1 villes intermédiaires, en calculant avec le coût maximum. la longueur des chemins correspondants et trouver le plus court d'entre eux. Ce sont des problèmes NP-difficiles (aucun algorithme n'est connu pour les résoudre en temps polynomial). n © Pavlovskaya T. A. (SPb NRU ITMO) 5

Méthode de décomposition Aussi appelée diviser pour mieux régner : n Une instance de tâche est décomposée en plusieurs instances plus petites de la même tâche, idéalement de même taille. n Les petites instances du problème sont résolues (généralement de manière récursive, bien que parfois un autre algorithme soit utilisé pour les petites instances). n Si nécessaire, la solution au problème d'origine est trouvée en combinant des solutions d'instances plus petites. La méthode de décomposition est idéale pour le calcul parallèle. © Pavlovskaya T. A. (SPb NRU ITMO) 7

Équation de décomposition récursive n Dans le cas général, une instance d'un problème de taille n peut être divisée en plusieurs instances de taille n/b, et dont on est amené à résoudre. n Équation de décomposition récursive généralisée : (1) n Pour simplifier, on suppose que la taille de n est égale à la puissance de b. n L'ordre de croissance dépend de a, b et f. © Pavlovskaya T. A. (SPb NRU ITMO) 8

Le théorème de décomposition principal (1) n On peut spécifier la classe d'efficacité de l'algorithme sans résoudre l'équation récursive elle-même. n Cette approche permet d'établir l'ordre de croissance de la solution sans déterminer les inconnues. © Pavlovskaya T. A. (SPb NRU ITMO) 9

Tri par fusion Trie le tableau donné en le divisant en deux moitiés, en triant chaque moitié de manière récursive et en fusionnant les deux moitiés triées en un seul tableau trié : Tri par fusion (A) si n>1 Première moitié A -> dans le tableau B Seconde moitié A -> dans tableau C Mergesort(B) Mergesort(C) Merge(B, C, A) // fusion ©Pavlovskaya T. A. (St. Petersburg NRU ITMO) 10

Src="http://present5.com/presentation/54441564_438337950/image-11.jpg" alt="Mergesort (A) si n>1 Première moitié de A -> vers tableau B Deuxième moitié de A"> Mergesort (A) if n>1 Первая половина А -> в массив В Вторая половина А > в массив С Mergesort(B) Mergesort(C) Меrgе(В, С, А) ©Павловская Т. А. (СПб НИУ ИТМО) 11!}

Fusionner des tableaux n Deux indices de tableau après l'initialisation pointent sur les premiers éléments des tableaux à fusionner. n Les éléments sont comparés et le plus petit est ajouté au nouveau tableau. n L'indice du plus petit élément est incrémenté (il pointe sur l'élément suivant immédiatement celui qui vient d'être copié). Cette opération est répétée jusqu'à épuisement d'un des tableaux à fusionner. Les éléments restants du deuxième tableau sont ajoutés à la fin du nouveau tableau. © Pavlovskaya T. A. (SPb NRU ITMO) 12

Analyse de tri par fusion n Soit la longueur du fichier une puissance de 2. n Nombre de comparaisons clés : C(n) = 2*C(n/2) + Cmerge (n) n > 1, C(1)=0 n Cmerge (n) = n-1 pire cas (nombre de comparaisons clés de fusion) n Pire cas Cw : d=1 a=2 b=2 Cw(n) = 2*Cw (n/2) +n-1 Cw (n ) (n log n) – selon les principaux Théorème ©Pavlovskaya T. A. (SPb NRU ITMO) (1) 13

n Le nombre de comparaisons clés effectuées par tri par fusion est au pire très proche du nombre minimal théorique de comparaisons pour tout algorithme de tri par comparaison. n Le principal inconvénient du tri par fusion est le besoin de mémoire supplémentaire, dont la quantité est linéairement proportionnelle à la taille des données d'entrée. © Pavlovskaya T. A. (SPb NRU ITMO) 14

Quicksort Contrairement au mergesort, qui sépare les éléments d'un tableau en fonction de leur position dans le tableau, le tri rapide sépare les éléments d'un tableau en fonction de leurs valeurs. 28 56 © Pavlovskaya T. A. (ITMO NRU de Saint-Pétersbourg) 1 0 29 3 -4 16 15

Description de l'algorithme n Sélectionner un élément pivot n Effectuer une permutation d'éléments pour obtenir une partition lorsque tous les éléments jusqu'à une certaine position s ne dépassent pas l'élément A [s], et les éléments après la position s ne sont pas inférieurs à celui-ci. n Évidemment, après séparation, A [s] est en position finale, et nous pouvons trier les deux sous-tableaux d'éléments avant et après A [s] indépendamment (en utilisant la même méthode ou une méthode différente) © Pavlovskaya T. A. (SPb NRU ITMO) 16

La procédure de permutation des éléments n Méthode efficace, basé sur deux passages de sous-réseau - de gauche à droite et de droite à gauche. A chaque passage, les éléments sont comparés au pivot. n Passe de gauche à droite (i) saute des éléments inférieurs au pivot et s'arrête au premier élément non inférieur au pivot. n Passe de droite à gauche (j) saute les éléments supérieurs à pivot et s'arrête au premier élément non supérieur à pivot. n Si les indices de scan ne se croisent pas, nous échangeons les éléments trouvés et continuons les passes. n Si les indices se croisent, on échange l'élément pivot avec Aj ©Pavlovskaya T. A. (SPb NRU ITMO) 17

Efficacité du tri rapide n Meilleur cas : toutes les partitions sont au milieu des sous-tableaux correspondants n Pire cas, toutes les partitions sont telles qu'un des sous-tableaux est vide, et la taille du second est inférieure de 1 à la taille du tableau à partitionné (dépendance quadratique). n Dans le cas moyen, nous supposons que le partitionnement peut être effectué dans chaque position avec la même probabilité : Cavg 2 n ln n 1, 38 n log 2 n © Pavlovskaya T. A. (SPb NRU ITMO) 18

Améliorations de l'algorithme n amélioration des méthodes de sélection de pivot n passage à un tri plus simple pour les petits sous-tableaux n suppression de la récursivité Ensemble, ces améliorations peuvent réduire le temps d'exécution de l'algorithme de 20 à 25 % (R. Sedgwick) © Pavlovskaya T. A. (SPb NRU ITMO) 19

Traversée d'arbre binaire Voici un autre exemple d'utilisation de la méthode de décomposition n La traversée avant visite d'abord la racine de l'arbre, puis les sous-arbres gauche et droit. n Dans un parcours symétrique, la racine est visitée après le sous-arbre de gauche mais avant de visiter le droit. n Lors du contournement ordre inverse la racine est visitée après les sous-arbres gauche et droit. © Pavlovskaya T. A. (SPb NRU ITMO) 20

Procédure de parcours d'arbre print_tree(tree); begin print_tree(left_subtree) visite racine print_tree(right_subtree) end ; 1 6 8 10 20 ©Pavlovskaya T. A. (SPb. GU ITMO) 21 25 30 21

Méthode de réduction de la taille du problème Basée sur l'utilisation de la relation entre la solution d'une instance donnée du problème et la solution d'une instance plus petite du même problème. Une fois qu'une telle relation est établie, elle peut être utilisée de haut en bas (récursivement) ou de bas en haut (pas de récursivité). (exemple - élever un nombre à une puissance) Il existe trois variantes principales de la méthode de réduction de taille : n diminution d'une quantité constante (généralement de 1) ; n réduction d'un facteur constant (généralement 2 fois); n réduction de taille variable. © Pavlovskaya T. A. (SPb NRU ITMO) 23

Tri par insertion Supposons que le problème du tri d'un tableau de dimensions n-1 ait été résolu. Il reste alors à insérer An au bon endroit : n Balayage du tableau de gauche à droite n Balayage du tableau de droite à gauche n Utilisation d'une recherche binaire du point d'insertion n Bien que le tri par insertion soit basé sur une approche récursive, il sera plus efficace de le mettre en œuvre de bas en haut (itératif). © Pavlovskaya T. A. (SPb NRU ITMO) 24

Implémentation de pseudocode pour i = 1 à n - 1 faire v = 0 et A[j] > v faire A

Efficacité du tri par insertion n Pire cas : effectue le même nombre de comparaisons que le tri par sélection n Meilleur cas (pour le tableau initialement trié) : la comparaison n'est effectuée qu'une seule fois à chaque passage de la boucle externe n Cas moyen (tableau aléatoire) : effectué ~2 fois moins de comparaisons que dans le cas d'un tableau descendant. Que. , le cas moyen est 2 fois meilleur que le pire des cas. Associé à d'excellentes performances pour les tableaux presque triés, cela distingue le tri par insertion des autres algorithmes élémentaires (sélection et bulle) n Modification de la méthode - insertion de plusieurs éléments en même temps, qui sont triés avant insertion. n Une extension du tri par insertion, Shellsort, fournit un algorithme encore meilleur pour trier des fichiers assez volumineux. © Pavlovskaya T. A. (SPb NRU ITMO) 26

Génération d'objets combinatoires n Les types d'objets combinatoires les plus importants sont les permutations, les combinaisons et les sous-ensembles d'un ensemble donné. n Habituellement, ils surviennent dans des tâches qui nécessitent une diverses possibilités choix. n S'y ajoutent les notions de placement et de partitionnement. © Pavlovskaya T. A. (SPb NRU ITMO) 28

Génération de permutations Nombre de permutations n Soit un ensemble de n éléments (set) donné. n N'importe quel élément peut prendre la première place dans la permutation, c'est-à-dire qu'il y a n manières de choisir le premier élément. Il reste (n-1) éléments pour choisir le deuxième élément de la permutation (il y a (n-1) façons de choisir le deuxième élément). n Il reste (n-2) éléments pour choisir le troisième élément de la permutation, etc. n Au total, un ensemble ordonné de n éléments peut être obtenu : de la manière suivante

Application de la méthode de réduction de taille au problème d'obtention de toutes les permutations de n Pour simplifier, on suppose que l'ensemble des éléments à permuter est l'ensemble des entiers de 1 à n. n La tâche du plus petit est de générer tout (n - 1) ! permutations. n En supposant qu'il a été résolu, nous pouvons obtenir une solution au plus grand problème en insérant n dans chacune des n positions possibles parmi les éléments de chacune des permutations de n - 1 éléments. n Toutes les permutations ainsi obtenues seront différentes, et leur nombre total : n(n- 1) ! =n ! n Vous pouvez insérer n dans les permutations précédemment générées de gauche à droite ou de droite à gauche. Il est avantageux de commencer de droite à gauche et de changer de direction à chaque passage à une nouvelle permutation de l'ensemble (1, . . . , n - 1). © Pavlovskaya T. A. (SPb NRU ITMO) 30

Exemple (génération ascendante de permutations) n 12 21 n 123 132 312 321 231 213 © Pavlovskaya T. A. (St. Petersburg NRU ITMO) 31

Algorithme de Johnson-Trotter La notion d'élément mobile est introduite. Une flèche est associée à chaque élément, un élément est considéré comme mobile si la flèche pointe vers un élément voisin plus petit. n Initialiser la première permutation avec la valeur 1 2. . . n (toutes les flèches vers la gauche) n tant qu'il existe un numéro de mobile k do n Trouver le plus grand numéro de mobile k Échanger k et le numéro voisin pointé par la flèche k n ITMO) 32

Ordre lexicographique n Soit la première permutation (par exemple, 1234). n Pour trouver chacune des suivantes : 1. Parcourez la permutation en cours de droite à gauche à la recherche de la première paire éléments voisins tel qu'un[i]

Un exemple pour la compréhension de l'algorithme 4321 © Pavlovskaya T. A. (SPb NRU ITMO) 34

Le nombre de toutes les permutations de n éléments Р(n) = n! © Pavlovskaya T. A. (ITMO NRU de Saint-Pétersbourg) 35

Sous-ensembles n Un ensemble A est un sous-ensemble d'un ensemble B si tout élément appartenant à A appartient aussi à B : A B ou A B n Tout ensemble est son propre sous-ensemble. L'ensemble vide est un sous-ensemble de n'importe quel ensemble. n L'ensemble de tous les sous-ensembles est noté 2 A (il est aussi appelé ensemble puissance, ensemble puissance, ensemble puissance, booléen, ensemble exponentiel). n Le nombre de sous-ensembles d'un ensemble fini composé de n éléments est 2 n (voir la preuve dans Wikipedia) © Pavlovskaya T. A. (SPb NRU ITMO) 36

Génération de tous les sous-ensembles n Appliquons la méthode de réduction de la taille du problème de 1. n Tous les sous-ensembles A = (a 1, . . . , an) peuvent être divisés en deux groupes - ceux qui contiennent l'élément an et ceux Qui ne. n Le premier groupe est l'ensemble des sous-ensembles (a 1, . . . , an-1) ; tous les éléments du deuxième groupe peuvent être obtenus en ajoutant l'élément an aux sous-ensembles du premier groupe. (a 1) (a 2) (a 1, a 2) (a 3) (a 1, a 3) (a 2, a 3) (a 1, a 2, a 3) lignes : 000 001 010 011 100 101 110 111 n Autres ordres : dense ; Code Gray : n 000 001 010 111 100 © Pavlovskaya T. A. (St. Petersburg NRU ITMO) 37

Génération de codes Gray n Un code Gray pour n bits peut être construit récursivement à partir d'un code pour n-1 bits en : n écrivant les codes dans l'ordre inverse n concaténant la liste d'origine et la liste inversée n ajoutant 0 au début de chaque code dans la liste d'origine et 1 au début des codes de la liste inversée. Exemple : n Codes pour n = 2 bits : 00, 01, 10 n Liste de codes inversés : 10, 11, 00 n Liste combinée : 00, 01, 10, 11, 00 n Zéros ajoutés à la liste initiale : 000, 001, 010 , 11, 00 n Unités ajoutées à la liste inversée : 000, 001, 010, 111, 100 © Pavlovskaya T. A. (St. Petersburg NRU ITMO) 38

Sous-ensembles de k éléments n Le nombre de sous-ensembles de k éléments n (0 k n) est appelé le nombre de combinaisons (coefficient binomial) : n La solution directe est inefficace en raison de la croissance rapide de la factorielle. n En règle générale, la génération des sous-ensembles de k éléments s'effectue dans l'ordre lexicographique (pour deux sous-ensembles quelconques, le premier à être généré est celui dont les indices d'éléments peuvent former un nombre à k chiffres plus petit dans le nombre n-aire système). n Méthode : n le premier élément d'un sous-ensemble de cardinalité k peut être n'importe lequel des éléments, en commençant par le premier et en terminant par le (n-k+1)-ème. n Une fois l'indice du premier élément du sous-ensemble fixé, il reste à sélectionner k-1 éléments parmi les éléments ayant des indices supérieurs au premier. n De plus, de la même manière, réduire le problème à une dimension plus petite jusqu'à le plus bas niveau la récursivité ne sélectionnera pas le dernier élément, après quoi le sous-ensemble sélectionné pourra être imprimé ou traité. © Pavlovskaya T. A. (ITMO NRU de Saint-Pétersbourg) 39

Exemple : combinaisons de 6 à 3 #include const int N = 6, K = 3 ; int a[K] ; void rec(int i) ( if (i == K) ( for (int j = 0; j 0 ? a + 1 : 1); a[i]

Propriétés des combinaisons n chaque sous-ensemble de n éléments d'un ensemble d'éléments donné correspond à un et un seul sous-ensemble de n-k éléments du même ensemble : n © Pavlovskaya T. A. (SPb NRU ITMO) 41

Placements n Un placement de n éléments par m est une séquence composée de m éléments différents d'un ensemble de n éléments (combinaisons constituées de n éléments donnés par m éléments et qui diffèrent soit par les éléments eux-mêmes, soit par l'ordre des éléments ) La différence dans les définitions des combinaisons et des placements : n Une combinaison est un sous-ensemble contenant m éléments sur n (l'ordre des éléments n'a pas d'importance). n Le placement est une séquence contenant m éléments sur n (l'ordre des éléments est important). Lors de la formation d'une séquence, l'ordre des éléments est important, et lors de la formation d'un sous-ensemble, l'ordre n'est pas important. © Pavlovskaya T. A. (SPb. GU ITMO) 44

Nombre de placements n Nombre de placements de n à m : Exemple 1 : Combien y a-t-il de nombres à deux chiffres dans lesquels le chiffre des dizaines et le chiffre des unités sont différents et impairs ? Ensemble principal : (1, 3, 5, 7, 9) - chiffres impairs, n=5 n Connexion - nombre à deux chiffres m=2, l'ordre est important, il s'agit donc d'un placement de "de cinq par deux". n Les permutations peuvent être considérées comme un cas particulier de placement avec m=n Exemple 2 : De combien de manières un drapeau peut-il être composé de trois bandes horizontales de couleurs différentes s'il y a un matériau de cinq couleurs ? © Pavlovskaya T. A. (SPb NRU ITMO) 45

Allocations avec répétitions n Allocations avec répétitions de n éléments de l'ensemble E=(a 1, a 2, . . . , an) par k - toute suite finie constituée de k éléments de l'ensemble donné E. n au moins en un endroit ils ont des éléments différents de l'ensemble E. n Le nombre de placements différents avec des répétitions de n à k est égal à nk. © Pavlovskaya T.A. (SPb NRU ITMO) 46

Partition d'ensembles n La partition d'un ensemble est sa représentation sous forme d'union montant arbitraire sous-ensembles disjoints deux à deux. n Nombre de partitions non ordonnées d'un ensemble de n éléments en k parties - Nombre de Stirling de 2ème espèce : n Nombre de partitions ordonnées d'un ensemble de n éléments en m parties de taille fixe - coefficient multinomial : n Le nombre de toutes les parties non ordonnées partitions d'un ensemble de n éléments est donnée par le numéro de Bell : © Pavlovskaya T. A. (SPb NRU ITMO) 47

Méthode de réduction par un facteur constant n Exemple : recherche binaire n De tels algorithmes sont logarithmiques et, étant très rapides, sont assez rares. Méthode de réduction par un facteur variable n Exemples : recherche et insertion dans un arbre de recherche binaire, recherche par interpolation : © Pavlovskaya T. A. (SPb. GU ITMO) 48

Analyse d'efficacité n La recherche par interpolation nécessite, en moyenne, moins de log 2 n+1 comparaisons clés lors de la recherche d'une liste de n valeurs aléatoires. n Cette fonction croît si lentement que pour toutes les valeurs pratiques réelles de n, elle peut être considérée comme une constante. n Cependant, dans le pire des cas, la recherche par interpolation dégénère en une recherche linéaire, considérée comme la pire possible. n La recherche par interpolation est mieux utilisée pour les fichiers volumineux et pour les applications où la comparaison ou l'accès aux données est une opération coûteuse. © Pavlovskaya T. A. (SPb NRU ITMO) 49

Méthode de transformation n Elle consiste dans le fait que l'instance de tâche est transformée en une autre, qui pour une raison ou une autre est plus facile à résoudre. n Il existe trois variantes principales de cette méthode : © Pavlovskaya T. A. (SPb NRU ITMO) 50

Exemple 1 : Vérification de l'unicité des éléments d'un tableau n Un algorithme de force brute compare par paires tous les éléments jusqu'à ce que deux éléments identiques soient trouvés, ou jusqu'à ce que toutes les paires possibles aient été examinées. Dans le pire des cas, l'efficacité est quadratique. n Vous pouvez aborder la solution du problème d'une autre manière - triez d'abord le tableau, puis comparez uniquement les éléments consécutifs. n Le temps d'exécution de l'algorithme est la somme du temps de tri et du temps de vérification des éléments voisins. n Si vous utilisez bon algorithme tri, l'ensemble de l'algorithme de vérification de l'unicité des éléments du tableau aura également une efficacité de O (n log n) ©Pavlovskaya T. A. (SPb NRU ITMO) 51