Archives de catégorie : NSI

Langage SQL

Nous avons eu l’occasion d’étudier la structure d’une base de données relationnelle, nous allons maintenant apprendre à réaliser des requêtes, c’est-à-dire que nous allons apprendre à créer une base des données, créer des attributs, ajouter de données, modifier des données et enfin, nous allons surtout apprendre à interroger une base de données afin d’obtenir des informations.

Pour réaliser toutes ces requêtes, nous allons devoir apprendre un langage de requêtes : SQL (Structured Query Language). SQL est propre aux bases de données relationnelles, les autres types de bases de données utilisent d’autres langages pour effectuer des requêtes.

Pour créer une base de données et effectuer des requêtes sur cette dernière, nous allons utiliser le logiciel « DB Browser for SQLite » (il se stue dans echange\DB Browser for SQLite).

SQLite est un système de gestion de base de données relationnelle très répandu. Noter qu’il existe d’autres systèmes de gestion de base de données relationnelle comme MySQL ou PostgreSQL. Dans tous les cas, le langage de requête utilisé est le SQL (même si parfois on peut noter quelques petites différences). Ce qui sera vu ici avec SQLite pourra, à quelques petites modifications près, être utilisé avec, par exemple, MySQL.

Nous allons commencer par créer notre base de données :

À faire vous-même 1

Après avoir lancé le logiciel « DB Browser for SQLite », vous devriez obtenir ceci :

DB Browser for SQLite

Cliquez sur Nouvelle base de données. Après avoir choisi un nom pour votre base de données (par exemple « db_livres.db »), vous devriez avoir la fenêtre suivante :

DB Browser for SQLite

Cliquez alors sur Annuler

Notre base de données a été créée :

DB Browser for SQLite

mais pour l’instant elle ne contient aucune table (aucune relation), pour créer une table, cliquez sur l’onglet « Exécuter le SQL ». On obtient alors :

DB Browser for SQLite

Copiez-collez le texte ci-dessous dans la fenêtre « SQL 1 »

CREATE TABLE LIVRES
	(id INT, titre TEXT, auteur TEXT, ann_publi INT, note INT);

Cliquez ensuite sur le petit triangle situé au-dessus de la fenêtre SQL 1 Exécuter (ou appuyez sur F5), vous devriez avoir ceci :

DB Browser for SQLite

Comme indiqué dans la fenêtre, « Requête exécutée avec succès » !

Vous venez de créer votre première table.


Revenons sur cette première requête :

Le CREATE TABLE LIVRES ne devrait pas vous poser de problème : nous créons une nouvelle table nommée « LIVRES ».

La suite est à peine plus complexe :

nous créons ensuite les attributs :

  • id
  • titre
  • auteur
  • ann_pulbi
  • note

Nous avons pour chaque attribut précisé son domaine : id : entier (INT), titre : chaîne de caractères (TEXT), auteur : chaîne de caractères, ann_publi : entier et note : entier

L’attribut « id » va jouer ici le rôle de clé primaire. On peut aussi, par souci de sécurité (afin d’éviter que l’on utilise 2 fois la même valeur pour l’attribut « id »), modifier l’instruction SQL vue ci-dessus, afin de préciser que l’attribut « id » est bien notre clé primaire :

CREATE TABLE LIVRES
(id INT, titre TEXT, auteur TEXT, ann_publi INT, note INT, PRIMARY KEY (id));	

Notre système de gestion de base de données nous avertira si l’on tente d’attribuer 2 fois la même valeur à l’attribut »id ».

Nous allons maintenant ajouter des données :

À faire vous-même 2

Toujours dans l’onglet « Exécuter le SQL », après avoir effacé la fenêtre SQL 1, copiez-collez dans cette même fenêtre la requête ci-dessous :

INSERT INTO LIVRES(id,titre,auteur,ann_publi,note)
	VALUES
	(1,'1984','Orwell',1949,10),
	(2,'Dune','Herbert',1965,8),
	(3,'Fondation','Asimov',1951,9),
	(4,'Le meilleur des mondes','Huxley',1931,7),
	(5,'Fahrenheit 451','Bradbury',1953,7),
	(6,'Ubik','K.Dick',1969,9),
	(7,'Chroniques martiennes','Bradbury',1950,8),
	(8,'La nuit des temps','Barjavel',1968,7),
	(9,'Blade Runner','K.Dick',1968,8),
	(10,'Les Robots','Asimov',1950,9),
	(11,'La Planète des singes','Boulle',1963,8),
	(12,'Ravage','Barjavel',1943,8),
	(13,'Le Maître du Haut Château','K.Dick',1962,8),
	(14,'Le monde des Ā','Van Vogt',1945,7),
	(15,'La Fin de l’éternité','Asimov',1955,8),
	(16,'De la Terre à la Lune','Verne',1865,10);

Ici aussi, aucun problème, la requête a bien été exécutée :

DB Browser for SQLite

La table LIVRES contient bien les données souhaitées (onglet « Parcourir les données ») :

DB Browser for SQLite

Nous allons apprendre à effectuer des requêtes d’interrogation sur la base de données que nous venons de créer.

Toutes les requêtes se feront dans la fenêtre SQL 1 de l’onglet « Exécuter le SQL »

À faire vous-même 3

Saisissez la requête SQL suivante :

SELECT id, titre, auteur, ann_publi, note
FROM LIVRES	

puis appuyez sur le triangle (ou la touche F5)


Après un temps plus ou moins long, vous devriez voir s’afficher ceci :

DB Browser for SQLite

Comme vous pouvez le constater, notre requête SQL a permis d’afficher tous les livres. Nous avons ici 2 mots clés du langage SQL SELECT qui permet de sélectionner les attributs qui devront être « affichés » (je mets « affichés » entre guillemets, car le but d’une requête sql n’est pas forcément d’afficher les données) et FROM qui indique la table qui doit être utilisée.

Il est évidemment possible d’afficher seulement certains attributs (ou même un seul) :

À faire vous-même 4

Saisissez la requête SQL suivante :

SELECT titre, auteur
FROM LIVRES

Vérifiez que vous obtenez bien uniquement les titres et les auteurs des livres


À faire vous-même 5

Écrivez et testez une requête permettant d’obtenir uniquement les titres des livres.


N.B. Si vous désirez sélectionner tous les attributs, vous pouvez écrire :

SELECT *
FROM LIVRES

à la place de :

SELECT id, titre, auteur, ann_publi, note
FROM LIVRES

Pour l’instant nos requêtes affichent tous les livres, il est possible d’utiliser la clause WHERE afin d’imposer une (ou des) condition(s) permettant de sélectionner uniquement certaines lignes.

La condition doit suivre le mot-clé WHERE :

À faire vous-même 6

Saisissez et testez la requête SQL suivante :

SELECT titre, ann_publi
FROM LIVRES
WHERE auteur='Asimov'

Vérifiez que vous obtenez bien uniquement les livres écrits par Isaac Asimov.

À faire vous-même 7

Écrivez et testez une requête permettant d’obtenir uniquement les titres des livres écrits par Philip K.Dick.


Il est possible de combiner les conditions à l’aide d’un OR ou d’un AND

À faire vous-même 8

Saisissez et testez la requête SQL suivante :

SELECT titre, ann_publi
FROM LIVRES
WHERE auteur='Asimov' AND ann_publi>1953

Vérifiez que nous obtenons bien le livre écrit par Asimov publié après 1953 (comme vous l’avez sans doute remarqué, il est possible d’utiliser les opérateurs d’inégalités).

À faire vous-même 9

D’après vous, quel est le résultat de cette requête :

SELECT titre
FROM LIVRES
WHERE auteur='K.Dick' OR note>=8

À faire vous-même 10

Écrire une requête permettant d’obtenir les titres des livres publiés après 1945 qui ont une note supérieure ou égale à 9.


Il est aussi possible de rajouter la clause SQL ORDER BY afin d’obtenir les résultats classés dans un ordre précis.

À faire vous-même 11

Saisissez et testez la requête SQL suivante :

SELECT titre
FROM LIVRES
WHERE auteur='K.Dick' ORDER BY ann_publi

Nous obtenons les livres de K.Dick classés du plus ancien ou plus récent.


Il est possible d’obtenir un classement en sens inverse à l’aide de la clause DESC

À faire vous-même 12

Saisissez et testez la requête SQL suivante :

SELECT titre
FROM LIVRES
WHERE auteur='K.Dick' ORDER BY ann_publi DESC

Nous obtenons les livres de K.Dick classés du plus récent au plus ancien.

À faire vous-même 13

Que se passe-t-il quand la clause ORDER BY porte sur un attribut de type TEXT ?


Vous pouvez constater qu’une requête du type :

SELECT auteur
FROM LIVRES

affiche plusieurs fois certains auteurs (les auteurs qui ont écrit plusieurs livres présents dans la base de données)

Il est possible d’éviter les doublons grâce à la clause DISTINCT

À faire vous-même 14

Saisissez et testez la requête SQL suivante :

SELECT DISTINCT auteur
FROM LIVRES

Nous avons vu précédemment qu’une base de données peut contenir plusieurs relations (plusieurs tables).

À faire vous-même 15

Créez une nouvelle base de données que vous nommerez par exemple db_livres_auteurs.db


À faire vous-même 16

Créez une table AUTEURS(id INT, nom TEXT, prenom TEXT, ann_naissance INT, langue_ecriture TEXT) à l’aide d’une requête SQL.

À faire vous-même 17

Créez une table LIVRES(id INT, titre TEXT, id_auteur INT, ann_publi INT, note INT) à l’aide d’une requête SQL.

À faire vous-même 18

Ajoutez des données à la table AUTEURS à l’aide de la requête SQL suivante :

INSERT INTO AUTEURS
(id,nom,prenom,ann_naissance,langue_ecriture)
VALUES
(1,'Orwell','George',1903,'anglais'),
(2,'Herbert','Frank',1920,'anglais'),
(3,'Asimov','Isaac',1920,'anglais'),
(4,'Huxley','Aldous',1894,'anglais'),
(5,'Bradbury','Ray',1920,'anglais'),
(6,'K.Dick','Philip',1928,'anglais'),
(7,'Barjavel','René',1911,'français'),
(8,'Boulle','Pierre',1912,'français'),
(9,'Van Vogt','Alfred Elton',1912,'anglais'),
(10,'Verne','Jules',1828,'français');

À faire vous-même 19

Ajoutez des données à la table LIVRES à l’aide de la requête SQL suivante :

INSERT INTO LIVRES
(id,titre,id_auteur,ann_publi,note)
VALUES
(1,'1984',1,1949,10),
(2,'Dune',2,1965,8),
(3,'Fondation',3,1951,9),
(4,'Le meilleur des mondes',4,1931,7),
(5,'Fahrenheit 451',5,1953,7),
(6,'Ubik',6,1969,9),
(7,'Chroniques martiennes',5,1950,8),
(8,'La nuit des temps',7,1968,7),
(9,'Blade Runner',6,1968,8),
(10,'Les Robots',3,1950,9),
(11,'La Planète des singes',8,1963,8),
(12,'Ravage',7,1943,8),
(13,'Le Maître du Haut Château',6,1962,8),
(14,'Le monde des Ā',9,1945,7),
(15,'La Fin de l’éternité',3,1955,8),
(16,'De la Terre à la Lune',10,1865,10);

Nous avons 2 tables, grâce aux jointures nous allons pouvoir associer ces 2 tables dans une même requête.

En général, les jointures consistent à associer des lignes de 2 tables. Elles permettent d’établir un lien entre 2 tables. Qui dit lien entre 2 tables dit souvent clef étrangère et clef primaire.

Dans notre exemple l’attribut « id_auteur » de la tables LIVRES est bien une clé étrangère puisque cet attribut correspond à l’attribut « id » de la table « AUTEURS« .

À noter qu’il est possible de préciser au moment de la création d’une table qu’un attribut jouera le rôle de clé étrangère. Dans notre exemple, à la place d’écrire :

CREATE TABLE LIVRES
(id INT, titre TEXT, id_auteur INT, ann_publi INT, note INT, PRIMARY KEY (id));

on pourra écrire :

CREATE TABLE LIVRES
(id INT, titre TEXT, id_auteur INT, ann_publi INT, note INT, PRIMARY KEY (id), FOREIGN KEY (id_auteur) REFERENCES AUTEURS(id));

grâce à cette précision, sqlite sera capable de détecter les anomalies au niveau de clé étrangère : essayez par exemple d’ajouter un livre à la table LIVRES avec l’attribut « id_auteur » égal à 11 !

Passons maintenant aux jointures :

À faire vous-même 20

Saisissez et testez la requête SQL suivante :

SELECT *
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id

Le « FROM LIVRES INNER JOIN AUTEURS » permet de créer une jointure entre les tables LIVRES et AUTEURS (« rassembler » les tables LIVRES et AUTEURS en une seule grande table). Le « ON LIVRES.id_auteur = AUTEURS.id » signifie qu’une ligne quelconque A de la table LIVRES devra être fusionnée avec la ligne B de la table AUTEURS à condition que l’attribut id de la ligne A soit égal à l’attribut id_auteur de la ligne B.

Par exemple, la ligne 1 (id=1) de la table LIVRES (que l’on nommera dans la suite ligne A) sera fusionnée avec la ligne 1 (id=1) de la table AUTEURS (que l’on nommera dans la suite B) car l’attribut id_auteur de la ligne A est égal à 1 et l’attribut id de la ligne B est aussi égal à 1.

Autre exemple, la ligne 1 (id=1) de la table LIVRES (que l’on nommera dans la suite ligne A) ne sera pas fusionnée avec la ligne 2 (id=2) de la table AUTEURS (que l’on nommera dans la suite B’) car l’attribut id_auteur de la ligne A est égal à 1 alors que l’attribut id de la ligne B’ est égal à 2.

Cette notion de jointure n’est pas évidente, prenez votre temps pour bien réfléchir et surtout n’hésitez pas à poser des questions.

À faire vous-même 21

Saisissez et testez la requête SQL suivante :

SELECT *
FROM AUTEURS
INNER JOIN LIVRES ON LIVRES.id_auteur = AUTEURS.id

Comme vous pouvez le constater, le résultat est différent, cette fois-ci ce sont les lignes de la table LIVRES qui viennent se greffer sur la table AUTEURS.


Dans le cas d’une jointure, il est tout à fait possible de sélectionner certains attributs et pas d’autres :

À faire vous-même 22

Saisissez et testez la requête SQL suivante :

SELECT nom, prenom, titre
FROM AUTEURS
INNER JOIN LIVRES ON LIVRES.id_auteur = AUTEURS.id

À faire vous-même 23

Saisissez et testez la requête SQL suivante :

SELECT titre,nom, prenom
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id

Si un même nom d’attribut est présent dans les 2 tables (par exemple ici l’attribut id), il est nécessaire d’ajouter le nom de la table devant afin de pouvoir les distinguer (AUTEURS.id et LIVRES.id)

À faire vous-même 24

Saisissez et testez la requête SQL suivante :

SELECT titre,AUTEURS.id,nom, prenom
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id

Il est possible d’utiliser la clause WHERE dans le cas d’une jointure :

À faire vous-même 25

Saisissez et testez la requête SQL suivante :

SELECT titre,nom, prenom
FROM LIVRES
INNER JOIN AUTEURS ON LIVRES.id_auteur = AUTEURS.id
WHERE ann_publi>1950

Enfin, pour terminer avec les jointures, vous devez savoir que nous avons abordé la jointure la plus simple (INNER JOIN). Il existe des jointures plus complexes (CROSS JOIN, LEFT JOIN, RIGHT JOIN), ces autres jointures ne seront pas abordées ici.

Nous en avons terminé avec les requêtes d’interrogation, intéressons-nous maintenant aux requêtes de mise à jour (INSERT, UPDATE, DELETE).

Nous allons repartir avec une base de données qui contient une seule table :

À faire vous-même 26

Créez une nouvelle base de données que vous nommerez par exemple db_livres2.db


À faire vous-même 27

Créez une table LIVRES à l’aide de la requête SQL suivante :

CREATE TABLE LIVRES
(id INT, titre TEXT, auteur TEXT, ann_publi INT, note INT, PRIMARY KEY (id));

À faire vous-même 28

Ajoutez des données à la table LIVRES à l’aide de la requête SQL suivante :

INSERT INTO LIVRES
(id,titre,auteur,ann_publi,note)
VALUES
(1,'1984','Orwell',1949,10),
(2,'Dune','Herbert',1965,8),
(3,'Fondation','Asimov',1951,9),
(4,'Le meilleur des mondes','Huxley',1931,7),
(5,'Fahrenheit 451','Bradbury',1953,7),
(6,'Ubik','K.Dick',1969,9),
(7,'Chroniques martiennes','Bradbury',1950,8),
(8,'La nuit des temps','Barjavel',1968,7),
(9,'Blade Runner','K.Dick',1968,8),
(10,'Les Robots','Asimov',1950,9),
(11,'La Planète des singes','Boulle',1963,8),
(12,'Ravage','Barjavel',1943,8),
(13,'Le Maître du Haut Château','K.Dick',1962,8),
(14,'Le monde des Ā','Van Vogt',1945,7),
(15,'La Fin de l’éternité','Asimov',1955,8),
(16,'De la Terre à la Lune','Verne',1865,10);

Nous avons déjà eu l’occasion de voir la requête permettant d’ajouter une entrée (utilisation d’INSERT)

À faire vous-même 29

Que va faire cette requête ? Vérifiez votre réponse en l’exécutant et en faisant une requête « SELECT * FROM LIVRES« .

INSERT INTO LIVRES
(id,titre,auteur,ann_publi,note)
VALUES
(17,'Hypérion','Simmons',1989,8);

À faire vous-même 30

Écrivez et testez une requête permettant d’ajouter le livre de votre choix à la table LIVRES.


« UPDATE » va permettre de modifier une ou des entrées. Nous utiliserons « WHERE« , comme dans le cas d’un « SELECT« , pour spécifier les entrées à modifier.

Voici un exemple de modification :

À faire vous-même 31

Que va faire cette requête ? Vérifiez votre réponse en l’exécutant et en faisant une requête « SELECT * FROM LIVRES« .

UPDATE LIVRES
SET note=7
WHERE titre = 'Hypérion'

À faire vous-même 32

Écrivez une requête permettant d’attribuer la note de 10 à tous les livres écrits par Asimov publiés après 1950. Testez cette requête.


« DELETE » est utilisée pour effectuer la suppression d’une (ou de plusieurs) entrée(s). Ici aussi c’est le « WHERE » qui permettra de sélectionner les entrées à supprimer.

À faire vous-même 33

Que va faire cette requête ? Vérifiez votre réponse en l’exécutant et en faisant une requête « SELECT * FROM LIVRES« .

DELETE FROM LIVRES
WHERE titre='Hypérion'

À faire vous-même 34

Écrivez une requête permettant de supprimer les livres publiés avant 1945. Testez cette requête.

les listes, les piles et les files

De nombreux algorithmes « classiques » manipulent des structures de données plus complexes que des simples nombres (nous aurons l’occasion d’en voir plusieurs cette année). Nous allons ici voir quelques-unes de ces structures de données. Nous allons commencer par des types de structures relativement simples : les listes, les piles et les files. Ces trois types de structures sont qualifiés de linéaires.

Les listes

Une liste est une structure de données permettant de regrouper des données. Une liste L est composée de 2 parties : sa tête (souvent noté car), qui correspond au dernier élément ajouté à la liste, et sa queue (souvent noté cdr) qui correspond au reste de la liste.

Le langage de programmation Lisp (inventé par John McCarthy en 1958) a été un des premiers langages de programmation à introduire cette notion de liste (Lisp signifie « list processing »). Voici les opérations qui peuvent être effectuées sur une liste :

  • créer une liste vide (L=vide() on a créé une liste L vide)
  • tester si une liste est vide (estVide(L) renvoie vrai si la liste L est vide)
  • ajouter un élément en tête de liste (ajouteEnTete (x,L) avec L une liste et x l’élément à ajouter)
  • supprimer la tête x d’une liste L et renvoyer cette tête x (supprEnTete(L))
  • Compter le nombre d’éléments présents dans une liste (compte(L) renvoie le nombre d’éléments présents dans la liste L)

La fonction cons permet d’obtenir une nouvelle liste à partir d’une liste et d’un élément (L1 = cons(x,L)). Il est possible « d’enchaîner » les cons et d’obtenir ce genre de structure : cons(x, cons(y, cons(z,L)))

Exemples :

Voici une série d’instructions (les instructions ci-dessous s’enchaînent):

  • L=vide() => on a créé une liste vide
  • estVide(L) => renvoie vrai
  • ajoutEnTete(3,L) => La liste L contient maintenant l’élément 3
  • estVide(L) => renvoie faux
  • ajoutEnTete(5,L) => la tête de la liste L correspond à 5, la queue contient l’élément 3
  • ajoutEnTete(8,L) => la tête de la liste L correspond à 8, la queue contient les éléments 3 et 5
  • t = supprEnTete(L) => la variable t vaut 8, la tête de L correspond à 5 et la queue contient l’élément 3
  • L1 = vide()
  • L2 = cons(8, cons(5, cons(3, L1))) => La tête de L2 correspond à 8 et la queue contient les éléments 3 et 5

À faire vous-même 1

Voici une série d’instructions (les instructions ci-dessous s’enchaînent), expliquez ce qui se passe à chacune des étapes :

  • L = vide()
  • ajoutEnTete(10,L)
  • ajoutEnTete(9,L)
  • ajoutEnTete(7,L)
  • L1 = vide()
  • L2 = cons(5, cons(4, cons(3, cons (2, cons(1, cons(0,L1))))))

Les piles

On retrouve dans les piles une partie des propriétés vues sur les listes. Dans les piles, il est uniquement possible de manipuler le dernier élément introduit dans la pile. On prend souvent l’analogie avec une pile d’assiettes : dans une pile d’assiettes la seule assiette directement accessible et la dernière assiette qui a été déposée sur la pile.

Les piles sont basées sur le principe LIFO (Last In First Out : le dernier rentré sera le premier à sortir). On retrouve souvent ce principe LIFO en informatique.

Voici les opérations que l’on peut réaliser sur une pile :

  • on peut créer une pile
  • on peut savoir si une pile est vide (pile_vide?)
  • on peut empiler un nouvel élément sur la pile (push)
  • on peut récupérer l’élément au sommet de la pile tout en le supprimant. On dit que l’on dépile (pop)
  • on peut accéder à l’élément situé au sommet de la pile sans le supprimer de la pile (sommet)
  • on peut connaitre le nombre d’éléments présents dans la pile (taille)

Exemples :

Soit une pile P composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le sommet de la pile est 22) Pour chaque exemple ci-dessous on repart de la pile d’origine :

  • pop(P) renvoie 22 et la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7 et 19 (le sommet de la pile est 19)
  • push(P,42) la pile P est maintenant composée des éléments suivants : 12, 14, 8, 7, 19, 22 et 42
  • sommet(P) renvoie 22, la pile P n’est pas modifiée
  • si on applique pop(P) 6 fois de suite, pile_vide?(P) renvoie vrai
  • Après avoir appliqué pop(P) une fois, taille(P) renvoie 5

À faire vous-même 2

Soit une pile P composée des éléments suivants : 15, 11, 32, 45 et 67 (le sommet de la pile est 67). Quel est l’effet de l’instruction pop(P)


Les files

Comme les piles, les files ont des points communs avec les listes. Différences majeures : dans une file on ajoute des éléments à une extrémité de la file et on supprime des éléments à l’autre extrémité. On prend souvent l’analogie de la file d’attente devant un magasin pour décrire une file de données.

Les files sont basées sur le principe FIFO (First In First Out : le premier qui est rentré sera le premier à sortir. Ici aussi, on retrouve souvent ce principe FIFO en informatique.

Voici les opérations que l’on peut réaliser sur une file :

  • on peut savoir si une file est vide (file_vide?)
  • on peut ajouter un nouvel élément à la file (ajout)
  • on peut récupérer l’élément situé en bout de file tout en le supprimant (retire)
  • on peut accéder à l’élément situé en bout de file sans le supprimer de la file (premier)
  • on peut connaitre le nombre d’éléments présents dans la file (taille)

Exemples :

Soit une file F composée des éléments suivants : 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 12). Pour chaque exemple ci-dessous on repart de la file d’origine :

  • ajout(F,42) la file F est maintenant composée des éléments suivants : 42, 12, 14, 8, 7, 19 et 22 (le premier élément rentré dans la file est 22 ; le dernier élément rentré dans la file est 42)
  • retire(F) la file F est maintenant composée des éléments suivants : 12, 14, 8, 7, et 19 (le premier élément rentré dans la file est 19 ; le dernier élément rentré dans la file est 12)
  • premier(F) renvoie 22, la file F n’est pas modifiée
  • si on applique retire(F) 6 fois de suite, file_vide?(F) renvoie vrai
  • Après avoir appliqué retire(F) une fois, taille(F) renvoie 5.

À faire vous-même 3

Soit une file F composée des éléments suivants : 1, 12, 24, 17, 21 et 72 (le premier élément rentré dans la file est 72 ; le dernier élément rentré dans la file est 1). Quel est l’effet de l’instruction ajout(F,25)


Types abstraits et représentation concrète des données

Nous avons évoqué ci-dessus la manipulation des types de données (liste, pile et file) par des algorithmes, mais, au-delà de la beauté intellectuelle de réfléchir sur ces algorithmes, le but de l’opération est souvent, à un moment ou un autre, de « traduire » ces algorithmes dans un langage compréhensible pour un ordinateur (Python, Java, C,…). On dit alors que l’on implémente un algorithme. Il est donc aussi nécessaire d’implémenter les types de données comme les listes, les piles ou les files afin qu’ils soient utilisables par les ordinateurs. Les listes, les piles ou les files sont des « vues de l’esprit » présent uniquement dans la tête des informaticiens, on dit que ce sont des types abstraits de données (ou plus simplement des types abstraits). L’implémentation de ces types abstrait, afin qu’ils soient utilisables par une machine, est loin d’être une chose triviale. L’implémentation d’un type de données dépend du langage de programmation. Il faut, quel que soit le langage utilisé, que le programmeur retrouve les fonctions qui ont été définies pour le type abstrait (pour les listes, les piles et les files cela correspond aux fonctions définies ci-dessus). Certains types abstraits ne sont pas forcément implémentés dans un langage donné, si le programmeur veut utiliser ce type abstrait, il faudra qu’il le programme par lui-même en utilisant les « outils » fournis par son langage de programmation.

Pour implémenter les listes (ou les piles et les files), beaucoup de langages de programmation utilisent 2 structures : les tableaux et les listes chaînées.

Un tableau est une suite contiguë de cases mémoires (les adresses des cases mémoire se suivent) :

File

Le système réserve une plage d’adresse mémoire afin de stocker des éléments.

File

La taille d’un tableau est fixe : une fois que l’on a défini le nombre d’éléments que le tableau peut accueillir, il n’est pas possible modifier sa taille. Si l’on veut insérer une donnée, on doit créer un nouveau tableau plus grand et déplacer les éléments du premier tableau vers le second tout en ajoutant la donnée au bon endroit !

Dans certains langages de programmation, on trouve une version « évoluée » des tableaux : les tableaux dynamiques. Les tableaux dynamiques ont une taille qui peut varier. Il est donc relativement simple d’insérer des éléments dans le tableau. Ce type de tableaux permet d’implémenter facilement le type abstrait liste (de même pour les piles et les files)

À noter que les « listes Python » (listes Python) sont des tableaux dynamiques. Attention de ne pas confondre avec le type abstrait liste défini ci-dessus, ce sont de « faux amis ».Filetableau dynamique

Autre type de structure que l’on rencontre souvent et qui permet d’implémenter les listes, les piles et les files : les listes chaînées.

Dans une liste chaînée, à chaque élément de la liste on associe 2 cases mémoire : la première case contient l’élément et la deuxième contient l’adresse mémoire de l’élément suivant.

Il est relativement facile d’insérer un élément dans une liste chaînée :

Il est aussi possible d’implémenter les types abstraits en utilisant des structures plus complexes que les tableaux et les listes chaînées. Par exemple, en Python, il est possible d’utiliser les tuples pour implémenter le type abstrait liste :

À faire vous-même 4

Étudiez attentivement les fonctions suivantes :


def vide():
    return None
def cons(x,L):
    return(x,L)
def ajouteEnTete(L,x):
    return cons(x,L)
def supprEnTete(L):
    return (L[0],L[1])
def estVide(L):
    return L is None
def compte(L):
    if estVide(L):
        return 0
    return 1 + compte(L[1])
		

À faire vous-même 5

Après avoir saisi et exécuté le programme étudié au « À faire vous-même 4 », tapez successivement les commandes suivantes dans une console Python :

  • L = vide()
  • estVide(L)
  • L = cons(5, cons(4, cons(3, cons(2, cons(1, cons(0,L))))))
  • estVide(L)
  • compte(L)
  • L = ajouteEnTete(L,6)
  • compte(L)
  • x, L=supprEnTete(L)
  • x
  • compte(L)
  • x, L=supprEnTete(L)
  • x
  • compte(L)

À faire vous-même 6

Étudiez l’implémentation des piles et des files en Python en vous aidant de la documentation officielle (5.1.1 et 5.1.2).

Exercices sur les piles et les files


FICHE REVISION

Auteur : David Roche

Algorithmes gloutons


Présentation des d’algorithmes gloutons avec exemples et TD. cet article est une copie d’un article du site www.math93.com/ , vous pouvez le voir ici .

Voici une petite vidéo sur les algorithmes Glouton

  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.

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


1.1. 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 ;
  • la recherche d’un plus court chemin dans un graphe ;
  • le problème du voyageur de commerce.

1.2. 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’il ne renvoie 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

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 on 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×10+1×5+2×2

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×5+2×2  soit 11 pièces au total ou 49=9×5+4×1  soit 13 pièces au total ou 49=49×1

  •   soit 49 pièces au total

Le problème du rendu de monnaie consiste à déterminer 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, contenue dans 49 euros.
    En l’occurrence, quatre fois une pièce de 10 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
      {1,2,5,10,20,50,100}
    • 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 {1,3,6,12,24,30},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×24+1

  • soit 3 pièces. 

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=[1,2,5,10,20,50,100]
  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. Écrire 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×10+1×5+2×2
    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:

  • Etape 1
    • Définissons le système de pièces à l’aide d’un tableau nommé  systeme constitué des valeurs des pièces classées par valeurs croissantes (de plus petite pièce 1).
    • On définit aussi une valeur à tester, les 49 euros de l’exemple ci-dessus, dans la variable valeur.
    • Ainsi que l’indice i de la plus grande des pièces de systeme.
# 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
  • Etape 2 : Fonctionnement de l’algorithme
    • On cherche à déterminer les pièces à rendre pour la variable valeur.
    • Initialisations
      • La somme à rendre à rendre est initialement stockée dans la variable somme_a_rendre. On l’initialise donc à  valeur.
      • liste_pieces, la liste des pièces à rendre est initialisée à une liste vide
      • i = len(systeme) - 1 : indice de la première pièce à comparer à la somme à rendre
    • On boucle tant que somme_a_rendre > 0
      • La variable piece prend la valeur de la pièce de systeme d’indice i
      • Si somme_a_rendre < piece
        • Alors i pend la valeur i-1
      • Sinon
        • alors on ajoute la piece à la liste des pièces à rendre liste_pieces
        • on enlève la valeur de piece de somme_a_rendre
    • On renvoie la liste : liste_pieces

Exercice 2

  • On cherche maintenant à généraliser notre algorithme avec le système de pièces et de billets utilisées en Europe 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 pourquoi 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.

Algorithme des k plus proches voisins

  1. Introduction
    L’algorithme des k plus proches voisins appartient à la famille des algorithmes d’apprentissage automatique (machine learning).
    L’idée d’apprentissage automatique ne date pas d’hier, puisque le terme de machine learning a été utilisé pour la première fois par
    l’informaticien américain Arthur Samuel en 1959. Les algorithmes d’apprentissage automatique ont connu un fort regain d’intérêt
    au début des années 2000 notamment grâce à la quantité de données disponibles sur internet.
    L’algorithme des k plus proches voisins est un algorithme d’apprentissage supervisé, il est nécessaire d’avoir des données labellisées. À partir d’un ensemble E de données labellisées, il sera possible de classer (déterminer le label) d’une nouvelle donnée (donnée n’appartenant pas à E). À noter qu’il est aussi possible d’utiliser l’algorithme des k plus proches voisins à des fins de régression (on cherche à déterminer une valeur à la place d’une classe), mais cet aspect des choses ne sera pas abordé ici. L’algorithme des k plus proches voisins est une bonne introduction aux principes des algorithmes d’apprentissage automatique, il est en effet relativement simple à appréhender (l’explication donnée aux élèves peut être très visuelle). Cette première approche des algorithmes d’apprentissage peut aussi amener les élèves à réfléchir sur l’utilisation de leurs données personnelles (même si ce sujet a déjà abordé auparavant) : de nombreuses sociétés (exemple les GAFAM) utilisent les données concernant leurs utilisateurs afin de ”nourrir” des algorithmes de machine learning qui permettront à ces sociétés d’en savoir toujours plus sur nous et ainsi de mieux cerné nos ”besoins” en termes de consommation.
  1. Principe de l’algorithme
    L’algorithme de k plus proches voisins ne nécessite pas de phase d’apprentissage à proprement parler, il faut juste stocker le jeu de
    données d’apprentissage.
    Soit un ensemble E contenant n données labellisées : E = {(yi
    , x⃗i)} avec i compris entre 1 et n, où yi correspond à la classe
    (le label) de la donnée i et où le vecteur x⃗i de dimension p (x⃗i = (x1i
    , x2i, …, xpi)) représente les variables prédictrices de la donnée i. Soit une donnée u qui n’appartient pas à E et qui ne possède pas de label (u est uniquement caractérisée par un vecteur x⃗u de dimension p). Soit d une fonction qui renvoie la distance entre la donnée u et une donnée quelconque appartenant à E. Soit un entier k inférieur ou égal à n. Voici le principe de l’algorithme de k plus proches voisins :
    ▷ On calcule les distances entre la donnée u et chaque donnée appartenant à E à l’aide de la fonction d
    ▷ On retient les k données du jeu de données E les plus proches de u
    ▷ On attribue à u la classe qui est la plus fréquente parmi les k données les plus proches.
  1. Étude d’un exemple
    3.1. Les données
    Nous avons choisi ici de nous baser sur le jeu de données ”iris de Fisher” (il existe de nombreuses autres possibilités). Ce jeu de
    données est composé de 50 entrées, pour chaque entrée nous avons :
    ▷ la longueur des sépales (en cm)
    ▷ la largeur des sépales (en cm)
    ▷ la longueur des pétales (en cm)
    ▷ la largeur des pétales (en cm)
    ▷ l’espèce d’iris : Iris setosa, Iris virginica ou Iris versicolor (label)
    Il est possible de télécharger ces données au format csv, par exemple sur le site GitHub Gist ou en le téléchargeant ici
    Une fois ces données téléchargées, Il est nécessaire de les modifier à l’aide d’un tableur :
    ▷ dans un souci de simplification, nous avons choisi de travailler uniquement sur la taille des pétales, nous allons donc supprimer les colonnes ”sepal_length” et ”sepal_width”
    ▷ il est nécessaire d’encoder les espèces avec des chiffres : 0 pour Iris setosa, 1 pour Iris virginica et 2 pour Iris versicolor (ce
    processus d’encodage des données textuelles est relativement classique en apprentissage automatique).
    3.2. Bibliothèques Python utilisées
    Nous allons utiliser 3 bibliothèques Python :
    ▷ Pandas [3] qui va nous permettre d’importer les données issues du fichier csv
    ▷ Matplotlib [4] qui va nous permettre de visualiser les données (tracer des graphiques)
    ▷ Scikit-learn [5] qui propose une implémentation de l’algorithme des k plus proches voisins.
    Ces bibliothèques sont facilement installables notamment en utilisant la distribution Anaconda (ou Miniconda).
    3.3. Première visualisation des données
    Une fois le fichier csv modifié, il est possible d’écrire un programme permettant de visualiser les données sous forme de graphique
    (abscisse : ”petal_length”, ordonnée : ”petal_width”) :
import pandas
import matplotlib.pyplot as plt
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')
plt.scatter(2.5, 0.75, color='k')
plt.legend()
plt.show()
FIGURE 1 – Représentation graphique des données
FIGURE 1 – Représentation graphique des données

3.4. Utilisation de l’algorithme des k plus proches voisins Le graphique ci-dessus (figure 1) montre que les 3 classes (Iris setosa, Iris virginica et Iris versicolor) sont relativement bien séparées. On peut alors ajouter une donnée non labellisée n’appartenant pas à l’ensemble d’origine (voir figure 2) :

FIGURE 2 – Ajout d’une donnée non labellisée

Dans l’exemple ci-dessus (figure 2) les élèves n’auront aucune difficulté à déterminer l’espèce de l’iris qui a été ajouté au jeu de données.
Dans certains cas (exemple : largeur pétale = 0,75 cm ; longueur pétale = 2,5 cm) il est un peu plus difficile de se prononcer ”au premier coup d’oeil” (voir figure 3) :

FIGURE 3 – Cas plus difficile…



À partir de l’exemple ci-dessus (voir figure 3), il est possible de demander aux élèves de proposer une méthode permettant de traiter
ce genre de cas litigieux. L’enseignant peut, grâce à une série de ”questions-réponses”, amener doucement les élèves à la solution
proposée par l’algorithme des k plus proches voisins :
▷ on calcule la distance entre notre point (largeur du pétale = 0,75 cm ; longueur du pétale = 2,5 cm) et chaque point issu du
jeu de données ”iris” (à chaque fois c’est un calcul de distance entre 2 points tout ce qu’il y a de plus classique) ;
▷ on sélectionne uniquement les k distances les plus petites (les k plus proches voisins) ;

▷ parmi les k plus proches voisins, on détermine quelle est l’espèce majoritaire. On associe à notre ”iris mystère” cette ”espèce
majoritaire parmi les k plus proches voisins”.
Dans l’exemple évoqué ci-dessus (largeur pétale = 0,75 cm ; longueur pétale = 2,5 cm), pour k=3, nous obtenons graphiquement :

FIGURE 4 – 3 plus proches voisins dans le cas : largeur pétale = 0,75 cm ; longueur pétale = 2,5 cm

Un iris ayant une largeur de pétale égale à 0,75 cm et une longueur de pétale égale à 2,5 cm a une ”forte” probabilité (cette notion
de probabilité d’obtenir un résultat correct grâce à cet algorithme, bien que très intéressante, pourra difficilement être abordée avec
des élèves de première) d’appartenir à l’espèce setosa.

3.5. Utilisation de scikit-learn (à installer si absente de votre éditeur)
La bibliothèque Python scikit-learn propose un grand nombre d’algorithmes lié à l’apprentissage automatique (c’est sans aucun
doute la bibliothèque la plus utilisée en apprentissage automatique). Parmi tous ces algorithmes, scikit-learn propose l’algorithme
des k plus proches voisins. Voici un programme Python permettant de résoudre le problème évoqué ci-dessus (largeur pétale = 0,75
cm ; longueur pétale = 2,5 cm) :

import pandas
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier

#traitement CSV
iris=pandas.read_csv("iris.csv")
x=iris.loc[:,"petal_length"]
y=iris.loc[:,"petal_width"]
lab=iris.loc[:,"species"]
#fin traitement CSV

#valeurs
longueur=2.5
largeur=0.75
k=3
#fin valeurs

#graphique
plt.scatter(x[lab == 0], y[lab == 0], color='g', label='setosa')
plt.scatter(x[lab == 1], y[lab == 1], color='r', label='virginica')
plt.scatter(x[lab == 2], y[lab == 2], color='b', label='versicolor')
plt.scatter(longueur, largeur, color='k')
plt.legend()
#fin graphique

#algo knn
d=list(zip(x,y))
model = KNeighborsClassifier(n_neighbors=k)
model.fit(d,lab)
prediction= model.predict([[longueur,largeur]])
#fin algo knn

#Affichage résultats
txt="Résultat : "
if prediction[0]==0:
    txt=txt+"setosa"
if prediction[0]==1:
    txt=txt+"virginica"
if prediction[0]==2:
    txt=txt+"versicolor"
plt.text(3,0.5, f"largeur : {largeur} cm longueur : {longueur} cm", fontsize=12)
plt.text(3,0.3, f"k : {k}", fontsize=12)
plt.text(3,0.1, txt, fontsize=12)
#fin affichage résultats

plt.show()

Nous obtenons le résultat suivant (voir figure 5) :

FIGURE 5 – 3 plus proches voisins à l’aide de scikit-learn dans le cas : largeur pétale = 0,75 cm ; longueur pétale = 2,5 cm

Il est ensuite possible de demander aux élèves de m le programme ci-dessus afin d’étudier les changements induits par la
modification du paramètre k (notamment pour k=5) en gardant toujours les mêmes valeurs de largeur et de longueur (largeur pétale
= 0,75 cm ; longueur pétale = 2,5 cm).
Pour terminer, il est aussi possible de demander aux élèves de travailler avec d’autres valeurs de longueur et largeur.

  1. Possibilité de projet
    Il est possible, dans le cadre d’un projet, de faire travailler les élèves sur un autre jeu de données, par exemple, ”Prédire les survivants
    du Titanic”. Le jeu de données peut être récupéré sur le site kaggle [6]. Le label est ”survivant” ou ”décédé”. Il sera nécessaire de
    retravailler les données comme nous l’avons fait pour le jeu de données ”Iris” (supprimer des colonnes, encodage…). Dans ce projet
    il sera possible de faire travailler les élèves sur des vecteurs d’entrée de dimension supérieure à 2 (le genre, l’âge, la classe occupée
    par le passager sur le bateau, …).

voici un lien vers le projet Titanic développé par Benoit Fourlegnie:

projet titanic

Mini projet dictionnaire

Projet

En utilisant les connaissances acquises jusqu’à présent, vous allez écrire un programme de gestion de répertoire téléphonique.

Cahier des charges

Ce programme devra proposer le menu suivant à l’utilisateur :

0-quitter
1-écrire dans le répertoire
2-rechercher dans le répertoire

3-mettre les numéros au format internationale
Votre choix ?

Si le choix est 0 : Le programme sera stoppé.

Si le choix est 1 :

L’utilisateur devra saisir un nom ou un prénom ou 0 s’il veut terminer la saisie ( » Nom (0 pour terminer) : « ….) :

  • L’utilisateur entre 0 => le programme devra le renvoyer vers le menu
  • L’utilisateur entre un nom ou prénom => le programme devra lui demander de saisir le numéro de téléphone correspondant au nom. Une fois le numéro saisi, le programme devra lui proposer d’entrer un nouveau nom (ou 0 pour terminer)…

exemple de saisie d’un utilisateur (toto)

Si le choix est 2 :

L’utilisateur devra saisir le nom recherché ( » Entrer un nom : « ), ou le numéro de téléphone ( » Entrer un numéro : « ).

  • Si le nom recherché est présent dans le répertoire, le programme devra afficher  » Le numéro recherché est :  » suivi du numéro de téléphone correspondant au nom saisi.
  • Si le nom recherché est absent du répertoire, le programme devra afficher  » Inconnu « .
  • …….

L’utilisateur est ensuite redirigé vers le menu principal.

recherche des utilisateurs (toto et titi)

Les noms, prénoms et numéros de téléphone devront être stockés dans un dictionnaire, le nom ou le prénom seront la clé et le numéro de téléphone sera la valeur associée à la clé.

Votre programme devra être composé au minimum de 3 fonctions : une fonction « menu », une fonction « lecture », et une fonction « ecriture »…….

Pensez à commenter votre programme, bien expliquer ce que doit faire vos fonctions et les différents tests que vous prévoyez.


Dictionnaires

Nous allons maintenant étudier un autre type abstrait de données : les dictionnaires aussi appelés tableau associatif.

On retrouve une structure qui ressemble, à première vue, beaucoup à un tableau (à chaque élément on associe un indice de position). Mais au lieu d’associer chaque élément à un indice de position, dans un dictionnaire, on associe chaque élément (on parle de valeur dans un dictionnaire) à une clef, on dit qu’un dictionnaire contient des couples clef:valeur (chaque clé est associée à une valeur). Exemples de couples clé:valeur => prenom:Kevin, nom:Durand, date-naissance:17-05-2005. prenom, nom et date sont des clés ; Kevin, Durand et 17-05-2005 sont des valeurs.

Voici les opérations que l’on peut effectuer sur le type abstrait dictionnaire :

  • ajout : on associe une nouvelle valeur à une nouvelle clé
  • modif : on modifie un couple clé:valeur en remplaçant la valeur courante par une autre valeur (la clé restant identique)
  • suppr : on supprime une clé (et donc la valeur qui lui est associée)
  • rech : on recherche une valeur à l’aide de la clé associée à cette valeur.

Exemples : Soit le dictionnaire D composé des couples clé:valeur suivants => prenom:Kevin, nom:Durand, date-naissance:17-05-2005. Pour chaque exemple ci-dessous on repart du dictionnaire d’origine :

  • ajout(D,tel:06060606) ; le dictionnaire D est maintenant composé des couples suivants : prenom:Kevin, nom:Durand, date-naissance:17-05-2005, tel:06060606
  • modif(D,nom:Dupont) ; le dictionnaire D est maintenant composé des couples suivants : prenom:Kevin, nom:Dupont, date-naissance:17-05-2005
  • suppr(D,date-naissance) ; le dictionnaire D est maintenant composé des couples suivants : prenom:Kevin, nom:Durand
  • rech(D,prenom) ; la fonction retourne Kevin

L’implémentation des dictionnaires dans les langages de programmation peut se faire à l’aide des tables de hachage. Les tables de hachages ainsi que les fonctions de hachages qui sont utilisées pour construire les tables de hachages, ne sont pas au programme de NSI. Cependant, l’utilisation des fonctions de hachages est omniprésente en informatique, il serait donc bon, pour votre « culture générale informatique », de connaitre le principe des fonctions de hachages. Voici un texte qui vous permettra de comprendre le principe des fonctions de hachages : c’est quoi le hachage . Pour avoir quelques idées sur le principe des tables de hachages, je vous recommande le visionnage de cette vidéo : wandida : les tables de hachage

Si vous avez visionné la vidéo de wandida, vous avez déjà compris que l’algorithme de recherche dans une table de hachage a une complexité O(1) (le temps de recherche ne dépend pas du nombre d’éléments présents dans la table de hachage), alors que la complexité de l’algorithme de recherche dans un tableau non trié est O(n). Comme l’implémentation des dictionnaires s’appuie sur les tables de hachage, on peut dire que l’algorithme de recherche d’un élément dans un dictionnaire a une complexité O(1) alors que l’algorithme de recherche d’un élément dans un tableau non trié a une complexité O(n).

Python propose une implémentation des dictionnaires, nous avons déjà étudié cette implémentation l’année dernière, n’hésitez pas à vous référer à la ressource proposée l’an passé : les dictionnaires en Python

Documentation Dictionnaires python

Mini projet Répertoire téléphonique

Auteur : David Roche

Révisions de Première (2 séances)

Description

Un administrateur de réseau pédagogique a créé des comptes utilisateurs à partir de données issues des bases du rectorat.

Le format du fichier qu’il a ainsi récupéré est au format csv. Les utilisateurs sont classés par ordre alphabétique.

L’administrateur, par soucis de simplification, souhaite disposer d’un fichier csv par classe, avec les utilisateurs de cette classe par ordre alphabétique.

On vous demande de créer un programme python qui permettra ce traitement. Dans les fichiers de classe, on retrouvera les mêmes champs que dans le fichier original. Chaque fichier créé contiendra les noms des utilisateurs triés par ordre alphabétique.

Exemple à partir du fichier « utilisateurs_simple.csv » :

Le programme devra créer 3 fichiers : « 1RICIMTB.csv » – « 1TMA .csv » – « 1UFA.csv » contenant chacun les utilisateurs de la classe correspondante, classés dans l’ordre alphabétique.

1RICIMTB.csv
1CAPT.csv
1UFA

Fichier de tous les utilisateurs :

Fichier simplifié des utilisateurs (pour mise au point) :

Pour aller plus loin…

Le fichier original est sous la forme suivante (image ci-dessous). Les champs sont différemment organisés et les noms d’utilisateurs ne sont pas classés dans l’ordre alphabétique. Il s’agira donc de les classer par ordre alphabétique dans les fichiers de classe…z

Ressource :

« Utilisation du module csv dans Python » (issu du site https://pythonforge.com/module-csv-lire-ecrire/)

Linux : les commandes de base en ligne de commande

À la « préhistoire » des systèmes d’exploitation, ces derniers étaient dépourvus d’interface graphique (système de fenêtres « pilotables » à la souris), toutes les interactions « système d’exploitation – utilisateur » se faisaient par l’intermédiaire de « lignes de commandes » (suites de caractères, souvent ésotériques, saisies par l’utilisateur). Aujourd’hui, même si les interfaces graphiques modernes permettent d’effectuer la plupart des opérations, il est important de connaitre quelques-unes de ces lignes de commandes.

Nous allons utiliser une clé Freeduc-JBART, cette clé est basée sur Debian-Live , ce qui nous permettra de travailler sous Linux .

Pour saisir des lignes de commandes, nous allons utiliser une console (aussi appelé terminal même si ce n’est pas exactement la même chose).

À faire vous-même 1

Après avoir démarrer sur votre clé Freeduc-JBART

Ouvrez une console, vous devriez avoir quelque chose qui ressemble à cela :

console

console système GNU/Linux

Nous avons ci-dessus la console de l’utilisateur « david » qui utilise un ordinateur qui se nomme « PC-Bureau » (« david@PC-Bureau »).


Principalement nous allons, grâce à la ligne de commande, travailler sur les fichiers et les répertoires. Dans les systèmes de type « UNIX » (par exemple GNU/Linux ou macOS), nous avons un système de fichier en arborescence :

console

système de fichiers

Dans le schéma ci-dessus on trouve des répertoires (noms entourés d’un rectangle, exemple : « home ») et des fichiers (uniquement des noms « grub.cfg »). À noter : les extensions des noms de fichiers, par exemple le « cfg » de « grub.cfg », ne sont pas obligatoires dans les systèmes de type « UNIX », par exemple, « bash » est bien un nom de fichier et il n’a pas d’extension.

On parle d’arborescence, car ce système de fichier ressemble à un arbre à l’envers.

Comme vous pouvez le constater, la base de l’arbre s’appelle la racine de l’arborescence et se représente par un « / »

Chemin absolu ou chemin relatif ?

Pour indiquer la position d’un fichier (ou d’un répertoire) dans l’arborescence, il existe 2 méthodes : indiquer un chemin absolu ou indiquer un chemin relatif. Le chemin absolu doit indiquer « le chemin » depuis la racine. Par exemple le chemin absolu du fichier fiche.ods sera : /home/elsa/documents/fiche.ods

Remarquez que nous démarrons bien de la racine / (attention les symboles de séparation sont aussi des /)

Il est possible d’indiquer le chemin non pas depuis la racine, mais depuis un répertoire quelconque, nous parlerons alors de chemin relatif :

Le chemin relatif permettant d’accéder au fichier « photo_1.jpg » depuis le répertoire « max » est : « images/photo_vac/photo_1.jpg »

Remarquez l’absence du / au début du chemin (c’est cela qui nous permettra de distinguer un chemin relatif et un chemin absolu).

Imaginons maintenant que nous désirions indiquer le chemin relatif pour accéder au fichier « gdbd_3.jpg » depuis le répertoire « photos_vac ».

Comment faire ?

Il faut « remonter » d’un « niveau » dans l’arborescence pour se retrouver dans le répertoire « images » et ainsi pouvoir repartir vers la bonne « branche ». Pour ce faire il faut utiliser 2 points : ..

« ../ski/gdbd_3.jpg »

Il est tout à fait possible de remonter de plusieurs « crans » : « ../../ » depuis le répertoire « photos_vac » permet de « remonter » dans le répertoire « max »

À faire vous-même 2

En vous basant sur l’arborescence ci-dessus, déterminez le chemin absolu permettant d’accéder au fichier :

  • « cat »
  • « rapport.odt »

Toujours en vous basant sur l’arborescence ci-dessus, déterminez le chemin relatif permettant d’accéder au fichier :

  • « rapport.odt » depuis le répertoire « elsa »
  • « fiche.ods » depuis le répertoire « boulot »

Comme déjà évoqué plus haut, les systèmes de type « UNIX » sont des systèmes « multi-utilisateurs » : chaque utilisateur possède son propre compte. Chaque utilisateur possède un répertoire à son nom, ces répertoires personnels se situent traditionnellement dans le répertoire « home ». Dans l’arborescence ci-dessus, nous avons 2 utilisateurs : « max » et « elsa ». Par défaut, quand un utilisateur ouvre une console, il se trouve dans son répertoire personnel. Dans l’image de la console ci-dessus, nous avons un « david@PC-Bureau ~ $ » (au passage, on appelle cela « l’invite de commande »), le « ~ » (caractère « tilde ») signifie que l’on se trouve actuellement dans le répertoire personnel de l’utilisateur courant, autrement dit dans le répertoire de chemin absolu « /home/david » (puisque l’utilisateur courant est « david »). Le répertoire « où l’on se trouve actuellement » est appelé « répertoire courant ». L’invite de commande vous indique à tout moment le répertoire courant : « david@PC-Bureau ~/Documents $ » vous indique que vous êtes dans le répertoire « Documents » qui se trouve dans le répertoire « david » qui se trouve dans le répertoire « home » (chemin absolu : « /home/david/Documents »)

Attention : les systèmes de type « UNIX » sont « sensibles à la casse » (il faut différencier les caractères majuscules et les caractères minuscules) : le répertoire « Documents » et le répertoire « documents » sont 2 répertoires différents.

La commande cd

Signification : list

La commande « cd » permet de changer le répertoire courant. Il suffit d’indiquer le chemin (relatif ou absolu) qui permet d’atteindre le nouveau répertoire :

Par exemple (en utilisant l’arborescence ci-dessus) :

  • si le répertoire courant est le répertoire « elsa » et que vous « voulez vous rendre » dans le répertoire « documents », il faudra saisir la commande : « cd documents » (relatif) ou « cd /home/elsa/documents » (absolu)
  • si le répertoire courant est le répertoire « photos_vac » et que vous « voulez vous rendre » dans le répertoire « ski », il faudra saisir la commande : « cd ../ski » (relatif) ou « cd /home/max/images/ski » (absolu)
  • si le répertoire courant est le répertoire « boulot » et que vous « voulez vous rendre » dans le répertoire « documents », il faudra saisir la commande : « cd .. » (relatif) ou « cd /home/elsa/documents » (absolu)

À faire vous-même 3

Toujours en utilisant l’arborescence ci-dessus, quelle est la commande à saisir si le répertoire courant est le répertoire « home » et que vous « voulez vous rendre » dans le répertoire « boulot » (vous utiliserez d’abord un chemin absolu puis un chemin relatif)

La commande ls

Signification : list

La commande « ls » permet de lister le contenu du répertoire courant.

console

Dans l’exemple ci-dessus, depuis le répertoire personnel de l’utilisateur « david », nous passons dans le répertoire « nsi » à l’aide d’un « cd nsi », puis nous affichons le contenu de ce répertoire « nsi » à l’aide de la commande « ls ». Nous trouvons dans le répertoire « nsi » : 2 fichiers (« fiche1.odt » et « photo.jpg ») et un répertoire (« test »).

À faire vous-même 4

Après avoir ouvert une console, utilisez la commande ls depuis votre répertoire personnel.


La commande « mkdir »

Signification : make directory

La commande « mkdir » permet de créer un répertoire dans le répertoire courant. La commande est de la forme « mkdir nom_du_répertoire »

console

Remarque : il est préférable de ne pas utiliser de caractères accentués dans les noms de répertoire (ou de fichier). Il en est de même pour les espaces (à remplacer par des caractères tirets bas « _ »)

La commande man

Signification : manual

Affiche les pages du manuel système.
Chaque argument donné à man est généralement le nom d’un programme, d’un utilitaire, d’une fonction ou d’un fichier spécial. Exemples d’utilisation :

  • man man
    affiche les informations pour l’utilisation de man
  • man mkdir
    affiche les informations pour l’utilisation de mkdir

‘q’ pour quitter.

À faire vous-même 5

Après avoir ouvert une console, utilisez la commande « mkdir » afin de créer un répertoire « test_nsi » dans votre répertoire personnel.

La commande « rm »

Signification : remove

La commande « rm » permet de supprimer un fichier ou un répertoire. La commande est de la forme « rm nom_du_répertoire_ou_nom_du_fichier »

console

La plupart des commandes UNIX peuvent être utilisées avec une ou des options. Par exemple, pour supprimer un répertoire non vide, il est nécessaire d’utiliser la commande « rm » avec l’option « -r » : « rm -r nom_du_répertoire »

Attention si vous utilisez la commande « rm * » cela supprime tous les fichiers présent dans le répertoire courant.

A noter que pour afficher le répertoire courant il existe une fonction « pwd », même s’il est spécifié sur le terminal en bleu…

console

La commande « touch »

La commande « touch » permet de créer un fichier vide. La commande est de la forme « touch nom_du_fichier_à_créer »

console

La commande « cp »

Signification : copy

La commande « cp » permet de copier un fichier. La commande est de la forme « cp /répertoire_source/nom_fichier_à_copier /répertoire_destination/nom_fichier »

console

À noter : le nom du fichier « destination » n’est pas obligatoirement le même que le nom du fichier « source » (on peut avoir « cp fic.txt info/fiche.txt »)

La commande « mv »

Signification : move

la commande « mv » permet de déplacer ou renommer des fichiers et des répertoires Options les plus fréquentes :

  • -f : Écrase les fichiers de destination sans confirmation
  • -i : Demande confirmation avant d’écraser
  • -u : N’écrase pas le fichier de destination si celui-ci est plus récent

Exemples d’utilisation :

  • mv monFichier unRep/
    Déplace monFichier dans le répertoire unRep
  • mv unRep/monFichier .
    Déplace le fichier monFichier du répertoire unRep là où on se trouve
  • mv unRep monRep
    Renomme unRep en monRep

À faire vous-même 6

Placez-vous dans le répertoire « test_nsi » créé au « À faire vous-même 5 ». Créez un fichier « test.txt » avec du texte à l’intérieur.

Saisir la commande « cat test.txt » que se passe t’il?

Créez un répertoire « doc ». Copiez le fichier « test.txt » dans le répertoire « doc ». Effacez le répertoire doc (et son contenu).

Gestion des utilisateurs et des groupes

Les systèmes de type « UNIX » sont des systèmes multi-utilisateurs, plusieurs utilisateurs peuvent donc partager un même ordinateur, chaque utilisateur possédant un environnement de travail qui lui est propre.

Chaque utilisateur possède certains droits lui permettant d’effectuer certaines opérations et pas d’autres. Le système d’exploitation permet de gérer ces droits très finement. Un utilisateur un peu particulier est autorisé à modifier tous les droits : ce « super utilisateur » est appelé « administrateur » ou « root ». L’administrateur pourra donc attribuer ou retirer des droits aux autres utilisateurs. Au lieu de gérer les utilisateurs un par un, il est possible de créer des groupes d’utilisateurs. L’administrateur attribue des droits à un groupe au lieu d’attribuer des droits particuliers à chaque utilisateur.

Comme nous venons de le voir, chaque utilisateur possède des droits qui lui ont été octroyés par le « super utilisateur ». Nous nous intéresserons ici uniquement aux droits liés aux fichiers, mais vous devez savoir qu’il existe d’autres droits liés aux autres éléments du système d’exploitation ((imprimante, installation de logiciels…).

Les fichiers et les répertoires possèdent 3 types de droits :

  • les droits en lecture (symbolisés par la lettre r) : est-il possible de lire le contenu de ce fichier
  • les droits en écriture (symbolisés par la lettre w) : est-il possible de modifier le contenu de ce fichier
  • les droits en exécution (symbolisés par la lettre x) : est-il possible d’exécuter le contenu de ce fichier (quand le fichier du code exécutable)

Il existe 3 types d’utilisateurs pour un fichier ou un répertoire :

  • le propriétaire du fichier (par défaut c’est la personne qui a créé le fichier), il est symbolisé par la lettre u
  • un fichier est associé à un groupe, tous les utilisateurs appartenant à ce groupe possèdent des droits particuliers sur ce fichier. Le groupe est symbolisé par la lettre g
  • tous les autres utilisateurs (ceux qui ne sont pas le propriétaire du fichier et qui n’appartiennent pas au groupe associé au fichier). Ces utilisateurs sont symbolisés la lettre « o »

Il est possible d’utiliser la commande « ls » avec l’option « -l » afin d’avoir des informations supplémentaires.

console

Prenons la première ligne :


-rw-r--r-- 1 david david 0 avril 13 19:58 fic.txt
 

Lisons cette ligne de gauche à droite :

  • le premier symbole « – » signifie que l’on a affaire à un fichier, dans le cas d’un répertoire, nous aurions un « d » (voir la 2e ligne)
  • les 3 symboles suivants « rw-« donnent les droits du propriétaire du fichier : lecture autorisée (r), écriture autorisée (w), exécution interdite (- à la place de x)
  • les 3 symboles suivants « r–« donnent les droits du groupe lié au fichier : lecture autorisée (r), écriture interdite (- à la place de w), exécution interdite (- à la place de x)
  • les 3 symboles suivants « r–« donnent les droits des autres utilisateurs : lecture autorisée (r), écriture interdite (- à la place de w), exécution interdite (- à la place de x)
  • le caractère suivant « 1 » donne le nombre de liens (nous n’étudierons pas cette notion ici)
  • le premier « david » représente le nom du propriétaire du fichier
  • le second « david » représente le nom du groupe lié au fichier
  • le « 0 » représente la taille du fichier en octet (ici notre fichier est vide)
  • « avril 13 19:58 » donne la date et l’heure de la dernière modification du fichier
  • « fic.txt » est le nom du fichier

Prenons la deuxième ligne :


drwxr-xr-x 2 david david 4096 avril 13 20:05 info
	  

Lisons cette ligne de gauche à droite :

  • le premier symbole « d » signifie que l’on a un répertoire
  • les 3 symboles suivants « rwx »donnent les droits du propriétaire du répertoire : lecture du contenu du répertoire autorisée (r), modification du contenu du répertoire autorisée (w), il est possible de parcourir le répertoire (voir le contenu du répertoire) (x)
  • les 3 symboles suivants « r-x »donnent les droits du groupe lié au répertoire : modification du contenu du répertoire interdite (- à la place de w)
  • les 3 symboles suivants « r-x »donnent les droits des autres utilisateurs : modification du contenu du répertoire interdite (- à la place de w)
  • le caractère suivant « 2 » donne le nombre de liens (nous n’étudierons pas cette notion ici)
  • le premier « david » représente le nom du propriétaire du répertoire
  • le second « david » représente le nom du groupe lié au répertoire
  • le « 4096 » représente la taille du répertoire en octets
  • « avril 13 20:05 » donne la date et l’heure de la dernière modification du contenu du répertoire
  • « info » est le nom du répertoire

À faire vous-même 7

Analysez la 3e ligne du résultat de la commande « ls -l » ci-dessus


Il est important de ne pas perdre de vu que l’utilisateur « root » a la possibilité de modifier les droits de tous les utilisateurs.

Le propriétaire d’un fichier peut modifier les permissions d’un fichier ou d’un répertoire à l’aide de la commande « chmod ». Pour utiliser cette commande, il est nécessaire de connaitre certains symboles :

  • les symboles liés aux utilisateurs : « u » correspond au propriétaire, « g » correspond au groupe lié au fichier (ou au répertoire), « o » correspond aux autres utilisateurs et « a » correspond à « tout le monde » (permet de modifier « u », « g » et « o » en même temps)
  • les symboles liés à l’ajout ou la suppression des permissions : « + » on ajoute une permission, « – » on supprime une permission, « = » les permissions sont réinitialisées (permissions par défaut)
  • les symboles liés aux permissions : « r » : lecture, « w » : écriture, « x » : exécution.

La commande « chmod » à cette forme :


chmod [u g o a] [+ - =] [r w x] nom_du_fichier
		 

par exemple


chmod o+w toto.txt
		

attribuera la permission « écriture » pour le fichier « toto.txt » « aux autres utilisateurs »

Il est possible de combiner les symboles :


chmod g-wx toto.txt
	 

La commande « chmod » ci-dessus permet de supprimer la permission « écriture » et la permission « exécution » pour le fichier « toto.txt » « au groupe lié au fichier »

Une fois de plus, « root » a tous les droits sur l’ensemble des fichiers et des répertoires, il peut donc utiliser la commande « chmod » sur tous les répertoires et tous les fichiers.

À faire vous-même 8

Analysez attentivement l’enchainement de commandes suivantes :

console

À faire vous-même 9

Créez un répertoire « test_nsi2 » dans votre répertoire personnel. Placez-vous dans le répertoire « test_nsi2 ». Créez un fichier « titi.txt », vérifiez les permissions associées à ce fichier. Modifiez les permissions associées au fichier « titi.txt » afin que les « autres utilisateurs » aient la permission « écriture »


Retrouver toutes les commandes ici : documentation Ubuntu console de commande