Terminales Spé NSI

Dans ce document on introduit une méthode permettant d’évaluer numériquement une solution de l’équation $f (x) = 0$, avec $f$ une fonction de $\mathbb{R}$ dans $\mathbb{R}$ (lorsque la solution existe, bien sur) : la méthode de dichotomie.

• La méthode de dichotomie est efficace et converge relativement vite. De plus, les conditions de son utilisation sont assez simples : la fonction $f$ doit seulement être continue et changer de signe sur l’intervalle choisi ;
• La méthode de Newton converge étonnement vite ! Les conditions de son utilisation sont cependant plus contraignantes : la fonction $f$ doit être dérivable.

Méthode de la dichotomie

Le raisonnement à mettre en œuvre s’appuie sur le théorème des valeurs intermédiaires.

Ce document étudie le problème de la sous-séquence de somme maximale. Ce problème est intéressant parce qu’il existe nombre d’algorithmes pour le résoudre et la complexité (en nombre d’opérations de somme) de ces algorithmes varie considérablement. Seulement deux algorithmes seront abordés, un prochain document présentera l’algorithme le plus efficace (cf. programmation dynamique).

Présentation

Exemples

• Pour le tableau tab = [-2, -5, 6, -2, -3, 1, 5, -6], la sous séquence de somme maximale est [6, -2, -3, 1, 5] et sa somme est 7.
• Pour le tableau tab = [0, 1, 2, -2, 3, 2], la sous séquence de somme maximale est [1, 2, -2, 3, 2] et sa somme est 6.
• Pour le tableau tab = [1, -2, 3, 10, -4, 7, 2, -5], la sous séquence de somme maximale est [3, 10, -4, 7, 2] et sa somme est 18.

Paradigme « Brute force »

1. On envisage dans un premier temps un algorithme basé sur le paradigme « Brute force » : on évalue la somme de chaque sous-tableau (parmi les $n(n + 1)/2$ sous-tableaux possibles) et à chaque évaluation on mémorise la somme maximale. Écrire le code de la fonction sous_tab_max dont la spécification est :

1
2
3
4
5
6

def sous_tab_max(tab: List[int]) -> int:
    """
    Recherche de la somme maximale dans un tableau.
    
    Paradigme : « Brute force ».
    """

Tester cette fonction.

L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer le maximum et le minimum des éléments dans un tableau.

1. Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards.

1
2
3
4

from random import randint

if __name__ == "__main__":
    tab = [randint(1, int(1e12)) for i in range(int(1e6))]

2. Utiliser les fonctions min et max fournies par le langage Python afin d’afficher les maximum et minimum dans la liste.

1
2
3
4

    print("Fonctions Python")
    val_min, val_max = (min(tab), max(tab))

    print("min = {}, max = {}".format(val_min, val_max))

3. Écrire le code de la fonction maxmin1 qui, à partir d’un algorithme de « brute force », détermine les maximum et minimum dans la liste passée en argument. La spécification de la fonction est :

1
2
3
4
5
6

def maxmin1(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.

    Paradigme « Brute force »
    """

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def maxmin1(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.

    Paradigme « Brute force »
    """
    val_max = tab[0]
    val_min = tab[0]

    for elt in tab:
        if elt > val_max:
            val_max = elt
        if elt < val_min:
            val_min = elt

    return (val_min, val_max)

4. Vérifier le bon fonctionnement de la fonction maxmin1 en affichant les maximum et minimum dans la liste, à la suite de ceux déterminés à l’aide des fonctions fournies par Python.

1
2
3

    print("Recherche « Brute Force »")
    val_min, val_max = maxmin1(tab)
    print("min = {}, max = {}".format(val_min, val_max))

5. Quelle est la complexité de la fonction maxmin1 ?

Héron d’Alexandrie est un ingénieur, un mécanicien et un mathématicien grec du premier siècle après J.-C.

On ne sait pas grand chose de la vie d’Héron, si ce n’est qu’il était originaire d’Alexandrie ; les historiens se sont même longtemps divisés sur l’époque où il a vécu. Leurs estimations allaient du 1^er siècle avant J.-C. au 3^ème siècle de notre ère. Aujourd’hui, la querelle est éteinte : il est clairement établi que Héron est postérieur à Vitruve mort en $- 20$, et contemporain de Pline l’Ancien (23 – 79), en étant actif autour de l’an 62. Il a donc bien vécu au 1^er siècle après J.-C. et sans doute au début du 2^ème siècle, donc sous l’Empire romain, mais dans l’Alexandrie grecque.

Écriture d’une classe Graphe

L’objectif de cette partie est l’écriture du code modélisant un graphe orienté. La représentation choisie est celle d’un dictionnaire de successeurs (en cours et dans le document 15,2 on a étudié les représentations par des matrice et liste de successeurs).
La représentation par un dictionnaire de successeurs présente de nombreux avantages. Par exemple,

• les sommets peuvent être des entiers ou des chaînes de caractères quelconques ;
• La complexité de la liste des successeurs est directement proportionnelle au nombre de successeurs pour un sommet donné. L’occupation mémoire est donc faible si les sommets possèdent peu de successeurs.
  Remarque : dans le cas d’une matrice d’adjacence, la taille est fixe et comporte $N^2$ éléments si le nombre de sommets est égal à $N$.

Remarque

Contrairement à ce qui a été fait dans le document 15,2, la classe qui va être implémentée ici permettra d’initialiser un graphe vide, puis de le constituer progressivement.

• Cours et exercices non corrigés

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations.

Matrice sommet-sommet

1. Écrire le code de la classe GrapheM qui implémente une matrice sommet-sommet.
   La spécification du constructeur de la classe est :

1
2
3
4

def __init__(self: GrapheM, mat: List[List[int]]) -> None:
        """
        Constructeur de la classe.
        """

Remarque : cette classe possède l’attribut mat qui référence la matrice d’adjacence.

• Cours et exercices non corrigés