Algorithmique II¶
Objectifs d’apprentissage¶
Le plan d’études pour l’informatique en tant que discipline obligatoire à l’École de maturité propose les contenus suivants pour la partie algorithmique de la thématique « Algorithmique et programmation » (ici Algorithmique II) :
Terminaison et complexité des algorithmes
Solutions heuristiques
Stratégies de résolution de problèmes complexes
En lien avec le plan d’études, nous avons identifié les objectifs d’apprentissage suivants qui sont abordés dans un ou plusieurs chapitres :
Comparer différentes solutions algorithmiques (chapitre Terminaison et complexité)
Évaluer la complexité d’un algorithme (chapitre Algorithmes de recherche)
Connaître une stratégie de résolution de problème complexe (chapitre Algorithmes de recherche)
Évaluer la qualité d’une solution algorithmique (chapitre Heuristiques)
En lien avec le dernier item du plan d’études, nous avons compilé une liste de stratégies de résolution de problèmes (voir ci-dessous), et de problèmes célèbres. Les stratégies et problèmes abordés dans la partie Algorithmique II sont affichés en gras.
Stratégies de résolution de problème¶
- Algorithmes de force brute
- Algorithmes gloutons
- Heuristiques
- Diviser pour régner
- Récursivité
- Programmation dynamique
- Algorithmes génétiques
- Algorithmes neuronaux
Problèmes célèbres¶
- Problème du sac à dos
- Problème du voyageur de commerce
- Problème du rendu de monnaie
- P=NP
- Plus court chemin
- Arbre couvrant minimal
- Chemins euleriens et hamiltoniens
- Max-flow min-cut
- Problème des mariages
- Problème des secrétaires
- K-SAT
- Set/vertex/edge cover
- Maximum independent set
- Maximum clique
- Coloration de graphes