Bonjour à tous,
Sachant que je n'ai rien suivi des cours magistraux d'algorithmique, mon prof m'a donné 2 exercices à faire. Selon lui, ce sont des exos facile ...
Mais actuellement voici mon visage:
Exercice 1:
On s’intéresse ici à des algorithmes permettant de déterminer le plus grand et le second
plus grand élément dans un tableau.
1) Montrer que, pour trouver le plus grand élément d’un tableau de taille n, il est nécessaire
de faire au moins n − 1 comparaisons.
2) Donner un algorithme déterminant le plus grand élément d’un tableau en le parcourant.
Combien de comparaisons fait-il pour un tableau de taille n ?
3) Adapter cet algorithme pour trouver le second plus grand élément du tableau. Combien
de comparaisons fait-il pour un tableau de taille n ?
4) Donner un autre algorithme trouvant le plus grand élément comme dans un tournoi
sportif (inutile d’écrire formellement l’algorithme, une figure explicative suffira). Combien
de comparaisons fait-il pour un tableau de taille n ?
5) Adapter cet algorithme pour trouver le second plus grand élément du tableau. Combien
de comparaisons fait-il pour un tableau de taille n ?
Exercice : Heuristiques goutonnes
On étudie le problème de la bi-partition : étant donné un ensemble de nombres, on veut
les répartir en deux sous-ensembles dont les sommes soient le plus proches possibles.
1) Proposer un algorithme glouton pour essayer de résoudre ce problème
2) L’appliquer aux ensembles suivants :
— {4, 5, 6, 7, 8},
— {2, 10, 3, 8, 5, 7, 9, 5, 3, 2},
— {771, 121, 281, 854, 885, 734, 486, 1003, 83, 62}.
Qu’en déduire ?
Montrer que si la solution optimale est une séparation en deux ensembles de sommes
respectives s1 et s2, alors l’algorithme glouton donne des ensembles de sommes respectives
inférieures ou égales à (4/3)max{s1, s2}.
Pouvez-vous m'expliquer rien que le sujet svp (J'essaye de faire des efforts mais cette matière me donne la varicelle)
Merci pour votre bonté !
Partager