Practical activity

Présentation & objectifs

Voici une liste d’exercices pour étudier la complexité d’un algorithme, construire des algorithmes en se concentrant sur les arbres binaires de recherche et les algorithmes randomisés.

Contenu de l’activité

1 — Complexité des opérations sur les listes

Dans cet exercice, vous allez essayer de comprendre l’utilisation, en termes de complexité, des opérations sur les listes (classiques) et les listes triées.

1.1 — Évaluer la complexité

Voici quelques opérations sur ces structures, avec quelques implémentations possibles (pas nécessairement optimales) :

1. Opérations sur listes classiques – Les fonctions suivantes manipulent une liste classique :

   ​

   Python Java

   def create_list ():  
     
       """  
           Create an empty list.  
           In:  
               * None.  
           Out:  
               * An empty list.  
       """  
     
       return []  
     
     
     
   def insert_list (l: list[int], element: int) -> None:  
     
       """  
           Insert an element at the end of the list  
           In:  
               * l:       The list.  
               * element: The element to insert.  
           Out:  
               * None.  
       """  
     
       l.append(element)  
     
     
     
   def delete_list (l: list[int], element: int) -> None:  
     
       """  
           Delete the first occurrence of the element from the list.  
           In:  
               * l:       The list.  
               * element: The element to delete.  
           Out:  
               * None  
       """  
     
        # Find the element to delete  
       for i in range(len(l)):  
           if l[i] == element:  
     
               # Shift elements to the left  
               for j in range(i, len(l) - 1):  
                   l[j] = l[j + 1]  
     
               # Remove the last element  
               l.pop()  
               break  
     
     
     
   def find_min_list (l: list[int]) -> int | None:  
     
       """  
           Find and return the minimum element in the list.  
           In:  
               * l: The list.  
           Out:  
               * The minimum element in the list.  
       """  
     
       # Check that not empty  
       if not l:  
           return None  
     
       # Initialize the minimum value to the first element  
       min_value = l[0]  
     
       # Find the minimum value in the list  
       for value in l:  
           if value < min_value:  
               min_value = value  
     
       # Return the minimum value  
       return min_value  
     
     
     
     
     
   # Test the functions  
   print("Testing regular list operations:")  
   a_list = create_list()  
   insert_list(a_list, 10)  
   insert_list(a_list, 5)  
   insert_list(a_list, 20)  
   print("list after inserts:", a_list)  
   delete_list(a_list, 5)  
   print("list after deleting 5:", a_list)  
   print("Minimum element in the list:", find_min_list(a_list))  

    import java.util.Arrays;  
     
    /**  
    * Regular list Operations  
    */  
    public class RegularlistOperations {  
     
        /**  
        * Create an empty list  
        * @return An empty list  
        */  
        public static int[] createlist() {  
            return new int[0];  
        }  
     
        /**  
        * Insert an element at the end of the list  
        * @param list The list  
        * @param element The element to insert  
        */  
        public static int[] insertlist(int[] list, int element) {  
            // lists are immutable in Java, so we need to create a new list  
            int[] newlist = Arrays.copyOf(list, list.length + 1);  
            // insert the element at the end of the new list  
            newlist[list.length] = element;  
            // return the new list  
            return newlist;  
        }  
     
        /**  
        * Delete the first occurrence of the element from the list  
        * @param list The list  
        * @param element The element to delete  
        */  
        public static int[] deletelist(int[] list, int element) {  
            for (int i = 0; i < list.length; i++) {  
                // find the element to delete  
                if (list[i] == element) {  
                    // create a new list without the element to delete  
                    int[] newlist = new int[list.length - 1];  
                    // copy the elements before the element to delete  
                    System.arraycopy(list, 0, newlist, 0, i);  
                    // copy the elements after the element to delete  
                    System.arraycopy(list, i + 1, newlist, i, list.length - i - 1);  
                    // return the new list  
                    return newlist;  
                }  
            }  
            // return the original list if the element is not found  
            return list;  
        }  
     
        /**  
        * Find and return the minimum element in the list  
        * @param list The list  
        * @return The minimum element in the list  
        */  
        public static Integer findMinlist(int[] list) {  
            // check if the list is empty  
            if (list.length == 0) {  
                return null;  
            }  
            // initialize the minimum value to the first element  
            int minValue = list[0];  
            // find the minimum value in the list  
            for (int value : list) {  
                // check if the current value is less than the minimum value  
                if (value < minValue) {  
                    // update the minimum value  
                    minValue = value;  
                }  
            }  
            // return the minimum value  
            return minValue;  
        }  
     
        public static void main(String[] args) {  
            System.out.println("Testing Regular list Operations:");  
            int[] list = createlist();  
            list = insertlist(list, 10);  
            list = insertlist(list, 5);  
            list = insertlist(list, 20);  
            System.out.println("list after inserts: " + Arrays.toString(list));  
            list = deletelist(list, 5);  
            System.out.println("list after deleting 5: " + Arrays.toString(list));  
            System.out.println("Minimum element in the list: " + findMinlist(list));  
        }  
    }  

2. Opérations sur listes triées – La fonction suivante manipule une liste triée :

   ​

   Python Java

   def create_sorted_list ():  
     
       """  
           Create an empty list .  
           In:  
               * None.  
           Out:  
               * An empty list.  
       """  
     
       return []  
     
     
     
   def insert_sorted_list (l: list[int], element: int) -> None:  
     
       """  
           Insert an element into the sorted list while maintaining the list's order.  
           In:  
               * l:       The sorted list.  
               * element: The element to insert.  
           Out:  
               * None  
       """  
     
       # Find the correct position for the new element  
       index = 0  
       while index < len(l) and l[index] < element:  
           index += 1  
     
       # Shift elements to make space for the new element  
       l.append(0)  
       for i in range(len(l) - 1, index, -1):  
           l[i] = l[i - 1]  
     
       # Insert the new element at the correct position  
       l[index] = element  
     
     
     
   def delete_sorted_list (l: list[int], element: int) -> None:  
     
       """  
           Delete the first occurrence of the element from the sorted list.  
           In:  
               * l:       The sorted list.  
               * element: The element to delete.  
           Out:  
               * None  
       """  
     
       # Find the element to delete  
       for i in range(len(l)):  
           if l[i] == element:  
     
               # Shift elements to the left  
               for j in range(i, len(l) - 1):  
                   l[j] = l[j + 1]  
     
               # Remove the last element  
               l.pop()  
               break  
     
     
     
   def find_min_sorted_list (l: list[int]) -> int | None:  
     
       """  
           Find and return the minimum element in the sorted list.  
           In:  
               * l: The sorted list.  
           Out:  
               * The minimum element in the list.  
       """  
     
       # Check that not empty  
       if not l:  
           return None  
     
       # The minimum element is the first element in the sorted list  
       return l[0]  
   
   
   
   # Test sorted list operations  
   print("\nTesting Sorted list Operations:")  
   sorted_list = create_sorted_list()  
   insert_sorted_list(sorted_list, 10)  
   insert_sorted_list(sorted_list, 5)  
   insert_sorted_list(sorted_list, 20)  
   print("Sorted list after inserts:", sorted_list)  
   delete_sorted_list(sorted_list, 5)  
   print("Sorted list after deleting 5:", sorted_list)  
   print("Minimum element in the sorted list:", find_min_sorted_list(sorted_list))  

    import java.util.Arrays;  
     
    /**  
    * Sorted list operations.  
    */  
    public class SortedlistOperations {  
     
        /**  
        * Creates an empty sorted list.  
        *  
        * @return an empty integer list.  
        */  
        public static int[] createSortedlist() {  
            return new int[0];  
        }  
     
        /**  
        * Inserts an element into the sorted list while maintaining the sorted order.  
        *  
        * @param list the original sorted list.  
        * @param element the element to be inserted.  
        * @return a new sorted list with the element inserted.  
        */  
        public static int[] insertSortedlist(int[] list, int element) {  
            int index = 0;  
            // Find the correct position for the new element  
            while (index < list.length && list[index] < element) {  
                index++;  
            }  
            // In java, lists are immutable, so we need to create a new list with the element inserted  
            int[] newlist = new int[list.length + 1];  
            // Copy the elements before the index  
            System.arraycopy(list, 0, newlist, 0, index);  
            // Copy the elements after the index  
            System.arraycopy(list, index, newlist, index + 1, list.length - index);  
            // Insert the element at the correct position  
            newlist[index] = element;  
            // Return the new sorted list  
            return newlist;  
        }  
     
        /**  
        * Deletes an element from the sorted list.  
        *  
        * @param list the original sorted list.  
        * @param element the element to be deleted.  
        * @return a new sorted list with the element removed, or the original list if the element is not found.  
        */  
        public static int[] deleteSortedlist(int[] list, int element) {  
            for (int i = 0; i < list.length; i++) {  
                // Find the element to delete  
                if (list[i] == element) {  
                    // Create a new list without the element to delete  
                    int[] newlist = new int[list.length - 1];  
                    // Copy the elements before the index  
                    System.arraycopy(list, 0, newlist, 0, i);  
                    // Copy the elements after the index  
                    System.arraycopy(list, i + 1, newlist, i, list.length - i - 1);  
                    // Return the new sorted list  
                    return newlist;  
                }  
            }  
            // Return the original list if the element is not found  
            return list;  
        }  
     
        /**  
        * Finds the minimum element in the sorted list.  
        *  
        * @param list the sorted list.  
        * @return the minimum element in the list, or null if the list is empty.  
        */  
        public static Integer findMinSortedlist(int[] list) {  
            // Check if the list is empty  
            if (list.length == 0) {  
                return null;  
            }  
            // The minimum element is the first element in the sorted list  
            return list[0];  
        }  
     
        /**  
        * Main method to test the sorted list operations.  
        *  
        * @param args command line arguments.  
        */  
        public static void main(String[] args) {  
            System.out.println("\nTesting Sorted list Operations:");  
            int[] sortedlist = createSortedlist();  
            sortedlist = insertSortedlist(sortedlist, 10);  
            sortedlist = insertSortedlist(sortedlist, 5);  
            sortedlist = insertSortedlist(sortedlist, 20);  
            System.out.println("Sorted list after inserts: " + Arrays.toString(sortedlist));  
            sortedlist = deleteSortedlist(sortedlist, 5);  
            System.out.println("Sorted list after deleting 5: " + Arrays.toString(sortedlist));  
            System.out.println("Minimum element in the sorted list: " + findMinSortedlist(sortedlist));  
        }  
    }  

Quelles sont les complexités temporelles (au pire cas) des différentes opérations ?
Comment la complexité temporelle dans une liste triée se compare-t-elle à celle d’une liste classique ?

1.2 — Écrivez vos propres fonctions

Maintenant, pour chacune des listes ci-dessus, écrivez une fonction qui, pour chaque élément de la liste, compte le nombre d’autres éléments plus grands ou égaux dans la liste.
La fonction doit retourner un dictionnaire qui, pour chaque élément, associe son résultat.

Comme votre fonction doit pouvoir comparer les éléments, un assert pourrait être intéressant à utiliser.
Nous supposons également que la liste ne doit contenir que des valeurs distinctes.

Quelles sont les complexités de ces fonctions ?

def count_greater (l: list[int|float]) -> dict[int|float, int]:  
  
    """  
        For each element, counts the number of other greater or equal elements in the list.  
        In:  
            * l: List to study.  
        Out:  
            * A dictionary of counts.  
    """  
  
    # Asserts  
    assert all([type(e) in [int, float] for e in l]), "l contains non-numeric elements."  
    assert len(set(l)) == len(l), "l contains duplicates."  
  
    # Fill a dictionary for each element  
    result = {}  
    for e in l:  
        result[e] = 0  
  
        # Count greater or equal elements  
        for f in l:  
            if f >= e:  
                result[e] += 1  
  
    return result  

def count_greater_sorted (l: list[int|float]) -> dict[int|float, int]:  
  
    """  
        For each element, counts the number of other greater or equal elements in the sorted list.  
        In:  
            * l: List to study.  
        Out:  
            * A dictionary of counts.  
    """  
  
    # Asserts  
    assert all([type(e) in [int, float] for e in l]), "l contains non-numeric elements."  
    assert len(set(l)) == len(l), "l contains duplicates."  
  
    # Fill a dictionary for each element  
    n = len(l)  
    result = {}  
    for i, e in enumerate(l):  
        result[e] = n - i  
  
    return result  

2 — Nombre premier

Un nombre premier est un nombre strictement positif qui n’est divisible (au sens de la division entière) que par 1 et lui-même (par exemple : 2, 3, 5, 7, 11, etc.).
Nous voulons déterminer si un entier est un nombre premier.
La méthode basique consiste à prouver que le nombre à traiter n’est pas premier en cherchant un diviseur qui donne un reste égal à 0.
Si un tel diviseur est trouvé, le nombre n’est pas premier.

Dans un fichier nommé prime.py, écrivez plusieurs fonctions pour tester si un nombre donné est premier.

1. Fonction complete_check_prime (number: int) -> Tuple[bool, int] – Utilisez la boucle for pour tester tous les diviseurs de 2 à (number - 1).
   La fonction retournera si le nombre est premier ou non.
   Elle retournera également le nombre d’itérations effectuées pour obtenir le résultat.
   Indiquez ensuite sa complexité algorithmique.

2. Fonction lless_dividers_prime (number: int, limit: int) -> Tuple[bool, int] – La première façon de faire est de traiter séparément le cas des nombres pairs.
   Si le nombre est divisible par 2, il n’est pas intéressant de vérifier les diviseurs pairs.
   La recherche doit être restreinte aux diviseurs impairs (3, 5, 7, etc.).
   La deuxième approche consiste à travailler sur des nombres ayant plusieurs diviseurs, comme 24, pour mettre en évidence une propriété des diviseurs qui limite la plage de recherche, comme la racine carrée d’un nombre.

   Écrivez la fonction qui implémente cette méthode dans prime_bis.py.
   Le programme retournera si le nombre est premier ou non.
   Il retournera également le nombre d’itérations effectuées pour obtenir le résultat.
   La boucle for peut être remplacée par une boucle while, plus adaptée à ce type de traitement.

   L’argument limit peut être égal au nombre, ou à sa racine carrée.
   Indiquez la complexité algorithmique pour chaque cas.

   Notez le nombre d’itérations retourné lorsque vous le testez sur des nombres premiers et non premiers pairs et impairs.

   Si vous souhaitez évaluer la performance de votre algorithme, vous pouvez le tester avec un nombre premier plus grand, comme 10007 ou 1e9+7
   qui est, soit dit en passant, le plus grand nombre premier stocké dans un entier 32 bits.

def complete_check_prime (number:int) -> Tuple[bool, int]:  
    """  
        Check if a number is prime by testing all divisors from 2 to (number - 1).  
        In:  
            * number: The number to check.  
        Out:  
            * A couple indicating if the number is prime or not and the number of iterations.  
    """  
    # worst case: iterate from 2 to number - 1  
    iterations = number - 2  
    # set is_prime to True by default  
    is_prime = True  
    for i in range(2, number):  
        if number % i == 0:  
            # if a divisor is found, the number is not prime  
            # store the number of iterations  
            iterations = i  
            # set is_prime to False and break the loop  
            is_prime = False  
            break  
    # return the result and the number of iterations  
    return (is_prime, iterations)  
  
  
# Test the functions  
number = 17  
is_prime, iterations = complete_check_prime(number)  
print(f"Is {number} a prime number? {is_prime}")  
print(f"Number of iterations: {iterations}")  

public class Prime {  
  
    /**  
     * Check if a number is prime by testing all divisors from 2 to (number - 1)  
     * @param number the number to check  
     * @return a couple indicating if the number is prime or not and the number of iterations  
     */  
    public static Object[] completeCheckPrime(int number) {  
        for (int i = 2; i < number; i++) {  
            if (number % i == 0) {  
                return new Object[] {false, i};  
            }  
        }  
        return new Object[] {true, number - 2};  
    }  
  
    public static void main(String[] args) {  
        int number = 17;  
        Object[] result = completeCheckPrime(number);  
        System.out.println("Is " + number + " a prime number? "+ result[0]);  
        System.out.println("Number of iterations: " + result[1]);  
    }  
}  

def less_dividers_prime (number: int, limit: int) -> Tuple[bool, int]:  
  
    """  
        Check if a number is prime by testing divisors up to the limit.  
        In:  
            * number: The number to check.  
            * limit:  The limit to test divisors up to.  
        Out:  
            * a couple indicating if the number is prime or not and the number of iterations.  
    """  
    # If the number is even, it is not prime  
    if number % 2 == 0:  
        return False, 0  
    i = 3  
    # worst case: iterate from 3 to limit  
    while i < limit:  
        if number % i == 0:  
            # if a divisor is found, the number is not prime  
            return False, i // 2  
        i += 2 # only check odd numbers  
    # if no divisor is found, the number is prime  
    return True, i // 2 -1  
  
  
  
# Test the functions  
number = 17  
is_prime, iterations = less_dividers_prime(number, number)  
print(f"Is {number} a prime number? {is_prime}")  
print(f"Number of iterations: {iterations}")  
is_prime, iterations = less_dividers_prime(number, int(number ** 0.5) + 1)  
print(f"Is {number} a prime number? {is_prime}")  
print(f"Number of iterations: {iterations}")  

import java.lang.Math;  
  
public class PrimeBis {  
  
    /**  
     * Check if a number is prime by testing divisors up to the limit  
     * @param number the number to check  
     * @param limit the limit to test divisors up to  
     * @return a couple indicating if the number is prime or not and the number of iterations  
     */  
    public static Object[] lessDividersPrime(int number, int limit) {  
        if (number % 2 == 0) {  
            return new Object[] {false, 0};  
        }  
        int i = 3;  
        while (i < limit) {  
            if (number % i == 0) {  
                return new Object[] {false, i / 2};  
            }  
            i += 2;  
        }  
        return new Object[] {true, i / 2 - 1};  
    }  
  
    public static void main(String[] args) {  
        int number = 17;  
        int limit = number;  
        Object[] result = lessDividersPrime(number, limit);  
        System.out.println("Is " + number + " a prime number? "+ result[0]);  
        System.out.println("Number of iterations: " + result[1]);  
        limit = (int) Math.sqrt(number) + 1;  
        result = lessDividersPrime(number, limit);  
        System.out.println("Is " + number + " a prime number? "+ result[0]);  
        System.out.println("Number of iterations: " + result[1]);  
    }  
}  

3 — Arbre binaire de recherche

Un arbre binaire de recherche (BST) est un arbre binaire dans lequel chaque nœud a une clé, et pour tout nœud x, la clé dans le sous-arbre gauche de x est inférieure à la clé dans x, et la clé dans le sous-arbre droit de x est supérieure à la clé dans x (voir le cours relatif aux BST pour plus de détails).

Nous allons implémenter un arbre binaire de recherche en Python à partir de zéro.
Nous fournirons les fonctions suivantes :

• tree_insert(tree: , value) pour insérer la valeur dans l’arbre.
• tree_search(tree, value) pour rechercher la valeur dans l’arbre.
• tree_delete(tree, value) pour supprimer la valeur de l’arbre.

3.1 — Insertion

L’algorithme d’insertion est le suivant :

1. Si l’arbre est vide, créez un nouveau nœud avec la valeur donnée et retournez l’arbre.
2. Si la valeur est inférieure à la valeur de la racine, insérez la valeur dans le sous-arbre gauche et retournez l’arbre.
3. Si la valeur est supérieure à la valeur de la racine, insérez la valeur dans le sous-arbre droit et retournez l’arbre.
4. Si la valeur est égale à la valeur de la racine, retournez l’arbre (inchangé).

Puis retournez la racine de l’arbre.
Notez que l’algorithme est récursif.

Créez un fichier nommé binary_tree.py et implémentez la fonction tree_insert(tree, value).

def tree_insert (tree, value):  
  
    """  
        Insert a value into the binary search tree.  
        In:  
            * tree:  The binary search tree.  
            * value: The value to insert.  
        Out:  
            * The root of the binary search tree.  
    """  
  
    # Base case: create a new node if the tree is empty  
    if tree is None:  
        return [value, None, None]  
  
    # Insert the value in the left subtree if it is less than the root value  
    if value < tree[0]:  
        tree[1] = tree_insert(tree[1], value)  
  
    # Insert the value in the right subtree if it is greater than the root value  
    elif value > tree[0]:  
        tree[2] = tree_insert(tree[2], value)  
  
    # Do nothing if the value is equal to the root value  
    # Return the root of the tree  
    return tree  
  
  
  
# Test the function  
tree = None  
values = [10, 5, 7, 4, 9]  
for value in values:  
    tree = tree_insert(tree, value)  
    print(tree)  

public class BinaryTree {  
  
    /**  
     * Insert a value into the binary search tree  
     * @param tree the binary search tree  
     * @param value the value to insert  
     * @return the root of the binary search tree  
     */  
    public static int[] treeInsert(int[] tree, int value) {  
        // Base case: create a new node if the tree is empty  
        if (tree == null) {  
            return new int[] {value, 0, 0};  
        }  
        // Insert the value in the left subtree if it is less than the root value  
        if (value < tree[0]) {  
            tree[1] = treeInsert(tree[1], value);  
        }  
        // Insert the value in the right subtree if it is greater than the root value  
        else if (value > tree[0]) {  
            tree[2] = treeInsert(tree[2], value);  
        }  
        // Do nothing if the value is equal to the root value  
        // Return the root of the tree  
        return tree;  
    }  
  
    public static void main(String[] args) {  
        int[] tree = null;  
        int[] values = {10, 5, 7, 4, 9};  
        for (int value : values) {  
            tree = treeInsert(tree, value);  
            System.out.println(lists.toString(tree));  
        }  
    }  
}  

3.2 — Recherche

L’algorithme de recherche est le suivant :

1. Si l’arbre est vide, retournez False.
2. Si la valeur est égale à la valeur de la racine, retournez True.
3. Si la valeur est inférieure à la valeur de la racine, recherchez dans le sous-arbre gauche.
4. Si la valeur est supérieure à la valeur de la racine, recherchez dans le sous-arbre droit.

L’algorithme est récursif.
Implémentez la fonction tree_search(tree, value) dans le fichier binary_tree.py.

def tree_search (tree, value):  
  
    """  
        Search for a value in the binary search tree.  
        In:  
            * tree:  The binary search tree.  
            * value: The value to search for.  
        Out:  
            * True if the value is found, False otherwise.  
    """  
  
    # Base case: return False if the tree is empty  
    if tree is None:  
        return False  
  
    # Return True if the value is equal to the root value  
    if value == tree[0]:  
        return True  
  
    # Search in the left subtree if the value is less than the root value  
    if value < tree[0]:  
        return tree_search(tree[1], value)  
  
    # Search in the right subtree if the value is greater than the root value  
    return tree_search(tree[2], value)  
  
  
  
# Test the function  
tree = None  
values = [10, 5, 7, 4, 9]  
for value in values:  
    tree = tree_insert(tree, value)  
print(tree_search(tree, 7))  # True  
print(tree_search(tree, 8))  # False  

/**  
 * Search for a value in the binary search tree  
 * @param tree the binary search tree  
 * @param value the value to search for  
 * @return true if the value is found, false otherwise  
 */  
public static boolean treeSearch(int[] tree, int value) {  
    // Base case: return false if the tree is empty  
    if (tree == null) {  
        return false;  
    }  
    // Return true if the value is equal to the root value  
    if (value == tree[0]) {  
        return true;  
    }  
    // Search in the left subtree if the value is less than the root value  
    if (value < tree[0]) {  
        return treeSearch(tree[1], value);  
    }  
    // Search in the right subtree if the value is greater than the root value  
    return treeSearch(tree[2], value);  
}  
  
// Replace the main method with the following code  
public static void main(String[] args) {  
    int[] tree = null;  
    int[] values = {10, 5, 7, 4, 9};  
    for (int value : values) {  
        tree = treeInsert(tree, value);  
    }  
  
    System.out.println(treeSearch(tree, 7));  // True  
    System.out.println(treeSearch(tree, 8));  // False  
}  

3.3 — Suppression

L’algorithme de suppression est plus complexe que ceux d’insertion et de recherche.

Le successeur en ordre d’un nœud dans un arbre binaire de recherche (BST) est le nœud avec la plus petite clé supérieure à la clé du nœud donné.

Nous considérerons trois cas :

1. Si le nœud à supprimer n’a pas d’enfants, on peut simplement le supprimer.
2. Si le nœud n’a qu’un seul enfant, on peut remplacer le nœud par son enfant.
3. Si le nœud a deux enfants, il faut trouver le successeur en ordre du nœud, remplacer le nœud par le successeur en ordre, supprimer le successeur en ordre, puis ajouter un nouveau lien entre les enfants du successeur en ordre et les parents du successeur en ordre.

Implémentez la fonction tree_delete(tree, value) dans le fichier binary_tree.py.

def tree_delete (tree, value):  
  
    """  
        Delete a value from the binary search tree.  
        In:  
            * tree:  The binary search tree.  
            * value: The value to delete.  
        Out:  
            * The root of the binary search tree.  
    """  
  
    # Base case: return None if the tree is empty  
    if tree is None:  
        return None  
  
    # Delete the value in the left subtree if it is less than the root value  
    if value < tree[0]:  
        tree[1] = tree_delete(tree[1], value)  
  
    # Delete the value in the right subtree if it is greater than the root value  
    elif value > tree[0]:  
        tree[2] = tree_delete(tree[2], value)  
  
    # Delete the root value if it is equal to the value  
    else:  
  
        # Case 1: the node has no children  
        if tree[1] is None and tree[2] is None:  
            return None  
  
        # Case 2: the node has only one child  
        if tree[1] is None:  
            return tree[2]  
        if tree[2] is None:  
            return tree[1]  
  
        # Case 3: the node has two children  
        # Find the inorder successor  
        successor = tree[2]  
        while successor[1] is not None:  
            successor = successor[1]  
  
        # Replace the root value with the inorder successor value  
        tree[0] = successor[0]  
  
        # Delete the inorder successor  
        tree[2] = tree_delete(tree[2], successor[0])  
  
    # Return the root of the tree  
    return tree  
  
  
  
# Test the function  
tree = None  
values = [10, 5, 7, 4, 9]  
for value in values:  
    tree = tree_insert(tree, value)  
    print(tree)  
for value in values:  
    tree = tree_delete(tree, value)  
    print(tree)  

/**  
 * Delete a value from the binary search tree  
 * @param tree the binary search tree  
 * @param value the value to delete  
 * @return the root of the binary search tree  
 */  
public static int[] treeDelete(int[] tree, int value) {  
    // Base case: return null if the tree is empty  
    if (tree == null) {  
        return null;  
    }  
    // Delete the value in the left subtree if it is less than the root value  
    if (value < tree[0]) {  
        tree[1] = treeDelete(tree[1], value);  
    }  
    // Delete the value in the right subtree if it is greater than the root value  
    else if (value > tree[0]) {  
        tree[2] = treeDelete(tree[2], value);  
    }  
    // Delete the root value if it is equal to the value  
    else {  
        // Case 1: the node has no children  
        if (tree[1] == null && tree[2] == null) {  
            return null;  
        }  
        // Case 2: the node has only one child  
        if (tree[1] == null) {  
            return tree[2];  
        }  
        if (tree[2] == null) {  
            return tree[1];  
        }  
        // Case 3: the node has two children  
        // Find the inorder successor  
        int[] successor = tree[2];  
        while (successor[1] != null) {  
            successor = successor[1];  
        }  
        // Replace the root value with the inorder successor value  
        tree[0] = successor[0];  
        // Delete the inorder successor  
        tree[2] = treeDelete(tree[2], successor[0]);  
    }  
    // Return the root of the tree  
    return tree;  
}  
  
// Replace the main method with the following code  
public static void main(String[] args) {  
    int[] tree = null;  
    int[] values = {10, 5, 7, 4, 9};  
    for (int value : values) {  
        tree = treeInsert(tree, value);  
    }  
  
    for (int value : values) {  
        tree = treeDelete(tree, value);  
    }  
}  

4 — Implémentation et test de la méthode congruentielle linéaire en Python

4.1 — Méthode congruentielle linéaire

Implémentez la méthode congruentielle linéaire (LCM) en Python pour générer une séquence de nombres pseudo-aléatoires.
La formule LCM est donnée par :
$$X_{n} = (aX_{n-1} + c) \mod m \;,$$
où :

• $X_{n-1}$ est le nombre aléatoire courant.
• $X_{n}$ est le nombre aléatoire suivant.
• $m$ est le module.
• $a$ est le multiplicateur.
• $c$ est l’incrément.

La fonction (appelée linear_congruential_generator) doit accepter les paramètres $m$, $a$, $c$, $X_0$, et $n$ (le nombre de nombres aléatoires à générer), et générer des séquences en utilisant deux ensembles de paramètres :

• Ensemble 1 : $m = 100, a = 17, X_0 = 27, c = 43$.
• Ensemble 2 : $a = 7^5, m = 2^{31}-1, X_0 = 27, c = 0$.

from numbers import Integral  
def linear_congruential_generator (m: Integral, a: Integral, c: Integral, x_0: Integral, n: Integral) -> list[Integral]:  
  
    sequence = [x_0]  
    for _ in range(1, n):  
        next_value = (a * sequence[-1] + c) % m  
        sequence.append(next_value)  
    return sequence  
  
m1, a1, X_01, c1 = 100, 17, 27, 43  
sequence1 = linear_congruential_generator(m1, a1, c1, X_01, 1000)  
  
m2, a2, X_02, c2 = 2**31 - 1, 7**5, 27, 0  
sequence2 = linear_congruential_generator(m2, a2, c2, X_02, 1000)  

Lors de la génération de nombres aléatoires, il est important de tester la qualité des nombres générés.
Nous pouvons tester l’uniformité des nombres générés en visualisant un histogramme et en calculant la moyenne et l’écart-type.

# Matplotlib library is required  
import matplotlib.pyplot as plt  
  
# First, normalize the sequence to be between 0 and 1  
normalized_sequence = [x / m for x in sequence]  
  
# Then, plot the histogram of the generated numbers  
plt.hist(normalized_sequence, bins=10, edgecolor='black')  
plt.title("Histogram of Generated Numbers")  
plt.xlabel("Value")  
plt.ylabel("Frequency")  
plt.show()  
  
# Calculate mean and standard deviation  
mean = np.mean(normalized_sequence)  
std_dev = np.std(normalized_sequence)  
print(f"Mean: {mean}, Standard Deviation: {std_dev}")  

4.2 — Test d’autocorrélation

Testez l’autocorrélation en mesurant la corrélation entre des nombres adjacents dans la séquence.
Pour ce faire, calculez le coefficient de corrélation entre la séquence et la séquence décalée d’une position.
La mesure la plus connue de la dépendance entre deux quantités est le coefficient de corrélation produit-moment de Pearson (PPMCC), ou “coefficient de corrélation de Pearson”.
Le PPMCC est une mesure de la corrélation linéaire entre deux variables $X$ et $Y$, donnant une valeur comprise entre +1 et −1 inclus, où 1 est une corrélation linéaire positive totale, 0 est aucune corrélation linéaire, et −1 est une corrélation linéaire négative totale.
Ici, $X$ est la séquence et $Y$ est la séquence décalée d’une position.

La formule du PPMCC est donnée par :

$$\begin{align*} r_{XY} &= \frac{\sum_{i=1}^{n}{(X_i - \bar{X})(Y_i - \bar{Y})}}{\sqrt{\sum_{i=1}^{n}{(X_i - \bar{X})^2}}\sqrt{\sum_{i=1}^{n}{(Y_i - \bar{Y})^2}}} \end{align*} \;,$$
où :

• $X_i$ et $Y_i$ sont les valeurs des séquences $X$ et $Y$ à la position $i$.
• $\bar{X}$ et $\bar{Y}$ sont les moyennes des séquences $X$ et $Y$.
• $n$ est la longueur des séquences.

Implémentez la fonction pearson_autocorrelation(x, y), exécutez-la sur les séquences générées, et affichez l’autocorrélation pour chaque séquence.
Qu’observez-vous ? Pouvez-vous affirmer que la séquence est aléatoire ?

def pearson_autocorrelation (x: list[Integral], y: list[Integral]) -> Integral:  
  
    """  
        Calculate the Pearson correlation coefficient between two sequences.  
        In:  
            * x: The first sequence.  
            * y: The second sequence.  
        Out:  
            * The Pearson correlation coefficient.  
    """  
  
    # Calculate the means of the sequences  
    n = len(x)  
    xmean = 0  
    ymean = 0  
    for i in range(n):  
        xmean += x[i]  
        ymean += y[i]  
    xmean /= n  
    ymean /= n  
  
    # Calculate the covariance and the deviations  
    cov_xy = 0  
    dev_x = 0  
    dev_y = 0  
    for i in range(n):  
        cov_xy += (x[i] - xmean) * (y[i] - ymean)  
        dev_x += (x[i] - xmean) ** 2  
        dev_y += (y[i] - ymean) ** 2  
  
    # Calculate the Pearson correlation coefficient  
    return cov_xy / (dev_x**.5 * dev_y ** 0.5)  

# Numpy library is required  
import numpy as np  
  
# Calculate the autocorrelation for the sequence  
print(np.corrcoef(sequence1[:-1], sequence1[1:])[0, 1])  

/**  
 * Calculate the Pearson correlation coefficient between two sequences  
 * @param x the first sequence  
 * @param y the second sequence  
 * @return the Pearson correlation coefficient  
 */  
public static double pearsonAutocorrelation(double[] x, double[] y) {  
    // Calculate the means of the sequences  
    int n = x.length;  
    double xmean = 0;  
    double ymean = 0;  
    for (int i = 0; i < n; i++) {  
        xmean += x[i];  
        ymean += y[i];  
    }  
    xmean /= n;  
    ymean /= n;  
  
    // Calculate the covariance and the deviations  
    double cov_xy = 0;  
    double dev_x = 0;  
    double dev_y = 0;  
    for (int i = 0; i < n; i++) {  
        cov_xy += (x[i] - xmean) * (y[i] - ymean);  
        dev_x += Math.pow(x[i] - xmean, 2);  
        dev_y += Math.pow(y[i] - ymean, 2);  
    }  
  
    // Calculate the Pearson correlation coefficient  
    return cov_xy / (Math.pow(dev_x, 0.5) * Math.pow(dev_y, 0.5));  
}  

4.3 — Test de la longueur du cycle

Nous voulons maintenant tester la longueur du cycle de la LCM.
La longueur du cycle est le nombre d’itérations avant que la séquence ne commence à se répéter.
Pour ce faire, nous allons stocker les nombres générés dans un ensemble et vérifier si le nombre est déjà dans l’ensemble.
Si le nombre est déjà dans l’ensemble, nous avons trouvé un cycle et pouvons retourner la longueur du cycle.
Si le nombre n’est pas dans l’ensemble, nous l’ajoutons à l’ensemble et continuons à générer des nombres.

Implémentez la fonction test_cycle_length(sequence) et exécutez-la sur les séquences générées.

def test_cycle_length (sequence: list[int]) -> int | None:  
  
    """  
        Test the cycle length of the LCM sequence.  
        In:  
            * sequence: The generated sequence.  
        Out:  
            * The cycle length if a cycle is detected, None otherwise.  
    """  
  
    seen = {}  
    for i, value in enumerate(sequence):  
        if value in seen:  
            cycle_length = i - seen[value]  
            print(f"Cycle detected after {i} steps with a cycle length of {cycle_length}.")  
            return cycle_length  
        seen[value] = i  
  
    print("No cycle detected in the given sequence.")  
    return None  

/**  
 * Test the cycle length of the LCM sequence  
 * @param sequence the generated sequence  
 * @return the cycle length if a cycle is detected, null otherwise  
 */  
public static Integer testCycleLength(int[] sequence) {  
    Map<Integer, Integer> seen = new HashMap<>();  
    for (int i = 0; i < sequence.length; i++) {  
        if (seen.containsKey(sequence[i])) {  
            int cycleLength = i - seen.get(sequence[i]);  
            System.out.println("Cycle detected after " + i + " steps with a cycle length of " + cycleLength + ".");  
            return cycleLength;  
        }  
        seen.put(sequence[i], i);  
    }  
    System.out.println("No cycle detected in the given sequence.");  
    return null;  
}  

5 — Optimisez vos solutions

Ce que vous pouvez faire maintenant est d’utiliser des outils d’IA tels que GitHub Copilot ou ChatGPT, soit pour générer la solution, soit pour améliorer la première solution que vous avez proposée !
Essayez de faire cela pour tous les exercices ci-dessus, pour voir les différences avec vos solutions.

Pour aller plus loin

On dirait que cette section est vide !

Quelque chose que vous auriez aimé voir ici ?
Faites-le nous savoir sur le serveur Discord !
Peut-être pouvons-nous l’ajouter rapidement.
Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !

Pour aller au-delà

6 — Coefficient de corrélation de Pearson incrémental

Le coefficient de corrélation de Pearson peut être calculé de manière incrémentale, ce qui peut être utile lorsqu’on traite de grands ensembles de données.
L’article suivant fournit une bonne explication du calcul incrémental du coefficient de corrélation de Pearson :

Tschumitschew, K., Klawonn, F. (2012). Incremental Statistical Measures.
In: Sayed-Mouchaweh, M., Lughofer, E. (eds) Learning in Non-Stationary Environments. Springer, New York, NY. https://doi.org/10.1007/978-1-4419-8020-5_2

Implémentez le calcul incrémental du coefficient de corrélation de Pearson et testez-le sur les séquences générées.