Synthèse

1. Abstraction, ADT et implémentation

1.1 Type abstrait de données

Un Abstract Data Type (ADT) décrit les données manipulées, les opérations autorisées et leur comportement, sans imposer leur représentation interne.

Le bon réflexe est : besoin → opérations → ADT → implémentation.

Une Stack est par exemple définie par son comportement LIFO et par les opérations autorisées : push, pop, peek et isEmpty. La représentation interne reste libre : elle peut ensuite être implémentée avec une liste chaînée ou un tableau dynamique.

En Java, une interface représente bien cette idée de contrat : elle expose les opérations de l’ADT sans donner leur implémentation.

interface Stack<E> {
    void push(E item);
    E pop();
    E peek();
    boolean isEmpty();
}

Une classe concrète choisit ensuite la représentation et implémente ce contrat :

class LinkedStack<E> implements Stack<E> {
    // représentation interne + implémentation des opérations
}

1.2 ADT vs structure de données

L’ADT répond à « que doit faire la structure ? ». L’implémentation répond à « comment le faire ? ».

Deux implémentations d’un même ADT peuvent donc offrir des complexités différentes. En algorithmique, on identifie d’abord les opérations nécessaires, puis on choisit la structure adaptée.

Stack<Integer> s1 = /* linked-list stack */;
Stack<Integer> s2 = /* array-based stack */;

1.3 Références et aliasing en Java

Pour un type primitif, une affectation copie la valeur. Pour un objet ou un tableau, elle copie la référence.

int[] a = {1, 2, 3};
int[] b = a;

b[0] = 99;
// a[0] vaut aussi 99

Java passe toujours les arguments par valeur. Pour un objet, la valeur copiée est sa référence : une méthode peut modifier l’objet partagé, mais réassigner son paramètre ne réassigne pas la variable de l’appelant.

static void mutate(int[] a) {
    a[0] = 42;
}

static void replace(int[] a) {
    a = new int[3];
}

2. Structures linéaires et itérateurs

2.1 Stack — LIFO

Une pile suit Last In, First Out.

Avec une liste simplement chaînée, placer le top en tête permet push et pop en temps constant : seules quelques références changent.

class Node<E> {
    E item;
    Node<E> next;
}

node.next = first;
first = node;

Placer le top en fin d’une singly linked list est moins intéressant : sans lien vers le prédécesseur, retirer le dernier élément impose un parcours en $\Theta(n)$.

2.2 Queue — FIFO

Une file suit First In, First Out : on ajoute en fin et on retire en tête.

Queue<Integer> q = new ArrayDeque<>();

q.add(1);
q.add(2);

int first = q.remove(); // 1

2.3 Stack avec deux queues

On peut maintenir l’invariant suivant :

• queue1 contient toute la stack, avec le top en tête ;
• queue2 reste vide entre deux opérations.

Dans cette version, pop() et peek() sont en $\Theta(1)$, tandis que push() coûte $\Theta(n)$.

public void push(E item) {
    queue2.add(item);

    while (!queue1.isEmpty()) {
        queue2.add(queue1.remove());
    }

    Queue<E> tmp = queue1;
    queue1 = queue2;
    queue2 = tmp;
}

2.4 Parcours d’une LinkedList

Un Iterator avance directement de nœud en nœud : parcourir $n$ éléments coûte $\Theta(n)$.

En revanche, appeler get(i) à chaque tour sur une LinkedList peut mener à $\Theta(n^2)$, car chaque accès par indice peut provoquer un nouveau parcours.

for (Integer x : list) {
    process(x);
}

À éviter sur une LinkedList :

for (int i = 0; i < list.size(); i++) {
    process(list.get(i));
}

2.5 Itérateurs fail-fast

Un itérateur fail-fast détecte qu’une structure a été modifiée après sa création et lève typiquement ConcurrentModificationException.

private final long expectedOps = nOp;

public E next() {
    if (expectedOps != nOp) {
        throw new ConcurrentModificationException();
    }

    // ...
}

3. Complexité et performances

3.1 $O$, $\Omega$, $\Theta$ et $\sim$

• $O(f(n))$ : borne asymptotique supérieure ;
• $\Omega(f(n))$ : borne asymptotique inférieure ;
• $\Theta(f(n))$ : même ordre de croissance ;
• $g(n)\sim f(n)$ : $g(n)/f(n)\to 1$.

Exemple :

$$5n^2 + 2n = \Theta(n^2)$$

mais

$$5n^2 + 2n \sim 5n^2$$

3.2 Complexité amortie

Un tableau dynamique peut avoir un push en $\Theta(n)$ lors d’un redimensionnement. Si la capacité double à chaque fois, les copies successives forment une somme géométrique.

Sur $n$ insertions, le coût total reste $\Theta(n)$, donc le coût amorti d’une insertion est $\Theta(1)$.

if (size == a.length) {
    a = Arrays.copyOf(a, 2 * a.length);
}

a[size++] = item;

3.3 Doubling ratio test

On mesure $T(n)$, puis $T(2n)$, et on regarde :

$$\frac{T(2n)}{T(n)}$$

Si $T(n)\sim an^b$, le ratio tend vers $2^b$.

• ratio $\approx 2$ → linéaire ;
• ratio $\approx 4$ → quadratique ;
• ratio $\approx 8$ → cubique.

long start = System.nanoTime();
run(input);
long elapsed = System.nanoTime() - start;

3.4 Heap, stack et JVM

Pendant l’exécution :

• la stack mémoire contient notamment les frames d’appels, paramètres et variables locales ;
• le heap contient principalement les objets et tableaux alloués.

-Xms fixe la taille initiale du heap JVM et -Xmx sa taille maximale. Le garbage collector récupère les objets qui ne sont plus accessibles.

Object x = new Object();
x = null;

4. Correction, tests et cas limites

4.1 Tests d’une structure de données

Il faut tester le cas nominal, mais surtout les cas limites : structure vide, un élément, plusieurs éléments, ordre des opérations, exceptions attendues et maintien des invariants.

assertTrue(stack.empty());

stack.push(1);
assertEquals(1, stack.peek());
assertEquals(1, stack.pop());

assertThrows(EmptyStackException.class, stack::pop);

4.2 Overflow et arithmétique Java

Une formule mathématiquement correcte peut être incorrecte en Java à cause de la représentation finie des entiers.

public static int average(int a, int b) {
    return (a + b) / 2;
}

a + b peut overflow avant la division. La division entière Java tronque aussi vers zéro.

System.out.println(-1 / 2); // 0

4.3 Random testing et reproductibilité

Les tests aléatoires permettent d’explorer beaucoup de séquences d’opérations. Une seed fixe rend un échec reproductible.

Random random = new Random(42);

La couverture de code aide à repérer les parties jamais exécutées, mais une couverture élevée ne prouve pas la correction.

5. Sorting

5.1 Principes

À compléter avec les prochains CM/TP : ordre, comparateurs, stabilité, invariants et coût des tris.

5.2 Algorithmes

À compléter : tris élémentaires, mergesort, quicksort, heapsort et comparaison de leurs complexités.

6. Searching et tables de symboles

6.1 Recherche

À compléter : recherche séquentielle, recherche dichotomique et choix de structure selon les opérations nécessaires.

6.2 Symbol tables et hashing

À compléter : tables de symboles, hashing, collisions et compromis temps/mémoire.

7. Arbres et structures hiérarchiques

7.1 Arbres de recherche

À compléter : BST, invariants, recherche, insertion et suppression.

7.2 Arbres équilibrés et heaps

À compléter : structures équilibrées, priority queues et heaps lorsque ces notions apparaîtront dans le cours.

8. Graphes et chaînes

8.1 Graphes

À compléter : représentations, parcours, connexité et principaux algorithmes de graphes.

8.2 Strings

À compléter : traitement de chaînes, recherche de motifs et structures spécialisées.