Algorithmique

Au programme de la classe de première

Documents

• Doc. Le rendu de monnaie

• Doc. Le problème du sac à dos

Algorithmique

En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie .

La récurrence est un raisonnement mathématique courant et parmi les plus puissants pour démontrer des théorèmes ou construire des objets. Par exemple, on l’utilise dans un cours de mathématique de lycée pour montrer que :

• Pour tout entier $n \geqslant 0$, on a : $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$ ;
• Un entier naturel n’est autre que 0 ou le successeur d’un entier naturel (0 est 0, 1 est le successeur de 0, 2 est le successeur de 1, …).

En programmation, on peut raisonner de façon identique, nous allons construire des fonctions et des structures de données (listes chaînées, arbres, etc.) à l’aide d’une hypothèse de récurrence et d’un point de départ. Le déroulement de la récurrence sera quant à lui pris en charge par la machine.

Au programme

Algorithmique

Au programme

Algorithmique

Introduction

Les algorithmes gloutons forment une catégorie d’algorithmes permettant de parvenir à une solution pour un problème d’optimisation qui vise à maximiser/minimiser une quantité (plus court chemin (GPS), plus petite durée d’exécution, meilleure organisation d’un emploi du temps, etc.)