Details

Category: NSI

Published: 25 February 2026

Last Updated: 16 April 2026

Details

Category: NSI

Published: 25 February 2026

Last Updated: 04 April 2026

Details

Category: NSI

Published: 25 February 2026

Last Updated: 06 April 2026

Details

Category: NSI

Published: 26 January 2023

Last Updated: 13 February 2023

Pyxel et Python

Pyxel est un moteur de jeu vidéo rétro pour Python.

Grâce à ses spécifications simples inspirées par les consoles rétro, comme le fait que seulement 16 couleurs peuvent être affichées et que seulement 4 sons peuvent être lus en même temps, vous pouvez vous sentir libre de créer des jeux vidéo dans le style pixel art.

1. Installation de Pixel

 Voir la section "Comment installer" sur la page de Pyxel.

Pour Windows

• Télécharger Edupyter 38, 39 ou 310 selon votre environnement
• Installer Edupyter
  Edupyter est portable et ne nécessite pas de droits administrateur. Edupyter peut être installé dans un dossier sur le disque dur ou sur une clé USB / disque amovible. L'installation ne fait que copier des fichiers et des dossiers dans le dossier d'installation choisi. Le système n'est pas modifié. Pour supprimer Edupyter il suffit de supprimer le dossier dans lequel il a été installé.
• Lancer Edupyter et cliquer sur l'icône qui apparaît à côté de l'horloge (voir aide).
• Ouvrir Thonny
• Saisir le code et enregistrer le fichier Python (en .py).
• Exécuter le code en cliquant sur la touche F5 ou le bouton vert. Cette action ouvrira automatiquement la fenêtre du jeu.

Sous Mac

• Après avoir installé Python3 (version 3.7 ou plus), lancez la commande suivante :

python3 -m pip install -U pyxel

• Si vous utilisez Python3, qui est installé par défaut sur Mac, veuillez ajouter sudo au début de la commande ci-dessus pour activer la commande pyxel.

Pour Repl.it

• Ouvrir le fichier sous Pyxel
• problème pour la gestion des images (à voir)

2. Tutoriels pour débuter avec Pyxel

Le jeu du snake

• Snake.Pyxel : Le td détaillé
  
  • Snake.Pyxel-Correction 
  • Correction sur Repl.it

Programmer un jeu vidéo avec Pyxel 

Doc officielle de Pyxel : https://github.com/kitao/pyxel

Prérequis : avoir fait en groupe le jeu du serpent, qui montre rapidement dans un exemple « tout fait » les fonctionnalités
principales. Dans ce tutoriel, nous allons explorer un peu plus en détail les mécanismes.

1. Tutoriel_Pyxel_1 / Correction
2. Tutoriel_Pyxel_2 / Correction
3. Tutoriel_Pyxel_3 / Correction
4. Tutoriel_Pyxel_4 / Correction
5. Tutoriel_Pyxel_5 / Correction
6. Tutoriel_Pyxel_6 / Correction

Autres Tutoriels

D'autres Tutos et exemples sont proposés sur le site de la Nuit du c0de.

3. Projet : Programmer un jeu vidéo avec Pyxel 

• Le jeu de la taupe : télécharger ce dossier
  C'est un fichier .ipynb que vous lirez via Jupyter lab
• Version PDF : le jeu de la taupe

4. Ajouter des images

• ll est possible d’utiliser un utilitaire Pyxel pour créer ou éditer des images, ou plus généralement des ressources (sons ...).
  On lance cet éditeur depuis un terminal.
  1. Sous EDUPYTER : click droit sur EDUPYTER puis Console
  2. Sous ANACONDA : lancer l'application  CMD.exe Prompt
• On se place dans le répertoire dans lequel se trouve notre jeu puis on exécute l'instruction suivante : pyxel edit image.pyres qui va créer une image nommée ici MonImage (on peut changer le nom !)

pyxel edit MonImage.pyres

•  L’interface de l’utilitaire Pyxel s’ouvre :
  Cet éditeur permet de dessiner des images façon pixel art.

  On dessine dans la partie gauche, qui « zoome » sur un carré de pixels découpé en 4 parties de (8x8).

Pyxel_Image_Editor.png

• Pour utiliser une partie de cette image il suffira d'utiliser la méthode pixel.blt(x,y,img,u,v,h) après avoir chargé l'image en écrivant au début du script, l’instruction : pyxel.load("MonImage.pyxres")

pyxel.load("MonImage.pyxres")

pyxel.blt(x, y, img, u, v, w, h)

Cette méthode pixel.blt(x,y,img,u,v,h) copie : 

• à la position (x, y) de l’écran de jeu;
• La portion de l'image MonImage.pyxres  qui est située à la position (u, v) et qui a pour taille (w, h). 
• Elle « découpe » donc un morceau de MonImage.pyxres déterminé par u, v, w, h et vient le « coller » au point (x, y) sur l’écran.
• Le paramètre img : Par défaut sa valeur est zéro.

Articles Connexes 

{module [116]}

Details

Category: NSI

Published: 26 May 2021

Last Updated: 10 February 2026

Classes de Première - Evaluations
NSI - Numérique et Sciences Informatiques

Les évaluations de la classe de première.

Année 2025-2026

• Test 1 - Les listes (niveau 1)  : énoncé / correction
  Testounet sur Capytale 
• Test 2 - Les listes (niveau 2) et fonctions de base : énoncé / correction
  Test sur Genumsi
• Test 3 : repésentation des donnés : énoncé - correction

Compléments NSI

Évaluation en fin de première

Les élèves qui ne concerveront pas cette spécialité en terminale, devront passer une épreuve commune en fin d'année de première. En voici les spécificités :

• • Durée : 2 heures
  • Format : QCM en 7 parties avec 4 réponses possibles pour chacune des 6 questions par partie.
    Au total donc 42 questions (moins de 3 minutes par question).
  • Notation : Attention, une bonne réponse rapportera 3 points, une mauvaise ou une multiple \(-1\) point et l'absence de réponse 0 point.
    
    
  • Exemples
    
    • Tous les sujets de la BDD : Sujets des ECC de NSI
    • générateur de QCM : https://genumsi.inria.fr/

{module [104]}

Articles Connexes 

{module [116]}

Details

Category: NSI

Published: 26 May 2021

Last Updated: 13 January 2026

Classes de Terminale - Evaluations
NSI - Numérique et Sciences Informatiques

Les évaluations de la classe de Terminale NSI.

Année 2025-2026

• DS 1 - POO : Sujet / corrigé.
  La POO, les classes
  
• DS 2 - SQL et bases de données : sujet / corrigé.
  Bases de données et language SQL
• DS 3 - Récursivité et Piles : sujet / corrigé.
  Récursivité et Piles/Files
• DS 4 - Arbres et POO : Sujet / Corrigé
  Les arbres binaires de recherches
• DS 5 - BAC BLANC 1 : sujet / corrigé.
  Bases de données et language SQL, POO, Récursivité, Piles et Files, Arbres binaires
• DS 6 - BAC BLANC 2 :
  • sujet J1/ corrigé J1.
  • sujet J2/ corrigé J2.
     

Articles Connexes 

{module [116]}

Details

Category: NSI

Published: 18 May 2020

Last Updated: 09 December 2025

NSI - Numérique et Sciences Informatiques
Les réseaux

 Plan du cours

• 1. Les réseaux informatiques : généralités
• 2. Les modèles OSI et TCP/IP : Le protocole TCP/IP
• 3. Adresse IP et notation CIDR pour les adresses IP
• 4. TP encapsulage et protocoles
• 5. TP de simulation d'un réseau : Filius
• 6. Pour vous tester
• 7. Resources sur les réseaux

1. Les réseaux informatiques : généralités

Une définition

• Un réseau informatique (Data Communication Network ou DCN) est un ensemble d'équipements reliés entre eux et qui échangent des informations.
• Dans les grandes lignes, un réseau est intégralement composé :
  • d'équipements informatiques (ordinateurs et matériel réseau) ;
  • et de liaisons point-à-point (cables, wifi, ... ) qui relient deux équipements entre eux.

Les différents types de réseaux

Certains réseaux sont limités à une salle, voire un bâtiment. D'autres font la taille d'une ville ou d'un quartier, quand d'autres ont une étendue nationale ou mondiale.

• Réseaux locaux
  Les réseaux les plus petits contiennent entre 2 et 100 ordinateurs, qui sont reliés avec des câbles ou une connexion sans fil.
  C'estle cas des réseaux personnels, internes aux entreprises ou aux écoles.
  • PAN (Personnal Area Network)  ou  LAN ( Local Area Network) .
• Réseaux interconnectés
  • MAN (Metropolitan Area Network) ont généralement la taille d'une ville ;
  • WAN (Wide Area Network), permettent de relier entre eux des réseaux locaux dans des villes différentes.
• Réseaux mondiaux
  Internet (interconnection of networks) est une interconnexion de réseaux à l'échelle mondiale. Environ 47 000 réseaux de grande taille sont interconnectés pour former internet. Les informations qui transitent sur internet passent par des câbles qui traversent les différents océans.

Les routeurs

• Chaque sous-réseaux est connecté à un ou plusieurs autres sous-réseaux. Les routeurs sont chargés du traffic, c'est à dire du routage des paquets de données.
• Les données sont propagées de proche en proche et doivent trouver leur chemin vers le récepteur.
• Tout le problème est de trouver un chemin entre l'émetteur et le récepteur.
• Le routeur utilise une table de routage, c'est à dire un tableau d'adresses vers les sous-réseaux adjacents.

L'adressage réseau : adresses MAC et IP

Lors du routage il faut déterminer quand la donnée a atteint sa destination. Pour cela, les relais doivent avoir pouvoir identifier les ordinateurs.

On peut imaginer le fonctionnement du reseau par analogie avec le réseau postal ou téléphonique.
 

Il existe plusieurs types d'adresses :

• les adresses physiques (MAC) 
  
  • L’adresse MAC (Media Access Control) est l’adresse physique d’un périphérique réseau (carte ethernet, carte wifi, ...).
  • Chaque adresse MAC est sensée être unique. On peut donc considérer qu’elle constitue une sorte de plaque d’immatriculation des appareils électroniques.
  • L'adresse MAC, n'est pas modifiable (enfin pas facilement !). 
  • Une adresse MAC-48 est constituée de 48 bits (6 octets) et est généralement représentée sous la forme hexadécimale en séparant les octets (de 00 à FF) par un tiret.
    Pour rappel 1 octet = 8 bits permet de représenter 2⁸ valeurs de 0 à 255 soit en hexadécimal de 00 à FF.

MAC : 00 - 21 - CC - 49 - F9 - 85

• les adresses logiques (IP)
  • Une adresse IP (Internet Protocol) est un numéro d'identification qui est attribué de façon permanente ou provisoire à chaque périphérique relié à un réseau informatique qui utilise l'Internet Protocol.
  • Il existe des adresses IP de version 4 sur 32 bits (IPV4), et de version 6 sur 128 bits (IPV6).
  • La version 4 est actuellement la plus utilisée (55% en 2025) mais est progressivement remplacée.
  • L'IPV4 est constituée de 32 bits (4 octets) et est généralement représentée sous la forme décimale en séparant les octets (de 0 à 255) par un point. Elle permet de générer 2³² adresses soit plus de 4 milliards.
    Pour rappel 1 octet = 8 bits permet de représenter 2⁸ valeurs de 0 à 255.

IPV4 : 172 . 16 . 254 . 1

• • L'IPV6 est constituée de 128 bits (16 octets) et est représentée en écriture hexadécimale, où les 8 groupes de 2 octets (16 bits par groupe donc de 0000 à ffff) sont séparés par un signe deux-points : Elle permet de générer 2¹²⁸ adresses soit plus de 3,4. 10³⁸.

 IPV6 : 2001 : db8 : 1 : 85a3 : ab : 2ab : ac1f : 8001

• Pourquoi avoir deux adresses MAC et IP ?
  • Une telle séparation a son utilité : elle permet le remplacement d'un ordinateur sans pour autant changer son adresse internet.
  • Une adresse IP permet d’identifier votre appareil de connexion sur un réseau.
  • Toutefois si vous utilisez le même appareil pour vous connecter à internet depuis un autre endroit, votre adresse IP ne sera plus la même car l’adresse IP dépend du réseau utilisé.
  • En revanche, l’adresse MAC ne change jamais et permet quant à elle d’identifier chacun des périphériques réseau, notamment sur un réseau local.

• Un exemple de réseau
  
  • Dans cet exemple :
    • les ordinateurs ont une adresses MAC (celle de la carte réseau) et une adresse IP,
    • les routeurs ont chacun deux adresses MAC et deux adresses IP (une par prise soit une par sous-réseau),
      Les routeurs peuvent avoir plus de 100 prises réseaux. Chacune de ces prises aura sa propre adresse MAC et sa propre adresse IP.
    • et les commutateurs réseaux (en anglais switch) sont voir comme une multiprise réseau qui redirige les messages sans les ouvrir ni les modifier.

•  Comment obtenir les adresses MAC et IP des éléments de votre réseau ?

• Windows
  Sur Windows, cliquez sur le bouton “Démarrer”, puis tapez “cmd” dans “Rechercher” pour atteindre l’Invité de Commande.
  Saisissez la fonction ipconfig /all (ou getmac /v)

• Linux
  Sous Linux, ouvrir un terminal et tapper : ifconfig.
• MAC
  Sur MAC, sélectionnez touche "OPTION" puis cliquez sur l'icone WIFI en haut à droite
  et pour plus de détails : ifconfig

Le protocole DNS : Adresse IP et nom de domaine

• Le plus souvent, pour se connecter à un serveur, l'utilisateur ne donne pas l'adresse IP, mais le nom de domaine, par exemple www.math93.com ou www.google.fr.
• Ce nom de domaine est ensuite converti en adresse IP par l'ordinateur de l'utilisateur en faisant appel au système de noms de domaine (DNS : Domain Name System).
• Le DNS, est le protocole utilisé pour traduire les noms de domaine Internet en adresse IP.

• Exemple : le site www.google.fr est aussi accessible par son adresse ipv4 : 216.58.201.227
  On peut facilement trouver l'adresse IP (IPv4 ou IPv6) en tappant dans votre console cmd (Command Prompt) :
  • ping www.adressedusite
    ou
  • ping -4 www.adressedusite 
     
    ou sur Mac ou Linux
  • ping -c 4 www.adressedusite 

 Top

2. Les modèles OSI et TCP/IP : Le protocole TCP/IP

L'ensemble des données transférées sur internet l'est grâce à un protocole de communication : le protocole TCP/IP (Transmission Control Protocol / Internet Protocol) basé sur le modèle théorique OSI (Open Systems Interconnection).

Le modèle OSI (Open Systems Interconnection) est un modèle conceptuel qui caractérise et normalise la façon dont différents composants logiciels et matériels impliqués dans une communication réseau doivent diviser le travail et interagir les uns avec les autres. Il contient sept couches. Vous pouvez voir les noms et fonctions de base de chaque couche dans la figure suivante.

Modèle TCP/IP vs. Modèle OSI

Le modèle TCP/IP est plus ancien que le modèle OSI. La figure suivante montre les relations correspondantes entre leurs couches.

  Top

3. Adresse IP et notation CIDR pour les adresses IP

Voici le TD sur les adresses IP, à traiter en Python :

• TP adresse IP / Version Capytale

Dans ce TP on travaille sur les adresses IP et les masques de sous-réseaux.
Un sous-réseau est une subdivision logique d'un réseau de taille plus importante.

Masque de sous-réseaux

Le masque de sous-réseau permet de distinguer la partie de l'adresse commune à tous les appareils du sous-réseau et celle qui varie d'un appareil à l'autre.

 Le masque de sous-réseau va indiquer le nombres d'adresses IP disponibles dans le sous-réseaux.

Adresses réservées

2 adresses sont réservées sur le réseaux :

• La première adresse d'un sous-réseau spécifie le réseau lui-même, elle sert pour des messages non nécessairement destinés aux seuls routeurs mais qui ne doivent normalement pas être reroutés vers Internet.
• La dernière adresse est une adresse de diffusion (broadcast) pour des messages normalement destinés aux seuls routeurs d'une liaison spécifique permettant les échanges entre tous les hôtes de ce sous-réseau d'une part et les autres réseaux extérieurs (dont l'Internet global). Cette adresse n'est habituellement pas reroutée vers Internet, sauf en cas d'utilisation de protocoles particuliers dont le routeur est un point de terminaison et de conversion.

Notation CIDR (Classless inter-domain routing) pour les adresses IP :

Exemple : IPv4 172.20.1.242 / 24

La notation CIDR (Classless Inter-Domain Routing) est une méthode utilisée pour spécifier la taille d'un bloc d'adresses IP. Cette méthode a remplacé la notation plus ancienne basée sur les classes de réseau (A, B, C, etc.) qui étaient limitées à des tailles de bloc spécifiques.

La notation CIDR est généralement utilisée pour spécifier le masque de sous-réseau associé à une adresse IP. Le masque de sous-réseau définit la plage d'adresses IP qui est utilisée pour un réseau particulier.

Le masque de sous-réseau est exprimé en bits, et la notation CIDR utilise une barre oblique pour séparer l'adresse IP de la longueur du masque de sous-réseau.

• Par exemple, l'adresse IPV4

192.168.1.1 / 24

signifie que les 24 premiers bits de l'adresse IP sont utilisés pour identifier le réseau, tandis que les 8 bits restants sont utilisés pour identifier des hôtes individuels sur le réseau.

La longueur du masque de sous-réseau peut varier de 1 à 32 bits, ce qui permet de spécifier des blocs d'adresses IP de différentes tailles. Les blocs d'adresses IP plus petits sont souvent utilisés pour des réseaux plus petits, tandis que les blocs plus grands peuvent être utilisés pour des réseaux de grande envergure.

La notation CIDR permet une utilisation plus efficace des adresses IP disponibles en évitant le gaspillage d'adresses inutilisées dans les blocs d'adresses plus grands. Elle permet également de diviser les blocs d'adresses IP en sous-réseaux plus petits pour une meilleure organisation et une meilleure gestion du réseau.

 Top

4. TP encapsulage et protocoles

On va regarder comment se déroule une transmission de données sur un réseau et préciser le fonctionnement des protocoles TCP et IP.

1. Cours sur le modèle de communication TCP/IP : lien vidéo.
   Description du protocole de transmision des données dans un réseaux.

{youtube} https://youtu.be/pqVtDF40Sw4 {/youtube}

1. TP encapsulation : version pdf.
   Utilisation de wireshark et traceroute.
   • Pour ce TP il sera nécessaire d'installer Wireshark : https://www.wireshark.org/
   • Localisation IP : iplocation.net / en.dnstools.ch / www.geodatatool.com /

  Top

5. TP de simulation d'un réseau : Filius

Filius est un logiciel de simulation de réseaux informatiques. Il permet de créer son propre réseau de le configurer, de le simuler et de visualiser les échanges d’informations.

Installation de Filius

• Lien de téléchargement : https://www.lernsoftware-filius.de/Herunterladen  Le site web et l’installateur sont en allemand, mais le logiciel est traduit en français.
  Choisir la langue lors de la première ouverture du logiciel. En cas d’erreur, supprimer le dossier .filius contenant les paramètres de langues se trouvant dans  C:\Users\ »nom d’utilisateur sur le réseau »\AppData\Local\.filius    
• Documentations complètes : Doc. Officielle (abglais) / Doc. en français .

TP simulation réseau, web et serveur DNS

• TP Filius : Simulation réseaux sous Filius.
  Simulation de deux sous-réseaux, serveurs Web et DNS.

  Top

6. Pour vous tester

Voici un QCM dont les questions sont extraites de la banque de sujets publique des ECC.

• QCM sur les réseaux : renseignez un identifiant quelconque.
• Le corrigé.

7. Resources sur les réseaux

• Localisation IP : iplocation.net / en.dnstools.ch / www.geodatatool.com /
   
• Wireshark : https://www.wireshark.org/
  Pour analyser les trames
   
  
• Simulation de réseaux
  • Packet Tracer Cisco : Windows et Linux
    Pour simuler un réseau, nécessite l'inscription à un cours avant de pouvoir télécharger la dernière version
  • GNS3 : https://www.gns3.com/
  • Filius  : http://www.lernsoftware-filius.de/Herunterladen
•  Liens vesr les commandes CMD
  
  • http://www.ybet.be/operating-06/dos-06.php

  Top

Articles Connexes 

{module [116]}

Details

Category: NSI

Published: 18 May 2020

Last Updated: 30 March 2022

NSI - Numérique et Sciences Informatiques
Algorithmes gloutons

Présentation des d'algorithmes gloutons avec exemples et TD.

1. Présentation de la notion d'algorithme glouton.
   1. Les problèmes d'optimisation.
   2. Résoudre un problème d'optimisation : les algorithmes gloutons
2. Le problème du rendu de monnaie.
3. Le TD sur les algorithmes gloutons et le rendu de monnaie.
4. Le problème du sac à dos.

1. Présentation de la notion d'algorithme glouton

Les problèmes d'optimisation

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble.

Les problèmes d'optimisation classiques sont par exemple : 

• la répartition optimale de tâches suivant des critères précis (emploi du temps avec plusieurs contraintes) ;
• le problème du rendu de monnaie ;
• le problème du sac à dos ;
• la recherche d’un plus court chemin dans un graphe ;
• le problème du voyageur de commerce.

Résoudre un problème d'optimisation : les algorithmes gloutons

De nombreuses techniques informatiques sont susceptibles d’apporter une solution exacte ou approchée à ces problèmes.

• Recherche de toutes les solutions
  La technique la plus basique pour résoudre ce type de problème d'optimisation consiste à énumérer de façon exhaustive toutes les solutions possibles, puis à choisir la meilleure. Cette approche par force brute, impose souvent un coût en temps trop important pour être utilisée.
      
• Les algorithmes gloutons
  Un algorithme glouton (greedy algorithm) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local.
  Au cours de la construction de la solution, l’algorithme résout une partie du problème puis se focalise ensuite sur le sous-problème restant à résoudre.
  La méthode gloutonne consiste à choisir des solutions locales optimales d'un problème dans le but d'obtenir une solution optimale globale au problème.
  • Le principal avantage des algorithmes gloutons est leur facilité de mise en œuvre.
  • Le principal défaut est qu'ils ne renvoient pas toujours la solution optimale nous le verrons.
  • Dans certaines situations dites canoniques, il arrive qu’ils renvoient non pas un optimum mais l’optimum d’un problème

 Top

2. Le problème du rendu de monnaie

Un achat dit en espèces se traduit par un échange de pièces et de billets. Dans la suite, les pièces désignent indifféremment les véritables pièces que les billets.

Supposons qu’un achat induise un rendu de 49 euros en considérant pour simplifier que les 'pièces' prennent les valeurs 1, 2, 5, 10, 20, 50, 100 euros. Quelles pièces peuvent être rendues ?

• \(49=4\times10+1\times 5 + 2\times2\) soit 7 pièces au total
  (Quatre pièces de 10 euros, 1 pièce de 5 euros et deux pièces de 2 euros.)
• ou \(49=9\times 5 + 2\times2\)  soit 11 pièces au total
• ou \(49=9\times 5 + 4\times1\)  soit 13 pièces au total
• ou \(49=49\times1\)  soit 49 pièces au total

Le problème du rendu de monnaie consiste à déterminier la solution avec le nombre minimal de pièces.

Rendre 49 euros avec un minimum de pièces est un problème d’optimisation. En pratique, tout individu met en œuvre un algorithme glouton.

1. Il choisit d’abord la plus grandeur valeur de monnaie, parmi 1, 2, 5, 10, 20 contenue dans 49 euros.
   En l’occurence, deux fois une pièce de 20 euros.
2. La somme de 9 euros restant à rendre, il choisit une pièce de 5 euros,
3. Puis deux pièces de 2 euros.

Solution optimale et système canonique du rendu de monnaie

Cette stratégie gagnante pour la somme de 49 euros l’est-elle pour n’importe quelle somme à rendre ?

• Un système canonique
  
  • On peut montrer que l'algorithme glouton du rendu de monnaie renvoie une solution optimale pour le système monétaire français
    $$\left \lbrace1 ,  2 , 5  , 10 , 20 , 50,100\right \rbrace$$
  • Pour cette raison, un tel système de monnaie est qualifié de canonique.
    
    
• Des systèmes non canoniques
  • D’autres systèmes ne sont pas canoniques. L’algorithme glouton ne répond alors pas de manière optimale.
  • Par exemple, avec le système \(\left \lbrace1 ,  3 , 6  , 12 , 24 , 30\right \rbrace\), l’algorithme glouton répond en proposant le rendu :
    \(49=30+12+6+1\) soit 4 pièces
    alors que la solution optimale est \(49=2\times24+1\), soit 3 pièces. 

  Top

3. Le TD sur les algorithmes gloutons et le rendu de monnaie

• Prérequis au TD

  • Python : liste, parcours de listes.
      

On cherche à implémenter un algorithme glouton de rendu de monnaie en ne considérant que des valeurs entières des pièces du système.
Par ailleurs, la plus petite pièce du système sera toujours 1, on est ainsi certain de pouvoir rendre la monnaie quelque soit la somme choisie.

Fonctionnement de l'algorithme glouton du rendu de monnaie

1. On choisit un système de monnaies, par exemple  $$systeme = \left \lbrace1 ,  2 , 5  , 10 , 20 , 50,100\right \rbrace$$
2. On choisit une valeur, par exemple \(valeur=49\) euros .
3. On choisit la plus grande 'pièce' du système inférieure à la valeur et on l'ajoute à la liste des pièces à rendre.
4. On calcule le reste à rendre et on recommence jusqu'à obtenir un reste à rendre nul.

Exercice 1

1. Ecrire une une fonction python qui reçoit deux arguments – la somme à rendre et le système de monnaie – et qui renvoie la liste des pièces choisies par l’algorithme glouton.
2. Tester votre fonction avec les valeurs et les systèmes proposés dans les exemples du cours ci-dessus.
3. Inventez un système non canonique différent de celui de l'exemple (mais toujours de valeur minimale 1) et trouver un exemple qui le prouve.
   Votre fonction devra donc donner une solution mais qui n'est pas optimale.
4. Complément : créer un programme (ou une autre fonction) qui va afficher toutes les informations suivantes :
   \(49=4\times10+1\times 5 + 2\times2\)
   Soit 7 pièces au total
   C'est à dire : Quatre pièces de 10 euros, 1 pièce de 5 euros et deux pièces de 2 euros.

Aide pour l'exercice 1

# valeurs des pièces du système choisi
systeme = [1,2,5,10,20,50,100]
# valeur à tester (par exemple 49 euros)
valeur=49
# indice de la première pièce à comparer à la somme à rendre
i = len(systeme) - 1

Exercice 2

• On cherche maintenant à généraliser notre algorithme avec le système de pièces et de billets utilisées en Europes et des valeurs décimales.
• On va donc considérer un système composé de pièces et de billets :
  • Les pièces (en euros) : 0,01 - 0,02  - 0,05 - 0,10 - 0,20 - 0,50 - 1 - 2 ;
  • Les billets (en euros)  : 5 - 10 - 20 - 50 - 100 - 200 - 500.

1. Modifier donc votre programme afin qu'il affiche le nombre les pièces à rendre et les billets.*
2.  Tester les avec plusieurs exemples.
3. Et si il n'y avait ni billet de 5, ni billet de 10 euros.
   Montrer avec un exemple bien choisi que la solution donnée par l'algorithme n'est pas optimale

Exercice 3 - Une pièce de 7 euros

• On peut se demander pourquyoi il n'y a pas de pièce de 7 euros par exemple.
• En fait c'est parce que si tel était le cas, l'algorithme glouton de rendu de monnaie ne serait plus optimal.

1. Tester votre algorithme en ajoutant une pièce de 7 euros dans le système.
2. Trouver un exemple qui renvoie une solution qui n'est pas optimale.

  Top

4. Le problème du sac à dos

Le problème du sac à dos, noté également KP (en anglais, Knapsack Problem) est un problème d'optimisation combinatoire. Il modélise une situation analogue au remplissage d'un sac à dos, ne pouvant supporter plus d'un certain poids, avec tout ou partie d'un ensemble donné d'objets ayant chacun un poids et une valeur.
Les objets mis dans le sac à dos doivent maximiser la valeur totale, sans dépasser le poids maximum.

Remarque historique

Le problème du sac à dos est l'un des 21 problèmes NP-complets de Richard Karp, exposés dans son article de 1972. Il est intensivement étudié depuis le milieu du XXe siècle et on trouve des références dès 1897, dans un article de George Ballard Mathews. La formulation du problème est fort simple, mais sa résolution est plus complexe.

Description du problème du sac à dos et stratégies

On dispose d’un sac pouvant supporter un poids maximal donné et de divers objets ayant chacun une valeur et un poids.
Il s’agit de choisir les objets à emporter dans le sac afin d’obtenir la valeur totale la plus grande tout en respectant la contrainte du poids maximal.

Ce problème peut se résoudre parforce brute, c’est-à-dire en testant tous les cas possibles. Mais ce type de résolution présente un problème d’efficacité. Son coût en fonction du nombre d’objets disponibles croît de manière exponentielle.

Nous pouvons envisager une stratégie gloutonne. Le principe d’un algorithme glouton est de faire le meilleur choix pour prendrele premier objet, puis le meilleur choix pour prendre le deuxième, et ainsi de suite. Plusieurs stratégies sont possibles : 

• Prendre l’objet qui a la plus grande valeur ;
• Prendre l’objet qui a le plus petit poids ;
• Prendre l’objet qui a le rapport valeur/poids le plus grand.

Un TP sur problème du sac à dos

• Un tp est disponible : le problème du sac à dos.

Articles Connexes 

{module [116]}

Details

Category: NSI

Published: 05 May 2019

Last Updated: 22 May 2023

NSI - Numérique et Sciences Informatiques

HTML (HyperText Markup Language) ,
PHP Hypertext Preprocessor
et Interation Client-Serveur : Exercices et applications

Prérequis au TD

1. Il faut impérativement avoir un environnement de travail PHP, c'est à dire un site Web ou un serveur installé sur votre ordinateur pour effectuer ce TD.
   Consulter si ce n'est pas le cas la page : PHP et Interation Client-Serveur : installation.
   
   
2. Il est par ailleurs nécessaire d'avoir traité le TD sur le Javascript : HTML (HyperText Markup Language) et Javascript

1. Programmer en PHP

Quelques remarques sur les fonctions, les structures conditionnels en PHP

• Les fonctions en PHP fonctionnent comme en Javascript. Le mot clé function permet de définir une fonction.
• Les paramètres sont écrits entre parenthèses précédés du symbole $ comme toute les variables.
• Le mot clé return permet de renvoyer une valeur.
• Il existe de nombreuses fonctions intégrées en PHP vous pouvez consulter ces sites de références au fur et à mesure des besoins.
  
  • Liste des fonctions PHP ;
  • Un tutoriel : https://www.w3schools.com/php/php_functions.asp
  • Un cours sur Openclassrooms : https://openclassrooms.com
• De même les structures conditionnelles if et if else fonctionnent comment en Javascript.
   
• Par exemple cette fonction renvoie le maximum des deux nombres

<?php
  function maximum($a,$b)
{
if ($a>$b)
    return $a;
else 
    return $b;
}
?>
  

• De même les structures itératives, les boucles for et while fonctionnent comment en Javascript.

Un exemple

L'exemple ci-dessous se sert d'une boucle for pour afficher un tableau à l'écran avec une boucles for et une boucle while . C'est magique.

<head>
  <title>
   PHP - Exemple 2
  </title>
  <meta charset="utf-8"/>
 </head>
 <body>
 <h1> PHP - Exemple 2 </h1>
 <table border="1">
  <tr>
   <?php
   for($i=1;$i<=10;$i=$i+1) // ou ($i=1;$i<=10;$i++)
   {
    echo "<td>$i</td>";
   }
   ?>
  </tr>
 </table>
 
 <p> </p>
 
 <table border="2">
  <tr>
   <?php
   $i = 1;
   while ($i <= 10) 
   {
    echo "<td>$i</td>";
	$i=$i+1;
	}
   ?>
  </tr>
 </table>
 
</body>
</html>

•  Lien vers le fichier .php sur le serveur : PHP-exemple2 / Code source.

Exercice 1
La fonction rand(a,b) renvoie un entier aléatoire compris entre a et b.
1. Ecrire un script qui choisit aléatoirement un nombre entre 1 et 15.
2. Et qui affiche le table de multiplication de ce nombre dans un tableau.
Toute amélioration est la bienvenue.

Exercice 2
La fonction rand(a,b) renvoie un entier aléatoire compris entre a et b.
Ecrire un script en php qui :
1. choisit 100 nombres aléatoires entre 0 et 100 ;
2. les affiche  ;
3. et affiche leur moyenne.
Toute amélioration est la bienvenue.

2. Interagir avec une page en PHP : les méthodes GET et POST

Un script PHP s'exécute sur le serveur lorsque l'utilisateur accède à un fichier par un lien. Ce script effectue un certain nombre d'instructions pour produire la page web demandée et s'arrête lorsque celle-ci est produite.
Comment faisons-nous pour passer une information d'une page à l'autre ? De l'utilisateur à la page .PHP ?

Par exemple, si je saisi mon compte utilisateur sur un site et qu'en cliquant je suis conduis vers la page de mon compte, comment cette page se souvient-elle du nom que j'ai écrit dans la page précédente ?

Il existe plusieurs solutions pour transmettre des informations d'une page aux autres :

• Cookies ;
• base de données ;
• fichiers textes ;
• la méthode  GET ;
• la méthode POST.

Nous allons étudier les méthodes GET et POST.

2a. La méthode GET
Interagir avec une page en PHP avec la méthode GET

• Vous pouvez consulter le cours sur openclassroom : https://openclassrooms.com

Les variables ne transitent pas toujours via un formulaire mais bien souvent par l'URL via la méthode GET.

L'URL (Uniform Resource Locator) sert à représenter une adresse sur le web comme celle du site www.math93.com.

Par exemple, après avoir fait une recherche sur Google, par exemple avec math93, la barre d'adresse contient une URL longue qui ressemble à ceci :

• Essayer : recherche Google math93

Dans cet exemple, les informations après le point d'interrogation sont des données que l'on fait transiter d'une page à une autre.

2a1. Former une URL pour envoyer des paramètres

Imaginons que votre site s'appelle math93.com et que vous avez une page PHP intitulée bonjour.php. Pour accéder à cette page, vous devez aller à l'URL suivante :

http://www.math93.com/bonjour.php

Pour envoyer des informations à la page bonjour.php, on va ajouter des informations à la fin de l'URL, comme ceci :

• On écrit les variables et les valeurs des variables après un point d'intérogation ? .
• On sépare les variables par le symbole & .
• La seule limite est la longueur de l'URL. En général il n'est pas conseillé de dépasser les 256 caractères.

2a2. Récupérer les valeurs des variables

Nous avons fait un lien vers le fichier php bonjour.php et à deux variables nom et prenom.

bonjour.php?nom=Galois&prenom=Evariste

Pour récupérer les valeurs des variables, on y accède via la variable $_GET.

• $_GET['nom'] .     à la valeur Galois ;  
  
• $_GET['prenom'] .  à la valeur Evariste ;

Par exemple on a ici avec le petit code en écrivant dant la console :

• https://www.math93.com/bonjour.php
• https://www.math93.com/bonjour.php?nom=Evariste&prenom=Galois

Essayer de changer les noms et prénoms dans l'adresse URL.

<head>
  <title>
   PHP - Exemple 3
  </title>
  <meta charset="utf-8"/>
 </head>
 <body>
 <h1> PHP - Exemple 3 </h1>
 <?php 
 // les variables existent-t-elles ?
 if(isset($_GET['nom']) and isset($_GET['prenom']))
 {// oui les variables existent 
    $lenom=$_GET['nom'];
    $leprenom=$_GET['prenom'];
    //echo "<p>Bonjour $_GET['prenom'] et $_GET['nom'] !</p>" ;
    echo "<p>Bonjour $leprenom   $lenom</p>" ;
 }
 else
 {
    echo "<p>Bonjour Madame ou Monsieur.</p>" ;
 }
 ?> 
</body>
</html>

• Remarque :  isset(var)   - Détermine si la variable var est déclarée et est différente de NULL.

Exercice 3
1. Ecrire une page qui prend deux nombres dans l'URL et affiche leur somme.
2. Modifier la page pour donner trois paramètres dans l'URL, deux nombres et une opération. Le résultat de l'opération sera affiché dans la page.
Toute amélioration est la bienvenue.

Exercice 4
1. Ecrire deux pages, la première choisissant un nombre au hasard entre -10 et 10
2. et contenant un lien vers la seconde qui affichera la racine carrée du nombre choisi, si cela est possible.
Toute amélioration est la bienvenue.

2a. La méthode POST
Interagir avec une page en PHP avec la méthode POST

Il existe une autre méthode pour passer des données d'une page à l'autre sans mentionner les valeurs dans l'URL.

Il s'agit de la méthode utilisée dans les formulaires

Un exemple

Reprenons l'exemple 3 avec le nom et le prénom.

1. On va donc écrire deux pages, la première une page HTML que l'on va nommer ex4-HTML.html, et la deuxième une page PHP l'on va nommer ex4-PHP.php
2. Afin de pouvoir accéder aux contenus envoyés par la méthode POST, il faut donner à chaque élément dont on veut récuperer les valeurs l'attribut name   .
3. Pour récupérer les valeurs des variables, on y accède via la variable $_POST.

• $_POST['nom'] .     à la valeur du nom entré ;   
  
• $_POST['prenom'] .  à la valeur du prénom entré ;

<!doctype html>
<html>
<head>
  <title>
   PHP - Exemple 4 - Méthode POST Fichier HTML
  </title>
  <meta charset="utf-8"/>
 </head>
 <body>
 <h1> PHP - Exemple 4 - Méthode POST Fichier HTML</h1>
  <form action="ex4-PHP.php" method="post">
  <label for="nom">Votre Nom :</label>  
  <input type="text" name="nom"> 
  <div> et </div> 
  <label for="prenom">Votre Prénom :</label>
  <input type="text" name="prenom">
  <input type="submit" value="Valider">
  </form>
</body>
</html>

<!doctype html>
<html>
<head>
  <title>
   PHP - Exemple 4 - Méthode POST Fichier PHP
  </title>
  <meta charset="utf-8"/>
 </head>
 <body>
 <h1> PHP - Exemple 4 - Méthode POST Fichier PHP </h1>
 <?php 
 // les variables existent-t-elles ?
 if(isset($_POST['nom']) and isset($_POST['prenom']))
 {// oui les variables existent 
    $lenom=$_POST['nom'];
    $leprenom=$_POST['prenom'];
    //echo "<p>Bonjour $_POST['prenom']   et $_POST['nom'] !</p>" ;
    echo "<p>Bonjour $leprenom    $lenom</p>" ;
 }
 else
 {
	echo "<p>Bonjour Madame ou Monsieur.</p>" ;
 }
 ?> 
</body>

• Lien vers le fichier .html sur le serveur : ex4-HTML.html .
• Remarque : Tous les paramètres de input : https://developer.mozilla.org/fr/docs/Web/HTML/Element/Input

Exercice 5
Reprendre les exercices 3 et 4 mais en utilisant la méthode POST et un formulaire.
Toute amélioration est la bienvenue.

Exercice 6 : un QCM
1. Ecrire deux pages, la première contenant un QCM avec au moins trois questions.
2. Les réponses seront proposées et l'utilisateur devra faire son choix par des cases à cocher.
3. La seconde page affichera le score obtenu.
Aide : Pour récupérer l'information "case cochée, c'est assez simple : la variable n'existe dans le post que si la case a été cochée.
Toute amélioration est la bienvenue.

Aide :

• https://www.zerocms.fr/PHP/formulaires-POST-url-GET-PHP.php
• Check-box et récupération 1
• https://apcpedagogie.com/recuperer-les-valeurs-des-checkbox-avec-php/

Articles Connexes 

{module [116]}

Details

Category: NSI

Published: 05 May 2019

Last Updated: 01 June 2021

NSI - Numérique et Sciences Informatiques
La recherche dichotomique

Prérequis au TD

• Python : liste, parcours de listes.

Présentation de la méthode de recherche par dichotomie

La recherche dichotomique, (en anglais : binary search), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié.

Le principe est le suivant :

• Trier le tableau de nombres ;
• Comparer l'élément que l'on cherche avec la valeur de la case au milieu du tableau ;
  • Si les valeurs sont égales, la tâche est accomplie,
  • sinon on recommence dans la moitié du tableau pertinente.

Le nombre d'itérations de la procédure, c'est-à-dire le nombre de comparaisons, est logarithmique en la taille du tableau.

Une introduction en vidéo de la recherche dichotomique

• Vidéo : la recherche dichotomique.

Le TD/Cours de recherche par dichotomie

• TD et cours : recherche par dichotomie.
  Les exercices proposés sont à traiter sur repl ou via Capytal.

Remarque et compléments

Les algorithmes proposés peuvent s'avérer être faux dans certains langages

Calcul du terme médian
Le problème vient de l'addition des indices \(a\) et \(b\) pour en trouver calculer la moyenne. En général, \(a\) et \(b\) sont des pointeurs, des adresses mémoires. Et leur somme peut dépasser la taille de représentation des adresses. En effet, ce n'est pas parce que \(a\) et \(b\) sont représentables en 64 bits que \(a+b\) l'est aussi. Il peut y avoir un dépassement.

Dans ce cas (qui peut arriver en pratique), le résultat obtenu en effectuant \((a+b)//2\) ne correspondra pas à la moyenne attendue.

Cette erreur est restée pendant plusieurs décennies dans divers bibliothèques (en Java, notamment) avant d'être détectée, (des compléments sur cette page).

Pour éviter cela, une version rigoureuse est

m = a + (b - a) // 2

En Python, cependant, on n'a pas ce problème (en Python3 du moins), car les entiers peuvent être arbitrairement grands.

Articles Connexes 

• Un cours très complet : la recherche dichotomique.
• Support eduscol : eduscol.

{module [116]}