Complexité algorithmique
Durée2h30Objectifs de la séance
Vous n’êtes certainement pas le/la premier(ère) développeur(se) à être confronté(e) à votre problème actuel. Cela signifie certainement que plusieurs solutions pour le résoudre ont déjà été envisagées.
Comment les comparer et sélectionner la plus appropriée ? C’est la question centrale abordée dans cette séance. Vous allez acquérir des compétences théoriques et techniques pour juger de l’adéquation entre un problème et une solution algorithmique possible. Pour ce faire, vous étudierez des propriétés algorithmiques théoriques basées sur la complexité temporelle et spatiale.
Avant le cours
Pré-requis
Pour pouvoir commencer à travailler sur l’activité, vous devez remplir les conditions suivantes :
- Veuillez apporter votre propre ordinateur.
- Assurez-vous d’avoir une connexion réseau fonctionnelle.
Articles à étudier
Pour pouvoir commencer l’activité pratique efficacement, consultez les documentations sur les différentes complexités et les mécanismes d’algorithmique pour améliorer son code :
-
La complexité algorithmique est une notion fondamentale en informatique.
-
La complexité algorithmique est une notion fondamentale en informatique.
-
Ces quiz sont là pour vous permettre de vérifier que vous avez compris les articles à étudier.
Contenu optionnel
Vous pouvez aussi consulter les ressources supplémentaires suivantes pour approfondir vos connaissances :
-
Nous présentons la structure de données appelée "arbre binaire de recherche" ("Binary Search Tree", BST).
-
Dans cet article, nous introduisons les algorithmes randomisés, qui utilisent l'aléa pour prendre des décisions, ce qui entraîne des variations potentielles dans l'exécution et le résultat entre différentes exécutions avec la même entrée.
Pendant le cours
Quiz Wooclap
Commencez par effectuer le quiz Wooclap de la session avec votre encadrant(e) pour vérifier que vous disposez des connaissances nécessaires pour aborder sereinement les activités pratiques.
Activité pratique
-
Dans cette partie, nous vous proposons de travailler sur l'analyse de plusieurs fonctions, allant de structures simples à des processus récursifs plus complexes.
Après le cours
Terminer l’activité pratique
Avant la prochaine séance, vous devez :
- Revoir le contenu des articles ci-dessus.
Préparer la prochaine séance
De plus, vous devez :
- Vérifier la section « Avant le cours » de la prochaine séance, et vous assurer d’avoir tout fait pour la préparer.