[PDF] Cours dInformatique pour Tous 2021 –

View - Download Cours dInformatique pour Tous 2021 –

Previous PDF

Next PDF

Cours d"Informatique pour Tous

2021 -Jules Svartz

Lycée Masséna

Lycée Masséna

Svartz Page 2/210

Lycée Masséna

Préambule

Ces notes de cours sont issues du cours d"informatique commune (IPT) subi par les élèves du lycée Masséna des

classes de première année MPSI (831), PCSI (833) et de deuxième année MP*, MP, PC*, PC, depuis l"année 2021 en

première année et 2022 en deuxième année. Il sera mis à jour régulièrement!

Le cours présenté ici est très détaillé, et tous les points ne sont pas nécessairement abordés en classe : il se veut

utile autant pour l"élève qui veut un récapitulatif que pour celui qui souhaite aller plus loin.

Le polycopié se divise en 7 parties, le programme de première année couvrant les quatre premières, le programme

de seconde année les autres. La première partie est dév olueà l"" initiation ». Elle se sub diviseen 4 c hapitres:

Le c hapitre0 est un c hapitred"in troductionà l"informatique, il présen teun p ointde vue historique sur le

développement de cette discipline, les principaux éléments constitutifs d"un ordinateur et le rôle du système

d"exploitation. Ce chapitre a disparu du nouveau programme, mais il forme une introduction historique

importante à la discipline, et sera sûrement traité encore les années à venir. Le cours présenté ici est

plutôt présenté en fin d"année, par choix pédagogique : il est en effet plus facile d"expliquer précisément le

comportement d"un micro-processeur à des élèves qui savent déja programmer et ont une connaissance du

système de numération binaire.

Le c hapitre1 présen tede manière d étailléeles élémen tsa uprogramme concernan tla programmation en

Python. Il est en pratique présenté peu à peu en cours et en TP, parallèlement aux chapitres qui suivent.

Le c hapitre2 présen tela représen tationdes nom bresen tiersdans différen tesbases, en particulier e nbinaire.

Les algorithmes de changement de base, quoique non au programme, sont un prétexte pour commencer à

faire des boucles et utiliser des listes.

Le c hapitre3 es tnormalemen tau programme au second semes tre,mais il me sem blein téressantde le

traiter tôt dans l"année, en parallèle des travaux pratiques. Il donne les outils pour l"analyse théorique

des algorithmes (terminaison / correction / complexité). C"est un chapitre crucial où sont présentés les

algorithmes " basiques » au programme de première année : parcours de listes, recherche dichotomique ou

de motif dans une chaîne de caractères...

La deuxième partie (au programme officie ltraitée uniquemen tsous forme de tra vauxpratiques) présen te:

au c hapitre4, les tec hniquesgloutonnes en algorithmique. Le c hapitreest v olontairementcourt p ourlaisser

des exemples en travaux pratiques.

au c hapitre5, la récursivité. On donne quelques élémen tsde preuv ede programmes dans ce con texte.

La troisième partie donne quelques complémen tsde Python. Elle se dé coupeen 3 c hapitres:

Le c hapitre6 se concen tresur la représe ntationdes nom bres.On se restrein tmain tenantau binaire, et on

explique les rudiments de calculs effectués par un processeur, avec des registres de taille fixe. On présente

aussi la représentation usuelle des nombres flottants.

Le c hapitre7 présen teles métho desp ourlire un fic hiertextuel en Python, ainsi que la création d"un tel

fichier. C"est l"occasion de revenir sur les chaînes de caractères! Le c hapitre8 présen teles mo dulesusuels en Python, il fera l"ob jetd"un ou deux TP(s). La quatrième par tieest l"o ccasionde mettre en pratique les tec hniquesvues précédemmen t.

On présen ted"ab ordle tri de données, problème essen tielen informatique. On a découp éle traitemen tdes

tris en deux parties, chapitre 9 pour les tris quadratiques, ainsi que le tri par comptage, chapitre 10 pour

les tris efficaces (tri fusion, tri rapide). Un bref c hapitre11 présen tela notion de jeu de tests p ourun programme.

Enfin, on étudie les bases des g raphesdans le c hapitre12. L"accen te stp ortésur le parcours de gra phes,le

programme ayant en ligne de mire l"algorithme de Dijkstra et sa varianteA.

Svartz Page 3/210

Lycée Masséna

La partie 5 présen teles bases de SQL et de l"algèbre relationnelle.

Le c hapitre13 donne le v ocabulaireet les premières requêtes SQL, en ce concen trantsur une seule base ;

Le c hapitre14 in troduitles liens en trerelations.

La p artie6 étend les tec hniquesgloutonnes vues en premi èresannées p ourrésoudre des problèmes par program-

mation dynamique.

Le c hapitre15 donne une impléme ntationp ossibleen Python de la structure de dictionnaires (a vecdes

listes Python), via des fonctions de hachage. On explique en particulier comment résoudre les collisions, et

comment une structure dynamique permet de justifier la complexitéO(1)que l"on attribue aux opérations

de dictionnaire en Python. Le c hapitre16 présen teles tec hniquesde programmation dynamique p roprementdites.

Enfin, la septième partie donne une in troductionà l"appren tissage(sup erviséou non), ainsi qu"à la théorie des

jeux.

Licence.Cette oeuvre est mise à disposition sous licence Attribution - Partage dans les Mêmes Conditions 2.0 France.

Pour voir une copie de cette licence, visitezhttp://creativecommons.org/licenses/by-sa/2.0/fr/ou écrivez à

Creative Commons, PO Box 1866, Mountain View, CA 94042, USA.

Svartz Page 4/210

TABLE DES MATIÈRESLycée MassénaTable des matières

I Initiation11

0 Ordinateurs, Systèmes d"exploitation et Python 13

0.1 Qu"est ce qu"un ordinateur? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

0.1.1 Turing et ses machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

0.1.2 Prémices aux ordinateurs et modèle de Von Neumann . . . . . . . . . . . . . . . . . . . . . . .

15

0.1.3 Le rôle de chaque élément. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

0.1.4 Avantages et inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

0.1.5 De nos jours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

0.1.6 Ordres de grandeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

0.2 Le système d"exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

0.2.1 Le multitâche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 9

0.2.2 Identification des utilisateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

0.2.3 Organisation des fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

0.2.4 Droits d"accès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

0.3 Le langage Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

1 Programmation en Python23

1.1 Types simples et expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1.1.1 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1.1.2 Entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

1.1.3 Flottants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

1.1.4 Booléens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

1.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

1.2.1 Identificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

1.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

1.3 Structures de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

1.3.1 Python et l"indentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

1.3.2 Instruction conditionnelle if/else (si/sinon) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

1.3.3 Boucle conditionnelle while (tant que) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

1.3.4 Boucle inconditionnelle for... (pour...) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

1.3.5 Break et Continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

1.3.6 Boucles imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

1.4 Structures de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

1.4.1 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

1.4.2 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

1.4.3 Chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

1.4.4 Dictionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

1.5 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 9

1.5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

1.5.2 Notions et syntaxe de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

1.5.3 Variables locales et globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

1.5.4 Références vers des objets mutables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

1.5.5 Une fonction : un objet comme les autres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

Svartz Page 5/210

TABLE DES MATIÈRESLycée Masséna2 Entiers dans différentes bases45

2.1 Écriture dans une base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

2.1.1 Rappels sur la base 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

2.1.2 Généralisation à une base quelconque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

2.1.3 Généralisation à des bases supérieures à 10. Hexadécimal . . . . . . . . . . . . . . . . . . . . .

46

2.1.4 Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

2.2 Changement de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

2.2.1 Si l"on sait calculer dans la base de départ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

2.2.2 Si l"on sait calculer dans la base d"arrivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

2.2.3 Un cas particulier : l"une des bases est une puissance de l"autre . . . . . . . . . . . . . . . . . .

4 8

3 Analyse d"algorithmes51

3.1 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3.1.1 Quelques exemples, exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

3.1.2 Variant de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

3.2 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.2.1 Correction des boucleswhile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53

3.2.2 Correction des bouclesfor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54

3.2.3 D"autres exemples : parcours linéaires de listes . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

3.2.4 Recherche efficace dans une liste triée : recherche dichotomique . . . . . . . . . . . . . . . . . .

56

3.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

3.3.1 Introduction et tri par sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 6

3.3.2 Complexité : définitions et méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 8

3.3.3 Applications aux algorithmes vus précédemment . . . . . . . . . . . . . . . . . . . . . . . . . .

59

3.3.4 Quelques ordres de grandeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

3.4 Recherche d"un motif dans une chaîne de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

II Techniques algorithmiques 63

4 Algorithmes gloutons65

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

4.2 Principe des algorithmes gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.3 Maximisation d"activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.3.1 Un algorithme optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

4.3.2 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

4.4 Rendu de monnaie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67
quotesdbs_dbs9.pdfusesText_15

[PDF] algoritmo de dijkstra java

[PDF] aliexpress france avis

[PDF] alkyl and aryl halides notes pdf

[PDF] alkyl halides notes pdf

[PDF] all google sites list

[PDF] all html5 tags list with examples pdf

[PDF] all police codes mn

[PDF] all the methods in the interface are internally

[PDF] allan_and_barbara_pease_ _body_language_the_definitive_book.pdf

[PDF] allemand langage familier

[PDF] aller + infinitif exercices

[PDF] aller retour paris ajaccio air france

[PDF] aller retour paris nice avion

[PDF] alliance gradebook pinnacle

[PDF] allocate memory for struct in c