Algorithmiques avancées 2002 Génie Informatique Université de Technologie de Belfort Montbéliard

Algorithmiques avancées 2002 Génie Informatique Université de Technologie de Belfort Montbéliard

-

Français
2 pages
Lire
Cet ouvrage peut être téléchargé gratuitement

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Algorithmiques avancées 2002. Retrouvez le corrigé Algorithmiques avancées 2002 sur Bankexam.fr.

Sujets

Informations

Publié par
Publié le 15 août 2008
Nombre de lectures 57
Langue Français
Signaler un problème
Examen de l’U.V. AG51
16/01/2002
J.Gaber (gaber@utbm.fr)
Exercice I
:
fouille de données (Data Mining)
On dispose de données structurées. Les objets sont représentés par des enregistrements (ou
descriptions) qui sont constitués d'un ensemble de champs (ou attributs) prenant leurs valeurs
dans un domaine. Un algorithme de fouille de données (data mining) est un processus qui
permet l'extraction de connaissances dans les bases de données (Knowledge Database
Discovery, KDD) contenant de grands jeux de données. On part du principe suivant, on
dispose d’un grand volume de données mais on ne dispose pas forcément de l’information.
Parmi les méthodes de mise en oeuvre d’un algorithme de fouille de données, nous avons
étudié celle de la recherche des règles d'association (Association Rules Mining, ARM) qui
consiste à déterminer les valeurs qui sont associées. L'exemple type est la détermination des
articles (les pattes et la sauce tomate, la baguette et le camembert et le jus de raisin, ...) qui se
retrouvent ensemble sur un même ticket de supermarché. L’intérêt est d’identifier des
opportunités de vente croisée et concevoir des groupements attractifs de produit.
Question I-1
Soit l’ensemble suivant décrivant des transactions effectuées dans notre supermarché favoris
pour l’achat de produits désignés par les lettres A(pattes), B(sauces tomates), C(eau minérale),
D(couches-culottes) et E(baguette)
T1
A, D
T2
A, B, C
T3
A,E
T4
A, D, E
T5
B, D
Donnez les règles dont le niveau de confiance minimum est de 50%
Question I-2
Donnez un algorithme génétique permettant la mise en oeuvre du processus de recherche des
règles d'association.
Exercice II
:
Optimisation
Pour finir leur projet dans les délais en tenant compte du nouveau volume horaire
hebdomadaire de 35h, des ingénieurs ont décidé de se partager les tâches journalière d’une
manière équitable. Sachant que ces
N
ingénieurs disposent d’une plage horaire journalière de
taille
T
et d’un ensemble de
M
tâches à réaliser chaque jour, chaque tâche
i
est de taille
t
i
c-à-d
nécessite une volume horaire
t
i
, proposez, au choix, un algorithme génétique ou un algorithme
utilisant un réseau de Hopfield permettant d’affecter les tâches d’une manière optimale.
Exercice III
:
Algorithmes géométriques
Donnez un algorithme permettant de vérifier si un point donné se trouve au dessus ou en
dessous d’un ensemble de droites. Evaluer la complexité de l’algorithme en détail.
Exercice IV
:
Structures de données
L’
arbre de priorité équilibré
(APE) intervient dans les problèmes de files d’attente avec
priorité où l’on doit effectuer plusieurs tâches selon un ordre de priorité.
Soit
A
un arbre binaire dont les étiquettes appartiennent à un ensemble totalement ordonné
(par exemple des entiers). On dit que
A
est un arbre de priorité équilibré s’il vérifie pour tout
noeud
n
de
A
:
-
l’étiquette de
n
est supérieure ou égale à celle de son ou ses fils s’il en a,
-
si
g
et
d
désignent les branches gauches et droite issues de
n
alors
N(g)-1 <= N(d) <= N(g)-1
.
On note par
N(x)
, le nombre de noeuds de l’arbre de racine
x
.
Par convention, un arbre vide
est un APE.
Question IV-1
: Donnez l’APE correspondant à l’insertion successives des tâches suivantes :
5 , 4, 1, 3, 2, 0. Les valeurs désignent le niveau de priorité.
Question IV-2
: Donnez la complexité des opérations suivantes :
a.
Insertion d’une nouvelle tâche ayant une certaine priorité.
b.
Extraction d’une tâche prioritaire (celle associée à la racine) et reconstitution d’un
APE avec les tâches restantes.
Barème : 5 points par exercice.