enonce deuxième session CDL 1999

1 - Preuve :
Soient les affirmations suivantes formant une 'énigme' :
"Les développeurs sont doués ou intelligents,
mais les développeurs intelligents ne développent pas en C,
pourtant il y a des développeurs qui développent en C et en Java
donc il y a des développeurs doués qui développent en Java."

Question 1.1 : Formaliser ce problème en calcul des prédicats.

Question 1.2 : Donner une preuve par les tableaux sémantiques.

2 - Prolog :
Les tableaux rectangulaires M x N seront représentés en prolog par la liste des lignes (qui sont des listes d'éléments) i.e. une liste de M listes de longueur N .
exemple :
1 6 21 14
10 16 3 11
24 13 8 25 est représenté par :
[[1,6,21,14] , [10,16,3,11] , [24,13,8,25]]
Le transposé d'un tableau 'tab' rectangulaire MxN est un tableau 'trans' rectangulaire NxM tel que {[universal] i,j (1<=i<=M & 1<=j<=N) -> (tab(i,j) = trans(j,i))}
ou intuitivement : "les lignes de 'tab' sont les colonnes de 'trans'"
ou bien "les colonnes de 'tab' sont les lignes de 'trans'"
Transposé du tableau de l'exemple :
[[1,10,24] , [6,16,13] , [21,3,8] , [14,11,25]]
Question 2 : Donner le programme Prolog de la construction du transposé d'un tableau 'tableau' donné sous la forme de la liste de ses lignes
Exemple d'exécution :
tab([[1,6,21,14] , [10,16,3,11] , [24,13,8,25]]).
?- tab(TAB) , transposé(TAB , TRA).
TAB = [[1,6,21,14],[10,16,3,11],[24,13,8,25]]
TRA = [[1,10,24],[6,16,13],[21,3,8],[14,11,25]]

3 - Hoare :
Un tableau rectangulaire 'Tab' de dimensions MxN (M lignes et N colonnes) peut aussi être représenté par un vecteur 'Vect' dont les éléments sont obtenus en mettant les lignes bout à bout. Alors un élément en I,J dans le tableau rectangulaire -Tab(I,J)- aura le rang R = (I-1)*N + J dans le vecteur : Vect(R)=Tab(I,J).
Pour passer de la représentation rectangulaire au vecteur on a écrit le programme suivant :
I := 1 ; J := 0 ; R := 0 ; NbrElem := M * N ;
while (R < NbrElem)
Invariant : {R = (I-1)*N +J & À COMPLETER.};
do
R := R+1 ;
if J < N then J := J+1 else (I := I+1 ; J := 1);
Vect(R) := Tab(I,J);
od
{[universal]x_i,x_j,x_r(1<=x_i<= M & 1<=x_j<= N & 1<=x_r <= M*N) ->
x_r= (x_i-1)*N+x_j& Tab(x_i, x_j) = Vect(x_r)}
Question 3.1 : Compléter l'invariant de boucle.
Indication informelle : les R premiers éléments de Vect sont les éléments des I-1 premières lignes de Tab mises bout à bout, suivies des J premiers éléments de la I-ème ligne.

Question 3.2 : Donner la preuve de la correction partielle de cette boucle.

4 - Java :
Dans Java 1.2 on a écrit la classe 'EnsembleOrdonne' suivante, qui étend la classe 'Ensemble' et implante l'interface 'SortedSet' :

class EnsembleOrdonne extends Ensemble implements SortedSet{
  protected Comparator       comp;
  public static final Comparator CROISSANT = new Comparator(){
    public int compare(Object o1, Object o2){
      if (o1 instanceof Comparable && o2 instanceof Comparable)
	return ((Comparable)o1).compareTo(o2);
      else
	throw new ClassCastException();
    }
  };
  public static final Comparator DECROISSANT = new Comparator(){
    public int compare(Object o1, Object o2){
      if (o1 instanceof Comparable && o2 instanceof Comparable)
	return -((Comparable)o1).compareTo(o2);
      else
	throw new ClassCastException();
    }
  };
  
  public EnsembleOrdonne(Comparator comp){
	super();
	this.comp = comp;
  }
...
// Définitions des méthodes de la classe 'EnsembleOrdonne'
...

}

Question 4.1 : Quelles sont les méthodes que doit implanter la classe 'EnsembleOrdonne' ?

Question 4.2 : Donner l'implantation, le code d'au moins 3 de ces méthodes.

Exemple d'utilisation :

class Entier implements Comparable{
  private int i;
  public Entier(int i){ this.i = i;}
  public int compareTo(Object o){ 
    if (o instanceof Entier)
      if (i < ((Entier)o).intValue()) return -1;
      else if (i == ((Entier)o).intValue()) return 0;
      else return 1;
    else
      throw new ClassCastException();
  }
  public boolean equals(Object o){
    return this.compareTo(o) == 0;
  }
  public int intValue(){ return i;}
  public String toString(){ return "" + i;}
}


public class TestCollection {
    public static void TestEnsembleOrdonne(){
      EnsembleOrdonne e  = new EnsembleOrdonne(EnsembleOrdonne.CROISSANT);
      EnsembleOrdonne e1 = new EnsembleOrdonne(EnsembleOrdonne.DECROISSANT);
      e.add(new Entier(8)); 
     for(int i=1; i< 10; i++){
	e.add(new Entier(i)); 
	e1.add(new Entier(i+5));
      }
      System.out.println(" e = " + e + " e1 = " + e1);
      System.out.println(" e.headSet(3) = " + e.headSet(new Entier(3)));
      System.out.println(" e.headSet(8) = " + e.headSet(new Entier(8)));
      System.out.println(" e.subSet(3,8) = " + 
				e.subSet(new Entier(3),new Entier(8)));
      
      System.out.println(" e.tailSet(5) = " + e.tailSet(new Entier(5)));
    }
    
    public static void main(String args[]) {
      TestEnsembleOrdonne();
    }
}
`
class UnsupportedOperationException extends RuntimeException{}

class Ensemble extends AbstractSet implements Set{
  protected java.util.Vector table = new java.util.Vector();
  public int size(){ return table.size();}
  public Iterator iterator(){
    class EnsembleIterator implements Iterator{
      private Object courant;
      private java.util.Enumeration e = table.elements();
      public boolean hasNext(){return e.hasMoreElements();}
      public Object next(){courant = e.nextElement(); return courant;}
      public void remove(){}
	table.removeElement(courant);
      }
    }
    return new EnsembleIterator();
  }
  public boolean add(Object o){
    if (!this.contains(o)){
       table.addElement(o);
       return true;
    }else{ 
      return false;
    }
  }
}


interface SortedSet extends Set {
    Comparator comparator();
    SortedSet subSet(Object fromElement, Object toElement);
    SortedSet headSet(Object toElement);
    SortedSet tailSet(Object fromElement);
    Object first();
    Object last();
}

interface Comparable {public int compareTo(Object o);}
interface Comparator{public int compare(Object o1, Object o2);}
interface Iterator {
    boolean hasNext();
    Object next();
    void remove();
}

interface Collection {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator iterator();
    Object[] toArray();
    Object[] toArray(Object a[]);
    boolean add(Object o);
    boolean remove(Object o);
    boolean containsAll(Collection c);
    boolean addAll(Collection c);
    boolean removeAll(Collection c);
    boolean retainAll(Collection c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

abstract class AbstractCollection implements Collection {
    protected AbstractCollection() {}
    public abstract Iterator iterator();
    public abstract int size();
    public boolean isEmpty() {return size() == 0;}
    public boolean contains(Object o) {
	Iterator e = iterator();
	if (o==null) {
	    while (e.hasNext())
		if (e.next()==null) return true;
	} else {
	    while (e.hasNext())
		if (o.equals(e.next())) return true;
	}
	return false;
    }
    public Object[] toArray() {
	Object[] result = new Object[size()];
	Iterator e = iterator();
	for (int i=0; e.hasNext(); i++)
	    result[i] = e.next();
	return result;
    }
    public Object[] toArray(Object a[]) {
        int size = size();
        if (a.length < size)
            a = (Object[])java.lang.reflect.Array.newInstance(
                                  a.getClass().getComponentType(), size);
        Iterator it=iterator();
        for (int i=0; i<size; i++)
            a[i] = it.next();
        if (a.length > size)
            a[size] = null;
        return a;
    }
    public boolean add(Object o) {throw new UnsupportedOperationException();}
    public boolean remove(Object o) {
	Iterator e = iterator();
	if (o==null) {
	    while (e.hasNext()) {
		if (e.next()==null) {
		    e.remove();
		    return true;
		}
	    }
	} else {
	    while (e.hasNext()) {
		if (o.equals(e.next())) {
		    e.remove();
		    return true;
		}
	    }
	}
	return false;
    }
    public boolean containsAll(Collection c) {
	Iterator e = c.iterator();
	while (e.hasNext())
	    if(!contains(e.next())) return false;
	return true;
    }
    
    public boolean addAll(Collection c) {
	boolean modified = false;
	Iterator e = c.iterator();
	while (e.hasNext()) {
	    if(add(e.next())) modified = true;
	}
	return modified;
    }

     public boolean removeAll(Collection c) {
	boolean modified = false;
	Iterator e = iterator();
	while (e.hasNext()) {
	    if(c.contains(e.next())) {
		e.remove();
		modified = true;
	    }
	}
	return modified;
    }
    public boolean retainAll(Collection c) {
	boolean modified = false;
	Iterator e = iterator();
	while (e.hasNext()) {
	    if(!c.contains(e.next())) {
		e.remove();
		modified = true;
	    }
	}
	return modified;
    }
    public void clear() {
	Iterator e = iterator();
	while (e.hasNext()) {
	    e.next();
	    e.remove();
	}
    }
    public String toString() {
	StringBuffer buf = new StringBuffer();
	Iterator e = iterator();
	buf.append("[");
	int maxIndex = size() - 1;
	for (int i = 0; i <= maxIndex; i++) {
	    buf.append(String.valueOf(e.next()));
	    if (i < maxIndex) buf.append(", ");
	}
	buf.append("]");
	return buf.toString();
    }
}


interface Set extends Collection {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator iterator();
    Object[] toArray();
    Object[] toArray(Object a[]);
    boolean add(Object o);
    boolean remove(Object o);
    boolean containsAll(Collection c);
    boolean addAll(Collection c);
    boolean retainAll(Collection c);
    boolean removeAll(Collection c);
    void clear();
    boolean equals(Object o);
    int hashCode();
}

abstract class AbstractSet extends AbstractCollection implements Set {
    protected AbstractSet() {
    }
    public boolean equals(Object o) {
	if (o == this)
	    return true;
	if (!(o instanceof Set))
	    return false;
	Collection c = (Collection) o;
	if (c.size() != size())
	    return false;
	return containsAll(c);
    }
    public int hashCode() {
	int h = 0;
	Iterator i = iterator();
	while (i.hasNext()) {
	    Object obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
	return h;
    }
}

/* *** fin *** */


/* une idée...