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

Gaga

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

• 2002

Informations

• Publié par: bankexam
• Publié le: 15 août 2008
• Nombre de lectures: 57
• Langue: Français

Extrait

Examen de l’U.V. AG51

16/01/2002

J.Gaber ([e-mail])

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.