1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    novembre 2012
    Messages
    15
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : novembre 2012
    Messages : 15
    Points : 7
    Points
    7

    Par défaut 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:


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

  2. #2
    Membre éprouvé
    Femme Profil pro
    Étudiant
    Inscrit en
    octobre 2016
    Messages
    792
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 22
    Localisation : France, Vaucluse (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Industrie

    Informations forums :
    Inscription : octobre 2016
    Messages : 792
    Points : 1 293
    Points
    1 293

    Par défaut

    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 :
    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?
    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 ?
    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?
    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.
    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.

Discussions similaires

  1. Réponses: 1
    Dernier message: 28/11/2015, 12h25
  2. Réponses: 2
    Dernier message: 07/04/2009, 11h45
  3. Tri sur des index ou des références
    Par beegees dans le forum C++
    Réponses: 2
    Dernier message: 10/05/2008, 12h29
  4. Réponses: 5
    Dernier message: 03/12/2007, 23h45
  5. Réponses: 3
    Dernier message: 30/08/2007, 15h41

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo