# 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

<ul>
<b><li>Algorithmes de force brute</li>
<li>Algorithmes gloutons</li>
<li>Heuristiques</li>
<li>Diviser pour régner</li>
<li>Récursivité</li></b>
<li>Programmation dynamique</li>
<li>Algorithmes génétiques</li>
<li>Algorithmes neuronaux</li>
</ul>


### Problèmes célèbres

<ul>
<b><li>Problème du sac à dos</li>
<li>Problème du voyageur de commerce</li> 
<li>Problème du rendu de monnaie</li>
<li>P=NP</li>
<li>Plus court chemin</li></b>
<li>Arbre couvrant minimal</li>
<li>Chemins euleriens et hamiltoniens</li>
<li>Max-flow min-cut</li> 
<li>Problème des mariages</li> 
<li>Problème des secrétaires</li>
<li>K-SAT</li>
<li>Set/vertex/edge cover</li>
<li>Maximum independent set</li>
<li>Maximum clique</li>
<li>Coloration de graphes</li>
</ul>