Scribd Logo
Importer

Bienvenue sur Scribd !

  • 193 vues

    Exam 1617

    Transféré par

    walidmg

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Exam 1617

    Transféré par

    walidmg
    193 vues2 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    193 vues2 pages

    Exam 1617

    Transféré par

    walidmg

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    Université Hassiba Benbouali de Chlef Durée : 1h30

    Faculté des sciences


    Département d’informatique
    Examen TG L2- 2017

    Exercice 1. (5 pts)
     Montrer que tout arbre est un graphe biparti.
     Soit T=(V,E) un arbre , Montrez que |V|=|E|+1.

    Exercie2. (5 pts)
    Une compagnie de développement de logiciels doit travailler sur trois projets P1,P2 et P3 dans les
    4 prochains mois. P1 peut commencer seulement après le premier mois et doit se terminer avant
    la fin du troisième mois. P2 et P3 peuvent commencer le premier mois et doivent se terminer,
    respectivement, avant la fin du quatrième et deuxième mois.
    Les projets nécessitent, respectivement un volume de, 8, 10 et 12 ingénieurs/mois. Chaque mois 8
    ingénieurs sont disponibles. A cause de la structure interne de la compagnie, pas plus de 6
    ingénieurs peuvent travailler, en même temps, sur le même projet.

    1. Décrire comment ce problème revient a un problème de max flot.


    2. Déterminer s'il est possible de compléter les trois projets dans les délais demandés.

    Exercice3. (5 pts)
    Soit le graphe G ci-dessous qui représente le plan d`un zoo. Le sommet A représente l`accès et les
    autres sommets sont les différents sites animaliers. Une arête représente une allée (un chemin)
    pondéré par la distance (en mètres) entre les deux secteurs. Pour nettoyer les allées, une balayeuse
    automobile est utilisée.
    1. Est-il possible que cette balayeuse n'emprunte chaque allée qu'une et une seule fois? Si oui,
    décrire le parcours correspondant.
    2. Les services de sécurités situés au secteur A doivent intervenir dans le secteur H. En utilisant
    l'algorithme de Dikjstra, déterminer le plus court chemin pour s'y rendre et donner sa longueur.

    AB AC AD AE BC BD BE CD CH DE DF DG EF FH GH
    50 300 150 150 200 150 200 100 250 100 100 200 150 250 150
    B
    A
    C

    G
    E
    H
    F
    Exercice 4. (5 pts)
    L’université de Chlef entame un projet qui nécessite la réalisation des tâches identifiées par les
    lettres A à I et dont les caractéristiques sont les suivantes:

    Tache Précédence Durée


    A - 4 jours
    B - 2 jours
    C A 2 jours
    D B ¼ jours
    E F 3 jours
    F - 1,5 jours
    G C 2,5 jours
    H E 10 jours
    I G, H 1,5 jours

     Dessiner le réseau de PERT correspondant


     Déterminez une durée totale minimale de rénovation et le chemin critique dans ce graphe.

    Vous aimerez peut-être aussi