Somme des $n$ nombres d'un tableau

 Posté le January 29, 2023  |  3 minutes  |  452 mots  |  David Latreyte

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 la somme des $n$ nombres (entiers) d’un tableau. Écrire le code de fonction somme1 dont la spécification est : 1 2 3 4 5 6 7 def somme1(tab: List[float]) -> float: """ Calcul de la somme des nombres éléments de tab. Algorithme : Récursivité enveloppée """ Penser à écrire un jeu de tests. [Voir plus]
Diviser pour régner  Récursivité 

Diviser pour régner

 Posté le January 29, 2023  |  4 minutes  |  808 mots  |  David Latreyte

Dans quel cas ? On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base. La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème. Remarque C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires. [Voir plus]
Diviser pour régner 

Décomposition d'un problème en sous-problèmes

 Posté le January 29, 2023  |  1 minutes  |  57 mots  |  David Latreyte

Principe

  • On décompose le problème en sous-problèmes plus simples.
  • On résout les sous-problèmes.
  • On combine les sous-problèmes de façon à construire la solution du problème initial.

Indépendance des sous-problèmes

  • Si les sous-problèmes sont indépendants les uns des autres : « Diviser pour règner ».
  • Si les sous-problèmes dépendent les uns des autres : « Programmation dynamique ».
Diviser pour régner  Programmation dynamique 

Recherche numérique de zéros de fonctions

 Posté le February 3, 2022  |  6 minutes  |  1220 mots  |  David Latreyte

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 ! [Voir plus]
Méthode de Newton  Dichotomie 

Problème de la sous-séquence de somme maximale

 Posté le January 28, 2022  |  4 minutes  |  825 mots  |  David Latreyte

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 Étant donné un tableau tab[1..n] d’entiers (positifs et négatifs), déterminer la valeur maximale du sous-tableau tab[g..h] donnant la plus grande somme de tous les sous-tableaux contigus de tab. [Voir plus]

Recherche des plus grand et petit éléments dans un tableau

 Posté le January 26, 2022  |  6 minutes  |  1158 mots  |  David Latreyte

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. Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards. Réponse 1 2 3 4 from random import randint if __name__ == "__main__": tab = [randint(1, int(1e12)) for i in range(int(1e6))] Utiliser les fonctions min et max fournies par le langage Python afin d’afficher les maximum et minimum dans la liste. [Voir plus]
Diviser pour régner  Recherche 

Héron d'Alexandrie

Chapitre 0

 Posté le September 5, 2021  |  6 minutes  |  1170 mots  |  David Latreyte

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 1er 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. [Voir plus]

Problème du rendu de monnaie

Chapitre 14,2

 Posté le February 28, 2021  |  8 minutes  |  1648 mots  |  David Latreyte

Énoncé du problème Un commerçant cherche à rendre la monnaie à ses clients de façon optimale, c’est-à-dire avec le nombre minimal de pièces et de billets. Dans ce problème, On suppose que les clients ne donnent que des sommes entières en euros (pas de centimes pour simplifier) ; Les valeurs des pièces et billets à disposition sont : 1, 2, 5, 10, 20, 50, 100, 200 et 500. On suppose que l’on a autant d’exemplaires que nécessaire de chaque pièce et billet ; Dans la suite, afin de simplifier, on désigne par « pièces » à la fois les pièces et les billets. [Voir plus]
Programmation dynamique 

Autour de la suite de Fibonacci

Chapitre 14,1

 Posté le February 25, 2021  |  11 minutes  |  2305 mots  |  David Latreyte

Rappel : récursivité terminale La définition de la fonction factorielle est $$ n! = \begin{cases} 0 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$ Définir la fonction fact_env qui calcule la factorielle d’un entier naturel $n$, sans oublier le jeu de tests. La spécification de la fonction est : 1 2 3 4 5 6 def fact_env(n: int) -> int: """ Retourne la factorielle de n. [Voir plus]
Récursivité  Récursivité terminale  Récursivité enveloppée  Programmation dynamique  Mémoïsation