Recherche numérique de zéros de fonctions

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

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

 Publié le January 28, 2022  |  4 minutes  |  824 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. [Lire]

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

 Publié 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. [Lire]
Diviser pour régner  Recherche 

Héron d'Alexandrie

 Publié le September 5, 2021  |  4 minutes  |  842 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. [Lire]

Parcours en profondeur : écriture du code en Python

 Publié le May 6, 2021  |  6 minutes  |  1168 mots  |  David Latreyte

É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é. [Lire]
Graphe  Structure de données 

Représentation d'un graphe en informatique

 Publié le April 22, 2021  |  7 minutes  |  1461 mots  |  David Latreyte

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 É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. [Lire]
Graphe  Structure de données 

Les graphes

 Publié le April 20, 2021  |  1 minutes  |  196 mots  |  David Latreyte

Au programme de la partie « Structures de données » Contenus Capacités attendues Commentaires Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés. - Modéliser des situations sous forme de graphes. - Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs. - Passer d’une représentation à une autre. On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux. [Lire]
Graphe  Structure de données