| Titre : | Informatique tronc commun : CPGE scientifiques 1re et 2e années - Nouveaux programmes |
| Auteurs : | Thierry Audibert, Auteur ; Oussalah Amar, Auteur |
| Type de document : | Monographie imprimée |
| Editeur : | Paris : Ellipses, 2022 |
| ISBN/ISSN/EAN : | 978-2-340-04870-6 |
| Format : | 1 vol. (596 p.) / couv. ill. en coul / 24 cm |
| Langues: | Français |
| Index. décimale : | 0.040711 |
| Résumé : | Ce cours couvre le programme d'informatique du tronc commun des classes préparatoires scientifiques de 1re et 2e années (MPSI, PCSI, PTSI, MP, PC, PSI et PT) mis en place en 2021. Il est décomposé en trois parties, chacune correspondant à un semestre d'enseignement : - Rappels sur le langage Python, Méthodes itératives, Récursivité, Tris, Algorithmes gloutons, Traitement de l'image ; Représentation des nombres en machine, Preuves et complexité, Graphes, Aperçu de la POO ; Bases de données et SQL, Dictionnaires, Programmation dynamique, Algorithmes et jeux, Algorithmes pour LIA. Il contient plus de 150 exercices, tous corrigés. Les scripts et des compléments sont disponibles sur le site des éditions Ellipses. |
| Sommaire : |
Partie I • Premier semestre
Chapitre 1 • Programmer avec Python13 1.1 Constantes, identificateurs, variables et affectations13 1.2 Mots réservés du langage 1.3 Types prédéfinis avec Python19 1.3.1 Types numériques : entiers, flottants, complexes 19 1.3.2 Le type None20 1.3.3 Le type booléen21 1.3.4 Les conteneurs22 1.3.5 Opérations sur les listes, ensembles et dictionnaires28 1.3.6 Exercices30 1.4 La programmation et les fonctions avec Python31 1.4.1 Blocs et 31 1.4.2 Instructions conditionnelles31 1.4.3 Parcours des objets itérables, boucles for35 1.4.4 Continue, pass38 1.4.5 Listes en compréhension39 1.4.6 Boucle while40 1.4.7 Break ou pas break ?44 1.4.8 Procédures et fonctions 45 1.4.9 Compléments : sous-procédures et visibilité des variables50 1.4.10 Exercices51 1.5 Modules ou bibliothèques 54 1.5.1 L’instruction import54 1.5.2 Tableaux (array) de la bibliothèque numpy 56 1.5.3 Les graphiques avec matplotlib 1.6 Corrigés des exercices70 Chapitre 2 • Quelques algorithmes itératifs fondamentaux95 2.1 Au début était l’arithmétique96 2.1.1 La division euclidienne des entiers96 2.1.2 L’écriture binaire d’un entier Calcul de la moyenne et de la variance 100 2.2.1 Calcul conjoint et analyse 100 2.2.2 Méthode des trapèzes 102 2.3 Algorithmes de recherche séquentielle103 2.3.1 Listes ou tableaux 103 2.3.2 Recherche d’un élément dans une liste 104 2.3.3 Recherche des plus grands éléments d’une liste 106 2.3.4 Dictionnaires et comptage 110 2.4 Boucles imbriquées114 2.4.1 Valeurs les plus proches dans un tableau114 2.4.2 Recherche d’une sous-chaîne dans une chaîne de caractères 115 2.5 Algorithmes dichotomiques117 2.5.1 Algorithme de recherche dichotomique117 2.5.2 Exponentiation rapide, version itérative 120 2.6 Corrigés des exercices 122 Chapitre 3 • Récursivité143 3.1 Introduction143 3.1.1 Vocabulaire, premiers exemples 143 3.1.2 Quelques dessins de fractales 147 3.2 Mise en garde concernant l’efficacité des programmes récursifs 151 3.3 Mise en oeuvre157 3.4 Diviser pour régner160 3.4.1 Recherche de deux points réalisant la plus petite distance 161 3.4.2 Exponentiation rapide, version récursive 163 3.4.3 Recherche dichotomique dans une liste triée 164 3.4.4 Illustration avec des tris 166 3.5 Corrigés des exercices167 Chapitre 4 • Les tris189 4.2 Tri par insertion 190 4.3 Tri rapide : diviser pour régner192 4.4 Tri fusion 194 4.5 Tri par insertion dichotomique 196 4.6 Complexité des tris198 4.7 Sort dans Python 199 4.8 Recherche de la médiane en temps linéaire 200 4.9 Corrigés des exercices Chapitre 5 • Algorithmes gloutons207 5.1 Introduction207 5.1.1 Optimisation combinatoire 207 5.1.2 Le principe des algorithmes gloutonsgloutonnes211 5.2.1 Le rendu de monnaie 211 5.2.2 Sélection d’activités 213 5.2.3 Allocations de salles de cours 216 5.3 Bilan219 5.4 Corrigés des exercices220 Chapitre 6 • Traitement de l’image233 6.1 Représentation des images, formats, outils233 6.1.1 Tableaux à plusieurs dimensions et représentation des images233 6.1.2 Des fichiers images vers les tableaux de numpy234 6.2 Dessiner une droite à l’écran240 6.3 Transformations géométriques d’une image243 6.3.1 Agrandir : Homothétique d’une image avec k > 1244 6.3.2 Mode d’emploi pour faire tourner une image 245 6.4 Traitements par convolution249 6.4.1 Filtres linéaires et convolution 249 6.4.2 Quelques effets du filtrage linéaire255 6.4.3 Détection de contours256 6.5 Corrigés des exercices262 Partie II • Deuxième semestre Chapitre 7 • Calcul numérique : problématique et outils279 7.1 Représentation des nombres et erreurs de calcul279 7.1.1 Numérations décimale, binaire, hexadécimale 280 7.1.2 Représentation des entiers sur n bits 282 7.1.3 Les entiers multi-précision de Python285 7.1.4 Représentation des flottants sur n bits 288 7.1.5 Peut on calculer avec les flottants ? 293 7.1.6 Exercices299 7.2 Corrigés des exercices Chapitre 8 • Preuves et complexité des programmes 311 8.1 Spécification d’un algorithme311 8.1.1 Le vocabulaire 311 8.1.2 Vérifier les pré-conditions et les post-conditions 312 8.1.3 Exemples 315 8.2 Le point sur la notion de preuve d’un algorithme316 8.3 Le point sur la notion de complexité321 8.3.1 La place, le temps, la précision 321 8.3.2 Les outils : théorie et pratique323 8.3.3 Exemples basiques329 8.3.4 Complexité de l’algorithme d’Euclide330 8.4 Analyse des programmes récursifs 334 8.5 Exercices337 8.6 Corrigés des exercices340 Chapitre 9 • Graphes365 9.1 Définitions 365 9.2 Listes d’adjacence367 9.3 Matrices d’adjacence369 9.4 Parcours en profondeur, composantes connexes370 9.5 Parcours, versions itératives375 9.5.1 Piles et files 375 9.5.2 Parcours en largeur, procédure itérative 375 9.5.3 Parcours en profondeur, version itérative 378 9.6 Un algorithme de plus court chemin381 9.7 Graphes, amas et percolation 386 9.8 Corrigés des exercices 390 Chapitre 10 • Un bref aperçu de la programmation objet405 10.1 Les concepts de la programmation objet405 10.2 Une classe pour la structure de graphe406 10.3 Percolation, une implémentation objet411 Partie III • Troisième semestre Chapitre 11 • Bases de données, langage SQL421 11.1 Introduction 11.2 Qu’est ce qu’une base de données relationnelle ?422 11.2.1 Les relations comme ensembles de p-uplets 422 11.2.2 Modèle relationnel 423 11.3 Algèbre relationnelle426 11.3.1 La sélection 427 11.3.2 La projection 427 11.3.3 Le produit cartésien de deux tables, le renommage et la jointure428 428 11.3.4 La jointure 429 11.3.5 Conflits de noms d’attributs et renommage 430 11.3.6 Union, intersection et différence430 11.3.7 Récapitulatif et expressions de requêtes avec l’algèbre relationnelle 431 11.4 Langage de manipulation de données, SQ433 11.4.1 Les interrogations433 11.4.2 GROUP BY, HAVING et les fonctions d’agrégation439 11.5 Exercices 442 11.6 SQLite, PosgtreSQL, MySQL445 11.7 Corrigés des exercices447 Chapitre 12 • À propos des dictionnaires463 12.1 Dictionnaires ou tableaux associatifs463 12.1.1 Tableau associatif comme type de données463 12.1.2 Tableaux associatifs et tables de hachage466 12.1.3 Quelques fonctions de hachage467 12.2 Compression de texte : LZ78 469 12.3 Corrigés des exercices471 12.4 Annexe474 Chapitre 13 • Programmation dynamique477 13.1 Premiers exemples477 13.1.1 Plus longue sous-suite commune 477 13.1.2 Produit de matrices, parenthésages optimaux482 13.1.3 Problèmes éligibles à la programmation dynamique486 13.2 Autres exemples488 13.2.1 Distance d’édition488 13.2.2 Algorithme de Roy-Floyd-Warshall 490 13.3 Corrigés des exercices Chapitre 14 • Algorithmes pour l’étude des jeux507 14.1 Jeux sur graphes507 14.1.1 Exemples de jeux à deux joueurs 507 14.1.2 Représentation par des graphes, vocabulaire 510 14.2 Calcul des attracteurs dans les jeux d’accessibilité512 14.2.1 Jeu d’accessibilité 512 14.2.2 Attracteurs et pièges 513 14.3 Algorithme du minimax, heuristiques 517 14.3.1 Arbres517 14.3.2 L’algorithme du minimax 522 14.3.3 L’algorithme du minimax avec heuristiques 524 14.4 Corrigés des exercices525 14.5 Une classe pour représenter les arbres 535 Chapitre 15 • Algorithmes pour l’étiquetage et la classification537 15.1 Vocabulaire et définitions 537 15.1.1 Classement et classification automatique 537 15.1.2 Distances, similarités539 15.1.3 Inertie d’une partition 541 15.1.4 À propos d’intelligence artificielle543 15.2 Classement supervisé, k-plus proches voisins544 15.2.1 L’algorithme544 15.2.2 Les tests 545 15.3 Classification non supervisée, algorithme des k-moyennes548 15.4 Bibliothèque scikit-learn552 15.4.1 scikit-learn.datasets552 15.4.2 k-plus proches voisins avec scikit-learn553 15.4.3 k-moyennes avec scikit-learn 553 15.4.4 Lexique français anglais (US)556 15.5 Corrigés des exercices557 Glossaire de l’informatique générale569 Bibliographie585 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| INF/775 | Livre | bibliothèque sciences exactes | Empruntable |
