[PDF] Informatique pour tous - Classes préparatoires scientifiques - 1re et

View - Download Informatique pour tous - Classes préparatoires scientifiques - 1re et

Previous PDF

Next PDF

VUIBERTTout-en-un

Tout le cours

Fiches de synthèse

Conseils méthodologiques

Vrai/faux

Exercices d'application

Problèmes de synthèse

Sujets de concours

Tous les corrigés détaillésTout le

programme avec PYTHON et SCILAB

A. Caignot •

M. Dérumaux • J. Labasque • L. Moisan

INFORMATIQUE POUR TOUS

Classes préparatoires scientifiques 1

re et 2 e années

Avant-propos

Cet ouvrage vous propose, en un seul volume, toutes les clés nécessaires pour réussir votre première et votre deuxième année d'informatique en classes préparatoires scienti- �ques.

Cours complet

Rigoureusement conforme aux nouveaux programmes, il contient tous les outils pour acquérir les connaissances et les savoir-faire indispensables.

Fiches de synthèse

Pour une révision ef�cace avant les épreuves, l'essentiel du cours est présenté de ma-

nière synthétique sous forme de �ches de révision.

Vrai/faux

Première étape vers l'entraînement, des Vrai faux vous permettent de tester rapidement la compréhension du cours. Exercices d'application et problèmes de synthèse Application directe du cours, ces nombreux exercices et problèmes sont assortis d'un

Sujets de concours

Pour se mettre en situation d'épreuve, une sélection d'exercices extraits de sujets de concours vous est proposée. Tous ces exercices sont intégralement corrigés. Retrouvez sur le site www.vuibert.fr, à la page du livre, des ressources complémentaires à téléchargerIII

Table des matières

Préface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .VII

Chapitre 1.Architecture des ordinateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11. Les composants et leurs connexions1- 2. L'architecture logicielle5- 3. Le codage des données

en mémoire7

Chapitre 2.Programmation et algorithmique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19

1. L'installation et l'utilisation de Python et Scilab19- 2. Les structures de données25- 3. Les

instructions de contrôle

39- 4. Les fonctions43- 5. Le débogage d'un programme50- 6. La

lecture et l'écriture de �chiers54- 7. Les tracés graphiques56- 8. La terminaison, la correction

et la complexité56-Synthèse64-Exercices66-Corrigés86

Chapitre 3.Simulation numérique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .111

1.XLa vectorisation des calculs111- 2.¨La résolution des équations non linéaires117-

3."L'intégration et la dérivation de signaux numériques129- 4.ªL'intégration des équations

différentielles137- 5.©La résolution d'un système linéaire par la méthode de Gauss146-

Chapitre 4.Initiation aux bases de données. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .219

1. Les motivations219- 2. L'architecture matérielle et logicielle des bases de données220- 3. La

modélisation d'une base de données222- 4. L'utilisation d'un logiciel pour manipuler des bases de données225- 5. L'algèbre relationnelle227-Synthèse237-Exercices239-Corrigés244

Chapitre 5.Algorithmique : approfondissement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .247

1. Les piles247- 2. Les fonctions récursives252- 3. Les algorithmes de tri259- 4. La program-

mation orientée objet267-Synthèse273-Exercices275-Corrigés283

Chapitre 6.Problèmes de synthèse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .299

- 3. La triangulation d'un polygone307- 4. La propagation de la chaleur dans une ailette313 - 5. Autour des nombres premiers318- 6. Transformation homographique d'une image numé- rique325- 7. La compression RLE des images clipart332- 8. La compression LZW337- 9. La compression de Huffman d'un texte341- 10. Une balade dans le métro parisien346V

PréfaceDepuis leur création à la �n duXIXesiècle (par Henri Vuibert, alors plus jeune agrégé de ma-

thématiques de France) les Éditions Vuibert proposent des manuels scienti�ques rédigés par les

meilleurs auteurs, tous professeurs passionnés par leur discipline et leur enseignement. Ce fut donc avec un très grand plaisir que je fus contacté pour diriger une nouvelle collec-

tion d'ouvrages scienti�ques destinés aux étudiants préparationnaires, en adéquation avec les

nouveaux programmes de la rentrée 2013.

Nous avons réuni pour cette tâche dif�cile des auteurs de grand talent, aussi bien pour leur

quali�cation disciplinaire que pour leur désir de communiquer leur savoir à un public de plus en

plus hétérogène.

Entre 1980 et 2010, le nombre d'étudiants de CPGE scienti�que a plus que doublé, de nouvelles

sections ont vu le jour, des classes ont ouvert dans un grand nombre de villes; pendant cette

période, la formation initiale scienti�que des élèves à la sortie de l'enseignement secondaire

a beaucoup évolué, en même temps que s'érodait le nombre d'heures alloué aux disciplines

scienti�ques.

L'écart s'est donc creusé entre la terminale et les classes préparatoires aux grandes écoles. Il

revient alors aux manuels, comme aux professeurs, de faire preuve de qualités pédagogiques

exceptionnelles, sans jamais sacri�er la rigueur indispensable qui est une des forces de l'enseigne-

ment supérieur "à la française». C'est dans ce but que les livres de la collection Vuibert Prépas

ont été pensés et rédigés. Ils sont destinés au plus grand nombre et visent à amener ce plus grand

nombre au niveau de l'excellence.

Le rôle d'un manuel de classe préparatoire n'est pas évident. Les étudiants disposent déjà de

leurs notes de cours, et parfois de polycopiés, provenant d'enseignants fort compétents. Mais

chacun sait qu'on observe mieux une statue et qu'on en apprécie mieux la beauté en la regardant

sous différents angles; il en est de même des disciplines scienti�ques dans lesquelles une diversité

d'approches ne peut que faciliter la compréhension et l'assimilation de notions a priori abstraites

et dif�ciles. En ce sens, les ouvrages de la collection " Vuibert Prépas » constituent une aide

conséquente pour les élèves de CPGE scienti�ques. À lire ces ouvrages, que ce soit dans les disciplines qui sont les miennes, Mathématiques et Informatique ou dans des disciplines qui me sont moins familières comme la Physique, la Chimie

ou les Sciences de l'Ingénieur, je ne peux être qu'admiratif devant le talent des auteurs de toutes

origines qui, dans des délais très courts, ont eu à coeur de faire passer leur amour pour la science

et pour son enseignement. Je suis certain que le public préparationnaire partagera mon enthousiasme pour cette collection qui marque le retour des éditions Vuibert au service de ces �lières.

Denis MonasseVII

Chapitre 4. Initiation aux bases de données

COURSFigure 4.1.Architecture client-serveur à 2 niveaux.

2.3. Architecture à 3 niveaux

Une architecture à 3 niveaux ou 3 tiers est l'architecture classique rencontrée sur les applications

internet (voir �gure 4.2). Elle est composée : d'un client. Par exemple, le navigateur internet qui demande à af�cher une page. Il recevra les informations du serveur et se chargera de la mise en page localement; d'un serveur, qui va traiter la demande du client. Par exemple, le serveur va devoir assembler les contenus à af�cher sur le navigateur. Mais, parmi ces contenus, certains sont dans une

base de données, le serveur envoie alors une requête à un serveur de base de données sous

format SQL;

d'un serveur de bases de données. Celui-ci va traiter les requêtes SQL et envoyer les données

nécessaires au serveur.

L'objectif est de répartir un maximum la charge entre l'accès aux données (géré par le serveur

de bases de données) et le traitement des données (géré par le serveur). Le client quant à lui se

contente la plupart du temps d'af�cher les contenus.

2.4. Architecture à N niveaux

Dans les services de données extrêmement complexes, le nombre de niveaux augmente. Chaque

niveau (sauf le client) sera composé d'un serveur qui sera dédié à une tâche particulière, l'objectif

étant de distribuer les différentes opérations pour paralléliser le traitement et améliorer la rapidité

d'exécution de l'ensemble de l'application.221

Informatique pour tousdemande

de page web page web en réponse requête SQL données demandées serveur http, php...serveur de bases de donnéesFigure 4.2.Architecture client-serveurs à trois niveaux.

3. La modélisation d'une base de donnéesDé�nition 4.1. Base de données

Une base de données est un ensemble structuré d'informations qui permet de répondre à un besoin spéci�que.

Pour pouvoir être consultée, modi�ée, créée, il est nécessaire d'avoir un logiciel de gestion des

bases de données qui va permettre de faire le lien entre une application cliente et les données de

la base.

Les logiciels de gestion de bases classiques sont basés sur le langage de requête structurée SQL

Structure Query Language), il en existe des payants, comme Microsoft SQL Server, par exemple, ainsi que des gratuits tels que MySQL, PostgreSQL, SQLite...

3.1. Modélisation par entité/association

Les éléments du monde réel que nous pouvons percevoir ne peuvent pas tous être représentés.

Il convient de faire un choix pour délimiter la représentation de ces éléments en fonction des

objectifs visés par l'application. Chaque élément du monde réel est représenté par une entité.

Chaque entité possède des attributs : la liste des paramètres qui caractérisent l'entité. Il convient

ensuite de dé�nir les associations entre les différentes entités, c'est-à-dire les relations entre les

différentes entités. On parle de modélisation par entité association. 222

Chapitre 4. Initiation aux bases de données

COURSExemple

Dans le cas de la bibliothèque, pour gérer uniquement la liste des livres et la liste des adhé-

rents, il faut dé�nir deux entités : • les livres, entité qui contient les attributs suivant : -titre : texte, -auteur : texte, -editeur : texte, -nb_pages : nombre, -annee : date format AAAA, -emprunteur : lien vers un adhérent à dé�nir, -date_retour : date format JJ/MM/AAAA; • les adhérents, entité qui contient : -nom : texte, -prenom : texte, -email : texte. asso-

ciation, nous illustrerons ici uniquement la syntaxe UML. Elle possède deux éléments graphiques

de base : un ensemble d'entité, qui est représenté par un rectangle à bord arrondi dans lequel se trouve le nom de l'ensemble des entités et le nom de leurs attributs; • une association, qui est représentée par un trait entre deux entités. livres titre auteur editeur nb_pages annee emprunteur date_retour adherents nom prenom email emprunte

3.2. Vocabulaire

Le modèle utilisé pour représenter une base de données est relativement simple : c'est celui

de plusieurs tableaux ou tables à deux dimensions. Par convention, les données des différents

éléments sont en ligne et les informations sont en colonne. Voici un exemple simple que nous

utiliserons par la suite : les livres d'une bibliothèque ainsi que les emprunteurs, présentés les deux

tables 4.2 et 4.3.

Quelques dé�nitions :

• les titres de colonnes sont les attributs notésA1,A2, ...,Ap; • l'ensemble des valeurs possibles d'un attributAest son domaine notéDom(A);

• chaque ligne est unn-upletet un élément deDom(A1)�Dom(A2)�����Dom(Ap);

• un schéma relationnel ou une relationRest dé�ni : -par un ensemble �ni et �xé d'attributs et de leur domaine notéS, -et par l'ensemble desn-upletsappelée extension de la relation.223

Informatique pour tous

idtitreauteur editeur nb_pages annee emprunteur date_retour1 Notre-Dame de Paris Victor Hugo Gosselin 636 1831 1 05/06/2014

2Les misérables Victor Hugo Lacroix 1662 1862

3 Voyage au centre de la Terre Jules Verne Hetzel 372 1864 1 10/06/2014

4 Le tour du monde en 80 jours Jules Verne Hetzel 223 1872 2 10/07/2014Table 4.2.Table des livres.id nom prenomemail1 DUPONT Jean jean.dupont@gmail.com2 MARTIN Paul paul.martin@gmail.com

Table 4.3.Table des adhérents.Par dé�nition, les attributs forment un ensemble, ce qui implique qu'il n'y a pas d'attribut en

double et que l'ordre des attributs n'est pas �xé : on ne parle pas du premier attribut mais de

l'attribut titre (dans notre exemple). Il est possible de restreindre une ligne à un sous-ensemble d'attributs, soitrunn-uplet, alors r(A2,A5,A3)est la restriction deraux attributsA2,A5etA3. De manière générale, siSest une partie defA1,A2,...,Apg, alorsr(S)dénote l'ensemble des valeurs prises par len-upletrpour les attributs appartenant àS.

Toujours par dé�nition, les lignes forment un ensemble, car il n'y a pas de ligne en double et, de

la même manière que les attributs, les lignes ne sont pas ordonnées.

Par exemple,Dom(id) =N�et l'extension de la relation adhérents est représentée par le ta-

bleau 4.3.

3.3. Notion de clés

Pour repérer unn-upletdans l'ensemble desn-upletsd'un type donné (c'est-à-dire un adhérent

parmi tous les adhérents), il est nécessaire de choisir un attribut qui identi�e de manière unique

cen-uplet. Dans l'exemple des adhérents, il n'y a pas de raison que le nom ou le prénom soit unique dans

la base de données. En revanche, l'adresse e-mail a plus de chance de l'être.Dé�nition 4.2. Clés

Un attribut qui permet d'identi�er de manière unique unn-upletest nomméclé. Un

n-upletpeut être identi�ée par plusieurs clés; dans ce cas, il convient de dé�nir une

clé primaire et desclés secondaires(utile pour la gestion des algorithmes de recherche non détaillés dans cet ouvrage). Dansle casdesadhérents,l'adresse e-mailpeutdonc être unecléprimaire(si l'onimposequ'elle soit unique : les membres d'une même famille doivent prendre une adresse e-mail différente). Dans le cas des livres, rien ne garanti l'unicité de chacun de ses attributs : plusieurs livres

pourraient avoir le même titre. Il faut donc ajouter un attribut qui permettra d'identi�er de

224

Chapitre 4. Initiation aux bases de données

COURS

manière unique les livres dans la base de données. En pratique, dans la majorité des cas, laclé

primairesera un identi�ant abstrait unique de type nombre; souvent notéid.

Toujours en pratique, la clé primaire doit :

• identi�er de manière unique unn-upletparmi l'ensemble desn-upletsde même type; • ne jamais être modi�ée (dans ce cas, l'adresse e-mail n'est pas bien adaptée); • prendre un minimum d'espace mémoire pour des raisons d'ef�cacité des recherches. La base de données est maintenant représentée par le schéma suivant. livres id titre auteur editeur nb_pages annee emprunteur date_retour adherents id nom prenom email emprunteRemarque

Pour dé�nir qui a emprunté un livre, l'attributemprunteurd'un livre fera référence à l'identi-

�antidde l'adhérent.

4. L'utilisation d'un logiciel

pour manipuler des bases de données

requêtes à la base de données pour ensuite traiter les résultats. La grande majorité de l'utilisation

des bases de données se situe au travers des sites web (avec les langages PHP, AJAX...) ou les applications sur tablette et smartphone. Pour ne pas avoir à apprendre d'autres langages de programmation, le programme d'informa- tique propose d'utiliser les bases de données à travers une interface graphique. Nous faisons le choix, dans cet ouvrage, d'utiliser des bases de données SQLite, qui est une implémentation

des bases SQL dans un �chier. SQLite ne nécessite pas l'installation d'un serveur SQL. Il existe

différentes interfaces graphiques permettant de dialoguer avec des bases de données SQLite. Nous

utiliserons ici SQLiteManager, un module complémentaire de Firefox, mais vous pouvez aussi utiliser SQLiteBrowser qui est un logiciel à part entière ( http://sqlitebrowser.org/

4.1. Installation de SQLiteManager

Il faut commencer par installer Firefox à partir de l'adresse : https://www.mozilla.org/fr/firefox/ Il suf�t ensuite d'ajouter l'extension en allant à l'adresse :

Informatique pour tousIl faut ensuite aller dans la barre des menus, puis la rubrique outils et cliquer sur SQLiteManager.

Dans le cas où la barre de menu est invisible, faire un clic droit sur la barre de l'application en haut

et cocher "Barre de menus».

Une fenêtre identique à celle de la �gure 4.3 doit s'ouvrir.Figure 4.3.Application SQLiteManager.

4.2. Utilisation de SQLiteManager

Dans cette fenêtre, vous pouvez créer une nouvelle base de données, puis ajouter une nouvelle

table en renseignant les éléments nécessaires (�gure 4.4).Figure 4.4.Création d'une table graphiquement avec SQLiteManager.

226

Chapitre 4. Initiation aux bases de données

COURSDans l'onglet "Structure» de la table, il est possible d'ajouter une ou plusieurs colonnes.

Dans l'onglet "Parcourir et rechercher», il est possible de voir les différents éléments de la table,

de faire des recherches simples, d'ajouter des lignes.

Dans l'onglet "Exécuter le SQL», il est possible de rentrer des commandes SQL et de les exécuter,

comme nous le verrons dans le paragraphe 5.

Pour tester, vous pouvez essayer de créer les tables "livres» et "adherents» de l'exemple de la

bibliothèque.

Vous pouvez également prendre la version �nale dans le dossier ressource. Pour charger la base

de données, cliquer sur "Base de données», "Connecter la base de données», puis sélectionner le

�chierbibliotheque.sqlite.

5. L'algèbre relationnelle

Une table de la base de données peut être considérée comme un ensemble den-upletssur lequel

on peut appliquer des opérations issues de la théorie des ensembles et au-delà. Une table est aussi appelée une relation, notéeR. Une relation est composée : • d'éléments : les éléments de la relation seront notésr;

• d'un schéma : liste des différents attributs avec leur domaine. On notera les schémasS;

• d'une extension : liste des valeurs de la table.

Dans le cadre du programme de CPGE, il faut être capable de traduire une opération de l'algèbre

relationnelle en une requête SQL pouvant s'appliquer sur une base de données classique.

5.1. Projection

La projection consiste à restreindre les éléments de la relation sélectionnée, c'est-à-dire à

sélectionner des colonnes de la table.Dé�nition 4.3. Projection SoitRune relation composée d'un schémaS. SoitX�Sune sous-partie du schéma. La projection de la relationRselonXest donnée par :

X(R)=fr(X)jr2Rg

oùr(X)est la restriction dersur les attributs deX. Le résultat d'une projection est une nouvelle relationR0composée du schémaX.Exemple On obtient :titreauteurNotre-Dame de Paris Victor Hugo

Les misérables Victor Hugo

Voyage au centre de la Terre Jules Verne

Le tour du monde en 80 jours Jules Verne227

Informatique pour tousLa traduction d'une projection en langage SQL se fait avec le mot clé :SELECTsuivi des attributs,

puis du mot cléFROMsuivi du nom de la relation (la table).Exemple Pour réaliser la projection de l'exemple précédent, il faut faire la requête :

SELECT titre , auteur

FROM livresRemarque

On peut aussi faire une projection sur tous les attributs en mettant l'opérateur *. La requête SELECT * FROM livresrenverra la table complète.

Il faut éviter au maximum d'utiliser la sélection complète, car elle est très consommatrice de

quotesdbs_dbs35.pdfusesText_40

[PDF] ds informatique pcsi

[PDF] td informatique mpsi

[PDF] exercices corrigés fonctions usuelles mpsi

[PDF] cours mpsi

[PDF] alain troesch

[PDF] ds physique mpsi louis le grand

[PDF] principe de conservation de l'énergie première s exercices

[PDF] controle energie mecanique 1ere s

[PDF] diagramme simplifié des niveaux d'énergie de l'atome de sodium

[PDF] le polonium 210 corrigé

[PDF] devoir seconde physique

[PDF] fonctions second degré controle

[PDF] exercice extraction liquide liquide

[PDF] controle physique seconde extraction

[PDF] exercice miscibilité 5eme