Fiche de révision : Spécification et algorithmique en C++

📋 Plan du Cours

1. Algorithmes et complexité
2. Entrées et sorties
3. Spécification et propriétés
4. Types variables et opérateurs
5. Structures de contrôle
6. Fonctions et assertions
7. Pile tas et pointeurs
8. Traitement des files
9. Compilation séparée
10. Makefile et dépendances
11. Algorithmes de tri

📖 1. Algorithmes et complexité

🔑 Notions clés & Définitions

• Algorithme : Suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre une classe de problèmes.

★ À maîtriser

📌 Un algorithme est indépendant du langage et de la machine, tandis qu’un programme traduit cet algorithme dans un langage de programmation et dépend du paradigme utilisé.

📌 La première version du calcul de la somme de 1 à n effectue n additions, tandis que la version de Gauss $s = \frac{n(n+1)}{2}$ effectue une addition, une multiplication et une division.

Compléments

• La programmation dynamique stocke dans des tableaux les solutions de sous-problèmes afin de les réutiliser au lieu de recalculer plusieurs fois les mêmes sous-problèmes.

💡 Astuce mémo

Algorithme indépendant du langage, programme dépendant d’un langage

📖 2. Entrées et sorties

★ À maîtriser

📌 La lecture et l’écriture au clavier nécessitent la bibliothèque iostream et utilisent respectivement std::cin et std::cout.

📌 L’ouverture d’un fichier avec ios::in permet de lire, avec ios::out d’écrire en écrasant le contenu existant, et avec ios::app|ios::out d’écrire à la suite du contenu existant.

Compléments

• Un fichier utilisé par un flux est ouvert avec open, lu ou écrit, puis fermé avec close.

💡 Astuce mémo

cin lit, cout écrit, fstream échange avec les fichiers

📖 3. Spécification et propriétés

🔑 Notions clés & Définitions

• Correction : Propriété d’un algorithme qui obtient les résultats prévus par sa spécification en fonction de ses entrées.
• Complexité temporelle : Ordre de grandeur, en fonction de la taille N de l’entrée, du nombre d’opérations effectuées par un programme.

📝 Points essentiels

• Les propriétés fondamentales d’un algorithme sont : (Knuth) :
  • la finitude
  • la définition précise
  • les entrées
  • les sorties
  • le rendement

💡 Astuce mémo

F-D-E-S-R : finitude, définition, entrées, sorties, rendement

📖 4. Types variables et opérateurs

🔑 Notions clés & Définitions

• Variable : Zone mémoire dotée d’un nom et d’un type déclaré avant son utilisation, dont la valeur peut être modifiée.

★ À maîtriser

• Les types de données principaux sont :
  • int pour les entiers
  • float ou double pour les réels
  • char pour les caractères
  • bool pour les booléens
  • string pour les chaînes de caractères

Compléments

📌 L’affectation modifie la valeur d’une variable, tandis qu’une comparaison produit un booléen à partir de deux expressions de même type.

📖 5. Structures de contrôle

📝 Points essentiels

• Une boucle for répète un traitement selon une initialisation, une condition et une évolution de l’indice.

📌 Une boucle while évalue sa condition avant d’entrer dans le corps, qui peut donc ne jamais être exécuté, et cette condition doit pouvoir évoluer.

📌 Dans un tableau de taille N indexé à partir de zéro, les indices valides vont de 0 à N-1 ; utiliser i <= N provoque un accès hors limites lorsque i vaut N.

💡 Astuce mémo

if, switch, for, while : choisir puis répéter

📖 6. Fonctions et assertions

🔑 Notions clés & Définitions

• Pré-condition : Condition que doivent respecter les paramètres d’une fonction ou d’un algorithme avant son exécution.

📝 Points essentiels

📌 Une fonction est caractérisée par son nom, ses paramètres avec leurs types et le type de son résultat, et elle permet de réutiliser un traitement sans copier-coller le code.

📌 Une assertion vérifie une condition de programmation et provoque l’arrêt du programme si cette condition est fausse, mais elle peut être désactivée en mode Release avec -DNDEBUG.

💡 Astuce mémo

Précondition violée → assertion échouée

📖 7. Pile tas et pointeurs

🔑 Notions clés & Définitions

• Pointeur : Type qui contient l’adresse d’une zone mémoire et permet d’accéder à la valeur située à cette adresse par déréférencement.

📝 Points essentiels

📌 La pile stocke notamment les paramètres d’appel et les variables locales avec une désallocation automatique selon le modèle LIFO, tandis que le tas sert à l’allocation dynamique et doit être libéré explicitement.

📌 En C++, l’opérateur new alloue dynamiquement une variable et renvoie son adresse, tandis que delete libère la mémoire correspondante.

💡 Astuce mémo

Pile automatique et LIFO, tas dynamique et libération explicite

📖 8. Traitement des files

🔑 Notions clés & Définitions

• File : Ensemble non vide possédant un premier élément, un procédé pour obtenir l’élément suivant et un procédé pour détecter la fin.

★ À maîtriser

• 🔄 Le schéma général de traitement est : initialiser les données, obtenir le premier élément, traiter l’élément courant tant qu’il n’est pas final, obtenir l’élément suivant

Compléments

• Pour compter les L d’une phrase, on lit des caractères jusqu’au point '.', puis on incrémente le compteur lorsque le caractère courant vaut 'L'.

💡 Astuce mémo

Premier élément → traitement → élément suivant → butée

📖 9. Compilation séparée

★ À maîtriser

📌 Chaque fichier .cpp contient des définitions de fonctions, chaque fichier .h déclare des fonctions, et les fichiers .o sont produits par compilation avant l’édition des liens.

• La compilation séparée consiste à compiler chaque fichier source en fichier objet, puis à assembler tous les fichiers objets lors de l’édition des liens pour produire l’exécutable.

Compléments

📌 Un fichier d’en-tête doit être protégé contre les inclusions multiples avec des macros conditionnelles ou avec #pragma once.

💡 Astuce mémo

.cpp → .o → édition des liens → exécutable

📖 10. Makefile et dépendances

🔑 Notions clés & Définitions

• Makefile : Fichier décrivant des règles de production et de dépendance permettant à la commande make de reconstruire les fichiers nécessaires.

📝 Points essentiels

📌 Une règle de Makefile a la forme cible: dépendances suivie, sur une ligne précédée d’une tabulation, de la commande de production de la cible.

📌 Si une dépendance est plus récente que sa cible, make exécute la règle de production correspondante et propage cette reconstruction dans le graphe des dépendances.

💡 Astuce mémo

Fichier source plus récent → reconstruction des dépendances

📖 11. Algorithmes de tri

★ À maîtriser

📌 Le tri par sélection recherche le minimum dans la partie non triée et l’échange avec son premier élément ; il est en place, non stable et réalise O(n²) comparaisons et O(n) échanges.

• Le tri par insertion considère la partie gauche comme triée, décale vers la droite les éléments supérieurs à la clé, puis insère la clé à sa position correcte.

• Le tri par insertion est en place et stable, avec une complexité O(n²) au pire et en moyenne, mais O(n) lorsque le tableau est déjà trié.

📌 Le tri rapide choisit un pivot, partitionne le tableau autour de ce pivot, puis trie récursivement les deux sous-parties ; sa complexité moyenne est O(n log n) et son pire cas est O(n²).

Compléments

• Le tri à bulles compare les éléments adjacents, échange ceux qui sont dans le mauvais ordre et répète les passages jusqu’à ce qu’aucun échange ne soit effectué.

💡 Astuce mémo

Sélection choisit, insertion décale, bulles échangent, rapide partitionne

📊 Tableaux de synthèse

Comparaison des tris

Types de mémoire