Fiche de révision : Introduction à la Programmation et Analyse

📋 Plan du Cours

1. Objectifs et compétences du programme
2. Programmation Python au premier semestre
3. Méthodes de programmation et analyse
4. Représentation des nombres
5. Graphes et plus courts chemins
6. Bases de données
7. Dictionnaires, programmation dynamique et jeux
8. Langage Python

📖 1. Objectifs et compétences du programme

🔑 Notions clés & Définitions

• Analyse et modélisation : Compétence centrée sur l’identification du problème et sur la représentation des données avec des objets conceptuels adaptés.
• Conception d’une solution : Compétence qui consiste à découper un problème en sous-problèmes, choisir une stratégie et décrire une démarche ou une structure de données.
• Mise en œuvre : Compétence consistant à traduire une solution algorithmique ou une structure de données dans un langage de programmation ou de requête.
• Justification et critique : Compétence qui consiste à prouver/corroborer la correction ou à évaluer et contrôler la solution produite.
• Communication et documentation : Compétence qui regroupe la présentation des choix et résultats, ainsi que la traçabilité de la production et de l’implémentation.

📝 Points essentiels

• Le programme vise six compétences : analyser/modéliser, concevoir, décrire/spécifier, mettre en œuvre, justifier/critiquer, communiquer et documenter.
• La progression s’appuie sur la résolution régulière de problèmes par une approche algorithmique et des activités de programmation.

💡 Astuce mémo

6 compétences comme un cycle : Analyser → Concevoir → Spécifier → Implémenter → Prouver → Communiquer.

📖 2. Programmation Python au premier semestre

🔑 Notions clés & Définitions

• Spécification des fonctions : Ensemble d’informations que l’on associe aux fonctions/programmes pour préciser précisément entrées et sorties attendues.
• Jeux de tests : Ensemble de cas d’essai associant des entrées à des sorties attendues pour vérifier le comportement d’un programme.
• Complexité en pire cas : Estimation du coût d’un algorithme lorsque l’exécution se fait dans le scénario le plus défavorable.
• Validation par invariants : Technique de preuve liée à la correction des algorithmes via des propriétés conservées au cours des boucles.

📝 Points essentiels

• Les séances de travaux pratiques consolident la programmation Python déjà vue au lycée et mettent en place un environnement de travail.
• Une discipline est exigée : spécification précise, annotations/commentaires, et jeux de tests.
• La complexité introduite au premier semestre est l’estimation asymptotique du coût dans le cas le pire.
• Les outils de validation incluent variants et invariants pour raisonner sur la correction.

💡 Astuce mémo

SPécifier + TESTer + (Pire cas) + (Variants/Invariants) : STTPI.

📖 3. Méthodes de programmation et analyse

🔑 Notions clés & Définitions

• Instruction et expression : Notion distinguant l’affectation comme instruction et l’évaluation comme expression dans le langage.
• Précondition et postcondition : Annotations qui formalisent ce qui doit être vrai avant et ce qui doit être vrai après l’exécution d’un bloc ou d’une fonction.
• Assertion : Vérification formulée dans le code qui, si elle échoue, provoque l’arrêt du programme.
• Variant de boucle : Grandeur utilisée pour démontrer la terminaison d’une boucle à partir d’exemples étudiés.
• Invariant de boucle : Propriété conservée pendant l’exécution d’une boucle, utilisée pour raisonner sur la correction.

📝 Points essentiels

• La correction est partielle quand le résultat est correct à l’arrêt, et totale quand elle est partielle et que l’algorithme termine.
• La terminaison peut être démontrée sur des exemples à l’aide d’un variant de boucle.
• Les jeux de tests doivent être écrits à la main avec entrées et sorties attendues, en testant aussi les limites.
• La complexité temporelle est abordée dans le pire cas en ordre de grandeur, et la notion de complexité en espace peut être discutée sur des exemples.

💡 Astuce mémo

Correction totale = (partielle) + (terminaison), grâce au couple invariant/variant.

📖 4. Représentation des nombres

🔑 Notions clés & Définitions

• Représentation des entiers fixes : Schéma de stockage d’entiers positifs sur un mot de taille fixe en mémoire.
• Complément à deux : Schéma de représentation des entiers signés sur un mot de taille fixe.
• Entiers multi-précision : Entiers de Python qui ne sont pas limités par une taille fixe de mot machine.
• Flottants : Représentation sur mots de taille fixe basée sur une mantisse et un exposant.

📝 Points essentiels

• La conversion de base n’est pas un objectif de formation, mais la représentation mémoire est utilisée pour expliquer des difficultés de calcul.
• Pour les flottants, la précision limite les résultats, notamment pour effectuer des comparaisons entre valeurs.
• 0 est représenté en flottants, et le programme n’aborde pas les nombres dénormalisés, les infinis ni NaN.
• Les opérations sur les entiers multi-précision posent une difficulté d’évaluation de leur complexité arithmétique.

💡 Astuce mémo

Entiers : taille fixe vs multi-précision ; Réels : impossibilités de représenter certains nombres ; Flottants : mantisse + exposant + précisions dangereuses.

📖 5. Graphes et plus courts chemins

🔑 Notions clés & Définitions

• Graphe orienté : Modèle de graphe dont les connexions entre sommets ont une direction via des arcs.
• Liste d’adjacence : Représentation d’un graphe en associant à chaque sommet la liste de ses voisins via des arêtes/arcs.
• Matrice d’adjacence : Représentation d’un graphe sous forme de matrice indiquant pour chaque paire de sommets la présence d’une relation.
• Dijkstra : Algorithme de recherche de plus court chemin dans un graphe pondéré à poids positifs.
• File de priorité : Structure de données utilisée pour extraire efficacement l’élément minimum au cours de l’algorithme.

📝 Points essentiels

• Le programme introduit les graphes avec les notions sommet/nœud, arc/arête, boucle, et degré (entrant/sortant) pour l’orienté.
• Les graphes sont implémentés via listes d’adjacence (listes ou dictionnaires) et matrices d’adjacence, sans multi-arcs ni multi-arêtes.
• Les parcours utilisent aussi piles et files, avec une sensibilisation à l’efficacité d’une file via collections.deque.
• La recherche de plus court chemin vise les poids positifs et utilise Dijkstra, avec A* présenté comme variante par heuristique.
• La détection de cycles et la connexité sont traitées pour le cadre non orienté et via des algorithmes adaptés au modèle de représentation.

💡 Astuce mémo

Dijkstra = poids positifs ; A* = Dijkstra + heuristique ; Deque = file qui ne traîne pas.

📖 6. Bases de données

🔑 Notions clés & Définitions

• Schéma de tables : Description des tables et de leurs attributs/colonnes, avec des types de données et un domaine associé.
• Clé primaire : Contrainte identifiant des enregistrements dans une table, pas forcément liée à un unique attribut.
• Clé étrangère : Référence d’une association vers une entité via une clé primaire pour relier des tables dans le modèle entité-association.
• Jointure interne : Opération SQL qui combine des tables à partir d’un prédicat d’égalité entre attributs de tables différentes.
• Agrégation SQL : Regroupement de lignes et calcul de valeurs globales via des fonctions comme MIN, MAX, SUM, AVG, COUNT.

📝 Points essentiels

• Le programme se limite à une description applicative en SQL et n’enseigne pas l’algèbre relationnelle ni le calcul relationnel.
• NULL est hors programme, et les opérateurs au programme incluent +, -, *, /, =, <>, <, <=, >, >=, AND, OR, NOT.
• Les associations 1-1 et 1-* se traduisent en SQL via des clés primaires et clés étrangères, avec séparation d’un - en deux associations 1-*.
• SELECT utilise WHERE pour filtrer, DISTINCT/LIMIT/OFFSET/ORDER BY pour contrôler le résultat, et HAVING pour filtrer des agrégats.
• Les jointures internes ont la forme T1 JOIN T2 ... ON ϕ où ϕ est une conjonction d’égalités.
• Les fonctions d’agrégation et GROUP BY permettent de calculer des statistiques, et des requêtes imbriquées sont présentées sur quelques exemples.

💡 Astuce mémo

WHERE filtre les lignes, HAVING filtre les groupes : double filtre dans SQL.

📖 7. Dictionnaires, programmation dynamique et jeux

🔑 Notions clés & Définitions

• Dictionnaire Python : Structure associant des clés à des valeurs, utilisée ici via des usages de boîte noire et des notions de hachage.
• Sous-structure optimale : Propriété indiquant que la solution optimale s’obtient à partir de solutions optimales de sous-problèmes.
• Chevauchement des sous-problèmes : Situation où les sous-problèmes se répètent, rendant utile la mémoïsation des résultats intermédiaires.
• Mémoïsation : Technique stockant des résultats pour éviter de recalculer des sous-problèmes identiques.
• Jeu sur graphe : Modélisation d’un jeu à deux joueurs où l’évolution des états suit un graphe biparti.

📝 Points essentiels

• Les dictionnaires sont utilisés en boîte noire dès la première année, et leurs principes (hachage et limitations des clés) sont présentés en deuxième année.
• En programmation dynamique, la mémoïsation peut être implémentée avec un dictionnaire et pose aussi un enjeu de complexité en mémoire.
• La reconstruction d’une solution optimale se fait à partir des informations calculées pendant la dynamique.
• Les jeux considérés sont à deux joueurs modélisés par un graphe biparti, avec stratégies sans mémoire et trois types d’états finals.
• Pour ces jeux, la détermination des positions gagnantes utilise le calcul des attracteurs et la construction de stratégies gagnantes.
• Min-max avec heuristique est présenté, tandis que l’élagage alpha-beta n’est pas au programme.

💡 Astuce mémo

PD = optimal + chevauchement, donc mémoïsation ; Jeux = attracteurs + min-max (avec heuristique).

📖 8. Langage Python

🔑 Notions clés & Définitions

• Typage dynamique : Principe où l’interpréteur détermine le type lors de l’exécution plutôt qu’à la compilation.
• Portée lexicale : Règle de recherche d’une variable : priorité au scope local de fonction, sinon au scope global du module.
• Appel par valeur : Principe d’évaluation : l’argument est évalué puis sa valeur est transmise à la fonction.
• Dictionnaire : Type de données indexé par clés, construit avec des paires clé:valeur et accessible via une clé.
• Assertions : Instruction assert qui valide une condition et arrête le programme si la condition est fausse.

📝 Points essentiels

• Python exige la compréhension des bases listées : indentation, portée lexicale, et appel de fonction par valeur.
• Sur les booléens, and/or/not sont pris en charge et and/or sont paresseux.
• Les types structurés incluent listes (compréhension, append, pop en fin), tuples/chaînes (len, indices, tranche) et dictionnaires (accès, insertion, présence in, len, copy).
• Les structures de contrôle au programme couvrent if/elif/else, while (sans else) avec break/return, et for (sans else) avec itération sur range/chaîne/tuple/liste/dictionnaire via keys et items.
• Les opérations arithmétiques et comparaisons au programme incluent notamment int : +, -, *, //, **, % (opérandes positifs) et float : +, -, *, /, **.
• En Python, assert est disponible sans message, et l’annexe exige aussi un ensemble de primitives de base : commentaire #, print simple, import, et fonctions de base pour fichiers texte.

💡 Astuce mémo

Si tu sais and/or paresseux + assert + portée lexicale, tu maîtrises l’ossature de l’annexe Python.

⚠️ Pièges & confusions fréquents

1. Confondre correction partielle et correction totale : totale exige à la fois correction à l’arrêt et terminaison.
2. Penser que WHERE et HAVING font la même chose : WHERE filtre des lignes alors que HAVING filtre des groupes après agrégation.
3. Croire que la représentation en flottants permet de comparer des valeurs comme des réels exacts : la précision peut invalider des comparaisons.
4. Utiliser une structure de file inefficace pour des parcours : les files via listes de Python posent des problèmes d’efficacité face à deque.
5. Essayer d’appliquer les algorithmes de plus courts chemins pondérés positifs à des graphes à poids non positifs sans adaptation.
6. Mélanger graphes orientés et non orientés : les notions de degré (entrant/sortant) et la connexité/cycles ne se traitent pas pareil.
7. Confondre programmation dynamique et glouton : la dynamique s’appuie sur sous-structure optimale et mémoïsation pour éviter des recomputations.

✅ Checklist Examen

1. Énoncer les six compétences visées et donner ce que recouvrent analyse/modélisation et conception d’une solution.
2. Décrire en quoi consistent la spécification des fonctions, les annotations/commentaires et les jeux de tests à la main.
3. Expliquer la différence entre complexité asymptotique en pire cas et d’autres mesures, au moins par ordre de grandeur.
4. Utiliser variants pour argumenter la terminaison et invariants pour argumenter la correction d’une boucle sur des exemples.
5. Définir et distinguer instruction vs expression, et reconnaître l’intérêt des préconditions/postconditions et des assertions.
6. Déterminer ce qui est hors programme en représentation des nombres : pas de norme IEEE-754, ni dénormalisés/infinis/NaN.
7. Définir vocabulaire des graphes : sommet, arc/arête, boucle, degré et chemin, et savoir écrire $G=(S,A)$ avec la bonne signification.
8. Comparer listes d’adjacence et matrices d’adjacence comme deux représentations, et savoir comment elles servent aux parcours.
9. Décrire l’objectif “plus court chemin” avec poids positifs et le rôle de Dijkstra, et citer le lien avec A* par heuristique.
10. Traduire des associations 1-1 et 1-* via clés primaires et clés étrangères dans une modélisation entité-association.
11. Écrire des requêtes SELECT avec WHERE, DISTINCT, ORDER BY, LIMIT/OFFSET, et distinguer WHERE de HAVING pour filtrer avant/après agrégation.
12. Utiliser UNION/INTERSECT/EXCEPT et produit cartésien, et savoir écrire des jointures internes sur des conjonctions d’égalités.
13. Expliquer les idées de programmation dynamique : sous-structure optimale, chevauchement, mémoïsation, et reconstruction à partir des calculs.
14. Implémenter/mentionner l’usage typique des dictionnaires en programmation dynamique pour mémoriser des résultats intermédiaires.