Algorithmes

Introduction

Nous avons déjà vu une partie des algorithmes dans le cours sur les graphes et les arbres. Nous verrons donc ici les algorithmes qui ne concernent pas directement les graphes :

diviser pour régner
programmation dynamique
Boyer-Moore (recherche textuelle)

Parties du programme abordées

Les parties encadrées en rouge sont « prépondérentes ». Vous pourrez choisir 3 exercices sur 5 lors de l'épreuve en ayant vu que les parties prépondérentes.

Contenus	Capacités attendues	Commentaires
Méthode « diviser pour régner ».	Écrire un algorithme utilisant la méthode « diviser pour régner ».	La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple. L’exemple du tri fusion permet également d’exploiter la récursivité et d’exhiber un algorithme de coût en n*log(n) dans les pires des cas.
Programmation dynamique.	Utiliser la programmation dynamique pour écrire un algorithme.	Les exemples de l’alignement de séquences ou du rendu de monnaie peuvent être présentés. La discussion sur le coût en mémoire peut être développée.
Recherche textuelle.	Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte.	L’intérêt du prétraitement du motif est mis en avant. L’étude du coût, difficile, ne peut être exigée.