Cours d’informatique commune MPSI 4 - Free
Lycée Louis-Le-Grand, Paris Année 2020/2021 Cours d’informatique commune MPSI 4 Alain TROESCH Version du: 26 septembre 2020
Cours d’informatique commune MPSI 4 - Free
Cours d’informatique commune MPSI 4 Alain TROESCH 2 Les bases de la programmation en Python 37 Le mot informatique est une contraction des deux termes
Architecture matérielle et initiation à l’algorithmique
Architecture matérielle et initiation à l’algorithmique Informatique MPSI Cours Chapitre 1– 02 Expressions, types et variables en Python 9 Septembre 2020 Savoirs et compétences : p AA C01 : Manipuler un OS ou un IDE p AA S01 : Se familiariser aux principaux composants d’une machine numérique p AA S2 : Se familiariser à la
Cours d’Informatique pour Tous - SFR
Cours d’Informatique pour Tous Jules Svartz LycéeMasséna LycéeMasséna explicitant brièvement l’usage des modules usuels en Python, notamment Numpy Les
Architecture matérielle et initiation à l’algorithmique
Architecture matérielle et initiation à l’algorithmique Informatique MPSI Cours Chapitre 1– 05 Tableaux 14 Octobre 2020 Savoirs et compétences : p AA C9 : Choisir un type de données en fonction d’un problème à résoudre p AA S11 : Manipulation de quelques structures de données 1Tableaux et type list en Python 2
Informatique - CN3 - David Malka MPSI
4 Fonction prédéfinies en Python D Malka Informatique - CN3 MPSI 2018-2019 18/27 Résolution numérique d’équation d’ordre supérieur à 1
Instructions itératives - Informatique Lycée Louis le Grand
Dans l’histoire de l’informatique on distingue traditionnellement deux types de routines1: les procédures, qui ne retournent pas de résultat et se contentent d’agir sur l’environnement, et les fonctions proprement dites, qui retournent un résultat (en général par le biais d’une instruction return) En Python cette distinction n
Chapitre 4 Représentation des nombres
Chapitre 4 informatique commune Représentation des nombres Dans ce chapitre, nous allons nous intéresser à la façon dont un nombre (entier ou réel) peut être représenté à l’intérieur d’un ordinateur Nous savons déjà1 que la mémoire des ordinateurs est découpée en blocs de 8 bits
[PDF] rapport isn terminale s
[PDF] eduscol ressources isn
[PDF] association d'utilité sociale définition
[PDF] bac s informatique et sciences du numérique
[PDF] définition utilité sociale loi ess
[PDF] utilité sociale des associations
[PDF] utilité sociale définition psychologie
[PDF] utilité sociale sociologie
[PDF] utilité sociale définition philosophique
[PDF] utilité sociale wikipédia
[PDF] le voyage du centurion résumé
[PDF] pathfinder metamagie
[PDF] wiki pathfinder
[PDF] séparation d'avec quelqu'un
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èresI Initiation11
0 Ordinateurs, Systèmes d"exploitation et Python 13
0.1 Qu"est ce qu"un ordinateur? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
130.1.1 Turing et ses machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
130.1.2 Prémices aux ordinateurs et modèle de Von Neumann . . . . . . . . . . . . . . . . . . . . . . .
150.1.3 Le rôle de chaque élément. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
160.1.4 Avantages et inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170.1.5 De nos jours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170.1.6 Ordres de grandeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
170.2 Le système d"exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
180.2.1 Le multitâche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 90.2.2 Identification des utilisateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
190.2.3 Organisation des fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
200.2.4 Droits d"accès . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
200.3 Le langage Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
211 Programmation en Python23
1.1 Types simples et expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
231.1.1 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
231.1.2 Entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
241.1.3 Flottants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
251.1.4 Booléens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
251.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
261.2.1 Identificateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
261.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
271.3 Structures de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
281.3.1 Python et l"indentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
281.3.2 Instruction conditionnelle if/else (si/sinon) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
281.3.3 Boucle conditionnelle while (tant que) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
291.3.4 Boucle inconditionnelle for... (pour...) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
301.3.5 Break et Continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
311.3.6 Boucles imbriquées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
321.4 Structures de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
321.4.1 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
321.4.2 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
351.4.3 Chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
361.4.4 Dictionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
381.5 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 91.5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
391.5.2 Notions et syntaxe de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
391.5.3 Variables locales et globales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
421.5.4 Références vers des objets mutables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
431.5.5 Une fonction : un objet comme les autres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44Svartz Page 5/210
TABLE DES MATIÈRESLycée Masséna2 Entiers dans différentes bases452.1 Écriture dans une base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
452.1.1 Rappels sur la base 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
452.1.2 Généralisation à une base quelconque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
452.1.3 Généralisation à des bases supérieures à 10. Hexadécimal . . . . . . . . . . . . . . . . . . . . .
462.1.4 Histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
462.2 Changement de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
472.2.1 Si l"on sait calculer dans la base de départ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
472.2.2 Si l"on sait calculer dans la base d"arrivée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
482.2.3 Un cas particulier : l"une des bases est une puissance de l"autre . . . . . . . . . . . . . . . . . .
4 83 Analyse d"algorithmes51
3.1 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
513.1.1 Quelques exemples, exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
523.1.2 Variant de boucle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
523.2 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
533.2.1 Correction des boucleswhile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
3.2.2 Correction des bouclesfor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54
3.2.3 D"autres exemples : parcours linéaires de listes . . . . . . . . . . . . . . . . . . . . . . . . . . .
553.2.4 Recherche efficace dans une liste triée : recherche dichotomique . . . . . . . . . . . . . . . . . .
563.3 Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
563.3.1 Introduction et tri par sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 63.3.2 Complexité : définitions et méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 83.3.3 Applications aux algorithmes vus précédemment . . . . . . . . . . . . . . . . . . . . . . . . . .
593.3.4 Quelques ordres de grandeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
603.4 Recherche d"un motif dans une chaîne de caractères . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61II Techniques algorithmiques 63
4 Algorithmes gloutons65
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
654.2 Principe des algorithmes gloutons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
664.3 Maximisation d"activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
664.3.1 Un algorithme optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
664.3.2 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
674.4 Rendu de monnaie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
674.4.1 Énoncé du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
674.4.2 Choix glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
674.4.3 Optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
685 Récursivité69
5.1 Principes de la récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
695.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
695.1.2 La pile d"exécution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
695.1.3 D"autres exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
715.1.4 Limites de la récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
715.1.5 Avantage de la récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
725.2 Terminaison, correction et complexité d"une fonction récursive . . . . . . . . . . . . . . . . . . . . . . .
745.2.1 Terminaison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
745.2.2 Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
755.2.3 Complexité des fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75III Compléments de Python 77
6 Représentation des entiers relatifs, représentation des flottants 79
6.1 Représentation des entiers relatifs en binaire, additions . . . . . . . . . . . . . . . . . . . . . . . . . . .
796.1.1 Entiers naturels de taille fixée et additions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79Svartz Page 6/210
TABLE DES MATIÈRESLycée Masséna6.1.2 Entiers relatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .80