INF4110-10 Revision pour l'examen final (Automne 1998)

Quelques questions de revision pour l'examen final -- INF4110-10

Automne 1998

Quelques questions de revision pour l'examen final -- INF4110-10

Automne 1998

1. Horaire d'un tournoi ( pts)

On désire concevoir un horaire des rencontres d'un tournoi de tennis impliquant n = 2^k joueurs. Les contraintes suivantes doivent être respectées:

1.

Chaque joueur doit jouer contre chacun des autres joueurs;

2.

Chaque joueur doit jouer exactement 1 match par jour, pour chacune des n-1 journées du tournoi.

Concevez un algorithme pour produire l'horaire d'un tel tournoi. Quelle est sa complexité asymptotique?

2. Problème de l'empaquetage ( pts)

Le problème de l'empaquetage (bin packing) est le suivant:

• On reçoit en entrée une série d'items $I_1, \ldots, I_n$. Chaque item est caractérisé par un attribut donnant sa taille, laquelle taille est un nombre réel tel que $0 < taille(I_j) \leq 1$.
• On désire empaqueter les divers items en les mettant dans des boîtes, toutes de taille égale à 1. Chaque boîte peut donc contenir tout groupe d'items dont la somme des tailles ne dépasse pas 1.
• Bien que l'on ait une immense provision de boîtes, l'objectif est évidemment de minimiser le nombre de boîtes requises pour empaqueter les divers items.

Concevez un algorithme pour résoudre ce problème. Votre algorithme n'a pas à produire la solution optimale. Toutefois, il devrait produire une solution pas trop mauvaise (en d'autres mots, ne mettez pas chaque item dans une boîte séparée!) en un temps relativement efficace.

Quelle est la complexité de votre algorithme en fonction de n (le nombre d'items)?

3. Construction d'un arbre binaire de recherche optimal ( pts)

Soit une suite ordonnée de clés c₁, ..., c_n, donc telle que c_i < c_i+1 (pour $i=1, \ldots n-1$).

On désire construire un arbre binaire de recherche qui minimisera le temps moyen de recherche. On suppose que l'on connaît, pour chaque clé, la probabilité que la clé soit demandée, dénotée par prob(c_i). On a donc:

$$\sum_{i=1}^n prob(c_i) = 1$$

Le coût associé à un arbre binaire peut être exprimé par le nombre de comparaisons requis pour chercher un élément donné, lequel coût est fonction de la position (profondeur) de l'item dans l'arbre. Soit d(c_i) la profondeur (depth) de la clé c_i dans l'arbre. Le coût moyen de recherche pour les diverses clés sera alors le suivant:

$$\sum_{i=1}^n prob(c_i) (1 + d(c_i))$$

Concevez un algorithme permettant de construire l'arbre binaire de recherche de coût optimal. Quelle est la complexité de votre algorithme?