# Algorithmique I

## Objectifs d'apprentissage 

Le **plan d'études** pour l'informatique en tant que discipline obligatoire à l'École de maturité propose les contenus suivants pour l'introduction à l'algorithmique (ici *Algorithmique I*) : 

- Décomposition d’un problème
- Algorithmes classiques
- Conception d’algorithmes simples

En lien avec le plan d'études, nous avons identifié les **objectifs d'apprentissage** suivants qui sont abordés dans un ou plusieurs chapitres :

- Résoudre un problème en décomposant une solution en étapes (chapitre Les algorithmes)
- Intégrer la pluralité des algorithmes (chapitre Trie, cherche et trouve)
- Formaliser une solution sous forme d’algorithme (chapitre Trie, cherche et trouve)
- Implémenter un algorithme sous forme de programme (chapitre Des algorithmes aux programmes)

Nous avons compilé une liste d'*algorithmes classiques* (voir ci-dessous), ce qui fait apparaitre 2 grandes classes d'algorithmes classiques, les **algorithmes de tri** et les **algorithmes de graphes**. Comme il est impossible de tout aborder et prenant en considération le niveau de mathématiques des élèves de 1ère année, nous avons privilégié dans un premier temps une entrée par les graphes.

### Algorithmes classiques

**Algorithmes de recherche**
<ul>
<li>Recherche binaire ou dichotomique</li>
<li>Recherche linéaire</li>
<li>Recherche dans une table de hachage</li>
<li>Algorithmes de tri</li>
<li>Tri par insertion</li>
<li>Tri par sélection</li>
<li>Tri à bulles</li>
<li>Tri par fusion</li>
<li>Tri rapide</li>
<li>Tri par tas</li>
<li>Tri stupide</li>
</ul>

**Algorithmes de graphes**
<ul>
<li>BFS ou algorithme de parcours en largeur (Parcours de graphe)</li> 
<li>DFS ou algorithme de parcours en profondeur (Parcours de graphe)</li>
<li>Prim (Arbre couvrant minimal)</li>
<li>Kruskal (Arbre couvrant minimal)</li>
<li>Dijkstra (Recherche d’un plus court chemin)</li> 
<li>A* (Recherche d’un plus court chemin)</li> 
<li>Bellman-Ford (Recherche d’un plus court chemin)</li>
<li>Floyd-Warshall (Recherche d’un plus court chemin)</li>
<li>Tri topologique</li>
<li>Welsh-Powell (Coloration de graphe)</li>
<li>Kosaraju (Composantes fortement connexes)</li>
</ul>

**Autres algorithmes classiques**
<ul>
<li>Conversion entre bases</li>
<li>Codage de Huffman</li>
<li>Codage de Hamming</li>
<li>PageRank</li>
<li>Automates cellulaires</li>
<li>Simulation de Monte-Carlo / Metropolis</li>
<li>Test de Miller-Rabin pour les grand nombres premiers</li>
<li>Algorithmes de cryptographie à clé publique (RSA, Diffie-Hellman, EL Gamal, …)</li>
</ul>