Tri par insertion

Chapitre 5,2

Objectifs

Le tri par insertion a été étudié en classe de 1ère. Dans ce document, après un rappel du cours de 1ère, nous allons implémenter une version récursive de cet algorithme et ensuite utiliser la possibilité que les fonctions en Python ont d’accepter des fonctions comme paramètres, afin de rendre plus générale et utile cette fonction de tri.

Tri du joueur de cartes

Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ». Comment un joueur de carte fait-il pour trier les cartes ? - Au début, la main gauche du joueur est vide et ses cartes sont posées sur la table. - Le joueur prend alors sur la table les cartes, une par une avec sa main droite, pour les placer dans sa main gauche. - Pour savoir où placer une carte dans son jeu, le joueur la compare avec chacune des cartes déjà présentes dans sa main gauche, *en examinant les cartes de la droite vers la gauche*. - *À tout moment, les cartes tenues par la main gauche sont triées* ; ces cartes étaient, à l'origine, les cartes situées au sommet de la pile sur la table.

Tri par insertion

Une correction du code à développer ci-dessous se trouve ici

Introduction

La méthode du tri par insertion est ilustré à ici , ou, de façon plus folklorique, ici .

[Lire]

Programmation Fonctionnelle

Chapitre 5,1

Qu’est-ce que la programmation fonctionnelle ?

S’il n’est pas facile de répondre précisément à cette question, on peut essayer de mettre en évidence les idées que le paradigme fonctionnel promeut :

  • Les fonctions doivent être des objets de première classe, c’est à dire que les fonctions doivent pouvoir être passées comme arguments à une fonction, les fonctions doivent aussi pouvoir être retournées par une fonction.

  • Les fonctions doivent (le plus possible) être pures, c’est à dire ne générer aucun effet de bord.

    [Lire]

Jeu de la vie

Le but de ce sujet est de réaliser en Python une implémentation du jeu de la vie en utilisant la programmation objet.

Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L’état d’une cellule au temps $t+1$ est fonction de l’état au temps $t$ d’un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.

Le jeu de la vie a été inventé par le mathématicien britannique John H. Conway (1937-2020). C’est un exemple de ce qu’on appelle un automate cellulaire bidimensionnel. Il se déroule sur un tableau rectangulaire $(L \times H)$ de cellules. Une cellule est représentée par ses coordonnées $x$ et $y$ qui vérifient $0 \leqslant x < L$ et $0 \leqslant y < H$.

[Lire]

Résoudre un problème grâce aux paradigmes objet et fonctionnel

L’objectif de ce document est d’illustrer une fois encore l’intérêt des différents paradigmes de programmation.

Cas d’étude : fonction avec paramètres

On considère l’équation qui traduit le mouvement d’une balle lancée verticalement vers le haut avec une vitesse $\vec{v}_0$ depuis l’origine des altitudes telle que l’écrit un physicien : $$y(t) = -\dfrac{1}{2}g\, t^2 + v_0\, t$$ Ce physicien a donc tendance à considérer que $y$ est une fonction de la variable $t$ et que cette fonction dépend des paramètres $v_0$ et $g$.

[Lire]

Méthodes spéciales en Python

Définit une classe nommée Fraction pour représenter les nombres rationnels. Cette classe doit posséder deux attributs num et denom, de type entier, qui représentent respectivement le numérateur et le dénominateur du nombre rationnel.
On demande que le dénominateur soit un entier positif.

Un corrigé de cette activité se trouve à cette adresse : https://repl.it/@dlatreyte/fraction

  1. Écrire le constructeur de cette classe. Une exception de type ValueError doit être levée si le dénominateur n’est pas un nombre entier positif.

    [Lire]

Simulation du fonctionnement d'une banque

L’objectif de ce document est de simuler (sommairement bien sûr) le fonctionnement d’une banque. Le programme doit permettre :

  • La création d’une banque ;
  • La création de comptes bancaires ;
  • La création de personnes propriétaires de ces comptes bancaires.

Une correction se trouve à cette adresse : https://repl.it/@dlatreyte/banque

Classe Personne

Dans un module nommé personne, créer la classe Personne dont la spécification est la suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Personne():
    """
    Modélisation d'une personne.

    Attributs
    ---------
    - nom : str
        Renseigné à la création de l'objet
    - Prenom : str
        Renseigné à la création de l'objet
    - email : str
        Email. Initialisé à ""
    - telephone : str
        Numéro de téléphone. Initialisé à ""
    - date_naissance : str
        Chaîne de caractères au format jour/mois/année (4 chiffres). Initialisé à ""
    - jour_naissance : int
        Déterminé à partir de la date de naissance. Initialisée à -1
    - mois_naissance : int
        Déterminé à partir de la date de naissance. Initialisée à -1
    - annee_naissance : int
        Déterminé à partir de la date de naissance. Initialisée à -1
    """

Les spécifications des méthodes sont les suivantes :

[Lire]

Programmation Objet

Programmation orientée objet

Un objet est une instance d’une classe.

L’un des objectifs principaux de la notion d’objet est d’organiser des programmes complexes grâce aux notions :

  • d’encapsulation ;
  • d’abstraction ;
  • d’héritage ;
  • de polymorphisme ;

Remarque : Seules les deux premières notions apparaissent dans le programme de NSI.

Encapsulation

Le principe de l’encapsulation est de regrouper dans le même objet, les données (attributs) et les traitements (méthodes) qui lui sont spécifiques. Ainsi un objet est défini par ses attributs et ses méthodes.

[Lire]

Fourniture et utilisation d'une API

API

Une API (en anglais « Application programming interface ») est une interface de programmation d’application. Elle est destinée à être utilisée par des programmes. Le principe de ce type d’interface est le même que celui des UI (« User Interface ») ou des GUI (« Graphical User Interface ») destinées elles à un utilisateur humain.

Composée de constantes, de fonctions, de classes, elle sert de lien entre un programme et les programmes qui vont l’utiliser. Elle peut être proposée par un service web avec une documentation décrivant l’utilisation qui permettra la communication et l’échange des données. Il existe, par exemple, plusieurs API de géolocalisation qui peuvent être intégrées à des programmes. Une API est très souvent proposée par une bibliothèque logicielle composée de fonctions destinées à être utilisées dans divers programmes.

[Lire]

Paradigmes de programmation

Langages de programmation

Un langage de programmation a besoin :

  • des règles de grammaire qui définissent la syntaxe des expressions ;
  • d’une sémantique qui définit le sens des expressions.

Un langage peut être :

  • interprété : un interpréteur lit et analyse le code séquentiellement, le traduit en langage machine et lance son exécution.
  • compilé : un compilateur lit et analyse le code puis le traduit en langage machine. Par la suite l’exécutable généré peut être lancé.

Remarque : Python un langage interprété mais le code n’est pas directement traduit dans le langage machine de l’ordinateur sur lequel le programme est lancé mais dans le langage machine d’une machine virtuelle (bytecode). Dans un second temps, ce langage machine est interprété par le logiciel.

[Lire]

Exercices

Enquêter sur une erreur dans un calcul de $\pi$

La somme des inverses des carrés des nombres entiers converge vers $\dfrac{\pi^2}{6}$.

$$\sum_{k=1}^{\infty} \dfrac{1}{k^2} = \dfrac{\pi^2}{6}$$

On utilise cette formule pour trouver une approximation de $\pi$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import math

def terme(k: int) -> float:
    return 1 / (k**2)

def approxpi(n: int) -> float:
    s = 0
    # utilise les termes jusqu’à 1/n**2 inclus
    for k in range(n):
        s = s + terme(k)
    return math.sqrt(s * 6)

[Lire]