Examen première session – 17 mai 2019

Durée 2h, documents autorisés

Mediane

On cherche un algorithme pour calculer la médiane d’une liste d’entiers.

Rappel : la médiane d’une liste \(L\) de longueur \(n\) est un élément \(m∈L\) tel que il y a dans \(L\) au plus \(\lfloor n/2 \rfloor\) entiers strictement plus petits que \(m\) et au plus \(\lfloor n/2 \rfloor\) strictement plus grands que \(m\).

: Proposer un algorithme qui fait appel à une procédure de tri. Quelle est sa complexité ?

: Donner un exemple de son exécution sur la liste \(L=[13,1,2,20,3,4,15,1,6]\).

: Proposer un algorithme de complexité \(O(n)\) en moyenne. Justifier la complexité.

: Donner un exemple de son exécution sur la liste \(L=[13,1,2,20,3,4,15,1,6]\).

Graphes

On considère le graphe non-orienté ci-dessous:

: Le graphe est-il connexe? Complet?

: Trouver un arbre couvrant minimal, par l’algorithme de Prim ou de Kruskal, au choix. Détailler les étapes de l’algorithme: en quel ordre sont sélectionnées les arêtes ?

: Trouver le chemin le plus court entre b et g par l’algorithme de Dijkstra. Détailler les étapes de l’algorithme: comment évoluent les informations attachées aux nœuds au fil de l’exécution?

: Proposer un algorithme qui détecte si un graphe est acyclique.

String matching

: Quelles sont les chaînes de caractères sur l’alphabet {a,b} acceptées par l’automate ci-dessous ? (0 est l’état initial)

: Donner la liste des états visités successivement par l’automate lorsqu’il reçôit en entrée la chaîne bbaaababba. Cette chaîne est-elle acceptée ?

: Dessinner un automate reconnaissant les occurrences du motif ababa.

: Proposer un algorithme qui reconnaît tous les mots contenant le motif aba ou le motif bab, en faisant une seule passe sur la chaîne de caractères en entrée.

Programmation linéaire

On considère le programme linéaire suivant :

Minimiser \(-2x - 5y\)
Sous
\(\begin{array}{c r r r} 2x& + y& ≤& 10,\\ -3x& + 2y& ≤& 27,\\ 5x& - y& ≤& 4, \end{array}\)

\(x,y≥0\).

: Mettre le programme linéaire sous forme relaxée en ajoutant des variables de relaxation.

: Trouver la solution du programme linéaire en détaillant les étapes de l’algorithme du simplexe.