Introduction à la Complexité Algorithmique

📋 Plan du Cours

1. Modèle de calcul
2. Complexité algorithmique
3. Analyse d’un algorithme
4. Outils mathématiques
5. Calcul de xn
6. Algorithmes récursifs
7. Algorithmes itératifs
8. Analyse de la validité
9. Notations de Landau
10. Croissance des fonctions
11. Notions de limite
12. Complexités classiques

📖 1. Modèle de calcul

🔑 Notions clés & Définitions

• Algorithme : procédure pas-à-pas permettant de résoudre un problème donné. Il doit être précis, fini, et efficace, en suivant une suite d'instructions élémentaires pour atteindre un résultat. AUTEUR (date) : « Un algorithme est une procédure déterministe pour résoudre un problème » (source).
• Spécification d’un algorithme : description formelle comprenant le nom, les paramètres d’entrée, la valeur de sortie, et éventuellement des commentaires. Elle définit précisément ce que l’algorithme doit faire, facilitant sa mise en œuvre et sa validation. AUTEUR (date) : « La spécification précise un algorithme en indiquant ses paramètres et ses résultats attendus » (source).
• Déclaration de variable : étape où l’on réserve un espace mémoire pour stocker une donnée, en lui attribuant un nom. Elle permet de manipuler des données durant l’exécution de l’algorithme. AUTEUR (date) : « La déclaration de variable est une instruction qui réserve un espace mémoire » (source).
• Instruction élémentaire : opération indivisible, comme une affectation, une opération arithmétique ou un test…