IFT1025 - Automne 2005 Examen Final

Échéance: Vendredi, 13 janvier 2006, 23h59

Introduction

L'échéance n'est pas flexible! Vous recevrez un 0 pour un examen soumis en retard!

Vous pouvez soumettre votre examen par courriel (au format MSWord, texte ou pdf) à eckdoug@iro.umontreal.ca N'utilisez pas remise et n'envoyez pas l'examen à pift1025 ou dift1025 (le trimestre d'Hiver 2006 va commencer avant le date limite pour la remise). Vous pouvez aussi choisir d'imprimer votre examen et de le remettre dans le casier du Prof. Douglas Eck (AA-2145). Le seul advantage du papier est qu'il y a un questione ou vous aurez à dessiner un arbre. Donc c'est peut-être plus facile de le dessiner avec un stylo. Mais il n'est pas nécessaire d'utiliser une représentation tres complexe. Vous pouvez simplement faire:

   F
  | |
 B   J
| | | |
A C G Q
Donc je vous recommande que la soumission électronique.

Vous pouvez utiliser n'importe quel ressource (web, livre, etc). Cependant, vous ne pouvez pas copier directemment le code d'un autre auteur. En plus, vous ne pouvez pas partager vos travaux ou discuter de l'examen avec les autres membres du cours. Je vais traiter des infractions comme le plagiat!

1. Classes, Héritage (15 Pts)

Écrire les classes nécessaires pour résoudre le problème suivant :

Une entreprise désire stocker et retrouver des informations concernant l'équipement dont elle dispose. Voici les contraintes :

Fournissez une fonction static void main(String [] args) qui crée au moins un équipement de chaque type et le stock dans une ArrayList<Equipment>. Faites une itération sur cette ArrayList et affichez chaque instance en utilisant sa fonction par défaut toString() . La fonction toString() devra afficher toutes les variables ainsi que la valeur actuelle de chaque équipement.

2. Exceptions (10 Pts)

Considèrez le code suivant:

import java.util.*;
class LengthByException{
    static int lengthOfTable(int [] x) {
        //Code manquant ici
    }

    public static void main(String [] args) {
	int [] x = new int[1000];
	int l = lengthOfTable(x);
	System.out.println("Length is "+l);
    }
}
Ecrivez la méthode lengthOfTable(). Cette méthode devra calculer la longueur de x sans pour autant utiliser x.length. Au lieu de cela, on devra calculer la longueur en forçant la génération d'une exception et en la traitant par la suite.

3. Graphisme (20 Pts)

Le programme suivant RandBall.java (dérivé de la class Pong.java discutée en classe) déplace une balle de manière aléatoire dans l'écran.

import java.awt.geom.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.*;
import javax.swing.*;
import java.util.Random;

public class RandBall extends JPanel implements Runnable {
    Random r;
    int ballX=100;
    int ballY=100;
    double ballDir=0;
    double randSpeed=5;
    Thread animator;

    RandBall () {
	r = new Random();
	animator = new Thread(this);
	animator.start();
    }

    public void run() {
	while (1==1) {
	    try {
		Thread.sleep(50);
		repaint();
	    } catch (InterruptedException e) {
		System.out.println(e);
	    }
	}
    }

    public void paintComponent(Graphics g) {
        super.paintComponent(g);
	ballDir=ballDir + (r.nextDouble()-.5);
	ballX+=(int)(randSpeed*Math.sin(ballDir));
	ballY+=(int)(randSpeed*Math.cos(ballDir));
	g.setColor(Color.RED);
	g.fillOval(ballX,ballY,10,10);
	if (ballX<0) ballX+=getWidth();
	if (ballY<0) ballY+=getHeight();
	ballX=ballX % getWidth();
	ballY=ballY % getHeight();
    }

    public static void main(String[] args)
    {
	JFrame frame = new JFrame();
	RandBall r = new RandBall();
	frame.add(r);

	final int FRAME_WIDTH = 300;
	final int FRAME_HEIGHT = 400;

	frame.setSize(FRAME_WIDTH, FRAME_HEIGHT);
	frame.setTitle("RandBall");
	frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
	frame.setVisible(true);
    }
}

Cette question est en 2 parties.

Partie I -- TracerBall.java (50%)

Écrivez la classe TracerBall qui hérite de RandBall. TracerBall devra stocker les 20 positions précédentes (x, y) de la balle et les représenter en tant que cercles, en utilisant la Graphics.drawOval() de telle manière que la trace de la balle soit visible. Stocker les coordonnées x, y dans un objet de type Dimension. Dimension est un objet simple qui sert juste a stocker (x, y). Par exemple :

Dimension d = new Dimension(10,20);
System.out.println(d.width + "x" + d.height);
aboutit à :
10x20

Utilisez une LinkedList d'objets Dimension pour stocker les positions (donc créez une liste en utilisant LinkedList<Dimension> l = new LinkedList<Dimension>()).

Partie II -- ChaseBall.java (50%)


Écrivez la classe ChaseBall qui hérite de TracerBall. ChaseBall devra ajouter un point bleu au milieu du panel. Quand l'utilisateur cliquera quelque part dans le panel, le point bleu devra réapparaître à cet endroit. La balle rouge sera elle aussi transfèrer a cet emplacement et continuera par la suite d'avoir un mouvement aléatoire.

4. Collections (20 Pts)

En classe, nous avons discuté de l'utilisation des arbres de recherche binaire (ou BST : Binary Search Tree) pour implanter une Map. Un code exemple a également été fourni dans CollectionsSimplifiees. Comme exemple, voici le code permettant d'ajouter 2 strings à un BST vide et par la suite, supprimer un des String de l arbre .
BST bst = new BST();
bst.insert("A");
bst.insert("B");
bst.delete("A");

Une faiblesse de notre implantation de BST est qu'elle peut mener a des arbres débalancés (unbalanced).

Donnez les réponses aux questions suivantes :

  1. (25%) Qu'est ce que cela signifie de dire qu'un arbre est débalancé? Pourquoi les arbres débalancés sont une plus mauvaise solution que les arbres balancés dans le cas de la recherche d'élément?
  2. (25%) Fournissez le code qui permet d'ajouter 7 Integers a un arbre vide, de telle maniere que l'arbre obtenu soit fortement débalancé. Dessinez cet arbre.
  3. (25%) Fournissez le code qui permet d'ajouter 7 Integers a un arbre vide, de telle maniere que l'arbre obtenu soit tout à fait balancé. Dessinez cet arbre.
  4. (25%) Décrivez la méthode permettant de supprimer un élément d'un BST. Considèrez séparément le cas ou l'élément à supprimer sera une feuille (un noeud sans enfant) et le cas ou l'élément à supprimer n'est pas une feuille (possède des enfants). Il n est pas nécessaire de fournir le code.

5. Implantation de structure de donnée (15 Pts)

Créez une map qui vous permet de faire une recherche par clé (comme dans les Map standards) ou par valeur (qui pourrait donner un ensemble de solutions). Votre version doit hériter de HashMap. Vous devrez également implanter les méthodes ArrayList getKeys(Object key) ainsi que public String toString(). Votre programme devra fonctionner avec le cod suivant: main(String [] args):
public static void main(String [] args) {
  BiMap bm = new BiMap();
  bm.put(new Integer(1),"camion");
  bm.put(new Integer(2),"camion");
  bm.put(new Integer(3),"voiture");
  bm.put(new Integer(4),"moto");
  System.out.println(bm);
  System.out.println("--------------");
  ArrayList l = bm.getKeys("camion");
  System.out.println(l);
}
de manière a produire la sortie suivante :
Par cle: {2=camion, 4=moto, 1=camion, 3=voiture}
Par valeur: {camion=[1, 2], moto=[4], voiture=[3]}
-------------
[1, 2]

6. Threads (20 Pts)


Le Diner de Philosophes

Cette question concerne le fameux problème du "diner de philosophes" que nous avons discuté en classe. Celui-ci met en avant le problème de "deadlock" dans des systèmes à threads multiples quand des ressources partagées doivent être utilisées. En résumé, 5 philosophes veulent diner ensemble. Il mange de la nourriture chinoise. Malheureusement, il n'y a qu'une seule baguette par convive et de ce fait, ils doivent se les partager. Pour manger, un philosophe doit prendre la baguette à sa gauche ainsi que celle à sa droite (les rendant momentanément indisponibles pour le convive à sa gauche et celui à sa droite qui, de ce fait ne peuvent pas manger). Un philosophe qui a 2 baguettes prend alors une bouchée puis repose ses 2 baguettes sur la table. Ainsi ses voisins pourront eux aussi manger. Voici une implantation défectueuse du "diner de philosophes" (Dining.java).

import java.util.ArrayList;

import java.util.Random;
class Dining {

    Random r;
    ArrayList<Philosophe> p;
    ArrayList<Baguette> c;
    static final int NUM_PHIL=5;
    Dining() {
	p = new ArrayList<Philosophe>();
	c = new ArrayList<Baguette>();
	r=new Random();
	for (int i=0;i<NUM_PHIL;i++) {
	    c.add(new Baguette());
	}

	for (int i=0;i<NUM_PHIL;i++) {
	    p.add(new Philosophe(i));
	}
    }


    public void eat() {
	for (Philosophe phil : p) {
	    phil.start();
	}
    }


    class Philosophe extends Thread {
	Baguette gauche;
	Baguette droite;
	int idx;
	Philosophe(int idx) {
	    super();
	    gauche=c.get(idx);
	    droite=c.get((idx+1)%NUM_PHIL);
	    this.idx=idx;
	}

	public void run() {
	    while (1==1) {
		try {
		    sleep(r.nextInt(1000));
		    gauche.get();
		    System.out.println("Le philosophe " + (idx+1) + " a pris la baguette a gauche");
		    sleep(r.nextInt(1000));
 		    droite.get();
		    System.out.println("Le philosophe " + (idx+1) + " a pris la baguette a droite");
		    System.out.println("Le philosophe " + (idx+1) + " a mange!");
		    sleep(r.nextInt(1000));
		    gauche.put();
		    System.out.println("Le philosophe " + (idx+1) + " a remis la baguette a gauche");
		    droite.put();
		    System.out.println("Le philosophe " + (idx+1) + " a remis la baguette a droite");
		} catch (Exception e) {
		    System.out.println(e);
		}
	    }
	}
    }
    class Baguette {
	private boolean taken=false;
	private int identity;

	Baguette () {
	}
	synchronized void put() {
	    taken=false;
	    notify();
	}
	synchronized void get() throws java.lang.InterruptedException {
	    while (taken) wait();
	    taken=true;
	}
    }

    public static void main(String [] args) {
	Dining d = new Dining();
	d.eat();
    }

}

Cette question est en 2 parties:

Retour a la page principale d'ift1025