Calculs de complexité pour des tris et des bipartitions

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: 8O :weird:


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é !

Bonjour,

Je ne vais pas te donner les réponses, car ce serait trop facile et ce n'est pas le but du forum ;) Mais voici quelques questions pour t'amener vers la bonne voie :

Citation:

---

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.

---

Soit A l'élément le plus grand tu tableau. Que dois-tu faire pour vérifier que cet élément est bien le plus grand du tableau?

Citation:

---

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 ?

---

Quelle est la caractéristique d'un plus grand élément quand on le compare aux autres éléments ?

Citation:

---

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 ?

---

Le second élément du tableau est le plus grand élément de quel ensemble?

Citation:

---

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 ?

---

Que se passe-t-il dans un tournoi sportif lors des phases d'éliminations? S'intéresser à ce que peut représenter le gagnant d'un tournoi.

Citation:

---

Exercice : Heuristiques gloutonnes

---

Là, je pense que tu devrais lire ton cours, car c'est un concept algorithmique qui y a sûrement été expliqué. Ou fais un petit tour sur ton moteur de recherche préféré et tu trouveras sûrement toutes les infos à ce propos.