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

📋 Plan du Cours

1. Représentation des données et types
2. Langage C et structure d’un programme
3. Mémoire dynamique en C
4. Pointeurs et mémoire en C++
5. Allocation dynamique en C++
6. Python : syntaxe et fonctions
7. JSON et modules en Python
8. JavaScript et applications Web
9. Classes, modules et Node.js
10. Complexité des algorithmes

📖 1. Représentation des données et types

🔑 Notions clés & Définitions

• Système binaire : Un système de numération où chaque chiffre n’est qu’un 0 ou un 1.
• Bit : Un bit est la plus petite unité de données représentée par une valeur 0 ou 1.
• Octet (byte) : Un octet est un groupe de 8 bits utilisé pour mesurer la taille des données.
• Encodage ASCII : Un standard qui code des caractères à l’aide de 7 bits, couvrant des valeurs de 0 à 127.
• Encodage Unicode : Un standard mondial qui code des caractères, nombres et symboles avec une taille de 4 à 32 bits, avec une valeur par défaut de 16 bits (2 octets).

📝 Points essentiels

• Les données et instructions sont stockées en binaire (0 et 1) car le matériel manipule des bits en mémoire.
• Un compilateur traduit code et nombres/chaînes/couleurs/caractères en codes binaires compris par l’ordinateur.
• Tailles indiquées : 2 octets pour short, 4 octets pour int, 4 octets pour float, 8 octets pour long, et 8 octets pour double.
• Charactères : l’ASCII utilise 7 bits (0 à 127), l’Extended ASCII utilise 8 bits (128 à 255), et Unicode utilise 16 bits par défaut.
• Une chaîne est représentée comme une suite de caractères, chaque caractère occupant 8 bits à la suite des autres.
• Les couleurs sont codées en hexadécimal via RGB avec 6 valeurs hexadécimales (2 par couleur), comme #FF0000 pour le rouge.

📖 2. Langage C et structure d’un programme

🔑 Notions clés & Définitions

• Langage C fortement typé : Langage C où chaque donnée a un type connu, fixé à la déclaration et ne change pas ensuite.
• Directives du préprocesseur : Commandes placées au début du code qui sont traitées par le compilateur avant la compilation du programme.
• Fonction C : Bloc de code destiné à exécuter une tâche précise, appelé explicitement avec ses paramètres.
• Pointeur : Variable dont la valeur est une adresse mémoire, permettant d’accéder et manipuler des données stockées ailleurs.

📝 Points essentiels

• Chaque variable possède un type et ce type ne peut pas être modifié après déclaration en C.
• Le préprocesseur sert à ajouter des fonctionnalités au programme avant la phase de compilation.
• L’exécution du programme démarre dans la fonction main.
• Pour obtenir l’adresse d’une variable, on utilise l’opérateur & (exemple &age).
• Pour lire la valeur pointée, on utilise l’opérateur de déréférencement * (exemple *ptrAge).
• Pour compiler un fichier source : gcc -o outputFile File.c puis pour exécuter : ./outputFile.

💡 Astuce mémo

& = adresse, * = contenu : adresse avec & puis valeur avec *.

📖 3. Mémoire dynamique en C

🔑 Notions clés & Définitions

• Allocation dynamique : L’allocation dynamique est une procédure qui modifie la taille d’une structure de données pendant l’exécution du programme.
• malloc : malloc alloue dynamiquement un bloc unique de mémoire de taille donnée et renvoie un pointeur (type void*) à caster, ou NULL en cas d’échec.
• calloc : calloc réserve un espace contigu pour n éléments et initialise chaque bloc à 0, en renvoyant un pointeur de type à caster ou NULL si la mémoire manque.
• free : free libère la mémoire allouée dynamiquement afin d’éviter le gaspillage et de corriger la durée de vie de la zone mémoire.
• realloc : realloc change la taille (et potentiellement la localisation) d’un bloc déjà alloué en conservant les valeurs existantes, avec un échec signalé par NULL.

📝 Points essentiels

• Les fonctions d’allocation dynamique à connaître sont malloc(), calloc(), free() et realloc(), toutes déclarées dans <stdlib.h>.
• malloc a pour syntaxe ptr = (type*) malloc(byte-size) et échoue en renvoyant NULL si l’espace demandé est insuffisant.
• calloc a pour syntaxe ptr = (type*) calloc(n, element-size) où n est le nombre d’éléments et element-size la taille d’un élément, et renvoie NULL si l’allocation échoue.
• free se note free(ptr) et sert à désallouer la mémoire pointée par ptr pour réduire le gaspillage.
• realloc a pour syntaxe ptr = realloc(ptr, newSize) : elle peut déplacer la zone mémoire, conserve les valeurs déjà présentes et initialise les nouveaux blocs avec une valeur indéfinie (garbage), et échoue par NULL si l’espace manque.

📖 4. Pointeurs et mémoire en C++

🔑 Notions clés & Définitions

• Variable référence : Une variable référence est un alias d’une variable existante, créée avec l’opérateur & pour permettre de manipuler la même donnée via un autre nom.
• Adresse mémoire : Une adresse mémoire est l’emplacement où la valeur d’une variable est stockée, et l’opérateur & permet d’y accéder.
• Déréférencement : Le déréférencement utilise l’opérateur * pour accéder à la valeur située à l’adresse contenue dans un pointeur.

📝 Points essentiels

• L’opérateur & renvoie l’adresse mémoire d’une variable, typiquement affichée en hexadécimal (exemple : 0x6dfed4).
• Une référence s’écrit avec &, et toute modification via la référence agit sur la variable d’origine.
• Un pointeur est déclaré avec * et reçoit l’adresse via &, puis peut pointer vers une variable de même type.
• L’opérateur *ptr donne la valeur pointée, et peut aussi être utilisé pour modifier directement la variable cible.
• Sans déréférencement, l’expression avec un pointeur (ex. ptr) représente l’adresse, alors que *ptr représente la valeur.

💡 Astuce mémo

& = adresse, * = valeur (adresse → *ptr pour obtenir la donnée).

📖 5. Allocation dynamique en C++

🔑 Notions clés & Définitions

• Opérateur new : L’opérateur new réserve dynamiquement un bloc de mémoire et retourne un pointeur vers l’objet (ou le tableau) créé.
• Opérateur delete : L’opérateur delete libère la mémoire précédemment allouée pour un objet créé par new.
• new (nothrow) : La forme new (nothrow) rend l’allocation non-échouable par exception et retourne un pointeur nul si l’allocation échoue.

📝 Points essentiels

• Un pointeur peut être initialisé à NULL puis recevoir l’adresse retournée par new avant toute utilisation.
• Pour libérer correctement un objet créé avec new, on utilise delete p et pas delete[].
• Pour libérer correctement un tableau créé avec new int[n], on utilise delete[] q et pas delete q.
• new T(valeur) initialise directement l’objet alloué avec la valeur donnée, par exemple new int(25).
• Quand on utilise new (nothrow), on teste le pointeur avec if (!p) pour détecter l’échec avant d’écrire via *p.
• Après un delete/delete[] sur le pointeur, il ne faut pas réutiliser ce pointeur pour accéder à la zone libérée.

💡 Astuce mémo

new construit en mémoire, delete défait : delete pour 1, delete[] pour tableau.

📖 6. Python : syntaxe et fonctions

🔑 Notions clés & Définitions

• Indentation en Python : L’indentation (espaces en début de ligne) structure le code et délimite les blocs comme ceux des fonctions, boucles et classes.
• Fonction Python : Une fonction Python est définie avec le mot-clé def et reçoit des paramètres qui peuvent être fournis autrement selon leur forme.
• Arguments nommés : Les arguments nommés s’écrivent sous la forme clé=valeur et permettent de fournir des valeurs sans dépendre de l’ordre des paramètres.
• **kwargs : **kwargs collecte un nombre inconnu d’arguments nommés dans un dictionnaire transmis à la fonction.

📝 Points essentiels

• Une commande Python peut s’étendre sur de nouvelles lignes, et la structure des blocs est imposée par l’indentation, qui est obligatoire.
• Les variables sont créées quand on leur assigne une valeur, sans commande de déclaration ni type fixé au départ, et elles peuvent changer de type.
• La fonction type() permet de récupérer le type d’une variable, et les chaînes peuvent être écrites avec des guillemets simples ou doubles.
• Pour exécuter un script, on lance Python avec le fichier en extension .py, par exemple python helloworld.py.
• Une fonction s’écrit avec def, et peut recevoir des arguments via arguments nommés (clé=valeur), *args et **kwargs.
• Le mot-clé return renvoie une valeur, et pass définit une fonction vide sans contenu.

📖 7. JSON et modules en Python

🔑 Notions clés & Définitions

• JSON : Format texte pour stocker et échanger des données, utilisé pour envoyer des informations entre un serveur et un programme.
• module Python : Fichier Python regroupant des fonctions que l’on peut réutiliser en les important dans un autre programme.
• paquet json : Bibliothèque intégrée de Python qui fournit des fonctions pour charger et produire des données JSON.

📝 Points essentiels

• En Python, on importe le module json avec import json pour traiter des données au format JSON.
• json.loads transforme une chaîne JSON en dictionnaire Python, puis on accède aux valeurs via les clés.
• json.dumps convertit une structure Python (comme un dictionnaire) en chaîne JSON.
• Un module Python se crée en enregistrant du code dans un fichier avec l’extension .py et il se réutilise via import.
• Lorsqu’on importe un module, on peut appeler ses fonctions comme module.nom_fonction après l’import.
• L’exemple indique qu’une donnée JSON peut représenter une semaine sous forme d’objets à clés (jours) et valeurs (aliments).

📖 8. JavaScript et applications Web

🔑 Notions clés & Définitions

• ECMA-262 : ECMA-262 : nom officiel du standard qui formalise JavaScript, avec une date de publication indiquée dans le cours.
• ECMAScript : ECMAScript : nom officiel du langage JavaScript, donné par le standard ECMA-262.
• Balise script : Balise script : balises HTML <script>...</script> qui délimitent le code JavaScript dans une page Web.
• this : this : mot-clé qui désigne l’objet courant selon le contexte d’une méthode, d’une instruction isolée ou d’un gestionnaire d’événement.

📝 Points essentiels

• JavaScript a été inventé par Brendan Eich en 1995, et le standard associé date de 1997 via ECMA-262.
• Dans une page HTML, le code JavaScript est placé entre les balises <script> et </script>, car JavaScript est le langage de script par défaut.
• HTML sert à définir le contenu des pages, CSS décrit la mise en page, et JavaScript sert à programmer le comportement des pages.
• Les versions citées sont ES1/ES2/ES3 (1997-1999) pour l’original, ES5 (2009) pour la première grande révision, puis ES6 (2015) pour la seconde révision.
• Le mot-clé this désigne l’objet propriétaire dans une méthode, le global lorsqu’il est seul, et l’élément ayant reçu l’événement dans un gestionnaire d’événement.

💡 Astuce mémo

Eich 1995 → ECMA-262 1997 : invention + standard, puis ES5 2009 et ES6 2015 pour les grandes révisions.

📖 9. Classes, modules et Node.js

🔑 Notions clés & Définitions

• Classes JavaScript : Une classe JavaScript est un modèle qui sert à créer des objets JavaScript, plutôt qu’un objet directement exploitable.
• Méthode constructor : Le constructor est une méthode spéciale exécutée automatiquement lors de la création d’une nouvelle instance pour initialiser les propriétés.
• Modules JavaScript : Un module JavaScript regroupe du code dans un fichier séparé et le partage via export et import.
• Node.js : Node.js est un environnement serveur open source qui exécute du JavaScript côté serveur.

📝 Points essentiels

• Les classes JavaScript sont introduites par ECMAScript 2015 (ES6) et fonctionnent comme des templates pour objets.
• Le constructor doit s’appeler exactement constructor, est appelé automatiquement à chaque new, et initialise les propriétés (sinon, un constructor vide est créé).
• Un module JavaScript peut exporter une fonction ou une variable, avec exports nommés ou un export par défaut unique par fichier.
• Les modules JavaScript ne fonctionnent qu’avec le protocole HTTP(s).
• Dans Node.js, on peut charger un module avec require, puis créer un serveur HTTP et l’écouter sur un port (exemple : 8080 avec localhost:8080).
• Les modules Node.js sont partagés via exports : ils rendent des propriétés et méthodes disponibles depuis le fichier importé.

💡 Astuce mémo

Classe = plan ; constructor = mise en route automatique de chaque nouvelle maison (instance).

📖 10. Complexité des algorithmes

🔑 Notions clés & Définitions

• Complexité asymptotique : La complexité asymptotique décrit comment le temps ou l’espace d’un algorithme évoluent quand la taille d’entrée $n$ devient grande.
• Notations asymptotiques : Les notations $O$, mega et 9 encadrent la croissance du temps d’exécution d’un algorithme pour de grandes valeurs de $n$.
• Complexités best/avg/worst : Le meilleur, moyen et pire cas mesurent le temps minimal, typique et maximal exécuté par un algorithme selon les entrées.

📝 Points essentiels

• Un bon algorithme est jugé sur la correction (bon résultat), la finitude (arrêt en un nombre fini d’étapes) et l’efficacité (temps et mémoire utilisés au mieux).
• La complexité en espace s’écrit comme la somme de l’espace auxiliaire (mémoire en plus) et de l’espace occupé par les valeurs d’entrée.
• Pour comparer des algorithmes, l’analyse asymptotique vise une mesure indépendante de la machine et cherche le meilleur compromis temps–mémoire.
• La notation $O(g(n))$ donne une borne supérieure : pour des constantes $c$ et $n_0$, on a $0\le f(n)\le c\cdot g(n)$ pour tout $n\ge n_0$.
• La notation $\Omega(g(n))$ donne une borne inférieure : pour des constantes positives $c$ et $n_0$, on a $0\le c\cdot g(n)\le f(n)$ pour tout $n\ge n_0$.
• Dans le cours, seules les bornes $O$ sont utilisées pour donner une limite haute (pire cas), en ignorant les termes de plus faible ordre quand $n$ devient grand.

💡 Astuce mémo

Borne en haut $O$ (Over), borne en bas $\Omega$ (Under), borne serrée $\Theta$ (Tight) : haut→pire, bas→meilleur, serré→équilibré.

📅 Repères chronologiques

📊 Tableaux de synthèse

Différences C et C++ (du cours)

Notations asymptotiques (bornes)

⚠️ Pièges & confusions fréquents

1. Confondre l’encodage ASCII (7 bits, valeurs 0 à 127) et l’Extended ASCII (8 bits, 128 à 255).
2. Croire que chaque caractère prend forcément 7 bits : en chaîne, le cours indique 8 bits par caractère (suite de caractères).
3. En C, confondre *ptr (valeur pointée) et ptr (adresse) quand le déréférencement n’est pas appliqué.
4. Oublier de distinguer realloc : elle peut déplacer la zone mémoire, conserve les valeurs existantes et les nouveaux blocs sont indéfinis (garbage).
5. Mélanger delete et delete[] en C++ : delete pour 1 objet, delete[] pour tableau (new int[n]).
6. En C, ne pas gérer l’échec d’allocation : malloc/calloc/realloc renvoient NULL si l’espace manque.
7. Confondre JSON et JavaScript : le cours indique que les noms JSON nécessitent des guillemets doubles, contrairement aux objets JS vus dans les exemples.

✅ Checklist Examen

1. 1. Savoir définir bit, octet/byte, et l’idée que tout est représenté en binaire (digits 0 et 1) dans la mémoire.
2. 1. Savoir donner les tailles du cours : short=2 octets, int=4 octets, float=4 octets, long=8 octets, double=8 octets.
3. 1. Savoir distinguer ASCII (7 bits 0 à 127), Extended ASCII (8 bits 128 à 255) et Unicode (4 à 32 bits, par défaut 16 bits).
4. 1. Savoir interpréter l’opérateur & en C (adresse mémoire) et l’opérateur * en C (déréférencement : valeur pointée).
5. 1. Savoir écrire/identifier les syntaxes et conditions d’échec de malloc, calloc, free et realloc (NULL en cas d’échec).
6. 1. Savoir expliquer free(ptr) en termes de désallocation et réduction du gaspillage (durée de vie de la zone mémoire).
7. 1. Savoir appliquer new/delete en C++ : new retourne un pointeur, delete libère, et tester new (nothrow) avec if (!p).
8. 1. Savoir associer correctement delete vs delete[] selon le cas (objet vs tableau) et comprendre l’interdiction de réutiliser le pointeur après delete/delete[].
9. 1. Savoir les règles Python du cours : indentation obligatoire, exécution python fichier.py, variables créées à l’affectation, et role de def/return/pass + *args/**kwargs.
10. 1. Savoir traiter JSON et modules : import json, json.loads/dumps, création de module avec .py et import, puis rappeler que JS modules nécessitent HTTP(s).
11. 1. Savoir la logique JavaScript/ECMAScript du cours : balise <script>, this (contexte méthode/isolé/gestionnaire), versions ES1/ES2/ES3 (1997-1999), ES5 (2009), ES6 (2015).
12. 1. Savoir la complexité : propriétés (correction/finiteness/efficiency), définitions time/space, et différencier O (borne supérieure pire cas) vs ω (borne inférieure) vs Θ (borne serrée), ainsi que best/avg/worst.