Cette séance a pour objectif de vous familiariser avec la création et la manipulation de modules.
Comme il est maintenant de tradition vous diviserez le code de votre programme principal en trois parties:
- Importation des modules ;
- Définitions des fonctions ;
- Partie principale (lieu d’appel des fonctions).
Vous documenterez aussi systématiquement vos fonctions (une aide sera fournie dans les questions relatives à la définition de chacune de ces fonctions).
[Lire]Rappels d'algorithmique
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 .
Lorsqu’on élabore ou étudie un algorithme, il est donc nécessaire de vérifier :
[Lire]Recherche d'un élément dans un tableau : algorithmes itératifs et récursifs
Recherche d’un élément dans un tableau
La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :
- La recherche linéaire itérative ;
- La recherche linéaire récursive ;
- La recherche dichotomique itérative ;
- La recherche dichotomique récursive.
Travail à faire
- Implémenter en Python les cinq algorithmes suivants et répondre aux questions.
Recherche séquentielle (ou linéaire)
Recherche séquentielle itérative
Algorithme 1
Fonction : recherche(tab, valeur)
Action : recherche la valeur « valeur » dans le tableau « tab »
Début
i ⟵ 0
i_val ⟵ -1
nb ⟵ Longueur(tab)
TantQue i < nb Faire
Si tab[i] = valeur Alors
i_val ⟵ i
FinSi
i ⟵ i + 1
FinTantQue
Renvoyer i_val
Fin
La récursivité appliquée aux chaînes de caractères et aux listes
Introduction
Une chaîne de caractère est une structure de données qui permet de rassembler en un unique objet une succession ordonnée de caractères. Ainsi, une définition récursive d’une chaîne de caractères pourrait être :
Définition récursive d’une chaîne de caractères
Une chaîne de caractères est :
- soit la chaîne de caractères vide ;
- soit constituée de son premier caractère et du reste des caractères qui forment aussi une chaîne de caractères (éventuellement vide).
Une liste est une structure de données qui permet de rassembler en un unique objet une succession ordonnée d’objets (ou de valeurs). Ainsi, une définition récursive d’une liste pourrait être :
[Lire]Récursivité sur les entiers
To understand recursion, you must first understand recursion.
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.
[Lire]Problème du sac à dos
Chapitre 23,02
Au programme
Algorithmique
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Algorithmes gloutons | Résoudre un problème grâce à un algorithme glouton. | Exemples : problèmes du sac à dos ou du rendu de monnaie. Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale. |
Algorithmes gloutons, problème du rendu de monnaie
Chapitre 23,01
Au programme
Algorithmique
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Algorithmes gloutons | Résoudre un problème grâce à un algorithme glouton. | Exemples : problèmes du sac à dos ou du rendu de monnaie. Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale. |
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.)
[Lire]Les différentes erreurs lorsqu'on calcule à l'aide d'un ordinateur
Derivation numérique
Dans ce document, on s’intéresse au différentes erreurs qui interviennent lorsqu’on effectue des calculs à l’aide d’un ordinateur. On prend pour exemple le calcul numérique de la dérivée d’une fonction, qu’elle soit définie analytiquement ou numériquement (par une table de valeurs).
Dérivation d’une fonction analytique — idée simple
Introduction
Le nombre dérivé $f’(x)$ en un point $x \in \mathbb{R}$, d’une fonction1 : $$ \begin{array}{l|rcl} f: & \mathbb{R} & \longrightarrow & \mathbb{R} \cr & x & \longmapsto & f(x) \end{array} $$
[Lire]