|
Questions de 16 points sur la conception et l'analyse d'algorithmes (CS1201) :
1. (a) Qu’est-ce qu’un algorithme diviser pour régner ? Expliquer l’approche générale des algorithmes diviser pour régner. (6 points)
(b) Utilisez l'approche diviser pour régner pour concevoir un algorithme permettant de trouver l'élément minimum dans un tableau de n éléments. Analysez la complexité temporelle de votre algorithme. (10 points)
2. (a) Expliquer le concept des techniques de hachage et de résolution de collisions. (6 points)
(b) Considérons une table de hachage de taille m et un ensemble de n éléments à hacher. Supposons que les éléments soient uniformément répartis entre les m emplacements. Quelle est la probabilité d’une collision lorsque n =m/2 ? Analysez le nombre moyen de comparaisons nécessaires pour insérer avec succès tous les éléments dans la table de hachage à l'aide d'un sondage linéaire. (10 points)
3. (a) Décrivez le concept de programmation dynamique et expliquez en quoi il diffère de l'approche diviser pour régner. (6 points)
(b) Utilisez la programmation dynamique pour résoudre le problème de coupe de tiges, où une tige de longueur n peut être coupée en tiges plus petites, et chaque tige de longueur i a un prix p[i]. Le but est de trouver le maximum de revenus pouvant être obtenu en coupant la tige en morceaux plus petits. Analysez la complexité temporelle et spatiale de votre algorithme. (10 points)
4. (a) Expliquer le concept de NP-complétude et son importance dans l'analyse des algorithmes. (6 points)
(b) Prouver que le problème suivant est NP-complet :Étant donné un ensemble de n éléments avec leurs poids et valeurs respectifs, déterminer s'il existe un sous-ensemble de ces éléments dont le poids total est inférieur ou égal à une limite donnée et dont le total la valeur est maximisée. (10 points)
5. (a) Expliquer le concept d’analyse amortie des algorithmes. Pourquoi est-il utilisé et quels sont ses avantages ? (6 points)
(b) Effectuer une analyse amortie de la structure de données de la pile, où les opérations push et pop sont les seules opérations autorisées. Déterminez la complexité temporelle moyenne de chaque opération. (10 points)
6. (a) Décrivez l'algorithme de Kruskal pour trouver l'arbre couvrant minimum d'un graphe non orienté pondéré. (6 points)
(b) Appliquez l'algorithme de Kruskal au graphique suivant et trouvez l'arbre couvrant minimum :
```
(1)---2---(3)
/ |
/ |
5 / 4
-----------
(4)---6---(5)
```
Calculez le poids total de l'arbre couvrant minimum. (10 points)
7. (a) Expliquer le concept d'une sorte topologique de graphe acyclique orienté (DAG). (6 points)
(b) Effectuez un tri topologique sur le DAG suivant :
```
(1) -> (2) -> (3)
\/
-> (4)
```
Fournissez l'ordre des sommets dans le tri topologique. (10 points)
8. (a) Décrivez le concept des arbres de recherche binaires (BST). Expliquez comment les BST sont utilisés pour des opérations de recherche et d'insertion efficaces. (6 points)
(b) Insérez les éléments suivants dans un BST initialement vide :20, 10, 30, 5, 15, 25, 35. Dessinez le BST résultant et analysez la complexité temporelle de la recherche d'un élément dans ce BST. (10 points)
N'oubliez pas de démontrer une compréhension claire des concepts, de fournir des explications correctes et d'analyser les complexités temporelles et spatiales des algorithmes, si nécessaire.
|
