Algorithmique intermédiaire : analyse d'algorithmes, structures de données

Thème 1: Analyse d'algorithmes: complexité temporelle et preuves

Objectifs:

• Comprendre que l'exécution d'une opération n'est pas instantanée
• Bien faire la différence entre "une ligne de code" et "une opération" car une ligne de code peut provoquer de nombreuses opérations.
• Savoir calculer la complexité temporelle d'un algorithme lorsque le paramètre n est précisé, ainsi que les opérations à compter.
• Savoir dire, entre deux algorithmes ayant des ordres de grandeur différents, lequel est le plus efficace. En particulier, bien comprendre la différence entre complexité d'ordre constant (le nombre d'opérations ne dépend pas de la taille de l'entrée) et d'ordre linéaire (le nombre d'opérations est proportionnel à la taille de l'entrée).
• Savoir estimer le temps d'exécution d'un algorithme à partir du nombre d'opérations par seconde et de la complexité de l'algorithme.
• Savoir prouver qu'un algo est correct par rapport aux spécifications demandées grâce à un invariant de boucle, dans des cas simples
• Savoir prouver qu'un algo avec une boucle Tant Que termine.