Serie - 1 Complexite Algo Iteratifs [PDF]

Zitiervorschau

ENIT : Ecole Nationale d’Ingénieurs de Tunis Cours : Algorithmique & Complexité

Hamrouni Kamel

Série d’exercices - 1 Algorithmes itératifs    Exercice-1 :  Complexité de séquences itératives Déterminer (en fonction de n à O( ) près) la complexité en nombre « d’opérations » de chaque séquence : Séq-1 :

For i = 1 to N do Opération ; Endfor Séq-2 : For i = 1 to N do For j = 1 to i do Opération ; Endfor Endfor Séq-3 : i=1 While ( i < N) Do i = 2*i Opération ; Endwhile Séq-4: For i = 1 To N Do J=1 While (J < N ) Do J=2*J Opération; Endwhile Endfor Séq-5: i=1 While ( i < N ) Do i = 2*i For j = 1 to i Do Opération; Endwhile

Séq-6:

Séq-7:

Séq-8 :

i=1 For j=1 To n do i = 2*i Endfor For j= 1 to i do Opération; Endfor i=1 For k = 1 To n do i = 2*i For L = 1 to i do For m = 1 to k do Opération ; Endfor Endfor Endfor For k = 1 to n do i=1 For j = 1 to k do i = 2*i Endfor For j = 1 to i do Opération Endfor Endfor

Exercice-2 : Recherche du maximum 1. Concevoir un algorithme de recherche du maximum dans un ensemble à n éléments 2. Quelle est la complexité de votre algorithme en nombre de comparaisons ? 3. Montrer qu'il est optimal.

Exercice-3 : Recherche du maximum et du minimum Nous supposons ici que l'ensemble considéré ne contient pas deux fois la même valeur. 1. Proposer un algorithme naif de recherche du maximum et du minimum d'un ensemble de n éléments. 2. Quelle est sa complexité en nombre de comparaisons ? 3. Proposer un algorithme plus efficace. Indication : dans une première phase les éléments sont comparés par paire. 1/4

Cours : Algorithmique & Complexité Série Algorithmes itératifs

Hamrouni Kamel

4. Quelle est sa complexité en nombre de comparaisons ?

Exercice-4 : Recherche du deuxième plus grand élément Nous supposons ici que l'ensemble considéré ne contient pas deux fois la même valeur. 1. Proposer un algorithme simple de recherche du deuxième plus grand élément. 2. Quelle est sa complexité en nombre de comparaisons ? 3. Réécrire l’algorithme de recherche du maximum sous la forme d'un tournoi de tennis. Il n'est pas nécessaire de formaliser l'algorithme ici, une figure explicative suffit. 4. Dans combien de comparaisons, le deuxième plus grand élément de l'ensemble s’est rendu compte qu’il est le plus petit des deux éléments comparés ? 5. Proposer un nouvel algorithme de recherche du deuxième plus grand élément. 6. Quelle est sa complexité en nombre de comparaisons ?

Exercice-5 : Puissance Xn (Méthode Chinoise) Ecrire un algorithme et implémenter le en C permettant de calculer Xn avec la méthode Chinoise. a- Donner une formule récurrente estimant sa complexité b- Calculer sa complexité en utilisant le théorème de résolution des récurrences.

Exercice-6 : Motif 1D Etant donnée un tableau entier A de taille N et un tableau entier F de taille U. On suppose que U est inférieur à N. a- Ecrire un algorithme naïf pour chercher les sous-tableaux F de A égaux au tableau F. L’algorithme doit afficher la position début à laquelle le tableau F est trouvé. b- Estimer sa complexité en fonction de N et U

Exercice-7 : Motif 2D Etant donnée une matrice entière A de dimension NxM et une matrice entière F de dimension UxV. On suppose que U est inférieur à N et V est inférieur à M. c- Ecrire un algorithme pour chercher les sous-matrices de A égales à la matrice F. L’algorithme doit afficher la position début à laquelle une matrice est trouvée. d- Estimer sa complexité en fonction de N, M, U et V Exemple: Matrice A :

Matrice F : La matrice F existe deux fois dans la matrice A : une à la position (0,0) et l’autre à la position (2,1). Attention, ceci n’est qu’un exemple, il faut écrire l’algorithme dans le cas général

1510371510 5101548510151215103 65101574613209

Exercice-8 : Chevauchement Soit une grille de taille NxM de lettres de l’alphabet. On voudrait déterminer le plus grand chevauchement partiel de deux copies identiques de la grille. Dans l’exemple ci-contre la grille admet Exemple-1

Exemple-2

ABCDEFGHABCDIJGHA

ABCDEFGHABCDEFIJGHABCDK

ABPQPQRSRS

ABPQABPQRSPQRSA

BKLIJGH

LIJGHABKLIJGH

AB

BRSAB

2/4

Cours : Algorithmique & Complexité Série Algorithmes itératifs

Hamrouni Kamel

un chevauchement partiel de 12 lettres. Elaborer un programme pour trouver le chevauchement partiel maximal d’une grille. Le programme doit imprimer les indices du début de chevauchement ainsi que la direction (vers le bas ou vers le haut). On peut aussi essayer (mais c’est un peu plus compliqué) d’imprimer le résultat sous la forme indiquée dans l’exemple. Estimer sa complexité.

Exercice-9 : Anagramme Deux mots sont dits anagrammes s’ils sont composés des mêmes lettres mais dans un ordre différent. Exemple : UN et NU, ELLES et SELLE, SURE et RUSE Etant donné, un tableau de N pointeurs. Chaque pointeur pointe sur une chaîne de caractères représentant un mot. a- Ecrire une fonction « max_anagram » qui permet de retourner la longueur du plus long anagramme. On vous conseille de commencer par écrire une fonction « anagram » qui vérifie si deux mots sont ou non anagrammes. Elle doit retourner la longueur du mot s’ils sont des anagrammes et 0 sinon. b- En supposant que les mots ont une longueur moyenne égale à M, estimer en fonction de N et M, la complexité nécessaire pour déterminer l’anagramme le plus long en nombre de comparaisons de caractères. c- Proposer un autre algorithme pour la fonction « anagram » pour réduire la complexité

Exercice-10 :  Mots composés Il existe des mots qui sont composés d’autres mots. Exemple : bonjour qui est composé du bon et du mot jour. Etant donné une liste de N mots, il s’agit de trouver les mots qui sont composés d’autres mots de la liste. Voici un exemple de listes de mots ; Bag, sun, day, moon, Sunday, Monday, airbag, MoonBag, air

Exercice-11 : Somme maximale d’un Torus 1- Soit une matrice entière de dimension NxM contenant des valeurs positives négatives ou nulles. Elaborer un algorithme permettant de 1 -1 0 0 -4 trouver la sous-matrice donnant la somme maximale. 2 3 -2 -3 2 On peut se contenter d’imprimer la valeur de la 4 1 -1 5 0 somme. 3 -2 1 -3 2 2- Un torus est une matrice de dimension NxM circulaire à la fois verticalement que horizontalement. Soit un -3 2 4 1 -4 torus contenant des valeurs entières pouvant être positives négatives ou nulles. Elaborer un algorithme permettant de trouver la sousmatrice donnant la somme maximale. Exemple : pour cette matrice le résultat est 15. Indication : il faut s’inspirer des algorithmes vus en cours pour déterminer la plus grande somme contigue dans une séquence.

Exercice-12 :  Recherche de sous-chaîne : algo. de Knuth-Morris-Pratt Etant donnée une chaîne de caractères S de longueur N et une sous-chaîne de caractères T de longueur M avec M