Terminales Spé NSI

É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.

Algorithme glouton

Un client nous achète un objet qui coûte 53 euros. Il paye avec un billet de 200 euros. Il faut donc lui rendre 147 euros, par exemple un billet de 100, deux billets de 20, un billet de 5 et une pièce de 2.

Rappel : récursivité terminale

La définition de la fonction factorielle est $$ n! = \begin{cases} 1 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$

1. 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. Algorithme : récursivité enveloppée """

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def fact_env(n: int) -> int:
    """
    Retourne la factorielle de n.

    Algorithme : récursivité enveloppée
    """
    if n == 0:
        return 1

    return n * fact_env(n - 1)


if __name__ == "__main__":
    assert fact_env(0) == 1
    assert fact_env(1) == 1
    assert fact_env(5) == 120
    assert fact_env(8) == 40320

Ce chapitre présente la première étape du processus de modélisation du monde réel. On commence par recueillir les informations à intégrer dans la base de donnée puis on les transcrit sous une forme qui nous permettra, dans le prochain chapitre, à passer au modèle relationnel (choix de la structure de la base, clés, ...).

Concepts relationnels

Modèle relationnel

Le modèle relationnel tire son nom de la notion de relation mathématique entre les éléments. Chacun de ces éléments peut prendre des valeurs dans un ensemble défini.

Par exemple, les appareils électroménagers d’une cuisine peuvent être contenus dans l’ensemble des valeurs suivantes : {Réfrigérateur, Cuisinière, Hotte, Robot, Lave-vaisselle}. On peut, par ailleurs, aussi considérer l’ensemble des couleurs que peuvent prendre ces appareils : {Rouge, Vert, Bleu, Jaune, Blanc, Noir, Rose}. Les combinaisons possibles entre les appareils et les couleurs sont au nombre de 35. Parmi toutes ces combinaisons possibles, on effectue une sélection qui représente la description d’une cuisine :

Qu’est-ce qu’une base de données ?

Le nombre d’informations disponibles et les moyen de les diffuser sont en constante progression. La croissance du Web a encore accru ce développement en fournissant l’accès à des bases de données gigantesques et très diverses par l’intermédiaire d’une interface commune (Amazon, Google, Facebook, ...).

Notion de base de données

Tout le monde a une idée naturelle de ce que peut être une base de donnée, nous stockons, sur nos disques durs, non seulement des fichiers musicaux, mais aussi des informations relatives à ces derniers : noms des artistes, des albums, dates d’enregistrements, noms et numéros des morceaux, parfois noms des musiciens, ...

Introduction

Dans le code suivant (qu’il faudra étudier et exécuter) :

1. Quel est le cas de base de l’algorithme récursif ?

   [Lire]

Introduction

Ce problème est une abstraction pour un grand nombre d’autres problèmes d’optimisation. Il a été utilisé en cryptographie comme base pour différents schémas de chiffrement1. Il faut cependant noter que la plupart de ces schémas de chiffrement ne sont plus actuellement considérés comme sûrs. ^1, il est utilisé lors du chargement des bateaux ou d’avions, lors de la découpe de matériaux (minimisation des coupes « chutes » lors de la découpe), etc.

Le développement des traitements informatiques nécessite la manipulation de données de plus en plus nombreuses. Leur organisation et leur stockage constituent un enjeu essentiel de performance. Le recours aux bases de données relationnelles est aujourd’hui une solution très répandue. Ces bases de données permettent d’organiser, de stocker, de mettre à jour et d’interroger des données structurées volumineuses utilisées simultanément par différents programmes ou différents utilisateurs. Cela est impossible avec les représentations tabulaires étudiées en classe de première.

Manipulation de points

On considère la classe nommée Point ayant les attributs suivants :

• __abs : attribut privé de type float pour représenter l’abscisse du point ;
• __ord : attribut privé de type float pour représenter l’ordonnée du point.

1. Définir la class Point et le constructeur __init__ permettant d’initialiser les deux attributs.

L’objectif de ce document est d’essayer de faire comprendre les idées mises en œuvre lors de l’écriture des système d’exploitation afin qu’un nombre de programmes plus important que le nombre de processeurs puisse fonctionner « simultanément ».

L’ordonnanceur

Rappel sur l’exécution d’un programme